| paper | d4-journals-jair-2018-0023 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\text{NP-hard}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given m alternatives and \tau trichotomous weak-order types with positive binary-rational masses \mu_t summing to one, compute a trichotomy P maximizing S_\mu(P)=\sum_{a\succ_P b}\Delta_\mu(a,b) , where \Delta_\mu(a,b)=\sum_t\mu_t(\mathbf{1}[a\succ_t b]-\mathbf{1}[b\succ_t a]) ; measure complexity in m,\tau , and the mass bit length.
The society is a distribution over complete trichotomous weak-order types. The decision variable is an ordered three-partition of the alternatives, and the objective is the sum of its downward pairwise margins \Delta_\mu(a,b) .
The mirror covers (3,3) -Kemeny winner determination and the transitive max- 3 -OP restriction; it leaves the paper’s other input/output restrictions and polynomial cases untreated.
The strongest mirror is the paper’s \((3,3)\)-Kemeny winner problem, expressed with a high-multiplicity electorate. A plausible regime is a very large review panel considering the same finite slate of proposals. Each reviewer assigns every proposal to one of three ordered tiers, such as advance, hold, or reject. A type is the reviewer’s complete tiering of the slate; its mass is the fraction of reviewers with that tiering. With many reviewers and a fixed slate, the number \(n\) of reviewers can greatly exceed the number \(\tau\) of distinct tierings.
Here is the continuous problem I would hand to a prover. Given \(m\ge3\) alternatives and \(\tau\) trichotomous weak-order types \(t=(T_t\succ_t M_t\succ_t B_t)\), each with positive binary-rational mass \(\mu_t\) and \(\sum_t\mu_t=1\), define the per-capita pairwise margin
\[
\Delta_\mu(a,b)=\sum_t\mu_t\bigl(\mathbf{1}[a\succ_t b]-\mathbf{1}[b\succ_t a]\bigr).
\]
For each possible output trichotomy \(P\), define its score as
\[
S_\mu(P)=\sum_{a\succ_P b}\Delta_\mu(a,b).
\]
Continuous \((3,3)\)-Kemeny Winner asks for an output trichotomy \(P\) maximizing \(S_\mu(P)\); any maximizer is a solution. Equivalently, its threshold version asks whether some \(P\) has \(S_\mu(P)\ge q\), for a rational \(q\). The instance is the alternatives, supported types, and masses; complexity is measured in \(m,\tau\), and the mass bit length \(L\). This is exactly the paper’s underlying winner question, with the population represented by type masses. Only the population is continuized: the collective outcome remains a three-tier order.
My lead anchor is Theorem 4, proved in this paper. It states that determining the winning ordering for a \((j,k)\)-Kemeny election is NP-hard when \(j\ge3\) and finite \(k\ge3\), or when \(j=L\) and finite \(k\ge3\); in particular, \((3,3)\)-Kemeny winner determination is NP-hard. The proof uses the paper’s max-cut reductions and shows how integer-valued weighted tournaments can be induced, up to a positive scale factor, by profiles of trichotomous weak orders. Thus the hardness survives grouping identical ballots into types and normalizing their counts into masses. The scale does not change which output maximizes the score. The max-cut hardness is established earlier; Theorem 4’s Kemeny hardness is proved here.
For the same problem with a transitivity promise, there is a second worthwhile anchor: Theorem 1, part 2, proved here. It states that max \(k\)-OP is NP-complete even on transitive weighted tournaments, for every \(k\ge3\). Its continuous mirror is Transitive Continuous Three-Tier Winner: use the instance and objective just defined, with the additional promise that \(\Delta_\mu(a,b)>0\) and \(\Delta_\mu(b,c)>0\) imply \(\Delta_\mu(a,c)>0\) for distinct alternatives. Ask for a maximizing three-tier output. The paper’s reduction gives rational weighted tournaments, which can be scaled to integer weights and represented by trichotomous profiles; the distribution therefore gives a precise population version of this restricted problem. This is a distinct, informative promise case: the majority relation can be transitive and winner determination can still be NP-hard.
I expect hardness transfers for both questions, Class B in the programme’s trichotomy. Indeed, any rational mass vector has a common denominator \(D\), so multiplying every mass by \(D\) gives a finite profile with integer voter counts and exactly the same winners. Conversely, any finite profile gives such a distribution. This is the high-multiplicity bridge, not a claim that continuity itself is novel. It also means the mirror preserves the problem rather than simplifying it until it becomes tractable; the authors should recognize both questions as their winner problem and a natural restricted version of it. The paper’s small-committee example is a poor population regime, but a large panel repeatedly reviewing a common slate is a credible one.
The mirror covers Section 5’s \((3,3)\)-Kemeny winner determination and, separately, the transitive max-\(3\)-OP case underlying Theorem 1, part 2. It does not continuize outcomes, time, or axioms. Further questions include whether the same problem is fixed-parameter tractable in \(\tau\), whether useful approximation algorithms exist, and where the polynomial boundary lies for societies whose margins are *purely acyclic* rather than merely transitive. The paper’s polynomial results for purely acyclic max \(k\)-OP make that last boundary especially concrete.
The weakest point is also clear: with rational masses and a scale-invariant winner objective, every continuous instance can be expanded into a finite profile. So this is a strong, faithful high-multiplicity mirror, but it does not suggest that the hardness will dissolve or create new fractional outcomes. Its case is for studying the complexity of a population-by-type representation in a credible large-panel regime—not for claiming that this paper’s winning rule acquires different mathematics in the continuum.
I cannot make a strong honest case that no worthwhile mirror exists. Theorem 4’s \((3,3)\)-Kemeny winner problem survives the best objection I can find. A trichotomous weak order is a complete type for this rule, and for rational masses a common denominator \(D\) gives voter counts \(n_t=D\mu_t\). The pairwise margins and every output score are multiplied by \(D\), so the maximizing orders are unchanged. A large review panel repeatedly ranking the same slate is a credible high-multiplicity regime.
The paper’s own profile construction makes the mirror more than a loose analogy: it realizes arbitrary integer margins using trichotomous orders, with at most two order types per alternative pair before identical types are combined. Thus the hardness can be expressed with polynomial support size, while the masses have finite binary descriptions. This is a high-multiplicity computational question even though its answer may transfer from the discrete problem. That transfer is not a collision under the programme’s rules.
The transitive max-\(3\)-OP anchor survives as well. Clearing denominators in the reduction’s rational weights preserves their signs, so a trichotomous profile can represent the same transitive margin relation after scaling. It is a promise restriction of the first mirror rather than an independent population question, but it remains well-posed and recognized by the paper’s results.
The strongest case against is narrower: these mirrors offer little prospect of new continuous-optimization structure. The objective depends on the population only through pairwise margins, which can be computed from the supported types; the hard search is over output orders on the alternatives. So this paper may be a weaker priority if ChoCo specifically seeks cases where fractional mass creates new algorithms. But hardness driven by the alternatives, and exact correspondence with finite profiles, are not grounds to dismiss a mirror here. Under the stated criteria, the negative case fails.
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.