Abstract
We study the speed of convergence to approximate solutions in iterative competitive games. We also investigate the value of Nash equilibria as a measure of the cost of the lack of coordination in such games. Our basic model uses the underlying best response graph induced by the selfish behavior of the players. In this model, we study the value of the social function after multiple rounds of best response behavior by the players. This work therefore deviates from other attempts to study the outcome of selfish behavior of players in non-cooperative games in that we dispense with the insistence upon only evaluating Nash equilibria. A detailed theoretical and practical justification for this approach is presented. We consider non-cooperative games with a submodular social utility function; in particular, we focus upon the class of valid-utility games introduced in [13]. Special cases include basic-utility games and market sharing games which we examine in depth. On the positive side we show that for basic-utility games we obtain extremely quick convergence. After just one round of iterative selfish behavior we are guaranteed to obtain a solution with social value at least \(\frac13\) that of optimal. For n-player valid-utility games, in general, after one round we obtain a \(\frac{1}{2n}\)-approximate solution. For market sharing games we prove that one round of selfish response behavior of players gives \(\Omega({1\over \ln n})\)-approximate solutions and this bound is almost tight. On the negative side we present an example to show that even in games in which every Nash equilibrium has high social value (at least half of optimal), iterative selfish behavior may “converge” to a set of extremely poor solutions (each being at least a factor n from optimal). In such games Nash equilibria may severely underestimate the cost of the lack of coordination in a game, and we discuss the implications of this.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Brucker, P., Hurink, J., Werner, F.: Improving local search heuristics for some scheduling problems. Discrete Applied Mathematics 72, 47–69 (1997)
Even-dar, E., Kesselman, A., Mansour, Y.: Convergence time to Nash equilibria. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, Springer, Heidelberg (2003)
Fabrikant, A., Papadimitriou, C., Talwar, K.: On the complexity of pure equilibria. In: STOC (2004)
Goemans, M., Li, L., Mirrokni, V.S., Thottan, M.: Market sharing games applied to content distribution in ad-hoc networks. In: MOBIHOC (2004)
Milchtaich, I.: Congestion games with player-specific payoff functions. Games and Economic Behavior 13(1), 111–124 (1996)
Monderer, D., Shapley, L.: Potential games. Games and Economic Behavior 14(1), 124–143 (1996)
Nisan, N., Ronen, A.: Algorithmic mechanism design. Games and Economic Behavior 35(1-2), 166–196 (2001)
Papadimitriou, C.: Algorithms, games, and the internet. In: STOC 2001 (2001)
Rosenthal, R.W.: A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory 2, 65–67 (1973)
Roughgarden, T., Tardos, E.: Bounding the inefficiency of equilibria in nonatomic congestion games. Games and Economic Behavior 47(2), 389–403 (2004)
Roughgarden, T., Tardos, E.: How bad is selfish routing? J. ACM 49(2), 236–259 (2002)
Schuurman, P., Vredeveld, T.: Performance guarantees of local search for multiprocessor scheduling. In: IPCO (2001)
Vetta, A.: Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions. In: FOCS (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mirrokni, V.S., Vetta, A. (2004). Convergence Issues in Competitive Games. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. RANDOM APPROX 2004 2004. Lecture Notes in Computer Science, vol 3122. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27821-4_17
Download citation
DOI: https://doi.org/10.1007/978-3-540-27821-4_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22894-3
Online ISBN: 978-3-540-27821-4
eBook Packages: Springer Book Archive