# The Core of Approval-Based Committee Elections with Few Seats

Dominik Peters

► To cite this version:

Dominik Peters. The Core of Approval-Based Committee Elections with Few Seats. Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25), Aug 2025, Montreal, Canada. pp.4014-4022, 10.24963/ijcai.2025/447. [https://hal.science/hal-05367820v1](https://hal.science/hal-05367820v1)

HAL Id: hal-05367820

Submitted on 17 Nov 2025

**HAL** is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire **HAL**, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_1.png" /></figure>
# The Core of Approval-Based Committee Elections with Few Seats

Dominik Peters¹

¹CNRS, LAMSADE, Université Paris Dauphine - PSL

Full version of the paper appearing in the proceedings of IJCAI 2025 · May 2025

## Abstract

In an approval-based committee election, the goal is to select a committee consisting of $k$ out of $m$ candidates, based on $n$ voters who each approve an arbitrary number of the candidates. The core of such an election consists of all committees that satisfy a certain stability property which implies proportional representation. In particular, committees in the core cannot be “objected to” by a coalition of voters who is underrepresented. The notion of the core was proposed in 2016, but it has remained an open problem whether it is always non-empty. We prove that core committees always exist when $k \le 8$, for any number of candidates $m$ and any number of voters $n$, by showing that the Proportional Approval Voting (PAV) rule due to Thiele (1895) always satisfies the core when $k \le 7$ and always selects at least one committee in the core when $k = 8$. We also develop an artificial rule based on recursive application of PAV, and use it to show that the core is non-empty whenever there are $m \le 15$ candidates, for any committee size $k \le m$ and any number of voters $n$. These results are obtained with the help of computer search using linear programs.

<table><tr><td>1</td><td>Introduction</td><td>2</td></tr><tr><td>2</td><td>Related Work</td><td>3</td></tr><tr><td>3</td><td>Preliminaries</td><td>4</td></tr><tr><td>4</td><td>Small Committee Size</td><td>6</td></tr><tr><td>4.1</td><td>Committee size k &le; 7</td><td>6</td></tr><tr><td>4.2</td><td>Committee size k = 8</td><td>8</td></tr><tr><td>4.3</td><td>Committee size k &ge; 9</td><td>10</td></tr><tr><td>5</td><td>Few Candidates</td><td>10</td></tr><tr><td>5.1</td><td>Analysis of the Method</td><td>11</td></tr><tr><td>6</td><td>Droop Quota</td><td>14</td></tr><tr><td>7</td><td>Conclusions</td><td>14</td></tr><tr><td>8</td><td>References</td><td>15</td></tr></table>
# 1 Introduction

The seminal work of Aziz et al. (2016, 2017) introduced a rigorous way of reasoning about voter representation in multi-winner elections. Their model considers approval-based committee elections, where the task is to identify a committee $W \subseteq C$ of $k$ out of $m$ candidates, based on a set of voters $N$, with each $i \in N$ indicating a subset $A_i \subseteq C$ of candidates that $i$ approves. Aziz et al. (2016, 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én (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 $W$ is core stable if for every set $T \subseteq C$, there are not too many voters who prefer the set $T$ to $W$, namely we have

$$|\{i \in N : |A_i \cap T| > |A_i \cap W|\}| < |T| \cdot \frac{n}{k}.$$

If this inequality were violated for some $T$, 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 $T$ in the committee.

The EJR property is weaker than core stability (because under EJR voters are only allowed to join the blocking coalition if they approve all the candidates in $T$, i.e., $|A_i \cap T| = |T|$), 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ński and Skowron, 2022) and on profiles where each candidate has at least $k$ 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 $k = 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 $k = 3$ to general $k$. 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 ($m + n \le 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 $m$ and $k$, and introduce a fractional variable for each possible ballot, indicating what fraction of the voters submit this ballot. Then, for every possible committee, enforce using binary variables that there exists 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 $m$ and $k$, for any number $n$ of voters. Unfortunately, the size of this program grows rapidly, and they are not easy to solve even for very small sizes (Gurobi solves $m = 7, k = 5$, in 450s, but did not solve $m = 7, k = 4$ after 134 000s (37h) on 8 cores).<fnref n="1" />

<footnote n="1">¹The same problem can also be encoded as an SMT problem on linear arithmetic. This can sometimes lead to</footnote>
In this paper, by deriving a new way of using solvers, we show that the core always exists for committee sizes up to $k = 8$, regardless of the number of candidates (improving upon the previous result for $k = 3$). We also show that the core always exists when the number $m$ of candidates is at most 15, for any $k \le m$. Both results hold for any number $n$ 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 $k$. We show via linear programs that PAV always selects a core-stable committee when $k \le 7$, and that it always selects at least one core-stable committee when $k = 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én rule and the Method of Equal Shares which fail the core for $k = 6$ and $k = 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.<fnref n="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 $T$ has too much support, we then re-compute PAV subject to the constraint that $T \subseteq W$ 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 $m \le 15$, this process always terminates with a core-stable committee. However, there are examples where the rule fails to guarantee the core for $m = 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ánchez-Fernández 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/.

## 2 Related Work

**Barriers to core existence.** Proving that the core is non-empty 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 fixed-parameter 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

<footnote>faster solve times, but it is also only feasible for very small sizes.</footnote>

<footnote n="2">²Note, however, that even for $k = 6$, PAV may select committees that fail laminar proportionality (Peters and Skowron, 2020) and are intuitively unfair. A three-voter example for $k = 6$ is $A_1 = \{c_1, c_2, c_3\}$, $A_2 = \{c_1, c_2, c_4\}$, and $A_3 = \{c_5, c_6, c_7\}$ where $W = \{c_1, c_2, c_3, c_5, c_6, c_7\}$ is a global PAV committee (tied with others) while laminar proportionality demands that $\{c_1, c_2, c_3, c_4\} \subseteq W$.</footnote>
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/e$ (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 approval-based 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 $W$ is in the $(\alpha, \beta)$-core, $\alpha, \beta \ge 1$, if for every potential deviation $T$, we have $|\{i \in N : |A_i \cap T| > \alpha \cdot |A_i \cap W|\}| < \beta \cdot |T| \cdot \frac{n}{k}$. For $\alpha = \beta = 1$, this is the core; for $\alpha > 1$, every member of the blocking coalition must increase their utility by a factor of $\alpha$; for $\beta > 1$, we require that blocking coalitions must be larger than usual by a factor of $\beta$.

Peters and Skowron (2020) show that PAV is in the (2,1)-core, and that the Method of Equal Shares is in the (log k, 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 + $\epsilon$, 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.** Analog 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/k$) via Lindahl equilibrium which is known to exist from fixed-point 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 approval-based fair mixing and related models (see, e.g., Brandl et al., 2021; Suzuki and Vollen, 2024; Bei et al., 2025).

# 3 Preliminaries

Let $C = \{c_1, \dots, c_m\}$ be a set of $m$ candidates. Let $k \in \{1, \dots, m\}$ be the committee size. A *committee* is a subset $W \subseteq C$ of winning candidates with $|W| = k$.

Let $\mathcal{A}$ denote the set of non-empty subsets of $C$, which we will refer to as *approval sets* or *ballots*. A *profile* is a map $P: \mathcal{A} \to \mathbb{Q}_{\ge 0}$ with $\sum_{A \in \mathcal{A}} P(A) = 1$, where $P(A)$ indicates the fraction of the voters that approve exactly the candidates in $A$. Given an approval set $A \in \mathcal{A}$ and a
committee W, the utility of the committee for A is the number of approved committee members: $u_A(W) = |A \cap W|$.

A nonempty set $T \subseteq C$ with $|T| \le k$ is called a potential deviation. Given a profile $P$, a committee $W$ is core stable if for every potential deviation $T$, we have

$$ \sum_{A \in \mathcal{A}: u_A(T) > u_A(W)} P(A) < \frac{|T|}{k}. $$

Otherwise, $T$ is called a deviation (or a successful deviation) from $W$. The core is the set of committees that are core stable.

The nth harmonic number is $H(n) = 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}$. The PAV score assigned to a committee $W$ by ballot $A \in \mathcal{A}$ is

$$ \text{PAV-score}_A(W) = H(u_A(W)). $$

Given a profile $P$, the PAV score of $W$ under profile $P$ is

$$ \text{PAV-score}_P(W) = \sum_{A \in \mathcal{A}} P(A) \cdot \text{PAV-score}_A(W). $$

A committee is called 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 $W$, $x \in W$ and $y \in C \setminus W$, we write $W_{xy} = W \setminus \{x\} \cup \{y\}$ for the committee obtained by replacing $x$ with $y$. Given a profile $P$ and a fixed committee $W$, we write

$$ \Delta_{P,x,y} = \text{PAV-score}_P(W_{xy}) - \text{PAV-score}_P(W) $$

for the increase in PAV score resulting from this swap. For a ballot $A$, we define $\Delta_{A,x,y}$ analogously. Then we say that $W$ is a local PAV committee if $\Delta_{P,x,y} \le 0$ for all $x$ and $y$. 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: neither disjoint deviations, nor deviations that contain only a single unelected candidate.

**Lemma 3.1** Let $W$ be a local PAV committee, and let $T$ be a potential deviation. Suppose we have

$$ (i) \ T \cap W = \emptyset, \quad \text{or} \quad (ii) \ |T \setminus W| \le 1. $$

Then $T$ is not a deviation from $W$.

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

(ii) If $T \setminus W = \emptyset$, then $T \subseteq W$, and there are no approval ballots that strictly prefer $T$ to $W$. If $T \setminus W = \{c\}$, then for every $A \in \mathcal{A}$ with $u_A(T) > u_A(W)$, we have $c \in A$. Writing $\ell = |T|$, if $T$ were a deviation, we would thus have a set $S$ of ballots forming $\ell/k$ of the profile, who all approve $c \notin W$, and who all have utility $u_A(W) < u_A(T) \le \ell$. Thus, we have a violation of the EJR+ axiom of Brill and Peters (2023) which local PAV committees are known to satisfy. $\square$

Note that Lemma 3.1(ii) implies that PAV satisfies the core when $k = m - 1$ or $k = m$.

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

**Lemma 3.2** (Farkas' Lemma) Let $A \in \mathbb{Q}^{mn}$ be an $m \times n$ matrix, and let $b \in \mathbb{Q}^m$. Then the following are equivalent.
(i) There does not exist $x \in \mathbb{Q}^n$ with $Ax \le b$.

(ii) There exists an integer vector $y \in \mathbb{Z}_{\ge 0}^m$ such that $y^T b < 0$ and $A^T y \ge 0$.

Thus, by exhibiting the integer vector $y$, one can prove the infeasibility of the system $Ax \le b$.

# 4 Small Committee Size

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

## 4.1 Committee size $k \le 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.<fnref n="3" /> Like other proofs that PAV is proportional, our proof reasons about the change in PAV score caused by certain swaps. 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 Python code available on GitHub.

**Theorem 4.1** *When $k \le 7$, every local PAV committee is in the core.*

*Proof.* Let $W$ be a PAV committee with $|W| = k \le 7$, and consider a potential deviation $T$. We need to show that $T$ is not successful. Writing

$$s = \sum_{\substack{A \in A \\ u_A(T) > u_A(W)}} P(A),$$

we need to show that $s < |T|/k$. We may assume that $s > 0$, since otherwise $T$ is definitely not successful.

We now consider the following process: we remove some candidate $x \in W \setminus T$ from the committee $W$, and replace it by some candidate $y \in T \setminus W$, and will estimate the total effect of these swaps. Because $W$ is a local PAV committee, we have

$$\sum_{x \in W \setminus T} \sum_{y \in T \setminus W} \Delta_{P,x,y} \le 0 \qquad (1)$$

We can rewrite (1) by computing the contributions of each ballot to the differences in PAV score. Let $A \in A$. Note that swapping in $y$ for $x$ either increases the utility $u_A(W)$ by 1 point (if $x \notin A$ but $y \in A$), decreases it by 1 point (if $x \in A$ but $y \notin A$), or otherwise it stays the same. The number of $(x, y)$ pairs leading to an increase is $|(W \setminus T) \setminus A| \cdot |(T \setminus W) \cap A|$; the number of pairs leading to a decrease is $|(W \setminus T) \cap A| \cdot |(T \setminus W) \setminus A|$. Thus, from the point of view of the ballot $A$, the total difference in PAV score summed across all $x$ and $y$ becomes

$$\delta_A := \sum_{x \in W \setminus T} \sum_{y \in T \setminus W} \Delta_{A,x,y} \\ = \frac{|(W \setminus T) \setminus A| \cdot |(T \setminus W) \cap A|}{u_A(W) + 1} - \frac{|(W \setminus T) \cap A| \cdot |(T \setminus W) \setminus A|}{u_A(W)}.$$

<footnote n="3">³There are examples where the sequential Phragmén rule fails core (and even EJR) for $k = 6$, and where MES fails core for $k = 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én, take the 3-voter profile $(ab, bc, ac)$, where Phragmén can elect *ababab*, with $T = \{c, c, c, c\}$ forming a deviation. For MES, take the 7-voter profile $(ab, ac, ad, bcd, bcd, bcd, bcd)$, where $bbbbbbb$ is an outcome of MES, with $T = \{c, c, c, d, d, d\}$ forming a deviation. (In these examples, there are other tied outcomes in the core, and I don't know if unique examples exist.)</footnote>
Thus we can rewrite (1) as follows:

$$ \sum_{A \in \mathcal{A}} P(A) \cdot \delta_A \le 0 \qquad (2) $$

We will now give lower bounds on the value of $\delta_A$.

First we give a trivial lower bound, valid for all $A \in \mathcal{A}$:

$$ \delta_A \ge - \frac{|(W \setminus T) \cap A| \cdot |(T \setminus W) \setminus A|}{u_A(W)} \quad \text{(dropping positive terms)} $$

$$ \begin{aligned} & \ge - \frac{|W \cap A| \cdot |T \setminus W|}{u_A(W)} \\ & = -|T \setminus W|. \end{aligned} \quad \text{(since } u_A(W) = |W \cap A|) $$

Next, suppose $A \in \mathcal{A}$ is a ballot with $u_A(T) > u_A(W)$, i.e., $|A \cap T| \ge |A \cap W| + 1$. For such ballots, there exists a better lower bound for $\delta_A$. In particular, it is the case that

$$ \delta_A > \left( \frac{k}{|T|} - 1 \right) \cdot |T \setminus W|. \quad (3) $$

This can be shown by a small exhaustive search over all possible combinations of the quantities appearing in the definition of $\delta_A$. In particular, write

$$ a = |(W \setminus T) \cap A|, \quad b = |(W \cap T) \cap A|, \quad c = |(T \setminus W) \cap A|. $$

Then we have $\delta_A = \frac{|W \setminus T| - a)c}{a+b+1} - \frac{a|(|T \setminus W| - c)}{a+b}$, and one can check that this is always strictly larger than $(\frac{k}{|T|} - 1) \cdot |T \setminus W|$ by trying all triples $(a, b, c)$ with $0 \le a \le |W \setminus T|$, $0 \le b \le |W \cap T|$, and $0 \le c \le |T \setminus W|$ which satisfy $b + c > a + b$ (which encodes that $u_A(T) > u_A(W)$).<fnref n="4" />

Based on these bounds, we have

$$ 0 \ge \sum_{A \in \mathcal{A}} P(A) \cdot \delta_A \quad \text{(by (2))} $$

$$ > s\left(\left(\frac{k}{|T|}-1\right)\cdot|T\setminus W|\right) + (1-s)\left(-|T\setminus W|\right) \quad (s>0) $$

$$ = |T \setminus W| \cdot \left(s\left(\frac{k}{|T|}-1\right) - (1-s)\right) $$

$$ = |T \setminus W| \cdot \left(s\left(\frac{k}{|T|}-1\right)\right). $$

Thus, because $|T \setminus W| > 0$, we have $0 > s\frac{k}{|T|} - 1$ and hence $s < \frac{|T|}{k}$, as desired. $\square$

While it may not look like it, the result of Theorem 4.1 was obtained by linear programming. Suppose that the result is false, so that there exists a profile $P$ and a local PAV committee $W$ such that some $T$ is a successful deviation. Without loss of generality, there exists such an example with $W = \{c_1, \dots, c_k\}$. Note that $P$ then forms a solution to the following system of linear inequalities, where we may assume that $C = W \cup T$:<fnref n="5" />

$$ \begin{aligned} & \sum_{A \in \mathcal{A}} P(A) = 1 \\ & \Delta_{P,x,y} \le 0 \quad \text{for all } x \in W \text{ and } y \in C \setminus W \\ & \sum_{A \in \mathcal{A}: u_A(T) > u_A(W)} P(A) \ge \frac{|T|}{k} \\ & P(A) \ge 0 \quad \text{for all } A \in \mathcal{A} \end{aligned} \qquad (4) $$

<footnote n="4">⁴Note that none of $a, b, c$ depend on $m$, so the search is finite and the proof works independently of the number of candidates.</footnote>

<footnote n="5">⁵We may make this assumption because a counterexample on a larger $C$ remains a counterexample when restricted to $W \cup T$, because a local PAV committee remains a local PAV committee after deleting candidates outside the committee.</footnote>
Thus, Theorem 4.1 is proven if the system (4) does not have a feasible solution, for all potential deviations $T$. By Farkas' lemma, that means that for every $T$, there exist $\alpha \in \mathbb{R}$, $(\beta_{xy})_{xy} \ge 0$, $\gamma \ge 0$ satisfying

$$ 
\begin{array}{ll}
\alpha - \frac{|T|}{k}\gamma < 0 & \\
\alpha + \sum_{x \in W} \sum_{y \notin W} \Delta_{A,x,y} \cdot \beta_{xy} - \gamma \ge 0 & \text{for all } A \in \mathcal{A} \text{ with } u_A(T) > u_A(W) \\
\alpha + \sum_{x \in W} \sum_{y \notin W} \Delta_{A,x,y} \cdot \beta_{xy} \ge 0 & \text{for all } A \in \mathcal{A} \text{ with } u_A(T) \le u_A(W)
\end{array}
$$

In fact, the proof of Theorem 4.1 simply constructs such a certificate solution for every $T$, where $\alpha = |T \setminus W|$ and $\beta_{xy} = 1$ whenever $x \in W \setminus T$ and $y \in T \setminus W$, and $\beta_{xy} = 0$ otherwise.

Due to the following remark, it is possible to compute a core-stable outcome in $O(m^2n)$ time whenever $k \le 7$.

**Remark 4.2** Let $k \le 7$ and $\varepsilon = 0.1/k^2$. By solving linear programs [GitHub], one can check that every committee that is $\varepsilon$-local-swap-stable (i.e., $\Delta_{P,x,y} \le \varepsilon$ for all $x$ and $y$) is in the core. An $\varepsilon$-local-swap-stable and thus a core-stable committee can be found by performing $O(k^2 \ln k) = O(1)$ many $\varepsilon$-improving swaps (see Aziz et al., 2018, Proposition 1), each of which takes $O(m^2n)$ time to find. It turns out that for $\varepsilon = 1/k^2$, it is not the case that every $\varepsilon$-local-swap-stable committee is in the core, even though this value of $\varepsilon$ is enough to ensure that the committee satisfies EJR (Aziz et al., 2018, Theorem 1). For example, in the profile with $P(\{a, b\}) = P(\{a, c\}) = 0.25$ and $P(\{d, e, f, g, h\}) = 0.5$, for $k = 6$, the committee $\{a, d, e, f, g, h\}$ fails the core due to $T = \{a, b, c\}$, but it is $1/40$-local-swap-stable, and $1/40 < 1/36 = 1/k^2$.

## 4.2 Committee size $k = 8$

Theorem 4.1 does not hold for $k = 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 $k = 8$) Consider an instance with 4 voters, $v_1$ approving $\{c_1, c_2, c_3\}$, and $v_2$ approving $\{c_1, c_2, c_4\}$, and the other 2 voters approving $\{c_5, c_6, c_7, c_8, c_9, c_{10}\}$. This profile is depicted below, where each voter approves the candidates above the voter's label.

<table><thead><tr><th></th><th></th><th>c<sub>10</sub></th><th>c<sub>9</sub></th><th>c<sub>8</sub></th></tr></thead><tbody><tr><td>c<sub>3</sub></td><td>c<sub>4</sub></td><td>c<sub>7</sub></td><td></td><td></td></tr><tr><td>c<sub>2</sub></td><td></td><td>c<sub>6</sub></td><td></td><td></td></tr><tr><td>c<sub>1</sub></td><td></td><td>c<sub>5</sub></td><td></td><td></td></tr></tbody><tfoot><tr><td colspan="2">v<sub>1</sub> v<sub>2</sub> v<sub>3</sub> v<sub>4</sub></td><td></td><td></td><td></td></tr></tfoot></table>

On this profile, $W = \{c_1, c_2, c_5, c_6, c_7, c_8, c_9, c_{10}\}$ is a global PAV committee (indicated in blue in the picture). However, $W$ is not in the core: consider $T = \{c_1, c_2, c_3, c_4\}$, which has support from $1/2$ of the voters, and $|T|/k = 1/2$. $\square$

Note, however, that in Example 4.3, there is more than one global PAV committee. In particular, $W' = \{c_1, c_2, c_3, c_5, c_6, c_7, c_8, c_9\}$ (obtained by removing $c_{10}$ and adding $c_3$) is also a global PAV committee and it is in the core.

It turns out that Example 4.3 is essentially the only example where a PAV committee fails to be core-stable for $k = 8$, as all such examples share the same structure.
**Lemma 4.4** Let P be a profile and suppose that W with $|W| = 8$ is a local PAV committee that is not in the core due to objection T. Then there exist distinct $a, b \in W$ and distinct $x, y \in C \setminus W$ such that $T = \{a, b, x, y\}$. In addition,

(i) one quarter of the voters submit ballots A such that $A \cap (W \cup T) = \{a, b, x\}$ and another quarter submit ballots with $A \cap (W \cup T) = \{a, b, y\}$,

(ii) the remaining half of the voters submit ballots that are disjoint from T, and

(iii) the PAV score of W is reduced by exactly 1/12 if any one member of $W \setminus \{a, b\}$ is removed.

*Proof.* We first check that if W is not in the core, then any core objection must use a T with $|T| = 4$ and $|W \cap T| = 2$. This can be deduced using the linear programming approach behind Theorem 4.1; by iterating through all possible T, we find that the system (4) has a solution only for T satisfying the condition in the theorem statement. Alternatively, one can check [GitHub] that the inequality (3) is only violated for such T; thus for other T the proof of Theorem 4.1 goes through.

Now fix such a $T = \{a, b, x, y\}$. Assume that there exists a profile P where W is a local PAV committee with successful deviation T but that violates any of the conditions (i)–(iii). Then if we delete all candidates outside $W \cup T$ from the profile, it would still fail (i)–(iii). Thus, for purposes of making the following linear programs finite, we may assume that $C = W \cup T$ (so $|C| = 10$).

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

maximize $P(\{a, b, x\})$ subject to P satisfying (4)

minimize $P(\{a, b, x\})$ subject to P satisfying (4)

maximize $P(\{a, b, y\})$ subject to P satisfying (4)

minimize $P(\{a, b, y\})$ subject to P satisfying (4)

The optimal solutions to all these programs is $\frac{1}{4}$.

To prove (ii), iterate through all ballots $A \in \mathcal{A}$ with $A \cap T \neq \emptyset$, except for $\{a, b, x\}$ and $\{a, b, y\}$. For each of these ballots, solve the following linear program:

maximize $P(A)$ subject to P satisfying (4)

For each such A, the optimal solution of the program is 0.

To prove (iii), iterate through all $c \in W \setminus \{a, b\}$ and solve the following linear programs:

maximize $\text{PAV-score}_P(W \setminus \{c\}) - \text{PAV-score}_P(W)$ subject to P satisfying (4)

minimize $\text{PAV-score}_P(W \setminus \{c\}) - \text{PAV-score}_P(W)$ subject to P satisfying (4)

The optimal solutions to these two programs are $-1/12$. $\square$

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 using a solver.

As we discussed, Example 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 core-stable. Thanks to Lemma 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 $k = 8$.
**Theorem 4.5** *When $k = 8$, some global PAV committee is in the core.*

*Proof.* Let $k = 8$ and let $P$ be a profile. If on $P$, all global PAV committees are in the core, we are done. So suppose that $W$ is a global PAV committee that is not core stable due to objection $T$. From Lemma 4.4, there exist distinct $a, b \in W$ and distinct $x, y \in C \setminus W$ such that $T = \{a, b, x, y\}$. Take any $c \in W \setminus \{a, b\}$. Then the committee $W' = W \setminus \{c\} \cup \{x\}$ has the same PAV score as $W$, because the removal of $c$ causes a decrease in PAV score of $1/12$ and the addition of $x$ causes an increase of at least $\frac{1}{4} \cdot \frac{1}{3} = 1/12$ due to the quarter of voters from (i) with ballots $A$ such that $A \cap (W \cup T) = \{a, b, x\}$. Thus, $W'$ is also a global PAV committee. We now show that $W'$ is in the core.

If not, we can apply Lemma 4.4 to $W'$ which gives us an objection $T' = \{a', b', x', y'\}$ to $W'$. Clearly, voters with ballots such that $A \cap (W \cup T) = \{a, b, x\}$ are not part of a blocking coalition because $\{a, b, x\} \subseteq W'$. Thus, we deduce that $a, b \notin T$ from (ii). Thus, the voters with ballots such that $A \cap (W \cup T) = \{a, b, y\}$ are also not supporters of $T'$. Then from part (i) we deduce that the only members of $W$ that are approved by any voters in $P$ are $a, b, a'$, and $b'$. Thus, there exists a member of $W \setminus \{a, b\}$ 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 $k \ge 9$

The PAV-based technique that worked for up to $k = 8$ does not continue to work for $k = 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 it is the smallest such example with respect to the number of voters ($n = 27$). The indicated committee is also the unique local PAV committee.

<figure><img src="image_2.png" /></figure>

Aziz et al. (2017, Example 6) gave an example where PAV uniquely selects a non-core-stable committee for $k = 10$ and $n = 20$.

## 5 Few Candidates

The goal of this section is to show that there always exists a core-stable committee on instances with $m \le 15$ candidates. From the results in Section 4, this is clearly true when $k \le 8$. By Lemma 3.1(ii), this is also true when $k = m - 1$ or $k = m$. But it is not clear when $k \in \{9, \dots, m-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 $m = 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 $T$ is a deviation from $W$, it then deletes all voters who prefer $T$ to $W$, and computes a local
**Algorithm 1 Recursive PAV rule**

**Input:** A profile $P$ and a committee size $k$

**Output:** A committee $W$

$\mathcal{A}' \leftarrow \mathcal{A}$, set of active ballots

$F \leftarrow \emptyset$, set of fixed candidates

while true do

If $|F| > k$, the algorithm fails

$W \leftarrow$ any committee locally maximizing the PAV score

w.r.t. the ballots in $\mathcal{A}'$ and subject to $F \subseteq W$

if there exists a successful deviation $T$ from $W$ then

$$F \leftarrow F \cup T$$

$$\mathcal{A}' \leftarrow \mathcal{A}' \setminus \{A \in \mathcal{A} : u_A(T) > u_A(W)\}$$

else

return $W$

PAV committee with respect to the remaining voters, but subject to the constraint that $T \subseteq W$. 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 Example 4.3, PAV selects the committee $W$ indicated there in blue (among other tied committees). This committee is blocked by $T = \{c_1, c_2, c_3, c_4\}$. Thus, the recursive PAV rule would now fix all members of $T$ as winners, and maximize the PAV-score with respect to voters $v_3$ and $v_4$, obtaining the committee $W^* = \{c_1, c_2, c_3, c_4, c_5, c_6, c_7, c_8\}$ (among other tied committees). This committee is in the core, so the rule terminates. Note that $W^*$ is not itself selected by PAV, though as we saw previously, there do exist other (global) PAV committees in the core in Example 4.3.

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 $m$ and a committee size $k$.

A list $(W_1, T_1), (W_2, T_2), \dots, (W_r, T_r)$ is called a potential history if for each $t \in [r]$, we have that $W_t$ is a committee, $T_t$ is a potential deviation, and $T_1 \cup \dots \cup T_{t-1} \subseteq W_t$.

**Definition 5.1** A potential history $(W_1, T_1), \dots, (W_r, T_r)$ is a history if there exists a profile $P$ such that for each $t \in [r]$ we have that $T_t$ is a successful deviation from $W_t$, and that for all $x \in W \setminus (T_1 \cup \dots \cup T_{t-1})$ and $y \in C \setminus W$, we have

$$\sum_{A \in \mathcal{A}_t} P(A) \cdot \text{PAV-score}_A(W_t) \geq \sum_{A \in \mathcal{A}_t} P(A) \cdot \text{PAV-score}_A(W_{xy})$$

where $\mathcal{A}_t = \{A \in \mathcal{A} : u_A(T_s) \leq u_A(W_s) \text{ for } s \in \{1, \dots, t-1\}\}$ is the set of “active” ballots. That is, $W_t$ 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 $(W_1, T_1), \dots, (W_r, T_r)$, we have $|T_1| + \dots + |T_r| \leq k$. Then a core-stable committee always exists for $m$ and $k$.
<table><caption>**Table 1** Statistics about the histories for $m = 15$.</caption><thead><tr><th>k =</th><th>9</th><th>10</th><th>11</th><th>12</th><th>13</th></tr></thead><tbody><tr><td>number of canonical histories</td><td>7</td><td>11</td><td>15</td><td>20</td><td>15</td></tr><tr><td>number of Farkas witnesses</td><td>20 476</td><td>25 313</td><td>18 567</td><td>43 140</td><td>6 877</td></tr><tr><td>time for checking Farkas (s)</td><td>2 648</td><td>3 301</td><td>2 087</td><td>5 857</td><td>725</td></tr></tbody></table>

histories, where we write $W_1 = \{c_1, \dots, c_{13}\}$ and $W_2 = \{c_1, \dots, c_{11}, c_{14}, c_{15}\}$.

∅, the empty history
(W_1, \{c_1, c_2, c_3, c_4, c_5, c_6, c_7, c_8, c_{14}, c_{15}\})
(W_1, \{c_1, c_{14}, c_{15}\})
(W_1, \{c_1, c_2, c_3, c_{14}, c_{15}\})
(W_1, \{c_1, c_2, c_{14}, c_{15}\})
(W_1, \{c_1, c_2, c_3, c_4, c_5, c_{14}, c_{15}\})
(W_1, \{c_1, c_2, c_3, c_4, c_{14}, c_{15}\})
(W_1, \{c_1, c_2, c_3, c_4, c_5, c_6, c_{14}, c_{15}\})
(W_1, \{c_1, c_{14}, c_{15}\}), \quad (W_2, \{c_2, c_{12}, c_{13}\})
(W_1, \{c_1, c_{14}, c_{15}\}), \quad (W_2, \{c_2, c_3, c_{12}, c_{13}\})
(W_1, \{c_1, c_2, c_3, c_{14}, c_{15}\}), \quad (W_2, \{c_4, c_5, c_{12}, c_{13}\})
(W_1, \{c_1, c_2, c_{14}, c_{15}\}), \quad (W_2, \{c_3, c_{12}, c_{13}\})
(W_1, \{c_1, c_2, c_{14}, c_{15}\}), \quad (W_2, \{c_3, c_4, c_{12}, c_{13}\})
(W_1, \{c_1, c_2, c_{14}, c_{15}\}), \quad (W_2, \{c_3, c_4, c_5, c_{12}, c_{13}\})

By running Algorithm 2 for $m = 15$ and $k = 9, \dots, 13$, we obtain the following result. (Note that existence for $m = 15$ implies existence for all $m \le 15$.)

**Theorem 5.3** If $m \le 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 $t \cdot k \cdot (m-k)$ integers, where $t$ is the length of the history, corresponding to the constraints in Definition 5.1, and verifying the correctness of the witness requires checking about $2^m$ inequalities. In total, there are 114 373 witnesses (taking 125 MB) and verifying their validity using a simple script [GitHub] performing exact fractional computations (without calling a solver) takes about 4 hours on 8 cores (see Table 1).

The recursive PAV rule fails for $m = 16$, $k \in \{10, 11\}$. For $m = 16$, $k = 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.<fnref n="7" /> The recursive PAV rule does work for $m = 16$, $k \in \{9, 12, 13, 14\}$, and it is plausible that it can be fixed ad hoc for $k \in \{10, 11\}$, so it is likely that the core continues to exist for $m = 16$.

<footnote n="7">⁷The history that witnesses this failure is the following: $(\{c_0, c_1, c_2, c_3, c_4, c_5, c_6, c_7, c_8, c_9\}, \{c_0, c_{10}, c_{11}\}), (\{c_0, c_1, c_2, c_3, c_4, c_5, c_6, c_{10}, c_{11}, c_{12}\}, \{c_{13}, c_{14}, c_{15}\}), (\{c_0, c_1, c_2, c_3, c_{10}, c_{11}, c_{12}, c_{13}, c_{14}, c_{15}\}, \{c_4, c_5, c_6, c_7, c_8\})$.</footnote>
# 6 Droop Quota

Our definition of core stability is based on the intuition that a $1/k$ fraction of the voters is “entitled” to decide on one of the committee members, and that an $\ell/k$ fraction is entitled to decide on $\ell$ committee members. The quantity $1/k$ 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/(k+1)$ is entitled to decide on one committee member. Thus, a committee $W$ is *Droop core stable* if for every potential deviation $T$, we have

$$ \sum_{A \in \mathcal{A}: u_A(T) > u_A(W)} P(A) \le \frac{|T|}{k+1}. $$

This is a stricter condition than the normal core, so if $W$ 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).<fnref n="8" />

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

**Example 6.1** (PAV may fail the Droop core for $k = 6$) Consider the instance depicted below:

<table><thead><tr><th></th><th></th><th>c<sub>8</sub></th><th>c<sub>7</sub></th><th>c<sub>6</sub></th><th>c<sub>5</sub></th></tr></thead><tbody><tr><td>c<sub>3</sub></td><td>c<sub>4</sub></td><td></td><td></td><td></td><td></td></tr><tr><td>c<sub>2</sub></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>c<sub>1</sub></td><td></td><td></td><td></td><td></td><td></td></tr></tbody><tfoot><tr><td>v<sub>1</sub></td><td>...</td><td>v<sub>7</sub></td><td>v<sub>8</sub></td><td>...</td><td>v<sub>14</sub></td><td>v<sub>15</sub></td><td>...</td><td>v<sub>24</sub></td></tr></tfoot></table>

On this profile, $W = \{c_1, c_2, c_5, c_6, c_7, c_8\}$ is the unique global (and unique local) PAV committee for $k = 6$. However $W$ is not in the Droop core: consider $T = \{c_1, c_2, c_3, c_4\}$, which has support from $\frac{14}{24} \approx 0.583$ of the voters, while $|T|/(k+1) = \frac{4}{7} \approx 0.571$ is strictly smaller. □

This example is minimal, so the Droop core is non-empty when $k \le 5$. Running the recursive PAV rule (Algorithm 1) with the Droop quota stops working even for $m = 10, k = 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 $k = 6$ and $m = 10$.

Our approach was based on linear programming, and in particular this approach allowed us to reason independently of the number of voters. The PAV rule and its variants are particularly well-suited for these LP formulations. However, finding core counterexamples for many other rules is not possible using similar linear programs. For example, the Method of Equal Shares

<footnote n="8">⁸However, regarding strategic aspects, impossibility theorems become somewhat more expansive when passing to the Droop quota (Peters, 2018, Section 5.3).</footnote>
(MES) (Peters and Skowron, 2020) or the sequential Phragmén method (Phragmén, 1894; Janson, 2016) do not admit the same kind of linear formulations (because they would require multiplying variables corresponding to ballot frequencies with variables corresponding to $\rho$-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. I am also not aware of any example 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 $n = 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ölz 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).

## 8 References

Haris Aziz, Anna Bogomolnaia, and Hervé Moulin. 2020. Fair mixing: the case of dichotomous preferences. *ACM Transactions on Economics and Computation* 8, 4 (2020), 18:1–18:27. doi:10.1145/3417738 [→ p. 4]

Haris Aziz, Markus Brill, Vincent Conitzer, Edith Elkind, Rupert Freeman, and Toby Walsh. 2016. Justified representation in approval-based committee voting. arXiv:1407.8269v4 [cs.MA] https://arxiv.org/abs/1407.8269v4 [→ p. 2]

Haris Aziz, Markus Brill, Vincent Conitzer, Edith Elkind, Rupert Freeman, and Toby Walsh. 2017. Justified representation in approval-based committee voting. *Social Choice and Welfare* 48, 2 (2017), 461–485. doi:10.1007/s00355-016-1019-3 [→ p. 2, 3, 10]

Haris Aziz, Edith Elkind, Shenwei Huang, Martin Lackner, Luis Sánchez-Fernández, and Piotr Skowron. 2018. On the complexity of extended and proportional justified representation. In *Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI)*. 902–909. doi:10.1609/aaai.v32i1.11478 [→ p. 2, 3, 8]

Haris Aziz, Serge Gaspers, Joachim Gudmundsson, Simon Mackenzie, Nicholas Mattei, and Toby Walsh. 2015. Computational aspects of multi-winner approval voting. In *Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS)*. 107–115. https://www.ifaamas.org/Proceedings/aamas2015/aamas/p107.pdf [→ p. 3]

Haniel Barbosa, Clark W. Barrett, Martin Brain, Gereon Kremer, Hanna Lachnitt, Makai Mann, Abdalrhman Mohamed, Mudathir Mohamed, Aina Niemetz, Andres Nötzli, Alex Ozdemir, Mathias Preiner, Andrew Reynolds, Ying Sheng, Cesare Tinelli, and Yoni Zohar. 2022. cvc5: A versatile and industrial-strength SMT solver. In *Proceedings of the 28th International Conference*
on Tools and Algorithms for the Construction and Analysis of Systems (TACAS) (Lecture Notes in Computer Science, Vol. 13243). Springer, 415–442. doi:10.1007/978-3-030-99524-9_24 [→ p. 15]

Xiaohui Bei, Xinhang Lu, and Warut Suksompong. 2025. Truthful cake sharing. *Social Choice and Welfare* 64 (2025), 309–343. doi:10.1007/s00355-023-01503-0 [→ p. 4]

Florian Brandl, Felix Brandt, Dominik Peters, and Christian Stricker. 2021. Distribution rules under dichotomous preferences: Two out of three ain't bad. In *Proceedings of the 22nd ACM Conference on Economics and Computation (EC)*. 158–179. doi:10.1145/3465456.3467653 [→ p. 4]

Markus Brill, Rupert Freeman, Svante Janson, and Martin Lackner. 2023. Phragmén's voting methods and justified representation. *Mathematical Programming* (2023). doi:10.1007/s10107-023-01926-8 [→ p. 2]

Markus Brill, Paul Gölz, Dominik Peters, Ulrike Schmidt-Kraepelin, and Kai Wilker. 2022. Approval-based apportionment. *Mathematical Programming* (2022). doi:10.1007/s10107-022-01852-1 [→ p. 2, 3, 5, 6]

Markus Brill and Jannik Peters. 2023. Robust and verifiable proportionality axioms for multi-winner voting. In *Proceedings of the 24th ACM Conference on Economics and Computation (EC)*. 301. doi:10.1145/3580507.3597785 Full version arXiv:2302.01989. [→ p. 2, 5]

Moses Charikar, Alexandra Lassota, Prasanna Ramakrishnan, Adrian Vetta, and Kangning Wang. 2024. Six candidates suffice to win a voter majority. arXiv:2411.03390 [cs.GT] To appear in STOC 2025. [→ p. 4]

Yu Cheng, Zhihao Jiang, Kamesh Munagala, and Kangning Wang. 2020. Group fairness in committee selection. *ACM Transactions on Economics and Computation (TEAC)* 8, 4 (2020), 1–18. doi:10.1145/3417750 [→ p. 2, 4]

Brandon Fain, Ashish Goel, and Kamesh Munagala. 2016. The core of the participatory budgeting problem. In *Proceedings of the 12th International Conference on Web and Internet Economics (WINE)*. 384–399. doi:10.1007/978-3-662-54110-4_27 [→ p. 4]

Brandon Fain, Kamesh Munagala, and Nisarg Shah. 2018. Fair allocation of indivisible public goods. In *Proceedings of the 2018 ACM Conference on Economics and Computation (EC)*. 575–592. doi:10.1145/3219166.3219174 [→ p. 4]

Duncan K. Foley. 1970. Lindahl's solution and the core of an economy with public goods. *Econometrica* 38, 1 (1970), 66–72. doi:10.2307/1909241 [→ p. 4]

Svante Janson. 2016. Phragmén's and Thiele's election methods. arXiv:1611.08826 [math.HO] https://arxiv.org/abs/1611.0882 [→ p. 2, 15]

Svante Janson. 2018. Thresholds quantifying proportionality criteria for election methods. arXiv:1810.06377 [cs.GT] https://arxiv.org/abs/1810.06377 [→ p. 14]

Zhihao Jiang, Kamesh Munagala, and Kangning Wang. 2020. Approximately stable committee selection. In *Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC)*. 463–472. doi:10.1145/3357713.3384238 [→ p. 2, 4]

