Greediness and equilibrium in congestion games

DOI10.1016/J.ECONLET.2013.10.005MaRDI QIDQ2453056zbMATH OpenOpenAlexFDO

Authors Sergey Kuniavsky, Rann Smorodinsky

Publication date 6 June 2014

Published in Economics Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.6156

zbMATH Keywords

congestion gamesequilibriumgreediness

Mathematics Subject Classification ID

Noncooperative games (91A10) Games involving graphs (91A43)

Abstract: Rosenthal (1973) introduced the class of congestion games and proved that they always possess a Nash equilibrium in pure strategies. Fotakis et al. (2005) introduce the notion of a greedy strategy tuple, where players sequentially and irrevocably choose a strategy that is a best response to the choice of strategies by former players. Whereas the former solution concept is driven by strong assumptions on the rationality of the players and the common knowledge thereof, the latter assumes very little rationality on the players' behavior. From Fotakis cite{fotakis10} it follows that for Tree Representable congestion Games greedy behavior leads to a NE. In this paper we obtain necessary and sufficient conditions for the equivalence of these two solution concepts. Such equivalence enhances the viability of these concepts as realistic outcomes of the environment. The conditions for such equivalence to emerge for monotone symmetric games is that the strategy set has a tree-form, or equivalently is a `extension-parallel graph'.

Recommendations

• Congestion games with player-specific payoff functions
• Games with congestion-averse utilities
• Strong equilibrium in congestion games
• Congestion games revisited
• CONGESTION GAMES AND POTENTIALS RECONSIDERED

Cites work

• A class of games possessing pure-strategy Nash equilibria
• Approximation and Online Algorithms
• Congestion games with linearly independent paths: convergence time and price of anarchy
• Epistemic Conditions for Nash Equilibrium
• Network structure and strong equilibrium in route selection games.
• Network topology and the efficiency of equilibrium
• On the impact of combinatorial structure on congestion games
• Potential games
• The complexity of pure Nash equilibria

Cited in

(5)

• Congestion games viewed from M-convexity
• Internalization of social cost in congestion games
• Repeated congestion games with bounded rationality
• Maximizing social welfare in congestion games via redistribution
• Mechanisms for (mis)allocating scientific credit

This page was built for publication: Greediness and equilibrium in congestion games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2453056)