Prior-free auctions for budgeted agents

Nikhil R. Devanur, Bach Q. Ha, Jason D Hartline

Research output: Chapter in Book/Report/Conference proceedingConference contribution

26 Scopus citations


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 languageEnglish (US)
Title of host publicationEC 2013 - Proceedings of the 14th ACM Conference on Electronic Commerce
Number of pages18
StatePublished - Jul 10 2013
Event14th ACM Conference on Electronic Commerce, EC 2013 - Philadelphia, PA, United States
Duration: Jun 16 2013Jun 20 2013


Other14th ACM Conference on Electronic Commerce, EC 2013
Country/TerritoryUnited States
CityPhiladelphia, PA


  • Budget
  • Envy-free
  • Mechanism design
  • Prior-free

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications
  • Computer Science Applications


Dive into the research topics of 'Prior-free auctions for budgeted agents'. Together they form a unique fingerprint.

Cite this