arXiv:2501.05334cs.GTcs.AI2025-01被引 1

研究买卖双方选址博弈,揭示受限选址下仍存在高效均衡。

The Bakers and Millers Game with Restricted Locations

  • 买卖双方根据对手密度与自身竞争度选择位置以优化利益比。
  • 算法证明受限情况下仍存在均衡,且社会福利近似最优的2倍以内。
  • 模型拓展了传统霍丹博弈,适用于商业选址与产品设计场景。

我们研究客户与卖家的战略选址问题,即文献中的“面包师与磨坊主博弈”。在推广设置中,每个磨坊主可自由选择任意位置设立磨坊,而每个面包师的选址受限。为获得最优议价能力,面包师希望选在有众多磨坊且竞争者少的位置;磨坊主则希望靠近大量面包师且竞争对手少。因此,双方均选择使本类型代理数量与异类型代理数量之比最优的位置。该问题最初源于分数式霍丹博弈,在商业与产品设计中有广泛应用。我们研究选址限制对博弈性质的影响:无限制时纯纳什均衡显然存在,而通过一个高效算法,我们证明即使在更复杂的受限设定下也存在均衡,且计算出的均衡近似最优社会福利至多为$2 rac{e}{e-1}$倍。此外,我们给出了价格的紧界(PoA/PoS)。从概念上,选址选择引入了新的合作结构——同位置代理形成联盟,自然限制了可能的联盟组合。本模型推广了完全二分图上的对称分数式霍丹博弈,以及效用在0处单峰的多样性霍丹博弈。我们认为这一推广也为其他霍丹博弈提供了重要方向。

原文摘要 · Abstract (English)

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.

博弈论选址优化纳什均衡社会福利

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。