Source-linked AI summary
Sparse Disapproval Guarantees a Nonempty Hare Core
Jiarui Fang
TL;DR
The paper addresses the open question of deterministic Hare-core nonemptiness for approval elections. It uses a complement-side missing-set rule that maximizes weighted coverage and then incidence, proving nonemptiness when each voter disapproves at most two candidates. The symbolic proof establishes the result for arbitrary positive rational weights and unbounded numbers of candidates, seats, and voter types, while finite verifiers provide audit evidence.
Problem
General deterministic Hare-core nonemptiness is open, despite existing results under bounded parameters or structured preference domains.
Method
The paper represents committees by missing sets, maximizing weighted coverage of two-candidate disapproval sets and then total disapproval incidence.
Results
For every m ≥ k ≥ 2, every approval election with |C \ A_i| ≤ 2 for every positive-weight voter has a nonempty Hare core.
Takeaways & Limitations
The complement-side coverage and tie-break mechanism makes co-rank-two core nonemptiness tractable across arbitrary candidate, seat, voter-type, and positive rational weight counts.
Takeaways & Limitations
The theorem does not cover voters disapproving three candidates, resolve co-rank-three, or imply unrestricted core nonemptiness.
Abstract
from arXiv · showhide
An approval committee is Hare-core stable if no coalition meeting the Hare quota can strictly improve by moving to another candidate set. Whether every approval election has such a committee remains open. We prove nonemptiness when each voter disapproves at most two candidates, with no bounds on the numbers of candidates, seats, or voter types. The result also permits arbitrary positive rational voter weights. Our deterministic rule represents a committee by its missing set. It first maximizes weighted coverage of two-candidate disapproval sets and then maximizes total disapproval incidence. An exact coverage inequality excludes targets one seat below the committee. The incidence objective excludes unanimous equal-size targets, while targets of size at most $k-2$ cannot improve any voter. Two implementation-level independent verifiers audit overlapping finite grids. The symbolic proof, not this bounded enumeration, establishes the theorem's unbounded quantifiers. The argument identifies complement-side coverage as a tractable mechanism for a broad parameter range within a sharply defined preference domain.
1 Introduction
The paper addresses the open question of deterministic Hare-core nonemptiness by proving it for approval elections where every voter disapproves at most two candidates, without bounds on candidates, seats, or voter types.
- General deterministic Hare-core nonemptiness remains open, despite results for bounded committee or candidate sizes, bounded voter types, and structured preferences.
- The restriction is |H_i| ≤ 2, unlike prior parameter and structural bounds.
- Each disapproval set is empty, a vertex, or an edge, turning missing-candidate selection into weighted vertex-edge coverage.
- The complement-side representation permits arbitrary numbers of candidates, seats, and voter types.
2 Selection rule and main theorem
The paper selects a committee through its missing set, maximizing weighted coverage and then disapproval incidence; every maximizing missing set yields a Hare-core committee.
- For m > k, the committee is represented by a size-s missing set B, where s = m − k.
- The rule lexicographically maximizes weighted coverage e(B) and total disapproval incidence j(B), then applies a fixed tie-break.
- For every m ≥ k ≥ 2, elections with |C \ A_i| ≤ 2 for every positive-weight voter have a nonempty Hare core.
- Every committee associated with an (e, j)-maximizing missing set is in the core, including the committee returned by the fixed tie-break.
- The rule is explicit and finite, but the paper does not claim a polynomial-time implementation.
3 Proof
The proof excludes blocking targets by size: targets at most k − 2 cannot improve any voter, targets of size k − 1 are controlled by coverage, and size-k targets by incidence tie-breaking.
- Targets of size at most k − 2: Targets larger than k cannot block because their Hare quota exceeds total voter weight; for T = C \ D, d = k − t and |D| = s + d.
- Targets of size at most k − 2: If d ≥ 2, each voter's gain is at most −d + |H_i| ≤ 0, so targets of size at most k − 2 cannot block.
- Targets of size k − 1: For d = 1, every gainer must be a two-disapproval voter whose disapproval pair lies entirely in D and avoids B.
- Targets of size k − 1: Averaging coverage over random size-s missing sets gives e(B) ≥ p_m,s w_2, placing every size-(k − 1) target's gainer weight strictly below its Hare quota.
- Targets of size k: For d = 0, any blocking target would require every positive-weight voter to gain; this implies e(D) ≥ e(B), contradicting coverage maximality or, under equality, j(D) > j(B), contradicting incidence tie-breaking.
4 Exact verification
Two independent verifiers audit overlapping finite grids, while the symbolic proof supplies the theorem's unbounded guarantees.
- The primary verifier checks 101,851 profile-parameter cases, 236,801 tied maximizers, and 12,020,946 literal committee-target inequalities.
- The independent verifier checks 106,620 profile-parameter cases, 265,371 tied maximizers, and 15,499,790 literal inequalities.
- Both implementations construct every tied maximizer rather than only one.
- The finite grids enumerate only stated small integer multiplicities and do not exhaust arbitrary rational weight denominators.
- Lemma 2 and the symbolic proof establish the unbounded quantifiers; the overlapping grids provide regression and falsification evidence only.
5 Scope and open boundary
The theorem applies to a sharply restricted preference domain and allows broad election features within that domain. It does not establish unrestricted core nonemptiness, and extending the mechanism beyond co-rank-two remains open.
- The theorem permits arbitrary positive rational weights, repeated ballots, unapproved candidates, and targets overlapping the committee.
- It excludes elections where a voter disapproves three candidates and does not resolve co-rank-three.
- The result does not imply unrestricted core nonemptiness or that dense approvals are empirically universal.
- Whether a higher-order objective can control deficit-one targets while preserving the equal-size tie-break remains open.
Reproducibility and AI assistance
The package supports exact replay and PDF building through a one-command workflow, while documenting AI assistance across development and manuscript preparation. The author states that they reviewed the work and take responsibility for its content.
- The package README provides a one-command exact replay and PDF build.
- GPT-5.6 Sol assisted proof exploration, verifier development, literature-query formulation, and manuscript preparation.
- The author reviewed the statements, proofs, citations, and executable artifacts and takes responsibility for the content.