Source-linked AI summary
Nash Core in Multiwinner Election
Ashish Goel, Zhihao Jiang, Chenghan Zhou
TL;DR
The paper addresses whether stable core committees exist in approval-based elections, especially when candidates are selected fractionally or discretely. It introduces candidate-weighted Nash-core formulations and payment certificates, proving fractional existence under an assumption, discrete existence for at most eight equally weighted voters, and efficiently verifiable certificates for unrestricted discrete elections. Experiments show that iterative heuristics efficiently find the proposed solutions on real voting data.
Problem
Core existence is unresolved for unrestricted discrete approval elections, while discrete-core membership is coNP-hard.
Method
The paper uses candidate-weighted Nash social welfare and proportional payments for fractional committees, then extends the framework to discrete Nash-core and weak Nash-core certificates.
Results
The paper proves fractional Nash-core existence under Assumption 1, core existence for elections with at most eight equally weighted voters, and that weak Nash-core membership implies discrete-core membership.
Takeaways & Limitations
The Nash-core framework supplies payment-based fractional core solutions and an efficiently verifiable route to discrete-core solutions in unrestricted elections.
Takeaways & Limitations
The unrestricted discrete-core existence question remains open, and the iterative heuristics lack formal convergence guarantees.
Abstract
from arXiv · showhide
In the approval-based committee selection problem, a committee is said to be in the core if no subset of voters has an incentive to deviate by selecting a \emph{blocking} committee of proportional size, such that every voter in the deviating group strictly prefers the blocking committee. We consider the setting where candidates can be selected fractionally. Under a mild regularity assumption, we show that there always exists a weighting of candidates such that the fractional committee maximizing the candidate-weighted Nash Social Welfare is in the core. We refer to such a solution as being in the \emph{Nash core}. Additionally, we show that a Nash core solution admits a payment assignment between voters and candidates, where each voter pays a candidate they approve in proportion to the weight. For the discrete setting, where each candidate is either included or excluded from the committee, we prove that every approval-based committee election with at most eight equally weighted voters has a core committee by rounding the fractional Nash core solution. Although the non-emptiness of the core in this setting remains an open question and checking core membership is coNP-hard, we extend the notion of the Nash core to the discrete case, yielding a formulation that is efficiently verifiable and offers a promising path toward establishing core existence in discrete settings. Finally, we test our approach on real voting data using a payment-guided heuristic. We empirically show that the Nash core solution can be efficiently computed through an iterative algorithm in both the fractional and discrete settings.
1 Introduction
The paper studies core stability in fractional and discrete approval-based committee selection. It introduces Nash-core formulations, proves fractional and bounded-voter existence results, develops efficiently verifiable discrete certificates, and evaluates iterative heuristics on real voting data.
- 1.1 Model and the Core: The core requires that no voter coalition can select a proportionally sized committee that every coalition member strictly prefers.The paper defines fractional and discrete core variants for approval-based committee selection.
- 1.3 Proportional Payment: A fractional Nash-core solution admits proportional payments in which voters allocate budgets among approved selected candidates according to weighted selected amounts.The payment interpretation links candidate prices, weights, and voter allocations.
- 1.4 Our Results: Fractional Nash-core solutions exist under Assumption 1 and always belong to the fractional core.They also optimize candidate-weighted Nash social welfare and correspond exactly to proportional payment schemes.
- Discrete Core Existence: Every approval-based election with at most eight equally weighted voters has a discrete core committee.The proof combines fractional Nash-core structure with exact computer-assisted classification of residual regions.
- Nash-Core Certificates: For unrestricted discrete elections, the discrete Nash core implies the weak Nash core, which implies the discrete core and is efficiently verifiable.The discrete Nash core extends PAV with weighted adjustments, while the weak variant modifies MES through weighted payments.
- Experiments: Iterative heuristics efficiently find fractional Nash-core and weak Nash-core pairs on tested real voting instances, although they lack formal convergence guarantees.The approach certifies weak Nash-core membership instead of directly checking coNP-hard discrete-core membership.
2 The Fractional Setting
The fractional setting establishes that, under Assumption 1, a candidate-weighted Nash-social-welfare solution exists and lies in the fractional core. It also connects Nash-core solutions to proportional payments, convex optimization, and Lindahl equilibria.
- 2.1 Nash Core Solution is Core Solution: Theorem 2 shows that every fractional Nash core solution is a fractional core solution.
- 2.2 Existence of Nash Core Solutions: A concave game is constructed whose pure Nash equilibrium corresponds to a fractional Nash core solution.The construction uses candidate players and an additional player maximizing the geometric mean of weighted voter utilities.
- 2.3 Connection with the Convex Program: A proportional payment assigns voter contributions to approved candidates according to weighted selected amounts, with discounts permitted for fully selected candidates.Each voter has a unit budget, and the candidate price is fixed at n/k.
- 2.3 Connection with the Convex Program: The convex program has optimal solutions in the fractional core, and every fractional Nash core solution corresponds to an optimal solution of that program.The program is convex because its objective is strictly concave in b and affine in x, with affine constraints; KKT conditions suffice for optimality.
- 2.4 Connection with Lindahl equilibrium: Every proportional payment induces per-voter prices forming a Lindahl equilibrium, although the converse implication does not hold.The paper explicitly notes that the converse is disproved by an example.
- 2.4 Connection with Lindahl equilibrium: The fractional Nash-core allocation and proportional-payment prices are used to establish discrete-core existence for elections with at most eight equally weighted voters.
3 Discrete-Core Nonemptiness for Eight Equal-Weight Voters
Every approval-based committee election with at most eight equally weighted voters has a committee in the discrete core. The proof rounds a fractional Nash-core allocation, reducing unresolved cases to finitely verified binary antichain instances.
- The proof begins with a fractional Nash-core allocation using the minimum possible number of fractional candidates and derives a structured residual binary matrix.The matrix has pairwise distinct antichain columns and full column rank after unresolved cases are isolated.
- Every approval-based committee election with at most eight equally weighted voters has a committee in the discrete core.
- The theorem applies to arbitrary committee sizes and candidate counts, but is parameterized by individual voters rather than voter types.
- If the residual floor vector is implementable, selecting the corresponding integral candidates yields a committee satisfying the required voter utility floors and hence lying in the discrete core.
- Exact computer-assisted verification settles all remaining eight-row regions using fixed and adaptive price–saturation certificates.The census contains 1,085,483 previously unsettled regions; 1,085,459 receive fixed certificates and 24 adaptive certificates.
- The result is existential and does not itself provide a polynomial-time algorithm, while unrestricted discrete-core nonemptiness remains open.
4 Nash-Core Certificates in the General Discrete Setting
The paper extends candidate-weighted Nash-core ideas to discrete committees through discrete and weak Nash-core certificates. Weak Nash-core membership is efficiently verifiable and implies membership in the discrete core, although certificate existence in unrestricted elections remains conjectural.
- Weak Nash-core membership can be checked efficiently, but the existence of these certificates for unrestricted elections remains conjectural.
- The discrete Nash core extends the candidate-weighted Nash-core framework to committees whose candidate variables are binary.
- Weighted harmonic utilities extend PAV to fractional candidate weights using the Digamma-based continuous harmonic-number generalization.
- The discrete Nash core maximizes a candidate-weighted harmonic-utility score over committees of size at most k.
- The weak Nash core instead requires that no unselected candidate would significantly increase the weighted score if added to the committee.
- Discrete Nash-core solutions imply weak Nash-core solutions, and weak Nash-core solutions lie in the discrete core.
5 Heuristically Computing the Core
The paper evaluates heuristic algorithms for approximately computing fractional Nash-core and weak Nash-core solutions on large real-world approval-election datasets.
- The evaluation uses Pabulib data, focusing on the 100 largest datasets and an additional 1000 smaller datasets.The largest datasets contain more than 3000 voters and 50 candidates; the ten largest contain approximately 10^5 voters and 100 candidates.
- The heuristics approximately compute both fractional Nash-core solutions and weak Nash-core solutions.
6 Conclusions and Future Directions
The paper develops Nash-core approaches for fractional and discrete approval-based committee selection, including exact bounded-voter results and efficiently verifiable certificates. It also identifies open existence and computation questions while reporting efficient empirical heuristics.
- The paper establishes fractional and discrete approaches to the core, including complementary Nash-based certificates for unrestricted discrete elections.
- Fractional Nash core, proportional payments, and fractional-core inclusion coincide under Assumption 1.
- Every election with at most eight equally weighted voters has a discrete core committee, while unrestricted discrete core existence remains unresolved.
- The weak Nash core is straightforward to verify and implies membership in the discrete core.
- Heuristic searches run efficiently on real-world voting data but provide numerical evidence without proving convergence or existence.
- Future directions include Nash-core uniqueness, theoretically guaranteed computation, unrestricted discrete-core existence, and weak Nash-core existence.
A.1 Proof of Theorem 1
Theorem 1 characterizes fractional Nash-core solutions exactly through proportional payments. Its proof establishes both implications using Nash optimality, payment conditions, and convex-optimization optimality conditions.
- Theorem 1 states that a fractional Nash-core pair is equivalent to a pair supported by a proportional payment.
- The forward direction derives proportional payments from weight-selection coupling and Nash optimality.
- Nash optimality implies positive voter utilities and full committee size under the standing nonempty-approval assumption.
- KKT conditions establish affordability, stability, and weight-selection coupling for the payment scheme.
- The reverse direction verifies positive utility, proportional payments, stability, and coupling, then uses concavity and convexity for Nash optimality.
- The proof concludes that the resulting payment-supported pair satisfies the fractional Nash-core definition.
A.3 Proof of Theorem 5
Theorem 5 links the discrete Nash core, weak Nash core, and discrete core. Consequently, a discrete Nash-core solution certifies discrete-core membership through an efficiently checkable intermediate condition.
- Theorem 5 proves that discrete Nash-core membership implies weak Nash-core membership, which implies discrete-core membership.
- The first implication is established by contradiction using candidate augmentation and optimality of the discrete Nash objective.
- The second implication shows that any blocking coalition would contradict the weak Nash-core inequalities.
- Thus a weak Nash-core solution yields a discrete core solution, and the discrete Nash core directly implies the discrete core.
- The theorem’s proof is assembled from the two implication lemmas and supporting appendix results.
B.1 Proof of the minimum-fractionality reduction
The minimum-fractionality reduction constrains any non-implementable fractional Nash-core solution. It shows that fractional candidates have distinct, incomparable supports and that the associated support matrix has full column rank.
- If a fractional solution is not implementable, its candidate-support columns are pairwise distinct and form an antichain under support inclusion.
- Identical fractional-candidate supports can be merged while preserving voter utilities and budget, reducing the number of fractional coordinates.
- Strict support inclusion contradicts Nash optimality because transferring mass increases some voters’ utilities without decreasing others.
- A nonzero null-space direction preserves utilities and can reduce fractionality, so the support matrix must have full column rank.
- The boundary cases with zero, one, or all-but-one fractional coordinates are already implementable by selecting suitable residual columns.
- Every fractional candidate has weight one, yielding positive coefficients satisfying A^Tα = 1.
B.2 Proof of the blocking-coalition inequalities
The section derives necessary inequalities for blocking coalitions by combining integral utility improvement with proportional-payment accounting. It then reduces the eight-row verification to finite polyhedral, endpoint, recession, and vertex checks whose exact certificates leave no unresolved region.
- Blocking-coalition inequalities: Proposition 15 derives necessary size and utility inequalities for any integral committee blocked by a voter coalition.The proof separates retained and newly selected candidates, then compares coalition payments and utilities with the proportional budget.
- Eight-voter bound: Lemma 18 strengthens these conditions for eight voters by imposing a lower bound on each coalition member’s payment share.The bound is used to establish positive price margins for coalitions of size at least two.
- Exact verification framework: Polyhedral reductions replace continuous verification with affine checks on closed floor polytopes, dual endpoints or recession directions, and vertex pairs.Full column rank leaves unique, one-dimensional, or two-dimensional price domains for eight, seven, and six fractional columns, respectively.
- Exact verification framework: The exact pipeline enumerates admissible residual matrices and nonimplementable floors, while soundness checks validate every retained certificate using rational arithmetic.Enumeration is complete up to relabeling, and exact filters reject only certified infeasible regions.
- Exact verification framework: The released failure files contain zero records, so every unresolved region is covered by an accepted certificate.This establishes the completeness of the finite verification for the classified cases.
B.4.2 Eight-row classification
The eight-row classification proves that every admissible residual region satisfies one of three exhaustive rounding or price-certificate alternatives. An exact computer-assisted census verifies all positive-dual full-column-rank antichains and leaves no counterexample.
- Classification alternatives: The multi-row alternative requires positive singleton margins and coalition implications for every selected row across the full floor and dual domains.The condition also requires the sum of the selected rows’ margins to remain positive.
- Computer-assisted proof: 1,085,483 unresolved regions were examined, with 1,085,459 receiving fixed certificates and 24 receiving adaptive certificates.The census is indexed by the number of fractional columns and covers the eight-row residual cases.
- Computer-assisted proof: No unresolved region remains after exact record-set comparison and the empty failure files.The verification uses exact domain reductions and proves that accepted certificates cover the complete unresolved set.
- Related classifications: The retained six-row classification independently verifies the smaller case but is not part of the logical dependency chain for the eight-row theorem.Its exact filtering found no counterexample among the final six-row regions.
B.5.2 Seven-row classification
The seven-row classification reduces all admissible cases to a small set of exceptional all-surplus regions after exact floor generation and filtering. Exact rational verification then certifies every remaining region without a counterexample.
- Classification: Lemma 31 states that every admissible seven-row region satisfies at least one of several rounding-certificate alternatives.The classification ranges over full-column-rank antichains with four to seven columns and nonempty dual domains.
- Exact reduction: 30,929 floor regions remain after complete generation and infeasibility filtering, with equality resolving all but 298 primitive all-surplus regions.Zero-row cases reduce immediately to the six-row classification.
- Exact reduction: 294 exceptional regions arise from square matrices with unique positive duals, while four arise from 7 × 6 matrices with line-segment dual domains.The differing matrix shapes determine the corresponding dual-domain verification.
- Verification: Exact rational verification certifies all 298 residual regions, and independent exact classifiers agree that no counterexample remains.The proof uses interval partitioning for rectangular dual domains and common-slack programs for possible boundary equalities.
B.6 Complexity of Floor-Preserving Rounding
The section proves that floor-preserving rounding is NP-complete by reducing Restricted Exact Cover by 3-Sets to committee selection. The reduction constructs a fractional Nash-core instance whose floor-preserving committees correspond exactly to exact covers, while clarifying that this hardness result does not settle discrete-core nonemptiness.
- Problem definition: Floor-Rounding asks whether an integral committee within budget preserves every voter’s utility floor induced by a fractional committee.The certificate is a committee satisfying the cardinality and floor inequalities.
- Reduction: The reduction from RXC3 creates one candidate and one private voter per triple, with each candidate selected fractionally at 1/3.Element voters approve the candidates corresponding to incident triples, while private voters approve their associated candidate.
- Reduction: The constructed approval matrix has full column rank and forms a binary antichain because each candidate has a private approval row.The identity block supplies full rank, and equal column sizes plus distinct private rows yield the antichain property.
- Nash-core construction: The fractional committee is a Nash-core pair, with element-voter utility 1, private-voter utility 1/3, and equal candidate weights.Concavity establishes Nash optimality, while proportional payments establish fractional-core membership.
- Hardness proof: A feasible floor-preserving committee exists exactly when the RXC3 instance has an exact cover, proving NP-hardness and, with polynomial verification, NP-completeness.Every selected triple must cover each element exactly once, and the constructed committee has the required budget.
- Scope: The result concerns preserving floors for a specified fractional core allocation and does not establish hardness of discrete-core nonemptiness.It also does not imply that a no-instance of Floor-Rounding has an empty discrete core.
Appendix C Further Experimental Details
The appendix provides iterative algorithms for computing fractional and weak Nash core solutions, with adaptive approximation parameters. It also introduces candidate capacities and outlines key update steps and inputs.
- Implementation: The heuristic-experiment code is publicly available in the paper’s linked GitHub repository.The repository contains the heuristic implementation referenced by the appendix.
- Algorithms: Both algorithms are iterative and terminate once an approximation solution is achieved, with parameters such as ϵ and η sometimes adapted in the code.Algorithm 1 computes the fractional Nash core solution, while Algorithm 2 computes the weak Nash core solution.
- Capacities: Candidate capacities hc represent identical copies and modify the Weight-selection Coupling condition from xc = 1 to xc = hc.The capacity adjustment is intended to better represent real voting data and reduce problem complexity.
- Inputs and outputs: The algorithms take n, m, k, voter approval sets, and candidate capacities as inputs, returning either a Nash Core or weak Nash core solution.The outputs are represented as (w, x).
- Update procedure: The computation initializes an integer vector x satisfying 0 ≤ x ≤ h and ||x||1 = k before applying iterative candidate-selection updates.Subsequent steps find candidates for which the update conditions apply, including reducing a selected xc′ by 1 when it maximizes the stated objective value.