Игра в нормальной форме

Представление игры в теории игр

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

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

Пример

Представленная матрица представляет собой нормальное представление игры, в которой игроки ходят одновременно (или, по крайней мере, не наблюдают за ходом другого игрока, прежде чем сделать свой собственный) и получают выигрыши, указанные для комбинаций сыгранных действий. Например, если игрок 1 играет сверху, а игрок 2 играет слева, игрок 1 получает 4, а игрок 2 получает 3. В каждой ячейке первое число представляет выигрыш игроку строки (в данном случае игроку 1), а второе число представляет выигрыш игроку столбца (в данном случае игроку 2).

Другие представления

Частичная топология игр с двумя игроками и двумя стратегиями, включая такие игры, как «Дилемма заключенного» , «Охота на оленя» и «Цыпленок».

Часто симметричные игры (где выигрыши не зависят от того, какой игрок выбирает каждое действие) представлены только одним выигрышем. Это выигрыш для игрока строки. Например, матрицы выигрышей справа и слева внизу представляют одну и ту же игру.

Топологическое пространство игр с родственными матрицами выплат также может быть отображено, причем смежные игры имеют наиболее похожие матрицы. Это показывает, как инкрементные изменения стимулов могут изменить игру.

Использование нормальной формы

Доминируемые стратегии

Матрица выплат облегчает устранение доминируемых стратегий , и обычно используется для иллюстрации этой концепции. Например, в дилемме заключенного мы видим, что каждый заключенный может либо «сотрудничать», либо «предать». Если предает ровно один заключенный, он легко отделается, а другой заключенный будет заперт на долгое время. Однако, если они оба предают, они оба будут заперты на более короткое время. Можно определить, что Сотрудничество строго доминируется Дефектом . Нужно сравнить первые числа в каждом столбце, в данном случае 0 > −1 и −2 > −5. Это показывает, что независимо от того, что выбирает игрок столбца, игрок строки выигрывает, выбрав Дефект . Аналогично сравнивается второй выигрыш в каждой строке; снова 0 > −1 и −2 > −5. Это показывает, что независимо от того, что делает строка, столбец выигрывает, выбрав Дефект . Это демонстрирует уникальное равновесие Нэша в этой игре: ( Дефект , Дефект ).

Последовательные игры в нормальной форме

Расширенная и нормальная иллюстрации последовательной игры с несовершенными и совершенными равновесиями Нэша на подыгровых уровнях отмечены красным и синим цветом соответственно.

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

1. Слева, если игрок 1 играет «Вверх» и «Слева» в противном случае
2. Слева, если игрок 1 играет сверху, и справа в противном случае
3. Справа, если игрок 1 играет «Вверх» и «Слева» в противном случае
4. Справа, если игрок 1 играет «Вверх» и «Справа» в противном случае

Справа — представление этой игры в нормальной форме.

Общая формулировка

Для того, чтобы игра была в нормальном состоянии, нам предоставляются следующие данные:

Существует конечное множество игроков I , каждый игрок обозначается i . Каждый игрок i имеет конечное число k чистых стратегий

${\displaystyle S_{i}=\{1,2,\ldots ,k\}.}$

Ачистый профиль стратегии - это ассоциация стратегий с игроками, то естьI-кортеж

${\displaystyle {\vec {s}}=(s_{1},s_{2},\ldots ,s_{I})}$

такой что

${\displaystyle s_{1}\in S_{1},s_{2}\in S_{2},\ldots ,s_{I}\in S_{I}}$

АФункция выигрыша — это функция

${\displaystyle u_{i}:S_{1}\times S_{2}\times \ldots \times S_{I}\rightarrow \mathbb {R} .}$

предполагаемая интерпретация которой — награда, присуждаемая одному игроку в результате игры. Соответственно, чтобы полностью определить игру, функция выигрыша должна быть указана для каждого игрока в наборе игроков I = {1, 2, ..., I }.

Определение : Игра в нормальной форме — это структура

${\displaystyle \mathrm {T} =\langle I,\mathbf {S} ,\mathbf {u} \rangle }$

где:

${\displaystyle I=\{1,2,\ldots ,I\}}$

это набор игроков,

${\displaystyle \mathbf {S} =\{S_{1},S_{2},\ldots ,S_{I}\}}$

представляет собой I -кортеж чистых наборов стратегий, по одному для каждого игрока, и

${\displaystyle \mathbf {u} =\{u_{1},u_{2},\ldots ,u_{I}\}}$

представляет собой I -кортеж платежных функций.

Ссылки

• Фуденберг, Д. ; Тироль, Дж. (1991). Теория игр . МТИ Пресс. ISBN 0-262-06141-4.
• Лейтон-Браун, Кевин; Шохам, Йоав (2008). Основы теории игр: краткое, междисциплинарное введение. Сан-Рафаэль, Калифорния: Morgan & Claypool Publishers. ISBN 978-1-59829-593-1.. 88-страничное математическое введение; бесплатное онлайн-издание во многих университетах.
• Люс, РД ; Райффа, Х. (1989). Игры и решения . Dover Publications. ISBN 0-486-65943-7.
• Шохам, Йоав; Лейтон-Браун, Кевин (2009). Многоагентные системы: алгоритмические, игровые и логические основы. Нью-Йорк: Cambridge University Press . ISBN 978-0-521-89943-7.. Полный справочник с точки зрения вычислений; см. Главу 3. Можно бесплатно загрузить онлайн.
• Вейбулл, Дж. (1996). Эволюционная теория игр . MIT Press. ISBN 0-262-23181-6.
• Дж. фон Нейман и О. Моргенштерн , Теория игр и экономическое поведение , John Wiley Science Editions, 1964. Первоначально опубликовано в 1944 году издательством Princeton University Press.