Answer: Polynomial-time solvable in \(m,\tau,L\), with at most \(m\) greedy updates.
Theorem 4 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateGiven an election E = (N, P, (A(i))i∈N, b, cost) and an outcome (W, X) ∈WX =(E), Algorithm 1 outputs (W ∗, X∗) ∈WX ∗(E) by performing at most |{p ∈P : π(p, X∗) < π(p, X)}| = O(m) update steps; each update step can be completed in time O(n log n + nm).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite project set \(P\), rational per-capita costs \(c_p>0\), per-capita budget \(B\), and rational masses \(\mu_A>0\) over approval types \(A\subseteq P\) summing to \(1\), compute a stable equal-shares state in time polynomial in \(m,\tau,L\). A state consists of an integral project set \(W\subseteq P\) and payer-type sets \(S_p\subseteq\{A:p\in A\}\); project \(p\in W\) has payer mass \(\sigma_p=\sum_{A\in S_p}\mu_A>0\) and per-capita price \(\pi_p=c_p/\sigma_p\), with each type’s total price at most \(B\). For type \(A\), let \(\ell_A=\sum_{p:A\in S_p}\pi_p\) and let \(z_A\) be its highest paid project price, or \(0\) if it pays for none. The state is unstable if some project \(p\) and set of approving types \(R\) have mass \(s=\sum_{A\in R}\mu_A>\sigma_p\), with every \(A\in R\) able to afford \(c_p/s\) either from unused budget, \(c_p/s\le B-\ell_A\), or by shifting away from a more expensive project, \(c_p/s<z_A\). Starting from the empty state or a feasible state of this form, find a stable state using greedy updates and the paper’s project-removal rule.
Let \(P\) be a set of \(m\) projects, with binary-rational costs \(c_p>0\) and budget \(B>0\). A society is given by its support \(\mathcal T\): the list of \(\tau\) distinct approval types \(A\subseteq P\) with positive binary-rational masses \(\mu_A\), summing to \(1\). Every project has positive approving mass. Here \(\tau\) is the support size, not the number of possible approval sets; \(L\) is the total input bit length, including any initial state.
An equal-shares state consists of an integral set \(W\subseteq P\) and nonempty payer sets \(S_p\subseteq\{A\in\mathcal T:p\in A\}\) for \(p\in W\). Set \(\sigma_p=\sum_{A\in S_p}\mu_A\), \(\pi_p=c_p/\sigma_p\), and \(\ell_A=\sum_{p\in W:A\in S_p}\pi_p\le B\). For \(p\notin W\), set \(S_p=\varnothing\), \(\sigma_p=0\), and \(\pi_p=+\infty\). Types participate with their entire mass; splitting a type is disallowed. Let \(z_A\) be its highest paid price, or \(0\) if it pays for nothing.
An instability witness is a project \(p\in P\) and approving-type set \(R\) with \(s=\sum_{A\in R}\mu_A>\sigma_p\), such that every \(A\in R\) satisfies \(c_p/s\le B-\ell_A\) or \(c_p/s<z_A\). A state is stable if no witness exists; selected projects are also tested.
A greedy update chooses a witness minimizing \(r=c_p/s\). For each \(A\in R\setminus S_p\) with \(r>B-\ell_A\), mark one highest-price project it currently pays for. Remove every marked project entirely, replace \(S_p\) by \(R\), and select \(p\); retain all other payer sets. Fix a project order to resolve equal update prices and equal highest paid prices; equal-price witnesses for the same project may be chosen arbitrarily.
Starting from the empty state or any supplied feasible equal-shares state, is computing a stable state reachable by these greedy updates possible in time polynomial in \(m,\tau,L\), or is this computational problem NP-hard?
For explicitly listed discrete voters, AMES reaches a stable equal-shares state from any feasible equal-shares state in \(O(m)\) greedy updates, each taking \(O(n\log n+nm)\) arithmetic operations. [Kraiczy and Elkind](https://arxiv.org/pdf/2310.10215).
No result settling this exact support-encoded mass problem was identified in the literature search.
Theorem. From the empty state or any supplied feasible equal-shares state, a stable state reachable by the prescribed greedy updates can be computed in time polynomial in \(m,\tau,L\). Every greedy execution performs at most \(m\) updates. Each update, including finding a minimum-price witness, can be implemented using \(O(\tau\log\tau+m\tau)\) exact rational arithmetic operations, with polynomially bounded bit lengths.
The proof has two parts: minimum-price witnesses can be found by scanning prefixes of an ordered list of types, and successive greedy update prices cannot decrease.
The convergence argument follows the strategy of Lemma 2 and Proposition 2 in [Kraiczy and Elkind](https://arxiv.org/pdf/2310.10215). Below, all statements needed for the indivisible, rational-mass setting are proved directly.
If \(m=0\), the empty state is already stable. Henceforth assume \(m\ge 1\).
Fix a feasible state \(X\). Write \(f_A=B-\ell_A\) for type \(A\)’s remaining budget. Define its willingness predicate at a positive price \(t\) by
\(A\in E_X(t)\quad\Longleftrightarrow\quad t\le f_A\ \text{or}\ t<z_A.\)
For a project \(p\), write
\(E_{X,p}(t)=\{A\in E_X(t):p\in A\}.\)
Also define \(\mu(R)=\sum_{A\in R}\mu_A\).
Willingness is downward closed in price: if \(0<t'\le t\) and \(A\in E_X(t)\), then \(A\in E_X(t')\). Indeed, \(t\le f_A\) implies \(t'\le f_A\), while \(t<z_A\) implies \(t'<z_A\).
We call a nonempty approving-type set \(R\) admissible for \(p\) if
\(R\subseteq E_{X,p}\bigl(c_p/\mu(R)\bigr).\)
Thus an admissible set is an instability witness precisely when \(\mu(R)>\sigma_p\).
Let \(R\) be admissible for \(p\), put \(t=c_p/\mu(R)\), and set \(Q=E_{X,p}(t)\). Then \(Q\) is admissible and \(\mu(Q)\ge\mu(R)\).
Proof. Admissibility gives \(R\subseteq Q\), so \(Q\) is nonempty and \(\mu(Q)\ge\mu(R)\). Consequently,
\(c_p/\mu(Q)\le c_p/\mu(R)=t.\)
Every member of \(Q\) is willing at \(t\), and hence, by downward closure, at \(c_p/\mu(Q)\). Therefore \(Q\) is admissible. \(\square\)
This is the property that avoids a subset-sum search: adding willing types makes the price smaller and preserves their willingness.
The strict inequality involving \(z_A\) requires careful treatment of endpoints. Define
\(h_A=\max\{f_A,z_A\},\qquad e_A=\begin{cases}1,&f_A\ge z_A,\\0,&f_A<z_A.\end{cases}\)
The willingness predicate is exactly
\(A\in E_X(t)\quad\Longleftrightarrow\quad t<h_A\ \text{or}\ (t=h_A\ \text{and}\ e_A=1).\)
To verify this, if \(f_A\ge z_A\), willingness is equivalent to \(t\le f_A=h_A\). If \(z_A>f_A\), willingness is equivalent to \(t<z_A=h_A\).
Order all types by decreasing \(h_A\), putting types with \(e_A=1\) before types with \(e_A=0\) when their \(h_A\) values agree. Break any remaining ties arbitrarily. For every positive \(t\), \(E_X(t)\) is a prefix of this order: it contains all types with \(h_A>t\), followed by exactly the types with \(h_A=t\) and \(e_A=1\).
For a project \(p\), restrict this order to its approving types, obtaining
\(A_1,\ldots,A_k.\)
Each \(E_{X,p}(t)\) is a prefix of this restricted order. For each nonempty prefix, define
\(R_j=\{A_1,\ldots,A_j\},\qquad s_j=\sum_{i=1}^{j}\mu_{A_i},\qquad t_j=c_p/s_j.\)
The prefix \(R_j\) is admissible if and only if its last member is willing at \(t_j\), that is,
\(t_j\le f_{A_j}\quad\text{or}\quad t_j<z_{A_j}.\)
Indeed, the willing approving types form a prefix, so willingness of \(A_j\) implies willingness of all preceding members. The converse follows immediately from admissibility.
If admissible sets for \(p\) exist, let \(j^*\) be the largest index whose prefix is admissible. Then \(R_{j^*}\) has maximum mass among all admissible sets for \(p\).
Proof. Take any admissible set \(R\). By Lemma 1, the set
\(Q=E_{X,p}\bigl(c_p/\mu(R)\bigr)\)
is an admissible prefix with \(\mu(Q)\ge\mu(R)\). Write \(Q=R_j\). The definition of \(j^*\) gives \(j\le j^*\). Since every type has positive mass, prefix masses strictly increase with the index. Hence
\(\mu(R)\le s_j\le s_{j^*}.\)
This proves the claim. It also shows that if no admissible prefix exists, no admissible set exists. \(\square\)
Therefore the witness search for \(p\) consists of scanning all its prefixes and retaining the largest admissible one. There is no need to assume that admissibility is monotone in the prefix index.
If its mass exceeds \(\sigma_p\), it is a witness of minimum possible price, because \(c_p/s\) strictly decreases with \(s>0\). If its mass does not exceed \(\sigma_p\), no witness for \(p\) exists.
In fact, the maximum-mass admissible set is unique. If \(R\) has maximum admissible mass, Lemma 1 and positivity of the masses force
\(R=E_{X,p}\bigl(c_p/\mu(R)\bigr).\)
All maximum-mass sets have the same price, and the right-hand side is determined by that price.
The ordering is shared by all projects. Computing the state quantities and sorting the types takes \(O(m\tau+\tau\log\tau)\) arithmetic operations and comparisons. Scanning the restricted lists for all projects takes \(O(m\tau)\) more. Comparing their minimum-price witnesses and applying the fixed project order therefore finds a prescribed greedy update within the claimed bound.
Consider an update of project \(p\) using witness \(R\), at price \(r=c_p/\mu(R)\).
Since \(\mu(R)>\sigma_p\), if \(p\) was selected, then
\(r<\pi_p.\)
The same comparison holds with the convention \(\pi_p=+\infty\) when \(p\) was unselected.
Let \(D\) be the set of marked projects. Every \(q\in D\) has old price strictly greater than \(r\). To see this, a project is marked by a type \(A\in R\setminus S_p\) for which \(r>f_A\). The witness condition then forces \(r<z_A\), and the marked project has price \(z_A\).
Also, \(p\notin D\): each marking type lies outside \(S_p\), so it does not currently pay for \(p\).
We check every type’s new load.
The new payer set of \(p\) is nonempty, consists of approving types, and has mass \(\mu(R)\), so it funds \(p\) exactly at price \(r\). Every other retained project keeps its payer set and price. Hence the resulting state is feasible and equal-shares.
The ordinary total budget constraint also follows from the type loads:
\(\sum_{q\in W'}c_q=\sum_{A\in\mathcal T}\mu_A\ell'_A\le B\sum_{A\in\mathcal T}\mu_A=B.\)
Suppose an update at price \(r\) changes state \(X\) to \(X'\). For every \(0<t<r\),
\(E_{X'}(t)\subseteq E_X(t).\)
Proof. Consider a type \(A\notin E_X(t)\). Its old quantities satisfy
\(f_A<t,\qquad z_A\le t.\)
It cannot belong to the update witness \(R\): because \(t<r\), both alternatives for willingness at \(r\) fail.
It also cannot pay for any removed project. Every removed project has old price greater than \(r>t\), whereas all its old payments have price at most \(z_A\le t\).
Finally, it cannot be an old payer of the updated project \(p\). If \(p\) was selected, its old price exceeds \(r>t\); if it was unselected, it had no old payers.
Thus \(A\) neither gains nor loses any payment. Its load and highest paid price remain unchanged, so it remains unwilling at \(t\). This proves the inclusion. \(\square\)
Proof. Suppose, for contradiction, that the resulting state \(X'\) has a witness \((q,Q)\) with price
\(t=c_q/\mu(Q)<r.\)
By Lemma 3, every member of \(Q\) was willing at \(t\) in \(X\). All still approve \(q\). It remains to verify the mass requirement in the old state.
There are three cases.
Therefore \((q,Q)\) was already a witness in \(X\), with price \(t<r\). This contradicts the choice of a minimum-price witness for the update. \(\square\)
Consequently, if the successive greedy update prices are \(r_1,r_2,\ldots\), then
\(r_1\le r_2\le\cdots.\)
This conclusion holds regardless of how equal-price choices are resolved.
Proof. Suppose project \(p\) is updated at step \(i\), acquiring price \(r_i\). Assume that a later step \(j\) is the first step to change its payer set or price. Immediately before that step, its price is still \(r_i\).
There are only two possible ways to change it.
All other updates retain \(p\)’s payer set. Thus no first later change exists. \(\square\)
Every update targets a project that has never previously been updated. Since there are \(m\) projects, there are at most \(m\) updates.
Whenever the current state is unstable, Lemma 2 finds a minimum-price witness and Section 4 guarantees a feasible update. Therefore the procedure cannot stop at an unstable state. The update bound forces it to terminate at a stable state.
The algorithm is:
The returned state is reachable by the required greedy updates, and the witness search tests selected projects as well as unselected ones.
Each iteration uses \(O(\tau\log\tau+m\tau)\) arithmetic operations and comparisons. Computing highest-price projects with the prescribed tie rule, marking removals, and modifying payer sets fits within \(O(m\tau)\). There are at most \(m\) updates and one final stability check, giving a total of
\(O\bigl(m\tau\log\tau+m^2\tau\bigr)\)
arithmetic operations and comparisons.
To justify polynomial bit complexity, let \(D\) be the product of the denominators of the input masses. Its binary bit length is \(O(L)\). Every mass can be written as \(M_A/D\), with \(M_A\) a positive integer, and normalization gives \(\sum_A M_A=D\).
Hence every payer or prefix mass is \(M/D\), where \(1\le M\le D\), and has an \(O(L)\)-bit representation. If \(c_p=a_p/b_p\), every finite state price or candidate prefix price has the form
\(c_p/(M/D)=a_pD/(b_pM),\)
whose numerator and denominator have \(O(L)\) bits.
A type load is a sum of at most \(m\) such prices. Its reduced rational representation has \(O(mL+\log m)\) bits: a common denominator can be obtained by multiplying those denominators, and the numerator has a bound of the same order. Remaining budgets and ordering endpoints consequently have polynomial bit length as well.
These bounds apply anew at every iteration. Prices always come directly from an input cost and a sum of input masses, so repeated updates introduce no recursive growth in their representations. Reduced exact rational arithmetic therefore implements every operation and comparison in polynomial time.
This proves the theorem for the exact support-encoded problem, without expanding masses into discrete voters or splitting any type.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The argument establishes a polynomial-time algorithm for the stated support-encoded problem, including arbitrary supplied feasible initial states. I found no mathematical gaps or false steps.
The willingness predicate correctly reproduces the witness condition, including its asymmetric endpoints: affordability permits equality, while replacement of a highest-price payment requires strict inequality.
Downward closure is valid. Reducing a positive price preserves either of the two willingness conditions.
Lemma 1 is correct. Admissibility implies \(R\subseteq E_{X,p}(c_p/\mu(R))\). Completing \(R\) with all types willing at its price increases its mass and therefore weakly decreases its price. Downward closure then establishes admissibility of the completed set. No type splitting is used.
The requirement \(\mu(R)>\sigma_p\) is correctly kept separate from admissibility.
The definitions of \(h_A\) and \(e_A\) encode willingness correctly:
Sorting by decreasing \(h_A\), with closed endpoints before open endpoints at equal \(h_A\), makes every willingness set a prefix. Restricting this order to a project’s approving types preserves the prefix property.
Consequently, the last-member test for prefix admissibility is valid. If the last member is willing at the prefix’s induced price, every preceding member is also willing at that price.
Lemma 2 correctly establishes maximum admissible mass. Every admissible set completes to an admissible prefix of at least its mass; the largest admissible prefix has at least the mass of every such completion. Strictly positive masses justify the strict increase of prefix masses.
The prover correctly scans all prefixes and does not assume that admissibility is monotone in the prefix index.
The witness-search conclusions follow:
The uniqueness assertion is also correct: a maximum-mass admissible set must equal its willingness completion, since every added type would contribute positive mass.
The comparison \(r<\pi_p\) follows from the strictly larger witness mass when \(p\) is selected. The convention \(\pi_p=+\infty\) handles an unselected project.
Every marked project has old price strictly greater than \(r\): a marking type cannot afford \(r\), so its witness condition must instead give \(r<z_A\). The marked project has price \(z_A\).
The updated project cannot itself be marked, since marking types lie outside its old payer set.
The four load cases exhaust all types and correctly bound their new loads. In particular:
Removing a marked project entirely can only cause additional payment losses; it does not invalidate these upper bounds.
The new payer set funds \(p\) exactly, and every other retained project keeps its price and payer set. The double-counting identity for total selected cost is correct.
Lemma 3 is valid.
For a type unwilling at \(t<r\), the inequalities \(f_A<t\) and \(z_A\le t\) exclude membership in the update witness. They also exclude payment for any marked project, because marked projects have old price greater than \(r\).
Such a type cannot be an old payer of the updated project either: that project’s old finite price exceeds \(r\), or it was unselected.
Thus none of the update’s payment changes affects this type. Its load and highest paid price remain unchanged, proving the claimed inclusion \(E_{X'}(t)\subseteq E_X(t)\).
Lemma 4 correctly checks both requirements for an alleged lower-price witness in the old state.
Willingness transfers backward by Lemma 3. The mass condition is verified in all three exhaustive project cases:
This would produce an old-state witness cheaper than the greedy choice, a contradiction. Therefore successive greedy prices cannot decrease. The argument does not require any additional tie-breaking assumption.
Lemma 5 correctly uses the first subsequent change to an updated project.
Updating that project again would strictly decrease its price. Removing it would require its current price to be strictly greater than the later update price. Both contradict nondecreasing greedy prices.
These are the only ways a project’s payer set or price can change under the prescribed rule. Therefore each project is updated at most once, yielding at most \(m\) updates.
The termination argument is complete: whenever a witness exists, the prefix search finds a greedy witness and the update remains feasible. Together with the update bound, this forces termination at a stable state. Selected projects are included in the search.
The stated per-iteration operation bound is justified. Computing state quantities, scanning approving-type prefixes, and applying an update each fit within \(O(m\tau)\); sorting contributes \(O(\tau\log\tau)\).
At most \(m\) updates and one final search give the stated total bound for \(m\ge1\). The case \(m=0\) is explicitly handled.
The bit-length argument is sound:
Recomputing prices from input costs and subset masses prevents recursive representation growth. Reduced exact rational arithmetic supplies the claimed polynomial bit complexity.
The proof addresses the exact assigned model: support-sized input, indivisible types, strict willingness endpoints, selected-project witnesses, prescribed removals, and arbitrary feasible initial states.
The reference to Kraiczy and Elkind is contextual. No theorem from that paper is needed as an unverified premise, since the necessary convergence statements are proved directly.
No additional clarification or repair 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.