# on_the_tree_representations_of_dichotomous_preferences__abe5283f.pdf

On the Tree Representations of Dichotomous Preferences

Yongjie Yang Chair of Economic Theory, Saarland University, Saarbr ucken, Germany yyongjiecs@gmail.com

We study numerous restricted domains of dichotomous preferences with respect to some tree structures. Particularly, we study the relationships among these domains and the ones proposed by Elkind and Lackner [2015]. We also show that recognizing all the restricted domains proposed in this paper is polynomial-time solvable. Finally, we explore the complexity of winner determination for several important approval-based multiwinner voting rules when restricted to these domains.

1 Introduction

Preference domain restrictions have been widely studied in computational social choice recently. The main motivations of the study can be summarized as follows. First, domain restrictions have been a successful approach to circumventing many impossibility theorems. One of the classic examples is arguably the single-peaked domain, restricted to which the median voter rule is non-dictatorial yet strategy-proof [Black, 1948; Moulin, 1980], circumventing Gibbard and Satterthwaite s impossibility theorem [Gibbard, 1973; Satterthwaite, 1975]. Second, many voting problems which are computationally hard in general become polynomial-time solvable when restricted to special domains [Brandt et al., 2015; Faliszewski et al., 2011]. Domain restrictions also offer many structural parameters for researchers to study voting problems from the parameterized complexity point of view. Many fixed-parameter tractability results have been established with respect to several domain restrictions [Bredereck et al., 2016; Cornaz et al., 2012; Yang, 2015; Yang and Guo, 2014]. Third, domain restrictions model many real-world applications, because, in many practical scenarios, the preferences of voters are subject to some combinatorial restrictions, resulting in a restricted domain of preferences. We refer to [Elkind et al., 2017] for a comprehensive discussion on domain restrictions. Following up the work of Elkind and Lackner [2015], we study several domain restrictions on dichotomous preferences. In general, in our models, either candidates or votes are mapped into vertices in a (rooted, oriented) tree and, more importantly, for the former case all approved candidates of every vote induce a special structure, and in

the latter case all votes approving a common candidate induce a specific structure. Domain restrictions based on tree structures have been studied previously. For instance, Demange [1983] extended the single-peaked domain proposed by Black [1948] to single-peaked preferences on a tree. Peters and Elkind [2016] studied single-peaked preferences on trees with further restrictions. Recently, a more general graph class, namely median graphs, has been used in the study of domain restrictions [Clearwater et al., 2015; Demange, 2012; Puppe and Slinko, 2019; Kung, 2015]. One common point of these models is that the trees or graphs involved are all undirected. These domains may not be able to model the scenarios where candidates or votes have domination or dependency relations. In this paper, we consider domain restrictions based on undirected trees, as well as rooted and oriented trees where each edge has a direction which may indicate the domination/dependency relations between the two vertices incident to the edge. We study inclusive relationships among domain restrictions defined in this paper and the ones studied in [Elkind and Lackner, 2015] (Section 3). In addition, we explore whether they can be recognized efficiently (Section 4). Finally, we study the complexity of WINNER DETERMINATION for many important approval-based multiwinner voting rules (Section 5).

2 Preliminary We assume the familiarity of basics in graph theory and complexity theory. A graph G = (N, A) consists of a set of vertices N and a set of edges A. A bipartite graph is a graph whose vertices can be partitioned into two subsets such that there are only edges between these two subsets. A path is a sequence u1, . . . , ut of vertices such that there is an edge between ui and ui+1 for each 1 i < t. A comb is obtained from a path by, for every vertex u in the path, introducing one degree-1 vertex adjacent to u. A tree is a connected graph without cycles. A star is a tree where there is a specific vertex, called the center, and every other vertex is of degree-1 and is adjacent to the center. A rooted tree is a tree with a specific vertex, called the root. An oriented tree is a tree where each edge has a direction. An arborescence is an oriented tree where there is exactly one vertex without incoming edges. We study approval-based multiwinner voting. In this setting, an election is a tuple E = (C, V ) where C is a set of candidates and V a multiset of votes. Each vote v V is a

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)

v1 = {a} v2 = {b, e, g} v3 = {b, e} v4 = {b, d}

Figure 1: An α-TR (left side) of an election (right side).

v1 = {d, a, f} v2 = {c, a, b} v3 = {e, d, f, a}

v1 = {c, a, b} v2 = {g, d, a, b} v3 = {g, d, f}

Figure 2: The oriented tree on the left side is a β-TR of the election E1 and a β-PTR of the election E2 on the right side.

