Proportional Fairness in Obnoxious Facility Location

• URL: http://arxiv.org/abs/2301.04340v2
• Date: Thu, 07 Nov 2024 06:13:43 GMT
• Title: Proportional Fairness in Obnoxious Facility Location
• Authors: Alexander Lam, Haris Aziz, Bo Li, Fahimeh Ramezani, Toby Walsh,
• Abstract summary: 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.
• Score: 70.64736616610202
• License:
• Abstract: We consider the obnoxious facility location problem (in which agents prefer the facility location to be far from them) and propose a hierarchy of distance-based proportional fairness concepts for the problem. These fairness axioms ensure that groups of agents at the same location are guaranteed to be a distance from the facility proportional to their group size. We consider deterministic and randomized mechanisms, and compute tight bounds on the price of proportional fairness. In the deterministic setting, we show that our proportional fairness axioms are incompatible with strategyproofness, and prove asymptotically tight $\epsilon$-price of anarchy and stability bounds for proportionally fair welfare-optimal mechanisms. In the randomized setting, we identify proportionally fair and strategyproof mechanisms that give an expected welfare within a constant factor of the optimal welfare. Finally, we prove existence results for two extensions to our model.

Related papers

• Nash Welfare and Facility Location [82.81742334337336]
  We consider the problem of locating a facility to serve a set of agents located along a line. The Nash welfare objective function, defined as the product of the agents' utilities, is known to provide a compromise between fairness and efficiency.
  arXiv  Detail & Related papers  (2023-10-06T09:06:44Z)
• 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)
• Fairness in Matching under Uncertainty [78.39459690570531]
  algorithmic two-sided marketplaces have drawn attention to the issue of fairness in such settings. We axiomatize a notion of individual fairness in the two-sided marketplace setting which respects the uncertainty in the merits. We design a linear programming framework to find fair utility-maximizing distributions over allocations.
  arXiv  Detail & Related papers  (2023-02-08T00:30:32Z)
• 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)
• Strategyproof and Proportionally Fair Facility Location [77.16035689756859]
  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.
  arXiv  Detail & Related papers  (2021-11-02T12:41:32Z)
• Wasserstein Robust Support Vector Machines with Fairness Constraints [15.004754864933705]
  We use a type-$infty$ Wasserstein ambiguity set centered at the empirical distribution to model distributional uncertainty. We numerically demonstrate that our proposed approach improves fairness with negligible loss of predictive accuracy.
  arXiv  Detail & Related papers  (2021-03-11T17:53:54Z)
• Learning Strategies in Decentralized Matching Markets under Uncertain Preferences [91.3755431537592]
  We study the problem of decision-making in the setting of a scarcity of shared resources when the preferences of agents are unknown a priori. Our approach is based on the representation of preferences in a reproducing kernel Hilbert space. We derive optimal strategies that maximize agents' expected payoffs.
  arXiv  Detail & Related papers  (2020-10-29T03:08:22Z)

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.