Sonja Kraiczy and Edith Elkind. 2024. A lower bound for local search Proportional Approval Voting. In *Proceedings of the 32nd Annual European Symposium on Algorithms (ESA)*. 82:1–82:14. doi:10.4230/LIPIcs.ESA.2024.82 [→ p. 3]
Christian Kroer and Dominik Peters. 2025. Computing Lindahl equilibrium for public goods with and without funding caps. arXiv:2503.16414 [cs.GT] https://arxiv.org/abs/2503.16414 [→ p. 4]

Jan Maly. 2023. The core of an approval-based PB instance can be empty for nearly all cost-based satisfaction functions and for the share. arXiv:2311.06132 [cs.GT] https://arxiv.org/abs/2311.06132 [→ p. 4, 15]

Kamesh Munagala, Yiheng Shen, and Kangning Wang. 2022a. Auditing for core stability in participatory budgeting. In Proceedings of the 18th International Conference on Web and Internet Economics (WINE). Springer, 292–310. doi:10.1007/978-3-031-22832-2\_17 [→ p. 4]

Kamesh Munagala, Yiheng Shen, Kangning Wang, and Zhiyi Wang. 2022b. Approximate core for committee selection via multilinear extension and market clearing. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 2229–2252. doi:10.1137/1.9781611977073.89 [→ p. 2, 4]

