141. Investment Guarantees for Inner Approximations
Invited abstract in session TA-2: Combinatorial Optimization, stream Discrete and Combinatorial Optimization.
Thursday, 8:45-10:15Room: H4
Authors (first author is the speaker)
| 1. | Sven de Vries
|
| FB IV - Mathematik, Uni Trier | |
| 2. | Stephen Raach
|
| Trier University | |
| 3. | Rakesh V. Vohra
|
| Department of Economics, University of Pennsylvania |
Abstract
Akbarpour, Kominers, Li, Li, and Milgrom [2023] provided a characterization
for when an incentive-compatible approximate mechanism’s worst-case allocative
and investment guarantees coincide. The characterization, however, fails in some
natural settings, such as multi-unit demand with linear utilities. In this case we pro-
pose an inner approximation framework that yields an incentive-compatible greedy
mechanism whose allocative and investment guarantees coincide.
Keywords
- Approximation Algorithms
- Auctions / Competitive Bidding
Status: accepted
Back to the list of papers