| paper | d4-conf-ecai-2008-0194 |
| 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, including axis construction, in \(O(L+m\tau)\) word-RAM time; the decision problem belongs to \(\mathrm P\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Proposition 2
statement extracted from the paper’s text layer
Given \(n\) alternatives and a finite-support distribution \(\mu\) over strict rankings, is there a linear order \(O\) such that every ranking \(t\) with \(\mu_t>0\) is single-peaked with respect to \(O\)? If so, output such an axis.
Types are strict rankings of the alternatives, with rational masses \(\mu_t\) summing to \(1\). The decision variable is a linear order \(O\); feasibility requires every positive-mass type to be single-peaked on \(O\). The masses do not enter an objective, and the algorithm operates on the \(\tau\) types in the support.
Covers Section 3’s consistency decision and axis construction. It leaves the compatible-axis counts, communication results, and approximate-single-peakedness extensions aside.
The strongest honest mirror is the paper’s Proposition 2. It proves here that single-peaked consistency for \(m\) voters and \(n\) alternatives can be decided in time \(O(nm)\). The paper’s algorithm returns a compatible axis when one exists and finds a contradiction otherwise; Proposition 2 improves the earlier \(O(mn^2)\) algorithm cited as [2]. This is the paper’s clearest named computational result. It contains no comparable named hardness result, so I would use this tractability result as the sole anchor.
Call the mirror Continuous Single-Peaked Consistency. An instance consists of a set \(X\) of \(n\ge 3\) alternatives and a finite-support distribution \(\mu\) over strict rankings of \(X\). Each positive mass \(\mu_t\) is a binary rational, and the support has size \(\tau\). The question is whether there is a linear order \(O\) of the alternatives such that every ranking \(t\) with \(\mu_t>0\) is single-peaked with respect to \(O\). A YES solution is such an axis; a NO answer means none exists. This is a feasibility problem, so it has no optimization objective: the axis is the decision variable. The mass records population share, while every positive-mass type must satisfy the condition.
A plausible regime is a large electorate—say hundreds of thousands of voters—ranking a modest slate of policy alternatives, with many voters sharing each observed ranking type. The types are complete preferences exactly as in the paper: two voters are alike for this problem when they give the same ranking. When the population is generated by a common latent policy axis, the number of possible ranking types is limited by the slate size even as the electorate grows, so \(N\gg\tau\) is plausible. The axis remains unknown and must be recovered, just as in the paper.
The continuous instance has a direct two-way dictionary with discrete profiles. A profile with \(N_t\) voters of ranking \(t\) gives \(\mu_t=N_t/N\); conversely, rational masses can be multiplied by a common denominator to form a finite profile. Thus the answer is unchanged. Applying the paper’s result to the support gives an algorithm polynomial in \(n,\tau,L\), where \(L\) is the total bit length of the masses; in the paper’s ranking-list model, the axis search takes \(O(n\tau)\). This is a Class A mirror. Its contribution is a tractable support-size formulation of the unknown-axis problem, not a claim that continuous populations make a hard problem easy.
The authors should recognize this as their problem: it preserves the complete rankings, the unknown common axis, and the requirement that every voter preference fit that axis. The mirror covers Section 3’s consistency and axis-finding result. The communication propositions depend on individual voters sending messages, and the paper’s later count of compatible axes is a different target, so I would not use either as an anchor here.
The weak point is that this mirror is very close to compressing a discrete profile by merging repeated ballots, and the masses do not affect the answer except through which types have positive mass. Also, one tiny positive-mass outlier can make the answer NO. That is a real limitation, but it does not make the model incoherent: exact consistency is the paper’s question, and a shared-axis population with repeated preference types is a sensible high-multiplicity regime. A natural follow-up—separate from the anchor—is to minimize the mass that must be removed before the remaining support admits a common axis, connecting the paper’s proposed approximate-single-peakedness direction to a continuous population.
Proposition 2 is a genuine computational result, and its mirror is well-defined. But the proposed continuous version has no population computation in it: for every distribution \(\mu\), the set of compatible axes is determined entirely by its support. For any two distributions with the same positive-mass rankings, even if their masses differ radically,
\[ \{O : \text{every }t\in\operatorname{supp}(\mu)\text{ is single-peaked on }O\} \]
is identical. One arbitrarily small positive-mass outlier has the same veto as half the society.
That makes the claimed support-size algorithm a direct compression of the paper’s existing algorithm. Deduplicate the discrete profile, run the algorithm on its \(\tau\) distinct rankings, and get the same \(O(n\tau)\) bound. The binary rational masses are never read. A continuous distribution can be scaled to an integer profile, but that dictionary adds no computational content here. This is not a complaint that the answer stays the same; it is that changing the population weights cannot change the instance’s feasible axes or the algorithm’s behavior. There is no mass-sensitive question for continuous optimization to resolve.
The strongest repair is the paper’s own approximate-single-peakedness direction: minimize the mass of voters to remove so that the rest share an axis,
\[ \min_O \sum_{t\notin \mathrm{SP}(O)}\mu_t. \]
That is a coherent, population-sensitive problem, and a large electorate with repeated ranking types is a sensible regime for it. But it is a new weighted optimization problem, not a mirror of Proposition 2’s exact consistency theorem. The paper itself presents deleting voters as a possible future problem; any value would come from studying that extension, not from continuizing the named result. Candidate deletion ignores population masses, while covering the profile with several axes changes the task into a different clustering problem.
So the negative case against the anchor is strong but narrow: exact consistency is already solved on the support, and the continuum contributes only weights that have no effect. It cannot honestly rule out the weighted deletion problem as worthwhile; that is where the case against any continuous mirror is weakest.
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.