Paper Reading AI Learner

The Bakers and Millers Game with Restricted Locations

2025-01-09 15:59:32
Simon Krogmann, Pascal Lenzner, Alexander Skopalik

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

PDF

https://arxiv.org/pdf/2501.05334.pdf


Tags
3D Action Action_Localization Action_Recognition Activity Adversarial Agent Attention Autonomous Bert Boundary_Detection Caption Chat Classification CNN Compressive_Sensing Contour Contrastive_Learning Deep_Learning Denoising Detection Dialog Diffusion Drone Dynamic_Memory_Network Edge_Detection Embedding Embodied Emotion Enhancement Face Face_Detection Face_Recognition Facial_Landmark Few-Shot Gait_Recognition GAN Gaze_Estimation Gesture Gradient_Descent Handwriting Human_Parsing Image_Caption Image_Classification Image_Compression Image_Enhancement Image_Generation Image_Matting Image_Retrieval Inference Inpainting Intelligent_Chip Knowledge Knowledge_Graph Language_Model LLM Matching Medical Memory_Networks Multi_Modal Multi_Task NAS NMT Object_Detection Object_Tracking OCR Ontology Optical_Character Optical_Flow Optimization Person_Re-identification Point_Cloud Portrait_Generation Pose Pose_Estimation Prediction QA Quantitative Quantitative_Finance Quantization Re-identification Recognition Recommendation Reconstruction Regularization Reinforcement_Learning Relation Relation_Extraction Represenation Represenation_Learning Restoration Review RNN Robot Salient Scene_Classification Scene_Generation Scene_Parsing Scene_Text Segmentation Self-Supervised Semantic_Instance_Segmentation Semantic_Segmentation Semi_Global Semi_Supervised Sence_graph Sentiment Sentiment_Classification Sketch SLAM Sparse Speech Speech_Recognition Style_Transfer Summarization Super_Resolution Surveillance Survey Text_Classification Text_Generation Time_Series Tracking Transfer_Learning Transformer Unsupervised Video_Caption Video_Classification Video_Indexing Video_Prediction Video_Retrieval Visual_Relation VQA Weakly_Supervised Zero-Shot