A unified characterization of the randomized strategy-proof rules (Q2231399)

The main result of this interesting paper is Theorem 1: Let \(\mathcal{D}\) be a minimally rich generalized intermediate domain. Then an RSCF (random social choice function) \(\phi:\mathcal{D}^n \rightarrow \Delta A\) is unanimous and strategy-proof if and only if it is a TRM (tops-restricted random min-max) rule. This theorem is so interesting because the authors show that many domains of practical importance are generalized intermediate, among them: single-peaked domains, single-crossing domains, single-dipped domains, single-peaked domains on trees with top-set along a path, multi-peaked domains, Euclidean domains and intermediate domains. As corollaries of their result, they show that all the domains considered in this paper satisfy tops-onlyness and deterministic extreme point property. In section 5 they also analyze the structure of unanimous and strategy-proof RSCFs on domains containing weak preferences for which indifference can occur only at the top two positions. In what follows we shall restrict ourselves to the definitions of the notions in Theorem 1, i.e., the notion of a minimally rich generalized intermediate domain and the notion of an RSCF being a TRM rule; for the other notions see the paper itself. A preference relation \(P\) is single-peaked if it decreases as one goes far away (with respect to a given ordering \(\prec\) of the alternatives) in any particular direction from its peak (top-ranked alternative). A domain is single-peaked if each preference in it is single-peaked. A preference relation \(P\) satisfies the betweenness property with respect to an alternative \(a\) if for all \(b \in A\), \(b \neq a\), if \(a\) is between \(\tau(P)\) (the top-ranked alternative of \(P\)) and \(b\), then \(aPb\). And a domain \(\mathcal{D}\) satisfies the betweenness property with respect to an alternative \(a\) if each preference relation \(P\) in \(\mathcal{D}\) satisfies this property with respect to \(a\). Finally, a domain \(\mathcal{D}\) is generalized intermediate if it satisfies the betweenness property with respect to each alternative in \(\tau(\mathcal{D})\), where \(\tau(\mathcal{D})\) is the set of alternatives that appear as a top-ranked alternative in some preference relation \(P\) in \(\mathcal{D}\). For two preference relations \(P\) and \(P'\) in a given domain, \(P \sim P'\) means that \(P\) and \(P'\) differ only on the ranking of the top two alternatives. And a domain \(\mathcal{D}\) with \(\tau(\mathcal{D}) = \{b_1, \ldots, b_k\}\) satisfies the minimal richness property if for any two consecutive \(b_j\) and \(b_{j+1}\) in \(\tau(\mathcal{D})\) there are preference relations \(P\) in \(\mathcal{D}\) with \(b_j\) as top-ranked alternative and \(P'\) in \(\mathcal{D}\) with \(b_{j+1}\) as top-ranked alternative such that \(P \sim P'\). In Example 1 the authors illustrate these notions with a domain consisting of eight preference relations over 10 alternatives. By \(\Delta A\) we mean the set of all probability distributions over \(A\). A random social choice function (RSCF) is a function \(\phi : \mathcal{ D}^n \rightarrow \Delta A\) that assigns a probability distribution over \(A\) at every preference profile. For \(a \in A\) and \(P_N \in \mathcal{D}^n\), \(\phi_a(P_N)\) is the probability of \(a\) at the outcome \(\phi(P_N)\). An RSCF \(\phi\) is a deterministic social choice function (DSCF) if \(\phi_a(P_N) \in \{0, 1\}\) for all \(a \in A\) and all \(P_N \in\mathcal{D}^n\). A DSCF \(f :\mathcal{D}^n \rightarrow A\) is a tops-restricted min-max rule (TM) rule if for all \(S \subseteq N\) there exists \(\beta_S \in \tau(\mathcal{D})\) satisfying the conditions that \(\beta_{\emptyset} = \max(\tau(\mathcal{D})\)), \(\beta_N = \min(\tau(\mathcal{D})\)) and \(\beta_T \preceq \beta_S\) for all \(S \subseteq T\) such that \(f(P_N) = \min_{S \subseteq N} [ \max_{i \in S}\{\tau(P_i), \beta_S\} ]\). An RSCF \(\phi : \mathcal{D}^n \rightarrow \Delta A\) is a tops-restricted random min-max (TRM) rule if \(\phi\) can be written as a convex combination of some TM rules on \(\mathcal{D}^n\).