Ties in Multiwinner Approval Voting

1 Introduction

In an approval-based multiwinner election, a group of voters expresses their preferences about a set of candidatesi.e., each voter indicates which of them he or she approvesand then, using some prespecified rule, the organizer selects a winning committee (a fixed-size subset of the candidates). Multiwinner elections can be used to resolve very serious matters-such as choosing a country's parliament-or rather frivolous ones-such as choosing the tourist attractions that a group of friends would visit-or those positioned anywhere in between these two extremes-such as choosing a department's representation for the university senate. In large elections, one typically does not expect ties to occur (although surprisingly many such cases are known 1 ), but for small and moderately sized ones the issue is unclear (whenever we speak of a size of an election, we mean both the number of candidates and the number of voters). While perhaps a group of friends may manage to not spoil their holidays upon discovery that they were as willing to visit one monument as another, a person not selected for a university senate due to a tie may be quite upset, especially if this tie is discovered after announcing the results. To address such possibilities, we study the following three issues:

1. We consider the complexity of detecting if two or more committees tie under a given voting rule. While for most rules this problem turns out to be intractable, for many settings we find practical solutions (in most cases it is ei-

1 https://en.wikipedia.org/wiki/List of close election results

• ther possible to use a natural integer linear programming trick or an FPT algorithm that we provide).
• We consider the complexity of counting the number of winning committees. We do so, because being able to count winning committees would be helpful in sampling them uniformly. Unfortunately, in this case we mostly find hardness and hardness of approximation results.
• We generate a number of elections, both synthetic and based on real-life data, and evaluate the frequency of ties. It turns out to be surprisingly high.

We focus on a subfamily of Thiele rules [Thiele, 1895; Aziz et al., 2015; Lackner and Skowron, 2021] that includes the multiwinner approval rule (AV), the approvalbased Chamberlin-Courant rule (CCAV), and the proportional approval voting rule (PAV), as well as on their greedy variants. We also study satisfaction approval voting (SAV), the Phragm´en rule, and Method of Equal Shares (MEqS). This set includes rules appropriate for selecting committees of individually excellent candidates (e.g., AV or SAV), diverse committees (e.g., CCAV or GreedyCCAV), or proportional ones (e.g., PAV, GreedyPAV, Phragm´en, or MEqS); see the works of Elkind et al. [2017] and Faliszewski et al. [2017] for more details on classifying multiwinner rules with respect to their application. We summarize our results in Table 1.

The issue of ties and tie-breaking has already received quite some attention in the literature, although typically in the context of single-winner voting. For example, Obraztsova and Elkind [2011] and Obraztsova et al. [2011] consider how various tie-breaking mechanisms affect the complexity of manipulating elections, Freeman et al. [2015] study different tie-breaking schemes, such as parallel-universes tie-breaking and randomized ones, in single-winner voting (mainly for STV), and recently Xia [2021] has made a breakthrough in studying the probability of ties in large, randomly-generated single-winner elections. Xia [2022] also developed a novel tie-breaking mechanism, albeit for a somewhat different setting than ours. Finally, Conitzer et al. [2009] have shown that deciding if a candidate is a tied winner in an STV election is NP-hard. While STV is not an approval-based rule and they focused on the single-winner setting, many of our results are in a similar spirit. Omitted proofs are in the full version of the paper [Janeczko and Faliszewski, 2023].

2 Preliminaries

By R+ we denote the set of nonnegative real numbers. For each integer t, we write [t] to mean {1, . . . , t}. We use the Iverson bracket notation, i.e., for a logical expression F, we interpret [F] as 1 if F is true and as 0 if it is false. Given a graph G, we write V (G) to denote its set of vertices and E(G) to denote its set of edges. For a vertex v, by d(v) we mean its degree (i.e., the number of edges that touch it).

An election E = (C, V,A) consists of a set of candidates C = {c1, . . . , cm} and a collection of voters V = (v1, . . . , vn), where each voter vi has a set A(vi) ⊆ C of candidates that he or she approves. We refer to this set as vi's approval set or vi's vote, interchangeably. We typically omit writing A (as it is clear from the context) and use a shortened notation E = (C, V ). By a small abuse of notation, for a candidate c we write A(c) to denote the set of voters that approve him or her. A multiwinner voting rule f is a function that given an election E = (C, V ) and committee size k ∈ [|C|] outputs a family of size-k subsets of C, i.e., a family of winning committees (denoted as f(E, k)). Below we describe the rules that we focus on.

