12 papers
Harmonic Ranking for Edge-Weighted Oblivious Matching
Bo Peng, Zhihao Gavin Tang
We study edge-weighted oblivious bipartite matching. The weight of every potential edge is known, but its existence is revealed only when the edge is probed, and a successful probe…
Random-Order Online Facility Location Beyond Uniform Opening Costs
Bo Peng, Zhihao Gavin Tang
We study online metric facility location in the random-order model with arbitrary positive opening costs. A finite set of candidate facilities and their costs is known in advance,…
EconCSLib: A Lean Library for Computational Economics and AI-Assisted Research
Xiaohui Bei, Jiajun Ma, Zhan Jing +2
Mathematical formalization uses interactive theorem provers to turn informal mathematical statements into machine-checkable artifacts. The success of mathlib, a large collaborative…
Optimal Pricing with Unreliable Signals
Zhihao Gavin Tang, Yixin Tao, Shixin Wang
We study a single-buyer pricing problem with unreliable side information, motivated by the increasing use of AI-assisted decision-making and LLM-based predictions. The seller obser…
Robust Mechanism Design with Anonymous Information
Zhihao Gavin Tang, Shixin Wang
In practice, auction data are often endogenously censored and anonymous, revealing only limited outcome statistics rather than full bid profiles. We study robust auction design whe…
Optimal Competitive Ratio of Two-sided Online Bipartite Matching
Zhihao Gavin Tang
We establish an optimal upper bound (negative result) of on the competitive ratio of the fractional version of online bipartite matching with two-sided vertex arrivals…
Pricing with a Hidden Sample
Zhihao Gavin Tang, Yixin Tao, Shixin Wang
We study prior-independent pricing for selling a single item to a single buyer when the seller observes only a single sample from the valuation distribution, while the buyer knows…
Combinatorial Philosopher Inequalities
Enze Sun, Zhihao Gavin Tang, Yifan Wang
In online combinatorial allocation, agents arrive sequentially and items are allocated in an online manner. The algorithm designer only knows the distribution of each agent's valua…
Online Stochastic Matching with Unknown Arrival Order: Beating against the Online Optimum
Enze Sun, Zhihao Gavin Tang, Yifan Wang
We study the online stochastic matching problem. Against the offline benchmark, Feldman, Gravin, and Lucier (SODA 2015) designed an optimal -competitive algorithm. A recent li…
Revisiting Ranking for Online Bipartite Matching with Random Arrivals: the Primal-Dual Analysis
Bo Peng, Zhihao Gavin Tang
We revisit the celebrated Ranking algorithm by Karp, Vazirani, and Vazirani (STOC 1990) for online bipartite matching under the random arrival model, that is shown to be -co…
Setting Targets is All You Need:Improved Order Competitive Ratio for Online Selection
Liyan Chen, Nuozhou Sun, Zhihao Gavin Tang
There is a rising interest for studying the online benchmark as an alternative of the classical offline benchmark in online stochastic settings. Ezra, Feldman, Gravin, and Tang (SO…
Optimal Robust Contract Design
Bo Peng, Zhihao Gavin Tang
We consider the robust contract design problem when the principal only has limited information about the actions the agent can take. The principal evaluates a contract according to…