| paper | d4-conf-atal-2017-0015 |
| 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}\)-hard under polynomial-time Turing reductions; moreover, \(\mathrm{coNP}\)-hard under polynomial-time many-one reductions. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 5.9
statement extracted from the paper’s text layer
Given a star \(H=(T,F)\), rational masses \(\mu_t>0\) summing to \(1\), and a succinct exact evaluator for a continuous nonnegative worth function \(V:\prod_{t\in T}[0,\mu_t]\to\mathbb{R}_{\ge 0}\) with \(V(0)=0\), decide whether there is a per-capita payoff vector \(p\in\mathbb{R}_{\ge 0}^{T}\) such that \(\sum_t\mu_t p_t=V(\mu)\) and \(\sum_t z_t p_t\ge V(z)\) for every \(z\in\prod_{t\in T}[0,\mu_t]\) whose positive-support types induce a connected subgraph of \(H\).
A finite-type cooperative transferable-utility game on a star: type \(t\) has mass \(\mu_t\), a coalition chooses mass \(z_t\) from each type, its support must be connected, its worth is \(V(z)\), and the allocation assigns per-capita payoff \(p_t\) uniformly within each type.
Covers Theorem 5.9’s core-nonemptiness hardness for nonnegative star games; leaves the other hardness results and the quasi-supermodular tractability results unaddressed.
The strongest positive case I see is Theorem 5.9, the paper’s hardness result for core nonemptiness. It studies the same objects a population mirror needs to preserve: a communication graph, feasible coalitions, coalition worth, and a payoff allocation for the grand coalition.
A plausible high-multiplicity regime is a large resource consortium with many interchangeable firms in each of a modest number of operational roles. A hub-and-spoke communication pattern fits the theorem’s star. Firms in one role share their production characteristics, outside options, and communication neighborhood; the number of firms can be far larger than the number \(\tau\) of roles. In the mirror, role \(t\) has population mass \(\mu_t\), and a coalition can include any mass \(z_t\in[0,\mu_t]\) of that role. Its feasible support—the roles with positive mass—must be connected in the role graph.
The anchor is Theorem 5.9, proved in this paper: given a graph game with a nonnegative characteristic function and a star as its underlying graph, deciding whether the core is nonempty is co-NP-complete. Its proof reduces from SAT, so the hardness is established here, not merely cited.
I would pose the mirror as Finite-Type Continuous Core Nonemptiness on Stars. An instance consists of a star \(H=(T,F)\), positive rational masses \(\mu_t\) summing to \(1\), and a polynomial-size exact evaluator for a nonnegative, continuous worth function \(V\) on the mass vectors \(z\in\prod_{t\in T}[0,\mu_t]\), with \(V(0)=0\). A coalition mass vector is feasible when its support is connected in \(H\). The question is whether there is a type-uniform per-capita payoff vector \(p\in\mathbb R^T\) such that \(p_t\ge 0\), \(\sum_t\mu_t p_t=V(\mu)\), and \(\sum_tz_tp_t\ge V(z)\) for every feasible \(z\). A vector \(p\) satisfying those conditions is a solution. This is the paper’s core question with divisible cohorts and arbitrary within-type coalition masses.
There is a direct hardness case for this formulation, including with a continuous \(V\). Given a Boolean formula \(\varphi\), form \(\psi=\varphi\land y\land\neg w\) using two fresh variables. Thus any satisfying assignment has both a true and a false variable, and the all-true assignment is not satisfying. Make one leaf type for each variable of \(\psi\), plus a hub type, with equal rational masses. For coalition mass \(z\), write \(q_t=z_t/\mu_t\); round each variable coordinate to \(a_i=1\) when \(q_i\ge\tfrac12\), and \(a_i=0\) otherwise. Define \(\beta_i=|2q_i-1|\), and set \(V(z)=\prod_{t\in T}q_t+2q_h\bigl(\prod_i\beta_i\bigr)\mathbf 1[\psi(a)\text{ is true}]\), where \(h\) is the hub.
This evaluator is polynomial size and runs in polynomial time. Although the Boolean test changes at the rounding thresholds, the corresponding factor \(\beta_i\) vanishes there, so \(V\) is continuous. At the all-or-none mass vectors corresponding to connected coalitions, it reproduces the reduction’s relevant worths: the grand coalition is worth \(1\), and a proper satisfying coalition containing the hub is worth \(2\).
If \(\varphi\) is unsatisfiable, so is \(\psi\), and \(V(z)=\prod_tq_t\). The payoff \(p_t=1\) for every type is in the core: its total is \(1=V(\mu)\), and \(\prod_tq_t\le\sum_t\mu_tq_t=\sum_tz_t\). If \(\varphi\) is satisfiable, a satisfying assignment gives a proper, connected coalition containing the hub with worth \(2\). Any core payoff must be nonnegative and sum to \(1\) over the whole population, so that coalition can receive at most \(1\), a contradiction. Thus this mirror is already co-NP-hard, even with uniform masses and a continuous worth function.
I expect B-style hardness transfer: the reduction’s combinatorics live in the number of role types, which represent the formula variables, rather than in how many agents occupy each type. Giving each role an arbitrarily large population does not erase its assignment choice. The precise open questions include the full complexity of the semi-infinite core-feasibility problem, whether fixed \(\tau\) admits efficient algorithms, and what continuous analogue of quasi-supermodularity would recover tractability.
This case covers only Theorem 5.9’s core-nonemptiness result for nonnegative star games. It does not claim to mirror the paper’s least-core, nucleolus, kernel, or quasi-supermodular tractability results.
The soft spot is the worth function: its SAT-gated construction is tailored to the paper’s worst-case reduction, not a natural mining technology. Also, \(\tau\) grows with the formula, so this argument does not establish hardness for a fixed set of types. I still think the mirror is worth asking: it keeps the paper’s coalition and core question, makes population mass genuinely divisible, and exposes that the hardness survives because role-level combinatorics remain after individual multiplicity disappears.
The strongest objection is that Theorem 5.9 does not specify a continuous game. Its input assigns worth to indivisible player subsets. Extending that worth to fractional masses requires new data: how value changes when only part of a type participates. The proponent’s SAT-gated \(V\) is one such choice, designed to preserve the reduction. A more natural production model might yield different core constraints and complexity. So the theorem alone does not supply a unique continuous mirror.
That objection does not defeat the anchor under ChoCo’s scope. A type-level worth function \(V(z)\) is a precise, recognizable population model, and the reduction can persist in an explicit high-multiplicity sequence. Make \(M\) identical clones of every role in the star, with each role’s clones forming a clique and hub clones linked to every leaf role. Give a coalition worth \(V(z)\), where \(z_t\) is the selected mass of role \(t\). The graph’s feasible coalitions then have the star’s support structure. In the unsatisfiable case, the proposed \(V\) reduces to \(\prod_t q_t\), and \(p_t=1\) satisfies every core constraint, including for fractional masses. In the satisfiable case, selecting all clones of the hub and the roles assigned true gives a proper connected coalition worth \(2\), while the grand coalition is worth \(1\). No nonnegative payoff allocation totaling \(1\) can cover that coalition. This works for arbitrarily large \(M\); symmetry also lets any core allocation be averaged to a type-uniform one.
The reduction’s formula grows with the number of types, so it does not establish hardness at fixed \(\tau\). That limits the result, but does not disqualify it: the programme treats \(\tau\) as an input parameter, and finding out that hardness survives mass divisibility is itself a computational result. Nor does the disappearance of singleton constraints in an atomless population help here: this reduction already has zero worth for singletons.
So the honest negative case is weak. The continuous extension is additional modeling structure, and its SAT-based worth function is tailored. But a repeated-role population with a mass-based worth function is coherent, the core question remains substantive, and the anchor survives arbitrary multiplicity. I cannot justify the universal claim that no worthwhile mirror exists.
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.