GRAPHS AND COOPERATION IN GAMES

GRAPHS AND COOPERATION IN GAMES

September 1976 | Roger B. Myerson
This paper introduces a graph-theoretic approach to analyze cooperation structures in games. Roger B. Myerson proposes a method to make a game's cooperation structure depend endogenously on players' choices. He defines fair allocation rules based on an equity criterion, where players should gain equally from cooperation. These rules are proven to be unique, closely related to the Shapley value, and stable for a wide class of games. The concepts are extended to games in "graph function" form, a new generalization of the characteristic function form. The paper discusses the concept of a cooperation graph, which allows for a richer description of cooperation structures than the traditional coalition concept. It explores how cooperation structures can be endogenously determined by players' choices, leading to stable allocation rules. The paper also introduces the idea of fair allocation rules, which ensure that players gain equally from cooperation. These rules are shown to be unique and closely related to the Shapley value. The paper further extends these ideas to games in graph function form, where the cooperation structure is represented by a graph. It proves that for any game in graph function form, there is a unique fair allocation rule that satisfies both efficiency and equity conditions. The paper concludes by showing that the Shapley value is a special case of this fair allocation rule when the cooperation structure is the complete graph. The results demonstrate the importance of graph-theoretic approaches in analyzing cooperation structures in games.This paper introduces a graph-theoretic approach to analyze cooperation structures in games. Roger B. Myerson proposes a method to make a game's cooperation structure depend endogenously on players' choices. He defines fair allocation rules based on an equity criterion, where players should gain equally from cooperation. These rules are proven to be unique, closely related to the Shapley value, and stable for a wide class of games. The concepts are extended to games in "graph function" form, a new generalization of the characteristic function form. The paper discusses the concept of a cooperation graph, which allows for a richer description of cooperation structures than the traditional coalition concept. It explores how cooperation structures can be endogenously determined by players' choices, leading to stable allocation rules. The paper also introduces the idea of fair allocation rules, which ensure that players gain equally from cooperation. These rules are shown to be unique and closely related to the Shapley value. The paper further extends these ideas to games in graph function form, where the cooperation structure is represented by a graph. It proves that for any game in graph function form, there is a unique fair allocation rule that satisfies both efficiency and equity conditions. The paper concludes by showing that the Shapley value is a special case of this fair allocation rule when the cooperation structure is the complete graph. The results demonstrate the importance of graph-theoretic approaches in analyzing cooperation structures in games.
Reach us at info@study.space