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

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

基于合作博弈论的电梯修建成本分摊博弈

老旧小区加装电梯是目前城镇化建设中的一个重要议题.问题的关键之一是如何在需求和收益高度异质的业主间分摊电梯安装成本.该文以合作博弈论为基础构建了电梯博弈模型,证明了电梯博弈为凸博弈,并给出了两类基于最小支撑树博弈的推广Bird配置,其中第二类推广Bird配置与现行的成本分摊机制很相似,且满足成本单调性、人口单调性以及感知公平性.