Truthful Mechanism Design for Facility Location Games Based on the Variance of the Agents Preferences


Student thesis: Doctoral Thesis

View graph of relations


Related Research Unit(s)


Awarding Institution
Award date15 Sep 2017


Designing mechanisms that achieve desirable properties is a key research topic in the literature of mechanism design and social choice theory, and have also attracted considerable attention of AI researchers and computer scientists in the recent years. The literature in algorithmic mechanism design mostly focuses on mechanism design, which can enforce payments to give an incentive for agents to act honestly. Researchers found that this kind of mechanisms cannot be applied to the real life efficiently because monetary transfers are not possible or desirable due to security/banking issues. Hence, in recent years, researchers turn their focuses to the mechanism design without monetary transfers.

Procaccia and Tennenholtz were the first to study this problem. They introduce a case study in approximate mechanism design without money, where we are given a list of agents on a line segment and each agent has his location information. The mechanism needs to locate a single facility based on the location information reported by all agents. The cost of an agent is the distance between his real location and the output location of the facility. It is obvious that agents have incentive to misreport their location information to gain advantages.

Hence, the mechanism should enforce the property of strategy-proofness. In other words, if agents misreport their locations, they will not gain any advantage in the final outcome. This model is then renamed as facility location game and extended to the scenario with multiple homogeneous facilities as well as one agent processing multiple locations case.

Meanwhile, Serafino and Ventre introduced a variant of the traditional facility location problem where two heterogeneous facilities are to be built on the line segment. Besides the location information, each agent has to report his preference on each of the facilities where the cost of an agent is the sum of the distances to his preferred facilities.

In this thesis, we studied three variants of the facility location game, which are the optional preference model, the fractional preference model and the relational preference model. In the work of Serafino and Ventre, although agents can report their preferences on the two heterogeneous facilities, i.e. how much they prefer the corresponding facilities, in some situations, agents may not require both of them. For example, if the heterogeneous facilities are the bus stops with different bus lines on it. Hence, in the optional preference model, when agents prefer both facilities, we will treat them as preferring any one of them, and pick the best one for them according to the objective function.

Then we observed that the literatures so far only use binary representation to indicate whether an agent prefers a facility or not. In some situations, it is likely that one agent may prefer one facility more than another facility. For example, a supermarket and a convenient store are going to be built, then an agent may only go to the supermarket during the weekend, whereas he may go to the convenience store every day in weekdays. Then his preference on the supermarket and convenient store should be 28\% and 72\% respectively.

Hence, we introduce the fractional model that allows agents to indicate how much they prefer the corresponding facilities in a fractional form, which can capture the real-life scenario.

To the best of our knowledge, in the literatures of the mechanism design for facility location problems, it is well known that the distance between the agent's real location and the output location of the facilities defines the cost of an agent. However, in some real-life scenarios, the cost may not be purely defined by the distance between the agent's real location and the location of the facilities. It may also involve other factors. For example, if the government decides to build a department store in a city, it is obvious that agents want it to be built closer to their living location because of convenience. But they may also want it to be built closer to their families or friends. Suppose a department store will offer some ad hoc promotions regularly, such as buy 2 get 1 free, get 30\% off when the accumulate payment is greater than \$1000, etc. Usually, a single customer may not be able to spend that much money to reach the target of the promotions.

In this scenario, he may also want to group the payment with his family or friends in order to get those discounts. But if his friend or family is far away from the department store, they will have less incentive to visit the store. Under this scenario, agents may want the locations of their friends and family also be taken into consideration when deciding the location of the facility. Hence, we propose the relational preference model, where each agent can give a weight to all other agents to indicate the importance of the relationship among them. Then the cost of an agent is equal to the sum of the distance between the agent's real location and the location of the facility and the distance between other agents' real locations and the location of the facility with the multiplication of the corresponding weight parameter.

In each of the proposed models, we present different deterministic strategy-proof mechanisms without monetary transfers. The performances of such mechanisms with respect to different objectives are also analyzed. These results significantly improve our knowledge and understanding on mechanism design of facility location games.

    Research areas

  • Facility Location, Mechanism Design, Social choice