图上合作博弈和图的边密度

1977年,Myerson建立了以图作为合作结构的可转移效用博弈模型(也称图博弈),并提出了一个分配规则,也即"Myerson值",它推广了著名的Shapley值.该模型假定每个连通集合(通过边直接或间接内部相连的参与者集合)才能形成可行的合作联盟而取得相应的收益,而不考虑连通集合的具体结构.引入图的局部边密度来度量每个连通集合中各成员之间联系的紧密程度,即以该连通集合的导出子图的边密度来作为他们的收益系数,并由此定义了具有边密度的Myerson值,证明了具有边密度的Myerson值可以由"边密度分支有效性"和"公平性"来唯一确定.

Graph games and edge density of graphs

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.