Skip to main content

Worst-case efficiency ratio in false-name-proof combinatorial auction mechanisms

Publication ,  Conference
Iwasaki, A; Conitzer, V; Omori, Y; Sakurai, Y; Todo, T; Guo, M; Yokoo, M
Published in: Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
January 1, 2010

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 falso-nanic-proof when all bidders are single-minded. The worst-case efficiency ratio is 2/(m + 1), i.e., optimal. Copyright © 2010, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.

Duke Scholars

Published In

Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS

EISSN

1558-2914

ISSN

1548-8403

ISBN

9781617387715

Publication Date

January 1, 2010

Volume

2

Start / End Page

633 / 640
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Iwasaki, A., Conitzer, V., Omori, Y., Sakurai, Y., Todo, T., Guo, M., & Yokoo, M. (2010). Worst-case efficiency ratio in false-name-proof combinatorial auction mechanisms. In Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS (Vol. 2, pp. 633–640).
Iwasaki, A., V. Conitzer, Y. Omori, Y. Sakurai, T. Todo, M. Guo, and M. Yokoo. “Worst-case efficiency ratio in false-name-proof combinatorial auction mechanisms.” In Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, 2:633–40, 2010.
Iwasaki A, Conitzer V, Omori Y, Sakurai Y, Todo T, Guo M, et al. Worst-case efficiency ratio in false-name-proof combinatorial auction mechanisms. In: Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS. 2010. p. 633–40.
Iwasaki, A., et al. “Worst-case efficiency ratio in false-name-proof combinatorial auction mechanisms.” Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, vol. 2, 2010, pp. 633–40.
Iwasaki A, Conitzer V, Omori Y, Sakurai Y, Todo T, Guo M, Yokoo M. Worst-case efficiency ratio in false-name-proof combinatorial auction mechanisms. Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS. 2010. p. 633–640.

Published In

Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS

EISSN

1558-2914

ISSN

1548-8403

ISBN

9781617387715

Publication Date

January 1, 2010

Volume

2

Start / End Page

633 / 640