Budget Feasible Facility Location Games: From Agents to Facilities

Project: Research

View graph of relations


Algorithmic game theory is a research field integrating game theory and algorithm design. The major target is to design good algorithms in strategic environments. In this project, we propose to study a well established problem in algorithmic game theory called facility location games. In the most classic setting, the government plans to build a facility (a convenience store or a bus stop) on a street where some strategic agents with private information live. Agents want to be as close as possible to the facility. The objective of the government is to collect the agents' information and use a mechanism to decide where to build the facility so that agents will not gain by reporting false information (this property is called strategyproofness) and certain objective values (like social cost or maximum agent cost) are approximately optimized. The mechanism can be either deterministic or randomized. An upper bound of the approximation ratio for strategyproof mechanisms can be proved by designing a certain strategyproof mechanism while a lower bound of the approximation ratio for strategyproof mechanisms means that in order to achieve strategyproofness, one cannot do better than that certain ratio. In the recent years, many extensions to the original facility location games are proposed and studied by the researchers, including the obnoxious facility games where agents want to be as far away as possible from the facility, dual preference model where some agents like the facility and others do not like the facility, double-peaked preference where an agent does not want to be too close to the facility but also not too far away from the facility, where the last two are proposed by us. Besides the one facility case, researchers have also studied two-facility location games. In the homogeneous two-facility location game, the two facilities are the same and therefore agents will only go to the better one of these two. In the heterogeneous two-facility location game, agents may like one facility or both facilities. When an agent likes both facility, earlier research assumes that the cost of an agent is the summation of her distance towards the two facilities. We extended the cost function to be either min or max where the cost of an agent is either decided by the closer facility or the farther facility. We also proposed a fractional model where the two facilities serve the similar purpose for all agents. For example, a supermarket and a convenience store. Different agents will allocate different proportion of time to these two facilities and therefore their cost will be a weighted sum of the distances towards these two facilities. Almost all previous works only study strategic behaviors of the agents. In this proposal, we plan to include facility holders into the game and study the strategic behaviors of both the agents and the facility holders. We will study the discrete version of the facility location games where each facility can only be built by its holder at a certain location. In order to handle the two different sides, we will also introduce money into facility location games and use a budget to limit the ability of the government to select facilities to be built. Finally, we combine the roles of agents and facility holders by considering community construction, which will have a great potential of opening up a new research direction for mechanism design where payments can only be given to the winner but all the agents participating in the game will have utility, bridging the gap between mechanism design with money and mechanism design without money. 


Project number9042814
Grant typeGRF
Effective start/end date1/01/20 → …