subset of C, representing the set of candidates approved by the corresponding voter. For each candidate c C, let V (c) be the multiset of votes approving c, i.e., V (c) = {v V : c v}. A k-committee is a subset of k candidates. A k-committee selection (multiwinner voting) rule maps each election (C, V ) to a k-committee, called the winners. An election E = (C, V ) can be also represented by a bipartite graph with the vertex bipartition (C, V ). Moreover, there is an edge between c C and v V if and only if v approves c, i.e., c v. We denote this graph by GE and call it the incidence graph of (C, V ). Now we are ready to give the formal definitions of several restricted domains for dichotomous preferences. Generally speaking, in each of these domains candidates are mapped into vertices of a tree and approved candidates of each vote induce some specific structure. We refer to Figures 1 3 for illustrations of these concepts. Let E = (C, V ) be an election.

α-Tree representation (α-TR) We say that E admits an αTR if there is a rooted tree with vertex set C {x} where x C is the root and, moreover, for every vote v V there is a candidate c C such that v approves exactly the candidates in the path from x to c, except x.

β-Tree representation (β-TR) We say that E admits a βTR if there is an oriented tree T with vertex set C such that the approved candidates of each vote induce an arborescence.

β-Path-tree representation (β-PTR) We say that E admits a β-PTR if there exists an oriented tree T = (C, A) such that the approved candidates of every vote v V induce a directed path in T.

Tree representation (TR) We say that E admits a TR if there exists a tree T = (C, A) such that the approved candidates of every vote induce a subtree of T.

Path-tree representation (PTR) We say that E admits a

v1 = {a, b, c, d, e, f} v2 = {e, f, d, g} v3 = {a, b, d}

v1 = {c, a, d, f} v2 = {b, a, d, e} v3 = {d, f, g}

Figure 3: The tree on the left side is a TR of the election E1 and a PTR of the election E2 on the right side.

PTR if there exists a tree T = (C, A) such that the approved candidates of every vote induce a path in T.

Analogous to the above definitions, we can define tree representations of an election where votes are mapped into vertices of a tree and require that for each candidate c the votes approving c induce some specific subgraph. For each of the above concepts we add the letter V immediately after the hyphen to denote such a tree representation. For instance, for β-TR, we say an election (C, V ) admits a β-VTR representation, if there is an oriented tree with vertex set V such that for every candidate c C, votes in V (c) induce an arborescence. As we also study some domains proposed in [Elkind and Lackner, 2015], let s also recall the definitions of these domains. For an integer i, let [i] = {1, 2, . . . , i}.

t-Partition (t-PART) We say that E is t-PART if there is a partition (C1, C2, . . . , Ct) of C such that for every vote v it holds that v = Ci for some i [t].

Voter extremal interval (VEI) We say that E is VEI if there is an order (v1, v2, . . . , vn) of V such that for every candidate c C, there exists an integer i [n] such that V (c) is either {v1, . . . , vi} or {vi+1, . . . , vn}.

Voter interval (VI) We say that E is VI if there is a linear order over V so that for every candidate c C, the votes approving c are consecutive in this order.

Candidate extremal interval (CEI) We say that E is CEI if there is an order (c1, . . . , cm) of C such that for every vote v V there exists an integer i [m] such that either v = {cj : 1 j i} or v = {cj : m j i}.

Candidate interval (CI) We say that E is CI if there is an order of C such that the approved candidates of every vote are consecutive in this order.

Dichotomous uniformly Euclidean (DUE) We say that E is DUE if we can map votes and candidates into the real line such that the approved candidates of every vote is at most r far from this vote, where r is a fixed number.

Weakly single-crossing (WSC) We say that E is WSC if there is an order of V such that for every pair of candidates c and c , the votes in each of V1 = V (c) \ V (c ), V2 = V (c ) \ V (c), and V \ (V1 V2) are consecutive with V \ (V1 V2) being between V1 and V2.

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)

VEI CEI WSC

Figure 4: An arc from one domain to another means that the former implies the latter. The relations indicated by solid arcs are from this paper and by dashed arcs are from [Elkind and Lackner, 2015].

