Finding Representative and Approximately Efficient Committees

1 Introduction

• The introduction frames the problem as finding efficient procedures that retain PAV's combination of EJR+ and Pareto optimality despite the NP-hardness of computing an optimal PAV committee.It describes PAV as maximizing the sum of harmonic utilities induced by voters' approved elected candidates.Source: §1 · pp. 1–2

Measuring Efficiency

• Fractional Pareto optimality is tractably verifiable by linear programming, and α-fPO also captures fractional improvements that may matter to voters considering lotteries.The paper motivates measuring efficiency through approximate fPO and PAV-score approximation, while noting that higher PAV scores do not always imply better committees.Source: Measuring Efficiency · pp. 2–3

Our Contributions

• The paper studies global PAV's efficiency and contrasts its α⋆-fPO guarantee with the weaker 2-fPO guarantee of local PAV.The comparison of relaxations and local search explains why adding local search to the DMMS algorithm may fail to retain α⋆-fPO.Source: Our Contributions · p. 3, Related Work · p. 5
• The paper also examines strategies for combining JR or EJR+ with exact fPO, but reports that later work showed no JR committee need satisfy fPO.The appendix counterexamples to attempted strategies are included as potential test cases despite being formally superseded.Source: Our Contributions · pp. 3–4
• For τ ≥ 1/poly(n,k), τ-local-PAV can be found by polynomial-time local search; local PAV provides a 2-fPO worst-case guarantee versus global PAV’s 1.346-fPO guarantee, and some instances have local-PAV score at most 2/3 of optimum.Source: Our Contributions · pp. 3–4
• The polynomial-time round-and-swap algorithm returns committees satisfying EJR+, weak PO, 1.346-fPO, and a 0.79-approximation to the PAV score.It uses pipage rounding followed by PAV-improving local search.Source: Our Contributions · p. 4

Related Work

• Computing optimal PAV is NP-hard, while prior work gives a 0.79 approximation threshold and polynomial algorithms on some restricted domains.The paper distinguishes its approach from DMMS through a concave lower surrogate and a local-search phase.Source: Related Work · p. 5

Problem instance

• An instance has voters with approved candidate subsets, a candidate set, and a committee size; integral committees select exactly k candidates, while fractional committees assign candidate weights summing to k.Each voter is assumed to approve at least one candidate.Source: §2 · p. 6

Pareto optimality

• Weak PO rules out a committee strictly preferred by every voter, whereas α-fPO rules out fractional committees that improve every voter's utility by at least factor α.The preliminaries distinguish integral PO, weak PO, and fractional Pareto optimality.Source: §2 · p. 7

Representation notions and voting rules

• EJR+ and related representation axioms constrain representation for sufficiently large groups, while PAV is a Thiele rule using harmonic weights.PAV maximizes the sum of voters' harmonic utilities, satisfies EJR+, and its optimal score is NP-hard to approximate beyond the stated threshold unless P = NP.Source: §2 · pp. 7–8

Voting rules

• A τ-local-PAV committee admits no winning-to-losing candidate swap that increases PAV by at least τ; inverse-polynomial τ permits polynomial-time local search.For τ ≤ n/k^2, such committees satisfy EJR+; unless P = NP, polynomial-time PAV-score approximation cannot exceed γ⋆≈0.79.Source: §2 · p. 8

Harmonic utility

• The function h is a Poisson-smoothed harmonic utility, with h(μ)=E[H_Z] for Z distributed as Poisson with mean μ.The supplied results give α⋆≈1.346 from h(α⋆)=1 and γ⋆=h(1)≈0.79.Source: §2 · pp. 9–10, Figure 1 · p. 9

PAV as a submodular function and pipage rounding

• PAV is monotone and submodular, and pipage rounding converts a fractional committee into an integral size-k committee without decreasing its multilinear-extension score.The rounding preserves candidate marginals and can be derandomized in polynomial time.Source: §2 · p. 10

3.1 Results for τ-local-PAV

• For a τ-local PAV committee, weak Pareto optimality holds when τ ≤ n/k²; every τ-local PAV committee is 2-fPO whenever 0 ≤ τ ≤ 1/(2k²).Source: §3.1 · pp. 11, 13
• For τ-local-PAV, the thresholds for (1+ε)-PO, 2-fPO, and the 2/3 PAV-score approximation are not tight, and their tight values remain open.The guarantees stated in Theorem 3.1 are for fixed n and k; for any fixed τ > 0, allowing k to grow precludes k-independent approximation guarantees for fPO and PAV score.Source: §3.1 · p. 15

3.2 Results for Global PAV

