Congestion Games: The Minimum Tollbooth Problem and Games with Uncertainty

2^nd December 2020, 13:00
Julian Nickerl
Ulm University

Abstract

In congestion games, players have to share a set of resources to achieve personal goals. Cars in a road network are a typical intuitive example. While everybody has a different origin and destination, they have to share the same roads, creating congestion on the way. To reduce stress on the network it would be beneficial if some participants of the network diverted to less favorable routes. Assuming selfish behavior, there is little incentive to do so, however. In the tollbooth problem tolls can be levied for the use of a road to create a financial incentive for such a diversion. The goal of the minimum tollbooth problem is to additionally minimize the tolled roads. In a separate branch of research on congestion games the reliability of the resources is in question, assuming that each is available only with a given probability. Even basic properties have to be reconsidered, in particular the definition of a strategy requires an extension.
In this talk, I present recent algorithmic and complexity theoretic research in both fields. In particular, I consider the minimum tollbooth problem in games with finite player and strategy sets, outlining a hardness result in the general case and a polynomial-time algorithm on series-parallel networks. I introduce a new model of games with uncertainty and demonstrate its completeness for a new complexity class based on PLS.

Additional Materials

• https://arxiv.org/pdf/1906.09865.pdf