TY  - JOUR
TI  - On efficient computation of equilibrium under social coalition structures
AB  - 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.
AU  - Ekici, Ozgun
AU  - Caskurlu, Bugra
AU  - Kızılkaya, Fatih Erdem
DO  - 10.3906/elk-1910-164
PY  - 2020
JO  - Turkish Journal of Electrical Engineering and Computer Sciences
VL  - 28
IS  - 3
SN  - 1300-0632
SP  - 1686
EP  - 1698
DB  - TRDizin
UR  - http://search/yayin/detay/338495
ER  -