Answer: Polynomial-time solvable: continuous NONDUMMY belongs to \(\mathrm{P}\).
Theorem 7 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe problem DUMMY is coNP-hard even if all weights in all component games are in {0, 1}, and G is an m- vector weighted voting game. PROOF. The reduction is from the classic NP-complete problem X3C (Exact Cover by 3-Sets) [8]. An instance of X3C is given by a ground set E = {e1, . . . , e3K }, and a system of subsets F = {S1, . . . , Sℓ}, where |Si| = 3, Si ⊆E for i = 1, . . . , ℓ. It is a “yes”-instance if E can be covered by K sets from F, i.e. there exists a set system F ′ ⊆F, |F| = K, such that for any e ∈E there exists an Si ∈F ′ such that e ∈Si, and a “no”-instance otherwise.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given supported types \(T\) with rational masses \(\mu_t\), nonnegative rational per-unit committee weights \(a_{tj}\), rational quotas \(q_j\), and a tested type \(t^\star\), decide whether there are coalition masses \(y_t\in[0,\mu_t]\) and some \(\delta>0\), with \(y_{t^\star}+\delta\le\mu_{t^\star}\), such that \(\sum_t a_{tj}y_t<q_j\) for at least one committee \(j\), while \(\sum_t a_{tj}(y_t+\delta\mathbf{1}[t=t^\star])\ge q_j\) for every committee.
A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_{t\in T}\mu_t=1\). Here \(\tau=|T|\) is the support size, not the number of possible types.
There are \(m\ge1\) committees. The input specifies binary-rational per-unit weights \(a_{tj}\ge0\), quotas \(q_j\in\mathbb Q\), and a tested type \(t^\star\in T\). Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
A coalition is a real mass vector \(y\) with \(0\le y_t\le\mu_t\). It wins precisely when \(\sum_{t\in T}a_{tj}y_t\ge q_j\) for every committee \(j\); equality counts as winning.
The continuous NONDUMMY problem asks whether there exist such a coalition \(y\) and a real \(\delta>0\) with \(y_{t^\star}+\delta\le\mu_{t^\star}\), such that \(\sum_{t\in T}a_{tj}y_t<q_j\) for at least one \(j\), while \(\sum_{t\in T}a_{tj}y_t+\delta a_{t^\star j}\ge q_j\) for every \(j\). The coalition may already contain mass of the tested type.
Is continuous NONDUMMY solvable in time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
For finite players and conjunctions of committee games, DUMMY is \(\mathrm{coNP}\)-hard even with weights in \(\{0,1\}\), and belongs to \(\mathrm{coNP}\); consequently NONDUMMY is \(\mathrm{NP}\)-complete. [Source](https://www.cs.ox.ac.uk/people/michael.wooldridge/pubs/aamas2009d.pdf)
No result settling this exact continuous problem was identified in the literature search.
Continuous NONDUMMY is solvable in time polynomial in \(m,\tau,L\). An algorithm uses at most \(m\) rational linear programs.
Write \(s=t^\star\), and define the committee scores
\(S_j(y)=\sum_{t\in T}a_{tj}y_t\).
Lemma. A NONDUMMY witness exists if and only if one exists with \(y_s=0\) and \(\delta=\mu_s\).
Proof. Suppose \((y,\delta)\) is a witness, and choose a committee \(k\) with \(S_k(y)<q_k\). Define \(x_t=y_t\) for \(t\ne s\), and \(x_s=0\).
Since every weight is nonnegative,
\(S_k(x)=S_k(y)-a_{sk}y_s\le S_k(y)<q_k\).
Thus \(x\) loses.
After adding the full tested mass, every committee \(j\) has score
\(S_j(x)+\mu_s a_{sj}=S_j(y)+(\mu_s-y_s)a_{sj}\).
The witness condition gives \(\mu_s-y_s\ge\delta\). Consequently,
\(S_j(x)+\mu_s a_{sj}\ge S_j(y)+\delta a_{sj}\ge q_j\).
Also, \(x\) respects all mass bounds, and \(\mu_s>0\). Therefore \((x,\mu_s)\) is a witness of the asserted form. The converse follows directly from the definition. \(\square\)
Define the polytope of winning coalitions containing the full tested mass:
\(F=\{z\in\mathbb R^T:0\le z_t\le\mu_t\text{ for every }t,\ z_s=\mu_s,\ S_j(z)\ge q_j\text{ for every }j\}\).
Its feasibility is easy to check. By nonnegativity, \(S_j(z)\le S_j(\mu)\) whenever \(0\le z\le\mu\). Hence:
Assume henceforth that \(F\) is nonempty. For each committee \(k\), solve the linear program
\(v_k=\min_{z\in F}\sum_{t\ne s}a_{tk}z_t\).
The minimum is attained: \(F\) is closed and bounded, and the objective is continuous.
Proposition. NONDUMMY holds exactly when \(v_k<q_k\) for at least one committee \(k\).
Proof, forward direction. By the lemma, take a witness \((x,\mu_s)\) with \(x_s=0\). Set \(z_t=x_t\) for \(t\ne s\) and \(z_s=\mu_s\). The post-addition coalition wins, so \(z\in F\). Since \(x\) loses, some committee \(k\) satisfies
\(\sum_{t\ne s}a_{tk}z_t=S_k(x)<q_k\).
Therefore \(v_k<q_k\).
Proof, reverse direction. Suppose \(v_k<q_k\), and let \(z\in F\) attain this minimum. Set \(x_t=z_t\) for \(t\ne s\) and \(x_s=0\). Then
\(S_k(x)=v_k<q_k\), so \(x\) loses. Adding \(\delta=\mu_s>0\) produces exactly \(z\), which wins. All mass bounds hold. Thus \((x,\mu_s)\) is a NONDUMMY witness. \(\square\)
The strict comparison matters: \(v_k=q_k\) does not establish a witness, because equality counts as winning.
The algorithm is:
The standard rational linear programming theorem provides a deterministic algorithm that detects infeasibility and, for a feasible program with finite optimum, computes an exact rational optimum in time polynomial in its dimensions and binary encoding length. Rational optimal solutions have polynomial encoding length, permitting exact comparison with a rational quota. See [Goemans’s linear programming notes, Sections 11–13](https://ocw.mit.edu/courses/6-854j-advanced-algorithms-fall-2008/908fe54d659623efadda2d033b895caf_notes_lp.pdf).
Here every program has:
In a dense matrix encoding, its bit length is \(O(L+\tau^2)\). The feasible region is nonempty after step 1 and bounded by the mass constraints, so every optimum is finite. The theorem applies even when this region has lower dimension.
Thus the total running time is \(m\cdot\operatorname{poly}(m,\tau,L)\) bit operations, including construction and exact comparisons. No enumeration of possible types is required: the variables correspond precisely to the \(\tau\) supported types.
The [finite-player hardness result](https://www.cs.ox.ac.uk/people/michael.wooldridge/pubs/aamas2009d.pdf) concerns indivisible coalition choices. Here coalition coordinates vary over real intervals, and the characterization above uses linear optimization over those intervals.
⟨structured verdict parsed — rendered above⟩
The argument resolves the intended continuous problem: its witness reduction and LP characterization are correct, and its running time is polynomial in \(m,\tau,L\). There is one minor wording issue in the statement about optimal-solution encoding length; no mathematical repair is needed.
The forward implication is valid.
\[
S_k(x)=S_k(y)-a_{sk}y_s\le S_k(y)<q_k.
\]
Thus removing the tested mass preserves a strictly losing committee.
\[
S_j(x)+\mu_s a_{sj}
=S_j(y)+(\mu_s-y_s)a_{sj}
\ge S_j(y)+\delta a_{sj}
\ge q_j.
\]
Each inequality uses an explicit hypothesis: the capacity condition, nonnegative weights, and the original witness’s post-addition winning condition.
The converse is immediate: the asserted canonical witness satisfies the original definition. The lemma covers coalitions that initially contain tested-type mass, as required.
The feasibility test is correct. Every admissible coalition satisfies \(z\le\mu\) coordinatewise, so nonnegative weights imply \(S_j(z)\le S_j(\mu)\).
Therefore, a grand-coalition score below its quota rules out every winning coalition and hence every NONDUMMY witness. Conversely, if all grand-coalition scores meet their quotas, \(\mu\) satisfies every defining constraint of \(F\).
No positivity assumption on quotas is used.
After the feasibility test succeeds, \(F\) is nonempty. Its finitely many non-strict linear constraints make it closed, and the mass bounds make it bounded. The linear objectives are continuous, so their minima are attained.
This reasoning remains valid when \(F\) has lower dimension or consists of one point.
Both directions are correct.
For the forward direction, the canonical witness produces \(z\in F\), and its losing committee supplies a feasible objective value strictly below the corresponding quota. Hence the minimum is also strictly below that quota.
For the reverse direction, an optimizer with \(v_k<q_k\) produces a coalition \(x\) with \(x_s=0\) that strictly loses committee \(k\). Adding \(\mu_s\) gives exactly the winning coalition \(z\). All capacity and positivity requirements are satisfied.
The existential quantifier over committees is handled correctly. Equality \(v_k=q_k\) does not qualify as a witness for that committee; another committee may still qualify.
The stated rational LP theorem is sufficiently precise for this application: deterministic polynomial time in dimensions and binary encoding length, with exact optimization for feasible programs having finite optimum. Here coefficients are rational, feasibility is established before optimization, and boundedness ensures finite optima. The cited notes discuss polynomial input/output sizes and polynomial-time LP algorithms in Sections 11–13. [Goemans’s linear programming notes](https://ocw.mit.edu/courses/6-854j-advanced-algorithms-fall-2008/908fe54d659623efadda2d033b895caf_notes_lp.pdf)
The constraint counts are correct: \(\tau\) variables, \(m+2\tau\) inequalities, and one equality.
The dense encoding bound \(O(L+\tau^2)\) is valid for the explicitly specified input: committee coefficients occupy input-sized space, while dense bound rows contribute \(O(\tau^2)\) constant-sized entries. Duplicated masses and objective coefficients contribute only \(O(L)\).
Exact grand-coalition score computation and rational comparisons require polynomial bit time. With at most \(m\) LP solves, the stated total bound \(m\cdot\operatorname{poly}(m,\tau,L)\) meets the task.
Minor issue — optimal-solution size wording. The sentence “Rational optimal solutions have polynomial encoding length” is too broad if interpreted universally. For example, the fixed LP minimizing zero on \([0,1]\) has rational optimal solutions \(2^{-N}\) with arbitrarily large encoding lengths. The needed statement concerns the existence of a polynomial-size rational optimum, or the optimum returned by the cited algorithm. This ambiguity does not invalidate the theorem application or the algorithm.
Minimum clarification: replace that sentence with an explicitly existential statement about a polynomial-size rational optimal solution.
The written argument handles nonpositive quotas, zero weights, zero tested-type weights, unattainable quotas, \(\tau=1\), \(m=1\), and equality at a quota without additional assumptions. Empty objective sums when \(\tau=1\) have their usual value zero.
The finite-player hardness comparison is contextual and is not used in the proof. The established result concerns precisely the supported continuous coordinates in the task.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.