January 15, 2021, Zoom

Congestion games provide us with a general model that is expressive enough to capture a number of otherwise unrelated applications - including routing, network design, and the migration of species. Yet they are structured enough to permit a useful theory. A congestion game consists of a ground set of resources, and each strategy of a player is to select a subset of them (e.g., a path in a network). Each resource has a univariate cost function that depends on the load induced by the players that use it, and each player aspires to minimize the sum of the resources’ costs in its chosen strategy. In this talk we focus on the fundamental model of weighted congestion games, where each player has a weight and the load of a resource depends on the sum of the weights of the players that use it. In this talk, we will - review results on the efficiency of the resulting Nash equilibria, - quantify how much we have to relax the concept of pure Nash equilibria to guarantee their existence, - discuss complexity questions with respect to the existence and computation of Nash equilibria. The bulk of the talk will be based on the following papers: - https://arxiv.org/abs/2002.07466 (ICALP 2020) - https://arxiv.org/abs/1802.09952 (ICALP 2018)

Martin is Head of the Economics and Computation Research Group and Deputy Head of the Computer Science Department at the University of Liverpool. Before joining Liverpool in 2009, Martin completed his PhD at the University of Paderborn in 2006 and a postoctoral fellowship at the International Computer Science Institute (ICSI) in Berkeley under the supervision of Richard Karp.

Martin’s expertise lies in the area of Algorithmic Game theory, which is at intersection of Theoretical Computer Science and Economic Game Theory. His research shaped the theory of congestion games, a fundamental model for selfish behaviour in networks. In particular, Martin is well known for his contributions on quantifying the inefficiency of Nash equilibria in congestion games.
Martin applied game theoretic concepts also to other fields. E.g., he contributed to the design of improved approximation algorithms for scheduling problems, general covering problems, network design problems, and reachability problems.