| paper | d4-conf-ijcai-2003-0171 |
| 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→P discrete result → its continuous mirror
Answer: The problem is in \(\mathrm{P}\): every valid instance has a nonempty core, and a rational core vector is computable in time polynomial in \(m,\tau,L\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t\geq 0\) summing to \(1\), and finitely many repeatable recipes \((a^j,w_j)\), define \(v(x)=\max\{\sum_j w_j\lambda_j:\sum_j a^j_t\lambda_j\leq x_t\ \forall t,\ \lambda_j\geq 0\}\) for each coalition composition \(0\leq x\leq\mu\). Does there exist a per-unit payoff vector \(p\geq 0\) with \(p\cdot\mu\leq v(\mu)\) and \(p\cdot x\geq v(x)\) for every \(x\leq\mu\)?
A society is a distribution \(\mu\) over complete worker types. Recipes \(j\), with type requirements \(a^j\) and transferable value \(w_j\), can be repeated at scale \(\lambda_j\); their maximum feasible value for composition \(x\) is \(v(x)\). The decision witness is a per-unit payoff vector \(p\); core nonemptiness asks whether it is feasible for the grand coalition and gives every coalition at least its value. The recipe-value problems are linear programs.
The mirror covers Theorem 2 for transferable-utility core nonemptiness under repeatable team recipes; it does not cover Theorems 1, 3, 4, or 5, or the paper’s other game variants.
My lead is Continuous Type-Core Nonemptiness for repeatable coalition synergies, mirroring Theorem 2. That theorem says that deciding whether a superadditive characteristic-form game with transferable utility has a nonempty core is NP-complete in the paper’s basis representation. The authors prove it here by reducing from Exact-Cover-by-3-Sets: they give each listed triple worth \(3\), and give \(S\cup\{x\}\), \(S\cup\{y\}\), and \(\{x,y\}\) worth \(6m\). An exact cover supports a core allocation; without one, the grand coalition cannot reach the value needed to avoid a blocking coalition.
A plausible setting is a large employer whose workforce has many employees but relatively few complete types, such as role, seniority, and skill profiles. A type’s members are interchangeable in everything the model uses. Mass \(\mu_t\) is the fraction of the workforce of type \(t\); a coalition may include any amount of each type. The employer’s collaborative opportunities are a finite list of repeatable team recipes: recipe \(j\) uses type-mass vector \(a^j\) and creates transferable value \(w_j\). Repeating a recipe at fractional scale is natural when the population is large and the same staffing pattern can be realized by many interchangeable employees.
Here is the problem I would hand to a prover. The input is a finite type set \(T\), binary-rational masses \(\mu_t\geq 0\) summing to \(1\), and finitely many recipes \((a^j,w_j)\), with nonnegative rational entries and each recipe consuming some positive mass. For any coalition composition \(x\leq\mu\), define its worth by
\[ v(x)=\max\left\{\sum_j w_j\lambda_j: \sum_j a^j_t\lambda_j\leq x_t\ \text{for every }t,\quad \lambda_j\geq0\right\}. \]
Continuous Type-Core Nonemptiness asks whether there is a per-person utility \(p_t\geq0\) for each type such that the grand-coalition allocation is feasible, \(p\cdot\mu\leq v(\mu)\), and no coalition can block it, \(p\cdot x\geq v(x)\) for every \(x\leq\mu\). The solution is the vector \(p\); the inequalities express the same core stability question as in Theorem 2. If a coalition’s worth exceeds its current total utility, transferable utility lets it give every member of that coalition a strict improvement.
I expect this mirror to be tractable. The grand coalition’s worth is a fractional packing LP, whose dual is
\[ \min \mu\cdot p \quad\text{subject to}\quad \sum_t a^j_t p_t\geq w_j\ \text{for every recipe }j,\qquad p\geq0. \]
A dual optimum supports the grand coalition and bounds the worth of every coalition composition, so it gives a core allocation. The LP has size polynomial in the number of types, recipes, and input bit length. This makes the connection to Theorem 2 concrete: the discrete reduction relies on packing triples integrally, while the population mirror allows mass to split across recipes and replaces that packing with an LP.
I consider this a plausible version of the authors’ problem because it retains their central question—whether there is a stable transferable-utility allocation against every coalition—and their concise basis-of-synergies representation. It also fits their employee compensation example. In a finite high-multiplicity instance, recipe placements are integral; in the continuous mirror, they are fractional. The mirror is specifically about the population becoming continuous; money remains transferable utility, not a new fractional outcome space.
This case covers Theorem 2 only. It does not claim to mirror the non-transferable-utility result or Theorem 5’s hybrid model. The main weakness is that scalable team recipes impose constant returns: the paper permits one-off or capacity-limited synergies, and those need not have the LP duality above. Also, Theorem 2’s reduction itself has essentially one distinct player role per element, so it does not demonstrate hardness in a regime where the number of types is small relative to the population. The natural next questions are whether capacity-limited recipes or hybrid non-transferable blocking restore hardness, and how the answer depends on the number of types.
The strongest objection is that Theorem 2’s hard instances do not have the repeated structure the proposed mirror needs. In the reduction, each \(S_i\) is a particular coalition of named players, and its value can be used only once in a disjoint partition. If those players are merged into one or a few types, the recipes stop referring to particular triples: they become repeatable fractional production activities, and the exact-cover structure is lost. If the types retain enough information to distinguish the players and their coalition relationships, the number of types grows with the instance, leaving no high-multiplicity regime.
Adding capacities to the recipes does not give a canonical translation. A fixed number of uses becomes negligible after normalizing by population size; capacity that scales with population turns the synergies into production technologies of the kind in the proposed LP model. Preserving more complicated identity-dependent interactions would require richer input that carries the original combinatorics. This is a serious objection to calling the repeatable-recipe model a mirror of the *hardness construction* in Theorem 2. It changes the basis of one-off coalitional synergies into scalable technology.
That does not, however, defeat the better version of the anchor. The paper asks about core nonemptiness for characteristic-form games, and it explicitly motivates the question with employees and company coalitions. A large workforce with recurring roles and scalable team opportunities is plausible, and core nonemptiness remains the authors’ central computational question. Under the programme’s rules, the fact that this specialization admits an LP solution is not a reason to reject it: a tractable mirror of a hard discrete problem is potentially the point.
So the negative case is weak at its most important step. It can show that the proposed model does not preserve Theorem 2’s exact-cover instances, but it cannot honestly establish that a type-based employee production game is outside the authors’ problem or not worth studying. I do not have a sound argument that no worthwhile continuous mirror exists in any scenario.
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.