3 Relations Among Different Domains In this section, we investigate the relationships among the restricted domains proposed in this paper and the ones studied by Elkind and Lackner [2015]. Our findings are summarized in the following theorem. Among these relations, we find that the relations among αTR, VI, and β-VPTR are particularly interesting. Recall that in α-TR, candidates are mapped into vertices of a tree, but in VI votes are mapped into vertices in a path. Nevertheless, we prove that α-TR is a special case of VI. The proof is based on the depth-first-search (DFS) traversal of the α-TR tree. Further given that VI is a special case of β-VPTR, we are able to bridge the relations between candidates-mapped tree representations and votes-mapped tree representations. We prove similar relations among α-TVR, CI, and β-PTR. For two domain restrictions A and B, A B, which reads A implies B, means that every A-election is a Belection but not necessarily the other way around. Theorem 1. The following relations hold: t-PART α-TR β-PTR PTR TR = β-TR, t-PART α-VTR β-VPTR VPTR VTR = β-VTR, α-VTR CI β-PTR, and α-TR VI β-VPTR, Moreover, the relations are complete, in the sense that if a concept of restricted domain has no inclusive relation with another one shown above, there is no such a relation in general. (See Figure 4 for a graphical illustration.)

Proof. Let E = (C, V ) be an election. We only prove for the relations involving candidates-mapped representations. t-PART α-TR. Let (C1, . . . , Ct) be a partition of C such that every vote in V is one of C1, . . . , Ct. We can construct a tree with vertex set C {x} such that x is the root and each Ci, 1 i t, induces a path in the tree with one of its endpoints being a child of x. α-TR VI. Let T be an α-TR representation of E with root x. For each vote v V , let cv C be the candidate so that the approved candidates in v are exactly the candidates in the path from x to cv, except x. We shall show that ordering the votes according to the DFS traversal numbers of their corresponding candidates leads to a VI ordering of the election. (See page 603 in [Cormen et al., 2009] for the definition of DFS) For each candidate c C, let DFS(c) be the DFS traversal number of c. Let v1, . . . , vn be an order of V such that for

every i, 1 i < n, it holds that DFS(cvi) < DFS(cvi+1). Due to the definition of DFS, for every candidate c, the votes which approve c are exactly the votes corresponding to c or some descendant of c, which lie continuously in the above defined order. We illustrate it with the election in Figure 1. A DFS traversal order is x, a, c, b, d, e, g, f. Clearly, cv1 = a, cv2 = g, cv3 = e, and cv4 = d. The DFS traversal numbers of a, g, e, d are respectively 2, 7, 6, 5. Hence, the corresponding order of V by the above definition is (v1, v4, v3, v2), in which the votes approving each candidate are consecutive. α-TR β-PTR. Let T be an α-TR representation of E with root x. Without loss of generality, let (c1, c2, . . . , ct) be any arbitrary order of the children of x. Let T be an oriented tree obtained from T by (1) remove the root x; (2) draw an arc from ci to ci+1 for every i [t 1] if t > 1; and (3) for each candidate c, orient the edges between c and its children so that c is the head of the edges. It is easy to see that T is a β-PTR representation of E. To show that the relation is strict, one can check that the election E2 in Figure 2 admits a β-PTR but does not admit an α-TR. β-PTR PTR. This relation is easy to see. To check that the inclusion is strict, consider an election with four candidates a, b, c, d, and three votes v1 = {a, b, c}, v2 = {a, b, d}, and v3 = {a, c, d}. This election admits a PTR but does not admit a β-PTR. β-TR = TR. It is clear that β-TR TR. It remains to show that TR β-TR. Let T be a TR tree of E with vertex set C. We pick any arbitrary candidate c C as the root and orient the edges accordingly so that there is a directed path from the root to every leave. Obviously, every subtree of T is an arborescence of the rooted tree. It is clear that PTR TR. So, we also have PTR β-TR. CI β-PTR. The relation is easy to see.

4 Complexity of Recognition

To exploit restricted domains to design algorithms, an important question is how efficiently we can determine whether an election falls into the category of some restricted domain. Many of our concepts are related to special hypergraphs whose recognition algorithms have been studied. We need the following notions for exposition. A hypergraph G = (N, A) is a tuple where N is the set of vertices and A the hyperedges each of which is a subset of N. A hypergraph can be represented by a bipartite graph where we have N as the vertex set on one side and on the other side we create one vertex a(e) for each hyperedge e A which is adjacent to all vertices included in e. A hypergraph (N, A) is a tree-hypergraph if there is a tree T with vertex set N such that every hyperedge in A induces a subtree of T. Particularly, such a tree T is referred to as a tree-support of G in the literature. Given a hypergraph G = (N, A), it has been shown that determining whether it is a tree-hypergraph can be done in polynomial time. More importantly, if G is a tree-hypergraph, a tree-support of G can be constructed in O(n2 (m + log n)) time where n = |N| and m is the number of hyperedges [Slater, 1978; Klemz et al., 2014; Korach and Stern, 2003; Johnson and Pollak, 1987; Buchin et al., 2011]. It is easy to see that an election E = (C, V )

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)

