| paper | d4-journals-jair-2022-0011 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-complete}\), already for \(\tau=1\) and \(\rho=1\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 25
statement extracted from the paper’s text layer
Given a finite object set \(X\), an explicit menu \(\mathcal{X}\subseteq 2^X\setminus\{\emptyset\}\), a finite support \(T\) of linear-ranking types with positive rational masses \(\mu_t\) summing to \(1\), and a threshold \(\rho\in[0,1]\), decide whether types of total mass at least \(\rho\) admit weak orders on \(\mathcal{X}\) satisfying dominance and strict independence relative to their rankings; return those types and witnessing orders.
A society is the distribution \(\mu\) over complete ranking types on \(X\). For each type \(t\), ask whether a weak order on the shared discrete menu \(\mathcal{X}\) satisfies dominance and strict independence relative to \(t\); maximize \(\sum_{t\in T}\mu_t\mathbf{1}[t\text{ admits such an order}]\).
Liftability is checked independently for each type, so the population adds a weighted coverage criterion without interaction across voters; the proponent acknowledges this criterion is new and frames it as an electorate audit.
fatal: False
The mirror covers Theorem 25’s weak-order liftability question for each ranking type. It does not extend the paper’s results on other orderability variants, succinct menus, or how lifted orders are aggregated.
The strongest mirror I can defend is a population coverage problem for lifted preferences. Let \(X\) be candidates or objects, and let \(\mathcal X\subseteq 2^X\setminus\{\emptyset\}\) be the common menu of feasible committees or bundles. A voter type \(t\) is a complete ranking \(\le_t\) of \(X\). The society is a distribution \(\mu\) over the \(\tau\) ranking types present, with each \(\mu_t\) a positive binary rational and \(\sum_t\mu_t=1\).
For each type we may choose a weak order \(\preceq_t\) on \(\mathcal X\). It must satisfy dominance and strict independence relative to \(\le_t\): adding an object worse than every object in a set must worsen that set, adding one better than every object in it must improve the set, and a strict preference between two sets must remain strict when the same admissible object is added to both. The proposed problem, Population \(DI^S\)-Lift Coverage, takes \((X,\mathcal X,\mu,\rho)\) and asks whether valid lifts can be supplied for types of total mass at least \(\rho\). Equivalently, maximize
\[
\sum_{t\in\operatorname{supp}(\mu)} \mu_t\,
\mathbf{1}\!\left[\text{some valid }\preceq_t\text{ exists}\right]
\]
and ask whether the maximum is at least \(\rho\). A solution is the covered set of types and a valid weak order for each.
A plausible regime is a large electorate choosing among committees from a shared candidate set: many voters, but relatively few distinct rankings. Voters of the same type are indistinguishable for this problem, so one lift serves their whole mass. This is a profile-level audit of how much of the electorate’s preference input can be extended over the combinatorial menu while preserving the paper’s axioms. It continuizes the population; the menu of committees remains discrete.
My anchor is Theorem 25, printed as: “\(DI^S\)-WO-Orderability is \(\mathrm{NP}\)-complete.” Its input is a finite \(X\), a linear order \(\leq\) on \(X\), and a family \(\mathcal X\subseteq 2^X\); it asks whether there is a weak order on \(\mathcal X\) satisfying dominance and strict independence with respect to \(\leq\). The paper proves this theorem, while noting that the result was already shown by Maly (2017). Here “WO” means the lifted order may be a weak order; the base order \(\leq\) is given.
The mirror preserves that question exactly when \(\mu\) has one type of mass \(1\) and \(\rho=1\). For an explicit menu and support, a certificate lists the covered types and their weak orders; the axioms can be checked in polynomial time. The one-type special case gives the theorem’s \(\mathrm{NP}\)-hardness, so the coverage decision problem is \(\mathrm{NP}\)-complete. I expect Class B: the hard combinatorics are in the object order and feasible-set family, and remain even when the electorate consists of one repeated type. This is a clean high-multiplicity bridge, but it does not claim that population size is the source of the hardness.
The mirror also generates concrete questions: how does the maximum covered mass behave as \(|X|\), \(\tau\), and the menu structure vary? Can the problem become tractable for structured families such as connected vertex sets, or when parameterized by \(|X|\)? What changes if \(\mathcal X\) is given succinctly? These concern the underlying lifting problem and its population-weighted extension, rather than continuous outcomes or probabilistic preferences.
The soft spot is that the coverage threshold is a new population-level criterion, not a result studied in the paper. At full coverage, \(\rho=1\), the masses matter only through which types have positive support; for \(\rho<1\), the mass weighting adds an explicit robustness question. The authors could reasonably recognize this as a profile-level extension of their liftability problem, given their combinatorial-voting motivation, but the mirror does not turn their axiomatic test into a collective voting rule.
Theorem 25 is the proponent’s strongest anchor, and it clears the basic scope test: it is a named NP-completeness result, and voters with the same ranking can sensibly be grouped into a type. I don’t see a sound objection based on missing multiplicity, identity dependence, a degenerate limit, or prior continuous work.
The best negative case is about what the proposed population problem computes. Fix \(X\) and \(\mathcal X\), and let \(f(t)\) indicate whether ranking type \(t\) admits a valid lifted order. The proposed maximum coverage is exactly
\[
\sum_{t\in\operatorname{supp}(\mu)} \mu_t f(t).
\]
For a threshold question, the certificate can name enough types of total mass at least \(\rho\) and give their lifts. Each type is checked independently; no choice or constraint for one type changes another’s feasibility. The mass weights the individual orderability predicate, while the paper supplies no population-level interaction or decision whose computation uses those weights. The continuum adds a distributional coverage statistic around the theorem’s single-order problem.
A more ambitious version could require a coherent lifting policy across types, aggregate the lifted preferences in an election, or pay to move mass toward liftable rankings. Those might create substantive population computations. But each needs extra structure—policy consistency, an aggregation rule, or costs—that the paper does not study. They would be new problems inspired by the paper, rather than stronger mirrors of Theorem 25. The coverage formulation is the best faithful mirror, and its soft spot is that its threshold and its interpretation as an electorate audit come from outside the paper.
That is a case against spending programme time on this mirror: its population component is a passive weighting of independent feasibility checks, with no continuous optimization structure to investigate. It is not a decisive refutation. The profile-audit interpretation is plausible in combinatorial voting, and the programme allows a well-posed Class B result even when the difficulty remains in the menu. If authors regard the liftable share of an electorate as their problem, this anchor survives; the negative case is therefore honestly weak.
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.