| paper | d4-conf-ijcai-2009-0180 |
| 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 many-one reductions · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3.3
statement extracted from the paper’s text layer
Given rational type masses \(\mu_t\), a symmetric rational interaction matrix \(W\), and a per-capita imputation \(x_t\), where \(v(q)=\frac12\sum_{t,u}W_{tu}q_tq_u\) and \(\sum_t\mu_tx_t=v(\mu)\), decide whether the imputation belongs to the type-mass bargaining set. An objection by type \(a\) against type \(b\) chooses \(q\in[0,\mu]\) with \(q_a>0\) and \(q_b<\mu_b\), and per-capita rates \(y_t>x_t\) for included mass, summing to \(v(q)\). A counterobjection chooses \(r\) with \(r_b>0\) and \(r_a<\mu_a\), specifies feasible overlap masses \(h_t\), and allocates exactly \(v(r)\) while meeting the original objection’s lower bounds on overlap and the imputation’s lower bounds outside it. The decision is whether every such objection has a feasible counterobjection; complexity is measured in \(\tau\) and the binary input length \(L\).
An atomless population has types \(t\in T\), masses \(\mu_t\), and symmetric pairwise interaction rates \(W_{tu}\), giving coalition mass \(q\) worth \(v(q)=\frac12\sum_{t,u}W_{tu}q_tq_u\). The decision variables are objection and counterobjection masses, overlap masses, and per-capita payoff rates; the objective is bargaining-set membership for an input imputation \(x\).
The mirror covers Theorem 3.3’s \(\Pi_2^P\)-hardness question for bargaining-set membership, specialized to type-homogeneous pairwise worths. It leaves Theorems 3.1–3.2, the compact-game membership results, and the bounded-treewidth kernel result aside.
The strongest mirror I see is for bargaining-set membership in a large coalition with repeated interaction roles. Imagine a large worker or producer consortium: there are many people in each role, and a person’s role completely determines their pairwise contribution rates with every other role. The number of people \(n\) can be enormous while the number of roles \(\tau\) stays much smaller.
Let the atomless population be partitioned into types \(t\in T\), with rational masses \(\mu_t\) summing to \(1\). A type specifies the person’s full interaction profile. A rational symmetric matrix \(W\) gives the worth rate between types. If a coalition contains mass \(q_t\) of each type, its worth is
\[ v(q)=\frac12\sum_{t,u\in T}W_{tu}q_tq_u. \]
This is the dense, type-homogeneous limit of a graph game: pairwise synergies are scaled so the consortium’s total worth remains finite as its population grows. The allocation under review is a per-capita payoff vector \(x\), with \(x_t\ge 0\) and \(\sum_t\mu_tx_t=v(\mu)\).
My anchor is Theorem 3.3, proved in this paper. It says that, given a graph game \(G\) and an imputation \(x\), deciding whether \(x\) belongs to the bargaining set \(B(G)\) is \(\Pi_2^P\)-hard. The reduction is from validity of quantified Boolean formulas of the form \((\forall\alpha)(\exists\beta)\phi(\alpha,\beta)\): objections encode assignments to the universal variables, and counterobjections encode satisfying extensions. The theorem is a hardness result for membership in the bargaining set, not an algorithm or a completeness claim.
The corresponding continuous question is Type-Mass Bargaining-Set Membership:
\[ \sum_{t:q_t>0}q_ty_t=v(q), \qquad y_t>x_t\quad\text{for every }t\text{ with }q_t>0. \]
\[
\max(0,q_t+r_t-\mu_t)\le h_t\le\min(q_t,r_t).
\]
It must distribute exactly \(v(r)\) across the overlap and the part outside the original objection, giving at least \(y_t\) on the overlap and at least \(x_t\) outside it.
This is a type-mass version of the paper’s actual objection/counterobjection question. It preserves the pairwise surplus logic and makes fractional coalition size native to the model. It does co-modify the solution concept: coalitions and challenges are described by type masses and per-capita rates, rather than named individuals and individual payoff vectors. That is the change the continuum makes necessary here.
I would expect this problem to be continuum-specifically hard (Class C), though that is a research hypothesis, not a result. The paper’s \(\Pi_2^P\)-hardness does not automatically transfer: its reduction relies on discrete coalitions, while the mass vectors above can be fractional. But membership still has a universal-versus-existential structure over real mass, overlap, and transfer variables, with a quadratic worth function. The central question is whether the reduction can force endpoint masses, preserving the discrete assignment choices, or whether fractional witnesses change the complexity. Fixed-\(\tau\) algorithms and the complexity as \(\tau\) grows are natural follow-ups.
The paper’s other results are outside this mirror: I am not proposing continuous kernel or nucleolus membership, or claiming to continuize all compact coalitional games. The weakest point is the type-mass objection rule. Some game theorists may reject it as a new collective bargaining concept rather than the bargaining set they study. The case for it is that it retains the paper’s defining computational question—whether every objection can be countered—while modelling the population itself as a distribution over repeated, fully specified interaction types.
Theorem 3.3 is the right anchor to challenge because the bargaining set is built around individual challengers: player \(i\) objects to player \(j\) through a coalition containing \(i\) and excluding \(j\). In an atomless population, including or excluding one named person changes neither the coalition’s mass nor its worth. If individual payoffs remain meaningful, changing the payoff of a zero-mass person costs nothing in the aggregate, so the objection and counterobjection conditions lose their intended force.
The proposed Type-Mass version repairs that problem by requiring positive mass of type \(a\) in the objection and leaving some type-\(b\) mass out. But that repair changes the strategic unit. It asks whether a positive bloc of one type can mount a challenge against another type, with uniform per-capita rates and fractional coalitions. That is a coherent bargaining question, but it is no longer obviously the paper’s question about one player’s objection to another. The difference is substantive: individual identity and the pairwise nature of the objection are what make membership in the bargaining set the object studied by Theorem 3.3.
The strongest alternative would keep named challengers as atoms while making the rest of the population continuous. In the natural dense graph limit, however, an individual’s contribution to total worth vanishes: with pair weights scaled to keep aggregate worth finite, a focal player’s interactions with the population contribute vanishing mass. Scaling those interactions to preserve the focal player’s influence makes the bulk worth grow with population size. A hybrid model can be specified, but its strategic content then sits in the retained finite agents; it is not a clean continuous-population mirror of the paper’s membership problem.
This is a real objection to the anchor, but it does not close the case. The type-mass game has a plausible repeated-role interpretation, a well-defined computational question, and preserves the objection/counterobjection structure at the level of positive-mass groups. If the authors regard bargaining between such blocs as their problem, the mirror survives. My negative case therefore rests on a genuine risk of changing the solution concept, not on a reason that the resulting question is computationally uninteresting. I cannot honestly establish the universal claim that no worthwhile continuous 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.