Achieving Good Nash Equilibrium by Temporal Addition of Dummy Players

Dadush, Ofek; Tamir, Tami

doi:10.15439/2021F112

Artykuł - szczegóły

Tytuł artykułu

Achieving Good Nash Equilibrium by Temporal Addition of Dummy Players

Autorzy

Dadush Ofek , Tamir Tami

Wybrane pełne teksty z tego czasopisma

http://annals-csis.org

Identyfikatory

DOI

10.15439/2021F112

Warianty tytułu

Konferencja

Federated Conference on Computer Science and Information Systems (16 ; 02-05.09.2021 ; online)

Języki publikacji

Abstrakty

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

computer science cost game Nash equilibrium

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

ofek.dadush@post.idc.ac.il

School of Computer Science The Interdisciplinary Center Herzliya, Israel

autor

Tamir Tami

tami@idc.ac.il

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

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-47167733-1a6f-4ef1-8611-fd5238d309c5