| paper | d4-conf-ijcai-2017-0331 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable; an admissible order can also be constructed in polynomial time. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a finite candidate set \(C\) and a rational distribution \(\mu\) over complete weak rankings, let \(R=\operatorname{supp}(\mu)\) and \(U_\mu=\bigcup_{r\in R}\operatorname{top}_r(C)\). Determine whether there is a linear order \(>\) of \(C\) satisfying the paper’s top-monotonicity conditions for every pair \(r,q\in R\) and every \(S\in\{C\}\cup\binom{U_\mu}{3}\), and construct such an order if one exists.
The types are complete weak rankings \(r\) with positive rational masses \(\mu_r\); the society has \(\tau=|R|\) types. The decision object is a linear order \(>\) of \(C\), with no optimization objective. For each eligible \(S\), each \(x\in\operatorname{top}_r(S)\), each \(y\in\operatorname{top}_q(S)\), and each \(z\in S\), if \(x>y>z\) or \(z>y>x\), require \(y\succeq_r z\) when \(z\in\operatorname{top}_r(S)\cup\operatorname{top}_q(S)\), and \(y\succ_r z\) otherwise. The finite-alternative interval condition is automatic; the masses matter only through which types have positive mass.
The mirror covers Theorem 3’s recognition and order-construction result for arbitrary profiles of weak rankings; Theorem 2 is a restricted case. It does not cover downstream voting consequences or the paper’s single-peakedness illustration.
The strongest anchor is Theorem 3, proved in this paper. It says that, given a finite set of alternatives and a finite profile of possibly weak preference orders, deciding whether there is a top-monotonic order of the alternatives—and computing one if it exists—is polynomial-time solvable. This is the paper’s full recognition problem; the minimally rich case in Theorem 2 is a restriction, so I would not count it as a separate anchor. The paper mentions Aziz’s NP-hard result for extending partial orders, but that is cited background, not a numbered result proved here, and it concerns a different problem.
My mirror is Continuous Top-Monotonic Recognition. An instance is a finite candidate set \(C\) and a distribution \(\mu\) with rational masses over complete weak rankings of \(C\). The \(\tau\) rankings with positive mass are the types. The question is whether there is a linear order \(>\) of \(C\) that is top-monotonic for every type in the support. A solution is such an order, or a correct report that none exists; this recognition problem has no optimization objective.
More precisely, let \(top_r(S)\) be the alternatives ranked highest by type \(r\) within \(S\), and let \(U_\mu=\bigcup_{r\in\operatorname{supp}(\mu)}top_r(C)\). Check the paper’s top-monotonicity conditions on the family consisting of \(C\) and every triple from \(U_\mu\), for every pair of support types \(r,q\), including \(r=q\). Whenever \(x>y>z\) or \(z>y>x\), with \(x\in top_r(S)\) and \(y\in top_q(S)\), require \(y\succeq_r z\) if \(z\in top_r(S)\cup top_q(S)\), and \(y\succ_r z\) otherwise. The finite-alternative interval condition is automatic. These are the paper’s conditions applied to the distribution’s positive-mass types.
A plausible regime is a large public consultation on a fixed slate of policy options: millions of residents submit complete rankings, perhaps with ties, but many share the same ranking. Types are those rankings, and their masses are population shares; \(n\) can be enormous while \(\tau\) is comparatively small. This continuizes the population while leaving the alternatives and the paper’s recognition question intact. The authors should recognize it as their problem because it asks for exactly the same societal order over exactly the same preference types.
The bridge is exact. Given rational \(\mu\), multiply all masses by a common denominator to obtain a finite profile with the same support; conversely, a finite profile gives its empirical distribution. Repeating voters of an existing type cannot change whether a qualifying order exists. Thus Theorem 3’s algorithm can run on one representative of each support type, giving the paper’s stated \(O(m^4 n^2)\) bound with \(n=\tau\): \(O(m^4\tau^2)\), plus input handling. The masses’ bit length \(L\) does not affect the answer, so the mirror is polynomial in \(m,\tau,L\). I expect it to be tractable (Class A), though the tractability comes from the paper’s structural algorithm and support compression, not from a new continuous-optimization technique.
The mirror covers Theorem 3’s recognition and axis-construction result, not winner determination or other consequences of top-monotonicity. A natural follow-on is to ask for the minimum population mass that must be reassigned among ranking types before the resulting support admits a top-monotonic order.
The weakest point is also clear: the masses have no effect as long as they stay positive. This is a sensible high-multiplicity version of the authors’ problem, and it can make computation depend on the number of types rather than the number of residents, but it does not reveal a new mass-sensitive phenomenon or dissolve discrete hardness.
The strongest case against this anchor is that Theorem 3 recognizes a property of the support, not of the population’s mass distribution. Its mirror has predicate \(TM(\operatorname{supp}\mu)\): once a type has positive mass, its size is irrelevant. This makes recognition discontinuous as mass tends to zero. For example, let \(r_1:a\succ b\succ c\), \(r_2:b\succ c\succ a\), and \(r_3:c\succ a\succ b\), and set
\[
\mu_\epsilon=(1-\epsilon)\delta_{r_1}+\frac{\epsilon}{2}\delta_{r_2}+\frac{\epsilon}{2}\delta_{r_3}.
\]
At \(\epsilon=0\), the single ranking is top-monotonic. For every \(\epsilon>0\), the support contains the three rankings that form a Condorcet cycle, so it is not top-monotonic. Thus an arbitrarily small subpopulation can change the answer. The mirror uses no mass-sensitive or continuous method: it runs the finite recognizer on the support.
A more population-sensitive proposal would tolerate a small mass of exceptions or ask for the minimum mass that must be changed or removed to make the support top-monotonic. That could be a worthwhile robustness problem, but it adds an optimization question absent from Theorem 3. It does not rescue the case against the exact mirror; it marks the boundary between that theorem’s recognition task and a new one.
This objection is still too weak to defeat the proponent under ChoCo’s stated criteria. The model explicitly represents a society by positive-mass types, and the public-consultation scenario makes repeated ranking types plausible. Dependence on every positive-mass type may be brittle, but it does not make the high-multiplicity version ill-posed. Nor can I use the fact that the masses do not affect the verdict as a disqualifier: the programme’s rules explicitly allow a valid mirror whose answer is unchanged. The honest negative case is therefore about limited conceptual novelty, not about the absence of a worthwhile continuous mirror. I cannot responsibly claim that it defeats Theorem 3’s 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.