| paper | Proxy Voting for Better Outcomes |
| authors | Gal Cohensius, Shie Mannor, R. Meir, E. Meirom, Ariel Orda |
| venue | ATAL 2017 |
| filed under | voting · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper already models the population by an infinite distribution \(f\), computes Voronoi masses, and evaluates weighted rules, so finite-support \(\mu\) is only an encoding of its existing model. Theorem 4 is a statistical loss bound, while Theorem 6 is constructive but still concerns the paper's finite-panel participation game. Making participation nonatomic changes the strategic problem, so no anchor supplies a distinct continuous-population computational mirror.
fails bit b-already — the paper is already native to the continuum
The paper already assumes the continuous population in Section 2, so replacing \(f\) by finite-support \(\mu\) is a re-encoding; making participation nonatomic would change the pivotality game.
fatal: True
The proposed formulation covers the paper's median analyses, including Theorem 4 and Theorem 6, but leaves the mean, binary-issue, and empirical analyses untouched.
The strongest honest case is a weak but genuine positive one: this paper supports a tractable computational companion to its proxy-voting model. It does not support a hardness-transfer story, and strictly speaking it contains no named computational-complexity theorem.
The natural regime is a large union, workplace, or online community. There are \(N\) potential voters, with \(N\gg \tau\) and only \(\tau\) relevant policy-position types. A type is a policy position \(z_t\), together with the induced distance-based preferences and proxy-selection behaviour. The mass \(\mu_t\) is the fraction of the whole population at that position. Thus many workers with the same policy position are genuinely interchangeable. A small available panel of \(n\) voters is sampled from this population; everyone else delegates to the nearest available proxy.
The continuous object is therefore the population distribution \(\mu\), not the policy outcome. For a realized proxy panel \(S=(s_1,\ldots,s_n)\), each population type is assigned to its nearest proxy, producing Voronoi weights \(w_j=\mu(V_j)\). The mechanism then returns the weighted median, weighted mean, or issue-wise weighted majority. The objective is the expected squared distance from the population optimum.
My lead anchor is Theorem 4, proved in this paper:
For the Median mechanism, \(\loss^P(n)=O(1/n^2)\) for every symmetric distribution \(f\) satisfying the paper’s standing regularity assumption that the density is positive near the population median.
This is a result about the expected squared error under random proxy participation: \(n\) agents are sampled independently from \(f\), all become available proxies, the population delegates to its nearest sampled proxy, and the weighted median is compared with the population median.
The corresponding problem is:
Continuum Proxy-Median Loss. Given an ordered finite type set \(T=\{z_1,\ldots,z_\tau\}\), rational masses \(\mu_t\), a sample size \(n\), and an error tolerance \(\varepsilon\), let \(x^\star\) be the \(\mu\)-median. Sample \(n\) proxy types independently from \(\mu\); assign every type to its nearest sampled proxy; and return the weighted median. Compute the exact expected loss
\(\displaystyle L_\mu^{P}(n)=\mathbb E_{S\sim\mu^n}\!\left[(\md^P(S)-x^\star)^2\right]\),
or an additive-\(\varepsilon\) approximation.
This is not merely an easier median problem: it preserves the paper’s random availability, nearest-proxy rule, weighted aggregation, and welfare objective. It is the high-multiplicity version of a population containing \(N\mu_t\) voters of each type.
The problem appears to be Class A. Lemma 1, also proved here, says that the proxy median is always the sampled proxy closest to \(x^\star\). Hence if \(d_1<\cdots<d_q\) are the distinct distances from \(x^\star\) to the type locations and
\(\displaystyle p_r=\mu\bigl(\{z:|z-x^\star|\le d_r\}\bigr)\),
then
\(\displaystyle L_\mu^{P}(n)=\sum_{r=1}^q d_r^2\bigl((1-p_{r-1})^n-(1-p_r)^n\bigr).\)
Thus the expected loss can be computed from the mass distribution without enumerating the exponentially many proxy samples. This also gives a direct algorithmic interpretation of Theorem 4’s \(O(1/n^2)\) phenomenon.
A second, independent anchor is Theorem 6, again proved here:
In the proxy scenario with lazy strategic participation, for every distribution \(f\) and every finite sample \(N\), there is a unique equilibrium of \(\md^{P+L}\). The only active voter is \(j^\star\), the sampled voter closest to the population median \(x^\star\). The participation game is weakly acyclic, and \(\loss^{P+L}(n)=\loss^P(n)\).
Its continuous computational counterpart is:
Continuum Proxy-Participation Equilibrium. Given a rational type distribution \(\mu\), a realized finite proxy panel \(S\), and the median mechanism, each panel member chooses active or inactive. Inactive population mass delegates to the nearest active member; utilities are minus distance from the resulting weighted median to the voter’s position; and lazy voters prefer inactivity whenever participation does not change the outcome. Compute the pure Nash equilibrium and the resulting outcome.
The expected answer is again Class A: compute the population median, find the sampled proxy closest to it, and output the singleton active set containing that proxy. No search over \(2^n\) participation profiles is needed.
The authors would recognise both questions as their own: the distribution \(f\), nearest-proxy assignment \(J_M\), Voronoi weights, median mechanism, loss function, and lazy-participation game are all taken directly from the paper. Nothing is replaced by a more convenient voting rule. The new contribution is to treat the distribution as a high-multiplicity input and ask for exact or approximate algorithms for the quantities the paper analyses asymptotically.
The weakest point is substantial. The paper already assumes an infinite population distribution, so a bare “continuous mirror” would collide with the paper’s existing model rather than transform a discrete one. Moreover, none of its numbered results is an NP-hardness, polynomial-time, FPT, or similar computational-complexity result. Theorem 4 and Theorem 6 are analytical anchors, not complexity anchors. I would therefore present this as a borderline, Class-A computational companion—not as a flagship continuization result showing that discrete hardness dissolves. I would also avoid Proposition 8 as an anchor: its headline gives \(8/n^2\), while the displayed derivation ends at \(2/n^2\).
The mirror covers the paper’s median results—random proxy participation and lazy strategic participation—but not the mean or binary-issue sections. Further questions would include the complexity of the analogous mean and majority problems, optimal proxy-panel selection rather than random sampling, arbitrary piecewise-rational densities, and proxy costs depending on distance.
The negative case is unusually strong because the paper has already performed the programme’s central move. Section 2 explicitly assumes an infinite population represented by a distribution \(f\), defines the population median, mean, and majority, and computes each proxy’s weight by integrating \(f\) over its Voronoi cell. This is already a continuous-population model, not merely a model with fractional outcomes or stochastic noise. Replacing \(f\) by a finite-support distribution \(\mu\) is only a discretized representation of the paper’s existing object. It does not produce a discrete-to-continuous mirror.
There is also no computational result in the paper to mirror. Theorem 4 is an asymptotic statistical bound, and Theorem 6 is an equilibrium characterization. Neither states a complexity classification, an algorithmic theorem, or an optimization problem whose continuous relaxation could reveal a new computational landscape. The proposed “Continuum Proxy-Median Loss” therefore adds a computational wrapper around an already-continuous analysis rather than continuizing a computational social-choice problem.
For Theorem 4, even the stronger exact-evaluation version is essentially already exposed by Lemma 1. Let \(x^\star\) be the population median, let \(d_1<\cdots<d_q\) be the distinct distances from \(x^\star\) to the finite type locations, and let \(p_r\) be the mass within distance \(d_r\). Then the exact loss is
\[ \sum_{r=1}^{q} d_r^2\left((1-p_{r-1})^n-(1-p_r)^n\right). \]
Sorting the type locations and evaluating these terms computes the quantity directly. This is a useful corollary of the paper’s lemma, but not a new high-multiplicity optimization problem, nor an instance of the programme’s characteristic exponentially large LP and pricing bottleneck. Asking for optimal panel selection or more complicated proxy costs could become interesting, but it would introduce a new intervention that the paper does not study; it would not mirror Theorem 4.
Theorem 6 fares worse. Its strategic players are the finitely many sampled, named voters \(N\). The distribution \(f\) only determines the weights assigned to them. Thus the proposed equilibrium problem is literally the paper’s \(P+L\) game with \(f\) encoded as \(\mu\), not a continuum version of that game.
Trying to make participation itself continuous exposes a substantive obstruction. An individual of measure zero cannot pivot a mass-weighted median or alter a Voronoi partition, so the pivotality argument driving Theorem 6 disappears; under lazy bias, participation consequently risks collapsing. If instead each type controls its entire mass, the strategic players become the \(\tau\) types, producing a different type-level game rather than a high-multiplicity version of the paper’s individual participation model. Retaining the finite proxy panel avoids that degeneration, but then the population has not been continuized in the strategic object.
The honest conclusion is that proxy voting might inspire new computational models, but this paper supplies no worthwhile continuous mirror for the programme: its population is already continuous, its anchors are not computational results, and the proposed versions either restate the paper or change the strategic problem fundamentally.
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.