Cost-sharing in Parking Games

本文从合作博弈理论的角度研究了停车函数的总位移统计量。我们引入了停车博弈，这是一种基于总位移统计量的特征函数形式的联合成本分担博弈。我们展示了停车博弈是超模成本分摊博弈，这表明合作是困难的（即它们的核心是空的）。接下来，我们研究了它们的Shapley值，这个值形式化了一个“公平”的成本分摊概念，相当于根据随机到达顺序为每辆车收取其预期边际位移。我们的主要贡献是提出了一个多项式时间算法来计算停车博弈的Shapley值，与已知的计算任意博弈Shapley值的难度结果形成对比。该算法利用了总位移的排列不变性、组合枚举和动态规划。最后，我们总结了超模成本分摊博弈的替代解概念和与组合学其他领域的联系的开放性问题。

论文研究了停车函数的总位移统计量，从合作博弈论的角度分析了该统计量的特性。论文试图解决的问题是如何公平地分摊停车费用。

论文提出了停车博弈的概念，通过计算Shapley值来实现费用的公平分配。与现有研究相比，该方法的新意在于将停车问题转化为博弈论问题，并提出了计算Shapley值的多项式时间算法。

论文的亮点在于提出了停车博弈的概念，并且开发了一种多项式时间算法来计算Shapley值。论文还探讨了超模博弈的其他解决方案，并与组合数学中的其他领域建立了联系。

最近相关的研究包括《Shapley Value Computation in Cooperative Games: A Comprehensive Survey》和《Game Theory and Parking Functions》等。