Существование ситуации равновесия в конечной позиционной игре с полной информацией

Ответ:

Теорема. В любой многошаговой (позиционной) игре с полной информацией на конечном древовидном графе существует ситуация абсолютного равновесия по Нэшу (NE).

Доказательство. Докажем по индукции по длине игры l. Пусть l ??1 (рис. 1). Предположим — множеству очередностей i-го игрока. Игрок i выбирает альтернативу из условия максимизации своего выигрыша .

Игроки получают, соответственно. Если i -й игрок отклонится, он получит меньше, следовательно, он будет действовать согласно стратегии, образующей абсолютное NE.

Предположим теперь, что теорема справедлива для всех игр, таких что длина каждой из них не превосходит l?1.

Докажем, что ситуация равновесия существует для игры G длины l.

Так как подыгры (см. рис. 2), имеют длину не более l ?1, то по индукционному предположению теорема справедлива, следовательно, существует ситуация абсолютного NE

Пусть.

.

И пусть в точке z* ходит игрок i:. Тогда игра G переходит в подыгру. Но в подыгре каждый i-ый игрок получает выигрыш, соответствующий ситуации NE. Поскольку — сужение стратегии на множество, то выигрыш i-го игрока в ситуации u* игры G равен выигрышу в ситуации.

(1).

Аналогично доказывается, если. Пусть произвольная стратегия игрока в игре G. Обозначим .

Тогда.

Утверждение теоремы следует теперь из (1), (2).