| paper | d4-conf-ijcai-2009-0318 |
| 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{PSPACE}\)-complete, hence \(\mathrm{NP}\)-hard, under promise-preserving polynomial-time reductions. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 6
statement extracted from the paper’s text layer
Given a finite goods set \(V\), a finite support \(\mathcal{T}\) of satisfiable CI-net types \(N_t\) over \(V\) with binary-rational masses \(\mu_t\ge 0\) summing to \(1\), bundles \(X,Y\subseteq V\), and a binary-rational threshold \(q\in[0,1]\), decide whether \(\sum_{t:\,X\succ_{N_t}Y}\mu_t\ge q\).
The society is a distribution \(\mu\) over complete preference types, each represented by a satisfiable CI-net. The input fixes two bundles and a threshold; the decision asks whether the mass of types that strictly prefer the first bundle to the second reaches that threshold.
The mirror covers Proposition 6's dominance result, including its stated restricted fragments. It leaves Proposition 7's SCI-net tractability result, Proposition 8's satisfiability result, and the paper's other results unaddressed.
The strongest mirror I see is Mass-Dominance\(_\infty\), anchored on Proposition 6.
Proposition 6 says that DOMINANCE for satisfiable CI-nets is PSPACE-complete, even under each of three restrictions: every statement compares singleton sets and has no negative preconditions; every statement compares singleton sets and has no positive preconditions; or every statement is precondition-free. DOMINANCE asks, given a CI-net \(N\) and bundles \(X,Y\), whether \(X \succ_N Y\). The paper establishes this result with reductions, using cited PSPACE-completeness for dominance in satisfiable binary CP-nets as a starting point for two of the restrictions.
For the continuous version, fix a finite set of indivisible goods \(V\). An instance gives a finite support \(\mathcal{T}\) of satisfiable CI-net preference types \(N_t\) over \(V\), with binary-rational masses \(\mu_t \ge 0\) summing to \(1\), two bundles \(X,Y\subseteq V\), and a rational threshold \(q\in[0,1]\). Ask whether
\[ \sum_{t:\,X\succ_{N_t}Y}\mu_t \ge q. \]
A type is the agent’s induced preference relation, represented by a CI-net; agents of the same type are indistinguishable for this question. The answer is yes or no. There is no optimization action: the quantity being tested is the fraction of society that strictly prefers \(X\) to \(Y\). Types for which the bundles are incomparable contribute no mass to that sum.
A plausible regime is a large membership organization comparing two bundles of indivisible benefits, where standardized roles or contracts produce a small number \(\tau\) of recurring conditional preference templates among \(N\) members, with \(N\gg\tau\). The continuous society records each template’s fraction of the membership. This keeps the population as the continuous object; the bundles themselves remain discrete. It also connects directly to the paper’s fair-division motivation: dominance between bundles is the reasoning operation behind questions such as who envies whose allocation.
This mirror inherits Proposition 6’s hardness exactly. Set \(\tau=1\), \(\mu_1=1\), and \(q=1\); the mass query is the original DOMINANCE instance. The paper’s hardness therefore survives in a one-type society, including when that type is in any of the stated restricted fragments. I expect this mirror to fall on the inherited-hardness side of the trichotomy: the society can be large, but the difficult combinatorics remain in reasoning over bundles and worsening-flip sequences.
The scope is deliberately narrow: it mirrors Proposition 6’s dominance question as a population-level preference query. It does not claim a complexity result for finding envy-free or Pareto-efficient allocations; the paper only sketches those applications. Natural follow-up questions are which CI-net fragments make the mass query tractable, and how aggregate envy queries behave when the compared bundles vary by type.
The weakest point is that Proposition 6 concerns one agent’s represented preference, while Mass-Dominance\(_\infty\) aggregates that predicate across a society. The population wrapper adds a meaningful collective question, but it does not uncover a new tractability gain: one type already preserves the full hardness. I think the mirror remains credible because dominance is the paper’s core reasoning problem and its fair-division discussion gives that reasoning a multi-agent role. A referee might still prefer a continuous allocation problem; this argument does not claim that such a problem has a named result in the paper.
The strongest objection is that Mass-Dominance changes the paper’s query into a prevalence statistic. For each supported CI-net type, one asks the original dominance question, then adds the masses of the types that answer yes. The paper gives no collective decision rule that uses this statistic. A fair-division version would be more compelling, but it would need to specify how bundles are assigned across types and whether fairness means no supported type envies, or only that the envious mass is below a threshold. Those choices are additional modeling work.
That objection does not defeat the mirror. The mass query is well-defined, and the fair-division setting gives it a plausible use: measuring how much of a large membership envies one bundle relative to another. Repeated preference templates make the high-multiplicity regime credible. The fact that \(\tau=1\) recovers the original PSPACE-complete query does not count against it; it establishes hardness for the continuous version.
So I cannot honestly defeat the anchor. The negative case is weak here: Proposition 6 supports a worthwhile continuous mirror, even though the paper itself does not supply the population-level question or its application.
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.