Paper Info
Title
The max k-cut game and its strong equilibria
Abstract
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.
Year
DOI
Venue
2010
10.1007/978-3-642-13562-0_22
TAMC
Keywords
Field
DocType
strong equilibrium,nash equilibrium,max k-cut game,max k,cut game,player i,player j,social welfare,strategy space,pure strategy,single player,autonomous agent,pure strategy nash equilibrium
Correlated equilibrium,Combinatorics,Mathematical economics,Risk dominance,Epsilon-equilibrium,Strategy,Best response,Repeated game,Normal-form game,Nash equilibrium,Mathematics
Conference
Volume
ISSN
ISBN
6108
0302-9743
3-642-13561-7
Citations 
PageRank 
References 
5
0.47
9
Authors
2
Name
Order
Citations
PageRank
Laurent Gourvès124130.97
Jérôme Monnot251255.74