Logo PTI Logo FedCSIS

Proceedings of the 16th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 25

Achieving Good Nash Equilibrium by Temporal Addition of Dummy Players

,

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 ()

Full text

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

  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.