Optimal false-name-proof single-item redistribution mechanisms

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.