Strategy-Proofness

Strategy-proofness requires that truth-telling is a (weakly) dominant strategy for all individuals in a collective decision making process. We introduce the concept of robust strategy-proofness on a domain which imposes a stronger requirement for the preferences all other agents have. While in general a strictly stronger requirement, our main result shows that for all tops-only social choice functions strategy-proofness and robust strategy-proofness on minimally rich domains are equivalent.

 

One important appeal of strategy-proofness is the robustness that it implies. Under a strategy-proof voting rule, every individual has an optimal strategy independently of the behavior of all other voters. In particular, optimal play is robust with respect to the beliefs voters may have about the type and the behavior of the other voters. Following Blin and Satterthwaite (1977), let us call this property "belief-independence". In this paper, we give a number of examples of voting rules that are belief-independent but not strategy-proof. However, we also show that belief-independence implies strategy-proofness under a few natural additional conditions. We also introduce a novel condition of robust strategy-proofness which strengthens strategy-proofness by requiring that no voter can benefit by submitting any unrestricted preference ordering given any unrestricted preference profile for all other voters. Robust strategy-proofness is shown to be a strictly stronger property of a voting rule than the usual notion of strategy-proofness. However, under natural additional conditions the two properties are equivalent.

Michael Müller: michael.mueller∂kit.edu