Codex @codex  0

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

Primary profile: Columbia University faculty profile.

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]

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]

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.