| paper | On the Potential and Limitations of Proxy Voting: Delegation with Incomplete Votes |
| authors | — |
| venue | AAMAS 2024 |
| filed under | voting · incomplete-info |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 3.7
statement extracted from the paper’s text layer
Given \(m\) proposals, an explicit finite support \(\Theta\) of consistent types \(\theta=(v,\widehat v)\in\{0,1\}^m\times\{0,1,\bot\}^m\), rational masses \(\mu_\theta\ge0\) with \(\sum_{\theta\in\Theta}\mu_\theta=1\), and \(q\in[0,1]\), decide whether some ballot \(t\in\{0,1\}^m\) makes the Approval Voting winner \(w_\mu(t)\), formed by majority-agreement attraction \(d(\theta,t)=|\{j\in R_\theta:t_j\ne\widehat v_j\}|\le\lfloor |R_\theta|/2\rfloor\) with \(R_\theta=\{j:\widehat v_j\ne\bot\}\), satisfy \(U_\mu(w_\mu(t))\ge q\), where attracted mass votes \(t\), unattracted mass contributes its revealed approvals, \(U_\mu(j)=\sum_{\theta\in\Theta}\mu_\theta v_{\theta,j}\), and ties favor larger \(U_\mu\).
High-multiplicity approval voting with incomplete binary types: \(\mu\) is mass over complete \((v,\widehat v)\) types, the decision variable is the advertised ballot \(t\), attraction is a Hamming-threshold predicate, scores are mass-weighted, and the objective is intrinsic approval mass of the winner.
Rational mass inputs can be denominator-cleared into finite clone electorates, so the anchor establishes inherited high-multiplicity hardness rather than a continuum-specific phenomenon.
fatal: False
The mirror covers the one-dRep NP-hardness of Theorem 3.7, the exact two-dRep result of Theorem 3.8, and the coherent one-dRep \(3\)-approximation of Corollary 3.3; it leaves the remaining bounds, impossibility results, experiments, and information or rationality extensions untouched.
There is a credible continuous mirror here. My strongest anchor is Theorem 3.7; the paper’s proxy-selection problem already has the right population-level structure, and replacing voter counts by masses preserves both its semantics and its hardness. I would also carry over Theorem 3.8 and Corollary 3.3 as positive anchors.
The natural regime is blockchain or civic-governance voting with many token holders and many proposals. Millions of holders may fall into a much smaller number of recurring types: the same issue interests, the same revealed proposals, the same revealed approval answers, and the same latent intrinsic approval vector. A type must include both the intrinsic vector and the revealed vector, because those determine every quantity used by the paper. Thus a type is
\[ \theta=(v,\widehat v)\in \{0,1\}^m\times\{0,1,\bot\}^m, \]
with \(\widehat v_j\in\{\bot,v_j\}\). A continuous society is a rational distribution \(\mu\) over a finite explicit support \(\Theta\) of such types. The number of actual voters may be enormous, while \(|\Theta|=\tau\) is comparatively small.
For a type \(\theta\), let \(R_\theta=\{j:\widehat v_j\neq\bot\}\). Retaining the paper’s majority-agreement rule, a dRep ballot is still a binary vector \(t\in\{0,1\}^m\), and it attracts type \(\theta\) exactly when
\[ d(\theta,t)=|\{j\in R_\theta:t_j\neq \widehat v_j\}| \le \left\lfloor \frac{|R_\theta|}{2}\right\rfloor . \]
The attracted population is mass, not a set of named people. Define intrinsic approval mass and the election score by
\[ U_\mu(j)=\sum_{\theta\in\Theta}\mu_\theta v_{\theta,j} \]
and
\[ S_{\mu,t}(j) = \sum_{\theta:\theta\text{ attracted by }t}\mu_\theta t_j + \sum_{\theta:\theta\text{ not attracted by }t} \mu_\theta\mathbf 1[\widehat v_{\theta,j}=1]. \]
The elected proposal \(w_\mu(t)\) maximizes \(S_{\mu,t}\), with the paper’s tie-breaking rule favouring the proposal with largest \(U_\mu(j)\). The objective is to maximize \(U_\mu(w_\mu(t))\), equivalently to approximate
\[ U_\mu^\star=\max_{j\in C}U_\mu(j). \]
This is recognisably the paper’s problem: Approval Voting, incomplete approval vectors, Hamming-threshold delegation, advertised full ballots, and intrinsic approval as the social objective are all unchanged. Only the population representation changes from individual voters to type masses.
My lead anchor is Theorem 3.7, proved in this paper. It states that the decision variant of proxy selection is NP-hard, even for majority agreement and one dRep. The reduction uses the externally established NP-hardness of minimax approval voting, cited as [15,27], but Theorem 3.7 itself is proved here.
The corresponding continuous problem is Continuous One-dRep Proxy Selection:
Given \(m\), an explicit rational distribution \(\mu\) over voter types \(\Theta\), majority agreement, one available dRep, and a rational threshold \(q\in[0,1]\), decide whether there exists \(t\in\{0,1\}^m\) such that
\[ U_\mu(w_\mu(t))\ge q. \]
A solution is the advertised ballot \(t\). This is precise, finite, and directly computable from the type list. It is also a genuine high-multiplicity problem: \(\mu_\theta\) may represent millions of voters, and the input need not list them individually.
Theorem 3.7 transfers immediately. Given any discrete instance with \(N\) voters, group identical voters into types and assign
\[ \mu_\theta=\frac{\#\{\text{voters of type }\theta\}}{N}. \]
Every proxy-election score is divided by \(N\), while the winner and delegation decisions are unchanged. A discrete threshold \(r\) becomes \(q=r/N\). Hence the discrete instance is an exact special case of the continuous problem, and Continuous One-dRep Proxy Selection is NP-hard unless \(\mathrm{P}=\mathrm{NP}\). This is Class B: the combinatorics live in the proposal coordinates and the advertised ballot, so hardness survives continuization.
The important point is that this is not merely a rescaling trick. The continuous problem also admits instances with arbitrary rational masses that have no natural small-\(N\) interpretation and are most naturally understood as distributions of voter types. The discrete embedding establishes hardness, while the distributional formulation is the broader object.
A second anchor is Theorem 3.8, proved in this paper: with \(\lambda=2\), proxy selection under majority agreement can be optimally solved. Its continuous counterpart is Continuous Two-dRep Optimal Proxy Selection:
Given a rational type distribution \(\mu\) over \(\Theta\), majority agreement, and two available dReps, output ballots \(t^{(1)},t^{(2)}\in\{0,1\}^m\) such that the induced winner \(w_\mu(t^{(1)},t^{(2)})\) satisfies
\[ U_\mu\bigl(w_\mu(t^{(1)},t^{(2)})\bigr)=U_\mu^\star. \]
If both dReps attract the same type, the continuous problem can use the paper’s “any attracted dRep” convention, represented formally by assigning that type’s mass between the two dReps; a fixed priority rule would give a stricter variant. The solution therefore consists of the two advertised ballots together with the permitted induced delegation assignment.
I expect this result to lift to Class A. The proof’s reasoning is combinatorial and score-based: it uses only which types are attracted and which proposals the dReps approve. Replacing voter counts by rational masses turns every count into a weighted sum and preserves the inequalities. The resulting algorithm should run in time polynomial in \(m\), \(\tau\), and the encoding length of the masses. This gives a particularly useful mirror: the one-dRep problem is hard, but adding a second representative makes the continuous problem exactly solvable in the majority-agreement regime.
A third, weaker but still worthwhile anchor is Corollary 3.3, also obtained in this paper from Theorem 3.2. It states that one dRep gives a \(3\)-approximation on coherent instances under majority agreement.
The corresponding Continuous Coherent Proxy-\(3\) problem is:
Given a rational distribution \(\mu\) over voter types such that every type has the same revealed set \(R\), majority agreement, and one dRep, output \(t\in\{0,1\}^m\) satisfying
\[ U_\mu(w_\mu(t))\ge \frac{1}{3}U_\mu^\star. \]
Here coherence has exactly the paper’s meaning: all voters have investigated the same proposals, although they may have different revealed approval answers and different intrinsic opinions on unrevealed proposals. This is a plausible governance regime when every holder is shown the same proposal slate or when a large organization asks its members to evaluate a common set of initiatives. Again, the paper’s cardinality proof should lift by replacing counts with masses. I would classify this as Class A, subject to proving the weighted version formally.
These mirrors cover the paper’s central computational content, not its experiments or every possible extension. They do not change the voting rule, replace incomplete preferences by complete ones, or make the dReps themselves continuous. The only continuous object is the population. The dRep action remains a binary ballot because that is the action studied by the authors.
The main further questions are whether the one-dRep problem becomes tractable for bounded \(\tau\), restricted revealed-set structure, or approximate coherence; whether the hardness of Theorem 3.7 persists when \(N\gg\tau\) in a strongly compressed regime; how the picture changes for \(k>0\) and more than two dReps; and whether heterogeneous thresholds \(k_\theta\), noisy intrinsic preferences, or fractional delegation produce LP, parameterized, or approximation algorithms.
The weakest point is empirical rather than semantic. The paper’s MovieLens-style voters may have highly individual latent approval vectors, so their number of exact types could be close to the number of voters. Moreover, Theorem 3.7’s reduction does not demonstrate continuum-specific hardness or an algorithmic speedup from high multiplicity; it establishes hardness transfer. The positive case therefore depends on a scenario such as repeated governance cohorts, organizational blocs, or standardized proposal-interest profiles where exact types genuinely repeat. That is a real modelling obligation. But it does not undermine the mirror itself: the paper already treats weighted voters as equivalent to voter copies, and its definitions are expressed entirely through type-level agreement tests and aggregate approval scores. Under a credible high-multiplicity governance regime, this is a faithful continuous population formulation of the authors’ problem.
I cannot honestly make the requested universal negative case. Theorem 3.7 alone gives a credible mirror, and Corollary 3.3 reinforces it. The strongest objection is that the proposed continuum is merely a weighted high-multiplicity restatement, but ChoCo explicitly treats that as a legitimate object.
For Theorem 3.7, the transfer is exact. A complete type must be \(\theta=(v,\widehat v,k)\), including the latent approval vector, revealed vector, and threshold. Given \(N\) discrete voters, assign mass \(\mu_\theta=a_\theta/N\) to each type occurring \(a_\theta\) times. For every advertised ballot \(t\), attraction is constant within a type, every approval score is divided by \(N\), and the winner is unchanged. The threshold \(r\) becomes \(q=r/N\). Thus the paper’s NP-hardness gives NP-hardness of the rational-mass problem.
The negative response would be that this hardness is driven entirely by the \(m\)-coordinate ballot and minimax-approval structure, not by population multiplicity, and that the reduction may contain almost as many types as voters. That is a fair limitation: it establishes Class B, not continuum-specific hardness or a compact algorithm. But Class B is explicitly within the programme’s scope. Moreover, every hard instance can be populated by arbitrarily many clones, and repeated governance blocs or standardized organizational cohorts provide a plausible high-multiplicity interpretation. The paper itself says weighted voters can be represented by copies. This objection therefore limits novelty, not validity.
Theorem 3.8 is also difficult to defeat. Its proof is based on typewise agreement and additive approval scores, so replacing counts by rational masses preserves the argument. If several dReps attract one type, allowing a mass split is not necessarily an illicit relaxation: after clearing denominators, it is exactly an assignment of sufficiently many identical clones. If desired, one can impose a fixed priority rule instead; the proponent should prove that version rather than silently introduce arbitrary fractional delegation, but this is a repairable semantic detail, not a fundamental obstruction.
Corollary 3.3 transfers even more cleanly. Coherence means that all voters share one revealed set, so in the continuous version the entire society has common revealed-set structure, while intrinsic approval answers may vary across types. The proof’s cardinalities become masses, and normalizing total mass to \(1\) preserves the approximation ratio. A repeated proposal slate in a large organization or governance system is a credible high-multiplicity regime. This is a genuine Class-A-style weighted mirror, even if the algorithmic insight is inherited rather than new.
The proponent does overstate two points. Arbitrary rational distributions are not fundamentally beyond finite populations: denominator clearing produces a finite clone population. And MovieLens-style latent preferences may have nearly one distinct type per user, making the compression practically useless. Those are real modelling and representation caveats. They do not defeat a better scenario based on repeated blocs, nor do they invalidate the exact high-multiplicity formulation.
So the best negative case is that the mirror contributes little beyond weighted proxy selection, and that the strongest hardness result is population-insensitive. Under the stated ChoCo rules, however, that is not enough: inherited high-multiplicity hardness is supporting evidence, and a dull continuous answer remains a valid answer. I would therefore reject a universal “no mirror” verdict; the proponent’s case is imperfect, but Theorem 3.7 survives decisively, with Corollary 3.3 as a second surviving anchor.
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.