Abstract
We consider prior-free auctions for revenue and welfare maximization when agents have a common budget. The abstract environments we consider are ones where there is a downward-closed and symmetric feasibility constraint on the probabilities of service of the agents. These environments include position auctions where slots with decreasing click-through rates are auctioned to advertisers. We generalize and characterize the envy-free benchmark from Hartline and Yan [2011] to settings with budgets and characterize the optimal envy-free outcomes for both welfare and revenue. We give prior-free mechanisms that approximate these benchmarks. A building block in our mechanism is a clinching auction for position auction environments. This auction is a generalization of the multi-unit clinching auction of Dobzinski et al. [2008] and a special case of the polyhedral clinching auction of Goel et al. [2012]. For welfare maximization, we show that this clinching auction is a good approximation to the envy-free optimal welfare for position auction environments. For profit maximization, we generalize the random sampling profit extraction auction from Fiat et al. [2002] for digital goods to give a 10.0-approximation to the envy-free optimal revenue in symmetric, downward- closed environments. Even without budgets this revenue maximization question is of interest and we obtain an improved approximation bound of 7.5 (from 30.4 by Ha and Hartline [2012]).
Original language | English (US) |
---|---|
Title of host publication | EC 2013 - Proceedings of the 14th ACM Conference on Electronic Commerce |
Pages | 287-304 |
Number of pages | 18 |
State | Published - Jul 10 2013 |
Event | 14th ACM Conference on Electronic Commerce, EC 2013 - Philadelphia, PA, United States Duration: Jun 16 2013 → Jun 20 2013 |
Other
Other | 14th ACM Conference on Electronic Commerce, EC 2013 |
---|---|
Country | United States |
City | Philadelphia, PA |
Period | 6/16/13 → 6/20/13 |
Keywords
- Budget
- Envy-free
- Mechanism design
- Prior-free
ASJC Scopus subject areas
- Software
- Computer Networks and Communications
- Computer Science Applications