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

«Матрица игры» перенаправляется сюда. Чтобы узнать об игре Криса Энгла, см. «Игра-рассказчик» § Альтернативные ролевые игры . Информацию об издателе см. в разделе Matrix Games .

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

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

Пример

Игра нормальной формы

Игрок 2 Игрок 1	Левый	Верно
Вершина	4 , 3	−1 , −1
Нижний	0 , 0	3 , 4

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

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

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

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

Оба игрока Игрок 2 Игрок 1 Олень заяц Олень 3, 3 0, 2 заяц 2, 0 2, 2

Просто грести Игрок 2 Игрок 1 Олень заяц Олень 3 0 заяц 2 2

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

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

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

Дилемма заключенного

Игрок 2 Игрок 1	Сотрудничать	Дефект
Сотрудничать	−1, −1	−5, 0
Дефект	0, −5	−2, −2

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

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

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

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

Игрок 2 Игрок 1	Левый, Левый	Левый, Правый	Вправо, Влево	Верно, верно
Вершина	4, 3	4, 3	−1, −1	−1, −1
Нижний	0, 0	3, 4	0, 0	3, 4

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

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

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

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

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

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

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

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

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

такой, что

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

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

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

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

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

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

где:

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

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

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

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

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

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

Ссылки

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