Strategic facility location problems with linear single-dipped and single-peaked preferences
- PDF / 700,577 Bytes
- 47 Pages / 439.37 x 666.142 pts Page_size
- 13 Downloads / 126 Views
Strategic facility location problems with linear single-dipped and single-peaked preferences Itai Feigenbaum1 • Minming Li2 • Jay Sethuraman3 • Fangzhou Wang2 Shaokun Zou2
•
Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We consider the design of mechanisms for locating facilities on an interval. There are multiple agents on the interval, each receiving a utility determined by their distances to the facilities. The objectives considered are maximization of social welfare (sum of utilities) and egalitarian welfare (minimum utility). Agents can misreport their locations, and so we require the mechanisms to be strategyproof—no agent should be able to benefit from misreporting; subject to strategyproofness, we attempt to design mechanisms that are approximately optimal (have small worst-case approximation ratios). The novelty of our work is the consideration of models in which single-dipped and single-peaked preferences exist simultaneously. We consider two models. In the first model, there is a single facility, and agents may disagree about its nature: some agents prefer to be near the facility, while others prefer to be far from it. In the second model, there are two facilities: a desirable facility that all agents want near, and an undesirable facility that all agents want far. We design a variety of approximately optimal strategyproof mechanisms for both models, and prove several lower bounds as well. For the social welfare objective, we provide bestpossible deterministic strategyproof mechanisms in the first model and the second model. We then provide improved randomized strategyproof mechanisms for each model, as well as a non-tight lower bound on the worst-case approximation ratio attainable by such mechanisms for the first model. For the egalitarian welfare objective, we provide a lower bound on randomized strategyproof mechanisms for the first model, as well as an optimal (non-approximate) strategyproof mechanism for the second model. All of our mechanisms are also group strategyproof: no coalition of agents can unanimously benefit from misreporting.
1 Introduction In classical facility location problems [6], given a set of agent locations, a planner’s goal is to locate facilities in a way that optimizes some function of the distances of the facilities from the agents. Procaccia and Tennenholtz [15] initiated a study of a version of facility location problems which involves strategic behavior and approximation. In that version, & Itai Feigenbaum [email protected] Extended author information available on the last page of the article
123
Autonomous Agents and Multi-Agent Systems
agents’ locations are private information, and agents may misreport this information so as to induce the planner into locating the facility at a location they find more favorable. The goal is to design a facility location mechanism that is strategyproof (incentivizes agents to report their locations truthfully) and approximately optimal (earns a substantive fraction of the optimal obje
Data Loading...
