Graphical congestion games with linear latencies

ABSTRACT

We introduce a new general framework for the analysis of non cooperative games with limited social knowledge. Such an incomplete knowledge is modeled by means of a social graph G in which nodes represent players and there is an edge from i to j if i knows j, with the assumption that the payoff of each player is affected only by the strategies of the adjacent ones. In particular, we consider congestion games with linear latency functions in which each player is aware only of a subset of all the other ones. We first give a complete characterization of the games possessing pure Nash equilibria, and then investigate the impact of the limited knowledge of the players on the performance of the game, in terms of price of anarchy and price of stability.

REFERENCES

• 1: R. Beier, A. Czumaj, P. Krysta, and B. Vocking. Computing Equilibria for Congestion Games with (Im)perfect Information. In Proc. of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM Press, pp. 746--755, 2004.
• 2: G. Christodoulou and E. Koutsoupias. The Price of Anarchy of Finite Congestion Games. In Proc. of the 37th Annual ACM Symposium on Theory of Computing (STOC), ACM Press, pp. 67--73, 2005.
• 3: G. Christodoulou and E. Koutsoupias. On the Price of Anarchy and Stability of Correlated Equilibria of Linear Congestion Games. In Proc. of the 13th Annual European Symposium on Algorithms (ESA), LNCS 3669, Springer, pp. 59--70, 2005.
• 4: A. Fabrikant, C. H. Papadimitriou, and K. Talwar. The Complexity of Pure Nash Equilibria. In Proc. of the 36th Annual ACM Symposium on Theory of Computing (STOC), ACM Press, pp. 604--612, 2004.
• 5: M. Gairing, B. Monien, and K. Tiemann. Selfish Routing with Incomplete Information. In Proc. of the 17th Annual ACM Symposium on Parallel Algorithms (SPAA), ACM Press, pp. 203--212, 2005.
• 6: J. C. Harsanyi. Games with Incomplete Information Played by Bayesian Players, I, II, III. Management Science, 14:159--182, 320--332, 468--502, 1967.
• 7: Elias Koutsoupias, Panagiota N. Panagopoulou and Paul G. Spirakis. Selfish Load Balancing Under Partial Knowledge In Proc. of 32nd International Symposium on Mathematical Foundations of Computer Science (MFCS), LNCS 4708, 609--620, 2007.
• 8: M. J. Kearns, M. L. Littman, and S. P. Singh. Graphical Models for Game Theory. In Proc. of the 17th Conference in Uncertainty in Artificial Intelligence (UAI), pp. 253--260, 2001.
• 9: Kleinberg, J. M. The small-world phenomenon: an algorithm perspective. In Proc. of the 32nd ACM Symposium on Theory of Computing (STOC) (2000), pp. 163--170.
• 10: R. W. Rosenthal. A Class of Games Possessing Pure-Strategy Nash Equilibria. International Journal of Game Theory, 2:65--67, 1973.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.0 GENERAL

General Terms:
Algorithms, Economics, Theory

Keywords:
algorithmic game theory, congestion games, nash equilibrium, price of anarchy, price of stability, social knowledge