В теории игр , нормальная форма является описанием игры . В отличии от развернутой формы , в нормальной форме представление не графическое сам по себе , а представляет собой игру путем в матрице . В то время как этот подход может быть более полезным для определения строго доминируемых стратегий и равновесий Нэша , некоторая информация теряется по сравнению с представлениями в расширенной форме. Представление игры в нормальной форме включает в себя все ощутимые и мыслимые стратегии и соответствующие им выплаты для каждого игрока.
В статических играх с полной , совершенной информацией представление игры в нормальной форме - это спецификация пространств стратегий игроков и функций выигрыша. Пространство стратегии для игрока - это набор всех стратегий, доступных этому игроку, тогда как стратегия - это полный план действий для каждого этапа игры, независимо от того, возникает ли этот этап на самом деле в игре. Функция выигрыша для игрока - это отображение перекрестного произведения пространств стратегий игроков на набор выигрышей этого игрока (обычно набор действительных чисел, где число представляет кардинальную или порядковую полезность - часто кардинальную в нормальной форме представление) игрока, то есть функция выигрыша игрока принимает в качестве входных данных профиль стратегии (то есть спецификацию стратегий для каждого игрока) и дает представление выигрыша в качестве своего выхода.
Пример
Игрок 2 Игрок 1 | Оставил | Верно |
---|---|---|
Вершина | 4 , 3 | −1 , −1 |
Нижний | 0 , 0 | 3 , 4 |
Предоставленная матрица представляет собой представление в нормальной форме игры, в которой игроки ходят одновременно (или, по крайней мере, не наблюдают за ходом другого игрока перед тем, как сделать свой собственный) и получают выплаты, указанные для комбинаций сыгранных действий. Например, если игрок 1 играет сверху, а игрок 2 - слева, игрок 1 получает 4, а игрок 2 - 3. В каждой ячейке первое число представляет выплату игроку ряда (в данном случае игроку 1), а второе число. представляет выплату игроку столбца (в данном случае игроку 2).
Другие представления
Часто симметричные игры (где выплаты не зависят от того, какой игрок выбирает каждое действие) представлены только с одной выплатой. Это выигрыш для рядового игрока. Например, матрицы выигрышей справа и слева ниже представляют одну и ту же игру.
|
|
Топологическое пространство игр со связанными матрицами выигрышей также может быть отображено, при этом смежные игры имеют наиболее похожие матрицы. Это показывает, как постепенные изменения стимулов могут изменить игру.
Использование нормальной формы
Доминируемые стратегии
Игрок 2 Игрок 1 | Сотрудничать | Дефект |
---|---|---|
Сотрудничать | −1, −1 | −5, 0 |
Дефект | 0, −5 | −2, −2 |
Матрица выплат облегчает устранение доминирующих стратегий , и ее обычно используют для иллюстрации этой концепции. Например, в дилемме заключенного мы видим, что каждый заключенный может либо «сотрудничать», либо «отступать». Если ошибается ровно один заключенный, он легко выходит, а другой заключенный надолго запирается. Однако, если они оба дезертируют, они оба будут заключены в тюрьму на более короткое время. Можно определить, что в Cooperate строго доминирует дефект . Необходимо сравнить первые числа в каждом столбце, в данном случае 0> −1 и −2> −5. Это показывает, что независимо от того, что выбирает игрок столбца, игрок строки добивается большего успеха, выбирая Дефект . Точно так же сравнивают вторую выплату в каждой строке; снова 0> −1 и −2> −5. Это показывает, что независимо от того, какая строка делает, столбец работает лучше, если выбрать Дефект . Это демонстрирует уникальное равновесие по Нэшу в этой игре ( Дефект , Дефект ).
Последовательные игры в нормальной форме
Игрок 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 играет сверху и справа, в противном случае
- Вправо, если игрок 1 играет сверху и слева, в противном случае
- Право, если игрок 1 играет сверху и справа, в противном случае
Справа - представление этой игры в нормальной форме.
Общая формулировка
Для того, чтобы игра была в нормальном виде, нам предоставляются следующие данные:
- Существует конечное множество P игроков, которое мы обозначим {1, 2, ..., m }
- Каждый игрок k в P имеет конечное число чистых стратегий
А Профиль чистой стратегии - это ассоциация стратегий для игроков, то естьm-кортеж
такой, что
А функция выплаты - это функция
предполагаемая интерпретация которого - награда, присуждаемая одному игроку в результате игры. Соответственно, чтобы полностью определить игру, функция выплаты должна быть указана для каждого игрока в наборе игроков P = {1, 2, ..., m }.
Определение : Игра в нормальной форме - это структура
где:
это набор игроков,
является m -набором наборов чистых стратегий, по одному для каждого игрока, и
является m -набором функций выигрыша.
Рекомендации
- Fudenberg, D .; Тироль, Дж. (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.
- J. von Neumann и O. Morgenstern , Theory of games and Economic Behavior , John Wiley Science Editions, 1964. Который был первоначально опубликован в 1944 году издательством Princeton University Press.