Congestion games with failures

DOI10.1016/J.DAM.2011.01.019MaRDI QIDQ642974zbMATH OpenOpenAlexFDO

Authors Michal Penn, Maria Polukarov, Moshe Tennenholtz

Publication date 27 October 2011

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2011.01.019

algorithms congestion games price of anarchy pure strategy Nash equilibrium resource failures semi-strong Nash equilibrium

Mathematics Subject Classification ID

Queues and service in operations research (90B22) Noncooperative games (91A10) Other game-theoretic models (91A40)

Review text

This paper introduces a new class of games, the so-called congestion games with failures (CGFs). The class of congestion games was first introduced by \textit{R. W. Rosenthal} [Int. J. Game Theory 2, 65--67 (1973; Zbl 0259.90059)]. Congestion games are noncooperative games and they have been used to model traffic behavior in road and communication networks, competition among firms for production processes, or migration of animals between different habitats and receive a lot of attention in the recent computer science and electronic commerce communities. The notion of failures is widely used in the field of distributed systems. The issue of failures in game-theoretic setting is extensively discussed by \textit{N. Linial} [``Game-theoretic aspects of computing, in: Handbook of game theory with economic applications. Vol. 2. Amsterdam: Elsevier. Handbooks in Economics. 1339--1395 (1994; Zbl 0925.90092)]. In CFGs, players share a common set of resources (service providers) and each service provider (SP) may fail with some known probability that may be constant or depend on the congestion on the resource. For reliability reasons, a player may choose a subset of the SPs in order to perform his task. The cost of a player for utilizing any SP is a nondecreasing function of the total number of players using this SP. A main feature of this setting is that the cost for a player for successful completion of his task is the minimum of the costs of his successful attempts. The dis-utility to a player depends not only on the number of players using the same SP, but also on the identity of the player in question. They prove that CFG always possess a pure strategy Nash equilibrium, although CGFs do not, in general, admit a potential function, and thus are not isomorphic to congestion games [cf. \textit{D. Monderer} and \textit{L. S. Shapley}, Games Econ. Behav. 14, No. 1, 124--143 (1996; Zbl 0862.90137)]. A potential function is a real-valued function over the set of pure strategy profiles, with the property that the gain or loss of a player shifting to another strategy while keeping the other players' strategies unchanged is equal to the corresponding increment of the potential function. In fact, they show that any sequence of best replies always converges to a Nash equilibrium profile, regardless of the initial point at which the improvement process has started. This property is termed the finite best response property [cf. \textit{I. Milchtaich}, Games Econ. Behav. 13, No. 1, 111--124 (1996; Zbl 0848.90131)]. They provide an efficient procedure for computing a pure strategy equilibrium (with time complexity \(O(mn\log n))\). Strongly coalition-proof (or, semi-strong) Nash equilibrium is a strategy profile for which there are no profitable coalition deviations which are robust against further individual deviations [cf. \textit{P. Milgrom} and \textit{J. Roberts}, Games Econ. Behav. 17, No. 1, 113--128 (1997; Zbl 0886.90189)]. They show the existence of semi-strong Nash equilibria in the class of CGFs. For the subclass of symmetric CFGs (the parameters of the game do not depend on service provider or player identity), they show that all SPs have the same congestion at Nash equilibrium and they give a constructive characterization of best and worst equilibria (strategy profiles that minimize and maximize, respectively, the social disutility over the set of equilibrium strategies). They show that in CGFs even the best possible ratio between equilibria and optimum disutilities depends on the parameters of the game and cannot be bounded by a constant value. As a result, the so-called price of anarchy i.e. the worst possible ratio between equilibrium and optimum disutilities is also unbounded. In a CGF, players strive to minimize the delay caused by using a set of alternative resources. In the alternative model of congestion games with load-dependent failures [cf. \textit{M. Penn, M. Polukarov} and \textit{M. Tennenholtz}, Games Econ. Behav. 67, No. 1, 156--173 (2009; Zbl 1173.91302)], the objective of a player is to maximize the difference between the expected benefit from the successful task completion and the total cost of the utilized resources. The current paper seems to offer a promising path of future research.

Recommendations

Cites work

Cited in

(13)

This page was built for publication: Congestion games with failures

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