2022/04/24 by Mengfan Ma, Ma, Mengfan, Mingyu Xiao +5
Decision Sciences · Economics, Econometrics and Finance · Social Sciences · #Artificial Intelligence (cs.AI) #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #Experimental Behavioral Economics Studies #FOS: Computer and information sciences #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.2204.11282
openalex publication_date 2022/04/24 · openalex created_date 2022/04/28 · openalex updated_date 2026/07/28
The facility location game has been studied extensively in mechanism design. In the classical model, each agent's cost is solely determined by her distance to the nearest facility. In this paper, we introduce a novel model where each facility charges an entrance fee. Thus, the cost of each agent is determined by both the distance to the facility and the entrance fee of the facility. In our model, the entrance fee function is allowed to be an arbitrary function, causing agents' preferences may no longer be single-peaked anymore: This departure from the classical model introduces additional challenges. We systematically delve into the intricacies of the model, designing strategyproof mechanisms with favorable approximation ratios. Additionally, we complement these ratios with nearly-tight impossibility results. Specifically, for one-facility and two-facility games, we provide upper and lower bounds for the approximation ratios given by deterministic and randomized mechanisms with respect to utilitarian and egalitarian objectives.