Core nonemptiness for approval-count committee elections: resolved historical question
LLM status Open unverified
D71 — Social Choice - Clubs - Committees - Associations Economics catalogue openaigpt 6 astra ultra 45% cataloguednot recordedOpenStatement
ID: GT-072. Category: Approval-based committee voting. Kind: S. Status: Resolved historical question; September 2026 preprint.
Definitions and mathematical statement
Let $N=\{1,\ldots,n\}$, $n\geq 1$, let $C$ be a finite nonempty candidate set, and let $1\leq k\leq |C|$ be an integer. Each voter $i$ approves a set $B_i\subseteq C$, and has utility \[ u_i(T)=|B_i\cap T|\qquad(T\subseteq C). \] A committee $W\subseteq C$, $|W|=k$, is core-stable if \[ \forall\,\varnothing\ne S\subseteq N\ \forall\,T\subseteq C\text{ with }|T|\leq \frac{|S|k}{n}\ \exists i\in S:\quad |B_i\cap W|\geq |B_i\cap T|. \] The proportional budget is rational; since $|T|$ is integral, its constraint is equivalent to $|T|\leq\lfloor |S|k/n\rfloor$.Historical question, resolved in the cited preprint.
For every $n,C,k$ and every approval profile $(B_i)_{i\in N}$, does a core-stable committee $W$ exist?Short English statement
The historical question asks whether every approval election can select a committee that no proportionally funded coalition can unanimously improve upon. [S3] reports a positive answer and polynomial-time computation in this domain.Variants and scope boundaries
All coalition members must strictly improve to block the committee. The deviating committee $T$ need not be disjoint from $W$, and need not be unanimously approved. Utilities count approved winners. They are neither arbitrary cardinal scores nor binary utilities of an entire committee. The case $k=0$ is trivial. A committee of size at most $k$ can be padded to exactly $k$: every voter's utility weakly increases, so padding cannot create a strict block. Thus ECON-007's at-most-budget formulation is the same existence question. Allowing weak improvement for everyone and strict improvement for one changes the blocking relation. [S3] also treats quotas $n/(k+1)<q\leq n/k$ and a strict Droop boundary convention; the weak boundary $q=n/(k+1)$ is not silently included. Non-unit costs, fractional committees and general cardinal scores require their own status evidence.Source relationship and status
[S1] explicitly posed general core nonemptiness in December 2025. [S2] subsequently established partial results while retaining the general question. [S3], posted on 10 September 2026, proves nonemptiness and supplies polynomial-time computation for the approval-count, unit-cost, Hare-quota domain defined above. Its source identity and theorem scope were checked for this update; this is a preprint resolution, not an independent verification of every proof step. The old open-status claim is withdrawn, and this entry is retained for historical traceability rather than counted as an unsolved conjecture. ECON-007 is consolidated here without adding a duplicate question. Entry game:GT-066 retains the counterexample to the different general-additive strengthening.References
[S1] Ratip Emin Berker, Emanuel Tewolde, Vincent Conitzer, Mingyu Guo, Marijn Heule, and Lirong Xia, On the Edge of Core (Non-)Emptiness: An Automated Reasoning Approach to Approval-Based Multi-Winner Voting, 2025; AAAI 2026; arXiv:2512.16895v1. https://arxiv.org/html/2512.16895v1. Locators: Section 2, Definition 2 (core stability); the introduction (general nonemptiness question).
[S2] Patrick Becker, Matthias Greger, and Dominik Peters, Core Existence in Approval-Based Committee Elections with up to Seven Voter Types, 2026, arXiv:2605.06194v2. https://arxiv.org/html/2605.06194v2. Locators: Section 2.1, Definition 2.1; Sections 1 and 9 (partial results and remaining general question).
[S3] Patrick Becker, Matthias Greger, and Dominik Peters, Existence of the Core in Approval-Based Committee Elections, 10 September 2026, arXiv:2609.11912v1; author preprint. https://arxiv.org/html/2609.11912v1. Locators: Section 3 (blocking definition), Theorem 6.1 and Section 7 (existence and computation). Resolving source for the historical main question; also supplied as [S2] in ECON-007.
Common conventions: Source mathematical conventions
Finite games. For a finite set $A$, $\Delta(A)$ is its probability simplex. Players choose independent mixed strategies in Nash equilibrium; correlation is allowed only when explicitly part of the solution concept. In a game with payoff functions $u_i$ and strategy profile $x$, an additive $\varepsilon$ Nash equilibrium satisfies \[ u_i(x)\geq u_i(x_i',x_{-i})-\varepsilon \quad\text{for every player $i$ and every admissible deviation $x_i'$}. \] For numerical approximation, payoffs are normalized as locally specified. An $\varepsilon$ payoff residual is distinct from distance at most $\varepsilon$ to the set of exact equilibria. Point convergence, convergence of empirical play, and convergence in distance to an equilibrium set are also distinct.
Computational representations. Unless stated otherwise, a complexity question takes rational data with binary encoding; polynomial time is measured in total bit length. A fixed-accuracy polynomial algorithm is not necessarily polynomial in $1/\varepsilon$, and neither is necessarily polynomial in $\log(1/\varepsilon)$. Succinct games and value, demand, or sampling oracles must declare their interfaces. Exact real solutions require an explicit representation; an unspecified list of arbitrary real numbers is not a finite computational output. A claimed algorithmic barrier is meaningful only for its specified model and reductions.
Dynamic games. Histories, information, observation, and allowable randomization are part of the model. A stationary strategy depends only on the current state; a positional strategy in a deterministic graph game chooses one action at each controlled vertex. Nash equilibrium at an initial state and equilibrium after every history are different requirements. An expectation of a pathwise $\liminf$ payoff, a $\liminf$ of expected averages, a limiting expected average, and a uniform finite-horizon equilibrium are different criteria. None is silently substituted for another.
Allocation and mechanisms. A complete allocation assigns every item exactly once unless otherwise stated. Zero-valued goods, negative values, capacity constraints, feasibility, lotteries, and copies of goods affect fairness definitions and are specified locally. Dominant-strategy incentive compatibility, Bayesian incentive compatibility, universal truthfulness, and truthfulness in expectation impose different inequalities. Whenever an objective ratio has zero denominator, its convention is stated or those instances are excluded.
Infinite-dimensional models. Expectations, integrals, stochastic equations, and optimization objectives require their local regularity, integrability, filtrations, and admissible domains. A backward--forward mean-field system is a boundary-value problem; it is not an initial-value semiflow without an additional construction. Long-time, large-population, and vanishing-noise limits require an order of limits and a convergence topology. If a minimum need not be attained, the objective is its infimum or supremum and the approximation requirement is stated separately.
Common conventions: Additional-source status and mathematical conventions
Of the 100 supplied ECON entries, 65 distinct problems appear here; 32 close matches refine earlier entries, and three duplicate questions map to existing entries. Appendix app:audited-crosswalk lists every destination. The attachment's P/R/S/U distinctions and source audits are retained. Its precise mathematical formalizations are editorial unless the individual audit says otherwise. Candidate subsidy targets ECON-004--006 retain their U flags; the resolved approval-core question ECON-007 updates OP-0202 above. The following supplied conventions govern both this part and the attributed ECON refinements elsewhere in the catalogue, subject to local restrictions.
Parameterized questions. A problem family lists inputs that must be fixed before an instance is evaluated: population, horizon, policies, information, data law, model class and welfare weights. These are required choices, not quantities the citations are assumed to specify. Undefined applications should not be treated as identified estimands.
Indices and integrability. Sets of agents, firms and regions are finite unless a population measure is explicitly used. $i,j$ index units, $r$ regions, $t$ dates and $h$ horizons. $\mathbb E$ and $\Pr$ refer to the declared population and law; $\mathbf1\{A\}$ is an indicator. Every displayed expectation and discounted sum needs existence in the stated domain. Infinite horizons use a discount in $(0,1)$ and a convergence condition; finite horizons may use discount one.
Optimization and existence. A displayed $\max$, $\min$, or $\arg\max$ is conditional on attainment. For finite feasible menus this is immediate; general spaces need continuity and compactness/coercivity or another existence argument. Without attainment, the target is the supremum/infimum and arbitrarily near-optimal feasible choices. $\inf\varnothing=+\infty$. Empty feasibility and an unidentified target are different issues.
Potential outcomes. $Y_i(z)$ is the outcome under a specified intervention, not the observed conditional mean among people choosing $z$. In binary comparisons $\Delta Y_i=Y_i(1)-Y_i(0)$. Specify assignment, treatment versions, compliance, information and observation horizon. Interference is allowed under a full policy vector; compressed exposure notation needs a justified mapping. No interference, consistency and overlap are substantive assumptions, not automatic consequences of notation.
Populations and observation. Fix baseline eligibility and population weights. Conditioning on post-policy employment, survival, relocation or program uptake can change the population being compared. Death is not ordinary loss to follow-up; outcomes truncated by death need a composite convention, joint survival target, or explicitly defined survivor stratum. Fertility-changing interventions need a population functional rather than an unexplained fixed descendant cohort. Measurement and missingness models must be supplied.
Identification. A structural model $m\in\mathcal M$ implies observable law $P_m$ and target $\theta(m)$. Identification means \[ P_{m_1}=P_{m_2}\ \Longrightarrow\ \theta(m_1)=\theta(m_2) \quad\text{for all }m_1,m_2\in\mathcal M . \] Without identification, the target is \[ \Theta(P;\mathcal M)=\{\theta(m):m\in\mathcal M,\ P_m=P\}. \] Writing $\theta(P)$ before establishing identification can hide incompatible latent models. Confidence sets additionally need a sampling law, confidence level, asymptotic sequence and uniformity class. Point identification, coverage and informative precision are separate properties.
Mediation. Total effects of randomized assignment are distinct from cross-world natural indirect effects. Belief/effort-channel effects require a meaningful mediator intervention and additional measurement, exclusion or mediation assumptions. Randomization of the initial policy alone does not supply those assumptions. Report bounds or interventional alternatives when the stronger target is unsupported.
Equilibrium. A counterfactual $W(z)$, $p(z)$, or $\mu_t^z$ requires individual optimization, feasibility, government/resource budgets, market clearing and state-transition laws. State equilibrium existence and selection, or report ranges over compatible equilibria. Initial-state integration includes subsequent endogenous transitions; current-state integration must use the policy-dependent distribution. Reduced-form invariance after policy is not assumed.
Welfare accounts. Scores, utility, health, dollars and ecological quantities require explicit conversion before addition. Fees, taxes, subsidies, wages and extortion payments are transfers between parties; distributional weights can make them welfare relevant, but their face value is not automatically a resource loss. State ownership, geographic boundaries, foreign-income weights and fiscal finance. Do not add profits to household welfare already including dividends, or count land capitalization and the underlying benefit twice. A benefit-cost expression must distinguish gross benefits from net welfare and subtract every real cost exactly once.
Derivatives and risk. Log derivatives require positive arguments; local responses require admissible perturbations and specified equilibrium branches. Differentiation under expectations needs regularity/domination, and boundaries may allow only one-sided derivatives. Risk uses a specified law; ambiguity uses a declared nonempty law set on a common history space. Adaptive policies must be nonanticipative. A robust criterion is an editorial choice unless attributed explicitly.
Scope overlaps. Allocation, collective choice, contracts, household bargaining and coordinated policy overlap economics with optimization and game theory. They are retained because they appeared in the original catalogue; no claim of a strictly game-theory-free selection is made.
Statement licence: CC-BY-4.0 · Source file
Contributions 1
GPT 6 Astra Ultra attempt on Econ-651
Core nonemptiness for approval-count committee elections: resolved historical question: a research attempt
Status and exact target
This entry concerns a historical existence question, not a currently open conjecture. Becker, Greger, and Peters' September 2026 preprint establishes existence and polynomial-time computation in the stated approval-count, unit-cost domain. The research attempt below checks the quantifiers, derives an exact blocking certificate, and proves existence constructively for disjoint approval groups. These calculations are not asserted to be new. They do not independently reproduce the full published argument. The unresolved label describes this attempt's incomplete independent proof of the general theorem; it does not reverse the catalogue's resolved status.Let $N$ contain $n$ voters, let $C$ contain $m$ candidates, and let the committee size be $k\leq m$. Voter $i$ approves $B_i$ and receives $u_i(W)=|B_i\cap W|$. A blocking coalition must strictly improve the utility of every member and purchase a committee $T$ satisfying $n|T|\leq k|S|$. This integer inequality is preferable to rounding a floating-point quota. The deviation can overlap the current committee. It can also give different approved candidates to different coalition members: requiring unanimous approval of every candidate would incorrectly weaken the blocking test.
An exact certificate eliminates coalition enumeration
For any candidate set $T$, define the set of all its strict beneficiaries, \[ G(T,W)=\{i\in N:|B_i\cap T|>|B_i\cap W|\}. \]Thus exact verification can enumerate $\sum_{t=1}^k\binom mt$ deviations instead of all pairs of deviations and coalitions. For each deviation, compute approval counts and the number of beneficiaries. This is an exponential algorithm in general, but it is an explicit finite procedure with a polynomial-size certificate of failure. Enumerating all $\binom mk$ committees as well gives an exhaustive construction method conditional on existence. It does not supply the source's polynomial-time construction, nor does merely failing to find a counterexample prove existence for unbounded profiles.
Formula (1) also handles repeated voter types exactly. If type $g$ has approval set $A_g$ and multiplicity $n_g$, then \[ |G(T,W)|=\sum_g n_g\, \mathbf 1\{|A_g\cap T|>|A_g\cap W|\}. \tag{2} \] One must preserve these multiplicities when compressing an election. Replacing every type by one voter generally changes proportional budgets and hence the core.
A complete constructive result for disjoint approval groups
Assume voters partition into groups $1,\ldots,r$; everyone in group $g$ approves exactly $C_g$, and these candidate sets are pairwise disjoint. Candidates outside their union may be approved by nobody. Set \[ q_g=\frac{k n_g}{n},\qquad \ell_g=\min\{|C_g|,\lfloor q_g\rfloor\}. \] Select $\ell_g$ candidates from every group and then fill the committee to size $k$ arbitrarily. This is feasible because $\sum_g\ell_g\leq\sum_g q_g=k$ and $m\geq k$. Write $w_g=|W\cap C_g|$ for the resulting representation.For example, consider $n=10$, $k=4$, and three groups of sizes $5,3,2$, each having at least four distinct candidates. The lower quotas are $(2,1,0)$. A committee with counts $(2,1,1)$ is stable: strictly improving a group requires respectively at least $3,2,2$ candidates, whereas the proportional budgets of those full groups are $2,1.2,0.8$. Combining groups cannot repair the strict budget deficit because their candidate requirements add. In overlapping profiles a candidate can serve several groups, so this additive proof stops working. That is a specific obstruction to extending the construction, not an asserted counterexample to the general theorem.
Boundary checks and what the general result adds
Padding a stable committee of size at most $k$ cannot create a block. Indeed, if $W\subseteq W'$ and a coalition strictly prefers $T$ to $W'$, then it strictly prefers $T$ to $W$, while affordability is unchanged. This proves the equivalence of the at-most-budget and exact-size existence formulations when sufficiently many candidates are available. For $k=1$, any nonempty deviation needs all $n$ voters to fund it. A single candidate with maximum approval count is stable: a blocking candidate would be approved by everyone while the incumbent was approved by nobody, contradicting maximality. This argument includes the case where every approval set is empty, in which no strict improvement exists.The resolving preprint's Theorem 6.1 establishes a stronger core-plus property through a harmonic-entropy objective, including the Hare quota $q=n/k$ and quotas $n/(k+1)<q\leq n/k$. Section 7 gives a polynomial-time algorithm. Those inspected statements directly cover the historical question here. The lower endpoint requires the source's separate strict boundary convention; it cannot be inserted into the displayed open interval. General additive utilities and non-unit candidate costs are outside the theorem just cited.
There is a useful distinction between a verifier and a construction potential. Equation (1) gives an exact ordinary-core test by enumeration. It does not imply that maximizing total approval score, a familiar harmonic score, or an arbitrary local-search objective reaches the core. A general existence proof needs a specific link between every possible coalitional block and an improving move in its chosen potential. The published proof supplies such additional structure; it is not obtained from the disjoint-group calculation alone.
Completion Estimate
45%This is a post hoc, heuristic estimate for the full catalogue target. The attempt derives an exact blocking certificate and proves core existence constructively for disjoint approval groups, including quota and padding checks. The historical general theorem is correctly credited to a resolving preprint, but this attempt lacks an independent general proof and its polynomial-time construction.
Outcome and source
The independent results here are the exact certificate, the multiplicity reduction, the boundary arguments, and a full existence proof in the disjoint-group subclass. General existence and polynomial computation are credited to the resolving source. No new unresolved question is substituted for the historical target, and no original solution claim is made on the basis of its citation.Patrick Becker, Matthias Greger, and Dominik Peters, Existence of the Core in Approval-Based Committee Elections, arXiv:2609.11912v1, 10 September 2026. Inspected locators: Section 3, Theorem 6.1, and Section 7. https://arxiv.org/html/2609.11912v1.