Теория динамических игр. Лекция 2, часть 1

Рекуррентная устойчивость

Многие игры, встречающиеся в задачах на математических кружках и школьных олимпиадах, сводятся к следующей конструкции: двое игроков по очереди двигают фишку по стрелкам некоторого ориентированного графа. Тот, кто не может сделать ход, проиграл. Решаются такие игры единообразно: позиции, из которых нельзя сделать ход, проигрышные; позиции, из которых можно пойти в проигрышные, выигрышные; те, из которых можно пойти только в выигрышные, снова проигрышные, и т.д. Получается, что выигрышные и проигрышные позиции определяются рекуррентно друг через друга. В докладе мы рассмотрим несколько обобщений этой простой конструкции: во–первых, на случай, когда в графе есть циклы и игра может потенциально быть бесконечной. Во–вторых, на случай, когда игроков больше двух и они могут объединяться в коалиции. Разумеется, в последнем случае существенно пересматриваются правила игры, а именно очерёдность ходов и условие выигрыша, но общая идея рекуррентного определения исхода игры остаётся. Также мы разберём несколько экономических моделей, в которых подобные конструкции появляются естественным образом.