| paper | Ordinal Approximation for Social Choice, Matching, and Facility Location Problems Given Candidate Positions |
| authors | Elliot Anshelevich, Wennan Zhu |
| venue | WINE 2018 |
| filed under | voting · distortion |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: A deterministic algorithm always outputs \(W\in F\) with \(R(W)\le 5\) in time polynomial in \(m,\tau,L\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 3.16
statement extracted from the paper’s text layer
Given candidates \(F\), a rational mass distribution \(\mu\) over reported rankings, and public ordinal comparisons of candidate distances, output a candidate \(W\) whose robust distortion over all compatible mass measures \(\lambda\) on complete latent metric types with report marginal \(\mu\) is at most \(5\): \(\sup_{\lambda}\frac{\int d_u(W)\,d\lambda(u)}{\min_{Y\in F}\int d_u(Y)\,d\lambda(u)}\le 5\).
The society is a mass measure \(\lambda\) over complete latent types \(u=(\sigma,d_u)\); the mechanism observes only the ranking marginal \(\mu\), chooses one candidate, and is evaluated by worst-case total metric cost over all compatible \(\lambda\).
The proponent's stated \(T\) contains only rankings although hidden cardinal costs affect social cost; a faithful mirror must therefore model complete latent cost types, their mass measure, and the observation map that exposes only rankings.
fatal: False
The mirror covers Theorem 3.16's \(5\)-distortion social-choice mechanism and Corollary 5.1.1(1)'s \(3\)-distortion matching mechanism after the latent-type repair; it leaves the other approximation ratios and Theorem A.1's impossibility result outside the computational anchor.
The strongest positive case is a continuous-population version of the paper’s metric-ordinal model. It is a legitimate high-multiplicity setting: millions of voters or patients, a small number of repeated preference types, and a finite set of candidates or facilities whose locations are public. The paper contains no named NP-hardness, FPT, or W[1]-hardness theorem, so the anchors here are algorithmic distortion results rather than hardness results.
My lead anchor is Theorem 3.16, proved in the paper. It states that Algorithm 2 has distortion at most \(5\) for minimum total social cost, and that this bound is tight for that algorithm. Algorithm 2 uses the majority graph of the agents’ rankings together with ordinal comparisons between candidate-to-candidate distances. It adds justified edges to the majority graph and returns a candidate that dominates every other candidate in the modified graph.
A precise mirror is the following.
Continuous Metric-Distortion Social Choice. An instance consists of a finite candidate set \(F\), a finite set \(T\subseteq S_F\) of ranking types, rational masses \(\mu_t\) summing to \(1\), and public ordinal information about the distances between candidates. A compatible metric realization assigns every type \(t\) a common latent cost vector \(d_t(\cdot)\), consistent with its ranking, and preserves the given candidate-distance comparisons. The action is to choose one candidate \(W\). Its robust distortion is
\[ \sup_{d\in\mathcal D} \frac{\sum_{t\in T}\mu_t d_t(W)} {\min_{Y\in F}\sum_{t\in T}\mu_t d_t(Y)}. \]
The problem is to output a candidate whose robust distortion is at most \(5\), or, in the optimization version, to minimize this worst-case ratio.
This is recognizably the authors’ problem: the candidates remain discrete, the objective remains total metric social cost, the mechanism still sees ordinal voter information and candidate-location information, and uncertainty still concerns hidden cardinal voter costs. Only the population is continuized. A high-multiplicity scenario is an electorate with \(n\) large and \(\tau\ll n\): for example, a national electorate with a few hundred recurring ballot types and a small candidate set.
The proof of Theorem 3.16 transfers naturally. Replace each count by mass, majority by \(\mu\)-majority, and sums over agents by integrals or finite sums over types. The triangle-inequality arguments and the majority-graph construction are unchanged. The paper’s tight example also survives normalization: the two large ranking cohorts and the small third cohort can be given rational masses, and as the small cohort’s mass tends to zero the ratio approaches \(5\). Thus the continuous problem has a concrete polynomial-time \(5\)-feasibility result, while the exact optimum and the possibility of improving the factor below \(5\) become worthwhile further questions. This is a Class A mirror as far as the paper’s stated guarantee is concerned.
A second worthwhile anchor is Corollary 5.1.1(1), proved in the paper. It states that minimum-weight bipartite matching in the metric setting, given agents’ ordinal preferences and the distances between facilities, admits a polynomial-time ordinal mechanism with distortion at most \(3\). The proof uses Theorem 5.1: a \(\beta\)-approximate solution to the projected, omniscient problem yields distortion at most \(1+2\beta\); exact minimum-cost matching gives \(\beta=1\).
Its continuous form is:
Continuous Ordinal Metric Matching. The instance contains ranking types \(T\) with masses \(\mu_t\), facilities \(F\) with per-capita supplies \(\nu_f\), where \(\sum_t\mu_t=\sum_f\nu_f=1\), public facility-location distances, and compatible hidden metric costs. A solution is a mass-matching plan \(x_{t,f}\ge0\) satisfying \(\sum_f x_{t,f}=\mu_t\) and \(\sum_t x_{t,f}=\nu_f\). Its cost in realization \(d\) is \(\sum_{t,f}x_{t,f}d_t(f)\), and its distortion is the ratio to the minimum cost over all feasible mass plans. The task is to produce a plan with worst-case distortion at most \(3\).
This is a natural high-multiplicity matching problem: many patients of a few preference types matched to many appointment slots at a few hospitals, or many workers of a few preference types matched to repeated positions at known employer locations. The fractional-looking plan does not make an individual patient divisible; it records the aggregate of many integral assignments. Facility supplies are scaled per capita, exactly as required for a population mirror.
The paper’s projection argument becomes especially transparent. Let \(p_f=\sum_{t:\operatorname{top}(t)=f}\mu_t\) be the mass projected to the location of its top facility. Solve a minimum-cost transportation problem from projected mass \(p\) to facility supply \(\nu\), using facility-to-facility distances, and then decompose the resulting flow back into the original ranking types. This is polynomial in \(m\), \(\tau\), and the encoding length of the masses. The same triangle-inequality and subadditivity proof gives the factor \(3\). Rational masses also give the two-way dictionary: clearing denominators recovers a finite replicated matching instance, while the continuous algorithm gives a high-multiplicity algorithm independent of the raw population size. This is again Class A.
The paper’s Theorem A.1 gives an important boundary, though I would not make it my lead anchor. It proves that median-cost bipartite matching has unbounded worst-case distortion even when agent rankings and facility distances are known. Its three-agent example uses two agents with the same ordinal ranking but different hidden cardinal costs; swapping their hidden costs leaves the observed ordinal instance unchanged but changes which matching has median cost \(2\varepsilon\) versus \(1\). The same construction can be written with population masses and a \(1/2\)-quantile objective.
However, this exposes the weakest point of the positive case. Under ChoCo’s strict definition of a complete type, agents with different cardinal cost vectors are different types, even if they submit the same ranking. The paper’s impossibility exploits precisely that gap between reported ordinal type and hidden cardinal type. Therefore I would only claim Theorem A.1 as a continuous mirror if the mirror explicitly preserves the paper’s partial-information model, allowing a reported ranking mass to conceal several homogeneous latent subcohorts. If the continuous model instead reveals complete cardinal types, that particular lower bound disappears.
More generally, the paper’s central contribution is information-theoretic approximation, not a discrete complexity barrier. For the two principal mirrors above, continuization may mostly expose algorithms that already aggregate repeated agents. That makes this a moderate rather than flagship ChoCo candidate. Still, the mirrors are concrete, faithful, and computationally meaningful: population masses are the honest quantity, facilities and candidates remain discrete, and the resulting robust optimization and transportation questions are exactly the kind of high-multiplicity problems the programme is meant to study.
The strongest negative case is a type-identity problem. The proposed mirrors aggregate agents by their reported rankings, but in this paper the operative objective depends on their hidden cardinal costs. Under ChoCo’s definition, two agents with the same ranking but different cost vectors are different types.
This defeats the proposed mirror of Theorem 3.16. The quantity
\[ \sum_t \mu_t d_t(W) \]
is valid only after adding the assumption that every agent with ranking \(t\) has the same latent cost vector \(d_t\). That is not a consequence of the paper’s model. In the paper, two agents may have the same ranking while having entirely different distances to every candidate. Their aggregate cost, and even which candidate minimizes it, depends on the hidden coupling between rankings and cardinal costs.
There are only three ways to repair this. If the latent vectors are revealed, the ordinal-information problem disappears. If they are fixed but hidden, then the input is not a distribution over complete types: it is a distribution over reported types together with an ambiguity set of possible latent populations. If arbitrary hidden heterogeneity is allowed within each ranking, the continuous object must be a measure over cardinal-cost types plus an observation map that forgets those costs. That is a new partially observed robust-mechanism problem, not the paper’s population continuization. The weighted-majority proof may survive, but it is then a theorem about the reported marginal, not a faithful continuous version of the distortion problem itself.
The matching anchor has the same defect, more sharply. The proposed flow \(x_{t,f}\) is sufficient only when all agents of ranking type \(t\) have identical assignment costs. If a ranking cohort contains agents with different hidden metric distances, the cost of sending mass to facility \(f\) depends on which latent subtypes receive it. An aggregate flow over rankings loses exactly the information needed to evaluate the matching objective. One must instead use flows \(x_{u,f}\) over complete latent types \(u\), while the mechanism sees only their ranking projection. Again, that requires a hidden population measure and an observation structure absent from the proposed mirror.
Per-capita facility supplies and repeated facility locations are perfectly defensible modelling choices; they are not the objection. They solve the scaling problem, but not the information problem. If complete latent types are made homogeneous, the resulting transportation LP is a new full-information high-multiplicity problem. If latent costs remain hidden, the problem is no longer represented by the proposed transportation instance.
Theorem A.1 makes the issue explicit rather than incidental. Its lower bound relies on agents \(a\) and \(b\) having the same observed ranking but different hidden cardinal costs. In ChoCo terminology they are not one type. Collapsing them into one mass invalidates the construction; separating them requires keeping their latent identities hidden, which produces the same ambiguity-set model described above. Thus this theorem cannot serve as an anchor for a pure continuous society.
I would therefore reject the proposed anchors as stated. They continuously aggregate reports, not complete voter or agent types. A richer project involving distributions over latent cardinal types, observation maps, and robust optimization could certainly be worthwhile, but that is a new information-theoretic model rather than a continuous-population mirror of this paper. The negative case is not mathematically airtight if ChoCo permits such hidden-type machinery; under the programme’s strict type definition, however, the proponent has not yet supplied a valid 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.