Let E = (C, V ) be an election and let k be the committee size. Under the multiwinner approval rule (AV), each voter assigns a single point to each candidate that he or she approves and winning committees consist of k candidates with the highest scores. Satisfaction approval voting (SAV) proceeds analogously, except that each voter v ∈ V assigns 1/|A(v)| points to each candidate he or she approves. In other words, under AV each voter can give a single point to each approved candidate, but under SAV he or she needs to split a single point equally among them.

Next we consider the class of Thiele rules, defined originally by Thiele [1895] and discussed, e.g., by Lackner and Skowron [2021] and Aziz et al. [2015]. Given a nondecreasing weight function w: N → R+ such that w(0) = 0, we define the w-Thiele score (w-score) of a committee S = {s1, . . . , sk} in election E to be:

The w-Thiele rule outputs all committees with the highest wscore. We require that for each of our weight functions w, it is possible to compute each value w(i) in polynomial time with respect to i. Additionally, we focus on functions such that w(1) = 1 and for each positive integer i it holds that w(i)-w(i-1) ≥ w(i+1)-w(i). We refer to such functions, and the Thiele rules that they define, as 1-concave. Three best-known 1-concave Thiele rules include the already defined AV rule, which uses function wAV(t) = t, the approvalbased Chamberlin-Courant rule (CCAV), which uses function wCCAV(t) = [t ≥ 1], and the proportional approval voting rule (PAV), which uses the function wPAV(t) = ∑ti=1 1/i.

While it is easy to compute some winning committees under the AV rule in polynomial time (out of possibly exponentially many), for the other Thiele rules, including CCAV and PAV, even deciding if a committee with at least a given score exists is NP-hard (see the works of Procaccia et al. [2008] and Betzler et al. [2013] for the case of CCAV, and the works of Aziz et al. [2015] and Skowron et al. [2016] for the general case). Hence, sometimes the following greedy variants of Thiele rules are used (E is the input election and k is the desired committee size):

Let f be a w-Thiele rule. Its greedy variant, denoted Greedy-f, first sets W0 := ∅ and then executes k iterations, where for each i ∈ [k], in the i-th iteration it computes Wi := Wi-1 ∪ {c} such that c is a candidate in C \Wi-1 that maximizes the w-score of Wi. Finally, it outputs Wk. In case of internal ties, i.e., if at some iteration there is more than one candidate that the algorithm may choose, the algorithm outputs all committees that can be obtained for some way of resolving each of these ties. In other words, we use the parallel-universes tie-breaking model [Conitzer et al., 2009].

When we discuss the operation of some Greedy-f rule on an election E and we discuss the situation after its i-th iteration, where, so far, subcommittee Wi was selected, then by the score of a (not-yet-selected) candidate c we mean the value w-scoreE(Wi ∪ {c}) -w-scoreE(Wi), i.e., the marginal increase of the w-score that would result from selecting c. We refer to the greedy variants of CCAV and PAV as GreedyCCAV and GreedyPAV (in the literature, these rules are also sometimes called sequential variants of CCAV and PAV, see, e.g., the book of Lackner and Skowron [2023]). Given a greedy variant of a 1-concave Thiele rule, it is always possible to compute at least one of its winning committees in polynomial time by breaking internal ties arbitrarily. Further, it is well-known that the w-score of this committee is at least a 1-1/e ≈ 0.63 fraction of the highest possible w-score; this follows from the classic result of Nemhauser et al. [1978] and the fact that w-score is monotone and submodular.

The Phragm´en (sequential) rule proceeds as follows (see, e.g., the works of Janson [2016] and Brill et al. [2017]):

