arXiv preprint ·
Strategic Facility Location in Euclidean Spaces
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
The strategic facility location problem is defined as follows: $n$ agents report their location in a metric space, and the objective is to design a \emph{mechanism} deciding the (possibly randomized) location of a facility such that agents have no incentive to lie about their position. We focus on the egalitarian cost, which means that the goal of the mechanism is to minimize the expected maximal facility-agent distance. Meanwhile, mechanisms must be \emph{truthful} (or \emph{strategyproof}): no agent may decrease their expected distance to the facility via lying on their location. Designing truthful mechanisms minimizing the approximation ratio is a well-studied problem, and the optimal solution is known for the real line. We focus in this paper on higher dimension Euclidean spaces, for which gaps remain between the best known lower and upper bounds. We first show that, maybe counter-intuitively, the problem is easier for two agents on the plane rather than on the line: the mechanism can exploit the additional dimension to prevent more efficiently agent lies. Based on this intuition, we devise lower bounds for $\mathbb R^d$ asymptotically matching the best known approximation factor of $2$ for large $d$. We also provide novel mechanism ideas, improving over the best known algorithms on the plane, and when the agents belong to $\mathbb R^d$ but the facility may use an additional dimension.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computer Science & Game Theory
Input-to-State Stability Framework for Fully Distributed Primal-Dual Dynamics for Quadratic GNEPs Without Multiplier Consensus
Optimal Rates for Agentic Networked Information Aggregation
Protocol effects on feature-based hardware-Trojan detection across Trust-Hub families
Riemannian Optimization for Multi-Player Quantum Games on Product Unitary Manifolds
The Internal Anatomy of Strategic Choice in Large Language Models
Get the few papers worth your time in Computer Science & Game Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.