AAAI Publications, Workshops at the Twenty-Ninth AAAI Conference on Artificial Intelligence

Font Size: 
Strategyproof Mechanisms for One-Dimensional Hybrid and Obnoxious Facility Location Models
Itai Feigenbaum, Jay Sethuraman

Last modified: 2015-04-01


We consider a strategic variant of the facility location problem. We would like to locate a facility on a closed interval. There are n agents located on that interval, divided into two types: type 1 agents, who wish for the facility to be as far from them as possible, and type 2 agents, who wish for the facility to be as close to them as possible. Our goal is to maximize a form of aggregated social benefit: maxisum– the sum of the agents’ utilities, or the egalitarian objective– the minimal agent utility. The strategic aspect of the problem is that the agents’ locations are not known to us, but rather reported to us by the agents– an agent might misreport his location in an attempt to move the facility away from or towards to his true location. We therefore require the facility-locating mechanism to be strategyproof, namely that reporting truthfully is a dominant strategy for each agent. As simply maximizing the social benefit is generally not strategyproof, our goal is to design strategyproof mechanisms with good approximation ratios. In this paper, we provide a best-possible 3approximate deterministic strategyproof mechanism, as well as a 23/13 approximate randomized strategyproof mechanism, both for the maxisum objective. We provide lower bounds of 3 and 3/2 on the approximation ratio attainable for maxisum, in the deterministic and randomized settings, respectively. For the egalitarian objective, we show that no bounded approximation ratio is attainable in the deterministic setting, and provide a lower bound of 3/2 for the randomized setting. To obtain our deterministic lower bounds, we characterize all deterministic strategyproof mechanisms when all agents are of type 1. Finally, while still restricting ourselves to agents of type 1 only, we consider a generalized model that allows an agent to control more than one location. In this generalized model, we provide best-possible 3and 3 approximate strategyproof 2 mechanisms for the maxisum objective in the deterministic and randomized settings, respectively.

Full Text: PDF