Let E = (C, V ) be an election and let k be the committee size. Each candidate costs a unit of currency. The voters start with no money, but they receive it continuously at a constant rate. As soon as there is a group of voters who approve a certain not-yet-selected candidate and who together have a unit of currency, these voters "buy" this candidate (i.e., they give away all their money and the candidate is included in the committee). The process stops as soon as k candidates are selected. For internal ties, we use the parallel-universes tie-breaking.

Method of Equal Shares (MEqS), introduced by Peters and Skowron [2020] and Peters et al. [2021], is similar in spirit, but gives the voters their "money" up front (we use the same notation as above):

Initially, each voter has a budget equal to k/|V |. The rule starts with an empty committee and executes up to k iterations as follows (for each voter v, let b(v) denote v's budget in the current iteration): For each not-yet-selected candidate c we check if the voters that approve c have at least a unit of currency (i.e., ∑v∈A(c) b(v) ≥ 1). If so, then we compute value ρc such that ∑v∈A(c) min(b(v), ρc) = 1, which we call the per-voter cost of c. We extend the committee with this candidate c′ , whose per-voter cost ρc′ is the lowest; the voters approving c′ "pay" for him or her (i.e., each voter v ∈ A(c′ ) gives away min(b(v), ρc′ ) of his or her budget). In case of internal ties, we use the paralleluniverses tie-breaking. The process stops as soon as no candidate can be selected.

The above process, referred to as Phase 1 of MEqS, often selects fewer than k candidates. To deal with this, we extend the committee with candidates selected by Phragm´en (started off with the budgets that the voters had at the end of Phase 1). We jointly refer to the greedy rules, Phragm´en, MEqS, and Phase 1 of MEqS as sequential rules.

We assume familiarity with basic classes of computational complexity such as P, NP, and coNP. #P is the class of functions that can be expressed as counting accepting paths of nondeterministic polynomial-time Turing machines. Additionally, we consider parameterized complexity classes such as FPT and W[1] (see, e.g., the textbooks of Niedermeier [2006] and Cygan et al. [2015]). #W[1] is a parameterized counting class which relates to W[1] in the same way as #P relates to NP [Flum and Grohe, 2004]. When discussing counting problems, it is standard to use Turing reductions: A counting problem #A reduces to a counting problem #B if there is a polynomial time algorithm that solves #A in polynomial time, provided it has oracle access to #B (i.e., it can solve #B in constant time). 2

3 UniqueWinning Committee

In this section we consider the problem of deciding if a given multiwinner rule outputs a unique committee in a given election. Formally, we are interested in the following problem.

Definition 3.1. Let f be a multiwinner voting rule. In the fUNIQUE-COMMITTEE problem we are given an election E and a committee size k, and we ask if |f(E, k)| = 1.

It is a folk result that for AV and SAV this problem is in P (see beginning of Section 4 for an argument). For Thiele rules other than AV, the situation is more intriguing. In particular, already the problem of deciding if a given committee is winning under the CCAV rule is coNP-complete [Sonar et al., 2020]. We show that for 1-concave Thiele rules other than AV the UNIQUE-COMMITTEE problem is coNP-hard (and we conjecture that the problem is not in coNP).

2 For #W[1], the running time can even be larger, but our #W[1]-hardness proofs use polynomial-time reductions.

Proposition 3.1. Let f be a 1-concave w-Thiele rule other than AV. Then f-UNIQUE-COMMITTEE is coNP-hard.

Proof. Let x = w(2) - w(1) and assume, for now, that x < 1. We give a reduction from INDEPENDENT-SET to the complement of f-UNIQUE-COMMITTEE. An instance of INDEPENDENT-SET consists of a graph G and an integer k, and we ask if there are k vertices neither of which is connected with the others. Let G′ be a graph obtained from G by adding k vertices such that each of the new vertices is connected to each of the old ones (but the new vertices are not connected to each other). If G does not have a size-k independent set, then G′ has a unique one, and if G has at least one size-k independent set, then G′ has at least two. Let us denote the vertices of G′ as V (G′ ) = {v1, . . . , vn} and its edges as E(G′ ) = {e1, . . . , em}. Let d(vi) be the degree of a vertex vi and δ be the highest degree in V (G′ ). We fix the committee size to be k and we form an election E with the candidate set V (G′ ) and with the following voters:

1. For each edge eℓ = {vi, vj} there is a single voter who approves vi and vj.
2. For each vertex vi there are δ-d(vi) voters approving vi.

Consider a set of k vertices from V (G′ ). If this set is an independent set, then interpreted as a committee in election E, it has w-score equal to δk. On the other hand, if S is not an independent set, then its score is at most (δk - 1) + x < δk. We know that G′ has an independent set of size k. If G also has one, then our election has at least two winning committees and, otherwise, the winning committee is unique. The case where x = 1 is in the full version of the paper.

For greedy variants of Thiele rules (with the natural exception of AV) and for the Phragm´en rule, deciding if the winning committee is unique is coNP-complete. Our proof for the greedy variants of Thiele rules is inspired by a complexityof-robustness proof for GreedyPAV, provided by Faliszewski et al. [2022]. For Phragm´en, somewhat surprisingly, their robustness proof directly implies our desired result. We also get analogous result for Method of Equal Shares and its Phase 1.

Theorem 3.2. Let f be a 1-concave w-Thiele rule, f ̸= AV. Greedy-f-UNIQUE-COMMITTEE is coNP-complete.

Corollary 3.3. UNIQUE-COMMITTEE is coNP-complete for GreedyCCAV, GreedyPAV, and PHRAGM´EN.

Theorem 3.4. UNIQUE-COMMITTEE is coNP-complete for Phase 1 of MEqS.

Proof. One can verify that the problem is in coNP. To show hardness, we give a reduction from the complement of the classic NP-complete problem, X3C. An instance of X3C consists of a universe set U = {u1, . . . , u3n} and a family S = {S1, . . . , S3n} of size-3 subsets of U. We ask if there are n sets from S whose union is U (we refer to such a family as an exact cover of U; note that the sets in such a cover must be disjoint). Without loss of generality, we assume that each member of U belongs to exactly three sets from S [Gonzalez, 1985] and that n is even.

Now we describe our election. Ideally, we would like to distribute different amounts of budget between different voters, but as MEqS splits the budget evenly, we design the election in such a way that in the initial iterations the respective voters spend appropriate amounts of money on the candidates that otherwise are not crucial for the construction. We form the following groups of voters (we reassure the reader that the analysis is more pleasant than it may appear):

1. Group B, which contains 144n3 - 12n voters.
2. Group BU , which contains 54n3 + 9n2 voters.
3. Group U ′ , which models the elements of the universe set U. For each ui ∈ U, there is a single corresponding voter in U ′ . We have |U ′ | = 3n.
4. Group U ′′ , which serves a similar purpose as U ′ , but contains more voters. Specifically, for each ui ∈ U, there are 6n corresponding voters in U ′′ ; |U ′′ | = 18n2 .
5. Group Vpd, which contains 12n voters.
6. Group VS, which contains 9n voters.
7. Two voters, d1 and d2.

In total, there are 198n3 + 27n2 + 12n + 2 voters. Further, we have the following groups of candidates:

1. Group CB of 144n3 - 12n2 candidates approved by the 144n3 voters from B ∪ Vpd.
2. Group CU of 54n3 + 24n2 + 5n/2 candidates approved by the 54n3 + 27n2 + 3n voters from BU ∪ U ′ ∪ U ′′ .
3. Candidate p approved by the 12n voters from Vpd.
4. Candidate d approved by the 15n voters from Vpd ∪ U ′ .
5. Candidates c1 and c2, both approved by d1 and d2.
6. Group D of 15n2 + 45n 2 +5 candidates approved by d1.
7. For each set Sℓ ∈ S such that Sℓ = {ui, uj , ut} we have a corresponding candidate sℓ approved by: (a) three unique voters from VS, (b) the voters from U ′ and U ′′ that correspond to the elements ui, uj , ut. We write S to denote this group of candidates and we refer to its members as the S-candidates. Each S-candidate is approved by 3 + 3 + 3 · 6n = 18n + 6 voters.

We have 198n3 +27n2 +28n+9 candidates in total. We set the committee size k to be equal to the number of voters, i.e., k = 198n3 + 27n2 + 12n + 2. Let us consider the following two committees (note that each of them contains fewer than k candidates; indeed, Phase 1 of MEqS sometimes chooses committees smaller than requested):

We claim that Phase 1 of MEqS always outputs committee Wd, and if (U, S) is a yes-instance then it also outputs Wp.

Let us analyze how Phase 1 of MEqS proceeds on our election. Since the committee size is equal to the number of voters, initially each voter receives budget equal to 1.

At first, we will select all candidates from CB. Indeed, there are 144n3 - 12n2 candidates in this group, each approved by 144n3 voters (from B ∪ Vpd). Each of these voters pays 1/144n3 for each of the candidates (this is the lowest per-voter candidate cost at this point). After these purchases, each voter from B ∪ Vpd will be left with budget equal to

Next, we will select all candidates from CU. Indeed, this set contains 54n3 + 24n2 + 5n/2 candidates approved by 54n3 + 27n2 + 3n voters (from BU ∪ U ′ ∪ U ′′ ) who have not spent any part of their budget yet. All candidates in CU will be purchased at the same pre-voter cost of 1/(54n3+27n2+3n) (the lowest one at this point). Each voter in BU ∪ U ′ ∪ U ′′ will be left with budget equal to 1 -

Next, we consider the S-candidates who, at this point, have the highest approval score among the yet unselected candidates. As each S-candidate is approved by exactly 18n + 6 voters and each voter still has budget higher or equal to 1/(18n+6), we keep selecting the S-candidates at the per-voter cost of 1/(18n+6) as long as there is at least one such candidate whose all voters still have budget of at least 1/(18n+6).

Upon selecting a given S-candidate, corresponding to set Sℓ, all the voters who approve him or her pay 1/(18n+6). This includes the three unique voters from VS and the voters from U ′ and U ′′ who correspond to the members of Sℓ. Prior to this payment, the voters from U ′ and U ′′ have budget equal to 1/(18n+6), so they end up with 0 afterward (and we say that they are covered by this S-candidate). Consequently, the S-candidates that we buy at the per-voter cost of 1/(18n+6) correspond to disjoint sets.

Now let us consider what happens when there is no Scandidate left who can be purchased at the per-voter cost of 1/(18n+6). This means that for each unselected S candidate, at least 6n + 1 voters approving him have already been covered and have no budget left. Hence, for a given S-candidate there are at least 6n+1 voters (from U ′ and U ′′ ) whose budget is 0, at most 12n+2 voters (from U ′ and U ′′ ) who each have budget of 1/(18n+6), and three voters (from VS) who each have budget equal to 1. To buy this S candidate, the voters from U ′ and U ′′ would have to use up their whole budget, and the voters from VS would have to pay at least:

each. However, at this point there are two candidates that can be purchased at lower per-voter cost.

Indeed, candidate p could be purchased by the 12n voters from Vpd at the per-voter cost of 1/12n (after buying the candidates from CB, they still have exactly this amount of budget left). Since candidate d also is approved by all the voters from Vpd, and also by the voters from U ′ , candidate d would either have the same per-voter cost as p (in case all the members of U ′ were already covered) or would have an even lower per-voter cost. The only other remaining candidates are c1, c2, and the candidates from D, but their per-voter costs are greater or equal to 1/2. Hence, at this point, MEqS either selects p or d. The former is possible exactly if the already selected S-candidates form an exact cover of U ′ (and, hence, correspond to an exact cover for our input instance of X3C).

If we select p, then the 12n voters from Vpd use up all their budget. The remaining voters who approve d, those in U ′ , have total budget equal to at most 3n · 1 18n+6 < 1, so d cannot be selected in any of the following iterations (within Phase 1). On the other hand, if we select d, then all the voters from U ′ would have to pay all they had left (that is, either 0 or 1 18n+6 , each) and voters from Vpd would split the remaining cost. That is, each voter from Vpd would have to pay at least:

Consequently, each voter from Vpd would be left with at most:

This would not suffice to purchase p, as 12n · 1 72n+24 < 1. Thus either we select d (and not p) or we select p (and not d; where this is possible only if we previously purchased Scandidates that cover all members of U ′ ).

In the following iterations, we purchase all remaining Scandidates (because each of them is approved by three unique voters from VS), as well as candidates c1 and c2 (voters d1 and d2 buy them with per-voter cost of 1/2 for each). This uses up the budget of d1 and, so, no candidate from D is selected. All in all, if there is no exact cover for the input X3C instance, then Wd is the unique winning committee, but otherwise Wd and Wp tie. This finishes the proof.

UNIQUE-COMMITTEE is also coNP-complete for the full version of MEqS. To see this, it suffices to note that after adding enough voters with empty votes, MEqS becomes equivalent to Phragm´en (because per-voter budget is so low that Phase 1 becomes vacuous) and inherits its hardness.

On the positive side, for sequential rules we can solve UNIQUE-COMMITTEE in FPT time with respect to the committee size: In essence, we first compute some winning committee and then we try all ways of breaking internal ties to find a different one. For small values of k, such as, e.g., k ≤ 10, the algorithm is fast enough to be practical.

Theorem 3.5. Let f be MEqS, Phase 1 of MEqS, Phragm´en, or a greedy variant of a 1-concave Thiele rule. There is an FPT algorithm for f-UNIQUE-COMMITTEE parameterized by the committee size.

Proof. Let E be the input election and let k be the committee size. First, we compute some committee W in f(E, k), by running the algorithm for f and breaking the internal ties arbitrarily. Next, we rerun the algorithm, but whenever it is about to add a candidate into the constructed committee, we do as follows (let T be the set of candidates that the algorithm can insert into the committee): If T contains some candidate c that does not belong to W, then we halt and indicate that there are at least two winning committees (W and those that include c). If T is a subset of W, then we recursively try each way of breaking the tie. If the algorithm completes without halting, we report that there is a unique winning committee (see the full version of the paper for correctness argument and running time analysis).

For 1-concave Thiele rules other than AV, UNIQUECOMMITTEE is co-W[1]-hard when parameterized by the committee size (this follows from the proof of Proposition 3.1

as INDEPENDENT-SET is W[1]-hard for parameter k). To solve the problem in practice, we note that for each 1-concave Thiele rule there is an integer linear program (ILP) whose solution corresponds to a winning committee. We can either use the ability of some ILP solvers to output several solutions (which only succeeds in case of a tie), or we can use the following strategy: First, we compute some winning committee using the basic ILP formulation. Then, we extend the formulation with a constraint that requires the committee to be different from the previous one and compute a new one. If both committees have the same score, then there is a tie.

4 CountingWinning Committees

Let us now consider the problem of counting the winning committees. Formally, our problem is as follows.

Definition 4.1. Let f be a multiwinner voting rule. In the f#WINNING-COMMITTEES problem we are given an election and a committee size k; we ask for |f(E, k)|.

There are polynomial-time algorithms for computing the number of winning committees for AV and SAV. For an election E with committee size k, we first sort the candidates with respect to their scores in a non-increasing order and we let x be the score of the k-th candidate. Then, we let S be the number of candidates whose score is greater than x, and we let T be the number of candidates with score equal to x. There are ( T k-S) winning committees.

Proposition 4.1. {AV, SAV}-#WINNING-COMMITTEES ∈P

On the other hand, whenever f-UNIQUE-COMMITTEE is intractable, so is f-#WINNING-COMMITTEES. Indeed, it immediately follows that there is no polynomial-time (2 - ε)- approximation algorithm for f-#WINNING-COMMITTEES for any ε > 0 (such an algorithm could solve f-UNIQUECOMMITTEE in polynomial time as for an election with a single winning committee it would have to output 1, and for an election with more winning committees it would have to output an integer greater or equal 2 2-ε > 1, so we could distinguish these cases 3 ). Yet, we have a stronger result.

Proposition 4.2. Let f be a 1-concave Thiele rule (different from AV), its greedy variant, Phragm´en, MEqS or Phase 1 of MEqS. Unless P = NP, there is no polynomial-time approximation algorithm for f -#WINNING-COMMITTEES with polynomially-bounded approximation ratio. 4

We note that the construction given in the proof of Proposition 3.1 also shows that for each 1-concave Thiele rule f ̸= AV, f-#WINNING-COMMITTEES is both #P-hard and #W[1]-hard for parameterization by the committee size (this reduction produces elections that have one more winning committees than the number of size-k independent sets in the input graph, and counting independent sets is both #P-complete and #W[1]-complete for parameterization by k [Valiant, 1979; Flum and Grohe, 2004]). For greedy variants of 1-concave Thiele rules and Phragm´en, we give a new hardness proof, as UNIQUE-COMMITTEE is in FPT.

3 We assume here that if a solution for a counting problem is x ∈ N, then an α-approximation algorithm, with α ≥ 1, has to output an integer between x/α and αx. If we allowed rational values on output, the inapproximability bound would drop to √2 - ε.

4 There is no polynomial p such that there exists a papproximation algorithm solving f-#WINNING-COMMITTEES

Theorem 4.3. Let f be Phragm´en or a greedy variant of a 1-concave Thiele rule (different from AV). f-#WINNINGCOMMITTEES is #P-hard and #W[1]-hard (for the parameterization by the committee size).

Proof. We first consider greedy variants of 1-concave Thiele rules. Let w be the weight function used by f. Let x = w(2) - w(1). We have w(1) = 1 and we assume that x < 1 (we will consider the other case later). We show a reduction from the #MATCHING problem, where we are given a graph G, an integer k, and we ask for the number of size-k matchings (i.e., the number of size-k sets of edges such that no two edges in the set share a vertex). #MATCHING is #Pcomplete and #W[1]-hard for parameterization by k [Curticapean and Marx, 2014].

Let G and k be our input. We form an election E where the edges of G are the candidates and the vertices are the voters. For each edge e = {u, v}, the corresponding edge candidate is approved by the vertex voters corresponding to u and v. We also form an election Ep, equal to E except that it has two extra voters who both approve a single new candidate, p.

We note that every candidate in both E and Ep is approved by exactly two voters. Hence, the greedy procedure first keeps on choosing candidates whose score is 2 (i.e., edges that jointly form a matching, or candidate p in Ep). It selects the candidates with lower scores (i.e., edges that break a matching) only when score-2 candidates disappear.

Let W be some size-k f-winning committee for election Ep. We consider two cases:

1. If p does not belong toW, then the edge candidates inW form a matching. If it were not the case, then before including an edge candidate with score lower than 2, the greedy algorithm would include p in the committee.
2. If p belongs to W then W \ {p} is an f-winning committee of size k - 1 for election E. Indeed, if we take the run of the greedy algorithm that computes W and remove the iteration where p is selected, we get a correct run of the algorithm for election E and committee size k - 1. Further, for every size-(k - 1) committee winning in E, S ∪ {p} is a size-k winning committee in Ep (because we can always select p in the first iteration).

So, to compute the number of size-k matchings in G, we take the number of winning size-k committees in Ep and subtract from it the number of winning size-(k - 1) committees in E. Rest of the argument is in the full paper.

Corollary 4.4. #WINNING-COMMITTEES is #P-hard and #W[1]-hard (for the parameterization by the committee size)

for GreedyCCAV, GreedyPAV, Phragm´en, and MEqS.

The above result holds for MEqS because of its relation to Phragm´en. For Phase 1 of MEqS, we have #P-hardness but #W[1]-hardness so far remains elusive.

Theorem 4.5. #WINNING-COMMITTEES is #P-hard for Phase 1 of MEqS.

5 Experiments

A'priori, it is not clear how frequent ties are in multiwinner elections. In this section we present experiments that show that they are quite common, at least if one considers elections of moderate size. Our code is available at https://github.com/ Project-PRAGMA/Ties-IJCAI-2023.

5.1 Statistical Cultures and the Basic Experiment

Below we describe how we generate elections and how we perform our basic experiments.

Resampling Model [Szufa et al., 2022] We have two parameters, p and ϕ, both between 0 and 1. To generate an election with candidate set C = {c1, . . . , cm} and with n voters, we first choose uniformly at random a central vote u approving exactly ⌊pm⌋ candidates. Then, we generate the votes, for each considering the candidates independently, one by one. For a vote v and candidate c, with probability 1 - ϕ we copy c's approval status from u to v (i.e., if u approves c, then so does v; if u does not approve c then neither does v), and with probability ϕ we "resample" the approval status of c, i.e., we let v approve c with probability p. On average, each voter approves about pm candidates.

Interval Model. In the Interval model, each voter and each candidate is a point on the interval [0, 1], chosen uniformly at random. Additionally, each candidate c has radius rc and a voter v approves candidate c if the distance between their points is at most rc. Intuitively, the larger the radius, the more appealing a given candidate is. We generate the radii of the candidates by taking a base radius r as input and, then, choosing each candidates' radius from the normal distribution with mean r and standard deviation r/2. Such spatial models are discussed in detail, e.g., by Enelow and Hinich; Enelow and Hinich [1984; 1990]. In the approval setting, they were recently considered, e.g., by Bredereck et al. [2019] and Godziszewski et al. [2021].

PabuLib Data. PabuLib is a library of real-life participatory budgeting (PB) instances, mostly from Polish cities [Faliszewski et al., 2023]. A PB instance is a multiwinner election where the candidates (referred to as projects) have costs and the goal is to choose a "committee" of at most a given total cost. We restrict our attention to instances fromWarsaw, which use approval voting, and we disregard the cost information (while this makes our data less realistic, we are not aware of other sources of real-life data for approval elections that would include sufficiently large candidate and voter sets). To generate an election with m candidates and n voters, we randomly select a Warsaw PB instance, remove all but m candidates with the highest approval score, and randomly draw n voters (with repetition, restricting our attention only to voters who approve at least one of the remaining candidates). We also considered several other strategies of choosing the candidates and obtained very similar results. Another argument for focusing on the most approved candidates is that the voters cared about them the most (in aggregate). We consider 120 PB instances fromWarsaw that include at least 30 candidates (and each of them includes at least a thousand votes).

Basic Experiment. In a basic experiment we fix the number of candidates m, the committee size k, and a statistical culture. Then, for each number n of voters between 20 and 100 (with a step of 1) we generate 1000 elections with m candidates and n voters, and for each of them compute whether our rules have a unique winning committee (we omit GreedyCCAV). Then we present a figure that on the x axis has the number of voters and on the y axis has the fraction of elections that had a unique winning committee for a given rule. For AV and SAV, we use the algorithm from the beginning of Section 4, for sequential rules we use the FPT algorithm from Theorem 3.5, and for CCAV and PAV we use the ILP-based approach, with a solver that provides multiple solutions.

5.2 Results

All our experiments regard 30 candidates and committee size 5. First, we performed three basic experiments for the resampling model with the parameter p (approval probability) set so that, on average, each voter approved either k/2, k, or 2k candidates. We used ϕ = 0.75 (according to the results of Szufa et al. [2022], this value gives elections that resemble the real-life ones). We present the results in the top row of Figure 1. Next, we also performed two basic experiments for the Interval model (with the base radius selected so that, on average, each voter approved either k/2 or k candidates), and with the PabuLib data (see the second row of Figure 1). These experiments support the following general conclusions.

First, for most scenarios and for most of our rules, there is a nonnegligible probability of having a tie (where, depending on the rule and the number of voters, this probability may be as low as 5% or as high as nearly 100%). This justifies why one needs to be ready to detect and handle ties in moderately sized multiwinner elections.

Second, we see that SAV generally leads to fewest ties, CCAV leads to most, and AV often holds a strong second position in this category. The other rules are in between. Phase 1 of MEqS often has significantly fewer ties than the other rules, but full version of MEqS does not stand out. PAV occasionally leads to fewer ties (in particular, on PabuLib data and on the resampling model with 2k approvals per vote).

6 Summary

We have shown that, in general, detecting ties in multiwinner elections is intractable, but doing so for moderately-sized ones is perfectly possible. Our experiments show that ties in such elections are a realistic possibility and one should be ready to handle them. Intractability of counting winning committees suggests that tie-breaking by sampling committees may not be feasible. Looking for fair tie-breaking mechanisms is a natural follow-up research direction.

Acknowledgments

This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 101002854).