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.

An induced subgraph game extended by one self-loop weight ${\ell }_i$ per player. Each loop is counted once, so $v(\{i\})={\ell }_i$ andSingleton and pair coalition values determine all weights; larger coalition values must then agree with their sums. Signed weights are allowed. For example, two loops of weight $1$ joined by an edge of weight $-1$ represent the simple cooperative game in which any coalition meeting those two players wins.

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]

No. Two positive self-loops and one negative edge give a simple cooperative game with an empty core of a cooperative game. Give players $1,2$ loop weights ${\ell }_1={\ell }_2=1$, put $w_{12}=-1$, and give every other loop and edge weight zero. For a coalition $S$,Thus a coalition wins exactly when it contains player $1$ or player $2$. This is monotone, has values in $\{0,1\}$, and satisfies $v(\varnothing )=0,v(N)=1$. Extra players for any $n\ge 3$ do not alter any coalition value.

The core singleton inequalities would require $x_1\ge 1$, $x_2\ge 1$ and $x_i\ge 0$ for every other player, while efficiency requires ${\sum }_i{x}_i=1$. These requirements are inconsistent. Equivalently, the two disjoint winning singleton coalitions leave no veto player. Signed weights are essential to this particular representation and are permitted in the induced subgraph game model.

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]

In an induced subgraph game, players are graph vertices and a coalition receives the sum of the weights of graph edges whose two endpoints lie in it. Therefore each two-player coalition determines the corresponding edge weight. For $G_1$ these weights would have to be $2,6,3$, making the grand coalition worth $2+6+3=11$, whereas its actual value is $15$. No other edge weights can repair that discrepancy without changing a two-player coalition's value. Even a convention allowing vertex weights would not help: its singleton values force all such weights to zero.

For $G_2$, the stated weighted graph triangle has grand coalition value $2+3+3=8$ and reproduces all three pair values. Empty and singleton coalitions contain no graph edges, so their values are zero. This verifies all eight coalitions and supplies the complete representation.

To compute the Shapley value, reveal players in a uniformly random permutation. An edge's weight contributes to an endpoint's marginal contribution precisely when the other endpoint appeared earlier. Each endpoint is later with probability $1/2$, independently of where the third player appears. Linearity of the expected value therefore splits each edge weight equally between its two endpoints:The values sum to $8=v_2(N)$, as required by the Shapley value's efficiency property. This is the general Shapley value of an induced subgraph game formula, not an assumption that all three players are symmetric: player $3$ has a different incident-weight total.

A computer scientist working on game theory, algorithms and computational complexity theory. Co-author with Christos Papadimitriou of On the Complexity of Cooperative Solution Concepts by Xiaotie Deng and Christos Papadimitriou, which studies induced subgraph games.

Primary profile: Peking University profile identifying Xiaotie Deng and his research interests.