| paper | d4-conf-wine-2023-0005 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(m,\tau,L\), with at most \(m\) greedy updates. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
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.
Participatory budgeting with integral project selection and a society given by rational masses over approval types. The state records which types pay for each selected project; payer mass determines per-capita price, and each type’s total payment must fit within \(B\). The task is to compute a stable state through greedy price-improving updates.
The mirror covers stable-outcome computation, stability verification, and the next-budget breakpoint corresponding to Theorems 4, 2, and 6. It leaves Theorem 5’s tie-consistency result, the empirical study, and a separate proof of the mass-level EJR guarantee open.
The strongest honest case is a mirror of AMES’s population model and its computation of stable, verifiably proportional outcomes. It is a good fit for the programme because AMES already makes voter counts computationally important: it compares the cost of a project with the number of people sharing it and gives each voter budget \(b/n\). The paper’s numbered results provide useful algorithmic anchors. It has no numbered hardness result of its own; the NP-hardness of checking EJR for an arbitrary outcome is background cited from [1, 2], not an anchor I would attribute to this paper.
A plausible regime is city or region wide participatory budgeting with thousands or tens of thousands of residents choosing from a fixed slate of projects. The voter types are their exact approval sets. In some such elections, repeated ballots from neighborhood or issue coalitions could give \(n\) residents but a much smaller support of \(\tau\) distinct ballots. The paper’s data establishes that large electorates and project slates are real—roughly 5,000 to 54,000 voters and 39 to 151 projects in the reported instances—but it does not report the number of distinct ballots. So it motivates the scale, not the claim that those particular elections have small \(\tau\).
Here is the mirror I would put to the authors. Give a finite project set \(P\), rational per-capita project costs \(c_p>0\), a rational per-capita budget \(B\), and approval types \(A_1,\ldots,A_\tau\subseteq P\) with rational masses \(\mu_a>0\) summing to \(1\). The type is the complete relevant description: agents with the same approval set face the same project costs and budget. Keep project selection integral: an outcome is still \(W\subseteq P\). A symmetric equal-shares state specifies, for each selected project \(p\), a set \(S_p\) of types paying for it. Its payer mass is \(\sigma_p=\sum_{a\in S_p}\mu_a\), and each paying resident contributes \(\pi_p=c_p/\sigma_p\). The state is feasible when every type’s total per-resident payment, \(\sum_{p:a\in S_p}\pi_p\), is at most \(B\).
This scaling gives an exact finite-replication dictionary. If \(N\mu_a\) is an integer for every type, set total project costs to \(Nc_p\) and total budget to \(NB\). The finite election then has the same per-voter project prices and loads. The continuous question is whether the mass input can be handled in time polynomial in \(m,\tau\), and the binary encoding length \(L\), rather than time proportional to the potentially enormous replicated electorate. That is a genuine high-multiplicity question. Residents are the continuous object; projects remain indivisible.
My lead is Continuous AMES. Theorem 4, proved in this paper, says that from an election and an equal-shares solution, Algorithm 1 reaches a stable solution in at most \(\left|\{p\in P:\pi(p,X^*)<\pi(p,X)\}\right|=O(m)\) greedy update steps, each taking \(O(n\log n+mn)\) time. Its continuous counterpart is: given the mass instance above and a feasible symmetric equal-shares starting state (or the empty state), compute a stable equal-shares outcome by greedily adding a project or increasing its payer mass, with AMES’s project-removal rule when supporters must free budget.
For this definition, let \(\ell_a\) be type \(a\)’s current total per-resident load and \(z_a\) its highest current project price, or \(0\) if it pays for none. A type can afford a proposed price \(q\) either from unused budget, \(q\le B-\ell_a\), or by shifting away from a more expensive project, \(q<z_a\). The state is unstable if some project \(p\) has a set \(R\) of approving types whose total mass \(s=\sum_{a\in R}\mu_a\) exceeds its current payer mass, and every type in \(R\) can afford \(c_p/s\) by one of those two routes. A greedy update chooses the feasible project-price improvement with the lowest new price. The strict inequality captures the paper’s finite \(\epsilon\) rule: in the continuum, there is no smallest positive gap between possible prices.
I expect this problem to be tractable, with a weighted implementation polynomial in \(m,\tau,L\). The paper’s \(O(m)\)-update argument is a promising template, and each update can work over the support types rather than the expanded electorate. That is a proposed theorem, not an automatic consequence of Theorem 4: the continuous version still needs a termination and bit-complexity proof.
The second question is Continuous Stability Verification. Theorem 2, also proved here, says that for an election with \(n\) voters and \(m\) projects, a process \(V(W,X)\) decides whether the supplied solution is stable in \(O(n\log n+mn)\) time. In the mass version, the input is the rational type distribution and a candidate symmetric equal-shares state; the task is to decide the stability condition just defined. I expect this to be in P in \(m,\tau,L\), using weighted threshold checks over the type capacities. This mirrors the paper’s certificate-based verification task. It does not claim that recognizing EJR from an arbitrary outcome becomes easy: the load state is extra input, and the decision being verified is stability.
That verifier matters because the paper proves that every stable solution provides EJR: for every cohesive group approving a project set \(T\), some member of the group has at least \(|T|\) approved projects in the outcome. The continuous programme should ask for the corresponding mass-level guarantee as part of the mirror—whether a cohesive group of positive mass contains a positive-mass subset receiving that representation.
A third, distinct question is Next Budget Breakpoint. Theorem 6, proved here, says that given a stable solution at budget \(b\), the minimum \(b'>b\) at which that solution becomes unstable can be computed in \(O(mn^2\log n)\) time. Its mass counterpart takes the type distribution, per-capita costs, a stable state at budget \(B\), and asks for the least \(B'>B\) at which that same state becomes unstable, or reports that no finite breakpoint exists. I expect a polynomial algorithm in \(m,\tau,L\), by computing weighted thresholds across types. This directly mirrors the paper’s budget-adaptive motivation while keeping the society—not a continuous budget path—as the continuized object.
The three problems cover the stable-outcome computation, its stability certificate, and the next budget increase that forces an update. They leave the paper’s empirical comparison uncovered. The weakest point is the finite-to-continuous stability rule: the paper’s \(\epsilon\) is tied to discrete price gaps, so the strict cheaper-price convention is a considered limit definition that the authors might refine. And although the support-type formulation looks algorithmically manageable, the paper’s polynomial runtime in \(n\) does not itself prove polynomial time in the compressed input size \(m,\tau,L\). Those are substantial proof obligations, but they are exactly the computational questions that make this a worthwhile mirror.
The strongest case against is that Theorem 4’s guarantee is tied to a finite price grid. Its \(O(m)\) update bound relies on finite payer counts and the positive gap \(\epsilon\) between possible payments. If a type’s mass can be split, payer mass and project price vary continuously; the proof’s progress argument no longer applies. So the proposed continuous AMES algorithm is a new dynamical problem, not a direct high-multiplicity translation of the theorem. The paper’s central claim is about this finite update process and budget reuse ([paper](https://arxiv.org/abs/2310.10215)).
That objection does not defeat the stronger mirror, though. One can define mass-level stability, allow fractional payer mass within each approval type, and ask whether a stable state can be computed in time polynomial in \(m,\tau,L\). The loss of the original proof is a research question, not evidence that the mirror is unworthy.
Theorem 2 is harder to dismiss: its stability verifier could be reformulated over type masses by sorting type capacities and accumulating their weights. The practical DAO motivation is specifically about people checking a proposed outcome; current MES tooling still works from explicit election files ([computation tool](https://equalshares.net/tools/compute/)). That makes the operational gain of a compressed verifier uncertain, but it does not remove the well-posed complexity question.
Theorem 6 concerns budget breakpoints, so its computational axis is budget rather than population. Still, holding a continuous society fixed and asking when its state first becomes unstable is a legitimate mirror. A careful version might ask for the infimum breakpoint and a witness, since a strict instability condition need not attain a least budget.
So the negative case’s real point is that the proponent has not established that any of these continuous algorithms or bounds follows from the finite ones. But the requested verdict is about whether worthwhile mirrors exist, not whether the proofs transfer unchanged. Theorem 4 is the vulnerable anchor; I cannot honestly defeat the verification or breakpoint questions, and I do not think the universal negative survives.
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.