Infinite games played on finite graphs (Q1314640)

The concept of an infinite game played on a finite graph is perhaps novel in the context of a rather extensive recent literature in which infinite games are generally played on an infinite game tree. We claim two advances for our model, which is admittedly more restrictive. First, our games have a more apparent resemblance to ordinary parlor games in spite of their infinite duration. Second, by distinguishing those nodes of the graph that determines the winning and losing of the game (winning- condition nodes), we are able to offer a complexity analysis that is useful in computer science applications.