Journal Article Congestion games viewed from M-convexity

Fujishige, Satoru  ,  Goemans, Michel  ,  Harks, Tobias  ,  Peis, Britta  ,  Zenklusen, Rico

43 ( 3 )  , pp.329 - 333 , 2015-04-17 , Elsevier B.V.
Presented at the Aussois Workshop on Combinatorial Optimization, January 5–9, 2015.
relation url = preprint version
Congestion games have extensively been studied till recently. It is shown by Fotakis (2010) that for every congestion game on an extension-parallel network, any best-response sequence reaches a pure Nash equilibrium of the game in n steps, where n is the number of players. We show that the fast convergence of best-response sequences results from M-convexity (of Murota (1996)) of the potential function associated with the game. We also give a characterization of M-convex functions in terms of greedy algorithms.

Number of accesses :  

Other information