| paper | Computational Aspects of Distortion |
| authors | — |
| venue | AAMAS 2024 |
| filed under | voting · distortion |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 2
statement extracted from the paper’s text layer
Given alternatives \(C\), finite ranking types \(T\subseteq S_C\), and rational masses \(\mu\in\Delta(T)\), compute a lottery \(p^\star\in\Delta(C)\) minimizing \(\delta(p,\mu)=\sup_u\max_{a\in C}W_u(a)/W_u(p)\), together with the optimum \(\delta^\star\), where \(W_u(a)=\sum_{t\in T}\int_0^{\mu_t}u_{t,z}(a)\,dz\) and each utility field is unit-sum and consistent with its ranking type; equivalently, by Theorem 1, the adversary may allocate each ranking mass among the finite top-\(k\) types \((t,k)\).
A finite-type atomless electorate with ranking masses \(\mu\), extreme utility types \((t,k)\), lottery decision \(p\in\Delta(C)\) or scaled variables \(\beta=\delta p\), and worst-case utilitarian distortion \(\max_a W_u(a)/W_u(p)\).
The initial formulation treats rankings rather than complete utility-bearing types as the population types, so a fully faithful model should expose the adversarial allocation over \((t,k)\) extreme types; this limits novelty but does not invalidate the mirror.
fatal: False
The mirror covers the instance-optimal lottery and fixed-lottery distortion results in Theorems 2 and 3. It leaves the exact worst-case distortion of RPSRs in Section 4, the conjectured hardness of its quadratic program, and the paper's structural results outside.
The strongest positive case is a direct high-multiplicity mirror of the paper’s ordinal-utilitarian distortion problem. It is not a claim that randomization is newly continuous: the lottery over alternatives is already present in the paper. The continuized object is the electorate itself.
My lead anchor is Theorem 2, proved in this paper. It states that, given a preference profile, an LP of size \(O(nm)\) computes the instance-optimal lottery and its distortion.
Define a continuous instance as \(C\), a finite set \(T\subseteq S_C\) of complete ranking types, and a rational mass vector \(\mu\in\Delta(T)\). Type \(t\) represents a fraction \(\mu_t\) of an atomless electorate. Its members have the same ordinal information, while their hidden unit-sum utilities may vary arbitrarily among the utilities consistent with \(t\), exactly as in the paper.
For a measurable utility field \(u\), let
\[ W_u(a)=\sum_{t\in T}\int_0^{\mu_t}u_{t,z}(a)\,dz \]
be the social welfare of alternative \(a\). For a lottery \(p\in\Delta(C)\), let \(W_u(p)=\sum_{a\in C}p_aW_u(a)\). The continuous problem is:
\[ \textsc{Continuum-Instance-Optimal-Distortion} \]
Given \((C,T,\mu)\), compute an exact pair \((p^\star,\delta^\star)\) such that
\[ p^\star\in\arg\min_{p\in\Delta(C)} \sup_u \frac{\max_{a\in C}W_u(a)}{W_u(p)} \]
and
\[ \delta^\star= \sup_u \frac{\max_{a\in C}W_u(a)}{W_u(p^\star)}. \]
Here \(u\) ranges over utility fields consistent with the ranking type of every member. As in the paper, one may take the closure of the strict-consistency sets; Theorem 1 shows that a worst case is attained by dichotomous utilities
\[ \phi_{t,k}(a)= \begin{cases} 1/k,&\text{if a is among the top k alternatives of t},\\ 0,&\text{otherwise}. \end{cases} \]
Thus the continuous problem is not replacing the paper’s utility model by a simpler one. The dichotomous reduction is a theorem of the paper.
If \(\beta_a=\delta p_a\), the mass version of the paper’s LP can be written through constraints of the form
\[ \sum_{t\in T}\mu_t \max_{k\in[m]} \frac{ \mathbf 1[\operatorname{rank}_t(a)\le k] -\sum_{j=1}^k\beta_{t(j)} }{k} \le 0 \qquad(a\in C), \]
with \(\beta_a\ge0\), minimizing \(\sum_a\beta_a\). The paper’s partial-maximum construction linearizes these constraints with \(O(\tau m)\) variables and constraints, where \(\tau=|T|\). Therefore the continuous problem is solvable in time polynomial in \(m\), \(\tau\), and the encoding length of \(\mu\). It is a Class A problem.
The natural regime is a large election or public consultation with a small or moderate shortlist and many repeated ordinal ballots: for example, millions of voters choosing among \(m=5\)–\(20\) candidates, but only \(\tau\) distinct complete rankings. The input records the fractions of voters submitting each ranking, not the names of the voters. This is a genuine high-multiplicity setting: if \(\mu_t=n_t/n\), replacing each type by \(n_t\) clones recovers a finite profile, and all welfare ratios are unchanged because both numerator and denominator scale by \(n\). Conversely, every finite profile induces such a rational \(\mu\).
The second anchor is Theorem 3, also proved in this paper. It gives an \(O(nm\log(nm))\)-time algorithm for computing the distortion of a fixed lottery on a given preference profile. Its continuous mirror is:
\[ \textsc{Continuum-Fixed-Lottery-Distortion} \]
Given \((C,T,\mu)\) and a rational lottery \(p\in\Delta(C)\), compute exactly
\[ \delta(p,\mu)= \sup_u \frac{\max_{a\in C}W_u(a)}{W_u(p)}. \]
A valid solution consists of \(\delta(p,\mu)\) and, optionally, a worst-case witness: an alternative \(a^\star\) and one top-\(k_t\) dichotomous utility \(\phi_{t,k_t}\) for each type. Lemma 1 supplies the relevant certificate subproblem: for a proposed threshold \(\rho\), test in linear time whether \(\delta(p,\mu)\le\rho\), and if not, return a violating utility field.
Duplicate agents again collapse exactly. The paper’s threshold expression becomes
\[ \sum_{t\in T}\mu_t \max_{k\in[m]} \frac{ \mathbf 1[\operatorname{rank}_t(a)\le k] -\rho\sum_{j=1}^kp_{t(j)} }{k}. \]
Scanning types rather than individuals gives the natural bound \(O(\tau m\log(\tau m))\), up to rational-arithmetic costs. This is also Class A.
These mirrors should be recognizable to the authors: they retain the same alternatives, ordinal input, unit-sum cardinal uncertainty, randomized decision, and welfare-ratio objective. Only the population representation changes from an explicit list of agents to a distribution over ranking types. Indeed, the paper’s large Preflib experiments and its emphasis on profiles with many voters make this regime especially plausible.
I would not anchor a third mirror on Section 4. Program Q is a promising continuous-population extension, but the paper gives no numbered complexity theorem for it and only conjectures NP-hardness. Theorems 1–3 provide the honest positive case; Section 4 can generate follow-up questions about whether exact worst-case distortion of an RPSR remains tractable when the population is given by \(\mu\), or whether that becomes a continuum-specific Class C problem.
The weakest point is that this mirror is mathematically modest. Theorem 2 already gives a polynomial algorithm on an explicit profile, so the continuized version mainly exposes an input-compression and high-multiplicity interpretation rather than unlocking a new algorithmic phenomenon. Also, because the paper’s lottery \(p\) is already fractional, the only genuinely new continuous object is \(\mu\). If the programme demanded every mirror to produce new complexity rather than a faithful mass formulation, this case would be weak. Under the programme’s stated standard, however, it is a clean direct mirror of two named, proved computational results, with an exact two-way finite/high-multiplicity dictionary and a clear Class A prediction.
The strongest negative case is that the proposed mirror does not quite satisfy ChoCo’s own notion of a type. In this paper, an agent’s utility vector is part of what determines distortion. Two agents with the same ranking but different hidden cardinal utilities are therefore not identical in every respect relevant to the problem. The proponent’s \(u_{t,z}\) quietly leaves this individual-level heterogeneity in place: \(t\) is only an observed ranking, while \(z\) indexes a continuum of hidden utility types. Thus \(\mu\) is not a distribution over complete voter types in the programme’s sense; it is a weighted ranking profile equipped with an adversarial utility field.
There are only three ways to repair this. One can include utilities in the type, but then the type space is generally continuous rather than the finite \(T\) assumed by the central model. One can fix one utility vector per ranking type, but then the problem is no longer the paper’s worst-case distortion problem. Or one can retain a correspondence of possible utilities for each ranking type, in which case the object is a robust weighted-profile problem rather than an ordinary continuous society.
That objection does not ultimately defeat the best version, however. Theorem 1 supplies exactly the required repair: for any fixed lottery, the adversary may be restricted to finitely many ranking–top-\(k\) extreme types. A robust high-multiplicity model with ranking masses and local top-\(k\) uncertainty is mathematically faithful, and the separability of the worst-case objective means that all voters of one ranking can even choose the same worst-case extreme utility. The objection therefore attacks the proponent’s presentation, not the existence of a sensible mirror.
The same conclusion applies to Theorem 3. Its fixed-lottery distortion depends on the electorate only through weighted sums of per-ranking worst-case terms:
\[ \max_{a\in C}\sum_{t\in T}\mu_t \max_{k\in[m]} \frac{\mathbf 1[\operatorname{rank}_t(a)\le k] -\rho\sum_{j=1}^{k}p_{t(j)}}{k}. \]
There is no identity-sensitive quantity here: welfare is additive, the uncertainty set factors by agent, and duplication changes nothing except the representation. That makes it difficult to find a genuine obstruction based on multiplicity, identity, or degeneration. The fixed-lottery mirror is a legitimate Class A high-multiplicity problem.
The best remaining criticism is one of worth rather than validity. The paper’s objectives already factor exactly through the ranking histogram, and its algorithms already process an explicit profile in time polynomial in the number of listed agents. Passing from the list to \(\mu\) exposes a compressed encoding, but introduces no mass-transfer decision, no new continuous geometry, and no population-dependent separation problem. Theorem 2’s LP and Theorem 3’s scan simply receive weights. This makes the mirrors unusually modest: they are canonical weighted-profile formulations rather than instances where continuization reveals a new algorithmic boundary.
That criticism must be used carefully. It cannot be stated as “continuization does not help,” since a dull Class A answer is still a valid result under the programme. Nor can high-multiplicity work be treated as prior-art collision. A large election with millions of voters and a small number of repeated ballots is plainly a sensible regime, and these mirrors do provide an exact high-multiplicity dictionary.
Indeed, Section 4 makes the negative case weaker still. Its vector \(\alpha\) is already a distribution over finitely many canonical agent types, and Program Q optimizes the worst-case distortion over that population distribution. Although the paper gives no polynomial complexity theorem for Q, this is already a plausible continuous-population formulation rather than evidence that no such formulation exists.
So the strongest case against is that the two proposed anchors are population-weighted restatements of anonymous robust voting problems, and that the proponent initially treats incomplete ranking types as complete types. Neither point survives the best repair using the paper’s dichotomous-utility theorem. I cannot honestly support the universal claim that no worthwhile continuous mirror exists: both Theorem 2 and Theorem 3 admit clean, natural high-multiplicity mirrors, even if their contribution to ChoCo would be comparatively modest.
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.