The Max k-Cut Game and Its Strong Equilibria
Gourvès, Laurent; Monnot, Jérôme (2010), The Max k-Cut Game and Its Strong Equilibria, in Kratochvil, Jan; Li, Angsheng; Fiala, Jiri; Kolman, Petr, Theory and Applications of Models of Computation 7th Annual Conference, TAMC 2010, Prague, Czech Republic, June 7-11, 2010. Proceedings, Springer : Berlin, p. 234-246. http://dx.doi.org/10.1007/978-3-642-13562-0_22
TypeCommunication / Conférence
Conference title7th Annual Conference Theory and Applications of Models of Computation (TAMC)
Conference countryRépublique tchèque
Book titleTheory and Applications of Models of Computation 7th Annual Conference, TAMC 2010, Prague, Czech Republic, June 7-11, 2010. Proceedings
Book authorKratochvil, Jan; Li, Angsheng; Fiala, Jiri; Kolman, Petr
Series titleLecture Notes in Computer Science
Number of pages480
MetadataShow full item record
Abstract (EN)An instance of the max k −cut game is an edge weighted graph. Every vertex is controlled by an autonomous agent with strategy space [1..k]. Given a player i, his payoff is defined as the total weight of the edges [i,j] such that player j’s strategy is different from player i’s strategy. The social welfare is defined as the weight of the cut, i.e. half the sum of the players payoff. It is known that this game always has a pure strategy Nash equilibrium, a state from which no single player can deviate. Instead we focus on strong equilibria, a robust refinement of the pure Nash equilibrium which is resilient to deviations by coalitions of any size. We study the strong equilibria of the max k −cut game under two perspectives: existence and worst case social welfare compared to a social optimum.
Subjects / Keywordsstrong equilibria; edge weighted graph; max k−cut game
Showing items related by title and author.