Thorsten Theobald -Technische Universität Berlin

Games of fixed rank - a hierarchy of bimatrix games

Abstract: Bimatrix games are the very basic model of game theory and serve to study strategic interactions. By John Nash's results it is well known that these games always contain an equilibrium ("Nash equilibrium").

However, beyong this results both the geometry ("how many Nash equilibria can there be?") and the algorithmics ("can Nash equilibria be computed efficiently?") are widely open questions. These questions are well understood for the subclass of zero-sum games.

In this talk we start by reviewing the discrete geometry and the algorithmics of bimatrix games, and then discuss a hierarchy of bimatrix games which is imposed by a natural rank condition. (Based on joint work with Ravi Kannan.)

Colloquium - 16:00

Leon Peeters -ETH Zürich

The Computational Complexity of Delay Management

Abstract: Delay management considers the problem of deciding when to guarantee connections from a delayed feeder train to a connecting train in a passenger railway system. Such a decision to guarantee a connection has a twofold impact. On the one hand, passengers in the delayed feeder train can still catch their connection, and do not have to wait for the next train. On the other hand, passengers in the connecting train now face a small delay, and may thus miss subsequent connections. The latter implies that the delay can propagate through the network. The trade-off between these two effects leads to the natural objective of minimizing the overall discomfort faced by the passengers. This deceptively simple sounding problem is surprisingly complicated, mainly because a local optimization is far from sufficient.

We model the railway network as a directed acyclic graph, where edges represent trains, and weighted paths represent passenger flows. Given initial delays of some of the passenger paths, the goal is to decide which edges (trains) wait for delayed passenger paths, such that the sum of all passenger delays is minimized. The focus is on the case of binary source delays, where all non-zero source delays are of equal size.

For this model, I will discuss the boundary between NP-completeness and polynomial solvability for various natural problem parameters. These parameters include the maximum number of passenger transfers, the railway network topology, and the capability of trains to reduce delays. For example, the delay management problem is strongly NP-complete when some passengers transfer three times and trains cannot catch up on their delay, already on a railway network with a series-parallel topology. On the other hand, the same situation with passengers transferring at most twice is polynomially solvable.