admits a TR (resp. VTR), if and only if the hypergraph corresponding to the bipartite graph GE with V (resp. C) being considered as the hyperedge set is a tree-hypergraph. This results in the following corollary. Corollary 1. Determining whether an election admits a TR (resp. VTR) can be done in polynomial time and, moreover, a TR (VTR) representation can be constructed in O(|C|2 (|V |+ log |C|)) (resp. O(|V |2 (|C| + log |V |))) time. Brandes et al. [2012] considered path-based tree-supports of hypergraphs and showed that determining whether a hypergraph admits a path-based tree-support can be solved in O(n3m) time, where n and m are respectively the number of vertices and the number of hyperedges in the hypergraph. Recall that a path-based tree-support of a hypergraph G = (N, A) is a tree-support T of G such that every hyperedge in A induces a path of T. Similar to the discussion above, we can obtain the following corollary. Corollary 2. Recognizing whether an election (C, V ) is PTR (resp. VPTR) can be done in polynomial time and, if so, a PTR (resp. VPTR) representation can be constructed in O(|C|3 |V |) (resp. O(|V |3 |C|)) time. A hypergraph G is called a directed path hypergraph if there is an oriented tree such that every hyperedge of G induces a directed path in this tree. Such a tree is called a dipath-based tree-support of G. Chaplick et al. [2010] investigated the relation between path-based tree-supports and dipath-based treesupports of hypergraphs, and proved that given a path-based tree-support T of a directed path hypergraph, it is always possible to orient the edges in T in some way to obtain a dipathbased tree-support of G. More importantly, any algorithm for constructing a path-based tree-support can be adapted to construct a dipath-based tree-support without increasing the time complexity in the worst case. Note that any hypergraph which has a dipath-based tree-support must have a path-based treesupport as well. Hence, we have the following result. Corollary 3. Determining whether an election admits a βPTR (resp. β-VPTR) can be done in polynomial time, and if so, a β-PTR (resp. β-VPTR) can be constructed in O(|C|3 |V |) (resp. O(|V |3 |C|)) time. Finally, we study a polynomial-time algorithm to recognize whether an election admits an α-TR or α-VTR. Theorem 2. Determining whether an election (C, V ) admits an α-TR (resp. α-VTR) can be done in polynomial time, and, if so, an α-TR tree can be constructed in O(p2 m2) time, where m = |C| and p = P v V |v|.

Proof. We only give the proof for α-TR. Let E = (C, V ) be an election and GE its incidence graph. Let m = |C| and p = P v V |v|. We first calculate all connected components of GE which can be done in O(m + p + mp) time. If E admits an α-TR, we shall construct a rooted tree T where candidates in each connected component induce a subtree rooted at a child of the root of T. Note that for each connected component we have a subelection (C , V ) where C C, V V , and C V is the vertex set of this connected component. Then, it suffices to separately determine if each of these subelections admits an α-TR. Particularly, if

all subelections admit α-TRs, we can get an α-TR representation of (C, V ) by merging all the roots of these trees. So, let s now only focus on one connected component H of GE, and let (C , V ) be the subelection corresponding to H. Observe that if there exists no candidate c C who is approved by all votes in V , (C , V ) does not admit an αTR; so does not (C, V ). Otherwise, let cπ(1), . . . , cπ(x) be the candidates in C each of which is approved in all votes in V . We fix an order cπ(1), . . . , cπ(x) of these candidates and accordingly construct a path. Then, we remove the candidates cπ(1), . . . , cπ(x) from H, possibly leading to several connected components in H, for which we iteratively determine whether the subelection with respect to each of these connected components admits an α-TR. If this is the case, similar to the above procedure, we merge all roots of these α-TR trees together with cπ(x). The algorithm can be implemented in O(p2m2) time.

5 Multiwinner Determination In this section, we explore how different domain restrictions shape the complexity of WINNER DETERMINATION for some approval-based multiwinner voting rules, and how to exploit structures of restricted elections to design tractability algorithms. Let (C, V ) be an election and k an integer. Chamberlin-Courant approval voting (CCAV) The score of a committee w is the number of votes intersecting w, i.e., |{v V : v w = }|. This rule selects a kcommittee w C with the maximum score. Proportional approval voting (PAV) The score of a committee w received from a vote v is defined as PAV(v, w) = 1 + 1