• Every global PAV committee is Pareto optimal and α⋆-fPO, where α⋆≈1.346, and the fractional guarantee is asymptotically tight.The tightness construction uses a fractional committee over auxiliary candidates that improves every voter while no integral committee beats the baseline committee.Source: §3.2 · pp. 15, 18

3.3 Results for the DMMS Algorithm

• The DMMS algorithm runs in polynomial time, gives a γ⋆≈0.79 approximation to optimal PAV score, and satisfies fPO, but a particular execution can fail JR.Because fPO implies PO and weak PO, the algorithm also satisfies those properties.Source: §3.3 · p. 18

3.4 Our Algorithm

• The round-and-swap algorithm is presented as a polynomial-time algorithm, and computes an approximately optimal solution to a concave program for Ψ.Its target satisfies Ψ(bx) ≥ Ψ⋆ − η, with η = 1/(1024n^2mk^2).Source: §3.4 · pp. 18–19
• Algorithm 1 returns an EJR+ committee that is α*-fPO (α*≈1.346), weakly Pareto optimal, (1+ε)-PO for every ε>0, and a 0.79-approximation to the optimal PAV score.The guarantees hold in polynomial time.Source: §3.4 · pp. 19–20
• The algorithm approximately optimizes a smooth concave surrogate, pipage-rounds the fractional solution under FPAV, then runs PAV-improving swaps until reaching a 1/(2k^2)-local-PAV committee.The local search performs swaps only when they improve PAV score by at least 1/(2k^2).Source: §3.4 · pp. 19–20
• Local search terminates within 2nk^2H_k swaps, yields EJR+, and preserves PAV(W) ≥ Ψ(x*) from the surrogate optimum.The swap bound follows because each swap increases PAV by at least 1/(2k^2), while any committee’s score is at most nH_k.Source: §3.4 · p. 20
• An example shows that a run using DMMS’s fractional committee followed by local search can fail 1.346-fPO and achieve no better than 2-fPO, although DMMS alone satisfies fPO.Thus, adding local search to that fractional committee can damage fractional Pareto optimality by a factor of at least 2.Source: §3.4 · p. 21

4 Conclusion and Future Directions

• The round-and-swap algorithm’s committee satisfies EJR+, weak PO, (1 + ε)-PO for every ε > 0, α⋆-fPO, and the optimal polynomial-time PAV-score approximation unless P = NP.The paper identifies the result as combining its representation and efficiency guarantees.Source: §4 · p. 21
• The paper analyzes efficiency properties of global PAV and local PAV, using multiplicative approximate fPO as a quantitative efficiency measure.It establishes a tight α⋆-fPO threshold for global PAV and weaker but nontrivial global efficiency guarantees for local PAV.Source: §4 · p. 21
• A future question is the sharp α threshold for committees satisfying JR and α-fPO, alongside whether such committees can be computed efficiently when existence is guaranteed.The paper notes that its algorithm gives an upper bound of α⋆ ≈ 1.346 even for EJR+, while the cited impossibility rules out α = 1 even for JR.Source: §4 · pp. 21–22
• The paper suggests revisiting failed approaches to combining JR or EJR+ with exact fPO, since some may yield approximate-fPO guarantees on general or restricted domains.Such approaches might improve on α⋆ with weaker representation requirements or additional structure.Source: §4 · p. 22

Usage of Artificial Intelligence

• LLMs helped produce many proofs and examples, and the authors say most results and techniques were found with model assistance.The authors distinguish their own role in posing questions and designing some techniques from assistance in obtaining other results.Source: Usage of Artificial Intelligence · p. 22
• The authors identify asking whether local PAV satisfies weak PO, relaxing fPO multiplicatively, and seeking a polynomial-time method as their technical contributions.They say GPT-5 supplied the proof of local PAV’s weak PO in October 2025.Source: Usage of Artificial Intelligence · p. 22
• The authors say they did almost all of the paper’s writing and presentation themselves.Source: Usage of Artificial Intelligence · p. 22

A.1 Connecting h(·) and Harmonic Numbers (Lemmas 2.1, 2.2, and 2.3)

• For a Poisson random variable Z with mean μ, h(μ) equals the expected harmonic number H_Z.Source: §A.1 · p. 27
• An integration step over [0, 1) yields a value of approximately 0.79.Source: §A.1 · p. 27
• For every integer t ≥ 1, h(t) < H_t, using the concavity of the piecewise-linear interpolation of harmonic numbers.The proof uses h(t) = E[H_X] for X distributed as Poisson with mean t.Source: §A.1 · p. 27
• For every integer t ≥ 1, h(t) ≥ γ⋆H_t, obtained by combining the first-interval contribution with bounds on later summands.Source: §A.1 · pp. 27–28
• The positive solution α⋆ of h(α⋆) = 1 satisfies α⋆ > 4/3.Source: §A.1 · p. 28

