Jeremy Kun : Anti-Coordination Games and Stable Graph Colorings

Posted by Phillip Wesolek , part of the Graduate Student Colloquium.

At

Oct. 28, 2013, 5:30 p.m.

In

SEO 636

Abstract

We present a general type of anti-coordination game played on a graph and analyze its stable and strictly stable Nash equilibria. We characterize when such equilibria exist and when their decision problem is NP-hard. Next we consider the directed case, a generalization which captures both coordination and anti-coordination. We prove the decision problem there for non-strict equilibria is also NP-hard.