| paper | d4-conf-ijcai-2018-0499 |
| 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→P discrete result → its continuous mirror
Answer: polynomial-time solvable · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 2
statement extracted from the paper’s text layer
Given a finite candidate set \(X\), ranking types \(T\) with positive rational masses \(\mu_t\) summing to \(1\), and an assignment \(\alpha:X\to\{\mathrm{GOOD},\mathrm{BAD}\}\), does there exist, for each type \(t\), a distribution of its mass over its preference upsets \(A\), together with an upward-closed set \(W\) of approval-mass vectors, such that each candidate’s vector \(q_x\) belongs to \(W\) exactly when \(\alpha(x)=\mathrm{GOOD}\)?
Types are complete preorders over \(X\), each unit of mass receives an integral approval upset \(A\), and \(\nu_{t,A}\) is the mass of type \(t\) assigned to \(A\). Candidate \(x\) has vector \(q_x\) with coordinate \(\nu_{t,A}\) when \(x\in A\), and \(0\) otherwise; the unknown monotone aggregator \(W\) classifies these vectors.
The paper permits identity-sensitive winning-coalition families, whereas \(W\) depends only on masses of preference–approval subtypes; the mirror therefore covers the anonymous regime rather than the full generality of Proposition 2.
fatal: False
The mirror covers Proposition 2’s representability question, with the pairwise characterization in Theorem 1 and the SAT formulation in Corollary 2 as related machinery. It leaves the AS1 explanation-length result and necessary-assignment questions based on reference cases aside.
The strongest mirror is the paper’s NP-hard Inv-NCS problem, in a setting where a large population is distributed over relatively few preference rankings—for example, a large public platform sorting a fixed slate of projects, with many participants sharing each ranking. A ranking type can still be divided into subgroups: each person gets an integral approval set, while the mass assigned to each approval set may be fractional.
My anchor is Proposition 2, proved in this paper. It states that deciding whether a given assignment \(\alpha:X\to\{\mathrm{GOOD},\mathrm{BAD}\}\) can be represented in the noncompensatory sorting model is NP-hard. The decision is over approval sets \(A_i\), each an upset of point of view \(i\)’s complete preorder, and an upward-closed family \(S\) of sufficient coalitions: a candidate is GOOD exactly when its approving coalition belongs to \(S\). The paper proves hardness by reduction from SAT.
Here is a continuous version of that same feasibility question. Call it Divisible Inverse NCS. An instance consists of a finite candidate set \(X\), a list \(T\) of \(\tau\) complete-preorder types with positive rational masses \(\mu_t\) summing to \(1\), and an assignment \(\alpha\). For each type \(t\), let \(\mathcal U_t\) be its preference upsets. Choose nonnegative masses \(\nu_{t,A}\), for \(A\in\mathcal U_t\), satisfying \(\sum_{A\in\mathcal U_t}\nu_{t,A}=\mu_t\). Each unit of mass assigned to \((t,A)\) has the integral approval set \(A\). For each candidate \(x\), form its approval-mass vector \(q_x\), whose \((t,A)\) coordinate is \(\nu_{t,A}\) if \(x\in A\), and \(0\) otherwise. The question is whether there are such masses and an upward-closed set \(W\) of mass vectors for which \(q_x\in W\) exactly when \(\alpha(x)=\mathrm{GOOD}\). A solution can give the nonzero \(\nu_{t,A}\) and generators for \(W\); in particular, \(W\) can be the upward closure of the GOOD candidates’ vectors.
I expect this mirror to be tractable. For each GOOD–BAD pair \((g,b)\), feasibility requires positive mass in some approval subtype that approves \(g\) and not \(b\). Such a subtype exists for ranking type \(t\) exactly when \(g\succ_t b\). If every opposite-label pair has some positive-mass type with that strict preference, allocate a small positive fraction of that type to an upset containing \(g\) but not \(b\). There are finitely many pairs, so these fractions can be chosen to fit within each type’s mass; the remaining mass can receive the empty upset. Thus the continuous decision reduces to checking, for every \((g,b)\), whether some type in the support strictly ranks \(g\) above \(b\), which takes polynomial time in \(|X|\) and \(\tau\). The mass magnitudes matter only through whether they are positive.
This covers Proposition 2’s representability question, not the paper’s explanation-length result or its work on necessary decisions from reference cases. It also generates further questions: how much mass must be assigned to approval subtypes to support an assignment, and what happens to necessary-assignment questions when the reference cases are fixed?
The soft spot is that this mirror makes the collective rule depend on masses of preference-and-approval subtypes, so it is anonymous within each subtype. The paper permits an arbitrary upward-closed family over named voters; its model can distinguish people with the same ranking. That symmetry is a real co-modification. I think the mirror remains recognizable as high-multiplicity NCS because it retains individual integral approvals and an otherwise unrestricted monotone aggregator over type masses, but its positive result depends on studying this anonymous population regime.
The case against has one real hinge: Proposition 2 is a named NP-hard computational result, so there is no “nothing to mirror” objection. The question is whether the proposed continuous version keeps the paper’s accountability problem intact.
In the paper, the input gives a preorder for each *named* point of view, and the unknown winning-coalition family \(S\) may distinguish people with identical preorders. That makes ranking alone an incomplete type: a person’s role in \(S\) can affect the decision. Since \(S\) is itself what Inv-NCS is trying to infer, refining types to include each person’s role may leave essentially one type per person. The paper explicitly allows this identity-sensitive model; an arbitrary monotone rule is not required to treat equal-ranking voters alike.
The proponent’s mass-vector version is the strongest repair. It is coherent for a large, anonymous electorate, but it changes the inferred rule: \(W\) sees only masses of preference-and-approval subtypes. In that model, feasibility reduces to
\[ \forall g\in\alpha^{-1}(\mathrm{GOOD}),\ b\in\alpha^{-1}(\mathrm{BAD}),\ \exists t\in T:\ \mu_t>0\ \land\ g\succ_t b. \]
If no positive-mass type strictly prefers \(g\) to \(b\), every permissible approval set containing \(g\) also contains \(b\), so the approval-mass vector for \(g\) is coordinatewise no greater than the one for \(b\). An upward-closed \(W\) cannot then classify \(g\) as GOOD and \(b\) as BAD. Conversely, when such a type exists for every opposite-label pair, its mass can be split into small pieces, one for each pair, to witness all the separations. Thus the continuous question studies an anonymous submodel in which the population can be divided freely, rather than the paper’s general problem of inferring an identity-sensitive winning rule.
That distinction also limits the proposed follow-on questions. Fixing an anonymous aggregator would ask a different question from Inv-NCS, which asks whether *some* winning rule can explain the assignment. And minimizing the mass of disclosed witnesses, without a minimum-share requirement, risks a zero infimum: every required separation can be witnessed by an arbitrarily small positive mass.
This is a reason to doubt that the mirror captures the paper’s full model, not a decisive reason to reject the anonymous version. A large electorate with a symmetric approval rule is plausible, and the programme explicitly permits co-modifications forced by a population model. Under that reading, the proposed feasibility test is a worthwhile mirror, even if it has a simple answer. The honest negative case is therefore weak: it can press the model mismatch, but cannot establish that no scenario makes this anchor worth studying.
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.