| paper | The Metric Distortion of Randomized Social Choice Functions: C1 Maximal Lottery Rules and Simulations |
| authors | — |
| venue | AAMAS 2025 |
| filed under | voting · distortion |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Proposition 2
statement extracted from the paper’s text layer
Given \(m\) alternatives \(X\), an explicit finite set \(T\) of complete ranking types with rational masses \(\mu_t\) summing to \(1\), a rational lottery \(p\in\Delta(X)\), and \(x^\ast\in X\), compute \(\sup_d \frac{\int_\Omega\sum_{x\in X}p(x)d(v,x)\,d\lambda(v)}{\int_\Omega d(v,x^\ast)\,d\lambda(v)}\), where \(\Omega\) is atomless, \(\lambda(\Omega_t)=\mu_t\), and \(d\) ranges over measurable metrics on \(\Omega\cup X\) consistent almost everywhere with each type's ranking, using the paper's \(0/0\) and positive-over-zero conventions.
A type-compressed LP with variables \(D_{t,x}\) and \(\theta_x\), normalization \(\sum_t\mu_tD_{t,x^\ast}=1\), inequalities \(D_{t,x^\ast}\ge\frac12(\theta_x-\theta_y)\) when \(x\succeq_t y\), \(D_{t,x}\le D_{t,x^\ast}+\theta_y\), and \(D_{t,x}+D_{t,x^\ast}\ge\theta_x\), maximizing \(\sum_t\mu_t\sum_xp(x)D_{t,x}\). The model has \(O(\tau m^2)\) constraints and retains adversarial hidden metric heterogeneity within ranking types.
The exact equality between the atomless metric supremum and the type-compressed LP is not proved in the paper, so within-type metric heterogeneity remains a genuine fidelity obligation.
fatal: False
The mirror covers Proposition 2 and the LP-based finite-profile metric-distortion evaluation, while leaving Theorem 1's distortion bounds, Theorems 2 and 3's asymptotic expectations, and the simulations as supporting results.
There is a credible, but deliberately narrow, continuous mirror. My lead anchor is Proposition 2, proved in this paper (using biased metrics from Charikar and Ramakrishnan [15] as an ingredient). Proposition 2 states that LP 1 exactly computes \(\operatorname{dist}(p,R,x^\ast)\), the worst-case metric distortion of a given lottery \(p\) against a fixed alternative \(x^\ast\), with \(O(nm^2)\) constraints. If the LP is unbounded, the distortion is infinite.
Theorem 1 is an important distortion theorem, but not a computational-complexity anchor under the programme’s strict standard; Theorems 2 and 3 are likewise asymptotic expectation results. I would use them as supporting evidence, not pretend that they establish separate algorithmic mirrors.
My proposed problem is Continuous Worst-Case Metric-Distortion Evaluation, \(\mathrm{CMD}_\infty\).
An instance consists of \(m\) alternatives \(X\), a finite set \(T\) of complete ranking types, rational masses \(\mu_t\ge 0\) with \(\sum_{t\in T}\mu_t=1\), a rational lottery \(p\in\Delta(X)\), and a designated alternative \(x^\ast\in X\). The population is an atomless measure space \(\Omega\), partitioned into sets \(\Omega_t\) of masses \(\mu_t\); every voter in \(\Omega_t\) reports ranking \(\succ_t\).
A feasible witness is a measurable metric \(d\) on \(\Omega\cup X\) such that \(x\succ_t y\) implies \(d(v,x)\le d(v,y)\) for almost every \(v\in\Omega_t\). Define \(\operatorname{sc}_d(p)=\int_\Omega\sum_{x\in X}p(x)d(v,x)\,d\lambda(v)\) and \(\operatorname{sc}_d(x^\ast)=\int_\Omega d(v,x^\ast)\,d\lambda(v)\). The problem asks for the exact value
\(\mathrm{CMD}_\infty(\mu,p,x^\ast)=\sup_d \operatorname{sc}_d(p)/\operatorname{sc}_d(x^\ast)\),
with the same \(0/0\) and positive-over-zero conventions as the paper. For the full distortion of \(p\), solve this problem for every \(x^\ast\) and take the maximum.
The continuous counterpart of LP 1 has variables \(D_{t,x}\ge 0\), representing type-level average distances, and \(\theta_x\ge 0\). Set \(\theta_{x^\ast}=0\), impose \(\sum_t\mu_tD_{t,x^\ast}=1\), and, for every type \(t\), impose the paper’s three families of inequalities:
\(D_{t,x^\ast}\ge \tfrac12(\theta_x-\theta_y)\) whenever \(x\succeq_t y\);
\(D_{t,x}\le D_{t,x^\ast}+\theta_y\) whenever \(x\succeq_t y\);
\(D_{t,x}+D_{t,x^\ast}\ge\theta_x\) for every \(x\).
The objective is \(\sum_t\mu_t\sum_xp(x)D_{t,x}\). The expected theorem is that this type-compressed LP has optimum exactly \(\mathrm{CMD}_\infty(\mu,p,x^\ast)\), including the possibility of an unbounded value. It has \(O(\tau m^2)\) constraints and rational coefficients, so it should be solvable in polynomial time in \(m\), \(\tau\), and the encoding length \(L\). Thus I expect this mirror to be Class A: tractable.
The high-multiplicity regime is plausible. Consider a large public-choice electorate selecting one of a fixed catalogue of facilities, policies, or services. Millions of residents may fall into a modest number of stable preference segments—same complete ranking because of common geography, transport constraints, demographic profile, or service needs—so \(N\gg\tau\). The mass \(\mu_t\) is the fraction of residents in segment \(t\). The lottery remains exactly the paper’s lottery over alternatives; only the voter population is continuized. The latent metric is still adversarial and unobserved, as in the paper. Agents of one ranking type need not be forced to have identical hidden cardinal distances: the atomless model must allow metric heterogeneity within a type, just as the discrete worst-case model allows different voters with the same ranking to have different metric locations.
The bridge is especially clean. If \(\mu_t=a_t/N\), replace each type mass by \(a_t\) cloned voters. Dividing the finite LP by \(N\) gives the continuous LP. Conversely, a rational continuous LP solution can be denominator-cleared into a finite repeated-type instance. Candidate identities, rankings, lottery probabilities, metric consistency, normalization, and distortion ratios are all preserved. This is a direct high-multiplicity mirror, not a fractional-outcome reformulation.
The paper’s own Theorem 2 and Theorem 3 make the regime recognizable: the authors already study what happens as \(n\) becomes large under impartial culture, including convergence of expected distortion for randomized rules. The proposed problem simply makes the repeated population explicit and asks for the computational value of the adversarial metric optimization rather than its asymptotic expectation.
The mirror covers Proposition 2 and the paper’s LP-based simulation methodology. It does not claim to turn Theorem 1’s \(4\)-distortion result into a new complexity theorem. If \(p\) is generated by a continuous C1ML rule, one can first compute a C1 maximal lottery from the mass-weighted majority relation and then invoke \(\mathrm{CMD}_\infty\); however, lottery selection and tie-breaking should be treated as a separate specification.
My weakest point is that the type-compressed equality is not written in the paper. Proposition 2 is stated with one distance vector per named voter, and the continuous proof must show that taking the supremum over atomless metrics commutes with aggregation by ranking type. A mirror that forced every member of a type to share one cardinal distance vector would be too weak and potentially non-faithful. The positive case therefore depends on proving the same two directions as Proposition 2: every continuous metric induces a feasible type-level LP point, and every feasible type-level point can be realized by a measurable metric population. That is a genuine proof obligation, but it is a focused extension of the paper’s existing LP argument rather than a change to the social-choice problem.
Further questions are whether the full C1ML evaluation problem remains polynomial under nonunique maximal lotteries, how accurately finite \(N\)-voter clone instances approximate the continuous value, and what happens when the ranking distribution is given succinctly rather than by an explicit list of \(\tau\) types.
Under the programme’s strict source gate, this paper has no suitable anchor. Theorem 1 is a distortion bound, Theorems 2 and 3 are asymptotic expectation statements, and the simulations are empirical. Proposition 2 is the only plausible exception, but it proves an LP characterization for a finite profile, not the complexity of a named computational problem. The claim that LP 1 is “fast” does not itself establish a new computational-social-choice task.
Even granting Proposition 2 as an anchor, the proposed mirror has a serious type-model problem. In this paper, \(d(v,x)\) is precisely the cost incurred by voter \(v\), and the metric-distortion objective optimizes over these costs. Two voters with the same ranking may have entirely different distance vectors. Thus the proponent’s “ranking type” is not a complete ChoCo type: it omits a parameter the problem uses. If costs are included in the type, the adversarial metric may give every voter a distinct type, so \(N\gg\tau\) is not guaranteed. If costs are supplied as part of the input, the problem is no longer metric-distortion evaluation, since the metric is no longer worst-case hidden. Restricting the adversary to finitely many cardinal types changes the feasible metric family.
There is a best repair, but it reveals how little population structure is doing. LP 1 is separable across voters of the same ranking type. Averaging their feasible distance vectors preserves every constraint, and repeating a type-level vector recovers a finite solution. Hence the proposed weighted LP is probably exactly correct. But this is merely deletion of repeated rows from an already polynomial finite LP:
\[ \sum_{v\in V}(\cdots) \quad\longrightarrow\quad \sum_t \mu_t(\cdots). \]
The atomless society, measurable metric, and continuous population contribute no new computational object; the interesting optimization remains the paper’s existing finite metric LP. This is a degenerate high-multiplicity quotient, not a continuous analogue in which population continuity creates a new complexity landscape.
A stronger reformulation cannot rescue the paper without changing the target. One could optimize over lotteries, over C1 maximal-lottery selections, or over distributions of complete metric types, but none is a computational result asserted here. Alternatively, one could require all members of a ranking segment to share cardinal costs; that gives a clean finite-type model, but it restricts the paper’s worst-case metrics. The fact that separability may make that restriction value-preserving would be a new symmetry theorem about certificates, not a direct mirror of the paper’s stated problem.
Theorem 2 and Theorem 3 do not provide additional anchors. Their \(n\to\infty\) analysis concerns random finite profiles under impartial culture, not computation over a continuous society; turning it into an expectation over random mass distributions would be a noise or probabilistic-population model, outside ChoCo’s scope.
So the negative case is strongest as a source-and-fidelity objection: the paper supplies no genuine computational-complexity result, and its only algorithmic proposition collapses to a weighted restatement of an existing finite LP while its latent costs prevent a straightforward complete-type interpretation. I would not call that an airtight impossibility claim. If the programme accepts LP characterizations as computational anchors and regards observable rankings as sufficient types despite hidden metric heterogeneity, Proposition 2 survives and gives a legitimate, though very modest, Class-A mirror.
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.