New Paradigm for Facility Location Games: Group Externality, Fractional Preference and Minimum Distance

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. If the facility is a garbage dump from which all the agents want to keep as far away as possible, then the problem is called obnoxious facility games.We combined these two preferences into a new model called dual preference model where some agents like the facility but other agents do not like it. We are also working on the case when there are indifferent agents. We also did another extension for preference called 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. One example facility of this type is the hospital, where distance and virus density needs to strike a balance. In the society where there are relationship between agents, it is quite normal that one agent will be affected by agents in the same community. We use group externality to represent this type of agent interaction and for the first time introduce it into the facility location games in this project.Besides 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. One example for the min cost is bus stops for two different routes, where if an agent likes both bus routes (which serve the same purpose for her), then she will go to the closer stop. In this proposal, we will further extend the model to 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 weighed sum of the distances towards these two facilities.Another two-facility model we proposed studies the scenario where all agents like facility 1 and dislike facility 2. This scenario is possible to appear when two facilities are related but serving diverse functions. For example, a police station and a detention house. To guarantee the quick response and efficient control from police when security incidents happen in the detention house, the distance between two facilities cannot be too large. In this proposal, we study the opposite constraint where the distance between two facilities cannot be too small (both for the expansion purpose in the case of garbage dump sites and for city planning purpose in the case of favorable facilities). This is the first time that the minimum distance constraint is proposed in the facility location games