Abstract
We study strategic location choice by customers and sellers, termed the Bakers and Millers Game in the literature. In our generalized setting, each miller can freely choose any location for setting up a mill, while each baker is restricted in the choice of location for setting up a bakery. For optimal bargaining power, a baker would like to select a location with many millers to buy flour from and with little competition from other bakers. Likewise, a miller aims for a location with many bakers and few competing millers. Thus, both types of agents choose locations to optimize the ratio of agents of opposite type divided by agents of the same type at their chosen location. Originally raised in the context of Fractional Hedonic Games, the Bakers and Millers Game has applications that range from commerce to product design. We study the impact of location restrictions on the properties of the game. While pure Nash equilibria trivially exist in the setting without location restrictions, we show via a sophisticated, efficient algorithm that even the more challenging restricted setting admits equilibria. Moreover, the computed equilibrium approximates the optimal social welfare by a factor of at most $2\left(\frac{e}{e-1}\right)$. Furthermore, we give tight bounds on the price of anarchy/stability. On the conceptual side, the location choice feature adds a new layer to the standard setting of Hedonic Games, in the sense that agents that select the same location form a coalition. This allows to naturally restrict the possible coalitions that can be formed. With this, our model generalizes simple symmetric Fractional Hedonic Games on complete bipartite valuation graphs and also Hedonic Diversity Games with utilities single-peaked at 0. We believe that this generalization is also a very interesting direction for other types of Hedonic Games.
Abstract (translated)
我们在文献中研究了顾客和卖家的战略选址选择,称之为烘焙师与磨粉工博弈(Bakers and Millers Game)。在我们的一般化设定中,每个磨粉工可以自由选择任何位置来设立磨坊,而每个烘焙师则受限于他们可以选择的位置来设立面包店。为了获得最佳的议价能力,一个烘焙师会选择那些有许多磨粉工可供购买面粉并且几乎没有其他竞争性烘焙师的位置。同样地,一位磨粉工也会选择那些有许多烘焙师但竞争对手较少的位置。因此,这两类参与者都会选择位置以优化他们所选位置上相反类型代理的数量与相同类型代理数量之比。 最初在分数欢乐游戏(Fractional Hedonic Games)的背景下提出,烘焙师与磨粉工博弈的应用范围从商业到产品设计不等。我们研究了位置限制对游戏特性的影响。尽管在一个没有位置限制的情景下纯纳什均衡显然存在,但我们通过一个复杂且高效的算法展示,在更加具有挑战性的受限情景中也存在着这样的均衡点。此外,计算出的均衡接近最优社会福利的一个因子为最多 $2\left(\frac{e}{e-1}\right)$。 除此之外,我们还给出了价格混乱度/稳定度的紧致界值。从概念上看,位置选择功能向标准的欢乐游戏(Hedonic Games)设置中添加了一层新的内容,也就是说,选择相同位置的代理形成一个联盟。这自然地限制了可以形成的可能联盟类型。因此,我们的模型推广了在完全双部分估值图上的简单对称分数欢乐博弈以及具有0单峰效用的欢乐多样性游戏。 我们相信这种泛化对于其他类型的欢乐游戏来说也是一个非常有趣的探索方向。
URL
https://arxiv.org/abs/2501.05334