Answer: \(\mathsf{P}\)
Theorem 6.5 — class: hardness
Given a finite type set \(T\) with rational masses \(\mu_t\) summing to \(1\), rational per-unit weights \(w_t\), rational prizes \(p_1\ge\cdots\ge p_k>0\), a type-symmetric tie rule, and a feasible anonymous current payoff rate \(r_t\), decide whether there exist \(i\in\{1,\ldots,k\}\) and a mass coalition \(y\in[0,\mu]\) such that \(R(y)=\sum_t r_ty_t<p_i\) and, under every measurable partition of the residual mass \(\mu-y\), \(y\), with weight \(W(y)=\sum_t w_ty_t\), ranks among the top \(i\) coalitions under that tie rule.
Definitions. An instance has a finite type set \(T\), binary-encoded rational data \(\mu_t\ge0\), \(a_t\), \(r_t\), and \(p_1\ge\cdots\ge p_k>0\), with \(\sum_t\mu_t=1\), and a finite adverse tie rule. For \(y\in[0,\mu]\), let \(W(y)=\sum_ta_ty_t\) and \(R(y)=\sum_tr_ty_t\).
A residual partition of \(\mu-y\) is any finite family of nonzero vectors \(z^j\in[0,\mu]\) with \(\sum_jz^j=\mu-y\). Rank \(y,z^1,\ldots,z^m\) by decreasing \(W\), resolving equalities by the given rule, with ties against \(y\) resolved adversely. Coalition \(y\) receives \(p_h\) if it has rank \(h\le k\), and otherwise receives \(0\).
Target. Is the continuous single-coalition-deviation problem—whether there exists \(y\ne0\) such that, for every residual partition, \(y\) receives some \(p_h>R(y)\)—in \(\mathsf{P}\), or is it \(\mathsf{NP}\)-hard?
Known results. For finite-player \(k\)-prize weighted voting games, deciding whether a given outcome admits a single-coalition deviation is \(\mathsf{NP}\)-hard. No result for the mass-distribution problem above was verified.
We use the standard convention that when \(y=\mu\), the residual partition is the empty family. Thus \(y\) is the unique coalition, has rank \(1\), and receives \(p_1\).
Fix a candidate coalition \(y\), and write
\[ x=\mu-y,\qquad b=W(y). \]
For a residual partition \(\mathcal Z=(z^1,\ldots,z^m)\), define
\[ N_y(\mathcal Z)=\left|\left\{j:W(z^j)\ge b\right\}\right|. \]
Because ties involving \(y\) are resolved adversely, every residual coalition with weight at least \(b\) is ranked ahead of \(y\), while every residual coalition of weight less than \(b\) is ranked behind \(y\). Hence the rank of \(y\) is exactly
\[ 1+N_y(\mathcal Z). \]
The tie rule between residual coalitions does not affect this number.
Define the positive residual weight
\[ P^+(x)=\sum_{t:a_t>0}a_tx_t. \]
This is not \(W(x)\): negative-weight residual mass can be isolated in losing coalitions and therefore does not reduce the adversary’s ability to create coalitions ahead of \(y\).
If \(x=0\), then \(y\) has rank \(1\).
If \(x\ne0\), the maximum possible number of residual coalitions ranked ahead of \(y\) is as follows.
\[ \left\lfloor\frac{P^+(x)}{b}\right\rfloor. \]
Suppose first that \(b>0\). Consider any residual partition and let \(J\) be the set of residual coalitions with \(W(z^j)\ge b\). Put \(q=|J|\) and \(s=\sum_{j\in J}z^j\). Since \(0\le s\le x\),
\[ qb\le\sum_{j\in J}W(z^j)=W(s) \le\sum_{t:a_t>0}a_ts_t \le P^+(x). \]
Therefore \(q\le\lfloor P^+(x)/b\rfloor\).
For the reverse inequality, let \(q=\lfloor P^+(x)/b\rfloor\). We construct \(q\) coordinatewise-disjoint vectors \(u^1,\ldots,u^q\), supported only on types with \(a_t>0\), such that \(W(u^i)=b\).
Indeed, whenever a nonnegative vector \(v\), supported on positive-weight types, satisfies \(W(v)\ge b\), one can choose \(u\le v\) with \(W(u)=b\): order the positive-weight coordinates, take their available masses until their accumulated weight first reaches \(b\), and take the necessary fractional amount of the last coordinate. This is possible because the masses are continuously divisible.
After constructing \(i-1\) such vectors, the remaining positive weight is at least
\[ P^+(x)-(i-1)b\ge(q-i+1)b\ge b. \]
Thus the construction continues through \(i=q\). The vectors \(u^1,\ldots,u^q\), together with the leftover vector \(x-\sum_i u^i\) when it is nonzero, form a residual partition. Each \(u^i\) is tied with \(y\) and is therefore ranked ahead of it. This proves the first case.
Now suppose \(b=0\). If \(x_t>0\) for some \(a_t\ge0\), then for every positive integer \(N\) we may split the mass \(x_t\) into \(N\) nonzero equal pieces. Each has weight \(a_tx_t/N\ge0=b\), so all \(N\) pieces are ranked ahead of \(y\). Hence the number is unbounded.
Conversely, if every residual type has strictly negative weight, then every nonzero residual coalition \(z\le x\) has \(W(z)<0=b\). Thus no residual coalition is ranked ahead of \(y\).
Finally, suppose \(b<0\) and \(x\ne0\). For every \(N\), partition \(x\) into \(N\) equal nonzero pieces \(x/N\). Since \(W(x)/N\) converges to \(0\), for all sufficiently large \(N\) one has
\[ W(x)/N>b. \]
Consequently, arbitrarily many residual coalitions can be ranked ahead of \(y\). This proves the lemma. \(\square\)
Suppose \(W(y)>0\), and let
\[ q(y)=\left\lfloor\frac{P^+(\mu-y)}{W(y)}\right\rfloor. \]
By Lemma 1, an adversarial partition can give \(y\) rank \(q(y)+1\), and no partition can give it a worse rank.
Since \(p_1\ge\cdots\ge p_k\), coalition \(y\) succeeds against every residual partition if and only if
\[ q(y)<k \quad\text{and}\quad R(y)<p_{q(y)+1}. \]
This condition has an equivalent formulation without a floor.
For \(W(y)>0\), coalition \(y\) succeeds if and only if there exists \(h\in\{1,\ldots,k\}\) such that
\[ P^+(\mu-y)<hW(y) \quad\text{and}\quad R(y)<p_h. \]
If \(y\) succeeds, set \(h=q(y)+1\). Then \(h\le k\), and the definition of the floor gives
\[ P^+(\mu-y)<hW(y). \]
Moreover, success for the partition attaining rank \(h\) gives \(R(y)<p_h\).
Conversely, suppose the two displayed inequalities hold for some \(h\). Then
\[ q(y)=\left\lfloor\frac{P^+(\mu-y)}{W(y)}\right\rfloor\le h-1. \]
Thus every residual partition gives \(y\) rank at most \(h\). At every such rank \(\ell\le h\), monotonicity of the prizes gives
\[ p_\ell\ge p_h>R(y). \]
Hence \(y\) succeeds against every partition. \(\square\)
For each fixed \(h\), the conditions in Lemma 2 form a system of strict rational linear inequalities:
\[ 0\le y_t\le\mu_t,\qquad W(y)>0,\qquad hW(y)-P^+(\mu-y)>0,\qquad p_h-R(y)>0. \]
The expression \(P^+(\mu-y)\) is linear because
\[ P^+(\mu-y)=\sum_{t:a_t>0}a_t(\mu_t-y_t), \]
and the set of indices with \(a_t>0\) is fixed by the input.
Assume \(y\ne\mu\) and \(W(y)=0\). By Lemma 1, \(y\) can succeed only if every residual type has strictly negative weight. Equivalently,
\[ y_t=\mu_t\qquad\text{for every }t\text{ with }a_t\ge0. \]
Under these equalities, every residual coalition has negative weight, so \(y\) always has rank \(1\). It succeeds exactly when \(R(y)<p_1\).
Thus successful zero-weight coalitions are characterized by the strict linear system
\[ 0\le y_t\le\mu_t,\qquad W(y)=0,\qquad y_t=\mu_t\ \text{for every }a_t\ge0,\qquad \sum_t y_t>0,\qquad p_1-R(y)>0. \]
The condition \(\sum_t y_t>0\) is equivalent to \(y\ne0\), because all coordinates are nonnegative.
The algorithm is:
Strict rational linear feasibility is decidable in polynomial time. Explicitly, for strict inequalities \(g_i(y)>0\), introduce a variable \(\delta\) and solve the rational linear program
\[ \max \delta \]
subject to
\[ g_i(y)\ge\delta\quad\text{for all }i,\qquad \delta\ge0, \]
together with the original non-strict constraints. The strict system is feasible exactly when this linear program is feasible with optimum strictly greater than \(0\). All variables \(y_t\) lie in the compact box \([0,\mu_t]\), so the relevant optima are finite. Exact rational linear programming and comparison of its rational optimum with \(0\) are polynomial-time operations.
There are \(k+1\) such linear programs, each with \(O(|T|)\) variables and constraints. Since the prize list is explicitly part of the input, this is polynomial in the binary input length.
Every successful coalition is covered:
Conversely, every coalition certified by one of Steps 1–3 succeeds by Lemmas 1 and 2.
Therefore the continuous single-coalition-deviation problem belongs to \(\mathsf{P}\). The finite-player \(\mathsf{NP}\)-hardness does not survive this formulation because continuous divisibility makes the adversary’s maximum number of qualifying residual coalitions depend only on the scalar positive residual weight \(P^+(\mu-y)\).
⟨structured verdict parsed — rendered above⟩
The prover correctly classifies the continuous problem as polynomial-time solvable. The worst-rank characterization is substantively correct, the reduction to finitely many rational linear-feasibility problems is valid, and the complexity analysis is adequate.
There are two minor presentation gaps in Lemma 1, neither requiring new mathematics. No major issue undermines the conclusion.
For a fixed \(y\), a residual coalition precedes \(y\) exactly when its weight is at least \(W(y)\), because ties involving \(y\) are resolved adversely. Thus the claimed rank formula \(1+N_y(\mathcal Z)\) is correct. The tie-breaking order among residual coalitions is irrelevant.
The treatment of \(y=\mu\) is also correct: the only residual partition is the empty family, so \(y\) has rank \(1\).
The upper bound is valid. For \(J\) the residual coalitions preceding \(y\), their sum \(s\) satisfies \(0\le s\le x\), and therefore
\( |J|W(y)\le W(s)\le P^+(x) \).
Discarding nonpositive coordinates can only increase \(W(s)\), so the second inequality is justified even when some \(a_t<0\).
The lower-bound construction also has the required substance. Continuous divisibility permits extracting vectors of weight exactly \(W(y)\) from the remaining positive-weight mass until \(\lfloor P^+(x)/W(y)\rfloor\) such vectors have been formed.
However, the vectors need not be “coordinatewise-disjoint” in the usual sense of having disjoint supports: a single sufficiently large positive-weight coordinate may have to be split among several vectors. What the construction establishes, and what the proof actually needs, is that their coordinatewise sum does not exceed \(x\). This should be stated accurately.
The leftover vector is valid when nonzero, and every constructed vector precedes \(y\) by adverse tie-breaking. The floor formula follows.
If some residual coordinate has \(a_t\ge0\), splitting its positive mass into arbitrarily many pieces indeed creates arbitrarily many coalitions of weight at least \(0\).
The write-up omits an explicit statement that residual mass outside that coordinate must also be placed into the partition. As written, the displayed pieces generally do not sum to all of \(x\). This is a routine completion of the partition and does not affect the qualifying pieces, but it should be mentioned for literal completeness.
If every coordinate present in the residual has strictly negative coefficient, every nonzero residual coalition has strictly negative weight. Hence no residual coalition precedes \(y\). This direction is correct.
For \(x\ne0\), the partition into \(N\) equal copies \(x/N\) is valid. Since \(W(x)/N\to0\) and \(W(y)<0\), sufficiently large \(N\) gives \(W(x)/N>W(y)\). Thus the number of preceding residual coalitions is unbounded. This is correct.
Calling this an unbounded “maximum” is mildly imprecise: there is no finite maximum, only arbitrarily large attainable values. The later argument uses the correct meaning.
For \(W(y)>0\), the worst attainable rank is \(q(y)+1\). Therefore universal success is equivalent to \(q(y)<k\) and \(R(y)<p_{q(y)+1}\).
Replacing the floor condition by the existence of \(h\) satisfying
\(P^+(\mu-y)<hW(y)\) and \(R(y)<p_h\)
is correct in both directions. Prize monotonicity is applied with the correct inequality direction.
For fixed \(h\), all constraints are rational linear inequalities because the positive-index set \(\{t:a_t>0\}\) is determined by the input. The condition \(W(y)>0\) automatically implies \(y\ne0\).
The zero-weight characterization is also correct: absence of any residual coordinate with nonnegative coefficient is equivalent to \(y_t=\mu_t\) for every \(a_t\ge0\). The constraint \(\sum_t y_t>0\) correctly enforces \(y\ne0\).
Although Section 4 initially assumes \(y\ne\mu\), its displayed system does not enforce that condition. This causes no algorithmic error: if it admits \(y=\mu\), that coalition genuinely succeeds and would already have been recognized by Step 1.
The common-slack-variable reduction correctly decides a finite system of strict rational linear inequalities. Compactness of \(0\le y\le\mu\) ensures the relevant objective is bounded and attained. Exact rational linear programming and comparison of the optimum with \(0\) are standard polynomial-time operations.
There are \(k\) positive-weight programs and one zero-weight program. Since all \(k\) prizes are explicitly encoded, iterating over \(h=1,\ldots,k\) is polynomial in the input length.
⟨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.