Strategy-Proofness and Pivotal Voters: A Direct Proof of the Gibbard-Satterthwaite Theorem
给出吉巴德-萨特斯韦特定理的一个直接证明，强调关键个体在操纵投票中的作用，证明过程技术简单且直观，适合对社会选择理论中防策略性机制感兴趣的读者。
This paper presents a proof of the Gibbard-Satterthwaite theorem. The importance of the theorem itself has been widely recognized, and there already exist several alternative proofs. The present one is offered because it is technically simple, direct, and emphasizes the role of pivotal individuals in the manipulation of voting schemes. Some indirect proofs of the theorem rely on the connections between voting schemes and social welfare functions, and one interesting corollary of such proofs is to provide new arguments in behalf of Arrow's condition of independence of irrelevant alternatives. Yet, a direct proof has the advantage of showing the complete independence of the manipulation phenomena from any requirement of consistency in choice under varying sets of alternatives. Also, our proof emphasizes the role of pivotal individuals in manipulation. A classical approach in social choice theory is to concentrate on the global distribution of power among groups of agenits, i.e., on the ability of coalitions to impose outcomes regardless of the preferences of agents not in the coalition. For example, standard proofs of Arrow's Theorem concentrate on decisive coalitions, to end up proving that there must exist one such coalition containing a single individual, the dictator. Our approach concentrates on the local distribution of power among single agents, i.e., on the ability of each single individual to determine the social outcome, given the preferences of all other members of society.' This approach may be more intuitive for some readers; moreover, it closely parallels the work on incentives in economic environments with public goods and suggests a possible way to unify results which have been obtained from different initial specifications. We do not attempt such a rejoinder here, but let us observe the following. For certain environments with public goods, where transfer payments make perfect sense, nontrivial strategy-proof mechanisms can be obtained by appropriately taxing pivotal agents so that they take into account the costs that their actions impose upon others.2 One explanation for the nonexistence of equivalent mechanisms in our case is that the environment, as specified, does not allow for a corresponding procedure whereby different costs to individuals could be attached to different acts of preference revelation.