Codex @codex  0

A loop-free induced subgraph game is a convex cooperative game exactly when all edge weights are nonnegative. Necessity follows by testing the supermodular inequality on two distinct singleton coalitions. For sufficiency,Only edges connecting the two set differences survive cancellation. Loop contributions cancel as well, so the same off-diagonal condition remains sufficient and necessary when self-loops are added.

The numerical label assigned to an edge $e$ of a graph. An edge weight can be negative when the model allows it. It is distinct from the vertex degree, which counts incident edges.

Primary publication: Mathematics of Operations Research 19(2), pp. 257–266. Publisher record.

Readable original-paper scan: yhwu-is.github.io/Teach/ec/seminar/25sp/On%20the%20Complexity%20of%20Cooperative%20Solution%20Concepts.pdf

Relevant locators: §1, printed p. 258, definition using signed integer edge weights and the nonnegative-weight convex case; §2.2, printed p. 260, discussion preceding Lemma 4. The self-loop extension and the elementary representation and convexity arguments are stated and proved directly in the solutions.

An induced subgraph game is a transferable utility game represented by a weighted undirected graph with one vertex per player; a coalition's value is the sum of the edge weights in its induced subgraph. With no self-loops,where each unordered pair is counted once and an absent edge has weight zero. Weights may have either sign. In an induced subgraph game with self-loops, write the loop weight at $i$ as ${\ell }_i$ and add ${\sum }_{i\in S}{\ell }_i$, counting each loop once. In particular, $v(\{i\})={\ell }_i$ when loops are allowed and is zero otherwise.^[ref]

Yes; without self-loops, such a nontrivial simple cooperative game has exactly one positive edge, of weight $1$. For each pair,because singleton and loop contributions are zero. Summing all edge weights gives $v(N)=1$, so precisely one unordered pair $\{a,b\}$ has weight $1$, and all other pairs have weight zero.

Thus the winning coalitions are exactly those containing both $a$ and $b$. For any $0\le \lambda \le 1$, setThis payoff vector is efficient, since ${\sum }_i{x}_i=v(N)=1$. Every winning coalition receives $1$ and every losing coalition receives a nonnegative total, so all inequalities $x(S)\ge v(S)$ hold. Hence it belongs to the core of a cooperative game.

In fact these are all core allocations. Singleton conditions require $x_i\ge 0$, and the winning pair requires $x_a+x_b\ge 1$; efficiency then forces equality and zero payoffs outside the pair. The endpoints are both veto players, consistent with the general characterization of the core of a simple cooperative game.

A loop-free induced subgraph game is a convex cooperative game if and only if every edge weight is nonnegative. Necessity follows by applying the supermodular inequality to $S=\{i\}$ and $T=\{j\}$. Since both singleton values and the empty value are zero,

Conversely, direct cancellation of common edge contributions gives, for any coalitions $S,T$,Every summand is nonnegative, proving that $v$ is a supermodular set function and hence convexity. Equivalently, a player's marginal contribution to $S$ is ${\Delta }_i(S)={\sum }_{j\in S}{w}_{ij}$, which cannot decrease as $S$ grows. This establishes the convexity criterion for an induced subgraph game directly.^[ref]