Strategyproof and Proportionally Fair Facility Location

• URL: http://arxiv.org/abs/2111.01566v3
• Date: Tue, 28 Nov 2023 16:00:07 GMT
• Title: Strategyproof and Proportionally Fair Facility Location
• Authors: Haris Aziz, Alexander Lam, Barton E. Lee, Toby Walsh
• Abstract summary: We focus on a simple, one-dimensional collective decision problem (often referred to as the facility location problem) We analyze a hierarchy of proportionality-based fairness axioms of varying strength. For each axiom, we characterize the family of mechanisms that satisfy the axiom and strategyproofness.
• Score: 77.16035689756859
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We focus on a simple, one-dimensional collective decision problem (often referred to as the facility location problem) and explore issues of strategyproofness and proportionality-based fairness. We introduce and analyze a hierarchy of proportionality-based fairness axioms of varying strength: Individual Fair Share (IFS), Unanimous Fair Share (UFS), Proportionality (as in Freeman et al, 2021), and Proportional Fairness (PF). For each axiom, we characterize the family of mechanisms that satisfy the axiom and strategyproofness. We show that imposing strategyproofness renders many of the axioms to be equivalent: the family of mechanisms that satisfy proportionality, unanimity, and strategyproofness is equivalent to the family of mechanisms that satisfy UFS and strategyproofness, which, in turn, is equivalent to the family of mechanisms that satisfy PF and strategyproofness. Furthermore, there is a unique such mechanism: the Uniform Phantom mechanism, which is studied in Freeman et al. (2021). We also characterize the outcomes of the Uniform Phantom mechanism as the unique (pure) equilibrium outcome for any mechanism that satisfies continuity, strict monotonicity, and UFS. Finally, we analyze the approximation guarantees, in terms of optimal social welfare and minimum total cost, obtained by mechanisms that are strategyproof and satisfy each proportionality-based fairness axiom. We show that the Uniform Phantom mechanism provides the best approximation of the optimal social welfare (and also minimum total cost) among all mechanisms that satisfy UFS.

Related papers

• The Leximin Approach for a Sequence of Collective Decisions [6.3734441349747035]
  We analyze the fairness of three known mechanisms: round-robin, maximum Nash welfare, and leximin. In the offline setting, we show that the three mechanisms fail to find a proportional or approximate-proportional outcome. In the online setting, we show that it is impossible to guarantee proportionality or its relaxations.
  arXiv  Detail & Related papers  (2023-05-29T11:28:27Z)
• First-Choice Maximality Meets Ex-ante and Ex-post Fairness [33.992491196317744]
  We design randomized mechanisms that satisfy first-choice maximality (FCM), i.e., maximizing the number of agents assigned their first choices. Our mechanisms also provide guarantees of ex-ante and ex-post fairness.
  arXiv  Detail & Related papers  (2023-05-08T09:57:30Z)
• 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)
• Social Diversity Reduces the Complexity and Cost of Fostering Fairness [63.70639083665108]
  We investigate the effects of interference mechanisms which assume incomplete information and flexible standards of fairness. We quantify the role of diversity and show how it reduces the need for information gathering. Our results indicate that diversity changes and opens up novel mechanisms available to institutions wishing to promote fairness.
  arXiv  Detail & Related papers  (2022-11-18T21:58: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)
• Monotonic Improvement Guarantees under Non-stationarity for Decentralized PPO [66.5384483339413]
  We present a new monotonic improvement guarantee for optimizing decentralized policies in cooperative Multi-Agent Reinforcement Learning (MARL) We show that a trust region constraint can be effectively enforced in a principled way by bounding independent ratios based on the number of agents in training.
  arXiv  Detail & Related papers  (2022-01-31T20:39:48Z)
• Near Instance-Optimality in Differential Privacy [38.8726789833284]
  We develop notions of instance optimality in differential privacy inspired by classical statistical theory. We also develop inverse sensitivity mechanisms, which are instance optimal (or nearly instance optimal) for a large class of estimands.
  arXiv  Detail & Related papers  (2020-05-16T04:53:48Z)
• 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.