Dominik Peters. 2018. Proportionality and strategyproofness in multiwinner elections. In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS). 1549–1557. https://arxiv.org/abs/2104.08594 [→ p. 14]

Dominik Peters, Grzegorz Pierczyński, and Piotr Skowron. 2021. Proportional participatory budgeting with additive utilities. In Advances in Neural Information Processing Systems, Vol. 34. 12726–12737. doi:10.48550/arXiv.2008.13276 [→ p. 4, 11]

Dominik Peters and Piotr Skowron. 2020. Proportionality and the limits of welfarism. In Proceedings of the 21st ACM Conference on Economics and Computation (EC). 793–794. doi:10.1145/3391403.3399465 Full version arXiv:1911.11747. [→ p. 2, 3, 4, 10, 15]

Edvard Phragmén. 1894. Sur une méthode nouvelle pour réaliser, dans les élections, la représentation proportionnelle des partis. Öfversigt af Kongliga Vetenskaps-Akademiens Förhandlingar 51, 3 (1894), 133–137. https://dominik-peters.de/archive/phragmen1894.pdf [→ p. 2, 15]

Grzegorz Pierczyński and Piotr Skowron. 2022. Core-stable committees under restricted domains. In Proceedings of the 18th International Conference on Web and Internet Economics (WINE). Springer, 311–329. doi:10.1007/978-3-031-22832-2\_18 [→ p. 2]

