| paper | Cooperative games with overlapping coalitions: Charting the tractability frontier |
| authors | Yair Zick, G. Chalkiadakis, Edith Elkind, E. Markakis |
| venue | AI 2019 |
| 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→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: the problem belongs to \(\mathrm{P}\), with running time \((m+\tau+L+1)^{O(1)}\) bit operations. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 3.4
statement extracted from the paper’s text layer
Given a finite type set \(\Theta\), rational masses \(\mu_\theta\) summing to \(1\), per-agent endowments \(w_\theta\), aggregate resource caps \(b_\theta\le\mu_\theta w_\theta\), explicitly listed finite contribution levels and singleton/pair values, and a threshold \(V\), choose nonnegative masses \(z_{\theta,r}\) and \(x_e^{r,s}\) of singleton and pair coalitions to maximize \(\sum_{\theta,r}v_\theta(r)z_{\theta,r}+\sum_{e,r,s}v_e(r,s)x_e^{r,s}\), subject for every type \(\theta\) to \(\sum_r z_{\theta,r}+\sum_{e\ni\theta,r,s}x_e^{r,s}\le\mu_\theta\) and \(\sum_r rz_{\theta,r}+\sum_{e\ni\theta,r,s}\rho_{\theta e}(r,s)x_e^{r,s}\le b_\theta\), where \(\rho_{\theta e}\) is that type’s contribution in pair \(e\); decide whether the optimum is at least \(V\), with coalitions of support greater than \(2\) having value zero.
A type-mass \(2\)-OCF market with rational masses \(\mu\), per-agent resource endowments, aggregate resource caps, explicitly listed contribution levels, singleton and pair values, nonnegative coalition-mass variables, and a linear total-value objective.
The mirror does not provide a polynomial two-way complexity equivalence with the discrete instances: expanding rational masses may require a population exponential in the encoding length, while the growing type-interaction table retains the X3C combinatorics.
fatal: False
It covers only Proposition 3.4’s optimal-value hardness result; it leaves the paper’s dynamic-programming, arbitration, deviation, treewidth, and Linear Bottleneck Game stability results unmirrored.
The strongest positive case is a high-multiplicity version of the paper’s optimal coalition-structure problem, anchored on Proposition 3.4.
Proposition 3.4, proved in this paper rather than cited, states that \(\optval\) is NP-complete even for \(2\)-OCF games with maximum agent weight \(\wmax=3\). The input is an OCF game \(\mathcal G\), a resource vector \(\vec c\), and a threshold \(V\); the question is whether the maximum value \(v^*(\vec c)\) achievable by a coalition structure of total weight \(\vec c\) is at least \(V\). The reduction is from X3C. There is a weight-one agent \(a_i\) for every ground element \(i\), and a weight-three agent \(a_S\) for every three-set \(S\). If \(i\in S\), a unit-unit coalition of \(a_i\) and \(a_S\) has value \(2\); a weight-three singleton coalition of \(a_S\) has value \(5\); every other partial coalition has value \(0\). Thus a set agent earns \(6\) if it serves all three elements of its set, but only \(5\) if it works alone. The threshold is \(5t+|A|/3\), and it is reached exactly when the X3C instance has an exact cover.
My lead mirror is Continuous Pairwise OCF Value. An instance contains:
A type is a complete capability and payoff profile: agents of the same type have the same resource endowment, singleton values, and pairwise values with every other type. A feasible solution is an aggregate coalition structure. Let \(z_{\theta,r}\) be the mass of singleton coalitions of type \(\theta\) using \(r\) units, and let \(x_{\theta\phi}^{r,s}\) be the mass of pair coalitions between types \(\theta\) and \(\phi\) using contributions \(r\) and \(s\). The resource constraints require that each type’s total allocated resource is at most \(b_\theta\). The objective is the total generated value, namely the corresponding linear sum of the \(z\)- and \(x\)-variables weighted by \(v_\theta(r)\) and \(v_{\theta\phi}(r,s)\). The question is whether the optimum is at least \(V\), and a solution is the aggregate allocation together with its value.
This is the same underlying question as \(\optval\): how profitably can agents divide their resources among overlapping coalitions? It is not a question about fractional outcomes replacing discrete outcomes. The continuous object is the population. Each infinitesimal agent has the same finite resource and capability profile as every other agent of its type; mass records how many such agents exist.
The X3C construction has a direct interpretation. Let \(q=|A|+t\), give every element type and set type mass \(1/q\), and retain the paper’s weights and values. Let \(x_{iS}\) be the mass of unit-unit coalitions between element type \(i\) and set type \(S\), and \(y_S\) the mass of set-type agents working alone. The relevant continuous problem is the LP
\( \sum_{S\ni i}x_{iS}\le 1/q \) for every element type \(i\),
\( \sum_{i\in S}x_{iS}+3y_S\le 3/q \) for every set type \(S\),
with objective \( 2\sum_{i,S:i\in S}x_{iS}+5\sum_S y_S\) \), and threshold \( V_\infty=(5t+|A|/3)/q\) \).
The variables are masses of coalitions, not fractional identities of named agents. For example, \(x_{iS}=1/(2q)\) means that half the agents of element type \(i\) are paired with half the resource capacity of set type \(S\). This is exactly what a high-multiplicity market of interchangeable suppliers and demand categories should permit. The LP has polynomially many variables and constraints, so this mirror is tractable in polynomial time in the number of types, contribution levels, and encoding length.
The regime is plausible. Imagine a large market with many interchangeable resource owners and many interchangeable suppliers, where a supplier type is characterized by the three customer categories it can serve, its capacity, and the value of completing a contract. There may be \(M\) agents of every role type, with \(M\) much larger than the number \(\tau=|\Theta|\) of role types. This is a genuine high-multiplicity regime: the agents are not named individuals with arbitrary prices, but repeated instances of standardized capability profiles. The paper’s own market-exchange motivation makes this interpretation natural.
The continuous result would be Class A. Proposition 3.4’s exact-cover obstruction depends on integral allocation among finitely many resource holders. In the mirror, the aggregate allocation is a finite LP. Some discrete exact-cover instances will admit fractional allocations reaching the threshold even when no integral exact cover exists; that is not a defect but the expected point at which population multiplicity dissolves the discrete obstruction.
There is also a two-way dictionary. A rational mass vector can be expanded into sufficiently many identical agents, so continuous solutions give high-multiplicity discrete allocations and rounding or additive-approximation guarantees. Conversely, any finite OCF instance embeds by assigning one type to each agent and mass \(1/n\). Thus the mirror does not claim that every discrete hardness result disappears. If the number of types grows with the population and carries all the combinatorics, hardness may remain. Its claim is narrower: the population-driven integrality in Proposition 3.4 disappears when many agents share finitely described types.
The main further questions are whether analogous LPs remain tractable for fixed \(k\)-OCF games, whether arbitration and core constraints admit a comparable type-mass formulation, and which additional restrictions—geographic indivisibility, type-specific indivisible bundles, or nonlocal reactions—restore hardness.
The weakest point is that the X3C reduction uses one distinct capability pattern for almost every element and set, so \(\tau\) still grows with the encoded instance. If “high multiplicity” were required to mean a fixed number of types, this would be a poor anchor. The defence is that the programme requires many agents relative to the number of types, not a constant type universe, and the LP remains polynomial even when \(\tau\) grows. I would therefore present this as a strong, qualified positive mirror of Proposition 3.4, covering the paper’s \(\optval\) result but not claiming to continuize its stability or arbitration results.
The strongest objection is that this does not really continuize Proposition 3.4’s source of complexity. In an arbitrary X3C instance, an element’s type is determined by the complete list of set-types with which it can interact, and a set’s type by its three incident element-types. Distinct incidence profiles therefore require distinct types. The proposed mirror has \(\tau=|A|+|\mathcal S|\) essentially because it has retained the entire finite hypergraph as its type space.
Replicating every type \(M\) times produces a large population, but it merely clones that finite hypergraph and permits fractional resource allocation over it. If \(\tau\) is fixed, the arbitrary X3C structure disappears and the problem is a fixed-dimensional packing LP. If \(\tau\) grows, all substantive combinatorics live in the type-interaction table; population mass is only a scaling and divisibility device. The result is therefore better described as fractional \(b\)-matching or resource packing on an explicitly supplied hypergraph than as a population-level analogue of the paper’s tractability frontier.
A stronger attempt to preserve the X3C structure would require each set-agent to be treated as an indivisible object that either completes its three links or does not. But that is precisely what the atomless model removes. Reintroducing it requires atomic agents, integer constraints, or nonconvex “all three links together” conditions. Those may be legitimate models, but they no longer give the clean continuous high-multiplicity relaxation proposed here.
The proponent’s two-way dictionary is also overstated. Assigning one type to each agent with mass \(1/n\) is a formal embedding, not a genuine high-multiplicity regime. Conversely, expanding a rational mass solution into individuals may require a population whose size is exponential in the encoding length, and exact threshold preservation is not automatic.
These points weaken the claim that the mirror captures the paper’s X3C hardness mechanism. They do not, however, defeat the mirror under ChoCo’s stated standard. The programme does not require a constant number of types, and a market with many interchangeable vendors of each standardized capability profile is plausible. Total profit depends only on aggregate resource use, not on individual identity, and fractional pairing is exactly what a continuum of interchangeable agents should permit. The resulting LP is a legitimate Class A high-multiplicity question, even if its answer is a fractional packing problem rather than an exact-cover problem.
So the honest negative case is weak. It can argue that this is a modest and somewhat generic mirror, and that the proponent should not present it as preserving Proposition 3.4’s combinatorial obstruction. It cannot support the universal claim that no worthwhile continuous mirror exists. On the programme’s rules, this anchor survives.
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.