City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Рекуррентная устойчивость (Даниил Мусатов)
Dynamic Game Theory

What: Lecture
When: Sunday, 11 April 2010, 13:00–14:35
Where: ПОМИ РАН

Description

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