| paper | d4-conf-aaai-2015-0685 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorems 6 and 10 assert tight distortion bounds, which the rubric explicitly excludes from the named computational-result gate. The proposed exact sum and median evaluations are coherent candidate extensions, but they introduce new computational questions and cannot supply the missing qualifying result from this paper.
fails bit a — no named computational result to mirror
The proposed exact-evaluation questions concern Theorem 6's sum objective and Theorem 10's median objective; they leave the paper's other distortion bounds, including its percentile results, without a proposed mirror.
A qualification first: this paper has no numbered result asserting that a problem is in P, NP-hard, FPT, or similar. Its named results are distortion bounds. So it offers no anchor of the exact complexity-class kind requested. The strongest honest positive case uses Theorems 6 and 10 as performance anchors and asks new computational questions about their high-multiplicity versions.
A plausible regime is a large recommender or e-commerce population divided into a small number of repeated user archetypes. A type must include the user’s ranking and the other traits the model uses, including their latent metric position; grouping everyone with the same ranking would be too coarse if their cardinal costs differ. Let \(T\) be the archetypes, \(\rho_t\) the ranking of type \(t\), and \(\mu_t\) its rational population share. The mechanism sees the ranking shares, while the metric costs remain hidden. Its cost for alternative \(a\) under a compatible metric \(d\) is
\[
C_\mu(a;d)=\sum_{t\in T}\mu_t d(t,a).
\]
This keeps the paper’s alternatives discrete and its metric-cost model intact; the population is the continuous object.
Theorem 6, proved by the authors here, is my sum-cost anchor: for every metric instance, Copeland’s distortion under total social cost is at most \(5\), and that bound is tight. The continuous question I would hand to a prover is Exact Sum-Distortion of Copeland. Its input is \(A,T,\rho,\mu\), with a fixed tie-breaking rule for Copeland. It asks for
\[
D_\Sigma(\mu)=
\sup_{d\in\mathcal D(\rho)}
\frac{C_\mu(w_{\mathrm{Cop}};d)}
{\min_{a\in A}C_\mu(a;d)},
\]
where \(\mathcal D(\rho)\) is the set of metric completions consistent with the types’ rankings. A solution is the exact supremum and a metric attaining or approaching it. I expect this problem to be tractable: enumerate the possible optimal alternative \(x\), normalize \(C_\mu(x;d)=1\), impose that \(x\) has minimum social cost, and maximize Copeland’s cost. Metric constraints and these sum-cost constraints are linear, giving a polynomial-size LP in \(m\) and \(\tau\), with the usual separate handling for zero optimum. Theorem 6 supplies the global guarantee \(D_\Sigma(\mu)\le 5\), with tightness over the input family.
Theorem 10, also proved here, is the median-cost anchor: Copeland’s median distortion is always at most \(5\), and the bound is tight. The associated problem is Exact Median-Distortion of Copeland on the same input, replacing \(C_\mu(a;d)\) with the upper weighted median
\[
Q_\mu(a;d)=\inf\left\{z:\sum_{t:d(t,a)\le z}\mu_t>\tfrac12\right\}.
\]
It asks for the supremum of \(Q_\mu(w_{\mathrm{Cop}};d)/\min_a Q_\mu(a;d)\), again with an attaining or approaching metric as a solution. The theorem’s universal bound transfers to this model. For exact per-instance evaluation, my tentative expectation is continuum-specific difficulty: the weighted median makes the relevant groups of types depend on the metric completion, creating subset-selection choices absent from the sum-cost LP. That is a conjecture about the new question, not a hardness result in this paper; an FPT algorithm in \(\tau\), or a polynomial formulation, is a natural first question. Theorem 8’s lower bound—no deterministic rule has worst-case median distortion below \(5\)—also explains why Theorem 10’s tight guarantee is especially compelling.
The rational-mass formulation is a genuine high-multiplicity mirror: multiplying all shares by a common denominator recovers a finite election, and repeated copies of an archetype preserve its metric costs. Thus these distortion guarantees carry over directly. That is evidence for the mirror, not a novelty collision: the paper proves guarantees for explicitly represented finite populations, while the proposed problems ask for exact robustness analysis on a compressed support, with complexity measured in \(m,\tau,L\). I would keep the scope to Theorems 6 and 10, rather than claim a mirror for every result in the paper.
The weak point is that the paper allows arbitrary hidden metric costs, and a society with few complete cost archetypes may be a stronger assumption than a society with few rankings. If realistic populations require nearly one archetype per person, the compressed regime disappears. The argument survives for settings with repeated latent-cost profiles, but the paper itself does not establish that such profiles are common.
The paper gives no named result about the complexity of a computational problem. Theorems 6 and 10 bound Copeland’s distortion; Theorem 8 gives a lower bound for every deterministic rule. Those are performance results, not algorithmic ones. The proposed “Exact Distortion” questions therefore introduce a new analysis problem rather than continuize a computational result from the paper.
For the sum-cost version, that new problem is well defined and appears to reduce to a polynomial-size LP: choose an optimal alternative, normalize its cost, impose the metric and ranking constraints, and maximize Copeland’s cost. That may be a useful robustness calculation. But the population continuum contributes little to it: the result depends on the ranking shares and an adversarial completion of the hidden metric. It neither computes a social-choice intervention on a society nor reveals a new phenomenon caused by population mass. Theorem 6’s bound and tightness claim also extend by replacing voter counts with shares; they do not require a new computational analysis.
There is a more basic modeling tension. For this problem, an agent’s latent costs affect the objective, so two agents with the same ranking but different costs are different types under ChoCo’s definition. If types include the latent metric positions, the proposed input does not specify their distribution; it specifies rankings and optimizes over all compatible positions. If types include only rankings, they omit information the problem uses. One can make the latter a coherent *robust uncertainty* problem, but that is a new problem about worst-case hidden costs, not a direct continuous population of complete types.
The median anchor is harder to dismiss. A weighted median is a natural objective for a population, and exact evaluation may require choices about which types lie below the relevant cost thresholds. That could produce an interesting algorithmic problem. But the proponent’s suggestion of continuum-specific hardness is only a conjecture: threshold subset selection could just as well be ordinary complexity in the support size \(\tau\), and if it yields a meaningful hardness or parameterized result, that would fit the programme. Theorem 8’s lower bound does not supply a computational question; it supplies another distortion guarantee that carries over to masses.
So the strongest case against is that the paper has no complexity result to mirror, while the proposed replacements are robustness analyses whose continuous formulation either omits complete type information or adds a new uncertainty-set problem. That makes the sum anchor look modest and indirect. The negative case is weakest for the median anchor: its weighted-quantile formulation is coherent, and I cannot rule out that its exact-computation question is worthwhile. I also cannot honestly establish the universal claim that no plausible repeated-type scenario exists.
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.