Strategy-proof social choice correspondences. (Q1347821)

Gibbard and Satterthwaite showed that any strategy proof and Pareto optimal social choice rule is dictatorial, assuming the number \(n\) of individuals is at least two and the number of alternatives is at least three. A social choice correspondence is usually defined as an aggregation function that assigns to each \(n\)-tuple of (linear) orderings of the alternatives a set of alternatives. In this paper the authors consider social choice correspondences that assign to each \(n\)-tuple of orderings of non-empty sets of alternatives a non-empty set of alternatives. This allows them to give an unambiguous and straightforward definition of strategy proofness. The authors consider two natural domain restrictions. An individual ordering \(R_i\) over the non-empty subsets of the set of alternatives is called conditionally expected utility consistent (CEUC) if the following holds: \(X\) \(R_i\) \(Y\) iff the conditional expected utility associated with \(X\) is higher than the conditional expected utility associated with \(Y\). And \(R_i\) is CEUC with Equal Probabilities (CEUCEP) if in addition \(i\) assigns an equal probability to every alternative. Let \(\mathcal{D}\)\(_U\) be the set of all CEUC orderings and let \(\mathcal{D}\)\(_E\) be the set of all CEUCEP orderings of the non-empty subsets of the set of alternatives. Assuming that all singletons are in the range of the rule, the authors show that on the domain \(\mathcal{D}\)\(_U\) the only strategy proof social choice correspondence satisfying unanimity is the dictatorial one; and that on the domain \(\mathcal{D}\)\(_E\) the only strategy proof social choice correspondences satisfying unanimity are dictatorial or bi-dictatorial (i.e., it chooses the union of the best elements of two fixed agents). The proofs of these two results require not less than nine pages. But they show that the results of Gibbard and Satterthwaite are remarkably robust: they also hold under these two natural domain restrictions.