| paper | Proportional Decisions in Perpetual Voting |
| authors | — |
| venue | AAAI 2023 |
| filed under | voting · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Proposition 1
statement extracted from the paper’s text layer
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 finite type population with mass \(\mu_t\), per-type current loads \(\ell_t\), and per-round supporting-mass variables \(x_t\); for each candidate minimize \((1 + \Sigma_t x_t\ell_t)/(\Sigma_t x_t)\), then update selected mass loads and continue online.
The mass optimization is degenerate: optimal support can be chosen as whole equal-load type blocks, making the process essentially a weighted finite-voter recoding; complete trajectory types may also be exponential in the horizon.
fatal: False
The mirror covers the computability claim in Proposition 1 and leaves the paper's axiomatic results, including proportionality and dry-spell theorems, untreated.
The positive case is real but narrow. The paper has one clear computational anchor, and I would use only that:
Proposition 1. “Perpetual Phragmén is not equivalent to any WAM and is computable in polynomial time.”
This is proved in the paper, not cited from elsewhere; Perpetual Phragmén is explicitly introduced as new to the perpetual setting. The other numbered results are axiomatic, so I would not pretend that Theorems 2, 3, 6, 7 or Propositions 4–10 provide additional computational anchors.
My lead mirror is Continuous Perpetual Phragmén Evaluation.
Consider a large membership organisation—say, a national union, professional association, housing federation, or platform—with millions of members making recurring decisions. There are only \(\tau\) relevant persistent voter types, where a type is a complete approval trajectory for the purposes of the process: two members of the same type approve exactly the same alternatives in every round. Type \(t\) has mass \(\mu_t\), with \(\sum_t\mu_t=1\), and typically \(\tau\ll n\). This is a genuine high-multiplicity regime: large constituencies repeatedly exhibit the same approval behaviour, while the process still makes one discrete decision at a time.
The continuous problem is as follows. An instance consists of a finite horizon \(K\), rational masses \(\mu_t\), a finite alternative set \(C_i\) and approval set \(A_i(t)\subseteq C_i\) for each round \(i\), and a fixed tie-breaking order. Each unit of population has a current Phragmén load \(\ell_i(t)\), initially zero. At round \(i\), for each alternative \(c\), choose a supporting submass \(x_t\) satisfying
\[ 0\le x_t\le \mu_t,\qquad x_t=0\ \text{if }c\notin A_i(t),\qquad q=\sum_t x_t>0. \]
The load after making \(c\) win with this supporting coalition is
\[ \lambda_i(c,x) = \frac{1+\sum_t x_t\ell_i(t)}{\sum_t x_t}. \]
Thus one unit of new decision load is distributed over a mass of supporters, and \(\lambda_i(c,x)\) is the resulting common load of that coalition. Define
\[ \lambda_i(c)=\min_x\lambda_i(c,x). \]
The rule chooses an alternative \(w_i\) minimizing \(\lambda_i(c)\), resolves ties by the fixed order, and returns both \(w_i\) and a minimizing supporting mass \(x\). The selected mass is relabelled with load \(\lambda_i(w_i,x)\); unselected mass retains its previous load. The output is the sequence of winners and load states over all \(K\) rounds. The process remains online: round \(i\) uses only the current approval profile and the loads generated by earlier rounds.
This is not merely an analogy. Given a discrete election with \(n\) voters, set \(\mu_t=n_t/n\), let \(x_t\) be the fraction of selected voters of type \(t\), and scale continuous loads by \(n\), so \(\ell_i^{\mathrm{cont}}=n\ell_i^{\mathrm{disc}}\). Then
\[ \lambda_i^{\mathrm{cont}} = n\cdot \frac{1+\sum_{v\in N'}\ell_i^{\mathrm{disc}}(v)} {|N'|}. \]
Consequently the continuous and discrete processes choose exactly the same winner, with only a uniform scaling of loads. The continuous problem extends the discrete mass grid to arbitrary rational fractions, precisely as a high-multiplicity relaxation should.
I expect this problem to be Class A: tractable. For a fixed alternative, sort its supporting state-types by current load. If \(Q_j\) is the cumulative supporting mass of the first \(j\) types and \(H_j\) their cumulative load, an optimum is attained at a prefix and has value
\[ \min_j \frac{1+H_j}{Q_j}. \]
The reason is structural: for any fixed selected mass, the lowest-load supporters are optimal; within an equal-load block, enlarging the coalition only decreases the average. Thus each alternative can be priced by sorting and scanning its supporters, followed by comparison across alternatives. The whole \(K\)-round process is polynomial in \(K\), the number of alternatives, \(\tau\), and the rational encoding length, rather than in the number \(n\) of named voters.
The authors should recognise this as their problem. Alternatives remain discrete, one alternative still wins per round, approval profiles may change from round to round, the procedure is online, and the objective is exactly their load-balancing objective. Only the population has been aggregated. It is not outcome-space continuity, a lottery, a mean-field equilibrium, or an offline optimisation problem.
This mirror covers Proposition 1 and nothing more. It also opens natural computational questions: minimum mass campaigning needed to change a future winner; robustness regions in the mass simplex; continuous dry-spell and quota guarantees; and whether the same evaluation remains tractable when the type family is given implicitly rather than explicitly.
The weakest point is that this is a modest anchor. The paper is primarily axiomatic, and Proposition 1 says that the original rule is already polynomial-time computable; the mirror does not dissolve an NP-hardness barrier or reveal a new Class A phenomenon. A referee might therefore regard it as a faithful high-multiplicity reformulation rather than a major complexity result. But the mirror itself is strong: it preserves the distinctive Phragmén process exactly, gives a sensible large-population regime, and yields a population-size-independent algorithm without changing the authors’ question.
The negative case cannot rely on the paper being purely axiomatic: Proposition 1 is a genuine computational anchor. Nor is there a convincing “no multiplicity” objection. A national union, professional association, or large platform could plausibly contain many members with the same approval trajectory. The strongest objection is instead that the proposed continuum collapses mathematically.
For a fixed alternative, order its supporting population by current load. If the selected prefix has mass \(Q\) and total load \(H\), adding mass \(\delta\) from a block of load \(\ell\) gives
\[ F(\delta)=\frac{1+H+\ell\delta}{Q+\delta}, \qquad F'(\delta)=\frac{\ell Q-(1+H)}{(Q+\delta)^2}. \]
The derivative has constant sign throughout the block. Thus an optimum takes the whole equal-load block or none of it. The only exception is equality, in which case the ratio is already \(\ell\), and assigning a partial block the new load changes nothing: its load was already \(\ell\).
Consequently the supposedly fractional coalition is never genuinely fractional. Starting with finitely many voter types, the process remains exactly a weighted finite-voter version of Perpetual Phragmén. The continuous algorithm is the paper’s existing sort-and-scan computation with rational masses in place of repeated named voters. It does not produce an LP, a separation problem, a new state space, or a population-driven complexity phenomenon. The variable that was meant to make the population continuous disappears from every nontrivial optimum. This is a genuine continuum-degeneracy objection, not merely the observation that the answer happens to be polynomial.
The proposed “complete approval trajectory” type also makes the regime less compelling. If types are defined only by their current approval set, aggregation loses the correlation between current approval, future approval, and accumulated load. To preserve the online process one must instead group voters by their entire \(K\)-round trajectory. That is legitimate, but it is a much stronger cohort assumption, and the number of trajectory types can be exponential in the horizon. If one moves to an atomless distribution over richer trajectories, the problem requires an implicit distribution or oracle representation; its complexity then comes from representing that distribution, not from the high-multiplicity relaxation of the paper’s finite voting process.
One could attach a more interesting question—minimum mass campaigning, winner robustness, or manipulation of future approval trajectories. But those introduce an intervention model, costs, and often a new temporal coupling absent from the paper. They are generic continuous-control problems for a rule, not mirrors of Proposition 1 itself. They may be worthwhile ChoCo problems, but they cannot repair the weakness of this anchor.
That is the best negative case: the only computational result is already a simple polynomial evaluation result, and its natural mass version is an exact weighted recoding in which divisibility has no effect. It does not justify substantial programme effort. The case is not airtight, however. If the programme counts population compression and parametric robustness as worthwhile contributions, the proponent’s mirror is faithful and the universal claim fails. I would therefore regard this as a weak negative or low-priority case, not a defensible proof that no continuous mirror is possible in any scenario.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.