2 + + 1 |v w| if v w = , and is 0 if v w = . This rule selects a k-committee with the maximum total score P v V PAV(v, w). Minimax approval voting (MAV) The score of a committee w is defined as maxv V (|v \ w| + |w \ v|), and this rule selects a k-committee with the minimum score. Recall that in the WINNER DETERMINATION problem for a rule ϕ {MAV, CCAV, PAV} (WD-ϕ), we are given an election and a rational number R, and the question is whether there is a k-committee with score at least (resp. most) R for PAV and CCAV (resp. MAV). It has been shown that in general elections WD-MAV, WDCCAV, and WD-PAV are all NP-hard [Aziz et al., 2015; Le Grand, 2004; Betzler et al., 2013], which sparks much study of these problems in restricted elections. In particular, Peters [2018] proved that WD-PAV and WD-CCAV are polynomial-time solvable when restricted to CI elections 1. As α-VTR is a subdomain of CI, the polynomial-time solvability directly transfers to α-VTR elections. In addition, WD-CCAV restricted to VI elections is also polynomial-time solvable [Elkind and Lackner, 2015]. However, whether WDPAV restricted to VI elections is polynomial-time solvable remained as an open question so far. We are not able to resolve

1The first polynomial-time algorithm for WD-CCAV is attributed to Betzler et al. [2013] and is based on the dynamic-programming technique. Peters [2018] showed the result by providing a totally unimodular integer linear programming for the problem.

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)

this open question, but based on the dynamic-programming technique we show that this problem is polynomial-time solvable when restricted to a subdomain of VI, namely the α-TR domain. In fact, we show this result for a large class of rules. An a-PAV rule is characterized by a non-increasing vector a = a1, . . . , ak of k non-negative real numbers. The score of a k-committee w from a vote v is P|v w| i=1 ai if v w = and is 0 otherwise. This rule selects a k-committee with the maximum total score. Therefore, CCAV and PAV are 1, 0, . . . , 0 -PAV and 1, 1

2, . . . , 1

k -PAV, respectively.

Theorem 3. WD-a-PAV restricted to α-TR elections is polynomial-time solvable.

Proof Sketch. Let (C, V ) be an α-TR election. Due to Theorem 2, we can construct an α-TR tree T of this election in polynomial time. Let x denote the root of T. For a candidate c, let P(c) be the set of all candidates in the unique path from x to c except x and c. Let Tc be the subtree rooted at c, V (Tc) the multiset of votes approving at least one candidate in Tc, and C(Tc) the set of candidates in Tc. A crucial observation is that there exists an optimal k-committee such that if some candidate c is in the committee then all candidates in P(c) are also in this committee. Based on this observation, we develop a dynamicprogramming algorithm as follows. For each candidate c and a non-negative integer i |C(Tc)|, let sc(c, i) denote the a-PAV score of an optimal (|P(c)| + i)-committee consisting of exactly i candidates from Tc with respect to the subelection (P(c) C(Tc), V (Tc)). Updating sc(c, i), i 1, can be reduced to a variant of the classic Knapsack problem. In particular, let c1, . . . , ct be the children of c. Note that for any cx and cy such that 1 x = y t, it holds that V (cx) V (cy) = . The question is then to find a vector i1, i2, . . . , it of non-negative integers such that (1) Pt j=1 ij = i 1; (2) ij |C(Tcj)| for every 1 j t; and (3) Pt j=1 sc(cj, ij) is maximized among all vectors satisfying the first and second conditions. Such a vector can be found in polynomial time using a similar dynamic programming algorithm for the Knapsack problem [Kellerer, 2016]. Given such a vector i1, i2, . . . , it , let

j=1 sc(cj, ij)+

x [t] V (Tcx)

|P (c)|+1 X

The score of an optimal k-committee is then sc(x, k) (regarding x as a candidate not approved by anyone).

For WD-MAV, Liu and Guo [2016] derived a polynomialtime algorithm for CI and VI elections, implying that WDMAV is also polynomial-time solvable in α-TR and α-VTR elections. We show that when restricted to a slightly expanded domain, the complexity of the problem changes. An election is a star/comb PTR (or other domains studied in this paper) election if it admits a PTR representation where the underling tree is a star/comb.

Theorem 4. WD-MAV and WD-PAV restricted to star PTR elections are NP-hard.

