Preference Restrictions in Computational Social Choice: Recent Progress

1 Introduction

Aggregating preferences of multiple agents by means of voting is often hard. One can identify two primary causes of this phenomenon. The first of them has to do with fundamental properties of collective preferences. Indeed, it was already known to the Marquis de Condorcet that even when individual voters are fully rational, their collective judgment may be irrational: if each voter ranks all alternatives in ¶a↪ b↪ c♦ from best to worst, it may happen that a majority of voters prefer a to b, a majority of voters prefer b to c, yet a majority of voters prefers c to a, i.e., there is a cycle in majority preferences. In a similar spirit-but almost two centuries laterArrow showed in his seminal work [1950] that when there are at least three alternatives, there is no perfect voting rule: he identified a small set of appealing axioms such that no voting rule for three or more alternatives can satisfy all of them. A closely related result was subsequently proved by Gibbard [1973] and Satterthwaite Satterthwaite [1975], who observed that under any 'reasonable' voting rule there exists a scenario where some voter benefits from misrepresenting her preferences.

The results listed in the previous paragraph indicate that preference aggregation is hard from a conceptual perspective. However, it is also hard in a precise technical sense: there are many useful preference aggregation procedures whose output is NP-hard to compute. In particular, this is the case for the Kemeny rule, which is arguably the most natural voting rule to aggregate a set of preference rankings into a single ranking, as well as for two popular committee selection rules that provide fully proportional representation, namely, the Chamberlin-Courant rule and the Monroe rule.

Now, social choice theorists have observed that the first source of hardness can be circumvented by focusing on scenarios where voters' preferences share some common structure. The most famous result of this type dates back to the

Dominik Peters

University of Oxford United Kingdom dominik.peters@cs.ox.ac.uk

important early work of Black [1948] and says that if voters' preferences are essentially single-dimensional, then there are no cycles in the majority preferences, and there is a voting rule that is strategyproof. The specific domain of preferences considered by Black is that of single-peaked preferences; similar results have been subsequently obtained for other restricted preference domains, such as those of preferences that are single-crossing or single-peaked on a tree (we provide formal definitions of these notions in Section 2).

It is then natural to ask whether the same approach can be used to circumvent computational complexity issues as well. The first foray in this direction was made by Walsh [Walsh, 2007], and since 2007 hardness and easiness results for various preference domains have been obtained for winner determination under a variety of voting rules, as well as for the problems of manipulation, control and bribery.

Interestingly, while purely social choice-theoretic issues (such as manipulability or majority cycles) vanish as soon as we assume that voters' preferences belong to a suitable restricted domain, many of the algorithms for voting-related problems require the knowledge of the respective structural relationship among voters/alternatives (such as the order of candidates witnessing that the profile is single-peaked). This means that, to make use of these algorithms, one also needs an efficient procedure to discover whether a given preference profile has the required structural property and to find a respective witness. Consequently, the problem of designing such procedures has received a considerable amount of attention, too, resulting in polynomial-time algorithms for recognizing preferences that belong to several prominent restricted domains, as well as hardness results for some further domains.

The goal of this paper is to discuss both of these strands of algorithmic results, as well as to provide pointers to the literature; a longer literature survey that covers this area in further detail is in preparation.

2 Domain restrictions

Preliminaries For every positive integer n, set [n] = ¶1↪ ▷ ▷ ▷ ↪ n♦. Let A be a finite set of alternatives, or candidates, and let m = ♣A♣. A weak order, or preference relation, is a binary relation over A that is complete and transitive. A linear order is a weak order that, in addition, is antisymmetric. Given a linear order v over A, we denote the top alternative in v by top(v).

A profile P = (v1↪ ▷ ▷ ▷ ↪ vn) over a set of alternatives A is a list of linear orders over A. We associate P = (v1↪ ▷ ▷ ▷ ↪ vn) with a set of voters N = [n]; the order vi is called the vote of voter i. For convenience, we write a ≻i b whenever (a↪ b) 2 vi, i.e., when voter i strictly prefers a to ab. Given a profile P over A, we define its majority relation ⌫maj as a weak order over A such that

We write a ≻maj b if a ⌫maj b, but not b ⌫maj a. Alternative a is a weak Condorcet winner if a ⌫maj b for all b 2 A; it is a Condorcet winner is a ≻maj b for all b 2 A.

Single-Peaked Preferences The domain of single-peaked preferences was first defined by Black [1948]. It captures settings where there is a natural ordering over the alternatives, and voters' preferences are consistent with this order. Popular examples include voting on tax rates, the military budget, or simply the temperature in the room.

Let C be a linear order over the set of alternatives A. A vote v over A is single-peaked with respect to C if for every pair of candidates a↪ b 2 A with top(v) C b C a or a C b C top(v) it holds that v ranks b above a. A profile P over A is singlepeaked with respect to C if every vote in P is single-peaked with respect to C; P is single-peaked if there exists a linear order C over A such that P is single-peaked with respect to C. We refer to any such order C as an axis for P .

