| paper | d4-conf-wine-2023-0032 |
| 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: in \(\mathrm P\), with running time polynomial in \(m,\tau,L\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 16
Given alternatives \(C\), a support \(\mathcal B \subseteq 2^C\) of approval types, and positive rational masses \(\mu_A\) summing to \(1\), does there exist a measurable assignment on \([0,1]\) of a type \(A(x)\in\mathcal B\) and a strict ranking \(\succ_x\) that places every member of \(A(x)\) above every alternative outside it, with \(\lambda(\{x:A(x)=A\})=\mu_A\) for each \(A\), such that for every pair \(a,b\in C\), the indicator of \(a\succ_x b\) is monotone in \(x\), in a direction that may depend on the pair?
A continuum of agents on an ordered axis, with approval sets as types and masses \(\mu_A\). Each agent receives an integral strict ranking consistent with their type; the question is whether these rankings form a single-crossing profile.
The mirror covers Theorem 16’s PSC recognition and completion. It leaves aside the forbidden-subprofile characterization and the general non-betweenness results.
My strongest case is a direct high-multiplicity mirror of Theorem 16, proved in the paper: given a collection of approval ballots, the authors give a polynomial-time algorithm that returns a single-crossing profile of complete rankings consistent with those ballots, or reports that no such profile exists. This is the paper’s main computational result. ([Theorem 16](https://tik-db.ee.ethz.ch/file/046eccefb441798bc3f64bdafd147ccd/))
A plausible regime is a large public consultation on a small slate of policy options: perhaps hundreds of thousands of participants, but only tens or hundreds of distinct approval sets. Take a type to be an approval set \(A\subseteq C\). For this problem, that is a complete description of the constraints on an agent’s unknown ranking: every ranking that puts approved options above disapproved ones is an allowed refinement. The input is a finite support \(\mathcal B\subseteq 2^C\) with positive binary-rational masses \(\mu_A\) summing to \(1\).
Call the resulting problem Continuous PSC Completion. Represent the population by \([0,1]\) with Lebesgue mass. Decide whether there are measurable maps \(x\mapsto A(x)\in\mathcal B\) and \(x\mapsto\succ_x\), where \(\succ_x\) is a strict ranking of \(C\), such that \(\lambda(\{x:A(x)=A\})=\mu_A\); \(\succ_x\) ranks every member of \(A(x)\) above every option outside it; and, for every pair \(a,b\in C\), the indicator \(\mathbf 1[a\succ_x b]\) is monotone in \(x\), with its direction allowed to depend on the pair. The maps describe both the societal axis and the completion of each ballot. A solution is a witness of these maps, representable as finitely many constant intervals; there is no optimization objective.
The mirror is faithful to the authors’ question: it still asks whether the *whole society’s* partial ballots can be completed to single-crossing innate preferences. It does not make outcomes or rankings continuous: almost every point on the axis gets one approval ballot and one integral, strict ranking. The authors should recognize it as their recognition problem with the population represented by type masses.
I expect Class A. From any continuous witness, choose one point of each positive-mass ballot type. Their rankings give a finite PSC completion, since restricting a single-crossing profile preserves single-crossing. Conversely, take a finite PSC witness with one representative per supported type, order the types as in its axis, and give each type a consecutive interval of length \(\mu_A\), using its witness ranking throughout that interval. Thus feasibility depends on the support, while the masses set the interval lengths. Running Theorem 16 on the \(\tau=|\mathcal B|\) representatives gives a polynomial-time algorithm in \(m,\tau,L\), where \(L\) is the mass encoding length; the interval endpoints are rational sums of input masses. The paper also observes that copying an approval row leaves its constraint structure unchanged, which supports this type-based compression. ([Paper, including the duplicate-row observation](https://tik-db.ee.ethz.ch/file/046eccefb441798bc3f64bdafd147ccd/))
I would not use the paper’s background statement that unrestricted non-betweenness is NP-hard as a hardness anchor: it is cited prior work, not a numbered result about the approval-induced instances that the paper solves. This mirror covers Theorem 16’s PSC recognition and completion, not the appendix’s forbidden-subprofile result or general non-betweenness. Natural follow-ons are whether the support reduction and tractability persist for three-valued approval—the paper’s stated next question—and how much population mass must be removed to leave a PSC society, which would make the actual masses matter.
My weakest point is that the fractions do not affect the yes/no answer. The continuous question is sensible and its population interpretation is exact, but its tractability comes from the paper’s finite polynomial-time result; it does not exhibit hardness dissolving under continuization or new continuous-optimization machinery.
Theorem 16 is the strongest anchor, and its mirror is formally sound. For a distribution over approval types, ask whether the positive-mass ballots admit strict-ranking completions whose pairwise comparisons are monotone along an axis. A continuous witness gives a finite PSC witness by selecting one representative of each type. Conversely, Theorem 16 can complete one copy of each supported ballot, and those completions can occupy consecutive intervals of the specified masses. So the mirror is faithful, has a plausible large-consultation setting, and runs in time polynomial in \(m,\tau,L\). The duplicate-row observation supports this reduction. I cannot defeat it by claiming there is no computational result or no sensible high-multiplicity regime.
The case against is about what the continuous model adds. For this recognition question, mass does not enter the constraints: every positive-mass ballot type matters, however small its mass, and only the support affects whether a completion exists. The axis and the constraints remain finite combinatorics; masses merely set interval lengths. Thus the continuum does not regularize the question or bring its algorithm within reach of continuous-optimization methods. Theorem 16 already supplies the answer after duplicate ballots are compressed. That is not a reason to reject a well-posed mirror merely because its answer is known, but it does make this a thin instance of the programme’s promised computational landscape.
A stronger mass-sensitive follow-on would ask for the least mass to remove so the remaining ballots are PSC. But it inherits the same support dependence: retaining any positive mass of a ballot type retains all its constraints, so an optimum can be taken to keep or remove each type in full. That becomes a weighted finite support-selection problem, not a fractional repair of the society. It may be worthwhile research, but it is a new optimization problem rather than a richer continuous version of Theorem 16.
So the negative case is limited: it can argue that this is a mechanically lifted, mass-insensitive mirror with little continuous structure to investigate. It cannot honestly show that the proposed question is incoherent or that the high-multiplicity regime is implausible. If the programme counts a clean complexity classification of such support-compressed societies as worthwhile, this anchor survives.
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.