Stéphane Le Roux

Talk on 15/7/15 : From winning strategy to Nash equilibrium

Game theory is usually considered applied mathematics, but a few
game-theoretic results, such as Borel determinacy, were developed by
mathematicians for mathematics in a broad sense. These results usually
state determinacy, i.e., the existence of a winning strategy in games
that involve two players and two outcomes saying who wins. In a
multi-outcome setting, the notion of winning strategy is irrelevant
yet usually replaced faithfully with the notion of (pure) Nash
equilibrium. This talk will show that every determinacy result over an
arbitrary game structure, e.g., a tree, is transferable into existence
of multi-outcome (pure) Nash equilibrium over the same game
structure. The equilibrium-transfer theorem requires cardinal or
order-theoretic conditions on the strategy sets and the preferences,
respectively, whereas counter-examples show that every requirement is
relevant, albeit possibly improvable. When the outcomes are finitely
many, the proof provides an algorithm computing a Nash equilibrium
without significant complexity loss compared to the two-outcome
case. As examples of application, this talk generalises Borel
determinacy, positional determinacy of parity games, and finite-memory
determinacy of Muller games. (From an article with the same title in
MLQ 2014.)