| paper | The Distortion of Distributed Metric Social Choice |
| authors | Elliot Anshelevich, Aris Filos-Ratsikas, A. Voudouris |
| venue | WINE 2021 |
| filed under | voting · distortion |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
The proposed high-multiplicity formulation is coherent, and both stated theorems plausibly extend to mass distributions. However, the paper's anchors are distortion bounds and impossibility results about mechanisms, which the gate explicitly excludes from the required computational character absent an algorithmic or complexity claim. Thus no anchor satisfies both bits, so the mirror grades red.
fails bit a — no named computational result to mirror
The named anchors are excluded distortion or rule-impossibility results, so the coherent mass formulation has no qualifying computational result from this paper to mirror.
fatal: True
The proposed mirror covers the line-metric \(\mathrm{MAX}\circ G\) results, especially Theorems 4.8 and 4.11, but it does not establish a qualifying computational mirror for the paper's other distortion bounds.
This paper supports a genuine continuous-population mirror, although the claim must be stated carefully: it is a mirror of distributed metric mechanism design and distortion, not of a named NP-hardness or polynomial-time theorem. The paper contains no theorem explicitly asserting NP-hardness, membership in \(P\), W[1]-hardness, or FPT; its named anchors are distortion bounds.
The natural mirror keeps the finite candidate set, the finite set of districts, the line or general metric, and the two-stage decision process. Only the population becomes continuous.
Fix alternatives \(A=\{a_1,\ldots,a_m\}\) at positions on a line, and districts \(d\in\{1,\ldots,k\}\). A voter type is a complete metric profile: equivalently, a location \(x_\theta\) together with the distances \((|x_\theta-a|)_{a\in A}\). Let \(\mu_{d,\theta}\) be the fraction of district \(d\)'s population having type \(\theta\). A district may have millions of residents but only \(\tau\) distinct types, with \(n\gg k\tau\). District membership is part of the agent's role, since it determines which local aggregation rule is applied.
For \(G\in\{\mathrm{AVG},\mathrm{MAX}\}\), define
\[ C_d^{\mathrm{AVG}}(a)=\sum_{\theta}\mu_{d,\theta}|x_\theta-a|, \qquad C_d^{\mathrm{MAX}}(a)=\max_{\theta:\mu_{d,\theta}>0}|x_\theta-a|. \]
The paper's \( \mathrm{MAX}\circ G \) objective becomes
\[ \Phi_G(a)=\max_{d} C_d^G(a). \]
A distributed mechanism consists of local maps \(L_d\), producing representatives \(y_d=L_d(\mu_d)\), followed by a global map \(H\) that sees only the representatives and returns \(w=H(y_1,\ldots,y_k)\). Its distortion is
\[ \sup_{\mu} \frac{\Phi_G(w)}{\min_{a\in A}\Phi_G(a)}. \]
This is not outcome-space continuization: \(A\), \(k\), and the metric remain finite/discrete objects. The sums over named agents are replaced by type-mass averages and maxima. Rational mass vectors recover ordinary finite instances, while duplicating every agent \(r\) times leaves the objective unchanged. Thus this is directly a high-multiplicity relaxation.
The most compelling anchor is Theorem 4.11, proved in this paper. It states:
For every \(G\in\{\mathrm{AVG},\mathrm{MAX}\}\), every distributed mechanism has \( (\mathrm{MAX}\circ G) \)-distortion at least \(1+\sqrt{2}\), even when the metric is a line.
My lead continuous problem would therefore be:
\[ \textsc{Continuous Distributed }(\mathrm{MAX}\circ G)\textsc{-Design}. \]
An instance consists of finite candidate positions on a line, \(k\) districts, and finite-support distributions \(\mu_1,\ldots,\mu_k\) over voter types. The question is to determine the minimum worst-case distortion achievable by any two-stage distributed mechanism, or, equivalently, whether a mechanism with distortion at most a given \(\rho\) exists. A solution must specify the local representative rules and the global rule, subject to the information restriction that local rules operate district by district and the final rule sees only the representatives.
The lower-bound proof survives unchanged. Put alternatives at \(0\) and \(2\). A district consisting entirely of type \(2-\sqrt{2}\) forces any mechanism beating \(1+\sqrt{2}\) to choose the alternative at \(0\); a district consisting entirely of type \(2+\sqrt{2}\) forces it to choose the alternative at \(2\). Combining these two large homogeneous districts produces a two-district continuous society on which whichever representative is selected globally incurs distortion at least \(1+\sqrt{2}\). Every “agent” in the proof can simply be replaced by a positive mass of identical agents. The reduction is therefore not relying on low population size.
The second anchor is Theorem 4.8, also proved here. For every \(G\in\{\mathrm{AVG},\mathrm{MAX}\}\), the paper defines the \(\lambda\)-Acceptable-Rightmost-Leftmost mechanism:
Theorem 4.8 proves that, on a line, its \( (\mathrm{MAX}\circ G) \)-distortion is at most
\[ \max\left\{2+\frac{1}{\lambda},\lambda\right\}. \]
The corresponding continuous problem is constructive:
\[ \textsc{Continuous-}\lambda\textsc{-ARL}. \]
Given the candidate coordinates and the type-mass distributions, compute every \(C_d^G(a)\), identify the \(\lambda\)-acceptable alternatives in each district, select the rightmost one, and then output the leftmost selected representative. With finite support this takes polynomially many arithmetic operations, essentially \(O(km\tau)\). Choosing \(\lambda=1+\sqrt{2}\) equalizes the two terms, yielding distortion \(1+\sqrt{2}\). Together with Theorem 4.11, the continuous line-metric problem has the exact answer \(1+\sqrt{2}\).
This is a Class-A-style continuous result: the finite-support problem is efficiently computable, and the optimal worst-case guarantee is characterized exactly. It is not a Class-B hardness transfer, because the paper has no named complexity-hardness anchor, nor is it continuum-specific hardness.
The scenario is plausible as a high-multiplicity one: large electoral districts, neighborhoods, or institutional subcommittees contain many residents with the same measured distance profile to a fixed set of public alternatives. The paper's authors should recognize the mirror immediately, because the candidates, metric costs, districts, local representatives, final winner, and distortion objective are all unchanged. Only the population representation changes from a list of agents to distributions over indistinguishable types.
The mirror deliberately covers only the paper's line-metric \( \mathrm{MAX}\circ G \) results, especially Theorems 4.8 and 4.11. It does not claim to continuize every objective or every ordinal result. Natural follow-up questions include whether the exact bound persists for arbitrary finite-support distributions, what happens for general metrics, whether ordinal information changes the continuous optimum, and how the result relates quantitatively to finite elections with rational multiplicities.
The weakest point is that this is a distortion-design paper rather than a complexity paper. Calling the bound \(1+\sqrt{2}\) a “complexity result” would be dishonest. The positive case is narrower: the paper's central distributed social-choice problem remains meaningful under high multiplicity, has a precise continuous formulation, and in this important regime admits an exact, efficiently computable solution.
The decisive objection is that this paper has no computational anchor for ChoCo to mirror. Its named results are distortion bounds and mechanism-design impossibility results. None gives a computational problem with an encoded input, output, complexity classification, algorithm, reduction, or parameterized question. The proposed \(\textsc{Continuous Distributed }(\mathrm{MAX}\circ G)\textsc{-Design}\) is therefore a new infinite-dimensional mechanism-design problem, not a continuization of one of the paper’s computational results.
Theorem 4.11 does not rescue the proposal. Its lower-bound construction can certainly be rewritten with positive mass on each of two identical types. But that observation shows precisely that population multiplicity is irrelevant to the theorem: the proof already works with one type per district and never exploits a finite population representation. In a finite-support formulation,
\[ C_d^{\mathrm{AVG}}(a)=\sum_{\theta}\mu_{d,\theta}|x_\theta-a|, \qquad C_d^{\mathrm{MAX}}(a)=\max_{\theta:\mu_{d,\theta}>0}|x_\theta-a|. \]
For a fixed mechanism, evaluating the winner and its distortion is just weighted summation, maximization, and comparison over the listed types and alternatives. There is no high-multiplicity optimization problem whose complexity might change.
Theorem 4.8 is no stronger. The \(\lambda\)-ARL rule is already an explicitly specified mechanism. Its continuous implementation merely computes the quantities above, tests \(m\) alternatives in each of \(k\) districts, and takes an extreme representative; with finite support this is essentially \(O(km\tau)\) arithmetic operations. Calling that an efficiently computable continuous result confuses evaluating a prescribed rule with solving a computational social-choice problem. If one instead asks for the best mechanism over all local and global maps, one has introduced a new minimax mechanism-design problem over an essentially unrestricted function class. The paper neither formulates nor motivates that problem.
Allowing arbitrary probability measures does not repair this. For \(\mathrm{AVG}\), one needs an integral; for \(\mathrm{MAX}\), an essential supremum. With a finite-support encoding this collapses to the same elementary calculation. With richer measures, the difficulty depends on the chosen representation or oracle for the measure, not on the paper’s distributed-social-choice structure. The ordinal version has the same problem: masses over rankings are finite, but the distortion still requires a supremum over compatible cardinal metrics, which is an additional robust-optimization model absent from the paper.
Thus the proponent has shown a coherent high-multiplicity restatement, and the lower and upper bounds survive it. That is the honest weak point of the negative case: the restatement is mathematically legitimate. But it is not a worthwhile ChoCo mirror in the programme’s computational sense. One can obtain either a notational replacement of finite sums by expectations, or a genuinely new mechanism-design problem whose computational content comes from extra choices not present in the paper. Neither anchors a continuous computational landscape for this paper.
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.