The proof is adapted from the reductions in [Aziz et al., 2015; Le Grand, 2004] by introducing a candidate being the center of the star and being approved by all votes. For CCAV, the above adaption does not work, because in this case if a candidate is approved in all votes, then any kcommittee including this candidate is a winning k-committee. Nevertheless, via a completely different reduction, we show that WD-CCAV remains NP-hard even when restricted to star β-PTR elections, a special case of PTR. In a graph, we say a vertex covers an edge if this vertex is one of the endpoints of this edge.

PARTIAL VERTEX COVER (PVC)

Given: A graph G = (U, F) with vertex set U and edge set F, two positive integers p and ℓ. Question: Is there a subset S U of p vertices which together cover at least ℓedges in G?

It is known that PVC remains NP-hard even when the input graph G is a bipartite graph [Caskurlu et al., 2017].

Theorem 5. WD-CCAV restricted to star β-PTR elections is NP-hard.

Proof. Let (G = (A B, F), p, ℓ) be a PVC instance where G is a bipartite graph with the bipartition (A, B). Let n = |F| be the number of edges. For each vertex u A B, we create a candidate c(u). In addition, we create a candidate d. For each edge e = (u, u ) F where u A and u B, we create a vote v(e) which approves d, c(u), and c(u ). Moreover, for each vertex u A B, we create a multiset V (u) of n votes each of which approves only c(u). It is easy to see that the election admits a star β-PTR, where there is an arc from every candidate c(u), u A, to the candidate d, and an arc from d to every candidate c(u), u B. We complete the construction by setting k = p and R = ℓ+p n. ( ) Assume that there exists an S A B of p vertices in G which covers at least ℓedges. Let w = {c(u) : u S}. We claim that w has CCAV score at least R. First, w intersects all p n votes in S u S V (u). In addition, if an edge e = (u, u ), u A, u B, is covered by some vertex in S, at least one of c(u) and c(u ) is in w; hence, w intersects the corresponding vote v(e). Since S covers at least ℓ edges, w intersects at least ℓvotes corresponding to these covered edges. In total, w intersects at least p n + ℓ= R votes. ( ) Suppose that the constructed election has a kcommittee w of score at least R. Observe that the candidate d cannot be in w, since otherwise w can intersect at most n+(k 1) n = k n < R votes. So, w {c(u) : u A B}. Let S = {u A B : c(u) w} be the set of vertices corresponding to w. Clearly, w intersects all k n votes in S u S V (u). As R = k n+ℓ, this implies that w intersects at least ℓedge-votes in G. Due to the construction, vertices in S cover all edges corresponding to these edge-votes.

We show that the polynomial-time solvability for VI elections does not extend to VTR elections with even specific underling tree structures.

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)

α-TR β-PTR PTR TR α-VTR β-VPTR VPTR VTR

PAV P [Thm. 3] ? NP-h (star) P [Peters, 2018] ? ? NP-h [Thm. 6] [Thm. 4] (star, comb)

CCAV P [Thm. 3] NP-h (star) P [Peters, 2018] P (star) NP-h [Thm. 6] [Thm. 5] [Thm. 7] (star, comb)

MAV P P (star) NP-h (star) P P (star) NP-h [Thm. 6] [Liu and Guo, 2016] [Thm. 8] [Thm. 4] [Liu and Guo, 2016] [Thm. 7] (star, comb)

Table 1: Entries marked with ( ) mean that the results are the same as the one immediately on the left (right) side.

Figure 5: An illustration of the proof of Theorem 6. Dark nodes correspond to the votes approving a candidate c(s) such that s = {u2, u3, u3κ} S.

RESTRICTED EXACT COVER BY THREE SETS (RX3C)

Given: A universe U = {u1, u2, . . . , u3κ}, a collection S of 3-subsets of U such that every u U occurs in exactly three elements in S. (So, |S| = 3κ) Question: Is there an S S such that |S | = κ and every u U occurs in exactly one element of S ?

Theorem 6. WD-PAV, WD-CCAV, and WD-MAV restricted to comb/star VTR elections are NP-hard.

