Shapley Facility Location Games
Shapley Facility Location Games
复制标题
沙普利设施定位游戏
DOI：
10.1007/978-3-319-71924-5_5
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Moshe Tennenholtz
中科院分区：
文献类型：
--
作者：
Omer Ben;Moshe Tennenholtz
设施的位置游戏一直是经济学，运营研究和计算机科学的主要兴趣的话题，从开创性的工作开始。空间设施的位置模型已成功预测了各种情况下竞争的结果。在典型的设施位置游戏中，用户/客户/选民将映射到代表他们偏好的度量空间，每个玩家在该空间中选择一个点（设施）。在文献中考虑的大多数设施位置游戏中，假定用户可以确定地采取行动：鉴于玩家选择的设施，用户被吸引到其最近的设施中。本文介绍了带有概率吸引力的设施位置游戏，由于与沙普利价值的连接令人惊讶，因此被称为Shapley设施的位置游戏。我们在此模型中采用的具体吸引力功能与有关选择预测的行为经济学文献的最新发现保持一致。鉴于此模型，我们的第一个主要结果是Shapley设施的位置游戏是潜在的游戏。因此，它们具有纯净的NASH平衡。此外，后者对于任何紧凑的用户空间，该空间上的任何用户分布以及任何数量的玩家都是正确的。请注意，这与Hotelling设施位置游戏形成鲜明对比。在我们的第二个主要结果中，我们表明，在假设玩家可以计算近似最佳响应的假设下，玩家可以通过动力学有效地学习近似平衡曲线。我们的第三个主要结果是对这类游戏的无政府状态价格的限制，并且显示界限很紧。最终，我们表明，玩家的收益与他们在联盟游戏中的沙普利价值一致，在该游戏中，联盟的收益是用户的社会福利。
Facility location games have been a topic of major interest in economics, operations research and computer science, starting from the seminal work by Hotelling. Spatial facility location models have successfully predicted the outcome of competition in a variety of scenarios. In a typical facility location game, users/customers/voters are mapped to a metric space representing their preferences, and each player picks a point (facility) in that space. In most facility location games considered in the literature, users are assumed to act deterministically: given the facilities chosen by the players, users are attracted to their nearest facility. This paper introduces facility location games with probabilistic attraction, dubbed Shapley facility location games, due to a surprising connection to the Shapley value. The specific attraction function we adopt in this model is aligned with the recent findings of the behavioral economics literature on choice prediction. Given this model, our first main result is that Shapley facility location games are potential games; hence, they possess pure Nash equilibrium. Moreover, the latter is true for any compact user space, any user distribution over that space, and any number of players. Note that this is in sharp contrast to Hotelling facility location games. In our second main result we show that under the assumption that players can compute an approximate best response, approximate equilibrium profiles can be learned efficiently by the players via dynamics. Our third main result is a bound on the Price of Anarchy of this class of games, as well as showing the bound is tight. Ultimately, we show that player payoffs coincide with their Shapley value in a coalition game, where coalition gains are the social welfare of the users.