Faculty Candidate Talk: Beyond Combinatorial Optimization: Polyhedral Methods for Game Theory

Monday, March 27, 2017 -
4:00pm to 5:00pm
CS 1240

Speaker Name: 

Carla Michini

Speaker Institution: 

UW-Madison, Wisconsin Institute for Discovery (WID)

Cookies: 

Yes

Cookies Location: 

CS 1240

Description: 

Combinatorial optimization is a well-studied field with many applications to real-world problems. Many classical results and efficient algorithms for combinatorial optimization are based on polyhedral methods. I will show how to extend the polyhedral approach to the context of games and equilibrium problems, by looking at the impact of total unimodularity, a property that plays a crucial role in integer programming. I will define a new class of games, called Totally Unimodular (TU) Congestion Games, where the players' strategies are binary vectors inside polyhedra with TU constraint matrices. In the symmetric case, I will show a strongly polynomial-time algorithm to (i) find a pure Nash equilibrium, and (ii) compute a socially optimal state. In the asymmetric case, I will state some negative complexity results. Our algorithm subsumes the algorithm of Fabrikant et al. for symmetric network congestion games, and it can be adapted also to (symmetric and asymmetric) matroid congestion games, showing to be a unifying tool for different problems in algorithmic game theory. I will conclude my talk by describing my future research directions.