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

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 strategiessuch that no viable coalition of agents can improve upon their coalitional welfare by jointly changing their strategies. ANash equilibrium, where viable coalitions are only singletons, and a super strong equilibrium, where every coalition isdeemed viable, are two extreme scenarios in regard to coalition formation. A recent trend in the literature is to considerequilibrium notions that allow for coalition formation in between these two extremes and which are suitable to modelsocial coalition structures that arise in various real-life settings. The recent literature considered the question on theexistence of equilibria under social coalition structures mainly in Resource Selection Games (RSGs), due to the simplicityof this game form and its wide range of application domains. We take the question on the existence of equilibria undersocial coalition structures from the perspective of computational complexity theory. We study the problem of decidingthe existence of an equilibrium in RSGs with respect to a given social coalition structure. For an arbitrary coalitionstructure, we show that it is computationally intractable to decide whether an equilibrium exists even in very restrictedsettings of RSGs. In certain settings where an equilibrium is guaranteed to exist we give polynomial-time algorithms tofind an equilibrium.

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