The Core of Approval-Based Committee Elections with Few Seats

1 Introduction

The seminal work of Aziz et al. [2016; 2017] introduced a rigorous way of reasoning about voter representation in multiwinner elections. Their model considers approval-based committee elections, where the task is to identify a committee 𝑊 ⊆ 𝐶 of 𝑘 out of 𝑚 candidates, based on the preferences of a set of voters 𝑁, with each 𝑖 ∈ 𝑁 indicating a subset 𝐴𝑖 ⊆ 𝐶 of candidates that 𝑖 approves. Aziz et al. [2017] formulated a compelling axiom called Extended Justified Representation (EJR) which gives representation guarantees to every group of voters who approve sufficiently many candidates in common. Researchers discovered that voting rules developed 130 years ago by Thiele [1895] and Phragm´en [1894] satisfy this or related axioms [Brill et al., 2023; Aziz et al., 2017; Janson, 2016]. Interesting new rules satisfying EJR have recently been developed [Aziz et al., 2018; Peters and Skowron, 2020; Brill and Peters, 2023], with one of them (the "Method of Equal Shares") now in active use for the participatory budgets in several cities in Poland, Switzerland, and the Netherlands.

Aziz et al. [2016; 2017, Section 5.2] also defined another representation axiom that is significantly stronger than EJR, called core stability in analogy to a similar concept from cooperative game theory. A committee 𝑊 is core stable if for every set 𝑇 ⊆ 𝐶, there are not too many voters who prefer the set 𝑇 to 𝑊, namely we have

If this inequality were violated for some 𝑇, then the set of voters on the left-hand side could form a blocking coalition of a size that is large enough for the coalition to "deserve" to decide to include 𝑇 in the committee.

The EJR property is weaker than core stability (as under EJR voters are only allowed to join the blocking coalition if they approve all the candidates in 𝑇, i.e., |𝐴𝑖 ∩𝑇 | = |𝑇 |), but in exchange there are several attractive voting rules satisfying EJR. On the other hand, Aziz et al. [2016; 2017] noted that "the core stability condition appears to be too demanding, as none of the voting rules considered in our work is guaranteed to produce a core stable outcome". No such voting rules have been discovered since. They conclude: "It remains an open question whether the core [is always] non-empty." This question remains open more than 8 years later.

Some amount of progress has been made, and in particular it is known that there always exist committees satisfying approximate variants of the core [Peters and Skowron, 2020; Jiang et al., 2020; Munagala et al., 2022b], and the core exists on single-peaked approval profiles [Pierczy´nski and Skowron, 2022] and on profiles where each candidate has at least 𝑘 copies [Brill et al., 2022].

To the best of my knowledge, the only known existence result that holds in general is that the core is non-empty for 𝑘 = 3, which Cheng et al. [2020, Section 3.1] showed by case analysis. Cheng et al. [2020] conclude that a "major open question is the existence of deterministic stable committees in the Approval Set setting, generalizing our positive result for 𝑘 = 3 to general 𝑘. We conjecture that such a stable committee always exists. Via computer-assisted search, we have shown that this conjecture holds for small numbers of voters and candidates (𝑚 + 𝑛 ⩽ 14)."

It might seem surprising that the state of the art has not improved beyond these very small parameter values. In particular, there is a natural way of using mixed integer linear programming (ILPs) to search for counterexamples to core existence: fix 𝑚 and 𝑘, and introduce a fractional variable for each possible ballot, indicating what fraction of the voters submit this ballot. Then, for every committee, enforce using binary variables that there is at least one successful core deviation. If an ILP solver determines that the resulting program is infeasible, this implies the non-emptiness of the core for 𝑚 and 𝑘, for any number 𝑛 of voters. Unfortunately, the size of this program grows rapidly, and they are not easy to solve even for very small sizes (Gurobi solves 𝑚 = 7, 𝑘 = 5, in 450s, but did not solve 𝑚 = 7, 𝑘 = 4 after 134 000s (37h) on 8 cores). 1

In this paper, by deriving a new way of using solvers, we show that the core always exists for committee sizes up to 𝑘 = 8, for any number of candidates (improving upon the previous result for 𝑘 = 3). We also show that the core always exists when the number 𝑚 of candidates is at most 15, for any 𝑘 ⩽ 𝑚. Both results hold for any number 𝑛 of voters.

These results are obtained by analyzing variants of Proportional Approval Voting (PAV), the voting rule proposed by Thiele [1895]. This voting rule works by maximizing a carefully chosen objective function over the set of all committees of size 𝑘. We show via linear programs that PAV always selects a core-stable committee when 𝑘 ⩽ 7, and that it always selects at least one core-stable committee when 𝑘 = 8, perhaps tied with other committees that fail core-stability. This performance of the PAV rule is remarkable, and contrasts with other rules such as the Phragm´en rule and the Method of Equal Shares which fail the core for 𝑘 = 6 and 𝑘 = 7, respectively (see Footnote 3). In many applications, the number of seats to fill will be 8 or fewer, and thus our result suggests that PAV is a good rule for such contexts. 2

For the results about limited numbers of candidates, we consider a recursive version of PAV where, if the PAV committee fails the core because some set 𝑇 has too much support, we then re-compute PAV subject to the constraint that 𝑇 ⊆ 𝑊 and without taking into account the voters who were part of the blocking coalition. If the result still fails core-stability, we add additional constraints. We show that if 𝑚 ⩽ 15, this process always terminates with a core-stable committee. However, there are examples where the rule is not in the core for 𝑚 = 16.