Pareto optimality

• Even exact local PAV can return a committee that is Pareto dominated, so local optimality does not guarantee Pareto optimality.In the construction, every voter has utility 1 under W, while W′ gives second-type voters utility 2 and leaves first-type voters at 1.Source: B Properties of Local PAV (Theorem 3.1) · pp. 30–31

Weak Pareto optimality

• For every τ > n/k², some τ-local-PAV committee is not weakly Pareto optimal.The auxiliary committee gives every voter utility 2 instead of 1, while the baseline committee remains τ-local PAV.Source: B Properties of Local PAV (Theorem 3.1) · p. 31

EJR+

• For τ ≤ n/k², every τ-local-PAV committee satisfies EJR+; the threshold is tight for this guarantee.The supplied construction is τ-local PAV but violates EJR+ for every τ > n/k².Source: B Properties of Local PAV (Theorem 3.1) · p. 31

(1 + ε)-Pareto optimality

• For τ ≤ 1/k², τ-local PAV is (1 + ε)-Pareto optimal for every ε > 0, but the guarantee cannot generally extend to τ > 1/k.The counterexample is τ-local for every τ > 1/k while W′ (1 + ε)-Pareto dominates W for 0 < ε < 1/(k−1).Source: B Properties of Local PAV (Theorem 3.1) · pp. 31–32

2-fPO counterexamples

• The 2-fPO bound is asymptotically tight even for exact local PAV: the construction is fractionally α-Pareto dominated for every α < 2k/(k + 1), which tends to 2.A separate construction shows that for τ > 1/⌈k/2⌉, τ-local PAV may fail 2-fPO.Source: B Properties of Local PAV (Theorem 3.1) · p. 32

2/3-PAV approximation counterexamples

• The PAV-score approximation guarantee is asymptotically at most 2/3 even for exact local PAV.In the construction, PAV(O)/PAV(W) tends to 2/3; another example shows failure of a 2/3-approximation when τ > 1/(σk + 1).Source: B Properties of Local PAV (Theorem 3.1) · p. 33

B.1 Justifying Parameter-Dependent Bounds

• For any fixed τ > 0, τ-local PAV admits no k-independent approximation factor for fractional Pareto optimality or positive k-independent multiplicative approximation to the optimal PAV score.The construction keeps the number of approved winners s fixed as k grows, while the all-approved committee has utility k and score Hk.Source: §B.1 · pp. 33–34

Proof of Asymptotic Tightness

• The construction assigns mass 1/c to each of ck auxiliary candidates, giving every voter fractional utility d/c = γ while the baseline committee gives utility 1.Taking γ between α and α⋆ yields fractional α-domination; the proof shows every committee using an auxiliary candidate has lower PAV score than the baseline committee.Source: C Proof of Asymptotic Tightness of… · pp. 35–36
• For every α < α⋆, there is an instance with a global PAV committee that is fractionally α-Pareto dominated, making the α⋆-fPO factor asymptotically tight.The proof chooses γ between α and α⋆, then constructs instances in which the baseline committee is the unique global PAV committee despite fractional domination.Source: C Proof of Asymptotic Tightness of… · pp. 35–36

D Properties of the DMMS algorithm

• The DMMS algorithm maximizes a relaxation using linearly interpolated harmonic scores, then pipage-rounds its fractional solution; the resulting committee satisfies fPO.The rounding preserves coordinates already equal to 0 or 1, and the algorithm’s output satisfies the weighted-support condition for fPO.Source: D Properties of the DMMS algorithm · pp. 36–37
• The DMMS algorithm can fail JR, and performing local search to obtain JR may yield an output that is not better than 2-fPO.In the construction, the algorithm can return W0 = S, which violates JR; local PAV search can reach W = L, whose fractional domination approaches a factor of 2.Source: D Properties of the DMMS algorithm · pp. 37–39

E Approaches That Fail To Show Existence of JR and fPO

• For every instance, JR and fPO coexist if and only if there is a committee of size at most k contained in a top set that leaves fewer than n/k approvers unrepresented for each candidate.If such a committee exists, adding the next-highest-scoring candidates to reach size k preserves JR.Source: E Approaches That Fail To Show… · p. 40

E.1 Sequential Weight-Raising Algorithm

