A characterization of possibility domains in strategic voting (Q2338654)

A set of admissible individual preferences is called a \textit{possibility domain} if it admits at least one non-dictatorial, unanimous and strategy-proof choice function assigning to every possible combination of individual preferences in the domain one feasible alternative. The authors present a complete characterization of all possibility domains which satisfy three conditions: top-connectedness, pervasiveness and richness. Many domains of practical importance such as single-peaked ones satisfy these conditions. While many papers on domain restrictions give only sufficient conditions for a domain to be an impossibility domain, this paper establishes both necessary and sufficient conditions for the same. The authors prove (Theorem 1) that such domains are possibility domains if and only if there is an inseparable top-pair in the domain. A pair of alternatives (\(a, b\)) is an inseparable top-pair in a domain if, whenever \(a\) appears as the best alternative in a preference, \(b\) is preferred to every alternative \(c \not \in \{a, b\}\) with the property that \(c\) appears as the best alternative in some preference in the domain. This theorem applies to a wide array of domains as illustrated by the authors in examples. Next they show (Theorem 2) that if a domain satisfying the three properties just mentioned has a top-circuit, then there does not exist an anonymous, unanimous and strategy-proof choice function on it. We still have to explain some definitions. Given a domain \(\mathbb{D}\) of individual preference orderings, \(\tau(\mathbb{D})\) is the set of alternatives that appear as the best alternative in some preference in \(\mathbb{D}\). Two alternatives \(a\) and \(b\) in \(\tau(\mathbb{D})\) are called \textit{top-connected} in \(\mathbb{D}\) if there are two preferences \(R\) and \(R'\) in \(\mathbb{D}\) such that \(R = a b \ldots\) and \(R'= b a \ldots\). The \textit{top-graph} of a domain \(\mathbb{D}\) is defined as the graph with the set of vertices as \(\tau(\mathbb{D})\) such that there is an edge between two alternatives in \(\tau(\mathbb{D})\) if and only if they are top-connected. A sequence \(c^0, c^1, \ldots, c^k\) of alternatives in \(\tau(\mathbb{D})\) is called a \textit{top-connecting path} if it constitutes a path in the top-graph of \(\mathbb{D}\), that is, if \(c^{i-1}\) and \(c^i\) are top-connected for all \(1 \leq i \leq k\). And a top-connecting path is called a \textit{top-circuit} if it constitutes a cycle in the top-graph of \(\mathbb{D}\). A domain \(\mathbb{D}\) is \textit{top-connected} if for all distinct alternatives \(a\) and \(b\) in \(\tau(\mathbb{D})\) there is a top-connecting path from \(a\) to \(b\). A domain satisfies \textit{pervasiveness} if for all distinct \(a\) and \(b\) in \(\tau(\mathbb{D})\), if there is a preference \(R = a b \ldots\) in the domain, then there is another preference \(R' = b a \ldots\) in it. And a domain satisfies \textit{richness} if for all distinct \(a\), \(b\) and \(c\) in \(\tau(\mathbb{D})\) with \(a\) and \(b\) top-connected and \(b\) and \(c\) top-connected in \(\mathbb{D}\), there are preferences \(R^a\) with \(a\) as the best alternative and \(R^c\) with \(c\) as the best alternative such that for each \(d\) with \(dc\) in \(R^a\) and \(da\) in \(R^c\) there is a preference \(R^b\) with \(b\) as the best alternative such that \(da \in R^b\) or \(dc \in R^b\). The practical relevance of these results is shown by detailing some scenarios where these results can be readily used. For instance, every single-peaked Euclidean domain satisfies the three conditions mentioned above. Consequently, a single-peaked Euclidean domain is a possibility domain if and only if its top-graph has a loose end; and there exist anonymous, unanimous, and strategy-proof choice functions on a single-peaked Euclidean domain if and only if it has no top-circuits. Similar results hold for single-dipped Euclidean domains on convex polytypes. The authors relate their results to other results in the literature on domain restrictions.