Prior-independent multi-parameter mechanism design

Nikhil Devanur*, Jason D Hartline, Anna Karlin, Thach Nguyen

*Corresponding author for this work

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

23 Scopus citations

Abstract

In a unit-demand multi-unit multi-item auction, an auctioneer is selling a collection of different items to a set of agents each interested in buying at most unit. Each agent has a different private value for each of the items. We consider the problem of designing a truthful auction that maximizes the auctioneer's profit in this setting. Previously, there has been progress on this problem in the setting in which each value is drawn from a known prior distribution. Specifically, it has been shown how to design auctions tailored to these priors that achieve a constant factor approximation ratio [2, 5]. In this paper, we present a prior-independent auction for this setting. This auction is guaranteed to achieve a constant fraction of the optimal expected profit for a large class of, so called, "regular" distributions, without specific knowledge of the distributions.

Original languageEnglish (US)
Title of host publicationInternet and Network Economics - 7th International Workshop, WINE 2011, Proceedings
PublisherSpringer Verlag
Pages122-133
Number of pages12
ISBN (Print)9783642255090
DOIs
StatePublished - 2011
Event7th International Workshop on Internet and Network Economics, WINE 2011 - Singapore, Singapore
Duration: Dec 11 2011Dec 14 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7090 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other7th International Workshop on Internet and Network Economics, WINE 2011
CountrySingapore
CitySingapore
Period12/11/1112/14/11

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Prior-independent multi-parameter mechanism design'. Together they form a unique fingerprint.

Cite this