Игра в нормальной форме - Normal-form game

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

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

Пример

Предоставленная матрица представляет собой представление в нормальной форме игры, в которой игроки ходят одновременно (или, по крайней мере, не наблюдают за ходом другого игрока, прежде чем сделать свой собственный) и получают выплаты, указанные для комбинаций сыгранных действий. Например, если игрок 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 играет сверху и справа, в противном случае

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

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

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

• Есть конечное множество п игроков, которые мы помечаем {1, 2, ..., м}
• Каждый игрок k в п имеет конечное число чистые стратегии

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

А чистый стратегический профиль представляет собой ассоциацию стратегий для игроков, то есть м-кортеж

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

такой, что

${ displaystyle s_ {1} in S_ {1}, s_ {2} in S_ {2}, ldots, s_ {m} in S_ {m}}$

А функция выплаты это функция

${ displaystyle F_ {i}: S_ {1} times S_ {2} times ldots times S_ {m} rightarrow mathbb {R}.}$

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

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

${ Displaystyle G = langle P, mathbf {S}, mathbf {F} rangle}$

куда:

${ Displaystyle Р = {1,2, ldots, м }}$

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

${ Displaystyle mathbf {S} = {S_ {1}, S_ {2}, ldots, S_ {m} }}$

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

${ Displaystyle mathbf {F} = {F_ {1}, F_ {2}, ldots, F_ {m} }}$

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

Рекомендации

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