Mechanism Design for Facility Location Games


Student thesis: Doctoral Thesis

View graph of relations


Related Research Unit(s)


Awarding Institution
Award date23 Jun 2020


Mechanism design is a research field integrating game theory and algorithm design. The major task is to design good algorithms in strategic environments. Facility location games constitute a well established area in approximate mechanism design without money. In the most classic setting, the authority plans to build some facilities on a street where some strategic agents with private information are located. Agents want to be as close as possible to the facilities. The objective of the authority is to collect the agents’ information and use a mechanism to decide where to build the facilities so that no agent will gain by reporting false information and certain system objectives are approximately optimized. The mechanism can be either deterministic or randomized.

In the recent years, many extensions to the classic facility location games have been proposed and studied. Most of them assume uniform preferences of agents. This thesis studies more diversified preferences of the agents. It consists of three parts: 1) a study on the two-opposite-facility location games with a penalty whose amount depends on the distance between the two facilities to be opened by an authority; 2) a study on the dual-role facility location games where every agent plays a dual role of facility and customer; 3) a study on the budgeted facility location games with strategic facilities.

In the first part, two-opposite-facility location games are considered, which is motivated by the practical scenario that the authority plans to build two facilities with opposite characteristics for agents on a street and the distance between the facilities should not be too large. Under the objective of maximizing the social welfare, randomized and deterministic truthful mechanisms with provable approximation ratios are designed, and a lower bound on the approximation ratio of any deterministic truthful mechanism is established.

In the second part, the budgeted facility location games are studied, where, in contrast to the classic setting, strategic facilities are the players of the game. In the game, customers and facilities are located at publicly known locations on a line segment. Each selfish facility has an opening-cost as her private information, and she may strategically report it. Upon receiving the reports, the government uses a mechanism to select some facilities to open and pay them using a given budget. Upper and lower bounds on the approximation ratios of truthful budget feasible mechanisms for four utilitarian and egalitarian objectives are derived.

In the third part, a novel model of monetary facility location games is proposed, where every agent plays a dual role of facility and customer. In this game, each selfish agent is located on a publicly known location in a metric space, and can allow a facility to be opened at her place. But the opening cost is the private information and she may strategically report the opening cost. Besides, each agent also bears a service cost equal to the distance to the nearest open facility. The normalized truthful mechanisms for this game are characterized. Truthful mechanisms are designed for approximately optimizing several system objectives.