Facility Location Games Beyond Single-Peakedness: the Entrance Fee Model

• URL: http://arxiv.org/abs/2204.11282v2
• Date: Mon, 15 Apr 2024 13:51:21 GMT
• Title: Facility Location Games Beyond Single-Peakedness: the Entrance Fee Model
• Authors: Mengfan Ma, Mingyu Xiao, Tian Bai, Bakh Khoussainov,
• Abstract summary: We introduce a novel model where each facility charges an entrance fee. In our model, the entrance fee function is allowed to be an arbitrary function. We design strategyproof mechanisms with favorable approximation ratios.
• Score: 18.86193543684732
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Facility Location Games with Scaling Effects [69.28397508730046]
  We take the classic facility location problem and consider a variation in which each agent's individual cost function is equal to their distance from the facility multiplied by a scaling factor. We find results on the total and maximum cost approximation ratios achievable by strategyproof and anonymous mechanisms.
  arXiv  Detail & Related papers  (2024-02-29T07:08:18Z)
• Refined Mechanism Design for Approximately Structured Priors via Active Regression [50.71772232237571]
  We consider the problem of a revenue-maximizing seller with a large number of items for sale to $n$ strategic bidders. It is well-known that optimal and even approximately-optimal mechanisms for this setting are notoriously difficult to characterize or compute.
  arXiv  Detail & Related papers  (2023-10-11T20:34:17Z)
• Proportional Fairness in Obnoxious Facility Location [70.64736616610202]
  We propose a hierarchy of distance-based proportional fairness concepts for the problem. We consider deterministic and randomized mechanisms, and compute tight bounds on the price of proportional fairness. We prove existence results for two extensions to our model.
  arXiv  Detail & Related papers  (2023-01-11T07:30:35Z)
• Random Rank: The One and Only Strategyproof and Proportionally Fair Randomized Facility Location Mechanism [103.36492220921109]
  We show that although Strong Proportionality is a well-motivated and basic axiom, there is no deterministic strategyproof mechanism satisfying the property. We then identify a randomized mechanism called Random Rank which satisfies Strong Proportionality in expectation. Our main characterizes Random Rank as the unique mechanism that achieves universal truthfulness, universal anonymity, and Strong Proportionality in expectation.
  arXiv  Detail & Related papers  (2022-05-30T00:51:57Z)
• Probabilistically Robust Recourse: Navigating the Trade-offs between Costs and Robustness in Algorithmic Recourse [34.39887495671287]
  We propose an objective function which simultaneously minimizes the gap between the achieved (resulting) and desired recourse invalidation rates. We develop novel theoretical results to characterize the recourse invalidation rates corresponding to any given instance. Experimental evaluation with multiple real world datasets demonstrates the efficacy of the proposed framework.
  arXiv  Detail & Related papers  (2022-03-13T21:39:24Z)
• Automated Mechanism Design for Classification with Partial Verification [64.69418921224529]
  We study the problem of automated mechanism design with partial verification. We focus on truthful mechanisms in the setting where all types share the same preference over outcomes.
  arXiv  Detail & Related papers  (2021-04-12T03:29:31Z)
• VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback [104.06766271716774]
  We study a multi-round welfare-maximising mechanism design problem in instances where agents do not know their values. We first define three notions of regret for the welfare, the individual utilities of each agent and that of the mechanism. Our framework also provides flexibility to control the pricing scheme so as to trade-off between the agent and seller regrets.
  arXiv  Detail & Related papers  (2020-04-19T18:00:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.