|
Published Articles >> Table of Contents >> Abstract
46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05)
pp. 142-154
Sink Equilibria and Convergence
Michel Goemans, MIT
Vahab Mirrokni, MIT
Adrian Vetta, McGill University
Full Article Text:
 
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.68
Send link to a friend
| Abstract |
|
We introduce the concept of a sink equilibrium. A sink equilibrium is a strongly connected component with no outgoing arcs in the strategy profile graph associated with a game. The strategy profile graph has a vertex set induced by the set of pure strategy profiles; its arc set corresponds to transitions between strategy profiles that occur with nonzero probability. (Here our focus will just be on the special case in which the strategy profile graph is actually a best response graph; that is, its arc set corresponds exactly to best response moves that result from myopic or greedy behaviour.) We argue that there is a natural convergence process to sink equilibria in games where agents use pure strategies. This leads to an alternative measure of the social cost of a lack of coordination, the price of sinking, which measures the worst case ratio between the value of a sink equilibrium and the value of the socially optimal solution. We define the value of a sink equilibrium to be the expected social value of the steady state distribution induced by a random walk on that sink. We illustrate the value of this measure in three ways. Firstly, we show that it may more accurately reflects the inefficiency of uncoordinated solutions in competitive games when the use of pure strategies is the norm. In particular, we give an example (a valid-utility game) in which the game converges to solutions which are a factor
|
 Additional Information
|
Citation:
Michel Goemans, Vahab Mirrokni, Adrian Vetta,
"Sink Equilibria and Convergence,"
focs,
pp. 142-154,
46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05),
2005
|
|
