Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
 

Competitive Facility Location in Congested Networks

Master Project - Summer 2024

Motivation

In classical facility location, a central authority places facilities, e.g., hospitals to serve a set of clients optimally. In practice, however, these are usually placed by selfish companies that want to make a profit. This produces inefficiencies, which we want to investigate. So far, we built a model of competitive facility location [1] which models clients that want to avoid congestion (i.e., waiting times) at their chosen facility. This model, however, completely ignores the traveling time to the facility, which of course also depends on the congestion of the used links. Therefore, we want to integrate our facility location model with the selfish routing game by Roughgarden and Tardos [2], which models traffic participants optimizing their traveling times in a congested network. This might result in a model similar to the one visualized below.

The Goal of this Project

The goal of the project is to build a realistic model for competitive facility location on congested networks. We have a rough starting point but new ideas are very welcome. Then, we want to investigate the behavior of this model, answering questions like:

1. Do stable states exist?

2. Are there efficient algorithms for computing strategies and stable states?

3. What is the impact of selfish actors?

 

What we expect from you.

You should bring the curiosity and willingness to delve into an interesting research topic in Algorithmic Game Theory and Graph Algorithms.

What you can expect from us.

We will gently introduce you to the field and accompany you all along this interesting journey. This will be a team effort, and we aim to publish our results at a renowned international conference.

[1]Simon Krogmann, Pascal Lenzner, Louise Molitor, and Alexander Skopalik. “Two-Stage Facility Location Games with Strategic Clients and Facilities”. In: IJCAI. 2021. DOI: 10.24963/ijcai.2021/41.
[2]Tim Roughgarden and Éva Tardos. “How bad is selfish routing?” In: Journal of the ACM (JACM) (2002). DOI: 10.1145/506147.506153.

 

Project Team

The Master Project is organized by the Algorithm Engineering Group. The following group members are participating:

Supervisor

Chair for Algorithm Engineering
Hasso Plattner Institute

Office: K-2.15
E-Mail: Friedrich(at)hpi.de

Supervisor

Chair for Algorithm Engineering
Hasso Plattner Institute

Office: K-2.17
E-Mail: Pascal.Lenzner(at)hpi.de

Supervisor

Chair for Algorithm Engineering
Hasso Plattner Institute

Office: K-2.09/10
E-Mail: Simon.Krogmann(at)hpi.de

Supervisor

Chair for Algorithm Engineering
Hasso Plattner Institute

Office: K-2.09/10
E-Mail: Paraskevi.Machaira(at)hpi.de