UnRAVeL Survey Lecture: Britta Peis: Sensitivity Analysis for Submodular Function Optimization with Applications in Algorithmic Game Theory

Thursday, June 10, 2021, 4:30pm

Speaker: Britta Peis



We consider integral-splittable congestion games. Such games can be used to model situations where selfishly acting users send traffic in integral units through a transport- or communication network, and where the travel times on the links depend on the congestion or load  induced by the joint strategy choices of the agents.

In 1973, Rosenthal proved that the existence of equilibria  cannot be guaranteed in general for this class of games. In this lecture, we show that equilibria can be guaranteed, and even computed,  if (and only if) the strategy spaces and the delay functions obey certain submodularity and discrete convexity properties.

In the first part of the lecture, we  will start with a gentle introduction into the world of submodular functions, polymatroids, and discrete convexity. 

In the second part, we will derive a sensitivity result for minimising a parameter-dependent separable discrete convex function over a polymatroid base polytope. 

Finally, in the third part, we use  this sensitivity result to show that a certain best-response dynamics converges to an equilibrium in integer-splittable polymatroid congestion games.


The talks of the UnRAVeL survey lecture 2021 will be given via Zoom every Thursday from 16:30 to 18:00:


Meeting ID: 960 4371 5437

Passcode: 039217