Related papers: Equitable Mechanism Design for Facility Location

Equitable Mechanism Design for Facility Location

URL: http://arxiv.org/abs/2506.10460v1
Date: Thu, 12 Jun 2025 08:08:58 GMT
Title: Equitable Mechanism Design for Facility Location
Authors: Toby Walsh,
Abstract summary: We consider strategy proof mechanisms for facility location which maximize equitability between agents.<n>We first prove a simple but fundamental impossibility result that no strategy proof mechanism can bound the approximation ratio of the optimal Gini index of utilities.
Score: 18.168659230989384
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We consider strategy proof mechanisms for facility location which maximize equitability between agents. As is common in the literature, we measure equitability with the Gini index. We first prove a simple but fundamental impossibility result that no strategy proof mechanism can bound the approximation ratio of the optimal Gini index of utilities for one or more facilities. We propose instead computing approximation ratios of the complemented Gini index of utilities, and consider how well both deterministic and randomized mechanisms approximate this. In addition, as Nash welfare is often put forwards as an equitable compromise between egalitarian and utilitarian outcomes, we consider how well mechanisms approximate the Nash welfare.

Related papers

Prediction-Augmented Mechanism Design for Weighted Facility Location [1.6552489352816389]
We provide a prediction augmented algorithmic framework for balancing the consistency and robustness over strategic agents with non-uniform weights.<n>We prove that there is no strategyproof deterministic mechanism that reach $1$-consistency and $Oleft( n cdot fracW_maxW_min right)$-robustness in weighted FLP, even with fully predictions of all agents.
arXiv Detail & Related papers (2025-07-09T03:13:52Z)
Fair and Welfare-Efficient Constrained Multi-matchings under Uncertainty [17.364297444721057]
We study fair allocation of constrained resources, where a market designer optimize overall welfare while maintaining group fairness. In many large-scale settings, utilities are not known in advance, but are instead observed after realizing the allocation. We discuss these trade-offs under two paradigms for preference modeling.
arXiv Detail & Related papers (2024-11-04T22:42:34Z)
Learning Payment-Free Resource Allocation Mechanisms [19.60309632660988]
We consider the design of mechanisms that limited resources among self-interested agents using neural networks. We contribute a new end-to-end neural network architecture, ExS-Net, that accommodates the idea of "money-burning" for mechanism design without payments.
arXiv Detail & Related papers (2023-11-18T01:21:54Z)
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)
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)
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)
LRA: an accelerated rough set framework based on local redundancy of attribute for feature selection [81.19294803707648]
We propose the LRA framework for accelerating rough set algorithms. It is a general-purpose framework which can be applied to almost all rough set methods significantly.
arXiv Detail & Related papers (2020-10-31T08:50:28Z)
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)
Towards Assessment of Randomized Smoothing Mechanisms for Certifying Adversarial Robustness [50.96431444396752]
We argue that the main difficulty is how to assess the appropriateness of each randomized mechanism. We first conclude that the Gaussian mechanism is indeed an appropriate option to certify $ell$-norm. Surprisingly, we show that the Gaussian mechanism is also an appropriate option for certifying $ell_infty$-norm, instead of the Exponential mechanism.
arXiv Detail & Related papers (2020-05-15T03:54:53Z)

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