False-name-proof combinatorial auction design via single-minded decomposition

Dengji Zhao, Siqi Luo, Taiki Todo, Makoto Yokoo

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

3 Citations (Scopus)


This paper proposes a new approach to building false-name-proof (FNP) combinatorial auctions from those that are FNP only with single-minded bidders, each of whom requires only one particular bundle. Under this approach, a general bidder is decomposed into a set of single-minded bidders, and after the decomposition the price and the allocation are determined by the FNP auctions for single-minded bidders. We first show that the auctions we get with the single-minded decomposition are FNP if those for single-minded bidders satisfy a condition called PIA. We then show that another condition, weaker than PIA, is necessary for the decomposition to build FNP auctions. To close the gap between the two conditions, we have found another sufficient condition weaker than PIA for the decomposition to produce strategy-proof mechanisms. Furthermore, we demonstrate that once we have PIA, the mechanisms created by the decomposition actually satisfy a stronger version of false-name-proofness, called false-name-proofness with withdrawal.

Original languageEnglish
Title of host publicationECAI 2014 - 21st European Conference on Artificial Intelligence, Including Prestigious Applications of Intelligent Systems, PAIS 2014, Proceedings
EditorsTorsten Schaub, Gerhard Friedrich, Barry O'Sullivan
PublisherIOS Press
Number of pages6
ISBN (Electronic)9781614994183
Publication statusPublished - Jan 1 2014
Event21st European Conference on Artificial Intelligence, ECAI 2014 - Prague, Czech Republic
Duration: Aug 18 2014Aug 22 2014

Publication series

NameFrontiers in Artificial Intelligence and Applications
ISSN (Print)0922-6389


Other21st European Conference on Artificial Intelligence, ECAI 2014
Country/TerritoryCzech Republic

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence


Dive into the research topics of 'False-name-proof combinatorial auction design via single-minded decomposition'. Together they form a unique fingerprint.

Cite this