| paper | d4-conf-aaai-2018-1085 |
| 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: \(\mathrm{NP}\)-complete for every fixed \(k\ge 3\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 7
statement extracted from the paper’s text layer
Given a finite candidate set \(C\), a distribution \(\mu\) over complete rankings of \(C\) with \(\tau\) positive-mass types, and fixed \(k\ge3\), decide whether \(C\) can be partitioned into \(k\) sets such that, after restricting the rankings to each set and aggregating identical projections, the positive-mass rankings can be ordered so that each preference direction for every candidate pair occupies an interval.
Each type is a complete ranking \(t\) carrying rational mass \(\mu_t>0\). The decision variable is a partition \(C=C_1\dot\cup\cdots\dot\cup C_k\); there is no objective, and each projected support is tested for single-crossing. For every fixed \(k\ge3\), the problem is NP-complete, and its answer is invariant under changes to positive masses.
The mirror covers Theorem 7's NP-completeness for alternative partition and also yields a continuous two-community version of Theorem 3. It does not address Theorem 4's local-swaps result or the other entries in the paper's complexity overview.
I would lead with Theorem 7. Let \(C\) be a finite candidate set, and let the society be a distribution \(\mu\) over complete rankings of \(C\), with \(\tau\) positive-mass ranking types and binary rational masses summing to one. For any candidate set \(B\subseteq C\), project each ranking onto \(B\) and aggregate the masses of rankings that become identical. Call this projected society single-crossing when its positive-mass rankings can be ordered so that, for every pair of candidates, each preference direction occupies an interval in the order. This is the paper’s single-crossing condition applied to a society represented by masses.
A plausible regime is a large election over a recurring, relatively small set of complete ballot types: for example, \(n=r\tau\) voters with \(r\) voters of each type and \(r\) large. Types are complete descriptions of voters for this problem because only their rankings matter. One interpretation of the question is whether an agenda can be split into a few policy bundles, each of which induces a one-dimensional ordering of voters; different bundles may have different orderings.
The continuous problem I would call Continuous \(k\)-Agenda Single-Crossing Partition is: given \(C,\mu\), and fixed \(k\), can \(C\) be partitioned into \(k\) sets \(C_1,\ldots,C_k\) such that the society projected onto each \(C_i\) is single-crossing? A solution is the candidate partition; there is no objective to minimize. This is the same structural question as the paper’s alternative-partition problem, with the population recorded by type masses.
The anchor is Theorem 7, proved in this paper: for every fixed \(k\ge 3\), it is NP-complete to decide whether a given profile’s alternative set can be partitioned into \(k\) sets so that the restriction of the profile to each set is single-crossing. The paper proves this by reduction from \(k\)-colouring. The continuous version is NP-complete for every fixed \(k\ge 3\): a discrete profile maps to masses proportional to its type counts, and conversely a continuous instance can be represented by one voter per supported ranking for this question. The answer depends on which types have positive mass, not their particular positive weights. Replicating every type any number of times preserves the answer, so hardness remains in regimes with many voters per type. This is a Class B mirror: the hardness lies in the candidate agenda and transfers to the continuous population.
A second, distinct mirror comes from Theorem 3, also proved in this paper. Its full result is: given a profile with \(n\) voters and \(m\) alternatives, one can decide in time \(O(n^4m^2)\) whether the voters can be partitioned into two groups such that each group’s profile is single-crossing. The proof reduces the check to 2SAT.
Its continuous counterpart, Continuous Two-Community Single-Crossing Partition, takes \(C,\mu\) and asks whether there is an allocation \(x_t\) for each type \(t\), with \(0\le x_t\le\mu_t\), such that the two subpopulations of masses \(x_t\) and \(\mu_t-x_t\) are both nonempty and single-crossing. The output is the mass allocation; again, this is a feasibility question. This is a direct match to partitioning voters, including the possibility that a type’s mass is split across communities. The paper’s algorithm gives a polynomial-time solution: represent each supported type by two identical voters and apply Theorem 3. The two copies can represent whether a type appears in one community or both, which is all the single-crossing checks require. This is a Class A mirror, running in time polynomial in \(m\), \(\tau\), and the input bit length \(L\). It raises natural follow-ups: what happens for three or more communities, and what changes if each community must receive a minimum share of the population?
The mirror is plausible because neither question is weakened: rankings remain complete, the same single-crossing test is applied, and the candidate agenda remains finite. The population alone is represented continuously. Theorem 7 is the stronger anchor for the programme’s complexity question; Theorem 3 shows that mass allocation also yields a precise algorithmic mirror.
The soft spot is that these structural tests largely depend on support, rather than on the numerical mass values. Theorem 7 especially is a conservative high-multiplicity extension, not an example where continuous optimization transforms the problem. That makes it a modest continuization, but still a faithful one: the paper’s problem is preserved, the large-population regime is natural, and the hardness boundary is explicit.
The strongest negative pressure is that Theorems 3 and 7 do not use the numerical masses. For Theorem 7, projecting a society onto a candidate set preserves exactly the ranking types that have positive mass; changing their positive weights does not change whether the projected society is single-crossing. This makes the mirror a high-multiplicity classification rather than a use of continuous-optimization machinery. That is a possible argument about research priority, but it cannot rule the mirror out: the programme explicitly includes hardness that survives in the continuous setting.
Theorem 3 also has a direct, sensible mirror. A continuous partition is determined by which ranking types appear in each community. If a type appears in both, split its mass, for example equally. Thus two copies of each supported type encode every possible pair of community supports, and applying the paper’s algorithm to those \(2\tau\) copies decides the question in polynomial time in \(m\), \(\tau\), and the input length. Large electorates with recurring ballot types make this a plausible regime. Requiring each community to have a minimum share would address concerns about tiny communities, but that is an additional constraint rather than a reason the basic mirror fails.
Theorem 7 survives as well. Map each discrete profile to masses proportional to its type counts; its answer is preserved. Conversely, because the property depends on the supported rankings, one voter per supported type suffices to represent a continuous instance. Large populations with recurring ballot types therefore give a natural high-multiplicity setting for the same question.
So I cannot make a responsible case that no worthwhile continuous mirror exists. The mass values’ irrelevance is the strongest honest criticism, and it is only a priority argument. Under the programme’s criteria, both anchors survive; Theorem 7 alone is enough to defeat the universal negative.
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.