| paper | d4-conf-ecai-2012-0161 |
| 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}\)-hard under polynomial-time Turing reductions; in fact, undecidable under the stated evaluator assumptions. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 5.2
statement extracted from the paper’s text layer
Given a finite set of candidate cohorts \(A\), rational masses \(\mu_a\) with \(\sum_{a\in A}\mu_a=1\), a succinct polynomial-time evaluator for a rational-valued worth function \(V\) on coalition mass vectors \(q\in\prod_{a\in A}[0,\mu_a]\), and a rational payoff-rate vector \(x\), decide whether \(\sum_{a\in A}\mu_a x_a=V(\mu)\) and \(\sum_{a\in A}q_a x_a\ge V(q)\) for every rational feasible \(q\). The input promises at most two hidden strategic types: \(a\) and \(b\) are equivalent exactly when, for every rational feasible base vector \(q\) and every positive rational \(\epsilon\) for which both additions are feasible, \(V(q+\epsilon e_a)=V(q+\epsilon e_b)\).
A cooperative game with a finite set \(A\) of candidate cohorts carrying population mass \(\mu\), coalition choices given by subpopulation masses \(q\), and worth \(V(q)\). The decision variable is a per-unit payoff rate \(x\); the question is whether it is an imputation in the core. Strategic types are equivalence classes under equal marginal worth for every feasible base coalition, and the partition is hidden.
The SAT1 reduction relies on support over individual cohorts and does not establish hardness when equivalent cohorts are aggregated under full marginal equality; a new reduction would be needed.
fatal: False
The mirror covers the IN-CORE result of Theorem 5.2; it leaves CORE-NONEMPTINESS as a separate query, type-recognition complexity, and the paper’s known-type algorithms and kernel and nucleolus results aside.
The strongest honest lead is Theorem 5.2, proved in the paper. It states that, on \(C_k(\mathrm{FP})\) when the game is *not* given in type-based form, both IN-CORE and CORE-NONEMPTINESS are co-NP-complete under randomized reductions, even for \(k=2\). The paper proves the hardness; membership is inherited from results cited in Figure 1. I would mirror its IN-CORE result.
Consider a large cooperative platform whose participants fall into a small number of repeated contract and technology profiles. A society has rational masses \(\mu_a\) over a finite list \(A\) of observable cohorts, with \(\sum_{a\in A}\mu_a=1\). The population can be much larger than \(\tau=|A|\); a coalition may draw any rational mass \(q_a\in[0,\mu_a]\) from each cohort. A polynomial-time worth oracle \(V(q)\) gives the coalition’s value. The strategic partition of the listed cohorts is not supplied.
Here is one precise mirror, Continuous Core Membership with Hidden Mass Types. A payoff rate \(x_a\) gives each unit of mass from cohort \(a\) that rate. Given \((A,\mu,V)\) and a rational candidate rate vector \(x\), ask whether
\[ \sum_{a\in A}\mu_a x_a=V(\mu) \quad\text{and}\quad \sum_{a\in A}q_a x_a\ge V(q) \ \text{for every rational }q\in\prod_{a\in A}[0,\mu_a]. \]
The answer is yes exactly when \(x\) is an imputation that no subpopulation can block.
To make the paper’s hidden-type condition precise in this mass model, use cohort-entry equivalence: \(a\) and \(b\) are equivalent if, for every coalition mass vector \(q\) with \(q_a=q_b=0\), adding the same positive rational mass \(\epsilon\) from either cohort gives the same worth:
\[ V(q+\epsilon e_a)=V(q+\epsilon e_b) \]
whenever both additions are feasible. The input promises at most two such classes but does not provide their partition. This models the computational question of recovering strategic classes from a succinct worth description.
The hardness-transfer case has a concrete reduction. Start with the paper’s SAT1 construction: take a Boolean formula \(\phi'\) with at most one satisfying assignment and form \(\phi=\phi'\land x_\alpha\land x_\gamma\land\neg x_\beta\), using fresh variables. Give every variable a cohort of mass \(1/n\), and set \(V(q)=1\) exactly when the assignment that sets \(i\) true iff \(q_i>0\) satisfies \(\phi\); otherwise set \(V(q)=0\). This oracle is polynomial-time computable. If \(\phi\) is unsatisfiable, the zero rate vector is in the core. If \(\phi\) is satisfiable, a coalition with the satisfying support has worth \(1\), so the zero vector is blocked. The grand coalition has worth \(0\), since its support includes \(x_\beta\). On this construction, cohort-entry equivalence is exactly the paper’s comparison of \(v(S\cup\{i\})\) and \(v(S\cup\{j\})\); the SAT1 construction has at most two resulting classes. Thus the continuous core-membership question retains the randomized hardness on instances with at most two hidden classes.
I expect this mirror to be Class B: the Boolean combinatorics remain in the compact worth oracle, and the continuous mass variables do not remove the blocker. This case covers Theorem 5.2’s IN-CORE hardness; it does not claim to mirror the known-type nucleolus and kernel algorithms. Follow-up questions include whether the continuous problem has a matching membership bound, whether hardness survives for continuous or piecewise-linear worth functions, and how supplying the type partition changes the result.
The weakest point is the type notion. Cohort-entry equivalence compares additions when both candidate cohorts are absent. A stricter atomless, per-agent notion would also compare marginal effects against coalitions already containing other mass from those cohorts, and the reduction above does not establish the two-class promise for that notion. So the core problem is a direct continuous-population version, but its connection to the paper’s exact type promise depends on whether authors and referees accept cohort-level entry as the right continuization of strategic equivalence.
The proponent chose a strong anchor: Theorem 5.2 gives a named computational result, and its setting—many players in a small number of repeated types—is a natural high-multiplicity regime. I see no honest case based on absent results or absent multiplicity. The strongest objection is to the proposed continuous reduction, not to the idea of a mirror.
Its worth oracle makes a coalition worth \(1\) whenever its *support* encodes the satisfying assignment, however little mass it takes from each selected cohort. That preserves the Boolean reduction, but it does so by treating each named variable as a separate coordinate. The claimed two-type condition does not make the worth depend only on the mass selected from each type.
For example, let \(U\) be the variables true in the unique satisfying assignment. The construction forces at least two variables into \(U\). Choose a small rational \(\delta\le 1/n\). Taking mass \(\delta/|U|\) from every cohort in \(U\) gives total mass \(\delta\) and worth \(1\). Taking mass \(\delta\) from just one cohort in \(U\) gives the same total mass from that proposed type, but worth \(0\): the support misses required variables. So the oracle cannot be represented as a worth function of the two aggregate type masses. Cohort-entry equivalence captures equality of certain marginal effects; it does not establish the invariance under fractional redistribution that a genuine two-type mass model needs.
A repaired version would describe the society by masses of complete types and let a coalition be specified by how much mass it takes from each type. That makes core membership a sensible continuous question, but the SAT1 construction no longer proves its hardness: the hidden assignment is carried by distinctions among cohorts that the two-type model has aggregated away. A different proof, and a more specific worth-function model, would be needed. Keeping the variable-specific coordinates preserves the proof, but then the construction has support size growing with the formula and arbitrarily small mass acts like an entire Boolean player. That is a weak high-multiplicity interpretation.
This objection does not show that no worthwhile mirror exists. A continuous core-membership problem for type-level worth functions could still be worth studying; the paper’s own high-multiplicity results make that regime credible. But the proponent’s reduction does not establish that Theorem 5.2’s hidden-type hardness transfers to such a model. My honest negative case is therefore limited: this anchor fails as evidence for a continuous hardness result, while the broader claim that no scenario yields a worthwhile mirror remains 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.