Please use this identifier to cite or link to this item: http://hdl.handle.net/2440/87289
Type: Conference paper
Title: Worst-case efficiency ratio in false-name-proof combinatorial auction mechanisms
Author: Iwasaki, A.
Conitzer, V.
Omori, Y.
Sakurai, Y.
Todo, T.
Guo, M.
Yokoo, M.
Citation: AAMAS 2010 - The 9th International Conference on Autonomous Agents and Multiagent Systems May 10-14, 2010, Toronto Canada, Conference Proceedings, vol. 1, 2010 / van der Hoek, W., Kaminka, G., Lesperance, Y., Luck, M., Sen, S. (ed./s), pp.633-640
Publisher: International Foundation for Autonomous Agents and Multiagent Systems
Publisher Place: USA
Issue Date: 2010
ISBN: 9780982657119
Conference Name: 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS) (10 May 2010 - 14 May 2010 : Toronto, Canada)
Statement of
Responsibility: 
Atsushi Iwasaki, Vincent Conitzer, Yoshifusa Omori, Yuko Sakurai, Taiki Todo, Mingyu Guo and Makoto Yokoo
Abstract: This paper analyzes the worst-case efficiency ratio of false-name-proof combinatorial auction mechanisms. False-name-proofness generalizes strategy-proofness by assuming that a bidder can submit multiple bids under fictitious identifiers. Even the well-known Vickrey-Clarke-Groves mechanism is not false-name-proof. It has previously been shown that there is no false-name-proof mechanism that always achieves a Pareto efficient allocation. Consequently, if false-name bids are possible, we need to sacrifice efficiency to some extent. This leaves the natural question of how much surplus must be sacrificed. To answer this question, this paper focuses on worst-case analysis. Specifically, we consider the fraction of the Pareto efficient surplus that we obtain and try to maximize this fraction in the worst-case, under the constraint of false-name-proofness. As far as we are aware, this is the first attempt to examine the worst-case efficiency of false-name-proof mechanisms. We show that the worst-case efficiency ratio of any false-name-proof mechanism that satisfies some apparently minor assumptions is at most 2/(m + 1) for auctions with m different goods. We also observe that the worst-case efficiency ratio of existing false-name-proof mechanisms is generally 1/m or 0. Finally, we propose a novel mechanism, called the adaptive reserve price mechanism that is false-name-proof when all bidders are single-minded. The worst-case efficiency ratio is 2/(m + 1), i.e., optimal.
Keywords: Mechanism design; Combinatorial auctions; Worst-case analysis; False-name-proofness
Rights: © 2010 International Foundation for Autonomous Agents and Multiagent Systems
RMID: 0020135791
Appears in Collections:Computer Science publications

Files in This Item:
There are no files associated with this item.


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.