d4-journals-jair-1999-0008

Theorem 3 is a named NP-completeness result, but its input already is a rationally weighted distribution over complete ranking types, and its objective is the proposed population agreement objective. Mapping each ordering function \(f_i\) to a type with mass \(w_i\) is exact in both directions, so the mirror merely renames an existing model and fails bit \(b\) as already continuous.

The objection that survived

Theorem 3 permits arbitrary rational weights summing to one, so those weights already function as type masses and there is no population discretization to continue.

What the mirror covers

The proposed mirror covers Theorem 3's hardness for weighted mixtures of tier rankings; it does not recast Theorem 1's online Hedge guarantee, Theorem 4's exact algorithm for two-level rankings, Theorem 5's approximation guarantee, or the metasearch experiments.

Open questions for a prover

The case FOR (proponent)

My lead mirror is Continuous Tiered-Preference Consensus. Consider a large professional association choosing a public order for a fixed slate of proposals. Each member places every proposal in one of three priority tiers. A member’s type is that complete tier assignment \(f_t:X\to\{0,1,2\}\); \(\mu_t\) is the fraction of members with that type. The intended regime is \(n\gg\tau\): many members, with repeated response patterns under a shared questionnaire.

For each type, define \(R_t(u,v)=1\) if \(f_t(u)>f_t(v)\), \(0\) if \(f_t(u)<f_t(v)\), and \(1/2\) if the proposals are in the same tier. Given the finite slate \(X\), the \(\tau\) supported types with binary-rational masses summing to one, and a rational threshold \(q\), ask whether there is a strict total order \(\rho\) such that
\[ \sum_{\substack{u,v\in X\\ \rho(u)>\rho(v)}}\ \sum_t \mu_t R_t(u,v)\ \ge q. \]
The optimization version asks for an order maximizing that score. This preserves the paper’s central decision: choose one total order to maximize agreement with aggregated pairwise preferences. It does not simplify the ranking objective.

The anchor is Theorem 3, proved in this paper by reduction from CYCLIC-ORDERING (citing Galil and Megiddo, 1977, and Garey and Johnson, 1979). It states that, for any \(S\) with \(|S|\ge3\), the following decision problem is NP-complete: given a rational threshold \(\lambda\), a set \(X\), ordering functions \(f_i:X\to S\), and rational weights \(w_i\in[0,1]\) summing to one, form
\[ \mathrm{PREF}(u,v)=\sum_{i=1}^{N}w_iR_{f_i}(u,v), \]
where \(R_{f_i}\) is the pairwise preference induced by \(f_i\). Decide whether some total order \(\rho\) has
\[ \mathrm{AGREE}(\rho,\mathrm{PREF}) =\sum_{\rho(u)>\rho(v)}\mathrm{PREF}(u,v)\ge\lambda. \]
That is the underlying ordering problem, not merely a result about an encoding.

The connection is exact. Set \(S=\{0,1,2\}\), treat each \(f_i\) as a population type of mass \(w_i\), and combine duplicate types by adding their masses. The resulting continuous instance has the same pairwise scores and the same feasible orders. Conversely, listing the supported types of any continuous instance gives an instance of Theorem 3. This is why the authors should recognize the mirror: their theorem already optimizes agreement with a weighted mixture of rank orderings. The population interpretation gives those weights the meaning of proportions of people with indistinguishable preferences.

I expect this mirror to be NP-complete, with hardness transferring (Class B). A discrete electorate with \(n_t\) members of type \(t\) has masses \(\mu_t=n_t/n\), and its average agreement is the continuous objective up to normalization. Moreover, the paper’s hardness construction uses uniform rational weights, so the hardness is present even for an explicit finite electorate; the reduction’s combinatorics lie in the items being ordered. It is not hardness created by fractional population mass. Further questions include whether small support \(\tau\) yields tractability, and whether continuous rational masses change approximation or parameterized complexity.

The soft spot is also unusually clear: the paper calls these weights the importances of ranking experts, not population shares. Recasting experts as people changes the application story, although it does not change the problem or objective. More seriously, because Theorem 3 already takes a rational distribution over ranking types as input, a strict novelty test could call this a collision: the mirror is mathematically the same finite-support distribution problem, not a newly opened computational question. My positive claim is therefore that this is a highly credible continuous-population interpretation with a direct named hardness anchor—not that continuization newly produces the hardness result.

The case AGAINST (opponent, writing after the proponent)

Theorem 3 already has the proposed mirror’s population distribution as its input. Take \(T=\{f_i\}\) and set \(\mu_{f_i}=w_i\), merging duplicate types. Then \(\mathrm{PREF}(u,v)=\sum_t\mu_tR_t(u,v)\), and the agreement threshold and feasible total orders are identical. The weights are arbitrary binary rationals summing to one, so there is no integer-voter restriction to relax. Here \(N\) is precisely the support size \(\tau\), and each \(f_i:X\to\{0,1,2\}\) is the proposed complete preference type. The paper also states the hardness for every \(S\) with \(|S|\ge3\), covering broader tier alphabets. Calling the types association members gives a plausible population story, but leaves the computational problem unchanged.

That makes this a collision in the programme’s sense: the paper itself proves the complexity result for a finite-support distribution over preference types. It is not merely an outside answer to a newly posed continuous question. Studying parameterized algorithms in \(\tau\) could be worthwhile, but it would refine the paper’s existing weighted-ranking problem; it would not supply a new problem created by continuization. A proposal that changes the objective—say, adding population control or evolving feedback—could also be worthwhile, but it would need its own anchor in the paper’s results.

This is a strong case against the proposed mirror. The universal claim is weaker: I cannot rule out valuable population-control or online-feedback questions in this domain. Those would be follow-on research questions, rather than continuous mirrors of Theorem 3.

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.