Answer: \(\mathrm{P}\) (polynomial-time solvable), including with unequal weights.
Theorem 9 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateIf n and m are not constant, the CHANCE- EVALUATION problem is NP-Complete for the Plurality voting protocol when not all the voters have equal weights.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), a target \(c^\star\), and types \(t\in T\) with rational masses \(\mu_t\), per-member weights \(w_t\), and distributions \(p_t\) over rankings, determine whether there are masses \(x_{t,\pi}\ge 0\), restricted to rankings with \(p_t(\pi)>0\), such that \(\sum_{\pi}x_{t,\pi}=\mu_t\) for each \(t\) and \(c^\star\)'s weighted Plurality score is at least every other candidate’s. The instance is the type list and its binary-rational data; report the complexity in \(|C|\), \(|T|\), the number of supported type-ranking pairs, and the input bit length.
Let \(C\) be a nonempty candidate set, \(m=|C|\), and \(c^\star\in C\). A society is given by its support: a nonempty list \(T\) of \(\tau=|T|\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). Here \(\tau\) counts supported types, not all possible types.
Each type has a positive binary-rational per-member weight \(w_t\) and an explicitly listed nonempty set \(S_t\) of strict complete rankings of \(C\), with positive binary-rational probabilities \(p_t(\pi)\) summing to \(1\); unlisted rankings have probability zero. Let \(q=\sum_t|S_t|\) and let \(L\) be the total input bit length.
A feasible allocation consists of real masses \(x_{t,\pi}\geq0\) for \(\pi\in S_t\), with \(\sum_{\pi\in S_t}x_{t,\pi}=\mu_t\). Probabilities restrict admissible rankings only; they do not prescribe allocated proportions. Under weighted Plurality, \(s_x(c)=\sum_t w_t\sum_{\pi\in S_t:\,\pi\text{ ranks }c\text{ first}}x_{t,\pi}\). Ties count as winning, corresponding to positive winning probability under uniform random tie-breaking.
Is deciding whether a feasible allocation satisfies \(s_x(c^\star)\geq s_x(c)\) for every \(c\in C\) in \(\mathrm{P}\), or is it NP-hard? State running times in \(m,\tau,q,L\).
For indivisible voters with explicitly supported uncertain rankings, this decision problem is strongly NP-complete with unequal weights and is in \(\mathrm{P}\) with equal weights. [Source](https://www.cs.ox.ac.uk/people/michael.wooldridge/pubs/aamas2008c.pdf)
No result settling exactly the divisible-mass problem above was identified in the literature search.
The decision problem is in \(\mathrm{P}\), including when the per-member weights are unequal. It reduces to one maximum-flow computation.
A conservative bound on the running time is
\[
\text{}
\]
\(O\!\left((m+\tau+1)(m+\tau+q)^2L^2\right)\)
bit operations. The algorithm can also construct a rational winning allocation whenever one exists.
We interpret the question as asking whether there exists a feasible allocation making \(c^\star\) a winner.
For each supported type \(t\), define
\(A_t=\{c\in C:\text{some }\pi\in S_t\text{ ranks }c\text{ first}\}\)
and \(a_t=w_t\mu_t\). Each \(A_t\) is nonempty.
Given a feasible allocation, let
\(y_{t,c}=w_t\sum_{\pi\in S_t:\,\pi\text{ ranks }c\text{ first}}x_{t,\pi}\)
for \(c\in A_t\). These quantities satisfy
\(y_{t,c}\geq0\), \(\sum_{c\in A_t}y_{t,c}=a_t\), and
\(s_x(c)=\sum_{t:\,c\in A_t}y_{t,c}\).
Conversely, suppose quantities \(y_{t,c}\) satisfy these nonnegativity and sum constraints. For each \(c\in A_t\), choose one ranking \(\pi_{t,c}\in S_t\) with \(c\) first. Assign
\(x_{t,\pi_{t,c}}=y_{t,c}/w_t\)
and assign zero to all other rankings. Rankings chosen for distinct first-ranked candidates are distinct. Consequently,
\(\sum_{\pi\in S_t}x_{t,\pi}=a_t/w_t=\mu_t\),
and the resulting scores are exactly the prescribed sums of the \(y_{t,c}\).
Thus the original problem is equivalent to distributing each type’s weighted mass \(a_t\) among candidates in \(A_t\). This uses \(w_t>0\) and unrestricted divisibility. The numerical probabilities impose no additional constraints under the stated model.
Define
\(H=\{t\in T:c^\star\in A_t\}\),
\(R=T\setminus H\), and
\(B=\sum_{t\in H}a_t\).
Lemma. A winning allocation exists if and only if one exists in which every type in \(H\) assigns all its mass to \(c^\star\). In such an allocation, the target’s score is \(B\).
Proof. Start with any winning allocation in the aggregated variables. For every \(t\in H\), replace its allocation by
\(y'_{t,c^\star}=a_t\)
and \(y'_{t,c}=0\) for all \(c\in A_t\setminus\{c^\star\}\). Leave types in \(R\) unchanged.
Each type still allocates precisely its weighted mass. The target’s score weakly increases, while every rival’s score weakly decreases. Therefore, for every rival \(c\),
\(s_{x'}(c^\star)\geq s_x(c^\star)\geq s_x(c)\geq s_{x'}(c)\).
The transformed allocation is winning, and its target score is \(B\). The reverse implication is immediate because the transformed allocations are a subset of feasible allocations. \(\square\)
It remains to distribute the weighted masses of types in \(R\) among their eligible rivals, giving each rival total score at most \(B\).
Construct a directed network with source \(u\), sink \(v\), one vertex for every type in \(R\), and one vertex for every candidate in \(C\setminus\{c^\star\}\). Its arcs and capacities are:
| Arc | Condition | Capacity |
|---|---|---|
| \(u\to t\) | \(t\in R\) | \(a_t\) |
| \(t\to c\) | \(t\in R,\ c\in A_t\) | \(a_t\) |
| \(c\to v\) | \(c\neq c^\star\) | \(B\) |
All capacities are finite, nonnegative rationals. Define \(F=\sum_{t\in R}a_t\). Accept precisely when the maximum-flow value equals \(F\).
Winning allocation implies a flow of value \(F\). By the lemma, take a winning allocation giving all types in \(H\) to the target. For each \(t\in R\), send \(a_t\) on \(u\to t\) and \(y_{t,c}\) on \(t\to c\). Send \(\sum_{t\in R:\,c\in A_t}y_{t,c}\) on \(c\to v\).
The type constraints give conservation at every type vertex. The definitions give conservation at every candidate vertex. Each type-to-candidate flow is at most \(a_t\), and each candidate-to-sink flow is at most \(B\), because the allocation is winning. The flow is therefore feasible and has value \(F\).
A flow of value \(F\) implies a winning allocation. The total capacity leaving the source is exactly \(F\). Hence a flow of value \(F\) saturates every arc \(u\to t\): the nonnegative unused capacities sum to zero.
Set \(y_{t,c}\) equal to the flow on \(t\to c\). Conservation at a type vertex gives
\(\sum_{c\in A_t}y_{t,c}=a_t\).
Conservation at a candidate vertex and the capacity of \(c\to v\) give
\(\sum_{t\in R:\,c\in A_t}y_{t,c}\leq B\).
Assign every type in \(H\) entirely to \(c^\star\). The target then has score \(B\), and every rival has score at most \(B\). Section 1 converts these quantities into an admissible ranking allocation. Ties are allowed, so this allocation is winning.
This proves the equivalence.
The boundary cases are included: if \(R\) is empty, then \(F=0\) and the answer is yes. In particular, this covers \(m=1\). If \(H\) is empty, then \(B=0\) while \(F>0\), so the answer is no.
Write \(r=|R|\) and \(e_A=\sum_{t\in R}|A_t|\). The network has
\(V=r+m+1\leq\tau+m+1\)
vertices and
\(E=r+e_A+m-1\leq\tau+q+m-1\)
arcs. The bound \(e_A\leq q\) holds because each distinct first-ranked candidate requires at least one explicitly supported ranking.
Edmonds–Karp computes a maximum flow using \(O(VE^2)\) elementary operations, independently of capacity magnitudes. Its hypotheses hold here: the network is finite, directed, and has nonnegative capacities. See [Goemans’s flow lecture notes, Section 4.3](https://math.mit.edu/~goemans/18453S17/flowscuts.pdf).
To implement this with exact integer arithmetic, write each product \(a_t=w_t\mu_t\) as \(n_t/d_t\), without requiring reduction, and let \(D=\prod_{t\in T}d_t\). Multiply all capacities and \(F\) by \(D\).
The sum of the denominator bit lengths used in these products is \(O(L)\), so \(D\) has \(O(L)\) bits. Each scaled quantity \(Da_t=n_t(D/d_t)\) also has \(O(L)\) bits. Summing at most \(\tau\) such quantities adds only \(O(\log\tau)\) bits, which is \(O(L)\). Thus all scaled capacities and the scaled acceptance threshold have \(O(L)\) bits.
Starting from zero flow, augmentations preserve integer flows. Individual arc flows and residual capacities remain bounded by the corresponding capacities, so their bit lengths remain \(O(L)\). Using elementary arithmetic, preprocessing takes \(O(\tau L^2)\) bit operations, and a conservative charge of \(O(L^2)\) per flow operation yields the stated overall bound:
\(O\!\left((m+\tau+1)(m+\tau+q)^2L^2\right)\).
Dividing an accepted integer flow by \(D\), then applying the construction in Section 1, produces a rational winning allocation with polynomial encoding length. No enumeration of unsupported types or unlisted rankings is required.
The cited paper proves hardness for unequal-weight indivisible voters and gives a flow algorithm for equal-weight voters in Theorems 9 and 10. Its hardness construction relies on each voter assigning its entire weight to one candidate. [Hazon et al., Sections 4.2](https://www.cs.ox.ac.uk/people/michael.wooldridge/pubs/aamas2008c.pdf).
Here, a type’s weighted mass may split across several candidates. The flow correspondence above establishes that such splits are valid allocations even with unequal weights. Therefore the divisible problem is polynomial-time solvable.
⟨structured verdict parsed — rendered above⟩
The prover resolves the intended existence question correctly: the divisible-mass problem is in \(\mathrm{P}\), including with unequal weights. The allocation equivalence, maximum-flow reduction, and stated conservative bit-complexity bound are sound. No substantive gaps or repairs are needed.
The prover explicitly interprets the task as asking whether there exists a feasible winning allocation. This matches the intended complexity question.
It correctly treats probabilities as support restrictions. The task imposes no requirement that allocated proportions equal the listed probabilities, so concentrating mass on selected supported rankings is admissible.
Both directions of the aggregation equivalence are valid.
This establishes equivalence, rather than merely a relaxation of the original problem.
The lemma is correct.
Moving all mass of each type in \(H\) to \(c^\star\) preserves every type’s mass constraint. It weakly increases the target’s score and weakly decreases every rival’s score. Thus every winning allocation can be transformed into the stated form while preserving winning.
After this transformation, the target’s score is exactly \(B\), and types in \(H\) contribute nothing to rivals. The remaining feasibility condition is therefore precisely the one stated for types in \(R\).
The network correctly represents the remaining allocation constraints.
Allocation to flow. The proposed flows satisfy conservation at type and candidate vertices. Nonnegativity and the type sum constraint ensure each type-to-candidate flow is at most \(a_t\). Winning ensures each candidate-to-sink flow is at most \(B\). The resulting flow has value \(F\).
Flow to allocation. There are no original arcs entering the source, and its total outgoing capacity is \(F\). A flow of value \(F\) consequently saturates every source-to-type arc. Conservation then supplies the required type sums, while candidate-to-sink capacities enforce rival scores at most \(B\). Section 1 supplies an admissible ranking allocation.
The use of non-strict inequalities correctly permits ties. Neither direction requires integrality of the original allocations.
The stated boundary cases are correct.
Candidates that never appear first also cause no difficulty: their scores are zero.
The counts
\[
V=r+m+1,\qquad E=r+e_A+m-1
\]
are correct. The bound \(e_A\leq q\) follows because each distinct eligible first-ranked candidate requires a distinct supported ranking within its type.
The cited Edmonds–Karp result gives \(O(VE^2)\) running time for shortest augmenting paths, independently of capacity magnitudes. The constructed network satisfies the required hypotheses: it is finite and directed, capacities are nonnegative, and zero is a feasible initial flow. The cited notes confirm the stated bound. [Goemans, Section 4.3](https://math.mit.edu/~goemans/18453S17/flowscuts.pdf).
The scaling argument is valid under the task’s explicit binary-rational encoding.
The denominator bit lengths of the products \(w_t\mu_t\), summed over types, are \(O(L)\). Consequently, \(D\), each scaled weighted mass, the scaled capacities, and the acceptance threshold have \(O(L)\) bits. Summing at most \(\tau\) terms adds only \(O(\log\tau)\) bits, which is absorbed by \(O(L)\).
Integer augmentations preserve integer flows. The reference to “corresponding capacities” is valid when understood as the capacities of the original arcs underlying the residual arcs; both forward and backward residual quantities remain bounded accordingly.
The preprocessing estimate and the conservative \(O(L^2)\) charge per flow operation support the claimed total bound:
\[
O\!\left((m+\tau+1)(m+\tau+q)^2L^2\right)
\]
bit operations. Reading the explicit input and constructing the network are also absorbed by this bound.
The rational allocation reconstruction has polynomial encoding length: the scaled flows, \(D\), and the input weights all have polynomial bit length.
The literature description is accurate. The cited paper’s Theorems 9 and 10 concern unequal-weight hardness and equal-weight polynomial solvability, respectively. Its hardness construction explicitly requires each voter’s weight to go entirely to one candidate. [Hazon et al., Section 4.2](https://www.cs.ox.ac.uk/people/michael.wooldridge/pubs/aamas2008c.pdf).
These results are contextual; the divisible result is established independently by the prover’s flow equivalence.
No actionable correction is required.
⟨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.