Proportional Fairness in Obnoxious Facility Location
- URL: http://arxiv.org/abs/2301.04340v1
- Date: Wed, 11 Jan 2023 07:30:35 GMT
- Title: Proportional Fairness in Obnoxious Facility Location
- Authors: Haris Aziz, Alexander Lam, 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.
- Score: 100.88307501458418
- License: http://creativecommons.org/publicdomain/zero/1.0/
- 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, not only are our
proportional fairness axioms incompatible with strategyproofness, the Nash
equilibria may not guarantee welfare within a constant factor of the optimal
welfare. On the other hand, in the randomized setting, we identify
proportionally fair and strategyproof mechanisms that give an expected welfare
within a constant factor of the optimal welfare.
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) - 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.