In the one-dimensional facility location problem, agents are located on the real line, and a planner's goal is to build one or more facilities on the line to serve the agents. The cost of an agent is her distance to the nearest facility. The problem asks to locate facilities to minimize the total cost of all agents (the utilitarian objective) or the maximum cost among all agents (the egalitarian objective). It is well-known that both optimization problems can be solved in polynomial time [19]. Over the past decade [1, 3, 7, 21, 23, 27], these problems have undergone intensive study from the perspectives of mechanism design and game theory. A key conversion in the models is that now each agent becomes strategic and may misreport her position to decrease her cost. These new problems are called the facility location games, which require to design mechanisms that elicit the true positions of agents and output facility locations to (approximately) minimize the total or maximum cost. Moulin [22] provides a complete characterization of strategyproof mechanisms for the facility location game on line where agents have single-peaked preferences, with no consideration for the optimization of the objective function.

We take the classic facility location problem and consider a variation, in which each agent's individual cost function is equal to their distance from the facility multiplied by a scaling factor which is determined by the facility placement. In addition to the general class of continuous scaling functions, we also provide results for piecewise linear scaling functions which can effectively approximate or model the scaling of many real world scenarios. We focus on the objectives of total and maximum cost, describing the computation of the optimal solution. We then move to the approximate mechanism design setting, observing that the agents' preferences may no longer be single-peaked. Consequently, we characterize the conditions on scaling functions which ensure that agents have single-peaked preferences. Under these conditions, we find results on the total and maximum cost approximation ratios achievable by strategyproof and anonymous mechanisms.

We consider the facility location problem in the one-dimensional setting where each facility can serve a limited number of agents from the algorithmic and mechanism design perspectives. From the algorithmic perspective, we prove t hat the corresponding optimization problem, where the goal is t o locate facilities to minimize either the total cost to all ag ents or the maximum cost of any agent is NPhard. However, we show that the problem is fixed-parameter tractable, and the optimal solution can be computed in polynomial time whenever the number of facilities is bounded, or when all facilit ies have identical capacities. We then consider the problem fro m a mechanism design perspective where the agents are strategic and need not reveal their true locations. We show that sev - eral natural mechanisms studied in the uncapacitated setti ng either lose strategyproofness or a bound on the solution qua l-ity for the total or maximum cost objective. We then propose new mechanisms that are strategyproof and achieve approximation guarantees that almost match the lower bounds.

We revisit the well-studied problem of constructing strategyproof approximation mechanisms for facility location games, but offer a fundamentally new perspective by considering risk averse designers. Specifically, we are interested in the tradeoff between a randomized strategyproof mechanism's approximation ratio, and its variance (which has long served as a proxy for risk). When there is just one facility, we observe that the social cost objective is trivial, and derive the optimal tradeoff with respect to the maximum cost objective. When there are multiple facilities, the main challenge is the social cost objective, and we establish a surprising impossibility result: under mild assumptions, no smooth approximation-variance tradeoff exists. We also discuss the implications of our work for computational mechanism design at large.

We study the problem of locating a single facility on a real line based on the reports of self-interested agents, when agents have double-peaked preferences, with the peaks being on opposite sides of their locations.We observe that double-peaked preferences capture real-life scenarios and thus complement the well-studied notion of single-peaked preferences. We mainly focus on the case where peaks are equidistant from the agents’ locations and discuss how our results extend to more general settings. We show that most of the results for single-peaked preferences do not directly apply to this setting; this makes the problem essentially more challenging. As our main contribution, we present a simple truthful-in-expectation mechanism that achieves an approximation ratio of 1+b/c for both the social and the maximum cost, where b is the distance of the agent from the peak and c is the minimum cost of an agent. For the latter case, we provide a 3/2 lower bound on the approximation ratio of any truthful-in-expectation mechanism. We also study deterministic mechanisms under some natural conditions, proving lower bounds and approximation guarantees. We prove that among a large class of reasonable mechanisms, there is no deterministic mechanism that outpeforms our truthful-in-expectation mechanism.