On efficient computation of equilibrium under social coalition structures

Name: On efficient computation of equilibrium under social coalition structures
Author: Caskurlu, B., Ekici, Özgür, Kizilkaya, F. E.

İsim	On efficient computation of equilibrium under social coalition structures
Yazar	Caskurlu, B., Ekici, Özgür, Kizilkaya, F. E.
Basım Tarihi:	2020
Basım Yeri	- TÜBİTAK
Konu	Algorithmic game theory, Laminar equilibrium, Contiguous equilibrium, Resource selection games
Tür	Süreli Yayın
Dil	İngilizce
Dijital	Evet
Yazma	Hayır
Kütüphane:	Özyeğin Üniversitesi
Demirbaş Numarası	1300-0632
Kayıt Numarası	c3b5b6bf-1e15-401c-b781-9262968853b3
Lokasyon	Economics
Tarih	2020
Notlar	TÜBİTAK
Örnek Metin	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.
DOI	10.3906/elk-1910-164
Cilt	28

Kaynağa git Özyeğin Üniversitesi

Aramaya Dön

Özyeğin Üniversitesi

Kaynağa git

On efficient computation of equilibrium under social coalition structures

Yazar Caskurlu, B., Ekici, Özgür, Kizilkaya, F. E.

Basım Tarihi 2020

Basım Yeri - TÜBİTAK

Konu Algorithmic game theory, Laminar equilibrium, Contiguous equilibrium, Resource selection games

Tür Süreli Yayın

Dil İngilizce

Dijital Evet

Yazma Hayır

Kütüphane Özyeğin Üniversitesi

Demirbaş Numarası 1300-0632

Kayıt Numarası c3b5b6bf-1e15-401c-b781-9262968853b3

Lokasyon Economics

Tarih 2020

Notlar TÜBİTAK

Örnek Metin 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.

DOI 10.3906/elk-1910-164

Cilt 28