| paper | Independence of Irrelevant Alternatives under the Lens of Pairwise Distortion |
| authors | — |
| venue | AAAI 2024 |
| filed under | voting · distortion |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper contains no numbered theorem asserting hardness, tractability, approximation, or parameterized complexity. The proposed continuous formulations are faithful high-multiplicity restatements of Theorems 3 and 6, but they remain analytic minimax distortion questions rather than mirrors of computational results. Therefore bit (a) fails and the grade is red.
fails bit a — no named computational result to mirror
The mirror covers the 1D-Euclidean Borda results in Theorems 3 and 6, while leaving Theorems 1, 2, 4, and 5, the experiments, unconstrained utilities, and other voting rules outside scope.
The strongest honest positive case is narrow: the paper has a faithful population mirror for its 1D-Euclidean pairwise-distortion results, with Theorem 3 as the lead. But under ChoCo’s strict anchor rule, this paper has no qualifying computational anchor. None of Theorems 1–6 asserts NP-hardness, membership in P, parameterized complexity, or an algorithmic classification. They are exact distortion theorems. Thus I would not call the paper a full positive/green case; I would call it a strong source of a continuous problem, but one that fails the programme’s named-complexity gate.
The lead mirror is the following.
Let \(A=\{x,y,z_1,\ldots,z_{m-2}\}\), with \(x\) at position \(0\) and \(y\) at position \(1\) on a line. A voter type is a complete metric type \(\theta=(p,\rho)\): \(p\in\mathbb Q\) is the voter’s position and \(\rho\) specifies how distance ties are resolved. A continuous society is a finite rational distribution \(\mu\) over such types; \(\mu_\theta\) is the fraction of the population at that location and with that tie behaviour. Two agents with the same \((p,\rho)\) are interchangeable in every respect used by the problem.
The designer chooses positions \(q(z_j)\in\mathbb R\) for the additional alternatives. Each type ranks alternatives by distance. BordaPW chooses between \(x\) and \(y\) according to
\[ \operatorname{BSc}_\mu(a)=\sum_{\theta}\mu_\theta\bigl(m-\operatorname{rank}_\theta(a)\bigr). \]
The social cost of \(a\) is
\[ \operatorname{SC}_\mu(a)=\sum_\theta \mu_\theta |p_\theta-q(a)|. \]
The distortion of the resulting pairwise choice is
\[ D_\mu(q)= \frac{\operatorname{SC}_\mu(\operatorname{BordaPW}(x,y))} {\min\{\operatorname{SC}_\mu(x),\operatorname{SC}_\mu(y)\}}. \]
Call the problem Continuous Borda Inf-Pairwise Distortion. Given \(m\) and a rational threshold \(R\), determine whether there is a placement \(q\) of the \(m-2\) additional alternatives such that every finite rational continuous society satisfies \(D_\mu(q)\le R\). A yes-solution consists of the alternative positions together with the universal guarantee.
This is precisely the population version of the paper’s cooperative placement problem: the number of voters disappears into mass, while the alternatives, metric domain, BordaPW rule, target pair, and social-cost objective remain unchanged. The high-multiplicity regime is plausible in a facility-location or regional-planning setting: millions of residents may share a coarse geographic or ideological position, while \(m\) candidate facilities or reference alternatives is small. The paper itself explicitly motivates additional alternatives as reference or “fake” facilities that help elicit preference intensity.
The anchor is Theorem 3, proved by the authors here in outline and fully in the longer version:
“The inf-pairwise distortion of the BordaPW pairwise rule in the 1D-Euclidean metric space is \((m+1)/(m-1)\) for any \(m\ge2\).”
In the continuous problem, the answer is therefore yes exactly when \(R\ge (m+1)/(m-1)\). Equidistant alternative placement supplies the witness. The lower-bound population in the proof already has fractional masses: \((m-1)/m\) of voters at the midpoint and \(1/m\) at \(y\). That is unusually good evidence that the continuous formulation is not an artificial relaxation; the theorem’s own proof is naturally written in mass language.
I would expect this restricted problem to be Class A: in this special 1D-Borda setting the minimax value has a closed form, and the continuous evaluator for a supplied finite type distribution is computable by aggregating scores and costs. The more interesting ChoCo questions would concern arbitrary scoring vectors, arbitrary candidate placements, approximate placement, and general metric spaces.
A useful secondary mirror is Continuous Borda Sup-Pairwise Distortion. It has the same type and mass model, but asks for
\[ \sup_{q}\sup_{\mu}D_\mu(q), \]
where both the additional-alternative positions and the continuous society are adversarial. Theorem 6, also proved by the authors, states:
“The sup-pairwise distortion of BordaPW in the 1D-Euclidean metric space is equal to \(2m-1\) for all \(m\ge2\).”
This is a less compelling practical scenario because adversarial alternative placement is pessimistic, but it is still faithful to the paper’s explicit worst-case analysis. It too is tractable in the narrow theorem-level formulation, while raising computational questions for other scoring rules and higher-dimensional or general metric domains.
The mirror deliberately covers only Theorems 3 and 6. It does not claim to continuize the paper’s experiments, unconstrained-utility setting, Copeland and plurality comparisons, or the conjecture following Theorem 4. Those would require separate modelling choices and should not be smuggled into the case.
The weakest point is decisive: these are analytic distortion bounds, not named computational results. The paper does not give ChoCo a result whose complexity can be classified after continuization. The proposed problems are legitimate continuous population versions of the paper’s minimax questions, and the authors would likely recognise them as such, but they are follow-on computational questions rather than mirrors of an existing NP-hard/P/FPT theorem. Under the programme’s formal screening rule, that absence is enough to reject the paper as a qualifying positive case, despite the unusually natural mass interpretation of its 1D metric results.
The negative case is decisive at ChoCo’s formal gate: this paper has no computational result to continuize. Theorems 1–6 are exact distortion bounds, not complexity theorems, algorithms, hardness results, or parameterized classifications. The paper’s other contributions are axiomatic framing and experiments. Thus no population model can produce a computational *mirror* of a result that is not computational in the first place.
Theorem 3 is nevertheless a faithful continuous population model, and this is where the negative case is weakest. A distribution over one-dimensional voter locations is sensible: social cost and Borda score are aggregate quantities, and residents can plausibly share a coarse location type. The proponent’s mass profile also matches the paper’s proof exactly.
But that fidelity reveals the problem. In the proposed “Continuous Borda Inf-Pairwise Distortion” problem, the society is universally quantified away. Borda scores and social costs are linear sums over voters, and every rational finite mass profile is just a normalized discrete profile. Conversely, the theorem’s adversarial profiles already use only a few voter locations. Replacing \(n\) voters by rational fractions changes notation and encoding, but introduces no population-side computational object. The proposed threshold question is simply Theorem 3 rewritten as “is \(R\ge(m+1)/(m-1)\)?” Its witness is the theorem’s equidistant placement. That is a legitimate continuous restatement of an analytic minimax theorem, not a continuization of a computational problem.
The best repair would be to provide a particular mass distribution and ask for the best placement of the additional alternatives, or to optimize over scoring rules, placement restrictions, or metric dimensions. Those could be worthwhile new optimization problems. But they change the quantifiers and objective of Theorem 3: they are follow-on facility-location or elicitation problems, not mirrors of anything computationally established in this paper. Moving to arbitrary scoring vectors or general metrics broadens the research agenda further, but only by supplying entirely new computational content.
Theorem 6 fails for the same reason, even more transparently. Its supremum ranges over both alternative positions and voter configurations, and the proof’s extremal population consists of only two groups. Passing to masses gives fractions such as \(\alpha\) and \(1-\alpha\); it does not expose a large-multiplicity algorithmic regime. The proposed continuous problem therefore has the already-stated answer \(2m-1\), rather than a complexity landscape inherited from the paper. Restricting the society and optimizing placements for that fixed society would again be a new problem, not a mirror of the theorem.
So the opponent should concede that the metric population story is natural and that neither identity sensitivity nor a degenerate limit defeats these formulations. The stronger objection is prior: both proposed anchors are analytic distortion identities, and their “continuous” versions merely normalize the same worst-case profiles. A continuous follow-on may eventually be valuable, but no scenario turns this paper into a qualifying ChoCo mirror without adding the computational problem oneself. Under the programme’s named-result rule, that is a red verdict.
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.