| paper | d4-conf-aaai-2014-0040 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: \(\text{Polynomial-time solvable}\), with exact rational probabilities encoded by binary numerators and denominators. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a finite alternative set \(A\) and a finite-support distribution \(\mu\) over complete weak rankings, with positive binary-rational masses summing to \(1\), compute an ESR lottery by running the ESR process on one representative for each type in \(\operatorname{supp}(\mu)\). What is the exact running time in \(m=|A|\), \(\tau=|\operatorname{supp}(\mu)|\), and the input bit length \(L\)?
The population is a distribution \(\mu\) over ranking types. Each positive-mass type contributes one representative to the ESR process; the mass values identify the support but do not weight the agents' guarantees. The output is a lottery satisfying the process's accumulated lower bounds, computed in time polynomial in \(m\), \(\tau\), and \(L\).
An arbitrarily small positive-mass type has the same influence as a large one, then disappears entirely at zero mass; the proponent acknowledges this but does not show that the resulting support-only computation is a substantial continuization.
fatal: False
The mirror covers exact ESR evaluation from Theorem 2. It leaves the paper's fairness, efficiency, strategyproofness, domain-equivalence, and DL-efficiency characterization results without continuous analogues.
The strongest mirror is continuous ESR evaluation. Imagine a large public deliberation over a finite agenda \(A\): each citizen submits a complete weak ranking, and the mechanism returns a lottery over the alternatives. A type is one such ranking; \(\mu_t\) is the fraction of the population with ranking \(t\). With many citizens but only \(\tau\) distinct rankings, the society is a finite-support distribution \(\mu\), with rational masses summing to \(1\).
Given \(A\) and \(\mu\), the problem is to compute an ESR lottery. Define the continuum version by letting citizens of each type follow the paper’s ESR process in sync. Since the process uses only preferences, identical citizens impose identical probability guarantees and move through the same equivalence classes together. Thus the type-level computation is exactly the paper’s algorithm run with one representative for each type with \(\mu_t>0\). A solution is any lottery \(p\) produced at termination that satisfies the accumulated lower bounds on the probability of each represented indifference class. ESR has no overall welfare-maximization objective; its stage-by-stage LPs maximize how long the process can continue while preserving feasibility.
My anchor is Theorem 2, proved in this paper: *the ESR algorithm runs in polynomial time*. The authors’ proof shows that each stage solves polynomially many linear programs, and at least one agent advances to their next equivalence class at every iteration, so there are at most \(n|A|\) iterations for \(n\) agents. In the continuous version, duplicate constraints and synchronized agents collapse to one representative per supported type. The same argument therefore gives an exact algorithm polynomial in \(m=|A|\), \(\tau\), and the input bit length \(L\). This is an inference from the theorem and its proof, not a separate theorem stated by the authors. The paper offers no named hardness result to anchor a second mirror.
The population regime is a large body whose members rank the same small set of public alternatives, with many people sharing each ranking. The lottery could be implemented as a genuine random selection, as the paper describes its outcomes. This is a credible regime for ESR in particular: its egalitarian treatment gives a minority preference type a voice regardless of its share. The continuous mirror covers the computational question of evaluating ESR for such a society; it does not claim to continuize the paper’s strategic or axiomatic results.
I expect this problem to be tractable. Its connection to the discrete problem is exact: any finite electorate with the same supported preference types produces the same type-level ESR computation, no matter how many duplicate citizens it contains. The continuous formulation makes that support-based computation explicit and removes population size from the runtime. It also raises a useful follow-up: how sensitive is ESR to a type’s appearance or disappearance as its mass approaches zero? A separate, mass-sensitive version—where a type’s share affects its influence—would be a further question, not this mirror.
The weak point is central: the numerical masses do not affect the ESR lottery; only whether a type has positive mass does. A reader expecting \(\mu_t\) to weight preferences in the way it weights scores will find this mirror thin. But it preserves the paper’s rule rather than modifying it: ESR’s per-agent guarantees and duplicate-insensitive process make support-only behavior an exact feature of its egalitarian design.
The serious objection is to the *continuous-population interpretation* of Theorem 2, not to its computational anchor: the paper does state a polynomial-time algorithm for ESR. For any distribution \(\mu\), however, the algorithm depends only on \(\operatorname{supp}(\mu)\). Agents with the same ranking follow the same stages, and their LP constraints are duplicates, so one representative per supported ranking suffices. Thus \(F(\mu)=f(\operatorname{supp}(\mu))\): within any fixed support, changing the masses changes nothing. A type with mass \(\varepsilon>0\) keeps the same influence as its mass approaches zero, then loses it entirely at zero.
That makes the proposed \(O(\mathrm{poly}(m,\tau,L))\) computation exact but thin as a continuization: its numerical population distribution is irrelevant; the problem is to run ESR on the set of rankings present. Deduplicating agents is a useful high-multiplicity implementation of the paper’s existing algorithm, yet it does not bring the mass vector into the computational question. Weighting constraints or reservation rates by \(\mu_t\) would make masses matter, but would define a different mechanism. The paper’s own egalitarian motivation—giving minority opinions substantial weight—makes that redesign especially hard to present as ESR itself.
The best counterexample to this objection is the assignment domain. The paper connects ESR to PS there, and a population of student types with proportionally scaled school capacities gives a natural, mass-sensitive continuum assignment problem. I cannot rule that out as a worthwhile mirror. The large-market PS literature gives it a continuum and limit foundation, though its results are analytic rather than a complexity classification; under ChoCo’s criteria, that supports the regime rather than settling the computational question. [Che and Kojima, *Asymptotic Equivalence of Probabilistic Serial and Random Priority Mechanisms*](https://onlinelibrary.wiley.com/doi/abs/10.3982/ECTA8354)
So the strongest negative case is narrow: the stated ESR mirror largely reduces to support compression, and a mass-sensitive version would change the rule. That does not defeat the assignment/PS route. I would call the case against the proposed anchor meaningful but weak as an argument that no worthwhile mirror 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.