| paper | Learning Cooperative Games |
| authors | M. Balcan, Ariel D. Procaccia, Yair Zick |
| venue | IJCAI 2015 |
| filed under | coalition · wvg |
| judged by | gpt-5.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 in the proper-learning sense: a learner with the requested polynomial time and sample bounds would imply \(\mathrm{NP}=\mathrm{RP}\). Polynomial sample complexity alone is possible. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4.2
statement extracted from the paper’s text layer
Given a known directed topology with one edge-agent location \(e_t\) per type \(t\in T\), rational population masses \(\mu_t\) with \(\sum_t\mu_t=1\), and unknown per-agent capacities \(a_t\), draw i.i.d. mass-coalition samples \(z_j\in\prod_{t\in T}[0,\mu_t]\) from an unknown \(\mathcal D\), labeled by \(F_a(z_j)=\operatorname{maxflow}(G(a\odot z),s,\mathrm{sink})\). Output a proper \(\widehat a\) with time and sample complexity polynomial in \(\tau=|T|\), input length, \(1/\varepsilon\), and \(\log(1/\delta)\), such that with probability at least \(1-\delta\), \(\Pr_{z\sim\mathcal D}[F_{\widehat a}(z)\ne F_a(z)]\le\varepsilon\).
A high-multiplicity network-flow PAC-learning model with homogeneous edge-agent types, available masses \(\mu_t\), participating masses \(z_t\), aggregate capacities \(a_tz_t\), and the objective of learning the unknown capacity vector \(a\) under exact PAC loss.
The strongest remaining objection is that Theorem 4.2 hardness can be supported entirely on Boolean corner coalitions, so its computational difficulty may add little genuinely fractional content and interior sampling requires a stipulated coalition distribution.
fatal: False
The mirrors cover Theorems \(4.2\) and \(4.7\); they leave PAC stability, path-restricted learning, threshold-task games, and the additional classes unclaimed.
The strongest positive case is that this paper supports two genuine population mirrors: a hardness-preserving one for network-flow games, and a tractable one for induced-subgraph games. The first is my lead because it is anchored in a hardness theorem.
The common continuization is this. There is a finite type set \(T\), with population masses \(\mu_t\) summing to \(1\). A coalition is no longer a subset of named players but a mass vector \(z\), where \(0\le z_t\le\mu_t\). Agents of one type are indistinguishable for the game: they have the same network role, capacity technology, or interaction parameters. The input distribution remains the paper’s PAC sampling distribution, now over coalition-mass vectors rather than subsets.
My lead problem is High-Multiplicity Network-Flow PAC Learning. Consider a network whose edge agents occur in large homogeneous classes. Type \(t\) specifies an edge location and common per-capita capacity \(a_t\); there are \(M_t\) interchangeable agents of that type, with \(M=\sum_tM_t\) and \(M\gg\tau=|T|\). The unknown capacities \(a_t\) define the target game. If coalition mass \(z_t\) activates type \(t\), its aggregate edge capacity is \(a_tz_t\), and the coalition value is
\[ F_a(z)=\operatorname{maxflow}(G(a,z),s,t). \]
The precise PAC problem is: given the known topology, rational type masses \(\mu\), accuracy and confidence parameters \(\varepsilon,\delta\), and samples \((z_j,F_a(z_j))\) drawn independently from an unknown distribution \(\mathcal D\) over \(\prod_t[0,\mu_t]\), output a proper network-flow hypothesis \(F_{\widehat a}\) such that, with probability at least \(1-\delta\) over the samples,
\[ \Pr_{z\sim\mathcal D}\!\left[F_{\widehat a}(z)\ne F_a(z)\right]\le\varepsilon. \]
The decision variable is the learned capacity vector \(\widehat a\); the objective is exact PAC prediction of future coalition values. The running time and sample complexity should be polynomial in \(\tau\), the input bit length, \(1/\varepsilon\), and \(\log(1/\delta)\), rather than in the potentially enormous number \(M\) of agents.
This is a natural mirror of the paper’s Theorem 4.2, proved in the paper: “Network flow functions are not efficiently learnable unless \(\NP=\RP\).” The theorem concerns learning an unknown network-flow characteristic function from sampled coalitions and their flow values under unrestricted coalition distributions. Its proof reduces learning \(k\)-min-sum functions, for \(k\ge3\), to network-flow learning by representing the \(k\) linear forms as serial network layers.
I expect the continuous problem to be Class B: hardness transfers. Given any discrete network-flow instance, make every original edge a type and give it \(M\) interchangeable copies. Restrict \(\mathcal D\) to the corner coalitions \(z_t\in\{0,\mu_t\}\), meaning that an entire type is either activated or absent. The resulting flow value is just a scaled copy of the original discrete value. Therefore a polynomial-time learner for the continuous problem would yield a polynomial-time learner for the discrete problem. The large multiplicity is genuine—the population can be made arbitrarily larger than the number of types—but the hardness lives in the number of edge types and network layers, not in the number of repeated agents.
This is not merely a restatement of the paper. The paper’s society is finite, and its distribution is over \(2^N\); it never studies a mass-valued coalition space or a high-multiplicity network. The continuous question also asks what happens away from the Boolean corners, where only fractions of a link class participate. It generates useful follow-ups: whether approximate-value learning becomes easier; whether fixed \(\tau\), bounded depth, or path-supported distributions yield efficient algorithms; and whether genuinely fractional support permits a continuum-specific obstruction.
A second, independent mirror is Continuous Induced-Subgraph PAC Learning. Consider a population of network vertices divided into \(\tau\) homogeneous types. Type \(a\) contains many agents with the same interaction weight with every type \(b\). For a coalition mass vector \(z\), define its induced-subgraph value by integrating pairwise interactions over the selected mass:
\[ V_\Theta(z) = \sum_{a<b}\theta_{ab}z_az_b + \sum_a \theta_{aa}\frac{z_a^2}{2}. \]
The factor \(1/2\) is the atomless analogue of counting unordered pairs within one type. If two agents differ in any interaction parameter, they are different types, so the model respects the programme’s complete-type requirement.
The continuous problem is: given samples \((z_j,V_\Theta(z_j))\) from an unknown distribution over coalition-mass vectors, output a proper matrix \(\widehat\Theta\) satisfying
\[ \Pr_{z\sim\mathcal D} \!\left[V_{\widehat\Theta}(z)\ne V_\Theta(z)\right] \le\varepsilon \]
with confidence \(1-\delta\). The underlying question is still learning an induced-subgraph cooperative game, not learning a quadratic encoding.
This mirrors Theorem 4.7, proved in the paper: “The class of induced subgraph games is efficiently PAC learnable.” The paper’s proof writes the value of a coalition as \( \vec e_S^{\,T}W\vec e_S \), observes that the unknown edge weights are \(O(n^2)\) linear parameters, and finds a consistent weighted adjacency matrix by solving a linear system. In the continuous mirror, the feature vector consists of the \(O(\tau^2)\) monomials \(z_az_b\). Consistent learning is therefore linear feasibility in \(O(\tau^2)\) variables, with polynomial sample complexity governed by the corresponding pseudo-dimension. I expect this mirror to be Class A.
The two mirrors cover only Theorems 4.2 and 4.7; I would not claim that every result in the paper continuizes naturally. Threshold-task games and MC-nets would require additional decisions about which attributes are shared by a mass type, while Theorem 3.1 concerns a payoff construction whose continuous analogue would need a separate definition of divisible coalition participation.
The weakest point is the lead network-flow mirror: its hardness proof can be supported entirely on all-or-nothing mass vectors, so an opponent can fairly say that the transfer is driven by replicated discrete types rather than by fractional population behaviour. The induced-subgraph mirror is more genuinely continuous, but it imposes homogeneous pairwise interactions and an atomless within-type convention. Those are real modelling choices. Still, both are legitimate high-multiplicity regimes: the first asks whether network-flow PAC learning remains hard when agents are mass-repeated, and the second asks whether pairwise cooperative values can be learned from aggregate population coalitions. That is enough for a credible continuous mirror, even though the expected classifications are respectively hardness transfer and tractability rather than continuum-specific novelty.
The strongest negative case is that the proposed mirrors do not really continuize the object driving the paper. They replace a finite set query \(S\subseteq N\) by a fractional query \(z\), while the “society” \(\mu\) is largely inert: it only bounds the coordinates of \(z\). The stochastic object remains an externally chosen query distribution \(\mathcal D\), not a distribution of agent types or a population-level social process.
This matters especially for Theorem 4.2. With \(M\) identical copies of each edge type, the proposed game is simply
\[ F_a(z)=\operatorname{maxflow}(G(a,z),s,t), \]
where the capacity of type \(t\) is \(a_tz_t\). At the Boolean corners \(z_t\in\{0,\mu_t\}\), this is just the original discrete network-flow learner with rescaled values. That is a valid hardness transfer, but it is a disguised discrete instance: the multiplicity contributes no state and the difficulty remains entirely in the \(\tau\) edge types and the network.
The stronger interior version does not rescue the population interpretation. Fractionally activating an edge type is naturally a divisible-capacity or resource-allocation model, not a population model. It can certainly be made meaningful, but then the continuation is happening in the resource/capacity variable. If instead coalitions are sampled by independently selecting members of a large homogeneous population, normalized mass vectors concentrate around their expectations as \(M\) grows, so the sampling distribution becomes nearly degenerate. To obtain a genuinely rich distribution over interior \(z\), one must stipulate an additional, essentially arbitrary coalition-generation process. Thus the network-flow anchor gives either a corner encoding of the discrete problem or a resource-continuation with no canonical population semantics.
The induced-subgraph anchor is harder to defeat. A better version than the one stated is entirely natural: take a blow-up graph in which type \(a\) contains many interchangeable vertices, every \(a\)-\(b\) pair has common weight \(\theta_{ab}\), and normalize the induced value by the square of the population size. If \(z_a\) is the selected mass of type \(a\), the finite model converges to
\[ V_\Theta(z) = \sum_{a<b}\theta_{ab}z_az_b + \sum_a \frac{\theta_{aa}}{2}z_a^2. \]
This respects the complete-type requirement and is a genuine high-multiplicity limit, not merely a relabelling of named vertices. Learning it from fractional coalition samples is linear learning in the features \(z_az_b\), with \(O(\tau^2)\) parameters.
The only negative point available here is that the continuous result is almost completely inherited from the paper’s existing quadratic-form proof: replacing indicator vectors by mass vectors turns \(e_S^{\mathsf T}We_S\) into a quadratic polynomial, and the same linear-system argument applies. There is no new separation problem, continuous optimization phenomenon, or population-level decision problem. But that is an argument about marginal payoff, not validity. The programme explicitly allows simple Class A mirrors, so it cannot be treated as a genuine obstruction.
Consequently, the universal negative claim cannot honestly be sustained. The network-flow mirror is weak as a population continuization because its mass variable is either a disguised Boolean query or a divisible resource. But the induced-subgraph mirror survives: it is a sensible high-multiplicity regime with a legitimate continuous population limit. The negative case is therefore, at best, an argument that this paper offers little continuum-specific novelty—not that it has no worthwhile continuous mirror 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.