最小支撑树博弈:重新审视Bird配置  

Minimum-cost spanning tree games: Bird rule revisited

作　　者：庄尔覃 谭志斌 白云飞 曹志刚 Ertan Zhuang;Zhibin Tan;Yunfei Bai;Zhigang Cao

机构地区：[1]北京交通大学经济管理学院,北京100044 [2]北京交通大学理学院,北京100044

出　　处：《中国科学：数学》2020年第9期1405-1416,共12页Scientia Sinica：Mathematica

基　　金：国家自然科学基金(批准号:71922003,71871009,11471326和71961137005)资助项目。

摘　　要：最小支撑树博弈是合作博弈中的经典模型,自1973年被Claus和Kleitman提出后持续得到学术界关注.最小支撑树博弈不仅跟图论和组合优化中的最小支撑树问题一脉相承,还在水网、电网和公路铁路网建设中的成本分摊问题中有重要应用. Bird配置因其简洁性和直观性持续受到大量关注,是最小支撑树博弈最著名的求解方案.本文基于Edmonds对最小支撑树问题的线性规划表示,利用对偶定理给出Bird配置一种新的等价公式.本文还研究了最小支撑树博弈的一种推广,即点加权的最小支撑树博弈,并证明了Bird配置的一个变形依然在这个推广博弈的核中.Minimum-cost spanning tree(MCST) game is a classical model in the theory of cooperative games.The MCST game has been drawing continuous attention since it was raised by Claus and Kleitman in 1973. The MCST game is closely related to the MCST problem, a fundamental model in graph theory and combinatorial optimization, and has been widely applied in cost allocations for constructions of water networks, power networks,road networks and railway networks, etc. Due to its simplicity and intuitiveness, the Bird rule is one of the most famous solutions in the MCST game and has been extensively studied in the literature. Based on the linear programming formulation of the MCST problem by Edmonds, we provide a new equivalent closed-form formula for the Bird rule. We also study a generalization of the MCST game with weighted nodes. We show that the core is nonempty in the generalized model, and in particular, a modified Bird rule is proved to be still applicable.

关 键 词：合作博弈 最小支撑树博弈 核 Bird配置 

分 类 号：O225[理学—运筹学与控制论]