As mentioned, these results were obtained with the help of linear programming. This becomes feasible even for these quite large sizes because we can fix one committee, and add constraints that this committee is the one selected by the voting rule under consideration. This is much simpler than a program that needs constraints for all possible committees. Linear programming has been used before to analyze sequential versions of PAV [Skowron, 2021; S´anchez-Fern´andez et al., 2017]. The infeasibility of the relevant programs can be compactly certified via Farkas' lemma, allowing efficient verification of our results without having to trust a solver. Code for these tasks is available at https: //github.com/DominikPeters/core-few-candidates/. Some details and proofs have been omitted in this conference version due to space constraints; these can be found in the full version at arXiv:2501.18304 [Peters, 2025].

1 The same problem can also be encoded as an SMT problem on linear arithmetic. This can sometimes lead to faster solve times, but it is also only feasible for very small sizes.

2 Note, however, that even for 𝑘 = 6, PAVmay select committees that fail laminar proportionality [Peters and Skowron, 2020] and are intuitively unfair. A three-voter example for 𝑘 = 6 is 𝐴1 = {𝑐1, 𝑐2, 𝑐3}, 𝐴2 = {𝑐1, 𝑐2, 𝑐4}, and 𝐴3 = {𝑐5, 𝑐6, 𝑐7} where 𝑊 = {𝑐1, 𝑐2, 𝑐3, 𝑐5, 𝑐6, 𝑐7} is a global PAV committee (tied with others) while laminar proportionality demands that {𝑐1, 𝑐2, 𝑐3, 𝑐4} ⊆ 𝑊.

2 RelatedWork

Barriers to core existence. Proving that the core is nonempty is difficult because several natural strategies are known not to work. Importantly, all known voting rules that satisfy weakenings of the core such as EJR fail the core, including the PAV rule [Aziz et al. 2017, Example 6; Peters and Skowron 2020, Section 1]. Peters and Skowron [2020, Theorem 10] show that every welfarist rule (one that depends only on voter utilities) must fail the core. They also show that every voting rule satisfying the Pigou-Dalton principle (which says that outcomes that induce a more equitable social welfare distribution should be preferred; this is satisfied by PAV) cannot satisfy the core, and indeed cannot provide better than a 2-approximation to it Peters and Skowron [2020, Theorem 5].

Computational complexity. It is NP-hard to compute the PAV rule [Aziz et al., 2015, Corollary 1], but it is fixedparameter tractable for a variety of parameters [Yang and Wang, 2023]. A local search variant of PAV retains its proportionality properties and can be computed in polynomial time [Aziz et al., 2018] for an appropriately chosen tolerance parameter [Kraiczy and Elkind, 2024]. The problem of checking whether a given committee is in the core is coNP-complete [Brill et al., 2022, Theorem 5.3] and remains hard even when every voter approves at most 6 candidates, and each candidate is approved by at most 2 voters [Munagala et al., 2022a, Theorem 1]. The verification problem is also hard to approximate to within a factor better than 1 + 1/𝑒 [Munagala et al., 2022a, Theorem 2], though a logarithmic approximation algorithm exists [Munagala et al., 2022a, Theorem 3].

More general settings. We work in the model of approvalbased committee elections. If non-approval preferences are allowed (such as cardinal additive valuations), the core may be empty [Fain et al. 2018, Appendix C; Peters et al. 2021, Example 2]. For participatory budgeting applications, one can replace the cardinality constraint in the definition of a committee by a knapsack constraint. For this non-unit cost setting, approval votes have several interpretations [Rey and Maly, 2023, Section 3.4.2]. One option is cost utilities, which measures a voter's utility by the total cost of approved winning projects. For this utility model, the core may be empty [Maly, 2023]. For cardinality utilities, where the voter's utility is the number of approved winning projects, the non-emptiness of the core is an open question.

Approximate core. Core stability can be relaxed through multiplicative approximations, in two main ways. Say that a committee 𝑊 is in the (𝛼, 𝛽)-core, 𝛼, 𝛽 ⩾ 1, if we have |{𝑖 ∈ 𝑁 : |𝐴𝑖 ∩ 𝑇 | > 𝛼 · |𝐴𝑖 ∩𝑊|}| < 𝛽 · |𝑇 | · 𝑛 𝑘 for every potential deviation 𝑇. For 𝛼 = 𝛽 = 1, this is the core; for 𝛼 > 1, every member of the blocking coalition must increase their utility by a factor of 𝛼; for 𝛽 > 1, we require that blocking coalitions must be larger than usual by a factor of 𝛽.

Peters and Skowron [2020] show that PAV is in the (2, 1)- core, and that the Method of Equal Shares is in the (log 𝑘, 1)- core (or a mild relaxation of that concept). Munagala et al. [2022b] show that the (9.27, 1)-core is non-empty even for general additive valuations. Fain et al. [2018, Appendix C] show that the (1 + 𝜀, 1)-core is non-empty if it is additionally additively relaxed. Jiang et al. [2020] show that the (1, 16)- core is non-empty, via rounding a stable lottery [Cheng et al., 2020]; they conjecture that at least the (1, 2)-core is always non-empty. A similar rounding technique has been used to analyze Condorcet winning sets [Charikar et al., 2024].

Fractional models. Analogs of core-stability have also been defined in fractional models. For example, Aziz et al. [2020] consider "fair mixing" in an approval-based model, where the output is a probability distribution over candidates (which can be interpreted as a division of a budget). They show that the rule maximizing Nash welfare (which is related to the PAV rule) satisfies core-stability. Fain et al. [2016] obtain the same result in a more general model with additive linear utilities. They also show that a core-stable outcome exists for fractional committees (which can be viewed as a probability distribution where each candidate receives mass at most 1/𝑘) via Lindahl equilibrium which is known to exist from fixedpoint theorems [Foley, 1970; Munagala et al., 2022b] and via convex programming [Kroer and Peters, 2025]. Various weakenings of the core have also been studied in approvalbased fair mixing and related models [see, e.g., Brandl et al. 2021; Suzuki and Vollen 2024; Bei et al. 2025].

