Theory Seminar: Totally Unimodular Congestion Games

Friday, February 5, 2016 - 2:00pm
CS 4310

Speaker Name: 

Carla Michini

Speaker Institution: 

UW-Madison (WID)

Cookies: 

Yes

Cookies Location: 

CS 4310

Description: 

We investigate a new class of congestion games, called Totally Unimodular Congestion Games, where the players' strategies are binary vectors in a polyhedron that is defined using a totally unimodular constraint matrix and an integer right-hand side. We study both the symmetric and the asymmetric variants of the game. Network congestion games belong to this class. Fabrikant et al. proved that a pure Nash equilibrium of symmetric network congestion games can be found in strongly polynomial time, while the asymmetric network congestion games are PLS-complete. We give a strongly polynomial-time algorithm to find a pure Nash equilibrium of any symmetric totally unimodular congestion game. We also identify four totally unimodular congestion games, where the players' strategies are matchings, vertex covers, edge covers and stable sets of a given bipartite graph. For these games we derive specialized combinatorial algorithms to find a pure Nash equilibrium in the symmetric variant, and show that the asymmetric variant is PLS-complete. This is a joint work with Alberto del Pia and Michael Ferris.

Speaker's bio: Carla Michini received a PhD in Optimization in 2012 from University of Rome La Sapienza. In 2011, she was a visiting scholar at CMU Pittsburgh, and from 2012 to 2014 she was a postdoctoral researcher at the Institute for Operations Research at ETH Zürich. Currently, she is a postdoctoral researcher in the Optimization group at the Wisconsin Institute for Discovery of UW-Madison.

Carla’s research focuses on different topics in combinatorial optimization, polyhedral combinatorics and integer programming, and spans both theoretical and algorithmic issues. She is particularly concerned with the study of structural properties of combinatorial problems and with their computational complexity.