Strategic Facility Location with Clients that Minimize Total Waiting Time
We study a non-cooperative two-sided facility location game in which facilities and clients behave strategically. This is in contrast to many other facility location games in which clients simply visit their closest facility. Facility agents select a location on a graph to open a facility to attract as much purchasing power as possible, while client agents choose which facilities to patronize by strategically distributing their purchasing power in order to minimize their total waiting time. Here, the waiting time of a facility depends on its received total purchasing power. We show that our client stage is an atomic splittable congestion game, which implies existence, uniqueness and efficient computation of a client equilibrium. Therefore, facility agents can efficiently predict client behavior and make strategic decisions accordingly. Despite that, we prove that subgame perfect equilibria do not exist in all instances of this game and that their existence is NP-hard to decide. On the positive side, we provide a simple and efficient algorithm to compute 3-approximate subgame perfect equilibria.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Two-Stage Facility Location Games with Strategic Clients and Facilities
We consider non-cooperative facility location games where both facilities and clients act strategically and heavily influence each other. This contrasts established game-theoretic facility location models with non-strate…
Vocal Bursts Valence PredictionEquilibria in Two-Stage Facility Location with Atomic Clients
We consider competitive facility location as a two-stage multi-agent system with two types of clients. For a given host graph with weighted clients on the vertices, first facility agents strategically select vertices for…
Facility Location Problem with Capacity Constraints: Algorithmic and Mechanism Design Perspectives
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, …
Optimizing Multiple Simultaneous Objectives for Voting and Facility Location
We study the classic facility location setting, where we are given $n$ clients and $m$ possible facility locations in some arbitrary metric space, and want to choose a location to build a facility. The exact same setting…
Truthful Facility Location with Additive Errors
We address the problem of locating facilities on the $[0,1]$ interval based on reports from strategic agents. The cost of each agent is her distance to the closest facility, and the global objective is to minimize either…