The domain of single-peaked profiles has many attractive properties: it admits a family of voting rules that are not susceptible to manipulation (see, e.g., [Moulin, 1991]), and for any profile in this domain the majority relation is transitive (i.e., Condorcet's paradox is circumvented).

Single-Crossing Preferences In contrast to single-peaked profiles, single-crossing profiles are defined in terms of an ordering of the voters. The definition of this domain can be traced back to the work of Mirrlees [1971] and Roberts [1977] on income taxation.

A profile P = (v1↪ ▷ ▷ ▷ ↪ vn) over A is single-crossing with respect to the given order of voters if for every pair of candidates a↪ b 2 C both sets ¶i 2 [n] : a ≻i b♦ and ¶i 2 [n] : b ≻i a♦ are contiguous subsets of [n]; P is singlecrossing if the votes in P can be permuted so that P becomes single-crossing with respect to the resulting order of voters.

Single-crossing profiles have many of the same properties as single-peaked profiles. In particular, the majority relation of a single-crossing profile is transitive.

Euclidean Preferences Euclidean preferences capture settings where voters and alternatives can be identified with points in the Euclidean space, with voters' preferences driven by distances to alternatives. This domain was considered by Coombs [1950].

Formally, a profile P is d-Euclidean (where d is a positive integer) if there exists a map x : N [ A ! Rd such that for all i 2 N and all a↪ b 2 A it holds that

That is, voter i prefers those alternatives that are closer to her according to the embedding x. Here, k · k refers to the usual Euclidean `2-norm on Rd .

It is not hard to see that 1-Euclidean preferences are both single-peaked and single-crossing, with the respective orderings of voters/alternatives determined by their positions on the real line under x. Interestingly, the converse is not true, i.e., there exist profiles that are single-peaked and singlecrossing, but not 1-Euclidean [Coombs, 1950; Elkind et al., 2014; Chen et al., 2015]. Another simple observation is that every profile is d-Euclidean for sufficiently large d. We also remark that d-Euclidean profiles with d > 2 do not necessarily have a Condorcet winner.

Preferences Single-Peaked/Single-Crossing on a Tree Demange [1982] observes that if we place candidates on a tree rather than a line, and require the voters' preferences to be driven by candidates' positions on that tree, we obtain a large preference domain that nevertheless retains some of the attractive properties of the single-peaked domain.

Formally, let T = (A↪E) be a tree with vertex set A. A profile P over A is single-peaked on T if P♣T 0 is singlepeaked for every path T 0 ✓ T. A profile P is single-peaked on a tree if there is a tree T such that P is single-peaked on T .

It can be shown that if a profile is single-peaked on a tree, it necessarily has a weak Condorcet winner; however, its majority relation need not be transitive.

In a similar manner we can define what it means for a profile to be single-crossing on a tree [Kung, 2015].

3 Recognition Algorithms

In this section, we will consider the problem of efficiently deciding whether a given preference profile belongs to one of the restricted domains listed in Section 2.

Single-Peaked Preferences Bartholdi III and Trick [1986] were the first to show that single-peaked preferences can be recognized in polynomial time. Their argument employed a reduction to the consecutive ones problem, which asks whether the columns of a given 0/1-matrix can be reordered so that in every row the 1s occur consecutively, i.e., as a contiguous block. Since the consecutive ones problem admits a linear-time algorithm [Booth and Lueker, 1976], this reduction implies that checking single-peakedness is possible in O(m2n) time. Later, Doignon and Falmagne [1994] developed a direct algorithm that runs in time O(mn + n2 ), and Escoffier et al. [2008] discovered an algorithm whose running time is O(nm). The algorithm of Escoffier et al. [2008] builds up an underlying axis from the outside in, and is based on the crucial observation that alternatives that are ranked last by some voters must be placed on one of the extreme ends of the axis under construction.

Ballester and Haeringer [2011] show that single-peaked preferences can be characterized in terms of two forbidden configurations: they identify two constant-size profiles (one with two voters and four alternatives and one with three voters and three alternatives) such that a profile P is singlepeaked if and only if neither of these two profiles is isomorphic to a subprofile of P. This observation provides an alternative polynomial-time algorithm for recognizing singlepeaked preferences: one can simply go over all subprofiles of a given size, and check that none of them is isomorphic to one of the two forbidden profiles.

Single-Crossing Preferences A simple way to recognize single-crossing preferences is to guess the leftmost vote, sort all other votes by their Kendall-tau distance to the first vote, and check if the resulting profile is single-crossing with respect to the resulting order of voters [Doignon and Falmagne, 1994; Elkind et al., 2012]; this can be done in O((mlogm)n2 ) time. One can also recognize singlecrossing preferences in O(m2n) time via a reduction to the consecutive ones problem [Bredereck et al., 2013]. This domain also admits a characterization in terms of a small number of forbidden configurations [Bredereck et al., 2013].

Euclidean Preferences Doignon and Falmagne [1994] present the first polynomial-time algorithm for recognizing 1-Euclidean profiles (this algorithm was later rediscovered by Elkind and Faliszewski [2014]). Their algorithm is based on the observation that any 1-Euclidean profile is singlecrossing, and the single-crossing order of voters is essentially unique. It checks if the input profile is single-crossing, and if so, uses the respective ordering of voters to determine a possible ordering of the alternatives in R; the task of determining the actual positions of voters and alternatives in R is then delegated to a linear (feasibility) program. Knoblauch [2010] describes a polynomial-time algorithm that is based on the fact that 1-Euclidean preferences are single-peaked; this algorithm, too, first places voters and alternatives on the line and then checks if the associated linear program has a feasible solution.

Interestingly, in contrast with single-peaked and singlecrossing preferences, 1-Euclidean preferences cannot be characterized by a constant number of forbidden configuration [Chen et al., 2015; Peters, 2016].

For d > 2, d-Euclidean preferences become quite unwieldy. The recognition problem is NP-hard for any fixed d > 2 and is, in fact, equivalent to the existential theory of the reals (ETR) [Peters, 2016]. Further, this problem is unlikely to be contained in NP, since there are d-Euclidean profiles all of whose embeddings need exponentially many bits to specify; the best known complexity upper bound is PSPACE.

Preferences Single-Peaked/Single-Crossing on Trees Trick [1989] describes an efficient algorithm for checking whether a given profile is single-peaked on some tree; interestingly, this algorithm may output a complicated tree even if the input profile is single-peaked on a path. One can then ask whether we can recognize in polynomial time if a given profile is single-peaked on a specific tree, or on some tree that has certain desirable properties, such as small diameter, low maximum degree or a constant number of leaves. It turns out that, while answering this question for a given tree is NP-hard [Peters and Elkind, 2016], a 'nice' tree can be identified efficiently for many underlying notions of 'niceness' [Yu et al., 2013; Peters and Elkind, 2016]. Complementing these results, Kung [2015] provides an efficient algorithm for deciding if a given profile is single-crossing on some tree.

4 Algorithms for Social Choice Problems on Restricted Domains

Many popular single-winner rules, such as, e.g., Plurality, Borda, Copeland, Maximin and ranked pairs are computationally easy; three prominent exceptions are the Dodgson rule, the Kemeny rule, and the Young rule, which all have NP-hard winner determination problems, see [Bartholdi III et al., 1989; Hemaspaandra et al., 1997; Dwork et al., 2001; Rothe et al., 2003; Hemaspaandra et al., 2005]. However, for each of these rules the winners can be computed in polynomial time for all restricted domains considered in this paper as long as the number of voters is odd. Indeed, these rules are Condorcet-consistent, i.e., they output the Condorcet winner when it exists, and for each of our domains it holds that every profile with an odd number of voters has a Condorcet winner. The profiles with an even number of voters are more challenging, since for some of these rules the set of winners may be a proper subset of the set of weak Condorcet winners; Brandt et al. [2015] show how to handle this case in polynomial time when voters' preferences are single-peaked.

Most of the results mentioned in the previous paragraph do not rely on having a witness that the input belongs to the respective domain (such as a single-peaked axis or a single-crossing order of the voters). In contrast, restricteddomain algorithms for two important committee selection rules, namely, the Chamberlin-Courant rule and the Monroe rule, tend to make heavy use of this information. Typically, they proceed by dynamic programming, where the structure of the dynamic program is driven by the respective ordering of voters/alternatives. This is the case, for instance, for the algorithms that determine Chamberlin-Courant winners and egalitarian Monroe winners under single-peaked preferences [Betzler et al., 2013] or Chamberlin-Courant winners under single-crossing preferences [Skowron et al., 2016]. Interestingly, the classic variant of the Monroe rule is surprisingly resistant to domain restrictions: it remains hard for both singlepeaked [Betzler et al., 2013] and single-crossing [Skowron et al., 2016] preferences.

Restricting the preferences to be single-peaked on a tree simplifies the winner determination problem for some committee selection rules (such as the egalitarian variant of the Chamberlin-Courant rule); however, to obtain an efficient algorithm for the classic variant of the Chamberlin-Courant rule we need to place additional constraints on the structure of the tree [Yu et al., 2013; Peters and Elkind, 2016]. In contrast, if a profile is single-crossing on a tree, classic ChamberlinCourant winners can be computed efficiently [Clearwater et al., 2015], irrespective of the shape of that tree.

Finally, many problems concerning strategic behavior in voting (such as manipulation, control and bribery) also become easier when voters' preferences are single-peaked or single-crossing [Walsh, 2007; Faliszewski et al., 2011; Brandt et al., 2015; Faliszewski et al., 2014; Magiera and Faliszewski, 2014; Erd´elyi et al., 2015; Elkind et al., 2016].