Operations Research Transactions

Previous Articles     Next Articles

Graph games and edge density of graphs

LI LiSHAN Erfang1,*   

  1. 1. School of Management, Shanghai University, Shanghai 200444, China
  • Received:2017-11-20 Online:2018-12-15 Published:2018-12-15

Abstract:

A cooperative game with transferable utility, shortly TU game, is a pair consisting of a finite set of players and a characteristic function assigning a worth to each coalition of players. Myerson (1977) introduced TU games with restricted cooperative structure represented by an undirected graph, or simply graph games, and presented an allocation rule, called the Myerson value, which  extended the well-known Shapley value. Under the assumption that only coalitions of connected players can cooperate and realize  gains from cooperation. However, the structures of  connected coalitions in the model are ignored. To measure the degree of closeness among the members of each connected set, we introduce the (local) edge density that is regarded as the income coefficient of the members of the connected set and define the Myerson value with  edge density. We show the Myerson value with edge density can be uniquely determined by component efficiency with the edge density and fairness.

Key words: graph, graph game, edge density, Myerson value, component efficiency, fairness