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

作者：李理; 单而芳^*

来源：运筹学学报, 2018, 22(04): 99-107.

DOI：10.15960/j.cnki.issn.1007-6093.2018.04.009

• 图
• 图博弈
• 边密度
• Myerson值
• 分支有效性
• 公平性

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

• 单位
  上海大学