Source-linked AI summary
Exact Sizewise Least Cores for Candidate-Disjoint Approval Chains
Jiarui Fang
TL;DR
Core existence for arbitrary approval elections remains open, and qualitative nonemptiness on nested-chain domains does not quantify the best committee’s quota-shortfall margin. This paper factors deviation scores and computes exact chain values; its active-component guarantee is sharp, and negative margins certify nearby core-nonempty profiles.
Problem
The core is known to be nonempty on the restricted chain domain, but that qualitative result does not identify the committee maximizing the guaranteed quota shortfall.
Source: §1 · p. 1Method
The paper factors committee deviation scores across disjoint components and uses prefix-packed local tables with seat allocation to compute exact rational optima and committees.
Source: §1 · p. 2, §12 · p. 12Results
1/[k min{qact, k + 1}] is the optimal per-profile guarantee, with extremal profiles showing sharp dependence on the active-component count.
Source: §12 · p. 12Takeaways & Limitations
A negative margin certifies a neighborhood of core-nonempty profiles, including perturbations outside the chain domain.
Source: §12 · p. 12The closed formula does not apply to arbitrary candidate-interval profiles or overlapping components, and unrestricted core nonemptiness remains unsettled.
Source: §11 · pp. 11–12
Abstract
from arXiv · showhide
For approval-based committee elections, the sizewise least-core value $\Gamma(P)$ minimizes the maximum excess support of a deviation over size-$k$ committees. Deviations are nonempty and contain at most $k$ candidates, with support measured relative to their Hare quota. A negative value certifies core nonemptiness, while $-\Gamma(P)$ is the largest worst-case quota shortfall secured by any committee. We quantify this margin on candidate-disjoint approval chains, a domain whose qualitative core nonemptiness is already known. We first factor each committee's deviation score over disjoint components. For chains, a closed local table yields the exact value and an attaining committee in polynomial time for rational weights. For nonnegative normalized real weights, let $q_{\mathrm{act}}\ge1$ count the connected components of the positive-support incidence graph. Then \[ \Gamma(P)\le-\frac{1}{k\min\{q_{\mathrm{act}},k+1\}}. \] Explicit extremal profiles show that this dependence on the active-component count is sharp. The margin is $1$-Lipschitz in total variation on the full ballot space. Each negative margin therefore certifies a neighborhood with nonempty core, even when perturbations leave the chain domain.
1 Introduction
The paper quantifies the quota-shortfall margin on candidate-disjoint nested chains, beyond the known qualitative result that some committee is unblocked. It defines the deviation score and outlines exact computation and a stability certificate.
1 Introduction
- Exact tables turn qualitative core nonemptiness on nested chains into an optimal committee and a quantified quota-shortfall margin.The tables allocate seats across lists and compute the largest guaranteed gap below the Hare quota.Source: §1 · p. 1
- The total-variation certificate guarantees stability near chain profiles but is not claimed to equal the optimal distance to core emptiness.The intrinsic active-component count excludes empty ballots and unused candidates.Source: §1 · pp. 1–2
- Committee scores factor across disjoint components, while prefix-packed local tables and seat allocation yield the global optimum.The contribution also includes an order-statistic formula and heap reconstruction.Source: §1 · p. 2
- Rational arithmetic gives a polynomial-time algorithm, but no strong-polynomial bit bound is claimed.The computations are falsification and regression evidence; quantitative results are proved analytically.Source: §1 · p. 2
2 Model and coalition costs
- A size-k committee faces nonempty deviations of at most k candidates, which may overlap the committee.The deviation score is the strict supporters’ mass minus the deviation’s size divided by k.Source: §2 · p. 2
- A coalition blocks only with strict utility improvement, and support equal to the sizewise Hare quota suffices to block.A negative score −η means every deviation’s support falls short of quota by at least η.Source: §2 · p. 2
- For nonempty type sets, τ_W(S) is the minimum size of an admissible deviation that strictly improves every type in S.It is +∞ when no such deviation exists.Source: §2 · p. 2
3 Exact component factorization
The component reduction represents each committee through local scores on disjoint blocks, while respecting the global deviation-size cap. Its proof handles feasible local unions and the over-budget case separately.
3 Exact component factorization
- Declared blocks partition candidates and voter types so each type’s approvals stay within its candidate block.Null candidates remain assigned to blocks and count in local seat allocation.Source: §3 · p. 3
- For each committee, deviation scores factor through blockwise local scores, while deviations with no strict supporters score at most −1/k.The proof splits deviations by block and removes pieces without local supporters.Source: §3 · p. 3
- When selected local coalition costs sum to at most k, their minimum-cost deviations unite into a feasible global deviation.Selected coalition mass need not equal actual supporter mass; the latter is at least the selected mass.Source: §3 · p. 3
- When local costs exceed k, the proof does not claim their union is feasible and instead uses the k+1 threshold.The disjoint type blocks support the over-budget argument.Source: §3 · p. 3
4 Exact component dynamic programming
The component dynamic program minimizes the global bottleneck by combining local table values, with coordinatewise monotonicity ensuring local minima can be assembled into an attaining committee. A two-branch recurrence handles whether an all-nonpositive allocation exists or a positive local score is unavoidable.
4 Exact component dynamic programming
- Coordinatewise monotonicity lets independent local argmins attain all local table minima for a fixed seat allocation, yielding an attaining global committee.Theorem 2 then reduces the global optimization to minimization over seat allocations.Source: §4 · p. 4
- The recurrence first checks all-nonpositive allocations; when feasible, it returns the larger of the bottleneck and the −1/k baseline.If none exists, it computes the positive-score branch instead.Source: §4 · p. 4
- Each recurrence uses O(hk^2) exact transitions, and stored minimizing predecessors recover an allocation.A local argmin is stored with each table entry.Source: §4 · pp. 3–4
5 Closed local tables for chains
For nested approval chains, prefix committees minimize each local table entry, and the resulting closed local scores can be combined to select an optimal committee. The example shows how this yields a quantified quota shortfall beyond qualitative core existence.
5 Closed local tables for chains
- A prefix committee weakly Pareto-dominates every other local committee of the same size, so it minimizes the local deviation score.For each deviation, its strict supporters under the prefix committee are contained among those under any alternative committee.Source: §5 · p. 5
- When a component has no nonempty approval sets, every local table entry is −∞ because no type can strictly support a deviation.The closed table proof also covers components whose candidates are all saturated or padded.Source: §5 · p. 5
- For a supporter-bearing deviation from a size-s prefix committee, the minimum cost is s + 1, and support comes only from approval types larger than s.Taking s + 1 candidates from the smallest chain set larger than s attains the bound.Source: §5 · p. 5
- The example’s local tables are (0, −3/4, −∞) and (0, −1/2, −∞), producing the best value at allocation (1, 1).The corresponding attaining committee is {a, c}.Source: §5 · p. 5
- For allocations (2, 0), (1, 1), and (0, 2), W = {a, c} attains Γ(P) = −1/2, maximizing the guaranteed shortfall of deviation support below quota.The allocations have respective values 0, −1/2, and 0.Source: §5 · p. 5
6 Exact polynomial-time algorithm
The closed chain tables yield an exact polynomial-time algorithm for rationally weighted candidate-disjoint chain profiles, returning both the value and an attaining committee. A heap implementation reconstructs an optimal seat allocation from local transition sequences.
6 Exact polynomial-time algorithm
- For rationally weighted candidate-disjoint chain profiles, Γ(P) and an attaining committee are computable in polynomial time.Exact rational addition and comparison have polynomial bit complexity in the binary input length; strong polynomiality is not claimed.Source: §6 · p. 6
- Advancing the component with the largest current transition head for k iterations recovers an attaining seat allocation.The heap removes the k largest sequence members, leaving the threshold head.Source: §6 · p. 6
- After validation and preprocessing, the algorithm uses polynomial time in the explicit incidence encoding and binary weight length.The stated operation bound excludes validation, sorting, and duplicate merging.Source: §6 · p. 7
- For arbitrary supplied local tables, the two-branch dynamic program remains necessary because nonincreasing abstract tables may lack an all-nonpositive optimum.Source: §6 · p. 7
7 Optimal quantitative bound
The positive-support incidence graph defines an intrinsic count of active components, excluding zero-weight types, empty ballots, and unsupported candidates. That count controls a universal negative bound on the least-core value for nonnegative normalized chain profiles.
7 Optimal quantitative bound
- The positive-support incidence graph omits zero-weight types, positive-weight empty ballots, and candidates unsupported by positive nonempty types.Its component count is intrinsic: reassignment of inert records or null candidates does not change q_act.Source: §7 · p. 7
- Isolated candidates contribute seat capacity but not support geometry.Source: §7 · p. 7
- When q_act = 0, only zero-weight types can have nonempty approval, every deviation has supporter mass zero and score at most −1/k, and the no-support singleton baseline attains Γ(P) = −1/k.Source: §7 · p. 7
- The proof sets a local demand at −ε, bounds the total demand using normalized positive mass, and combines local witnesses padded to k candidates.The argument covers inert-only blocks and both q_act ≤ k + 1 and q_act > k + 1.Source: §7 · pp. 7–8
8 Sharpness and extremal profiles
The extremal value is sharp on varying-profile classes, with explicit profiles attaining or approaching it as the active-component count changes. Fixed-incidence equality has a sufficient witness condition, while negative margins also yield stability under perturbations beyond the chain domain.
Extremal witnesses
- For r=min{h,k+1}≥2, r positive-weight star components with candidate counts summing to k+1 attain equality; the r=1 case attains −1/k.Any size-k committee underallocates some component, while a corresponding seat allocation attains the matching value.Source: §8 · pp. 8–9
Fixed-profile boundaries
- For fixed blocks or incidence, equality follows if the subfamily contains a positive composition witness; this is sufficient, not a necessity classification.At m=k, the unique committee forces Γ=−1/k.Source: §8 · pp. 8–10
Exactly h active components
- For exactly h active components, the extremal value is −1/[k min{h,k+1}] when candidate count, blocks, incidence, and normalized weights may vary.The supremum is attained for h≤k+1; for h>k+1, the family approaches it, without asserting nonattainment in the full class.Source: §8 · p. 9
Extremal witnesses
- When h>k+1, k+1 principal singleton components plus ℓ=h−k−1 low-mass components approach the exact supremum −1/[k(k+1)].Every ballot is nonempty and positive, so the profile has exactly h support-active components.Source: §8 · p. 9
Stability
- Γ is 1-Lipschitz in total variation on the full ballot space, and a chain profile with qact≥1 retains nonempty core within radius 1/[k min{qact,k+1}].No optimality of this radius is asserted.Source: §8 · pp. 9–10
9 Candidate intervals and related work
The chain domain is a subclass of candidate-interval preferences, whose qualitative core nonemptiness was already known. The paper distinguishes its quantitative signed least-core results from existing interval, apportionment, and game-theoretic results.
Candidate intervals
- Ordering candidates by chain layers makes every approval set an interval in one global order, placing the chain domain inside candidate-interval preferences.Pierczyński and Skowron proved polynomial-time core nonemptiness for finite candidate-interval profiles; the qualitative result was already known for this domain.Source: §9 · p. 10
Related work
- Berker et al. already cover the equal-singleton outer-extremum endpoint and the m=k+1 upper side, but not the support-active refinement for arbitrary m.The cited apportionment and interval results address different models or objectives.Source: §9 · p. 10
- Existing knapsack recurrences and least-core methods for transferable-utility games do not establish the paper’s results for globally seat-capped approval deviations.The passage distinguishes their payoff variables and coalition structure from the local table, factorization, and active-component bound here.Source: §9 · p. 10
10 Exact regression checks
The three regression benchmarks attain the active-component bound, and two exact checkers provide complementary finite tests of the analytic results.
Regression checks
- Two independently implemented exact checkers test local tables, factorization, allocation procedures, extremal witnesses, and total-variation stability.They also cover boundary cases including empty ballots, zero weights, null candidates, and the deviation cap.Source: §10 · p. 11
Benchmark results
- All three regression benchmarks attain active-component bound (17), with exact values reported in Table 1.The passage describes these checks as regression evidence, not a replacement for the analytic proofs.Source: §10 · p. 11, Table 1 · p. 11
11 Limitations and the first non-chain fork
The exact chain analysis has limits beyond its stated domain, while Proposition 2 handles only a narrow first non-chain fork. The results do not settle unrestricted core nonemptiness or quantitatively solve all candidate-interval profiles.
11 Limitations and the first non-chain fork
- The closed formula requires prefix-dominance and does not cover overlapping components, signed weights, weak improvement, Droop quota, non-unit costs, or deviations larger than k.The fixed-candidate theorem does not resolve fixed incidence; when |C| = k, the value is −1/k.Source: §11 · p. 11
- With two one-candidate extensions of a common nonempty root, Proposition 2 proves the baseline value −1/k for every permitted committee size.For the intermediate case k = |R| + 1, selecting one branch makes only the other branch type able to improve, and its score is at most −1/k.Source: §11 · p. 11
- Proposition 2 does not cover arbitrary branch depths, overlaps, or additional incomparable sets, and the remaining fork project is unresolved.The results neither construct an empty-core election nor settle unrestricted core nonemptiness or quantitatively solve all candidate-interval profiles.Source: §11 · pp. 11–12
12 Conclusion
The paper gives an exact quantitative analysis on candidate-disjoint nested chains, with polynomial-time computation and a sharp active-component guarantee. Its appendices document proof dependencies and finite regression checks, while distinguishing those checks from analytic proof.
12 Conclusion
- The chain-domain analysis yields an exact rational optimum and committee in polynomial time, plus the per-profile guarantee and matching extremal results.Total-variation stability makes each negative margin certify a neighborhood of profiles with nonempty core.Source: §12 · p. 12
A Proof dependencies
- The proof dependency map traces the local table through the allocation results and active-component bounds, while identifying Proposition 2 as a separate boundary argument.Finite verification files document checks and their scopes.Source: A Proof dependencies · p. 12
B Exact regression data and reproduction
- All three benchmarks attain the active-component bound; their exact regression histograms and checker coverage are reported in the appendix.The benchmarks use integer margins M(W) = nkgp(W), with run-length encoding recording each value and multiplicity.Source: B Exact regression data and reproduction · p. 12, Table 2 · p. 12
Use of AI-assisted tools
- The author reports using GPT-5.6 Sol for exploratory proof search, prototyping, literature-query formulation, and manuscript revision, with final content reviewed by the author.Exact computational claims are accompanied by independently implemented verification code.Source: Use of AI-assisted tools · p. 13