Congestion games viewed from M-convexity

DOI10.1016/j.orl.2015.04.002zbMath1408.91042OpenAlexW2171358488MaRDI QIDQ1785371

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

Publication date: 28 September 2018

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2433/197956

zbMATH Keywords

congestion gamesbest-response dynamicsdiscrete convexityM-convex function

Mathematics Subject Classification ID

Games involving graphs (91A43) Combinatorial optimization (90C27)

Related Items

A common generalization of budget games and congestion games, Computation and efficiency of potential function minimizers of combinatorial congestion games, Simpler exchange axioms for M-concave functions on generalized polymatroids, Generalizations of weighted matroid congestion games: pure Nash equilibrium, sensitivity analysis, and discrete convex function

Cites Work

• Unnamed Item
• Unnamed Item
• Convexity and Steinitz's exchange property
• Valuated matroids: A new look at the greedy algorithm
• Congestion games with linearly independent paths: convergence time and price of anarchy
• Efficient graph topologies in network routing games
• Valuated matroids
• Strong equilibrium in congestion games
• Minimization of an M-convex function
• Network structure and strong equilibrium in route selection games.
• Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem.
• \(M\)-convex functions and tree metrics
• Applications of discrete convex analysis to mathematical economics
• Coordinatewise domain scaling algorithm for M-convex function minimization
• Potential games
• Greediness and equilibrium in congestion games
• A class of games possessing pure-strategy Nash equilibria
• Submodular functions and optimization.
• On the impact of combinatorial structure on congestion games
• DISCRETE CONCAVITY FOR POTENTIAL GAMES
• Discrete Convex Analysis
• Topological Uniqueness of the Nash Equilibrium for Selfish Routing with Atomic Users
• GROSS SUBSTITUTES CONDITION AND DISCRETE CONCAVITY FOR MULTI-UNIT VALUATIONS: A SURVEY
• Topological Conditions for Uniqueness of Equilibrium in Networks
• Note on Multimodularity and L-Convexity
• Discrete convexity and equilibria in economies with indivisible goods and money