Two-Stage Facility Location Games with Strategic Clients and Facilities

Simon Krogmann, Pascal Lenzner, Louise Molitor, Alexander Skopalik

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

8 Downloads (Pure)

Abstract

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-strategic clients that simply select the closest opened facility. In our model, every facility location has a set of attracted clients and each client has a set of shopping locations and a weight that corresponds to her spending capacity. Facility agents selfishly select a location for opening their facility to maximize the attracted total spending capacity, whereas clients strategically decide how to distribute their spending capacity among the opened facilities in their shopping range. We focus on a natural client behavior similar to classical load balancing: our selfish clients aim for a distribution that minimizes their maximum waiting times for getting serviced, where a facility's waiting time corresponds to its total attracted client weight. We show that subgame perfect equilibria exist and give almost tight constant bounds on the Price of Anarchy and the Price of Stability, which even hold for a broader class of games with arbitrary client behavior. Since facilities and clients influence each other, it is crucial for the facilities to anticipate the selfish clients' behavior when selecting their location. For this, we provide an efficient algorithm that also implies an efficient check for equilibrium. Finally, we show that computing a socially optimal facility placement is NP-hard and that this result holds for all feasible client weight distributions.

Original languageEnglish
Title of host publicationProceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI 2021)
Subtitle of host publicationMontreal, 19-27 August 2021
EditorsZhi-Hua Zhou
PublisherInternational Joint Conferences on Artificial Intelligence
Pages292-298
Number of pages7
ISBN (Electronic)978-0-9992411-9-6
DOIs
Publication statusPublished - 2021
Event30th International Joint Conference on Artificial Intelligence, IJCAI 2021 - Virtual, Online, Canada
Duration: 19 Aug 202127 Aug 2021
Conference number: 30

Publication series

NameIJCAI International Joint Conference on Artificial Intelligence
ISSN (Print)1045-0823

Conference

Conference30th International Joint Conference on Artificial Intelligence, IJCAI 2021
Abbreviated titleIJCAI 2021
Country/TerritoryCanada
CityVirtual, Online
Period19/08/2127/08/21

Fingerprint

Dive into the research topics of 'Two-Stage Facility Location Games with Strategic Clients and Facilities'. Together they form a unique fingerprint.

Cite this