| paper | Metric Distortion with Elicited Pairwise Comparisons |
| authors | Soroush Ebadian, Daniel Halpern, Evi Micha |
| venue | IJCAI 2024 |
| filed under | voting · distortion |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3
statement extracted from the paper’s text layer
Given \(m\) candidates \(C\), a query budget \(t\), and a unit-mass society with finite-support rational distribution \(\mu\) over latent complete metric voter types, choose a fixed measurable schedule \(Q(u)\subseteq\binom{C}{2}\) with \(\lvert Q(u)\rvert\le t\) and an aggregation rule; an aggregate oracle returns exact response masses, and the objective is to minimize worst-case \(\operatorname{cost}_{\mu}(a)/\min_{c\in C}\operatorname{cost}_{\mu}(c)\) over compatible hidden metric societies.
A high-multiplicity batch-elicitation model: latent \(\mu\) over complete metric types, fixed pairwise-query schedule \(Q\), query cost \(t\) per unit mass, exact response histograms, and one discrete candidate minimizing multiplicative social-cost distortion.
The exact mass-response oracle, and for Theorem \(2\) an explicit mass order, are not part of the paper's individual-query interface, so a strict reader could regard the mirror as a new oracle model.
fatal: False
The mirror covers the unrestricted tradeoff in Theorems \(1\) and \(2\) and the fully nonadaptive tradeoff in Theorem \(3\); it leaves Theorems \(4\)--\(6\), their gaps, and the later open variants untouched.
The strongest positive case is a genuine high-multiplicity version of the paper’s metric-voting model: the outcome remains one discrete candidate, while the electorate becomes a rational mass distribution over repeated latent metric types. This is a population continuization, not outcome-space fractionalization.
Let \(C\) be the \(m\) candidates. A complete voter type \(t\) specifies a ranking \(\sigma_t\) and the distances \(d(t,c)\) to every candidate, with a common pseudometric on \(C\cup T\) certifying that the rankings are metric-consistent. A society is a rational distribution \(\mu\in\mathbb{Q}^{T}\), where \(\mu_t\) is the mass of type \(t\). Its social cost is
\[ \operatorname{cost}_{\mu}(c)=\sum_{t\in T}\mu_t d(t,c), \]
and the distortion of an output \(a\) is
\[ \operatorname{dist}_{\mu}(a) = \frac{\operatorname{cost}_{\mu}(a)} {\min_{c\in C}\operatorname{cost}_{\mu}(c)}. \]
The metric and type distribution are hidden from the algorithm. It sees only pairwise-comparison answers from the unit-mass population. Formally, the unit mass is partitioned into agents \(u\in[0,1]\), whose type pushforward is \(\mu\); asking \(u\) about \(\{a,b\}\) returns whether \(a\succ_u b\). In the exact continuum implementation, a measurable block of agents can be queried together and returns the mass of each response. This is simply the normalized histogram of the individual answers, and the algorithms below use only such aggregate information. Clearing denominators turns any rational instance into a large population of identical clones.
The regime is plausible in precisely the high-multiplicity sense relevant to ChoCo. Consider a large RLHF or opinion-aggregation platform whose users are generated from a finite collection of stable reward or opinion templates. A type records not merely the ordinal ranking but the latent metric position determining all candidate distances. Millions of users may share one of, say, tens or hundreds of such templates, so \(N\gg\tau\). This is not a claim that every real electorate has repeated cardinal types; it is a legitimate instance regime in which the paper’s query problem becomes a mass problem.
My lead anchor is Theorem 2, proved in this paper. It states that, when \(n\ge \lceil (m-1)/t\rceil\) and \(t\le m-1\), Algorithm 2 is a single-pass, \(t\)-query algorithm with distortion at most
\[ 6\left\lceil\frac{m-1}{t}\right\rceil+1. \]
The corresponding continuous problem is:
Continuous Single-Pass \(t\)-Query Metric-Distortion Elicitation. Given \(C\), \(t\), a finite type set \(T\), rational mass vector \(\mu\), and hidden metric data consistent with those types, construct a single-pass policy that assigns at most \(t\) pairwise queries to every infinitesimal voter and outputs one candidate. The objective is to minimize the worst-case distortion over all compatible hidden metrics and type distributions.
A solution is therefore a measurable query policy together with a candidate-selection rule and a proved guarantee \(\rho\) satisfying
\[ \operatorname{dist}_{\mu}(A(d,\mu))\le \rho \]
for every compatible \((d,\mu)\).
The continuous lift of Algorithm 2 is direct. Put
\[ R=\left\lceil\frac{m-1}{t}\right\rceil \]
and partition the unit population into \(R\) consecutive mass blocks. In block \(r\), use at most \(t+1\) active candidates, run the mass version of Plurality Veto, retain its winner, and eliminate the other candidates from that block. Each voter is queried only within its own block, so the procedure is single-pass and uses at most \(t\) queries per voter. The proof’s directed elimination tree and disjoint voter paths become a disjoint-path-mass argument. Counts are replaced by masses, and the social-cost inequality becomes a statement about integrals. Thus the same proof gives an \(O(R)\) guarantee; the finite theorem’s \(6R+1\) bound is a safe target.
Theorem 1, also proved here, supplies the matching lower-bound companion: every \(t\)-query algorithm has distortion at least \(m/t-1\). Its proof is already fundamentally a mass argument: among the queried candidate appearances, some candidate is exposed on only a small fraction of the population, after which two compatible metric societies force the algorithm into a bad choice. Hence the expected continuous landscape is Class A with an essentially tight
\[ \Theta\!\left(\frac{m}{t}\right) \]
tradeoff, at least in the unrestricted finite-support version. The lower bound transfers by taking rational masses corresponding to cloned finite voters; bounded-support refinements would be a separate question.
My second anchor is Theorem 3, proved in the paper, although its lower-bound proof is deferred to the full version. The theorem states that fully nonadaptive \(t\)-query algorithms have distortion at least \(m^2/t-1\), while a fully nonadaptive algorithm achieves distortion at most \(3m^2/t+1\) under the stated finite-population condition. Its key Lemma 3 is derived from Kempe’s earlier metric-voting framework, but Theorem 3 itself is the paper’s result.
The corresponding problem is:
Continuous Fully Nonadaptive Metric-Distortion Elicitation. Given \(C\), \(t\), \(T\), and \(\mu\), choose before seeing any answer a measurable assignment \(Q(u)\subseteq \binom{C}{2}\) with \(|Q(u)|\le t\) for every voter \(u\). After receiving all responses, output one candidate minimizing worst-case metric distortion.
A solution consists of the fixed query assignment and an aggregation rule. For \(M=\binom{m}{2}\), the continuous analogue of the paper’s construction assigns every candidate pair \(\{a,b\}\) to exactly \(t/M\) population mass. The algorithm forms the weighted majority tournament, directing \(a\to b\) when at least half of the mass queried on \(\{a,b\}\) prefers \(a\), and returns a king vertex. Each majority edge is supported by mass at least \(t/(2M)\). The weighted version of Lemma 3 then gives distortion \(O(M/t)=O(m^2/t)\), while the finite lower-bound construction transfers through rational masses. This is another Class A problem with an essentially tight nonadaptivity penalty:
\[ \Theta\!\left(\frac{m^2}{t}\right). \]
This second mirror is especially clean because the continuum removes divisibility issues. In a finite population, distributing query slots equally among all \(M\) candidate pairs requires a condition such as \(n\ge M/t\). With mass, every pair can receive exactly \(t/M\) population mass. The result is not merely “fractional voters”; it is a meaningful high-multiplicity query-allocation problem.
Both mirrors preserve what the paper is actually about: hidden metric preferences, discrete candidates, pairwise ordinal queries, a per-voter query budget, restrictions on adaptivity, and multiplicative social-cost distortion. They do not replace the problem by expected utility, fractional winners, or an axiomatic question. The only continuous object is the population.
The further questions are also natural: can the exact optimal constants in the \(m/t\) and \(m^2/t\) regimes be determined; how does the answer depend on \(\tau\); can one interpolate between full nonadaptivity and single-pass adaptivity; and what happens under anonymous schedules requiring every type or every voter to receive the same query pattern? One could also study rounding from rational mass policies back to finite populations, or noisy mass-response oracles.
The weakest point is the query interface. If a referee insists that a continuum algorithm may only address individual agents and may not receive exact response masses from a block, then the batch formulation grants an additional idealized capability. The repair is to define the model as the exact high-multiplicity limit of individually queried clones: every agent retains its own \(t\)-query budget, while the algorithm’s state stores normalized response counts. The two anchored algorithms use only those aggregate counts, so the mass formulation is lossless for them. Still, this caveat means the result should be presented as a precise high-multiplicity extension of the paper’s query model, not as an already-established theorem about arbitrary atomless populations.
The paper clears the named-result gate: Theorems 1, 2, and 3 are genuine computational anchors. The strongest negative case therefore concerns not the theorems, but the access model that the proposed mirrors quietly replace.
In the paper, voters are named query endpoints. The algorithm does not know \(d\) or \(\sigma\), chooses a pair for a particular voter, receives one bit, and may use that voter’s transcript in deciding the next query. A ChoCo type, however, must include the complete information relevant to the objective, including the voter’s candidate distances. If \(T\), \(\mu\), and those complete types are given explicitly, then \(\operatorname{cost}_{\mu}(c)\) is already computable and the elicitation problem disappears. If they are hidden, then \(\mu\) is not the society input; it is a latent distribution accessible only through some additional oracle. The proposed formulation cannot simultaneously preserve the paper’s information restriction and make the continuous society an explicit input.
Keeping the original individual-query interface does not repair this. A finite computation over an atomless population observes only a measure-zero set of voters. The unqueried mass can be assigned either preference and metric realizations, so the finite paper’s guarantee cannot be obtained by finitely many individual interactions. The constraint “at most \(t\) queries per voter” is pointwise; it does not yield a finite population-level information budget. The paper’s algorithms terminate after scanning \(n\) named voters, whereas their atomless counterparts require querying the entire unit mass.
The proponent’s batch-response repair changes precisely this point. A query to a measurable block that returns the exact response mass is a powerful aggregate oracle. In a finite population of \(N\) clones, obtaining that quantity from the original interface requires up to \(N\) individual answers; it is not one query whose cost remains bounded as \(N\) grows. Saying that normalized response counts can be stored after querying all clones does not make those interactions disappear, nor does it provide a finite algorithm in the original model. The batch oracle may define a worthwhile new model of population polling, but its tractability comes from aggregate access, not from continuizing the population alone.
This defeats the proposed lift of Theorem 1. With individual access, the continuous problem has no finite implementation corresponding to the paper’s \(t\)-query algorithm. With exact mass access, the pigeonhole lower bound becomes an integral version of the same finite argument, and Algorithm 2 becomes a mass-counting procedure. That is a legitimate batch-elicitation extension, but not a direct continuous mirror of the theorem’s query model. Clearing denominators only proves rational-clone equivalence; it does not establish a compact hidden-distribution representation.
Theorem 2 has an additional defect. “Single-pass” is a property of an ordered stream of named voters. A distribution \(\mu\) contains no arrival order. To define the mirror faithfully one must add an ordering \(\lambda:[0,1]\to T\), or a joint distribution of type and position. The proponent’s consecutive mass blocks silently supply this missing structure. If the guarantee must hold for every \(\lambda\), then the order is irrelevant and the result is just the finite proof with counts replaced by integrals. If the order matters, then the object is an ordered population process, not a society represented by \(\mu\). In either case, the mass-response oracle remains necessary for termination.
Theorem 3 is less vulnerable to history dependence, but not immune. Fully nonadaptive querying still assigns a fixed query schedule to named voters. The marginal type distribution \(\mu\) does not specify which latent types receive which candidate pairs. A faithful model must retain a coupling between types and schedules, or quantify over all such couplings. The proponent’s allocation of exactly \(t/\binom{m}{2}\) mass to every pair is therefore not supplied by \(\mu\); it is an additional designer-controlled schedule together with exact pairwise response aggregation. The resulting weighted-majority tournament is a sensible batch-polling problem, but again the new computational object is the aggregate-query interface.
There is a real concession. Large platforms with recurring preference or reward templates are a plausible high-multiplicity regime, and rationally cloning each hidden type preserves the metric-distortion objective. Thus “metric voters cannot repeat” and “the bounds merely survive unchanged” would be bad objections. The sharper conclusion is narrower: these theorems’ substance lies in eliciting hidden, individually addressable information. A distribution over complete types either reveals that information, making queries redundant, or hides it behind a sampling/marginal oracle, creating a different problem.
Consequently, under ChoCo’s population-only continuization requirement, none of the three anchors supplies a worthwhile direct mirror. If ChoCo admits exact mass-response oracles as author-recognizable extensions, the negative case is weak: the proponent has a coherent Class-A batch-elicitation programme. Under the stricter access semantics, however, all three proposed mirrors fail for the same fundamental reason.
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.