Proof. We give only the proof for PAV in Comb VTR elections. Let (U, S) be an instance of the RX3C problem such that |U| = |S| = 3κ. For each s S, we create a candidate c(s). Concerning the votes, we first create 3κ votes v1, v2, . . . , v3κ. Then, for each u U, we create one vote v(u). Importantly, we let the candidate c(s) corresponding to s S be approved by all votes vi such that 1 i 3κ, and by every vote v(u) such that u s. Hence, every candidate is approved by 3k + 3 votes. Finally, we set k = κ and R = 3k + 3k(1 + 1

k). Figure 5 depicts the construction. We show the correctness as follows. ( ) Let S S be an exact 3-set cover. Let w be the k-committee consisting of every c(s) such that s S . Due to the construction, all the 3κ votes vi, 1 i 3κ, approve all candidates. Moreover, as S is an exact 3-set cover, every vote v(u), u U, approves exactly one candidate c(s) w such that u s and s S . It is then easy to verify that the score of the committee w is exactly R. ( ) Let w be a k-committee with score at least R. As all the 3κ votes vi, 1 i 3κ, approve all candidates, the score of the committee w with respect to the votes in {v(u) : u U} is at least R 3k(1+ 1

k) = 3k. It is fairly easy to check that this is the case only when every vote v(u) where u U approves exactly one candidate in w, which implies that {s : s S, c(s) w} is an exact 3-set cover.

We fill the gaps by the following theorems. Theorem 7. WD-CCAV and WD-MAV restricted to star VPTR elections are polynomial-time solvable.

Proof. We give only the proof for CCAV. Let (C, V ) be the election in a given instance. Observe that if there are two candidates c, c C such that V (c) V (c ), removing c does not change the answer to the instance. Hence, hereinafter, we assume that no such two candidates exist. Let v0 V denote the center and v1, . . . , vn 1 the leaves in the VPTR representation of (C, V ). Observe that if v0 does not approve any candidate, all k-committees have the same score under the above assumption. Otherwise, let C be the set of candidates approved by three votes (one of them is v0). Under the above assumption, if |C | < k, any optimal k-committee contains C and any arbitrary k |C | candidates from C \ C ; we are done. If |C | k, we solve the problem by reducing it to the PARTIAL EDGE COVER (PEC) problem which is polynomial-time solvable [Plesn ık, 1999]. In particular, for each vote vi, 1 < i n 1, we create a vertex, denoted still by vi for simplicity. Then, for every candidate c C such that V (c) = {v0, vi, vj} where 1 i = j n 1, we create an edge between vi and vj. Now, the question is equivalent to finding a subset of k edges that cover as many vertices as possible. This is exactly a PEC instance.

Theorem 8. WD-MAV restricted to star β-PTR elections is polynomial-time solvable.

6 Conclusion We studied several restricted domains of dichotomous preferences, where candidates/votes are mapped into vertices of a (rooted, oriented) tree, and votes/candidates induce some specific structures. Particularly, we studied the relations among these domains and the ones in [Elkind and Lackner, 2015] (Figure 4), the complexity of recognizing them, and the complexity of WINNER DETERMINATION restricted to these domains (Table 1). Except DUE, all domains shown in Figure 4 can be recognized in polynomial time. The complexity of determining whether an election satisfies DUE remained open.

References [Aziz et al., 2015] Haris Aziz, Serge Gaspers, Joachim Gudmundsson, Simon Mackenzie, Nicholas Mattei, and Toby Walsh. Computational aspects of multi-winner approval voting. In AAMAS, pages 107 115, 2015.

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)

[Betzler et al., 2013] Nadja Betzler, Arkadii Slinko, and Johannes Uhlmann. On the computation of fully proportional representation. J. Artif. Intell. Res., 47:475 519, 2013. [Black, 1948] Duncan Black. On the rationale of group decision-making. J. Polit. Econ., 56(1):23 34, 1948. [Brandes et al., 2012] Ulrik Brandes, Sabine Cornelsen, Barbara Pampel, and Arnaud Sallaberry. Path-based supports for hypergraphs. J. Discrete Algorithms, 14:248 261, 2012. [Brandt et al., 2015] Felix Brandt, Markus Brill, Edith Hemaspaandra, and Lane Hemaspaandra. Bypassing combinatorial protections: Polynomial-time algorithms for single-peaked electorates. J. Artif. Intell. Res., 53:439 496, 2015. [Bredereck et al., 2016] Robert Bredereck, Jiehua Chen, and Gerhard Woeginger. Are there any nicely structured preference profiles nearby? Math. Soc. Sci., 79:61 73, 2016. [Buchin et al., 2011] Kevin Buchin, Marc van Kreveld, Henk Meijer, Bettina Speckmann, and Kevin Verbeek. On planar supports for hypergraphs. J. Graph Algorithms Appl., 15(4):533 549, 2011. [Caskurlu et al., 2017] Bugra Caskurlu, Vahan Mkrtchyan, Ojas Parekh, and Krishnamurthy Subramani. Partial vertex cover and budgeted maximum coverage in bipartite graphs. SIAM J. Discrete Math., 31(3):2172 2184, 2017. [Chaplick et al., 2010] Steven Chaplick, Marisa Gutierrez, Benjamin L evˆeque, and Silvia Tondato. From path graphs to directed path graphs. In WG, pages 256 265, 2010. [Clearwater et al., 2015] Adam Clearwater, Clemens Puppe, and Arkadii Slinko. Generalizing the single-crossing property on lines and trees to intermediate preferences on median graphs. In IJCAI, pages 32 38, 2015. [Cormen et al., 2009] Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. Introduction to Algorithms, 3rd Edition. MIT Press, 2009. [Cornaz et al., 2012] Denis Cornaz, Lucie Galand, and Olivier Spanjaard. Bounded single-peaked width and proportional representation. In ECAI, pages 270 275, 2012. [Demange, 1983] Gabrielle Demange. Single-peaked orders on a tree. Math. Soc. Sci., 3(3):389 396, 1983. [Demange, 2012] Gabrielle Demange. Majority relation and median representative ordering. SERIEs-J. Span. Econ., 3(1):95 109, 2012. [Elkind and Lackner, 2015] Edith Elkind and Martin Lackner. Structure in dichotomous preferences. In IJCAI, pages 2019 2025, 2015. [Elkind et al., 2017] Edith Elkind, Martin Lackner, and Dominik Peters. Structured preference. In Trends in Computational Social Choice, chapter 10, pages 187 207. AI Access, 2017. [Faliszewski et al., 2011] Piotr Faliszewski, Edith Hemaspaandra, Lane Hemaspaandra, and J org Rothe. The shield that never was: Societies with single-peaked preferences

