Стратегия с доминированием Макса

В теории игр стратегия с доминированием по максимуму — это стратегия , которая не является лучшим ответом на какой-либо стратегический профиль других игроков. Это расширение понятия строго доминируемых стратегий , которые также имеют максимальное доминирование.

Определение

Стратегии с доминированием Макса

Стратегия $s_{i}\in S_{i}$ игрока $i$ является максимально доминируемым , если для каждого профиля стратегии других игроков $s_{-i}\in S_{-i}$ есть стратегия $s_{i}^{\prime }\in S_{i}$ такой, что $u_{i}(s_{i}^{\prime },s_{-i})>u_{i}(s_{i},s_{-i})$. Это определение означает, что $s_{i}$ не является лучшим ответом ни на один профиль стратегии $s_{-i}$, поскольку для каждого такого профиля стратегии существует другая стратегия $s_{i}^{\prime }$ что дает более высокую полезность, чем $s_{i}$ для игрока $i$.

Если стратегия $s_{i}\in S_{i}$ доминирует строго стратегия $s_{i}^{\prime }\in S_{i}$ тогда оно также является максимально доминируемым , поскольку для каждого профиля стратегии других игроков $s_{-i}\in S_{-i}$, $s_{i}^{\prime }$ это стратегия, по которой $u_{i}(s_{i}^{\prime },s_{-i})>u_{i}(s_{i},s_{-i})$.

Даже если $s_{i}$ строго доминируется смешанная стратегия, а также максимально доминируемая .

Стратегии со слабым доминированием по максимуму

Стратегия $s_{i}\in S_{i}$ игрока $i$ является слабо максимально доминируемым , если для каждого профиля стратегии других игроков $s_{-i}\in S_{-i}$ есть стратегия $s_{i}^{\prime }\in S_{i}$ такой, что $u_{i}(s_{i}^{\prime },s_{-i})\geq u_{i}(s_{i},s_{-i})$. Это определение означает, что $s_{i}$ либо не лучший ответ , либо не единственный лучший ответ на любой профиль стратегии. $s_{-i}$, поскольку для каждого такого профиля стратегии существует другая стратегия $s_{i}^{\prime }$ который дает по крайней мере ту же полезность, что и $s_{i}$ для игрока $i$.

Если стратегия $s_{i}\in S_{i}$ доминирует слабо стратегия $s_{i}^{\prime }\in S_{i}$ тогда он также слабо доминируется по максимуму , поскольку для каждого профиля стратегии других игроков $s_{-i}\in S_{-i}$, $s_{i}^{\prime }$ это стратегия, по которой $u_{i}(s_{i}^{\prime },s_{-i})\geq u_{i}(s_{i},s_{-i})$.

Даже если $s_{i}$ слабо доминируется смешанной стратегией, а также слабо доминируется по максимуму .

Макс-решаемые игры

Определение

Игра $G$ называется макс-разрешимой, если путем итерационного исключения стратегий с макс-доминированием в конце остается только один профиль стратегии.

Более формально мы говорим, что $G$ является макс-разрешимой, если существует последовательность игр $G_{0},...,G_{r}$ такой, что:

• $G_{0}=G$
• $G_{k+1}$ получается путем удаления одной стратегии с доминированием максимального максимума из пространства стратегий одного игрока в $G_{k}$.
• Остался только один профиль стратегии. $G_{r}$.

Очевидно, что каждая максимально разрешимая игра имеет уникальное чистое равновесие Нэша , которое представляет собой профиль стратегии, оставшийся в $G_{r}$.

Как и в предыдущей части, можно соответственно определить понятие слабо максимально разрешимых игр , которые представляют собой игры, для которых игра с единым профилем стратегии может быть достигнута путем исключения стратегий со слабо макс-доминированием . Основное отличие состоит в том, что игры со слабым доминированием максимума могут иметь более одного чистого равновесия Нэша и что порядок исключения может привести к различным равновесиям Нэша.

Пример

	Сотрудничать	Дефект
Сотрудничать	-1, -1	-5, 0
Дефект	0, -5	-3, -3
Рис. 1: матрица выигрышей заключенного дилеммы

Дилемма заключенного является примером игры с максимальным разрешением (поскольку она также разрешима с доминированием). В стратегии сотрудничества максимально доминирует дефект стратегии для обоих игроков, поскольку дефект игры всегда дает игроку более высокую полезность, независимо от того, что играет другой игрок. Чтобы увидеть это, обратите внимание: если игрок в ряду играет в сотрудничестве, то игрок в столбце предпочтет сыграть в отказ и выйти на свободу, чем играть в сотрудничество и отсидеть один год в тюрьме. Если игрок в ряду играет в «дефект», то игрок в столбце предпочтет сыграть в «дефект» и отсидеть три года в тюрьме, а не играть в сотрудничество и отсидеть пять лет в тюрьме.

Максимально решаемые игры и динамика лучших ответов

В любой игре с максимальным разрешением динамика наилучшего ответа в конечном итоге приводит к уникальному чистому равновесию по Нэшу в игре. Чтобы увидеть это, все, что нам нужно сделать, это заметить, что если $s_{1},s_{2},s_{3},...,s_{k}$ представляет собой последовательность выбывания в игре (это означает, что сначала $s_{1}$ исключается из пространства стратегий некоторого игрока, поскольку в нем доминирует максимум, то $s_{2}$ исключается и т. д.), то в динамике наилучшего ответа $s_{1}$ никогда не будет воспроизводиться игроком после одной итерации лучших ответов, $s_{2}$ никогда не будет сыгран игроком после двух итераций лучших ответов и так далее. Причина этого в том, что $s_{1}$ не лучший ответ на любой стратегический профиль других игроков $s_{-i}$ поэтому после одной итерации лучших ответов игрок, должно быть, выбрал другую стратегию. Поскольку мы понимаем, что никогда не вернемся в $s_{1}$ в любой итерации лучших ответов мы можем рассматривать игру после одной итерации лучших ответов так, как будто $s_{1}$ выбыл из игры, и завершите доказательство по индукции.

Слабо макс-решаемая игра

1, 1	0, 0
1, 0	0, 1
0, 1	1, 0

Тогда может показаться неожиданным, что слабо решаемые по максимуму игры не обязательно сходятся к чистому равновесию Нэша при использовании динамики наилучшего ответа , как можно видеть в игре справа. Если игра начинается с нижней левой ячейки матрицы, то возможна следующая наилучшая динамика повтора: игрок строки перемещается на одну строку вверх в центральную строку, игрок столбца перемещается в правый столбец, игрок строки возвращается в нижний ряд, игрок столбца возвращается к левому столбцу и так далее. Очевидно, что это никогда не сходится к единственному чистому равновесию по Нэшу в игре (которое представляет собой верхнюю левую ячейку в матрице выигрышей ).

См. также

Доминирование (теория игр)

Внешние ссылки и ссылки

• Нисан, Ноам; Шапира, Майкл; Зохар, Авив (2009), Асинхронная динамика лучшего ответа , Берлин: Springer-Verlag, заархивировано из оригинала 17 апреля 2003 г. Асинхронная динамика наилучшего ответа. [1] .