On Strong Equilibria in the Max Cut Game
Gourvès, Laurent; Monnot, Jérôme (2009), On Strong Equilibria in the Max Cut Game, in Leonardi, Stefano, Proceedings of the 5th International Workshop on Internet and Network Economics, Springer-Verlag : Berlin, p. 608-615. http://dx.doi.org/10.1007/978-3-642-10841-9_62
TypeCommunication / Conférence
Conference titleWINE 2009, 5th International Workshop on Internet and Network Economics
Book titleProceedings of the 5th International Workshop on Internet and Network Economics
Book authorLeonardi, Stefano
Series titleLecture Notes in Computer Science
Number of pages642
MetadataShow full item record
Abstract (EN)This paper deals with two games defined upon well known generalizations of max cut. We study the existence of a strong equilibrium which is a refinement of the Nash equilibrium. Bounds on the price of anarchy for Nash equilibria and strong equilibria are also given. In particular, we show that the max cut game always admits a strong equilibrium and the strong price of anarchy is 2/3.
Subjects / KeywordsNash Equilibrium; Max Cut
Showing items related by title and author.