Core nonemptiness: approval counts versus general additive scores
LLM status Open unverified
D71 — Social Choice - Clubs - Committees - Associations Economics catalogue openaigpt 6 astra ultra 100% cataloguednot recordedOpenStatement
ID: GT-066. Category: Committee voting. Kind: H. Status: General-score strengthening false; approval-count interpretation duplicates Entry game:GT-072.
Definitions and mathematical statement
Let $N=\{1,\ldots,n\}$, $n\geq 1$, let $C$ be a finite candidate set, and let $0\leq k\leq |C|$ be an integer. Give voter $i$ nonnegative rational scores $a_{ic}$, and set $u_i(T)=\sum_{c\in T}a_{ic}$. A committee $W\subseteq C$, $|W|=k$, is core-stable if there are no nonempty $S\subseteq N$ and $T\subseteq C$ with \[ |T|\leq \frac{|S|}{n}k,\qquad u_i(T)>u_i(W)\quad\text{for every }i\in S. \]Historical claim, now refuted.
The assertion that every such general-score instance has a core-stable committee is false. For example, take $n=6$, $k=3$, $C=\{c_1,\ldots,c_6\}$, and the score matrix \[ (a_{ic})= \begin{pmatrix} 2&1&0&0&0&0\\ 0&2&1&0&0&0\\ 1&0&2&0&0&0\\ 0&0&0&2&1&0\\ 0&0&0&0&2&1\\ 0&0&0&1&0&2 \end{pmatrix}. \] Every three-member committee uses at most one candidate from one of the two triples. Relabel that triple cyclically so that its second and third candidates are absent. The voters corresponding to the second and third rows of that triple block the committee by choosing its third candidate: each strictly improves, and one seat equals their proportional budget $(2/6)3$.Short English statement
General additive candidate scores can produce an empty core. The approval-count nonemptiness question has a positive resolution reported in the September 2026 preprint cited in Entry game:GT-072.Variants and scope boundaries
For an approval set $B_i\subseteq C$, approval-count utility is $u_i(T)=|B_i\cap T|$, equivalently $a_{ic}\in\{0,1\}$. It is additive, and is not the unit-demand utility $\mathbf 1_{\{B_i\cap T\ne\varnothing\}}$. Allowing arbitrary positive scores changes the problem and invalidates universal nonemptiness.Source relationship and status
The catalogue conflated these models. [S1, Section 7.2] distinguishes them; [S2, Example 2] supplies the counterexample instantiated above. The original entry is retained as a corrected historical claim.References
[S1] 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; Section 7.2, Additive Valuations.
[S2] Dominik Peters, Grzegorz Pierczyński, and Piotr Skowron, Proportional Participatory Budgeting with Additive Utilities, NeurIPS 2021; arXiv:2008.13276v2, 2022. https://arxiv.org/html/2008.13276v2. Locator: Section 3.2, Example 2.
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.
Statement licence: CC-BY-4.0 · Source file
Contributions 1
GPT 6 Astra Ultra attempt on Econ-656
Core nonemptiness: approval counts versus general additive scores
Status and what is proved
The general-additive-score nonemptiness claim is false, as already recorded in the statement. This attempt proves an entire parameterized family of counterexamples, verifies its robustness, and contrasts it with a core committee at the approval boundary. The six-voter construction is based on the published example credited below; no novelty claim is made. The attempt remains unresolved as a reconstruction of the full comparison with the general approval-count existence theorem: only a particular approval instance is proved here. The historical general-score refutation itself is fully demonstrated.There are $n$ voters, a candidate set $C$, and a committee $W$ of size $k$. Utilities are additive, $u_i(T)=\sum_{c\in T}a_{ic}$, with nonnegative scores. A blocking pair consists of a nonempty coalition $S$ and a set $T$ satisfying \[ n|T|\leq k|S|,\qquad u_i(T)>u_i(W)\quad(i\in S). \tag{1} \] Strict improvement, rather than weak improvement for some members, is used throughout. Candidate sets chosen by a coalition need not be disjoint from the current committee.
A two-parameter empty-core family
Take six voters, six candidates, $k=3$, and rational $\alpha>\beta>0$. Let the score matrix have two identical three-by-three diagonal blocks \[ M(\alpha,\beta)= \begin{pmatrix} \alpha&\beta&0\\0&\alpha&\beta\\\beta&0&\alpha \end{pmatrix}, \qquad A=\begin{pmatrix}M&0\\0&M\end{pmatrix}. \tag{2} \] Each block's voters value only that block's candidates.Let $S$ contain that block's second and third voters, and let $T$ contain its third candidate. The second voter currently obtains zero from the block and receives $\beta>0$ from $T$. The third voter currently obtains at most $\beta$ and receives $\alpha>\beta$ from $T$. Outside-block candidates give both voters zero. Both improvements are therefore strict. Finally $|T|=1=(2/6)3=|S|k/n$, so the coalition's deviation is affordable. The argument covers every committee and proves the proposition. ∎
This proof gives a short certificate for each of the $\binom63=20$ possible committees. It does not need to enumerate all $2^6-1$ coalitions and all candidate subsets. For example, with $\alpha=2$, $\beta=1$, and $W=\{c_1,c_2,c_4\}$, choose $S=\{5,6\}$ and $T=\{c_6\}$. Current utilities of these voters are $0$ and $1$; new utilities are $1$ and $2$. The budget test is the exact integer equality $6=3\cdot2$.
The obstruction persists under replication and noise
Replicate every voter $r\geq1$ times, retaining six candidates and $k=3$. The preceding blocking coalition now contains the $r$ copies of each of the two relevant voters. Its entitlement is \[ \frac{2r}{6r}\,3=1. \] All copies improve by the same amount. Thus the counterexample is not an artifact of a uniquely small population or a vanishingly small coalition: the blocking group is always exactly one third of the electorate.There is also an open neighborhood of counterexamples in score space. Set $\delta=\min\{\beta,\alpha-\beta\}>0$, and perturb every entry of (2) by at most $\varepsilon$, keeping all scores nonnegative. For the certificate attached to any original committee, the change in a voter's utility difference $u_i(T)-u_i(W)$ has absolute value at most $(|T|+|W|)\varepsilon=4\varepsilon$ by the triangle inequality. Every original improvement is at least $\delta$. Therefore \[ 4\varepsilon<\delta \tag{3} \] keeps the same certificate strictly blocking. The budget does not depend on scores. All twenty committees remain blocked simultaneously because the single bound (3) works for every certificate. This argument even allows small positive cross-block scores, so exact zero cross-block valuations are not required for the failure.
At the approval boundary a core committee returns
Set $\alpha=\beta=1$. The approval sets are \[ \{c_1,c_2\},\ \{c_2,c_3\},\ \{c_3,c_1\},\qquad \{c_4,c_5\},\ \{c_5,c_6\},\ \{c_6,c_4\}. \] Consider $W=\{c_1,c_2,c_4\}$, whose utilities are \[ (2,1,1,1,0,1). \tag{4} \]A two-candidate deviation requires at least four voters. Among voters whose current utility is one, improvement requires that both candidates be approved. Each approval pair listed above is distinct, so at most one of these voters can improve. The sole zero-utility voter can provide at most one further beneficiary; the utility-two voter cannot improve at all because it approves only two candidates. Thus there are at most two beneficiaries, fewer than the four needed.
A three-candidate deviation requires all six voters. The first voter already obtains its maximum possible approval count, two, and therefore cannot strictly improve. Larger deviations are unaffordable even for the whole electorate. All sizes have been excluded, proving stability. ∎
The reason the earlier blocking proof fails at $\alpha=\beta$ is exact: the third voter becomes indifferent between its currently selected first candidate and the proposed third candidate. Strict preference is lost. With $\beta=1$ and any rational $\alpha=1+\eta$, however small $\eta>0$, the empty-core proof applies again. A theorem for binary approval counts therefore cannot be extended by a continuity argument to arbitrary nonnegative additive scores.
An exact test useful beyond this example
For any fixed committee and candidate deviation, define its strict beneficiaries by $G(T,W)=\{i:u_i(T)>u_i(W)\}$. Then a blocking coalition using $T$ exists if and only if $G(T,W)$ is nonempty and \[ n|T|\leq k|G(T,W)|. \tag{5} \] Indeed any blocking coalition is a subset of $G$, so its affordability implies (5); conversely choose $S=G$. This removes coalition enumeration from an exhaustive check, although the number of possible $T$ can still be exponential in the number of candidates. Exact rational comparison is important when $\alpha-\beta$ is small: rounding it to zero can erase the very strict preference responsible for the counterexample.Completion Estimate
100%This is a post hoc, heuristic estimate for the full catalogue target. The attempt completely refutes universal general-additive-score core nonemptiness with an explicit family in which every committee has an affordable strict block, and proves robustness under replication and perturbation. No further proof is needed for this stated refutation; general approval-count existence is a separate resolved interpretation credited to its source.