## Achieving Good Nash Equilibrium by Temporal Addition of Dummy Players

### Ofek Dadush, Tami Tamir

DOI: http://dx.doi.org/10.15439/2021F112

Citation: Proceedings of the 16th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 25, pages 163–172 (2021)

Abstract. We consider cost-sharing games in which resources' costs are fairly shared by their users. The total players' cost in a Nash Equilibrium profile may be significantly higher than the social optimum. We compare and analyze several methods to lead the players to a good Nash Equilibrium by temporal addition of dummy players. The dummies create artificial load on some resources, that encourage other players to change their strategies.

### References

- E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler, and T. Roughgarden. The price of stability for network design with fair cost allocation. SIAM Journal on Computing, 38(4):1602–1623, 2008.
- V. Bilò and C. Vinci. On the impact of singleton strategies in congestion games. In Proc. 25th Annual European Symposium on Algorithms, pages 17:1–17:14, 2017.
- I. Caragiannis, M. Flammini, C. Kaklamanis, P. Kanellopoulos, and L. Moscardelli. Tight bounds for selfish and greedy load balancing. Algorithmica, 61(3):606–637, 2011.
- E. Even-Dar and Y. Mansour. Fast Convergence of Selfish Rerouting. In Proc. of SODA, pp. 772–781, 2005.
- M. Feldman, Y. Snappir, and T. Tamir. The efficiency of best-response dynamics. In The 10th International Symposium on Algorithmic Game Theory (SAGT), 2017.
- A. Fanelli, M. Flammini, and L. Moscardelli. Stackelberg strategies for network design games. In Proc. of International Workshop on Internet and Network Economics (WINE). pp. 222 –âĂŞ233, 2010.
- D. Fotakis. Stackelberg strategies for atomic congestion games. Theory of Computing Systems, 47(1):218–249, 2010.
- T. Harks and M. Klimm. On the existence of pure nash equilibria in weighted congestion games. Math. Oper. Res., 37(3):419–436, 2012.
- S. Ieong, R. McGrew, E. Nudelman, Y. Shoham, and Q. Sun. Fast and compact: A simple class of congestion games. In Proceedings of the 20th National Conference on Artificial Intelligence - Volume 2, AAAI’05, 2005.
- Y. A. Korilis, A. A. Lazar, and A. Orda. Achieving network optima using stackelberg routing strategies. IEEE/ACM Trans. Netw., 5(1):161–173, 1997.
- E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. Computer Science Review, 3(2):65–69, 2009.
- W. Krichene, J. D. Reilly, S. Amin, and A. M. Bayen. Stackelberg routing on parallel networks with horizontal queues. IEEE Transactions on Automatic Control, 59(3):714–727, 2014.
- I. Milchtaich. Congestion games with player-specific payoff functions. Games and Economic Behavior, 13(1):111 – 124, 1996.
- D. Monderer and L. S. Shapley. Potential Games. Games and Economic Behavior, 14: 124–143, 1996.
- C. H. Papadimitriou. Algorithms, games, and the internet. In Proc. 33rd ACM Symp. on Theory of Computing, pages 749–753, 2001.
- R. W. Rosenthal. A class of games possessing pure-strategy nash equilibria. International Journal of Game Theory, 2:65–67, 1973.
- T. Roughgarden. Stackelberg scheduling strategies. SIAM Journal on Computing, 33(2):332–350, 2004.
- T. Tamir. The power of one evil secret agent. Theoretical Computer Science, 839:1–12, 2020.
- B. Vöcking. Algorithmic Game Theory, chapter 20: Selfish Load Balancing. Cambridge University Press, 2007.