Please use this identifier to cite or link to this item: http://hdl.handle.net/2440/108242
Type: Conference paper
Title: Optimal false-name-proof single-item redistribution mechanisms
Author: Tsuruta, S.
Oka, M.
Todo, T.
Kawasaki, Y.
Guo, M.
Sakurai, Y.
Yokoo, M.
Citation: Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems, 2014 / vol.1, pp.221-228
Publisher: International Foundation for Autonomous Agents and Multiagent Systems
Issue Date: 2014
ISBN: 9781634391313
Conference Name: 13th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2014) (05 May 2014 - 09 May 2014 : Paris, France)
Statement of
Responsibility: 
Shunsuke Tsuruta, Masaaki Oka, Taiki Todo, Yujiro Kawasaki, Mingyu Guo, Yuko Sakurai, and Makoto Yokoo
Abstract: Although the celebrated Vickrey auction is strategy-proof and guaranteed to achieve an efficient allocation in a singleobject auction, if there exists no outside party (i.e., a seller or an auctioneer) with the right to collect the payment, the collected payment will be wasted. Redistribution mechanisms try to redistribute the payment to participating agents as much as possible without violating strategy-proofness. However, when a losing agent can obtain part of the payment, she may have an incentive to participate under multiple identities and receive a greater share of the redistribution. Our goal is to develop false-name-proof redistribution mechanisms that are robust against such manipulations. First, we prove that no mechanism simultaneously satisfies falsename- proofness and allocative efficiency, except for the Vickrey auction. Next, we propose a class of false-name-proof redistribution mechanisms, which are characterized by several parameters. We show that each mechanism in the class is not dominated by any other false-name-proof mechanism in terms of social welfare. Precisely, by choosing these parameters appropriately, all instances of this class are guaranteed to achieve at least the same amount of social welfare obtained by any false-name-proof mechanism. Furthermore, we formalize an optimization problem that determines appropriate parameter values based on prior information about participating agents.
Keywords: Mechanism design, redistribution, false-name-proofness
Description: Session A2 - Algorithmic Game Theory I
Rights: Copyright © 2014, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.
RMID: 0030025149
Appears in Collections:Computer Science publications

Files in This Item:
File Description SizeFormat 
RA_hdl_108242.pdfRestricted Access413.53 kBAdobe PDFView/Open


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