Congestion games viewed from M-convexity

作者：Fujishige Satoru^*; Goemans Michel; Harks Tobias; Peis Britta; Zenklusen Rico

来源：Operations Research Letters, 2015, 43(3): 329-333.

DOI：10.1016/j.orl.2015.04.002

• Congestion games
• Discrete convexity
• Best-response dynamics
• M-convex function
• Discrete convexity

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.

• 出版日期2015-5