are more open to manipulation and control. Inf. Comput., 209(2):89 107, 2011. [Gibbard, 1973] Allan Gibbard. Manipulation of voting schemes: A general result. Econometrica, 41(4):587 601, 1973. [Johnson and Pollak, 1987] David Johnson and Henry Pollak. Hypergraph planarity and the complexity of drawing Venn diagrams. J. Graph Theory, 11(3):309 325, 1987. [Kellerer, 2016] Hans Kellerer. Knapsack. In Encyclopedia of Algorithms, pages 1048 1051. Springer, 2016. [Klemz et al., 2014] Boris Klemz, Tamara Mchedlidze, and Martin N ollenburg. Minimum tree supports for hypergraphs and low-concurrency Euler diagrams. In SWAT, pages 265 276, 2014. [Korach and Stern, 2003] Ephraim Korach and Michal Stern. The clustering matroid and the optimal clustering tree. Math. Program., 98(1-3):385 414, 2003. [Kung, 2015] Fan-Chin Kung. Sorting out single-crossing preferences on networks. Soc. Choice Welfare, 44(3):663 672, 2015. [Le Grand, 2004] Rob Le Grand. Analysis of the minimax procedure. Technical report, Department of Computer Science and Engineering, Washington University, St. Louis, Missouri., 2004. [Liu and Guo, 2016] Hong Liu and Jiong Guo. Parameterized complexity of winner determination in Minimax committee elections. In AAMAS, pages 341 349, 2016. [Moulin, 1980] Herv e Moulin. On strategy-proofness and single peakedness. Public Choice, 35(4):437 455, 1980. [Peters and Elkind, 2016] Dominik Peters and Edith Elkind. Preferences single-peaked on nice trees. In AAAI, pages 594 600, 2016. [Peters, 2018] Dominik Peters. Single-peakedness and total unimodularity: New polynomial-time algorithms for multi-winner elections. In AAAI, pages 1169 1176, 2018. [Plesn ık, 1999] J an Plesn ık. Constrained weighted matchings and edge coverings in graphs. Discrete Appl. Math., 92(2-3):229 241, 1999. [Puppe and Slinko, 2019] Clemens Puppe and Arkadii Slinko. Condorcet domains, median graphs and the single-crossing property. Economic Theory, 67(1):285 318, 2019. [Satterthwaite, 1975] Mark Allen Satterthwaite. Strategyproofness and Arrow s conditions: Existence and correspondence theorems for voting procedures and social welfare functions. J. Econ. Theory, 10(2):187 217, 1975. [Slater, 1978] Peter Slater. A characterization of Soft hypergraphs. Canad. Math. Bull., 21(3):335 337, 1978. [Yang, 2015] Yongjie Yang. Manipulation with bounded single-peaked width: A parameterized study. In AAMAS, pages 77 85, 2015. [Yang and Guo, 2014] Yongjie Yang and Jiong Guo. Controlling elections with bounded single-peaked width. In AAMAS, pages 629 636, 2014.

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)