Answer: Polynomial-time solvable.
Proposition 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximatePerpetual Phragm´en is not equivalent to any WAM and is computable in polynomial time. We note that the Method of Equal Shares (Peters and Skowron 2020), a multi-winner voting rule closely related to WAMs, the definition can easily be adapted to that framework by defining a voting rule that assigns the same weights as Perpetual Consensus if αkpvq is positive and 0 otherwise. Moreover, observe that compared to Lackner (2020), we divided all weights by n to highlight the similarity to Perpetual Phragm´en.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite horizon, rational masses over explicitly listed complete approval-trajectory types, round-specific approval profiles and alternatives, and tie-breaking orders, compute the online Perpetual Phragmén winner sequence and supporting mass/load states when each round selects a supporting mass minimizing the resulting common load.
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational. Here \(\tau\) is the support size, not the number of possible types. Masses sum to \(1\), and mass within a type is divisible.
The input explicitly lists a horizon \(K\geq1\), nonempty alternative sets \(C_r\), and complete approval trajectories \((A_r(i))_{r=1}^K\), with \(\varnothing\neq A_r(i)\subseteq C_r\). It supplies a type order and an alternative order for each round. Let \(m=\max_r|C_r|\) and let \(L\) be the total input bit length.
Represent the load state by cohorts: each cohort \(j\) has a type \(i(j)\), positive mass \(p_j\), and load \(\ell_j\geq0\). Initially each type forms one cohort of load \(0\); merge cohorts with identical type and load.
In round \(r\), a supporting selection consists of real masses \(0\leq x_j\leq p_j\) with \(\sum_jx_j>0\) and \(B_r(x)=\bigcap_{j:x_j>0}A_r(i(j))\neq\varnothing\). Its resulting common load is \(q(x)=(1+\sum_jx_j\ell_j)/\sum_jx_j\); each round incurs total load \(1\).
Choose a selection minimizing \(q(x)\). Resolve selection ties by the lexicographically largest vector \(x\), ordering cohorts first by the supplied type order and then by increasing load. Choose the first alternative in \(B_r(x)\) under the supplied round order. Selected mass receives load \(q(x)\); unselected mass retains its load.
Each round may use only current approvals, past approvals and decisions, masses, and the supplied orders. Compute the exact winner sequence, supporting selections, and cohort load states.
Is exact computation of this continuous Perpetual Phragmén process possible in polynomial time in \(m,\tau,K,L\), or is it NP-hard?
Discrete Perpetual Phragmén is computable in polynomial time and is not equivalent to any weighted approval method ([verified full version](https://martin.lackner.xyz/publications/AAAI-Proportional%20Decisions%20in%20Perpetual%20Voting-with-appendix.pdf)). No result settling this precisely specified divisible-mass problem was located.
The specified process admits an exact algorithm polynomial in \(m,\tau,K,L\). The key fact is that its lexicographic tie-breaking rule always selects each current cohort either completely or not at all. Consequently, starting from the prescribed initial state, every type always has exactly one cohort.
We prove the optimization, tie-breaking, and bit-complexity claims separately.
Fix a round and its current cohorts. For an alternative \(c\), define its supporting cohorts by
\(J_c=\{j:c\in A_r(i(j))\}\).
Ignore alternatives with \(J_c=\varnothing\). For every other alternative, define
\(F_c(t)=\sum_{j\in J_c}p_j\max\{t-\ell_j,0\}\).
This function is continuous, equals zero at \(t=\min_{j\in J_c}\ell_j\), is strictly increasing thereafter, and tends to infinity. Hence there is a unique threshold \(t_c\) satisfying
\(F_c(t_c)=1\).
Lemma. Among selections supported entirely on \(J_c\), the minimum resulting load is \(t_c\). The minimizing selections are exactly those satisfying
\(x_j=p_j\) when \(j\in J_c\) and \(\ell_j<t_c\),
\(x_j=0\) when \(j\notin J_c\) or \(\ell_j>t_c\),
and arbitrary \(x_j\in[0,p_j]\) when \(j\in J_c\) and \(\ell_j=t_c\).
Proof. For any such selection, write \(q=q(x)\). Rearranging the definition of \(q\) gives
\(1=\sum_{j\in J_c}x_j(q-\ell_j)\).
For each summand,
\(x_j(q-\ell_j)\leq p_j\max\{q-\ell_j,0\}\).
Therefore \(1\leq F_c(q)\), which implies \(q\geq t_c\).
At \(q=t_c\), the difference between the two sums is
\(F_c(t_c)-\sum_{j\in J_c}x_j(t_c-\ell_j) =\sum_{\substack{j\in J_c\\\ell_j<t_c}}(p_j-x_j)(t_c-\ell_j) +\sum_{\substack{j\in J_c\\\ell_j>t_c}}x_j(\ell_j-t_c)\).
Every term on the right is nonnegative. Equality holds precisely when all cohorts strictly below the threshold are fully selected and all cohorts strictly above it are unselected. Cohorts at the threshold contribute zero regardless of their selected mass.
Conversely, any selection satisfying these conditions obeys
\(\sum_{j\in J_c}x_j(t_c-\ell_j)=F_c(t_c)=1\).
It has positive selected mass because \(F_c(t_c)=1\) requires at least one cohort strictly below \(t_c\). Rearranging this identity proves \(q(x)=t_c\). This proves the lemma.
Let
\(t_*=\min_{c:J_c\neq\varnothing}t_c\).
There is at least one alternative with supporters: every type has positive mass and a nonempty approval set.
For any feasible selection \(x\), choose \(c\in B_r(x)\). Its selected cohorts belong to \(J_c\), so the lemma gives
\(q(x)\geq t_c\geq t_*\).
Conversely, the lemma supplies a feasible selection attaining \(t_*\) for any alternative with threshold \(t_*\). Thus the global minimum is exactly \(t_*\).
For each alternative satisfying \(t_c=t_*\), define the vector
\(v_j^c= \begin{cases} p_j,&j\in J_c\text{ and }\ell_j\leq t_*,\\ 0,&\text{otherwise}. \end{cases}\)
By the lemma, \(v^c\) is a globally minimizing selection. Moreover, it is the lexicographically largest minimizing selection supported on \(J_c\): the only free coordinates belong to cohorts at load \(t_*\), and setting each to its maximum \(p_j\) dominates every other permissible choice coordinatewise.
Now consider any global minimizer \(x\). Choosing \(c\in B_r(x)\) gives
\(t_*=q(x)\geq t_c\geq t_*\),
so \(t_c=t_*\). The lemma then implies that \(x\) is coordinatewise bounded above by \(v^c\). Therefore the lexicographically largest global minimizer is exactly
\(x^*=\operatorname{lexmax}_{c:t_c=t_*}v^c\),
using the supplied cohort order.
After computing \(x^*\), compute its actual approval intersection
\(B_r(x^*)=\bigcap_{j:x_j^*>0}A_r(i(j))\),
and choose its first alternative under the supplied round order. This follows both tie-breaking instructions in their specified order.
Every coordinate of every vector \(v^c\) is either zero or the entire cohort mass. The same therefore holds for \(x^*\).
Thus each cohort either remains entirely at its old load or moves entirely to \(t_*\). No cohort splits.
Initially each type has one cohort. Inductively, each type continues to have exactly one cohort throughout all rounds. Consequently:
This proves that neither the internal state nor the requested output suffers from cohort proliferation.
Write the current state as masses \(p_i\) and loads \(\ell_i\), one for each type.
For a supported alternative \(c\), sort its supporting types by nondecreasing load:
\(\ell_{i_1}\leq\ell_{i_2}\leq\cdots\leq\ell_{i_s}\).
For each nonempty prefix, compute
\(q_{c,k}=\dfrac{1+\sum_{h=1}^{k}p_{i_h}\ell_{i_h}}{\sum_{h=1}^{k}p_{i_h}}\).
Then
\(t_c=\min_{1\leq k\leq s}q_{c,k}\).
Indeed, every prefix is a feasible selection supported on \(c\), so the lemma implies \(q_{c,k}\geq t_c\).
For the reverse inequality, take the prefix consisting of all supporting types whose load is strictly less than \(t_c\). It is nonempty because \(F_c(t_c)=1\), and it is a prefix even when equal loads occur. For this prefix, the threshold equation reads
\(\sum_{\ell_i<t_c,\ i\in J_c}p_i(t_c-\ell_i)=1\),
which rearranges to \(q_{c,k}=t_c\).
Hence sorting and scanning prefixes computes every threshold using exact rational arithmetic. The remaining vector comparisons, approval intersections, and updates are also polynomial in the number of types and alternatives.
The same sorted-prefix idea appears in the discrete computation in Proposition 1 of [Lackner and Maly’s paper](https://martin.lackner.xyz/publications/AAAI-Proportional%20Decisions%20in%20Perpetual%20Voting-with-appendix.pdf). The argument above proves its weighted version and the particular selection tie-breaking required here.
It remains to bound the sizes of the exact rational numbers. A polynomial number of arithmetic operations alone would not suffice.
Write the input masses as \(p_i=a_i/b_i\), with positive integers \(a_i,b_i\). Let
\(D=\prod_{i=1}^{\tau}b_i,\qquad w_i=Dp_i\).
Then every \(w_i\) is a positive integer, and
\(\sum_i w_i=D\).
The binary length of \(D\) is at most the sum of the input denominator lengths, hence is \(O(L)\).
We maintain every load after round \(r\) with a common, possibly unreduced denominator:
\(\ell_i=N_i/E_r\).
Initially \(E_0=1\) and every \(N_i=0\).
Suppose the selected type set in the next round is \(S\), and put
\(W=\sum_{i\in S}w_i\).
Because the selection takes whole types, its common resulting load is
\(q=\dfrac{DE_r+\sum_{i\in S}w_iN_i}{E_rW}\).
Therefore we may set
\(E_{r+1}=E_rW\).
For selected types, the new numerator is \(DE_r+\sum_{i\in S}w_iN_i\); for unselected types, the new numerator is \(WN_i\). These are all integers.
Since \(1\leq W\leq D\), induction gives
\(E_r\leq D^r\).
Next, total mass-weighted load after round \(r\) equals \(r\). Indeed, the increase in one round is exactly
\(\sum_i x_i(q-\ell_i)=1\).
All loads are nonnegative. Thus each type satisfies
\(p_i\ell_i\leq r\),
and, using \(p_i=w_i/D\),
\(0\leq\ell_i\leq rD/w_i\leq rD\).
Consequently,
\(0\leq N_i=E_r\ell_i\leq rD^{r+1}\).
Both the numerators and common denominators therefore have binary length
\(O((r+1)L+\log(r+1)+1)\).
The threshold-prefix calculations obey the same polynomial bound. Their numerators have the form \(DE_r+\sum_{i\in S}w_iN_i\), and their denominators are \(E_rW\), where \(1\leq W\leq D\). Thus every operand and intermediate result throughout the algorithm has polynomial bit length in \(K,L\).
Exact addition, multiplication, division, and comparison of integers of these lengths take polynomial time. Fractions can also be reduced for output using the Euclidean algorithm.
For each round:
Every step uses only masses, supplied orders, current approvals, and the state determined by previous rounds. Hence the algorithm meets the online restriction.
There are polynomially many arithmetic operations, all on numbers of polynomial bit length. Each state has only \(\tau\) cohorts, so the complete requested output also has polynomial size.
Therefore exact computation of this precisely specified continuous Perpetual Phragmén process is polynomial-time solvable in \(m,\tau,K,L\).
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output establishes an exact polynomial-time algorithm for the specified continuous process, including both tie-breaking rules, supporting selections, and cohort states. I found no major or minor mathematical issues.
For each nonempty supporting set \(J_c\), all masses \(p_j\) are positive. Consequently, the stated function \(F_c\) is continuous, vanishes at the minimum supporting load, increases strictly above that load, and is unbounded. These properties justify existence and uniqueness of \(t_c\) satisfying \(F_c(t_c)=1\).
Ignoring alternatives without supporters is valid: no positive-mass selection can have such an alternative in its approval intersection.
The rearrangement
\(1=\sum_{j\in J_c}x_j(q-\ell_j)\)
follows directly from the definition of \(q\), since selected mass is positive.
The summand inequality is valid for every possible sign of \(q-\ell_j\). If it is nonnegative, the inequality follows from \(x_j\leq p_j\); if it is negative, the left side is nonpositive and the right side is zero. Thus \(1\leq F_c(q)\), and the threshold properties imply \(q\geq t_c\).
This argument covers arbitrary real selected masses, rather than assuming full-cohort selections in advance.
The displayed difference of sums has the correct signs and coefficients. All its terms are nonnegative. Because masses are positive and the loads in each indexed sum are strictly below or strictly above \(t_c\), equality forces precisely the stated full-selection and zero-selection conditions.
Loads equal to \(t_c\) contribute zero, so their selected masses are unrestricted within their allowed intervals.
The converse is also complete. The threshold equation ensures that at least one supporting cohort lies strictly below \(t_c\). Every such cohort is fully selected, so the characterized selection has positive total mass. Rearrangement then gives \(q(x)=t_c\). Its approval intersection contains \(c\), ensuring feasibility.
Every feasible selection has some \(c\in B_r(x)\). Applying the fixed-alternative lemma to that \(c\) proves the global lower bound \(q(x)\geq t_*\). A threshold-attaining selection supplies attainment.
For any global minimizer, the chain
\(t_*=q(x)\geq t_c\geq t_*\)
correctly forces \(t_c=t_*\). The fixed-alternative characterization then establishes coordinatewise domination by \(v^c\).
Each \(v^c\) is itself feasible and globally optimal. Coordinatewise domination implies lexicographic domination under the prescribed cohort order. Therefore taking the lexicographic maximum over these finitely many vectors produces the lexicographically largest global minimizer. This also establishes existence of the required tie-breaking outcome.
Computing the actual intersection \(B_r(x^*)\) afterward correctly implements the separate alternative tie-break. The output does not mistakenly identify the generating alternative \(c\) with the final winner.
Every candidate vector \(v^c\) selects each cohort either fully or not at all, and the chosen vector is one of these candidates. Thus no round splits a cohort.
Starting with one cohort per type, the stated induction preserves exactly one positive-mass cohort per type. Merging cannot combine different types, and no additional cohort of the same type is created. Hence the bound of exactly \(\tau\) cohorts is correct, and increasing-load ordering within a type becomes vacuous.
Selected cohorts have load at most \(t_*\), so updates preserve nonnegative loads.
Every nonempty prefix selects positive mass and shares the supporting alternative \(c\), so its resulting load is at least \(t_c\).
The supporting cohorts strictly below \(t_c\) form a nonempty prefix in any nondecreasing load order. Equal-load ties do not obstruct this assertion, because the strict cutoff includes or excludes an entire equal-load block. The threshold equation gives equality for this prefix. Therefore the claimed minimum-over-prefixes formula is correct.
The historical attribution is accurate at the level claimed: the appendix proof of Proposition 1 uses sorting by load and examining prefixes. The present output independently proves its continuous weighted claim, so it does not rely on transferring that discrete result without checking hypotheses. [Lackner and Maly, appendix, Proposition 1](https://martin.lackner.xyz/publications/AAAI-Proportional%20Decisions%20in%20Perpetual%20Voting-with-appendix.pdf)
The construction \(D=\prod_i b_i\) makes every \(w_i=Dp_i\) a positive integer. Normalization gives \(\sum_i w_i=D\), and the binary length of \(D\) is bounded by the input denominator lengths.
Given the proved full-type selection property, the formula
\(q=(DE_r+\sum_{i\in S}w_iN_i)/(E_rW)\)
is algebraically correct. Both selected and unselected numerator updates correctly express the new state over \(E_{r+1}=E_rW\).
Since the selection is nonempty, \(1\leq W\leq D\), proving \(E_r\leq D^r\).
The total weighted-load increment is exactly one. Starting from zero, total weighted load after round \(r\) is therefore \(r\). Nonnegative loads imply the individual bound \(\ell_i\leq rD/w_i\leq rD\), and hence \(N_i\leq rD^{r+1}\). The resulting stated bit-length bound is valid, including initialization.
Prefix calculations use the same integer numerator and denominator forms. Their weighted sums and exact comparison products have polynomial bit length under the established bounds. There are at most \(m\) alternatives and \(\tau\) supporting types per round, so sorting, prefix scans, vector comparisons, intersections, and updates require polynomially many operations.
Each recorded state contains only \(\tau\) cohorts with polynomial-length rational data. Recording all \(K\) rounds therefore has polynomial size.
The round algorithm uses only current approvals, supplied orders, masses, and the state from earlier rounds. It satisfies the online restriction despite the input listing complete trajectories.
Repair feedback: None is required. The proof resolves the assigned target as written.
⟨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.