| paper | On the Edge of Core (Non-)Emptiness: An Automated Reasoning Approach to Approval-Based Multi-Winner Voting |
| authors | Ratip Emin Berker, Emanuel Tewolde, Vincent Conitzer, Mingyu Guo, Marijn J. H. Heule, Lirong Xia |
| venue | AAAI 2026 |
| filed under | multiwinner · multiwinner |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: The decision problem is in \(\mathrm P\) under the stated explicit cost-table representation. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
Given candidates \(C\), committee size \(k\), approval types \(T\subseteq 2^C\), rational population distribution \(\mu\in\Delta_{\mathbb Q}(T)\), margin \(\delta>0\), and conversion costs \(\gamma(A,B)\), choose \(W\in\binom{C}{k}\) and a transport plan \(y_{A,B}\ge 0\) with \(\sum_B y_{A,B}=\mu_A\), inducing \(\nu_B=\sum_A y_{A,B}\), to minimize \(\sum_{A,B}\gamma(A,B)y_{A,B}\) subject to \(\sum_{B:\,|B\cap W'|>|B\cap W|}\nu_B\le |W'|/k-\delta\) for every \(\varnothing\ne W'\subseteq C\) with \(|W'|\le k\).
A type-level core-repair model: approval types carry population mass \(\mu_A\), transport variables move mass between types at costs \(\gamma(A,B)\), and the final distribution \(\nu\) must support a selected committee \(W\) against every proportional deviation.
The transport-and-repair objective is not the paper’s original adversarial search over vote distributions; it is a new intervention problem built on the paper’s core constraints.
fatal: False
The mirror covers Theorem 1 and the paper’s core-stability and least-core formulation, but leaves the duality results, Droop-core results, priceability counterexamples, and related axiomatic conclusions untouched.
The strongest honest positive case is a narrow one: the paper’s direct distributional formulation is already very close to a continuous-population model, so I would not present merely replacing its finite profile by \(\mu\) as a new mirror. The defensible mirror adds a genuinely population-level action: repairing a large approval electorate by moving mass between recurring approval types until a core-stable committee exists.
My lead anchor is the paper’s printed Theorem 1 (the theorem labelled milp), proved in this paper. For every admissible \(m,k\), it states that the optimal values of the paper’s max–min–max problem and its MILP formulation coincide; moreover, the optimal vote distributions \(\bfx^\star\) of the max–min–max problem are exactly the \(\bfx\)-components of optimal MILP solutions, and the MILP variable \(\mu^\star\) is the largest attainable value of the distribution’s sizewise-least core. In the underlying problem, the distribution chooses a society, the committee \(W\) is chosen adversarially, and a deviation \(W'\) is then chosen to maximize excess support over its proportional quota.
This is a formulation theorem rather than an NP-hardness or polynomial-time theorem. The paper does not itself prove a named \(P\), NP-hardness, W[1]-hardness, or FPT result; the NP-hardness of checking core stability is cited from elsewhere. I therefore would not mislabel that citation as an anchor.
The continuous problem I would propose is \(\delta\)-Core-Repair\(_\infty\). An instance consists of candidates \(C\), committee size \(k\), a finite set \(T\subseteq 2^C\) of approval types, a rational population distribution \(\mu\in\Delta_{\mathbb Q}(T)\), a rational safety margin \(\delta>0\), and conversion costs \(\gamma(A,B)\) for changing a unit of mass from approval type \(A\) to approval type \(B\). A solution chooses a committee \(W\in\binom{C}{k}\) and a transport plan \(y_{A,B}\ge 0\) satisfying \(\sum_B y_{A,B}=\mu_A\). The resulting population is \(\nu_B=\sum_A y_{A,B}\), and the objective is to minimize \(\sum_{A,B}\gamma(A,B)y_{A,B}\), subject to
\[ \sum_{\{B\in T:\ |B\cap W'|>|B\cap W|\}}\nu_B \leq \frac{|W'|}{k}-\delta \]
for every nonempty \(W'\subseteq C\) with \(|W'|\leq k\).
The output is therefore a committee, a final type distribution, and a minimum-cost mass transfer. With no permitted conversions, this reduces to finding the most robust core-stable committee for a given society. As \(\delta\) tends to zero, it recovers the paper’s strict core condition. The margin simply makes the optimization problem closed and finite-precision well defined.
The type interpretation is natural in a large public-project or federated-optimization setting. There may be millions of residents or clients but only \(\tau\) recurring approval profiles: for example, groups that approve the same facilities, objectives, or AI systems. Two agents are the same type when they have the same approval set and the same conversion-cost profile. Thus \(n\gg\tau\), and \(\mu_A\) is genuinely the fraction of the population of type \(A\), not an average over idiosyncratic named voters. The committee remains integral; only population mass and type-level campaigning are continuous.
The authors should recognize this as their problem rather than a weakened surrogate. The deviation family is unchanged: every subset \(W'\) of up to \(k\) candidates is still tested, and preference remains the paper’s strict approval-count comparison. The continuous part is only the population and the mass-transfer action. Theorem 1 supplies the exact excess-support expression and shows why the resulting fixed-population problem has the same linear structure that their MILP exploits.
I would expect the general problem to be Class B. Continuization removes dependence on the raw number of voters, but not the combinatorics of candidate subsets and deviations. A finite election embeds by setting \(\mu_A=n_A/n\); each type can also be replicated arbitrarily many times without changing the instance. Thus any hardness arising from candidate or deviation structure survives in a high-multiplicity population. For fixed \(m\), or whenever the deviation family has an efficient separation oracle, the fixed-\(W\) version becomes a linear program, suggesting a Class A regime. The central algorithmic question is precisely whether the deviation oracle
\[ \max_{W':\,1\leq |W'|\leq k} \left( \sum_{\{B:\ |B\cap W'|>|B\cap W|\}}\nu_B -\frac{|W'|}{k} \right) \]
can be solved efficiently for structured type families.
This mirror covers Theorem 1 and the paper’s core-stability computation. It does not claim to mirror the paper’s priceability counterexamples, PAV discussion, or Droop-core results, although the same question can be repeated with \(k+1\) in the quota and with additional priceability constraints.
The weakest point is also clear: the paper already treats vote distributions \(\bfx\) as an exact compression of finite profiles. A bare “continuous core non-emptiness” problem would therefore collide with the paper itself. The case survives only because \(\delta\)-Core-Repair\(_\infty\) makes the distribution an input society and introduces a type-level population action and cost objective. That is an extension of the paper’s computational core, not a claim that its existing MILP is novelly continuous. Further questions include fixed-\(\tau\) parameterized algorithms, approximation and finite-population rounding guarantees, and simultaneous repair to Droop core plus Lindahl or weak priceability.
I would reject the proposed mirror. The decisive problem is that the paper has already continuized its population, while its strongest named result is not a computational-complexity result.
Theorem 1 only proves equivalence between the paper’s max–min–max formulation and its MILP. It does not establish membership in \( \mathrm{P} \), hardness, approximation, parameterized tractability, or any other complexity classification. The cited NP-hardness of core checking belongs to external work. The remaining named results are distributional characterizations, non-emptiness theorems, or axiomatic counterexamples. Thus the paper supplies no qualifying computational anchor for ChoCo.
More fundamentally, the paper’s vote distribution is already exactly the continuous society in the programme’s sense. For an approval type \(A\subseteq C\),
\[ \mu_A=\frac{|\{i:A_i=A\}|}{n}, \]
and core stability is already expressed as
\[ \sum_{A:\,|A\cap W'|>|A\cap W|}\mu_A <\frac{|W'|}{k}. \]
The paper explicitly proves that the individual electorate can be replaced by these type masses without changing the core. Every rational \(\mu\) can be converted back into a finite profile by clearing denominators. This is not merely suggestive high multiplicity; it is the paper’s own exact model. A continuous core-existence, least-core, Droop-core, or priceability problem would therefore restate the paper rather than mirror it.
The proposed \(\delta\)-Core-Repair problem avoids that collision only by changing the problem. The paper chooses \(\mathbf{x}\) adversarially to find a worst profile; it does not receive a society \(\mu\) and modify it through a transport plan \(y\). Adding conversion costs, a repair objective, and a chosen final distribution creates a new continuous bribery or intervention problem. That may be a worthwhile project, but Theorem 1 supplies no result about it, and the authors do not study population repair. With no conversions it collapses back to the paper’s already-continuous problem; with conversions it is no longer a mirror of the paper’s contribution.
Unrestricted repair is also liable to become behaviorally artificial or degenerate. The all-approval type \(A=C\) never strictly prefers any deviation \(W'\) of size at most \(k\) to a \(k\)-committee \(W\), since \(|C\cap W'|\leq |C\cap W|=k\). Hence, whenever conversion to that type is permitted and affordable, the whole population can be made core-safe immediately. Preventing this requires substantive restrictions on which approvals can be changed, or on campaign budgets and directionality. Those restrictions would be the real research model, not a consequence of continuization.
The same objection defeats stronger alternatives. The lower-bound theorem, Droop corollary, dual formulation, and priceability counterexamples all already quantify over vote distributions. Replacing \(\mathbf{x}\) by \(\mu\) adds nothing; adding transport or repair adds a new problem without a paper-level computational anchor.
The negative case is not an impossibility proof: a carefully designed type-level campaigning model could be an interesting follow-on, especially with nontrivial restrictions and rounding questions. But it would be a new continuous-intervention programme inspired by this paper, not a worthwhile continuous mirror of any result the paper actually proves.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.