3 Preliminaries

Let 𝐶 = {𝑐1, . . . , 𝑐𝑚} be a set of 𝑚 candidates. Let 𝑘 ∈ {1, . . . , 𝑚} be the committee size. A committee is a subset 𝑊 ⊆ 𝐶 of winning candidates with |𝑊| = 𝑘.

Let A denote the set of non-empty subsets of 𝐶, which we will refer to as approval sets or ballots. A profile is a map 𝑃 : A → Q⩾0 with � 𝐴∈A 𝑃(𝐴) = 1, where 𝑃(𝐴) indicates the fraction of the voters that approve exactly the candidates in 𝐴. Given an approval set 𝐴 ∈ A and a committee 𝑊, the utility of the committee for 𝐴 is the number of approved committee members: 𝑢𝐴(𝑊) = |𝐴 ∩𝑊|.

A nonempty set 𝑇 ⊆ 𝐶 with |𝑇 | ⩽ 𝑘 is called a potential deviation. Given a profile 𝑃, a committee 𝑊 is core stable if for every potential deviation 𝑇, we have

Otherwise, 𝑇 is called a deviation (or a successful deviation) from𝑊. The core is the set of committees that are core stable. The 𝑛th harmonic number is 𝐻(𝑛) = 1 + 1 2 + 1 3 + · · · + 1 𝑛 . The PAV score assigned to a committee 𝑊 by ballot 𝐴 ∈ A is

Given a profile 𝑃, the PAV score of 𝑊 under profile 𝑃 is

A committee is a global PAV committee if it has the highest PAV score. The PAV rule selects all global PAV committees.

We will also be interested in local maxima of the PAV objective, i.e., committees that have a weakly higher PAV score than any committee obtained by performing a single swap. For a committee 𝑊, 𝑥 ∈ 𝑊 and 𝑦 ∈ 𝐶 \ 𝑊, we write 𝑊𝑥𝑦 = 𝑊 \ {𝑥} ∪ {𝑦} for the committee obtained by replacing 𝑥 with 𝑦. Given a profile 𝑃 and a fixed committee 𝑊, we write

for the increase in PAV score resulting from this swap. For a ballot 𝐴, we define Δ𝐴,𝑥,𝑦 analogously. Then we say that 𝑊 is a local PAV committee if Δ𝑃,𝑥,𝑦 ⩽ 0 for all 𝑥 and 𝑦. Note that every global PAV committee is also a local PAV committee.

The following lemma shows that a local PAV committee never admits deviations of certain kinds: disjoint deviations and deviations that contain only a single unelected candidate.

Lemma 3.1. Let 𝑊 be a local PAV committee, and let 𝑇 be a potential deviation. Suppose we have

Then 𝑇 is not a deviation from𝑊.

Proof. (i) is proved by Brill et al. [2022, Theorem 3.2 and Remark 3.4] using a swapping argument.

(ii) If 𝑇 \ 𝑊 = ∅, then 𝑇 ⊆ 𝑊, and there are no approval ballots that strictly prefer 𝑇 to 𝑊. If 𝑇 \ 𝑊 = {𝑐}, then for every 𝐴 ∈ A with 𝑢𝐴(𝑇) > 𝑢𝐴(𝑊), we have 𝑐 ∈ 𝐴. Writing ℓ = |𝑇 |, if 𝑇 were a deviation, we would thus have a set 𝑆 of ballots forming ℓ/𝑘 of the profile, who all approve 𝑐 ∉ 𝑊, and who all have utility 𝑢𝐴(𝑊) < 𝑢𝐴(𝑇) ⩽ ℓ. Thus, we have a violation of the EJR+ axiom of Brill and Peters [2023] which local PAV committees are known to satisfy. □

Note that Theorem 3.1(ii) implies that PAV satisfies the core when 𝑘 = 𝑚 - 1 or 𝑘 = 𝑚.

We recall the following well-known result about systems of linear inequalities, providing a certificate of infeasibility.

