Graduate Student Colloquium
Jeremy Kun
UIC
Anti-Coordination Games and Stable Graph Colorings
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.
Monday October 28, 2013 at 5:30 PM in SEO 636