Evaluating the Performance of Approximation Mechanisms under Budget Constraints
Juan Carlos Carbajal, Ahuva Mu’alem · 2026
Read Evaluating the Performance of Approximation Mechanisms under Budget Constraints by Juan Carlos Carbajal, Ahuva Mu’alem (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-14120.txt.
Description
Juan Carlos Carbajal and one co-author study a 2026 arXiv problem in auction design with budget limits. A seller holds one object, while a buyer privately knows both value and budget. Private budgets make the classic monopoly problem hard to solve exactly, so the paper tests simple approximation mechanisms against optimal ones.
Three measures judge performance: the guaranteed share of optimal revenue, the gain from relaxation, and a revenue non-monotonicity gap. For bounded distributions, simple menus of polylogarithmic size can approach optimal revenue closely, even with correlated values and budgets. For unbounded support, and even some bounded cases, no finite or sublinear menu guarantees any positive revenue share, even under independence.
Catalog record
| CREATOR | Juan Carlos Carbajal, Ahuva Mu’alem |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 111 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-14120