Equilibria 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 opening their facilities. Then, the clients strategically select which of the opened facilities in their neighborhood to patronize. Facilities want to attract as much client weight as possible, clients want to minimize congestion on the chosen facility. All recently studied versions of this model assume that clients can split their weight strategically. We consider clients with unsplittable weights but allow mixed strategies. So clients may randomize over which facility to patronize. Besides modeling a natural client behavior, this subtle change yields drastic changes, e.g., for a given facility placement, qualitatively different client equilibria are possible. As our main result, we show that pure subgame perfect equilibria always exist if all client weights are identical. For this, we use a novel potential function argument, employing a hierarchical classification of the clients and sophisticated rounding in each step. In contrast, for non-identical clients, we show that deciding the existence of even approximately stable states is computationally intractable. On the positive side, we give a tight bound of $2$ on the price of anarchy which implies high social welfare of equilibria, if they exist.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
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 faci…
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 PredictionFacility Reallocation on the Line
We consider a multi-stage facility reallocation problems on the real line, where a facility is being moved between time stages based on the locations reported by $n$ agents. The aim of the reallocation algorithm is to mi…
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…
Orbital Facility Location Problem for Satellite Constellation Servicing Depots
This work proposes an adaptation of the Facility Location Problem for the optimal placement of on-orbit servicing depots for satellite constellations in high-altitude orbit. The high-altitude regime, such as Medium Earth…