Answer: Every valid instance admits a rational stable allocation, constructible in time polynomial in \(m,\tau,L\). The decision problem is in \(\mathrm{P}\).
Proposition 3 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateA strong equilibrium exists in any instance of the vot- ing game with players’ preferences in L(M) and F=Antiplurality.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a candidate set \(M\), a tie-break order \(\triangleright\), and a binary-rational distribution \(\mu\) over a finite support \(T\) of strict rankings, is there a rational allocation \(q_{t,a}\ge 0\), with \(\sum_{a\in M}q_{t,a}=\mu_t\), such that no positive-mass coalition whose members all prefer some \(y\) to the current winner \(w\) can reassign its veto ballots to make \(y\) the tie-broken minimum-veto winner? If so, construct such an allocation.
Let \(M\) contain \(m\ge 2\) candidates, with a fixed strict tie-break order \(\triangleright\). A society is given by its support: a list \(T\) of \(\tau\) strict ranking types \(\succ_t\), each with positive binary-rational mass \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings; \(L\) is the total input bit length.
An allocation consists of rational masses \(q_{t,a}\ge 0\) with \(\sum_a q_{t,a}=\mu_t\). Each individual casts one veto; these masses describe a divisible population's deterministic ballots. Write \(V_a(q)=\sum_t q_{t,a}\); the winner \(w(q)\) is the first candidate in \(\triangleright\) among those minimizing \(V_a(q)\).
A coalition selects real masses \(0\le c_{t,a}\le q_{t,a}\) with \(\sum_{t,a}c_{t,a}>0\), and replaces them by real masses \(r_{t,a}\ge 0\) satisfying \(\sum_a r_{t,a}=\sum_a c_{t,a}\) for every \(t\). Its resulting allocation is \(q'=q-c+r\); all outside ballots remain fixed. It improves if \(y=w(q')\) satisfies \(y\succ_t w(q)\) for every type with \(\sum_a c_{t,a}>0\). Call \(q\) stable if no such coalition improves.
Is deciding whether a rational stable allocation exists in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? Can such an allocation be constructed whenever one exists in time polynomial in \(m,\tau,L\)?
For finitely many voters with strict preferences and fixed priority tie-breaking, veto always admits a strong equilibrium, constructible in polynomial time in the explicit input size. [Discrete result](https://pdfs.semanticscholar.org/6021/3ee1b7993e4326437fa344eb7c69fe076f86.pdf)
No published result settling this exact divisible-population problem was identified in the literature search.
Every valid instance admits a rational stable allocation. Such an allocation can be constructed in time polynomial in \(m,\tau,L\). Thus the decision problem is in \(\mathrm{P}\).
The construction compresses the feasible-elimination approach underlying the discrete result in [Proposition 3 of Gourvès, Lesca, and Wilczynski](https://pdfs.semanticscholar.org/6021/3ee1b7993e4326437fa344eb7c69fe076f86.pdf). Below, we prove the elimination procedure directly and establish stability against arbitrary real-valued coalition deviations.
Let \(p\) denote the first candidate in \(\triangleright\).
For any allocation of total mass \(1\), a winning candidate has veto mass at most \(1/m\), because the minimum of the \(m\) veto masses is at most their average.
Moreover, a candidate \(y\ne p\) can win only if its veto mass is strictly less than \(1/m\). Indeed, if \(y\) won with veto mass \(1/m\), every candidate would have veto mass at least \(1/m\). Since the masses sum to \(1\), all would equal \(1/m\), and tie-breaking would elect \(p\).
Consequently:
These thresholds apply equally to rational and real allocations.
Choose a positive integer \(D\) such that \(D\mu_t\) is integral for every \(t\). For example, take the product of the denominators in the input.
Set \(N=mD\), and represent type \(t\)'s mass by the integer \(n_t=N\mu_t\). Then \(\sum_t n_t=N\). These units are only a device for constructing the allocation; deviations will remain unrestricted real masses.
Define integer elimination thresholds by
\(\beta_p=D+1,\qquad \beta_a=D\text{ for }a\ne p.\)
Thus \(\sum_{a\in M}\beta_a=N+1\).
We will assign exactly \(\beta_a\) veto units to every eliminated candidate \(a\), using only units whose type ranks \(a\) last among the candidates still present.
Initially, let \(S=M\), and let the remaining count of each type be \(n_t\). Maintain the invariant
\(\sum_{a\in S}\beta_a=n+1,\)
where \(n\) is the total remaining count.
Suppose \(|S|\ge2\). Each remaining type has a unique least-preferred candidate in \(S\), because preferences are strict. Let \(b_a\) be the total remaining count whose least-preferred candidate in \(S\) is \(a\). Then
\(\sum_{a\in S}b_a=n.\)
There must be some \(a\in S\) with \(b_a\ge\beta_a\). Otherwise, integrality would give \(b_a\le\beta_a-1\) for every \(a\in S\), and hence
\(n=\sum_{a\in S}b_a\le\sum_{a\in S}(\beta_a-1)=n+1-|S|\le n-1,\)
a contradiction.
Choose such an \(a\). Extract exactly \(\beta_a\) units from the types currently ranking \(a\) last in \(S\), assign those units to veto \(a\), and remove them from the remaining counts. Remove \(a\) from \(S\).
Extraction is possible because \(b_a\ge\beta_a\): traverse the eligible types, taking the smaller of their remaining count and the still-needed amount. All counts remain integers. Both sides of the invariant decrease by \(\beta_a\), so the invariant persists.
Repeat until only one candidate \(w\) remains. At that point, the invariant gives a remaining count of \(\beta_w-1\). Assign all these remaining units to veto \(w\).
Finally, divide every assigned count by \(N\), obtaining \(q_{t,a}\). Every initial unit has been assigned exactly once, so
\(q_{t,a}\ge0,\qquad \sum_a q_{t,a}=\mu_t.\)
Thus \(q\) is a rational allocation.
Every eliminated candidate \(a\ne w\) receives veto mass \(\beta_a/N\), while \(w\) receives \((\beta_w-1)/N\).
There are two cases.
If \(w=p\): every candidate receives veto mass \(D/N=1/m\). Tie-breaking elects \(p=w\).
If \(w\ne p\): the veto masses are
\(V_w(q)=\frac{D-1}{N}=\frac1m-\frac1N,\qquad V_p(q)=\frac{D+1}{N}=\frac1m+\frac1N,\)
and
\(V_a(q)=\frac DN=\frac1m\quad\text{for }a\notin\{w,p\}.\)
Therefore \(w\) has strictly the smallest veto mass and wins.
In both cases, \(w(q)=w\).
The construction has the following protection property:
For every losing candidate \(y\ne w\), if \(q_{t,y}>0\), then \(w\succ_t y\).
To prove this, observe that every unit assigned to veto \(y\) was extracted when \(y\) was least preferred among the then-remaining candidates. The eventual survivor \(w\) was still present. Strict preferences therefore imply \(w\succ_t y\).
Now suppose a coalition improves from \(w\) to some \(y\ne w\), using real masses \(c_{t,a}\) and \(r_{t,a}\).
Any participating type must satisfy \(y\succ_t w\). By the protection property, such a type has \(q_{t,y}=0\), and hence \(c_{t,y}=0\). Every nonparticipating type also has \(c_{t,y}=0\). Consequently, the coalition withdraws no veto mass from \(y\), and
\(V_y(q')=V_y(q)+\sum_t r_{t,y}\ge V_y(q).\)
If \(y=p\), then \(w\ne p\), so \(V_y(q')\ge 1/m+1/N>1/m\). Section 1 shows that \(p\) cannot win.
If \(y\ne p\), then \(V_y(q')\ge1/m\). Again by Section 1, \(y\) cannot win.
Both cases contradict the proposed improvement. Therefore \(q\) is stable. This argument imposes no integrality or rationality restriction on the coalition.
The product \(D\) of the input denominators has bit length \(O(L)\), even though its numerical value may be large. Hence \(N=mD\) has bit length \(O(L+\log m)\).
All remaining counts, assigned counts, and thresholds are integers bounded by \(N\). There are exactly \(m-1\) elimination steps. Scanning each ranking at every step to find its least-preferred remaining candidate uses \(O(\tau m^2)\) elementary operations; aggregation and extraction also take polynomial time. All arithmetic uses integers of polynomial bit length.
The output contains \(\tau m\) rational entries, each expressible with denominator \(N\) and numerator bounded by \(N\). Its total encoding length is polynomial in \(m,\tau,L\).
Thus the algorithm constructs a rational stable allocation for every valid input in polynomial time, without expanding the society into an explicit electorate.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output establishes that every valid instance admits a rational stable allocation and gives a construction polynomial in \(m,\tau,L\). No major or minor mathematical issues were found.
Total veto mass is \(1\), so the minimum veto mass is at most \(1/m\). If a winner has veto mass exactly \(1/m\), every candidate must have that mass, and priority elects \(p\). Thus the stated blocking thresholds correctly distinguish \(p\) from all other candidates. This reasoning applies to real allocations as well as rational ones.
Taking \(D\) as the product of the encoded denominators makes every \(D\mu_t\), and hence every \(n_t=mD\mu_t\), integral. The identities
\(N=mD\), \(\sum_t n_t=N\), and \(\sum_a\beta_a=N+1\) are correct. All thresholds are positive.
The invariant holds initially. Strict preferences give each remaining type a unique least-preferred candidate in the nonempty set \(S\), so the counts \(b_a\) partition all remaining units.
If every \(b_a<\beta_a\), integrality yields
\(n\le n+1-|S|\le n-1\) whenever \(|S|\ge2\), a contradiction. Therefore an eligible candidate always exists. The described extraction assigns exactly its threshold without making any type’s remaining count negative. Removing that candidate and those units preserves the invariant.
Each iteration removes one candidate, so termination occurs after exactly \(m-1\) eliminations.
At termination, the remaining count is \(\beta_w-1\), which is nonnegative. Assigning it to \(w\) accounts for every initial unit exactly once. Division by \(N\) therefore produces nonnegative rational entries with the required type totals.
A zero remaining count is permitted by the allocation definition and does not invalidate this step.
If \(w=p\), every candidate receives \(D/N=1/m\), so priority elects \(w\). If \(w\ne p\), the survivor receives \((D-1)/N\), priority candidate \(p\) receives \((D+1)/N\), and every other candidate receives \(D/N\). These values make \(w\) the unique minimum. The formulas remain valid when \(D=1\).
Every positive allocation to an eliminated candidate \(y\) comes from a type ranking \(y\) last among the candidates present at its elimination. The eventual survivor \(w\) is present then. Strict preferences consequently imply \(w\succ_t y\). This establishes the property for every losing candidate and every type with \(q_{t,y}>0\).
Any improving coalition must elect some \(y\ne w\), and each participating type must satisfy \(y\succ_t w\). The protection property then forces \(q_{t,y}=0\) for every participating type, hence \(c_{t,y}=0\). For a nonparticipating type, nonnegativity and \(\sum_a c_{t,a}=0\) likewise force \(c_{t,y}=0\).
Thus no coalition can withdraw any existing veto mass from its proposed winner. The displayed inequality \(V_y(q')\ge V_y(q)\) follows directly from nonnegative replacement masses. The deviation constraints also preserve nonnegativity and total mass \(1\), so the universal thresholds remain applicable.
If \(y=p\), its retained veto mass exceeds \(1/m\). Otherwise, its retained veto mass is at least \(1/m\). Both cases prevent \(y\) from winning. The argument covers arbitrary real selections and replacements; it does not assume coalition integrality.
Under the task’s binary encoding of rational masses, the product of the denominators has bit length \(O(L)\), and \(N\) has bit length \(O(L+\log m)\). Counts and thresholds are bounded by \(N\); in particular, \(D+1\le mD\) because \(m\ge2\) and \(D\ge1\).
Scanning all rankings at each elimination takes \(O(\tau m^2)\) elementary operations. Aggregation, extraction, and initial scaling use polynomially many operations on integers of polynomial bit length. The algorithm never enumerates the \(N\) units individually. Its \(\tau m\) output entries also have polynomial total encoding length.
[Proposition 3 of the cited paper](https://pdfs.semanticscholar.org/6021/3ee1b7993e4326437fa344eb7c69fe076f86.pdf) uses the indicated feasible-elimination approach for discrete antiplurality. The submitted continuous argument proves its own progress and stability claims directly, so it does not depend on transferring a discrete theorem to real coalitions.
Required repair or clarification: none. The existence, construction, and decision claims are all established.
⟨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.