Evaluating the Performance of Approximation Mechanisms under Budget Constraints
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914514829574144 |
|---|---|
| author | Carbajal, Juan Carlos Mualem, Ahuva |
| author_facet | Carbajal, Juan Carlos Mualem, Ahuva |
| contents | We study revenue maximization in a buyer-seller setting where the seller has a single object and the buyer has both a private valuation and a private budget. Private budgets complicate the classic single-product monopoly problem, making optimal mechanisms difficult to characterize. To address this, we evaluate the robust performance of approximation mechanisms relative to optimal mechanisms using three performance measures: the guaranteed fraction of optimal revenue, the maximal value of relaxation, and a revenue non-monotonicity gap. Our analysis reveals sharp contrasts. For distributions with bounded support, simple mechanisms with polylogarithmic menu size can approximate optimal revenue arbitrarily well, even when valuations and budgets are correlated. By contrast, for distributions with unbounded support, and even for bounded distributions concentrated in the unit square, no simple mechanism -- or any mechanism with a finite or sublinear menu -- can guarantee a positive fraction of optimal revenue. In particular, no finite-menu mechanism guarantees any positive fraction even under independence. We also show unbounded revenue gains from certain relaxations under negative correlation and identify cases of revenue non-monotonicity. Overall, our results show that approximation guarantees with private budgets are fragile, revealing fundamental limits to simplicity and robustness in mechanism design. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_14120 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Evaluating the Performance of Approximation Mechanisms under Budget Constraints Carbajal, Juan Carlos Mualem, Ahuva Computer Science and Game Theory We study revenue maximization in a buyer-seller setting where the seller has a single object and the buyer has both a private valuation and a private budget. Private budgets complicate the classic single-product monopoly problem, making optimal mechanisms difficult to characterize. To address this, we evaluate the robust performance of approximation mechanisms relative to optimal mechanisms using three performance measures: the guaranteed fraction of optimal revenue, the maximal value of relaxation, and a revenue non-monotonicity gap. Our analysis reveals sharp contrasts. For distributions with bounded support, simple mechanisms with polylogarithmic menu size can approximate optimal revenue arbitrarily well, even when valuations and budgets are correlated. By contrast, for distributions with unbounded support, and even for bounded distributions concentrated in the unit square, no simple mechanism -- or any mechanism with a finite or sublinear menu -- can guarantee a positive fraction of optimal revenue. In particular, no finite-menu mechanism guarantees any positive fraction even under independence. We also show unbounded revenue gains from certain relaxations under negative correlation and identify cases of revenue non-monotonicity. Overall, our results show that approximation guarantees with private budgets are fragile, revealing fundamental limits to simplicity and robustness in mechanism design. |
| title | Evaluating the Performance of Approximation Mechanisms under Budget Constraints |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2602.14120 |