Lemma 3.2 (Farkas' Lemma). Let 𝐴 ∈ Q 𝑚𝑛 be an 𝑚 × 𝑛 matrix, and let 𝑏 ∈ Q 𝑚 . Then the following are equivalent.

• (i) There does not exist 𝑥 ∈ Q 𝑛 with 𝐴𝑥 ⩽ 𝑏.
• (ii) There exists an integer vector 𝑦 ∈ Z 𝑚 ⩾0 such that 𝑦 𝑇 𝑏 < 0 and 𝐴 𝑇 𝑦 ⩾ 0.

Thus, by exhibiting the integer vector 𝑦, one can prove the infeasibility of the system 𝐴𝑥 ⩽ 𝑏.

4 Small Committee Size

In this section, we discuss core-stable committees when the committee size 𝑘 is small. We give existence results when 𝑘 ⩽ 8, separately handling the cases 𝑘 ⩽ 7 and 𝑘 = 8.

4.1 Committee Size 𝑘 ⩽ 7

For committee sizes up to 7, core-stable committees always exist because every local PAV committee is in the core. This establishes existence of core-stable committees, but also indicates that PAV rule is a very good rule for smaller committee sizes. 3 Like other proofs that PAV is proportional, our proof reasons about the change in PAV score caused by certain swaps. In particular, it shows that if 𝑊 is a committee with |𝑊| ⩽ 7 such that 𝑇 is a successful deviation, then on average, replacing an element of 𝑊 \ 𝑇 by an element of 𝑇 \ 𝑊 will increase the PAV score of 𝑊. Hence there exists at least one such swap that increases the PAV score of 𝑊, and hence it cannot be a local PAV committee. The proof is omitted due to space constraints, but can be found in the full version [Peters, 2025]. To establish a key inequality, the proof refers to the result of a computer enumeration of all possible ballot types, which can be reproduced using code available on GitHub.

Theorem 4.1. When 𝑘 ⩽ 7, every local PAV committee is in the core.

The result of Theorem 4.1 can also be obtained by linear programming. Suppose that the result is false, so that there exists a profile 𝑃 and a local PAV committee 𝑊 such that some 𝑇 is a successful deviation. Without loss of generality, there exists such an example with 𝑊 = {𝑐1, . . . , 𝑐𝑘}. Note that 𝑃 then forms a solution to the following system of linear inequalities, where we may assume that 𝐶 = 𝑊 ∪ 𝑇: 4

Thus, Theorem 4.1 is proven if the system (1) does not have a feasible solution, for all potential deviations 𝑇. This can be certified using Farkas' lemma, and the proof of Theorem 4.1 implicitly constructs such a certificate solution for every 𝑇.

Due to the following remark, it is possible to compute a core-stable outcome in 𝑂(𝑚 2 𝑛) time whenever 𝑘 ⩽ 7.

Remark 4.2. Let 𝑘 ⩽ 7 and 𝜀 = 0.1/𝑘 2 . By solving linear programs [code on GitHub], one can check that every committee that is 𝜀-local-swap-stable (i.e., Δ𝑃,𝑥,𝑦 ⩽ 𝜀 for all 𝑥 and 𝑦) is in the core. An 𝜀-local-swap-stable and thus a core-stable committee can be found by performing 𝑂(𝑘 2 ln 𝑘) = 𝑂(1) many 𝜀-improving swaps [see Aziz et al. 2018, Proposition 1], each of which takes 𝑂(𝑚 2 𝑛) time to find. It turns out that for 𝜀 = 1/𝑘 2 , 𝜀-local-swap-stable committees need not be in the

3 There are examples where the sequential Phragm´en rule fails core (and even EJR) for 𝑘 = 6, and where MES fails core for 𝑘 = 7. These counterexamples work even for the party-approval setting [Brill et al., 2022], where each candidate can be placed in the committee several times. For Phragm´en, take the 3-voter profile (𝑎𝑏, 𝑏𝑐, 𝑎𝑐), where Phragm´en can elect 𝑎𝑏𝑎𝑏𝑎𝑏, with 𝑇 = {𝑐, 𝑐, 𝑐, 𝑐} forming a deviation. For MES, take the 7-voter profile (𝑎𝑏, 𝑎𝑐, 𝑎𝑑, 𝑏𝑐𝑑, 𝑏𝑐𝑑, 𝑏𝑐𝑑, 𝑏𝑐𝑑), where 𝑏𝑏𝑏𝑏𝑏𝑎𝑎 is an outcome of MES, with 𝑇 = {𝑐, 𝑐, 𝑐, 𝑑, 𝑑, 𝑑} forming a deviation. (In these examples, there are other tied outcomes in the core, and I don't know if unique examples exist.)

4 We may make this assumption because a counterexample on a larger 𝐶 remains a counterexample when restricted to 𝑊 ∪𝑇, because a local PAV committee remains a local PAV committee after deleting candidates outside the committee.

core, even though this value of 𝜀 is enough to ensure that the committee satisfies EJR [Aziz et al., 2018, Theorem 1]. For example, in the profile with 𝑃({𝑎, 𝑏}) = 𝑃({𝑎, 𝑐}) = 0.25 and 𝑃({𝑑, 𝑒, 𝑓 , 𝑔, ℎ}) = 0.5, for 𝑘 = 6, the committee {𝑎, 𝑑, 𝑒, 𝑓 , 𝑔, ℎ} fails the core due to 𝑇 = {𝑎, 𝑏, 𝑐}, but it is 1/40-local-swap-stable, and 1/40 < 1/36 = 1/𝑘 2 .

4.2 Committee Size 𝑘 = 8

Theorem 4.1 does not hold for 𝑘 = 8: There are profiles where some local (and even global) PAV committee is not in the core.

Example 4.3 (PAV may fail core for 𝑘 = 8). Consider an instance with 4 voters, 𝑣1 approving {𝑐1, 𝑐2, 𝑐3}, and 𝑣2 approving {𝑐1, 𝑐2, 𝑐4}, and the other 2 voters approving {𝑐5, 𝑐6, 𝑐7, 𝑐8, 𝑐9, 𝑐10}. This profile is depicted below, where each voter approves the candidates above the voter's label.

On this profile, 𝑊 = {𝑐1, 𝑐2, 𝑐5, 𝑐6, 𝑐7, 𝑐8, 𝑐9, 𝑐10} is a global PAV committee (indicated in blue in the picture). However, 𝑊 is not in the core: consider 𝑇 = {𝑐1, 𝑐2, 𝑐3, 𝑐4}, which has support from 1 2 of the voters, and |𝑇 |/𝑘 = 1 2 . □

Note, however, that in Theorem 4.3, there is more than one global PAV committee. In particular, 𝑊 ′ = {𝑐1, 𝑐2, 𝑐3, 𝑐5, 𝑐6, 𝑐7, 𝑐8, 𝑐9} (obtained by removing 𝑐10 and adding 𝑐3) is also a global PAV committee and it is in the core.

It turns out that Theorem 4.3 is essentially the only example where a PAV committee fails to be core-stable for 𝑘 = 8, as all such examples share the same structure.

Lemma 4.4. Let 𝑃 be a profile and suppose that 𝑊 with |𝑊| = 8 is a local PAV committee that is not in the core due to objection 𝑇. Then there exist distinct 𝑎, 𝑏 ∈ 𝑊 and distinct 𝑥, 𝑦 ∈ 𝐶 \𝑊 such that 𝑇 = {𝑎, 𝑏, 𝑥, 𝑦}. In addition,

• (i) one quarter of the voters submit ballots 𝐴 such that 𝐴 ∩ (𝑊 ∪ 𝑇) = {𝑎, 𝑏, 𝑥} and another quarter submit ballots with 𝐴 ∩ (𝑊 ∪𝑇) = {𝑎, 𝑏, 𝑦},
• (ii) the remaining half of the voters submit ballots that are disjoint from𝑇, and
• (iii) the PAV score of 𝑊 is reduced by exactly 1/12 if any one member of 𝑊 \ {𝑎, 𝑏} is removed.

Proof. We first check that if 𝑊 is not in the core, then any core objection must use a 𝑇 with |𝑇 | = 4 and |𝑊 ∩ 𝑇 | = 2. This can be deduced using the linear programming approach behind Theorem 4.1; by iterating through all possible 𝑇, we find that the system (1) has a solution only for 𝑇 satisfying the condition in the theorem statement.

Now fix such a 𝑇 = {𝑎, 𝑏, 𝑥, 𝑦}. Assume that there exists a profile 𝑃 where 𝑊 is a local PAV committee with successful deviation 𝑇 but that violates any of the conditions (i)-(iii). Then if we delete all candidates outside 𝑊 ∪𝑇 from the profile, it would still fail (i)-(iii). Thus, for purposes of making the following linear programs finite, we may assume that 𝐶 = 𝑊 ∪𝑇 (so |𝐶| = 10).

To prove (i), we solve the following four linear programs:

maximize 𝑃({𝑎, 𝑏, 𝑥}) subject to 𝑃 satisfying (1) minimize 𝑃({𝑎, 𝑏, 𝑥}) subject to 𝑃 satisfying (1) maximize 𝑃({𝑎, 𝑏, 𝑦}) subject to 𝑃 satisfying (1) minimize 𝑃({𝑎, 𝑏, 𝑦}) subject to 𝑃 satisfying (1)

The optimal solutions to all these programs is 1 4 .

To prove (ii), iterate through all ballots 𝐴 ∈ A with 𝐴∩𝑇 ≠ ∅, except for {𝑎, 𝑏, 𝑥} and {𝑎, 𝑏, 𝑦}. For each of these ballots, solve the following linear program:

maximize 𝑃(𝐴) subject to 𝑃 satisfying (1)

For each such 𝐴, the optimal solution of the program is 0. To prove (iii), iterate through all 𝑐 ∈ 𝑊 \ {𝑎, 𝑏} and solve the following programs, both again subject to 𝑃 satisfying (1):

maximize PAV-score𝑃 (𝑊 \ {𝑐}) - PAV-score𝑃 (𝑊)

minimize PAV-score𝑃 (𝑊 \ {𝑐}) - PAV-score𝑃 (𝑊)

The optimal solutions to these two programs are -1/12. □

The claims made in this proof about the optimal values of the various linear programs can be certified by exhibiting solutions to the dual programs. These certificates (using exact fractions, not floating point numbers) are available on GitHub, together with a script checking their validity without a solver.

As we discussed, Theorem 4.3 shows an example of a global PAV committee that is not core-stable, but there are other global PAV committees for the same profile that are corestable. Thanks to Theorem 4.4, we deduce that the same holds for all counterexamples. Hence, for every instance, at least one global PAV committee is in the core, and thus the core is always non-empty for 𝑘 = 8.

Theorem 4.5. When 𝑘 = 8, some global PAV committee is in the core.

Proof. Let 𝑘 = 8 and let 𝑃 be a profile. If on 𝑃, all global PAV committees are in the core, we are done. So suppose that 𝑊 is a global PAV committee that is not core stable due to objection 𝑇. From Theorem 4.4, there exist distinct 𝑎, 𝑏 ∈ 𝑊 and distinct 𝑥, 𝑦 ∈ 𝐶 \𝑊 such that 𝑇 = {𝑎, 𝑏, 𝑥, 𝑦}. Take any 𝑐 ∈ 𝑊 \ {𝑎, 𝑏}. Then the committee 𝑊 ′ = 𝑊 \ {𝑐} ∪ {𝑥} has the same PAV score as 𝑊, because the removal of 𝑐 causes a decrease in PAV score of 1/12 and the addition of 𝑥 causes an increase of at least 1 4 · 1 3 = 1/12 due to the quarter of voters from (i) with ballots 𝐴 such that 𝐴 ∩ (𝑊 ∪ 𝑇) = {𝑎, 𝑏, 𝑥}. Thus, 𝑊 ′ is also a global PAV committee. We now show that 𝑊 ′ is in the core.

If not, we can apply Theorem 4.4 to 𝑊 ′ which gives us an objection 𝑇 ′ = {𝑎 ′ , 𝑏 ′ , 𝑥 ′ , 𝑦 ′ } to 𝑊 ′ . Clearly, voters with ballots such that 𝐴 ∩ (𝑊 ∪ 𝑇) = {𝑎, 𝑏, 𝑥} are not part of a blocking coalition because {𝑎, 𝑏, 𝑥} ⊆ 𝑊 ′ . Thus, we deduce that 𝑎, 𝑏 ∉ 𝑇 from (ii). Thus, the voters with ballots such that 𝐴 ∩ (𝑊 ∪ 𝑇) = {𝑎, 𝑏, 𝑦} are also not supporters of 𝑇 ′ . Then from part (i) we deduce that the only members of 𝑊 that are approved by any voters in 𝑃 are 𝑎, 𝑏, 𝑎 ′ , and 𝑏 ′ . Thus, there exists a member of 𝑊 \ {𝑎, 𝑏} who is not approved by any voter, so the removal of that member does not lead to a reduction in PAV score, contradicting (iii). □

4.3 Committee Size 𝑘 ⩾ 9

The PAV-based technique that worked for up to 𝑘 = 8 does not continue to work for 𝑘 = 9, since there are examples where there is a unique global PAV committee which fails to be in the core. The following example has this property, and is minimal with respect to the number of voters (𝑛 = 27).

5 FewCandidates

The goal of this section is to show that there always exists a core-stable committee on instances with 𝑚 ⩽ 15 candidates. From the results in Section 4, this is clearly true when 𝑘 ⩽ 8. By Theorem 3.1(ii), this is also true when 𝑘 = 𝑚 - 1 or 𝑘 = 𝑚. But it is not clear when 𝑘 ∈ {9, . . . , 𝑚 - 2}.

Inspecting the examples in Section 4 where PAV fails the core, we see that they are well-structured. Indeed, they are even laminar instances in the sense of Peters and Skowron [2020, Definition 2], and it is easy to see that on these profiles, a core-stable committee does exist. Thus, there is some hope to prove existence of core-stable committees by "patching" the PAV committee when it fails to be in the core.

We will define an artificial rule, based on PAV, and we will show that it satisfies core stability for up to 𝑚 = 15 candidates. We call it the recursive PAV rule. On a high level, the rule first computes a local PAV committee, and checks if it satisfies the core. If so, it returns it. If not, and 𝑇 is a deviation from 𝑊, it then deletes all voters who prefer 𝑇 to 𝑊, and computes a local PAV committee with respect to the remaining voters, but subject to the constraint that 𝑇 ⊆ 𝑊. It then checks if the result is in the core; if not, it adds additional constraints until it reaches a core-stable committee. This rule is formally described using pseudocode in Algorithm 1.

For example, in the profile of Theorem 4.3, PAV selects the committee 𝑊 indicated there in blue (among other tied committees). This committee is blocked by 𝑇 = {𝑐1, 𝑐2, 𝑐3, 𝑐4}. Thus, the recursive PAV rule would now fix all members of 𝑇 as winners, and maximize the PAV-score with respect to voters 𝑣3 and 𝑣4, obtaining the committee 𝑊 ∗ = {𝑐1, 𝑐2, 𝑐3, 𝑐4, 𝑐5, 𝑐6, 𝑐7, 𝑐8} (among other tied committees). This committee is in the core, so the rule terminates. Note that 𝑊 ∗ is not itself selected by PAV.

Algorithm 1 Recursive PAV rule

Input: A profile 𝑃 and a committee size 𝑘 Output: A committee 𝑊 A ′ ←A, set of active ballots 𝐹 ← ∅, set of fixed candidates while true do If |𝐹| > 𝑘, the algorithm fails 𝑊 ← any committee locally maximizing the PAV score w.r.t. the ballots in A ′ and subject to 𝐹 ⊆ 𝑊 if there exists a successful deviation 𝑇 from𝑊 then 𝐹 ← 𝐹 ∪𝑇 A ′ ←A ′ \ {𝐴 ∈ A : 𝑢𝐴(𝑇) > 𝑢𝐴(𝑊)} else return 𝑊

This method is reminiscent of the Greedy Cohesive Rule [Peters et al., 2021], which similarly repeatedly patches a committee until it satisfies the representation axiom FJR.

5.1 Analysis of the Method

Fix a number of candidates 𝑚 and a committee size 𝑘.

A list (𝑊1, 𝑇1), (𝑊2, 𝑇2), . . . , (𝑊𝑟 , 𝑇𝑟 ) is called a potential history if for each 𝑡 ∈ [𝑟], we have that 𝑊𝑡 is a committee, 𝑇𝑡 is a potential deviation, and 𝑇1 ∪ · · · ∪ 𝑇𝑡-1 ⊆ 𝑊𝑡 .

Definition 5.1. A potential history (𝑊1, 𝑇1), . . . , (𝑊𝑟 , 𝑇𝑟 ) is a history if there exists a profile 𝑃 such that for each 𝑡 ∈ [𝑟] we have that 𝑇𝑡 is a successful deviation from𝑊𝑡 , and that for all 𝑥 ∈ 𝑊 \ (𝑇1 ∪ · · · ∪𝑇𝑡-1) and 𝑦 ∈ 𝐶 \𝑊, we have

where A𝑡 = {𝐴 ∈ A : 𝑢𝐴(𝑇𝑠) ⩽ 𝑢𝐴(𝑊𝑠) for 𝑠 ∈ {1, . . . , 𝑡 - 1}} is the set of "active" ballots. That is, 𝑊𝑡 locally maximizes the PAV score among all committees that include all prior deviations, taking only those voters into account that did not participate in prior deviations.

Thus, a history provides a trace of the execution of Algorithm 1 for some profile. The following result states that it is enough to analyze the set of histories to determine if Algorithm 1 always terminates with a core-stable committee.

Proposition 5.2. Suppose that for every history (𝑊1, 𝑇1), . . . , (𝑊𝑟 , 𝑇𝑟 ), we have |𝑇1| + · · · + |𝑇𝑟 | ⩽ 𝑘. Then a core-stable committee always exists for 𝑚 and 𝑘.

Proof. Let 𝑃 be a profile, and run Algorithm 1 on it. By the assumption, in each iteration, |𝐹| ⩽ |𝑇1| + · · · + |𝑇𝑟 | ⩽ 𝑘, so the algorithm does not fail. By the if-clause, if the algorithm terminates, it returns a committee that is core-stable. Thus, it suffices to show that the algorithm terminates.

Note that after each iteration of the algorithm, it either terminates or it has found a successful deviation. Suppose iteration 𝑟 has ended without the algorithm terminating. The sequence of committees and deviations (𝑊1, 𝑇1), . . . , (𝑊𝑟 , 𝑇𝑟 ) identified by the algorithm up to iteration 𝑟 forms a history. Since |𝑇𝑡 | ⩾ 1 for all 𝑡, it follows from |𝑇1|+· · ·+|𝑇𝑟 | ⩽ 𝑘 that 𝑟 ⩽ 𝑘. So it must terminate after at most 𝑘 + 1 iterations. □

Algorithm 2 Finding all histories

Input: Number 𝑚 of candidates and a committee size 𝑘 Output: A collection of all histories and Farkas certificates H0 ← {∅}, the empty history for 𝑡 = 1, 2, . . . do for all 𝐻 ∈ H𝑡-1 do for all potential continuations (𝑊𝑡 , 𝑇𝑡 ) do if (𝑊𝑡 , 𝑇𝑡 ) is not canonical w.r.t. 𝐻 then continue Set 𝐻 ′ ← 𝐻 + (𝑊𝑡 , 𝑇𝑡 ) Solve LP to check if 𝐻 ′ is a history If yes, add 𝐻 ′ to H𝑡 If no, generate a Farkas certificate if H𝑡 = ∅ then break

Thus, to prove the existence of core-stable committees, it suffices to enumerate all histories and check that they fulfil the condition of Theorem 5.2. Given a potential history, one can check using an LP solver whether it is a history by checking whether the system of linear inequalities in Theorem 5.1 has a solution. This way, we can compute the set of histories using a standard breadth-first search, as shown in Algorithm 2. A key insight to speed up the search is that we may break symmetries and only consider "canonical" histories in our enumeration. For example, we may assume without loss of generality that 𝑊1, the first committee of the history, is {𝑐1, . . . , 𝑐𝑘}. Similarly, we do not need to consider all potential deviations 𝑇1: given our choice of 𝑊1, the candidates in 𝑊1 are indistinguishable to each other, as are the candidates in 𝐶 \ 𝑊1. Thus, it suffices to take one deviation for each possible combination of the sizes of |𝑇1 ∩𝑊1| and of |𝑇1 ∩ (𝐶 \𝑊1)|. Similar symmetry-breaking conditions apply for later steps.

For example, for 𝑚 = 15 and 𝑘 = 13, Algorithm 2 produces the following set of (canonical) histories, where we write 𝑊1 = {𝑐1, . . . , 𝑐13} and𝑊2 = {𝑐1, . . . , 𝑐11, 𝑐14, 𝑐15}.

∅, the empty history (𝑊1, {𝑐1, 𝑐2, 𝑐3, 𝑐4, 𝑐5, 𝑐6, 𝑐7, 𝑐8, 𝑐14, 𝑐15}) (𝑊1, {𝑐1, 𝑐14, 𝑐15}) (𝑊1, {𝑐1, 𝑐2, 𝑐3, 𝑐14, 𝑐15}) (𝑊1, {𝑐1, 𝑐2, 𝑐14, 𝑐15}) (𝑊1, {𝑐1, 𝑐2, 𝑐3, 𝑐4, 𝑐5, 𝑐14, 𝑐15}) (𝑊1, {𝑐1, 𝑐2, 𝑐3, 𝑐4, 𝑐14, 𝑐15}) (𝑊1, {𝑐1, 𝑐2, 𝑐3, 𝑐4, 𝑐5, 𝑐6, 𝑐7, 𝑐14, 𝑐15}) (𝑊1, {𝑐1, 𝑐2, 𝑐3, 𝑐4, 𝑐5, 𝑐6, 𝑐14, 𝑐15}) (𝑊1, {𝑐1, 𝑐14, 𝑐15}), (𝑊2, {𝑐2, 𝑐12, 𝑐13}) (𝑊1, {𝑐1, 𝑐14, 𝑐15}), (𝑊2, {𝑐2, 𝑐3, 𝑐12, 𝑐13}) (𝑊1, {𝑐1, 𝑐2, 𝑐3, 𝑐14, 𝑐15}), (𝑊2, {𝑐4, 𝑐5, 𝑐12, 𝑐13}) (𝑊1, {𝑐1, 𝑐2, 𝑐14, 𝑐15}), (𝑊2, {𝑐3, 𝑐12, 𝑐13}) (𝑊1, {𝑐1, 𝑐2, 𝑐14, 𝑐15}), (𝑊2, {𝑐3, 𝑐4, 𝑐12, 𝑐13}) (𝑊1, {𝑐1, 𝑐2, 𝑐14, 𝑐15}), (𝑊2, {𝑐3, 𝑐4, 𝑐5, 𝑐12, 𝑐13})

By running Algorithm 2 for 𝑚 = 15 and 𝑘 = 9, . . . , 13, we obtain the following result. (Note that existence for 𝑚 = 15 implies existence for all 𝑚 ⩽ 15.)

Theorem 5.3. If 𝑚 ⩽ 15, a core-stable committee exists.

The computations establishing Theorem 5.3 can be verified based on Farkas certificates: the code repository includes, for each history and each possible extension of the history that induces an infeasible system of linear inequalities, a Farkas witness. Each witness is a list of about 𝑡 · 𝑘 · (𝑚 - 𝑘) integers, where 𝑡 is the length of the history, corresponding to the constraints in Theorem 5.1, and verifying the correctness of the witness requires checking about 2 𝑚 inequalities. In total, there are 114 373 witnesses (taking 125 MB). Verifying their validity using a simple script [available on GitHub] that performs exact fractional computations (without calling a solver) takes about 4 hours on 8 cores (see Table 1).

The recursive PAV rule fails for 𝑚 = 16, 𝑘 ∈ {10, 11}. For 𝑚 = 16, 𝑘 = 10, the smallest failure example I have found has 40 448 550 voters, though the ILP for minimizing this number did not converge within a reasonable amount of time. The example is available online. 5 The recursive PAV rule does work for 𝑚 = 16, 𝑘 ∈ {9, 12, 13, 14}, and it is plausible that it can be fixed ad hoc for 𝑘 ∈ {10, 11}, so it is likely that the core continues to exist for 𝑚 = 16.

6 Droop Quota

Our definition of core stability is based on the intuition that a 1/𝑘 fraction of the voters is "entitled" to decide on one of the committee members, and that an ℓ/𝑘 fraction is entitled to decide on ℓ committee members. The quantity 1/𝑘 is known as the Hare quota. But one can also define core stability based on the Droop quota, according to which each group of voters that makes up a strictly larger fraction than 1/(𝑘+1) is entitled to decide on one committee member. Thus, a committee 𝑊 is Droop core stable if for every potential deviation 𝑇, we have

This is a stricter condition than the normal core, so if 𝑊 is Droop core stable then it is also core stable.

For most proportionality notions considered in the literature on approval-based committee elections, passing to the more demanding Droop quota does not cause many issues. For example, PAV still satisfies EJR when defined with the Droop quota, and analogous statements are true for many pairs of voting rules and representation axioms [Janson, 2018]. 6

5 The example witnessing this failure induces the history

({𝑐0, 𝑐1, 𝑐2, 𝑐3, 𝑐4, 𝑐5, 𝑐6, 𝑐7, 𝑐8, 𝑐9}, {𝑐0, 𝑐10, 𝑐11}),

({𝑐0, 𝑐1, 𝑐2, 𝑐3, 𝑐4, 𝑐5, 𝑐6, 𝑐10, 𝑐11, 𝑐12}, {𝑐13, 𝑐14, 𝑐15}),

({𝑐0, 𝑐1, 𝑐2, 𝑐3, 𝑐10, 𝑐11, 𝑐12, 𝑐13, 𝑐14, 𝑐15}, {𝑐4, 𝑐5, 𝑐6, 𝑐7, 𝑐8}).

6 However, regarding strategic aspects, impossibility theorems become somewhat more expansive when passing to the Droop quota [Peters, 2018, Section 5.3].

Unfortunately, our positive results do not extend to the Droop core. While PAV satisfies the core for up to 𝑘 = 8 (Section 4), it violates the Droop core already for 𝑘 = 6.

On this profile, 𝑊 = {𝑐1, 𝑐2, 𝑐5, 𝑐6, 𝑐7, 𝑐8} is the unique global (and unique local) PAV committee for 𝑘 = 6. However 𝑊 is not in the Droop core: consider 𝑇 = {𝑐1, 𝑐2, 𝑐3, 𝑐4}, which has support from 14 24 ≈ 0.583 of the voters, while |𝑇 |/(𝑘 +1) = 4 7 ≈ 0.571 is strictly smaller. □

This example is minimal, so the Droop core is non-empty when 𝑘 ⩽ 5. Running the recursive PAV rule (Algorithm 1) with the Droop quota stops working even for 𝑚 = 10, 𝑘 = 6.

7 Conclusions

Based on the computations of this paper, we know that the core is non-empty for all small instances. This should probably strengthen our belief that the core is always non-empty. However, the recursive PAV method we defined to establish the result stops working for 16 or more candidates, so it seems doubtful that analyzing this method would allow proving a general existence result. Conversely, finding a counterexample to core existence will also be challenging since it will need to be large. For the Droop quota, however, it even remains unknown whether core always exists for 𝑘 = 6 and 𝑚 = 10.

Our approach was based on linear programming and allowed us to reason independently of the number of voters. The PAV rule and its variants are well-suited for these LP formulations. Finding core counterexamples for many other rules is not possible using similar linear programs. For example, the Method of Equal Shares (MES) [Peters and Skowron, 2020] or the sequential Phragm´en method [Phragm´en, 1894; Janson, 2016] do not admit the same kind of linear formulations (one would need to multiply variables corresponding to ballot frequencies with variables corresponding to 𝜌-values or to loads). The lack of such a linear formulation can be formally established using the techniques of Xia [2025]. In part because computer search is difficult for these rules, to the best of my knowledge, there is no known profile where both PAV and MES fail core-stability simultaneously, or a profile where the rule that maximizes the PAV score among all priceable committees [Peters and Skowron, 2020] fails core-stability.

Maly [2023] presents an example in the participatory budgeting setting with cost utilities where the core is empty. That example uses only 3 voters. It would be interesting to see if computer-aided methods could establish that for committee elections, the core is always non-empty for 𝑛 = 3 voters. Note that in this case, candidates can be specified via the set of voters that approve the candidate, so there are only 2 3 different types of candidates, and thus a profile can be specified via variables that indicate how many candidates of each type exist.

Acknowledgements

I thank Paul G¨olz for useful discussions, and Jannik Peters and the anonymous reviewers at IJCAI 2025 for feedback that improved the presentation of the paper. I have used Gurobi and the cvc5 solver [Barbosa et al., 2022] in this work. This work was funded in part by the Agence Nationale de la Recherche under grant ANR22-CE26-0019 (CITIZENS) and as part of the France 2030 program under grant ANR-23-IACL-0008 (PR[AI]RIE-PSAI).