Achieving Good Nash Equilibrium by Temporal Addition of Dummy Players

• Autorzy: Dadush Ofek , Tamir Tami

Identyfikatory

DOI

10.15439/2021F112

• Konferencja: Federated Conference on Computer Science and Information Systems (16 ; 02-05.09.2021 ; online)
• Języki publikacji: EN

Abstrakty

EN

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. We show that it is NP-hard to calculate an optimal strategy for the dummy players. We then focus on symmetric singleton games for which we suggest several heuristics for the problem. We analyze their performance distinguishing between several classes of instances and several performance measures.

Słowa kluczowe

EN

computer science; cost; game; Nash equilibrium

PL

informatyka; koszt; gra; równowaga Nasha

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2021
• Tom: Vol. 25
• Strony: 163--172
• Opis fizyczny: Bibliogr. 19 poz., rys., wz., tab., wykr.

Twórcy

autor

Dadush Ofek

• School of Computer Science The Interdisciplinary Center Herzliya, Israel

autor

Tamir Tami

• School of Computer Science The Interdisciplinary Center Herzliya, Israel

Bibliografia

• 1. 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.
• 2. 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.
• 3. 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.
• 4. E. Even-Dar and Y. Mansour. Fast Convergence of Selfish Rerouting. In Proc. of SODA, pp. 772–781, 2005.
• 5. M. Feldman, Y. Snappir, and T. Tamir. The efficiency of best-response dynamics. In The 10th International Symposium on Algorithmic Game Theory (SAGT), 2017.
• 6. 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.
• 7. D. Fotakis. Stackelberg strategies for atomic congestion games. Theory of Computing Systems, 47(1):218–249, 2010.
• 8. T. Harks and M. Klimm. On the existence of pure nash equilibria in weighted congestion games. Math. Oper. Res., 37(3):419–436, 2012.
• 9. 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.
• 10. 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.
• 11. E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. Computer Science Review, 3(2):65–69, 2009.
• 12. 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.
• 13. I. Milchtaich. Congestion games with player-specific payoff functions. Games and Economic Behavior, 13(1):111 – 124, 1996.
• 14. D. Monderer and L. S. Shapley. Potential Games. Games and Economic Behavior, 14: 124–143, 1996.
• 15. C. H. Papadimitriou. Algorithms, games, and the internet. In Proc. 33rd ACM Symp. on Theory of Computing, pages 749–753, 2001.
• 16. R. W. Rosenthal. A class of games possessing pure-strategy nash equilibria. International Journal of Game Theory, 2:65–67, 1973.
• 17. T. Roughgarden. Stackelberg scheduling strategies. SIAM Journal on Computing, 33(2):332–350, 2004.
• 18. T. Tamir. The power of one evil secret agent. Theoretical Computer Science, 839:1–12, 2020.
• 19. B. Vöcking. Algorithmic Game Theory, chapter 20: Selfish Load Balancing. Cambridge University Press, 2007.

Uwagi

1. Track 1: Artificial Intelligence in Applications

2. Session: 14th International Workshop on Computational Optimization