Strategic facility location problems with linear single-dipped and single-peaked preferences

摘要

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 best-possible 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.