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

• 作者: 庄尔覃 谭志斌 白云飞 曹志刚
• 来源期刊: 中国科学（数学）
• 关键词: 合作博弈 最小支撑树博弈 核 Bird配置
• 年，卷（期）: 2020,（9）
• 所属期刊栏目: 论文
• 页码范围: 1405-1416
• 页数: 12页
• 语种: 中文
• DOI: 10.1360/SSM-2020-0060

摘要

最小支撑树博弈是合作博弈中的经典模型,自1973年被Claus和Kleitman提出后持续得到学术界关注.最小支撑树博弈不仅跟图论和组合优化中的最小支撑树问题一脉相承,还在水网、电网和公路铁路网建设中的成本分摊问题中有重要应用.Bird配置因其简洁性和直观性持续受到大量关注,是最小支撑树博弈最著名的求解方案.本文基于Edmonds对最小支撑树问题的线性规划表示,利用对偶定理给出Bird配置一种新的等价公式.本文还研究了最小支撑树博弈的一种推广,即点加权的最小支撑树博弈,并证明了Bird配置的一个变形依然在这个推广博弈的核中.