• The weight-raising idea is adapted from related rules for fair mixing and fractional committees.The section cites Brandl et al. (2021) and Suzuki and Vollen (2024) for related approaches.Source: §E.1 · p. 41
• The natural weight-raising procedure ends with a top set covering every voter, but a JR committee need not exist within that set.The procedure repeatedly raises the weights of voters not represented in the current top set until a new candidate joins it.Source: §E.1 · p. 41
• With 39 voters and k = 3, the initial top set excludes the candidate approved by B, and no JR committee exists within that set.Any three candidates in the top set represent at most three of the 16 voters in B, leaving 13 unrepresented voters who all approve the excluded candidate.Source: §E.1 · p. 41
• For k ≥ n−1, the approach proves the existence of JR+fPO: represent n voters when k ≥ n, or any n−1 voters when k = n−1.When k = n−1, representing n−1 voters suffices for JR because n/k > 1.Source: §E.1 · p. 41

E.2 Sufficient Conditions on the Weight Vector

• The discussion motivates weight bounds related to inverse utility, a form also appearing in the first-order condition for maximizing Nash welfare over divisible private goods.The passage describes the condition as making each agent’s weight approximately equal to 1/ui(Ai).Source: §E.2 · pp. 41–42
• The EJR+ proof strategy draws on the familiar 1/ui(W) terms in the proof that PAV satisfies EJR+ (Aziz et al., 2017).The section formulates a sufficient weight condition from this connection.Source: §E.2 · p. 42
• A weighted-welfare-maximizing committee satisfies EJR+ when each voter’s weight lies between 1/ui(W) + 1 and 1/ui(W), with 1/ui(W) treated as infinity at zero utility.The condition is presented as a sufficient weight-based route to EJR+.Source: §E.2 · p. 42
• The analogous JR condition requires unrepresented voters to have weight at least 1 and the committee’s total weighted support to be below n.Under these conditions, a weighted-welfare-maximizing committee satisfies JR.Source: §E.2 · p. 42
• Minimizing total weighted support subject to the JR weight condition does not always yield a value below n.In a six-voter example of two disjoint triangles, every qualifying maximizing committee has total weighted support at least 6 = n.Source: §E.2 · pp. 42–43

E.3 Support of Efficient Rules for Fractional Committee Selection

• Every committee in every lottery implementing a fractional Nash optimal committee can fail JR in the constructed instance.The fractional optimum assigns mass 4/19 to each of 19 original candidates and zero to newly added candidates; implementing lotteries therefore use size-4 committees of original candidates, each leaving 3003 voters unrepresented, at least n/k = 2907.Source: §E.3 · p. 43
• The same instance shows that RUT and capped Lindahl rules can fail ex-post JR because their implementing lotteries are supported only on size-4 committees of original candidates.The passage identifies RUT and the capped Lindahl equilibrium as fractional rules with fPO and JR-like fairness properties.Source: §E.3 · p. 43

E.4 Repeated Search for Dominating Committee

• Searching for Pareto improvements from a JR committee could preserve JR, but checking for an integral Pareto improvement is NP-hard.Each Pareto improvement increases utilitarian social welfare by at least one utility point, so the proposed process would terminate if the search were feasible.Source: §E.4 · p. 44
• A fractional improvement cannot always be replaced by a JR committee from a convex combination: {c1, c5} is JR but not fPO, yet no such combination fractionally dominates it.The example identifies a failure mode for the proposed iterative search using fractional improvements.Source: §E.4 · p. 44

E.5 Maximizing approval score subject to JR

• Convex Thiele objectives are characterized by strictly increasing, convex h and are not natural candidates for JR-style fairness; approval score is the linear boundary case.Approval Voting itself can fail JR, but maximizing its score subject to JR gives a JR and PO committee, which may still fail fPO.Source: §E.5 · p. 44
• In the example, c1, c2, and c3 each have approval score 60, while c6 scores 64 and c5 scores 36.The 33 voters approving only c5 are fewer than 100/3, whereas c5 is approved by 34 unrepresented voters in each higher-scoring alternative.Source: §E.5 · p. 45
• The unique JR committee maximizing approval score, W* = {c1, c2, c3}, is fractionally dominated by y, while the only committees with at least its score violate JR.The alternative y gives every voter at least their utility under W* and gives the voter approving only {c6} utility 0.2 rather than 0.Source: §E.5 · p. 45

• All Thiele methods satisfying JR fail fPO, motivating the question of whether optimizing a Thiele score subject to fPO preserves JR (Becker et al., 2026, Observation 2).Source: §E.6 · p. 45

Example E.10

• The 8-seat PAV committee W is fPO and uniquely PAV-maximizing among fPO committees, yet violates JR because 60 voters approving b are unrepresented.The argument also shows that every other size-8 committee has a strictly lower PAV score.Source: §E.6 · pp. 45–47

Example E.11

• The 4-seat committee W is fPO and uniquely CC-maximizing among fPO committees, with CC score 180, yet the example violates JR.The example states that W has CC score 180; a listed alternative committee has score 141.Source: §E.6 · p. 46