Congestion games viewed from M-convexity.pdfVIP

Operations Research Letters 43 (2015) 329–333 Contents lists available at ScienceDirect Operations Research Letters journal homepage: /locate/orl Congestion games viewed from M-convexity? Satoru Fujishige a,?, Michel Goemans b, Tobias Harks c, Britta Peis d, Rico Zenklusen e a Research Institute for Mathematical Sciences, Kyoto University, Kyoto 606-8502, Japan b Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA c School of Business and Economics, Department of Quantitative Economics, Maastricht University, PO Box 616 6200 MD, The Netherlands d School of Business and Economics, RWTH Aachen, Kackertstr. 7, 52072 Aachen, Germany e Institute for Operations Research, Department of Mathematics, ETH Zurich, HG G 21.3, R?mistrasse 101, 8092 Zurich, Switzerland article info Article history: Received 27 January 2015 Received in revised form 3 April 2015 Accepted 3 April 2015 Available online 17 April 2015 Keywords: Congestion games Discrete convexity Best-response dynamics M-convex function Discrete convexity abstract 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 Elsevier B.V. All rights reserved. 1. Introduction Congestion games (or finite potential games) have extensively been studied in the literature (e.g., [1,8,11,12,14]). An interesting special class of congestion games on networks, which is called congestion games on extension-parallel networks, is considered by Holzman and Law-yone [12] (see also [6,14,19]). Fotakis [8] showed a fast convergence behavior of t