Optimization Online


Totally Unimodular Congestion Games

Alberto Del Pia (delpia***at***wisc.edu)
Michael Ferris (ferris***at***cs.wisc.edu)
Carla Michini (michini***at***wisc.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 right-hand 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 right-hand 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 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' 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 PLS-complete.

Keywords: pure Nash equilibrium, total unimodularity, congestion game

Category 1: Combinatorial Optimization (Polyhedra )

Category 2: Other Topics (Game Theory )

Category 3: Integer Programming (0-1 Programming )

Citation: University of Wisconsin-Madison, November 2015

Download: [PDF]

Entry Submitted: 11/09/2015
Entry Accepted: 11/09/2015
Entry Last Modified: 10/05/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society