غلبه truthtelling و ساختار شبکه تعادل نش
Abstract
1- Introduction
2- Model and definitions
3- Lattice structure of Nash equilibrium allocations
4- Discussion: robustness checks and extensions
5- Conclusion
References
Abstract
Truthtelling is often viewed as focal in the direct mechanisms associated with strategy-proof decision rules. Yet many direct mechanisms also admit Nash equilibria whose outcomes differ from the one under truthtelling. We study a model that has been widely discussed in the mechanism design literature (Sprumont, 1991) and whose strategy-proof and efficient rules typically suffer from the aforementioned deficit. We show that when a rule in this class satisfies the mild additional requirement of replacement monotonicity, the set of Nash equilibrium allocations of its preference revelation game is a complete lattice with respect to the order of Pareto dominance. Furthermore, the supremum of the lattice is the one obtained under truthtelling. In other words, truthtelling Pareto dominates all other Nash equilibria. For the rich subclass of weighted uniform rules, the Nash equilibrium allocations are, in addition, strictly Pareto ranked. We discuss the tightness of the result and some possible extensions.
Introduction
In the mechanism design literature, the single-peaked preference domain has played a central role. Most importantly, it paved a way out of the many impossibility results on the design of prior-free mechanisms. The celebrated Gibbard and Satterthwaite theorem (see Gibbard (1973) and Satterthwaite (1975)) showed the impossibility of designing efficient and strategy-proof rules that would escape the dictatorship predicament under arbitrary preferences. In contrast, within the confine of the single-peaked domain, possibility results emerge. In a pathbreaking paper, Moulin (1980) characterizes the class of generalized median voting rules when the feasible set is made of all points on a line. On the private goods front, Sprumont (1991) studies the problem of allocating a divisible and nondisposable good.1 Sprumont (1991) characterizes a remarkable rule: the uniform rule which is uniquely characterized down by efficiency, strategy-proofness and a fairness requirement. The Sprumont model has received a great deal of attention in the mechanism design literature, from alternative characterizations of the uniform rule (see e.g. Ching (1994), Thomson (1994a,b, 1995, 1997)), to the exploration of different families of rules (Barberà et al. (1997), Moulin (1999)), or the extensions of the model and the preference domain (see e.g. Adachi (2010), Bochet et al. (2013), Massó and Neme (2004) among others).2 In this paper, we show an unexpected property for a rich family of rules in the Sprumont model. We consider the largest class identified in the literature, the sequential allotment rules, characterized in Barberà et al. (1997) by the combination of efficiency, strategy-proofness and replacement monotonicity. Notice that each sequential allotment rule is fully implementable in dominant strategies by its direct revelation mechanism—this can be seen for instance following the results in Mizukami and Wakayama (2007).