  


Totally Unimodular Congestion Games
Alberto Del Pia (delpiawisc.edu) Abstract: We investigate a new class of congestion games, called Totally Unimodular Congestion Games, in which the strategies of each player are expressed as binary vectors lying in a polyhedron defined using a totally unimodular constraint matrix and an integer righthand side. We study both the symmetric and the asymmetric variants of the game. In the symmetric variant, all players have the same strategy set, i.e. the same constraint matrix and righthand side. Network congestion games are an example of 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 PLScomplete. We give a strongly polynomialtime 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' strategy sets 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 the asymmetric variant is PLScomplete. Keywords: pure Nash equilibrium, total unimodularity, congestion game Category 1: Combinatorial Optimization (Polyhedra ) Category 2: Other Topics (Game Theory ) Category 3: Integer Programming (01 Programming ) Citation: University of WisconsinMadison, November 2015 Download: [PDF] Entry Submitted: 11/09/2015 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  