Simon Rey and Jan Maly. 2023. The (computational) social choice take on indivisible participatory budgeting. arXiv:2303.00621 [cs.GT] https://arxiv.org/abs/2303.00621 [→ p. 4]

Luis Sánchez-Fernández, Edith Elkind, Martin Lackner, Norberto Fernández, Jesús Fisteus, Pablo Basanta Val, and Piotr Skowron. 2017. Proportional justified representation. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI). 670–676. doi:10.5555/3298239.3298338 [→ p. 3]

Piotr Skowron. 2021. Proportionality degree of multiwinner rules. In Proceedings of the 22nd ACM Conference on Economics and Computation (EC). 820–840. doi:10.1145/3465456.3467641 [→ p. 3]

Mashbat Suzuki and Jeremy Vollen. 2024. Maximum flow is fair: A network flow approach to committee voting. In Proceedings of the 25th ACM Conference on Economics and Computation (EC). 964–983. doi:10.1145/3670865.3673603 [→ p. 4]
Thorvald N. Thiele. 1895. Om Flerfold Valg. *Oversigt over det Kongelige Danske Videnskabernes Selskabs Fordhandlinger* (1895). https://dominik-peters.de/archive/thiele1895.pdf [→ p. 1, 2, 3]

Lirong Xia. 2025. A linear theory of multi-winner voting. arXiv:2503.03082 [cs.GT] https://arxiv.org/abs/2503.03082 [→ p. 15]

Yongjie Yang and Jianxin Wang. 2023. Parameterized complexity of multiwinner determination: more effort towards fixed-parameter tractability. *Autonomous Agents and Multi-Agent Systems* 37, 2 (2023), 28. doi:10.1007/s10458-023-09610-z [→ p. 3]