5 October 2012, Computational Social Choice Seminar, Krzysztof Apt
Given a strategic game, when we allow the players to improve their choices on a unilateral basis, we are naturally brought to the concept of an improvement path, in which at each stage a single player who did not select a best response is allowed to select a better strategy. By definition each finite improvement path ends in a Nash equilibrium. This leads to the concept of a weakly acyclic game in which one stipulates that from any initial joint strategy some finite improvement path exists. In this talk we provide a natural classification of weakly acyclic games using the concept of a scheduler. This is a joint work with Sunil Simon.