Consistent social choice functions and systems of distinct representatives (Q1062886)

According to \textit{B. Peleg} [Econometrica 46, 153-161 (1978; Zbl 0373.90002)] a social choice function is exactly and strongly consistent if and only if for any profile of preferences \((R^ 1,R^ 2,..,R^ n)\) there is a profile \((Q^ 1,Q^ 2,..,Q^ n)\) such that the latter profile gives the same social outcome as \((R^ 1,R^ 2,...,R^ n)\) and no coalition can obtain a social choice preferable to each of its members if the rest of the group maintains the \(Q^ i\) preferences. The profile \((Q^ 1,Q^ 2,...,Q^ n)\) is called an equilibrium point of the social choice function relative to \((R^ 1,R^ 2,...,R^ n).\) Peleg has proposed several social choice functions which are exactly and strongly consistent. They are based on a procedure of successive elimination of most disliked alternatives [see also \textit{B. Peleg}, ''Game theoretic analysis of voting in committees'', chapter 5 (1984; Zbl 0563.90002)]. The present paper modifies Peleg's functions and describes them in terms of ''systems of distinct representatives''. Let \(N=\{1,2,...,n\}\) denote a set of n individuals. Let X denote a set of alternatives. Let L(X) denote the set of linear orders on X. A coalition is a subset of N. Definition 1: A constrained social choice function (CSCF) is a pair consisting of a domain \(D\subset L(X)\) and a function F from \(D^ N=D\times D\times...\times D\) to X. Definition 2: Let \(n\geq m-1\) and \(| X| =m\), \(\beta\) : \(X\to N\) be such that \(\sum_{x\in X}\beta (x)=n+1\). Then a point y is \(\beta\)-feasible relative to \((R^ 1,R^ 2,..,R^ n)\subset (L(x))^ N\) if and only if there exists a sequence \(C_ 1\), \(C_ 2,...,C_{m-1}\) of coalitions and a sequence \(x_ 1\), \(x_ 2,...,x_{m-1}\) of distinct alternatives such that (1) \(| C_ i| =\beta (x_ i)\) for each i; (2) for each i, for all \(j\in C_ i\), for all \(z\in X\setminus \{x_ 1,x_ 2,...,x_{i-1}\}\), \(zR^ jx_ i\); (3) for all \(i\neq j\), \(C_ i\cap C_ j=\emptyset\); (4) for all i, \(y\neq x_ i\). Here \(| C_ i|\) denotes the cardinality of the coalition \(C_ i\). Definition 3: A CSCF is a \(\beta\)-elimination method if and only if \(F(R^ 1,R^ 2,..,R^ n)\) is \(\beta\)-feasible relative to \((R^ 1,R^ 2,..,R^ n)\) for all \((R^ 1,R^ 2,..,R^ n)\in D^ N\) and \(D\subset L(X).\) Theorem 1. Any \(\beta\)-elimination is strongly and exactly consistent. Definition 4. Let \(U_ 1\), \(U_ 2,...,U_ n\) be a collection of subsets of a set U. A system of distinct representatives (SDR) is a sequence \(v_ 1\), \(v_ 2,...,v_ n\) of distinct elements of U such that \(v_ i\in U_ i\) for each i. Theorem 2. Let \(| X| =n+1\) and let \(R^ 1\), \(R^ 2,...,R^ n\) be a sequence of linear orders of X. Let \(y\in X\) and let \(U_ i=\{x\in X:\) \(x\neq y\) and \(yR^ ix\}\). Let \(\beta (x)=1\) for all \(i\neq j\). Then y is \(\beta\)-feasible if and only if the system \(U_ i\) has an SDR. The authors emphasize that there exist rapid algorithms for computing their social choice functions. They also show that these functions are monotonic.