Buğra ÇAŞKURLU, Özgün EKİCİ, Fatih Erdem KIZILKAYA

On efficient computation of equilibrium under social coalition structures

In game-theoretic settings the key notion of analysis is an equilibrium, which is a profile of agent strategies such that no viable coalition of agents can improve upon their coalitional welfare by jointly changing their strategies. A Nash equilibrium, where viable coalitions are only singletons, and a super strong equilibrium, where every coalition is deemed viable, are two extreme scenarios in regard to coalition formation. A recent trend in the literature is to consider equilibrium notions that allow for coalition formation in between these two extremes and which are suitable to model social coalition structures that arise in various real-life settings. The recent literature considered the question on the existence of equilibria under social coalition structures mainly in Resource Selection Games RSGs , due to the simplicity of this game form and its wide range of application domains. We take the question on the existence of equilibria under social coalition structures from the perspective of computational complexity theory. We study the problem of deciding the existence of an equilibrium in RSGs with respect to a given social coalition structure. For an arbitrary coalition structure, we show that it is computationally intractable to decide whether an equilibrium exists even in very restricted settings of RSGs. In certain settings where an equilibrium is guaranteed to exist we give polynomial-time algorithms to find an equilibrium.

Keywords:

Algorithmic game theory laminar equilibrium, contiguous equilibrium, resource selection games,

PDF

___

[1] Anshelevich E, Caskurlu B, Hate A. Partition equilibrium always exists in resource selection games. Theory of Computing Systems 2013; 53 (1): 73-85. doi: 10.1007/s00224-013-9463-2
[2] Anshelevich E, Dasgupta A, Kleinberg J, Tardos E, Wexler T et al. The price of stability for network design with fair cost allocation. SIAM Journal on Computing 2008; 38 (4): 1602-1623. doi:10.1137/070680096
[3] Aumann RJ. Acceptable points in general cooperative n-person games. Contributions to the Theory of Games 1959; 4: 287-324. doi: 10.1515/9781400882168-018
[4] Baye MR, Tian G, Zhou J. Characterizations of the existence of equilibria in games with discontinuous and nonquasiconcave payoffs. The Review of Economic Studies (1993); 60 (4): 935-948. doi: 10.2307/2298107
[5] Caskurlu B, Ekici O, Kizilkaya FE. On existence of equilibrium under social coalition structures. arXiv:1910.04648 [cs.GT] 2019.
[6] Christodoulou G, Koutsoupias E, Nanavati A. Coordination mechanisms. Theoretical Computer Science 2009; 410 (36): 3327-3336. doi: 10.1016/j.tcs.2009.01.005
[7] Cohen JE, Horowitz P. Paradoxical behaviour of mechanical and electrical networks. Nature 1991; 352 (6337): 699-701. doi: 10.1038/352699a0
[8] Correa JR, Schulz AS, Stier-Moses NE. A geometric approach to the price of anarchy in nonatomic congestion games. Games and Economic Behavior 2008; 6 4(2): 457-469. doi: 10.1016/j.geb.2008.01.001
[9] Czumaj A, Krysta P, Vöcking B. Selfish traffic allocation for server farms. SIAM Journal on Computing 2010; 39 (5): 1957-1987. doi: 10.1137/070693862
[10] Feldman M, Tennenholtz M. Structured coalitions in resource selection games. ACM Transactions on Intelligent Systems and Technology 2010; 1 (1): 1-21. doi: 10.1145/1858948.1858952
[11] Hayrapetyan A, Tardos E, Wexler T. The effect of collusion in congestion games. Proceedings of the thirty-eighth annual ACM symposium on Theory of computing (STOC’06), 2006.
[12] Hoefer M, Penn M, Polukarov M, Skopalik A, Vocking B. Considerate equilibrium. Proceedings of 22nd International Joint Conference on Artificial Intelligence 2011; 234-239. doi: 10.5591/978-1-57735-516-8/IJCAI11-050
[13] Kamihigashi T, Keskin K, Sağlam Ç. Organizational refinements of Nash equilibrium. Discussion Paper Series DP2017-25, Research Institute for Economics & Business Administration, Kobe University, 2017.
[14] Milinski M. An evolutionarily stable feeding strategy in sticklebacks. Zeitschrift für Tierpsychologie 1979; 51 (1): 36-40. doi:10.1111/j.1439-0310.1979.tb00669.x
[15] Nash J. Non-Cooperative Games. Annals of Mathematics 1951; 54 (2): 286-295. doi: 10.2307/1969529
[16] Quint T, Shubik M. A model of migration. Cowles Foundation for Research in Economics, Yale University 1994; 1088.
[17] Reny PJ. On the existence of pure and mixed strategy Nash equilibria in discontinuous games. Econometrica 67.5 (1999): 1029-1056.
[18] Rosenthal RW. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory 1973; 2: 65–67. doi: 10.1007/bf01737559

Turkish Journal of Electrical Engineering and Computer Science-Cover

ISSN: 1300-0632
Yayın Aralığı: Yılda 6 Sayı
Yayıncı: TÜBİTAK

Arşiv