University of Twente Student Theses


Equilibria in the Two-Stage Facility Location Game With Unsplittable Clients

Vos, M.C. (2023) Equilibria in the Two-Stage Facility Location Game With Unsplittable Clients.

[img] PDF
Abstract:We consider a non-cooperative facility location game where facility and client players strategically interact on a given host graph. This is represented as a sequential game comprised of two stages, where each stage is a simultaneous game played by the facility and the client players, respectively. Facility players aim to maximize the expected attracted purchasing power. Clients aim to minimize the expected congestion they encounter, where we assume that the congestion at each facility is proportional to the total purchasing power of clients patronizing the facility. In contrast to recent publications on similar games, we assume that clients cannot split up their purchasing power over multiple facilities. We demonstrate the existence of instances of this game that admit no subgame perfect equilibria and show that determining the existence of such equilibria is NP-hard. Additionally, we establish sufficient conditions for the existence of such equilibria, notably the condition of all clients possessing equal purchasing power. For this unweighted game, we present an algorithm to compute subgame perfect equilibria and analyze their efficiency by providing bounds on the price of anarchy and stability. Lastly, we examine the existence of approximate subgame perfect equilibria.
Item Type:Essay (Master)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:31 mathematics
Programme:Applied Mathematics MSc (60348)
Link to this item:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page