Игра в расширенной форме

Эта статья требует внимания специалиста по математике . Пожалуйста , добавьте причину в или разговоре параметр для этого шаблона , чтобы объяснить проблему с статьей. WikiProject Mathematics может помочь нанять эксперта. ( Март 2011 г. )

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

Конечные игры расширенной формы [ править ]

Некоторые авторы, особенно во вводных учебниках, изначально определяют игру в расширенной форме как просто игровое дерево с выплатами (без несовершенной или неполной информации) и добавляют другие элементы в последующих главах в качестве уточнений. В то время как остальная часть этой статьи следует этому мягкому подходу с мотивирующими примерами, мы заранее представляем конечные игры расширенной формы, как (в конечном итоге) построенные здесь. Это общее определение было введено Гарольдом В. Куном в 1953 году, который расширил более раннее определение фон Неймана с 1928 года. Таким образом, после презентации Харта (1992) , игра с n игроками в расширенной форме состоит из следующего:

• Конечное множество из n (рациональных) игроков
• Корневое дерево , называемое дерево игры
• Каждый терминал (лист) узел дерева игры имеет п -кратный из выигрышей , а это означает есть один выигрыш для каждого игрока в конце каждой возможной комбинации
• Перегородка из нетерминальных узлов дерева игры в п + 1 подмножеств, по одному для каждого (рационального) игрока, и с помощью специального подмножества для фиктивного игрока , называется вероятность (или природа). Подмножество узлов каждого игрока называется «узлами игрока». (Таким образом, игра с полной информацией имеет пустой набор узлов Шанса.)
• Каждый узел случайного игрока имеет распределение вероятностей по исходящим ребрам.
• Каждый набор узлов рационального игрока далее разбивается на информационные наборы , которые делают определенные выборы неотличимыми для игрока при выполнении хода в том смысле, что:
  • существует взаимно однозначное соответствие между исходящими ребрами любых двух узлов одного и того же информационного набора - таким образом, набор всех исходящих ребер информационного набора разделен на классы эквивалентности , каждый класс представляет собой возможный выбор для хода игрока на какой-то момент - и
  • каждый (направленный) путь в дереве от корня до конечного узла может пересекать каждый информационный набор не более одного раза
• полное описание игры, заданное указанными выше параметрами, известно игрокам

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

Приведенная выше презентация, хотя и точно определяет математическую структуру, по которой ведется игра, опускает, однако, более техническое обсуждение формализации утверждений о том, как ведется игра, например, «игрок не может различать узлы в одном и том же наборе информации при принятии решения» . Их можно уточнить с помощью эпистемической модальной логики ; см. подробности в Shoham & Leyton-Brown (2009 , глава 13).

Совершенная информация игра для двух игроков по игре дерева (как определено в комбинаторной теории игр и искусственного интеллекта ) может быть представлена в виде развернутой форме игры с результатами (т.е. выиграть, проиграть или рисовать ). Примеры таких игр включают крестики-нолики , шахматы и бесконечные шахматы . ^{[1] [2]} Игра с деревом ожидаемого минимума , как и игра в нарды , не имеет несовершенной информации (все информационные наборы являются одиночными), но имеет ходы случайности. Например, покеримеет как случайные ходы (раздающиеся карты), так и несовершенную информацию (карты, тайно хранящиеся у других игроков). ( Бинмор 2007 , глава 2)

Совершенная и полная информация [ править ]

Полное представление в развернутой форме определяет:

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

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

Первоначальный узел принадлежит игроку 1, что указывает на то, что игрок 1 ходит первым. Игра по дереву выглядит следующим образом: игрок 1 выбирает между U и D ; Игрок 2 наблюдает за выбором игрока 1 и затем выбирает между U ' и D' . Выплаты указаны в дереве. Четыре результата представлены четырьмя конечными узлами дерева: (U, U '), (U, D'), (D, U ') и (D, D'). Выплаты, связанные с каждым результатом, соответственно, следующие (0,0), (2,1), (1,2) и (3,1).

Если игрок 1 играет D , игрок 2 будет играть U ', чтобы максимизировать свой выигрыш, и поэтому игрок 1 получит только 1. Однако, если игрок 1 играет U , игрок 2 максимизирует свой выигрыш, играя D', а игрок 1 получает 2. Игрок 1 предпочитает 2 к 1 и поэтому будет играть U, а игрок 2 - D ' . Это идеальное равновесие в подигре .

Несовершенная информация [ править ]

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

1. Каждый узел в наборе принадлежит одному игроку.
2. Когда игра достигает набора информации, игрок, который собирается двигаться, не может различать узлы в наборе информации; т.е. если информационный набор содержит более одного узла, игрок, которому принадлежит этот набор, не знает, какой узел в наборе был достигнут.

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

Если в игре есть набор информации с более чем одним участником, говорят, что эта игра имеет несовершенную информацию . Игра с точной информацией такова, что на любом этапе игры каждый игрок точно знает, что произошло ранее в игре; т.е. каждый информационный набор представляет собой одноэлементный набор. ^{[1] [2]} Любая игра без точной информации содержит несовершенную информацию.

Игра справа такая же, как и вышеприведенная, за исключением того, что игрок 2 не знает, что делает игрок 1, когда он приходит играть. Первая описанная игра содержит точную информацию; игра справа нет. Если оба игрока рациональны и оба знают, что оба игрока рациональны, и все, что известно любому игроку, известно каждому игроку (т.е. игрок 1 знает, что игрок 2 знает, что игрок 1 рациональный, а игрок 2 знает это, и т. Д.) до бесконечности ), игра в первой игре будет следующей: игрок 1 знает, что если он играет U , игрок 2 будет играть D ' (потому что для игрока 2 выигрыш 1 предпочтительнее выигрыша 0), и поэтому игрок 1 получит 2. Однако, если игрок 1 играет D , игрок 2 будет играть U '(поскольку для игрока 2 выигрыш 2 лучше, чем выигрыш 1), и игрок 1 получит 1. Следовательно, в первой игре равновесие будет ( U , D ' ), потому что игрок 1 предпочитает получать 2 к 1. и так будет играть U, а игрок 2 сыграет D ' .

Во второй игре менее ясно: игрок 2 не может наблюдать за ходом игрока 1. Игрок 1 хотел бы обмануть игрока 2, заставив его думать, что он играл в U, когда он фактически играл в D, так что игрок 2 будет играть D ', а игрок 1 получит 3. Фактически во второй игре существует идеальное байесовское равновесие, в котором игрок 1 играет D и игрок 2 играет U» и игрок 2 имеет убеждение , что игрок 1 будет определенно играть D . В этом равновесии каждая стратегия рациональна с учетом имеющихся убеждений, и каждое убеждение согласуется с играемыми стратегиями. Обратите внимание, как несовершенство информации меняет исход игры.

Для того, чтобы более легко решить эту игру для равновесия Нэша , ^[3] он может быть преобразован в нормальной форме . ^[4] Учитывая, что это одновременная / последовательная игра, у первого и второго игрока есть две стратегии . ^[5]

• Стратегии игрока 1: {U, D}
• Стратегии игрока 2: {U ', D'}

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

• Если игрок 1 играет вверх (U), игрок 2 предпочитает играть вниз (D ') (Выплата 1> 0)
• Если игрок 1 играет вниз (D), игрок 2 предпочитает играть вверх (U ') (Выплата 2> 1)
• Если игрок 2 играет вверх (U '), игрок 1 предпочитает играть вниз (D) (Выплата 1> 0).
• Если игрок 2 играет вниз (D '), игрок 1 предпочитает играть вниз (D) (3> 2)

Эти предпочтения могут быть отмечены в матрице, и любое поле, в котором оба игрока имеют предпочтение, обеспечивает равновесие по Нэшу. Эта конкретная игра имеет единственное решение (D, U ') с выигрышем (1,2).

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

Неполная информация [ править ]

Может случиться так, что игрок не знает точно, каковы выплаты в игре или к какому типу принадлежат его оппоненты. В такого рода играх есть неполная информация . В развернутом виде она представлена ​​как игра с полной, но несовершенной информацией с использованием так называемого преобразования Харшаньи . Это преобразование вводит в игру понятие выбора природы или выбора Бога.. Представьте себе игру, в которой работодатель решает, стоит ли нанимать соискателя работы. Способности соискателя могут быть одним из двух: высокими или низкими. Уровень их способностей случайный; у них либо низкая способность с вероятностью 1/3, либо высокая способность с вероятностью 2/3. В этом случае удобно моделировать природу как своего рода игрока, который выбирает способности претендента в соответствии с этими вероятностями. Однако у природы нет вознаграждений. Выбор природы представлен в дереве игры незаполненным узлом. Края, исходящие от узла выбора природы, помечаются с вероятностью наступления события, которое он представляет.

Игра справа - это игра с полной информацией (все игроки и выплаты известны всем), но с неполной информацией (работодатель не знает, каким был ход природы). Начальный узел находится в центре и не заполнен , поэтому природа идет первой. Природа выбирает с той же вероятностью тип игрока 1 (что в этой игре равносильно выбору выигрышей в сыгранной вспомогательной игре), либо t1, либо t2. У игрока 1 для них есть отдельные наборы информации; т.е. игрок 1 знает, что они за тип (это не обязательно). Однако игрок 2 не соблюдает выбор природы. Они не знают тип игрока 1; однако в этой игре они наблюдают за действиями игрока 1; т.е. есть точная информация. Действительно, теперь уместно изменить приведенное выше определение полной информации: на каждом этапе игрыкаждый игрок знает, что было сыгранодругими игроками . Что касается частной информации, каждый игрок знает, во что играла природа. Информационные наборы, как и прежде, представлены пунктирными линиями.

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

Если оба типа играют в одно и то же действие (объединение), равновесие не может быть сохранено. Если оба играют D , игрок 2 может сформировать уверенность в том, что они находятся на любом узле в информационном наборе, только с вероятностью 1/2 (потому что это шанс увидеть любой тип). Игрок 2 максимизирует свой выигрыш, играя D ' . Тем не менее, если они играют D» , тип 2 предпочел бы играть U . Это не может быть равновесием. Если оба типа играют U , игрок 2 снова формирует уверенность в том, что они находятся в любом из узлов с вероятностью 1/2. В этом случае игрок 2 пьесы D» , но тогда тип 1 предпочитает играть D .

Если тип 1 играет U и типа 2 играет D , игрок 2 будет играть D» любые действия , они наблюдают, но тип 1 предпочитает D . Только равновесие , следовательно, с 1 типа игры D , тип 2 игры U и игрок 2 играть U» , если они наблюдают D и рандомизации , если они наблюдают U . Своими действиями игрок 1 сообщил игроку 2 свой тип.

Формальное определение [ править ]

Формально конечная игра в развернутом виде - это структура, в которой:${\ displaystyle \ Gamma = \ langle {\ mathcal {K}}, \ mathbf {H}, [(\ mathbf {H} _ {i}) _ {i \ in {\ mathcal {I}}}], \ {A (H) \} _ {H \ in \ mathbf {H}}, a, \ rho, u \ rangle}$

• ${\ displaystyle {\ mathcal {K}} = \ langle V, v ^ {0}, T, p \ rangle}$- конечное дерево с набором узлов , уникальным начальным узлом , набором конечных узлов (пусть будет набором узлов решений) и непосредственной функцией-предшественницей, на которой представлены правила игры,${\ displaystyle V}$${\ displaystyle v ^ {0} \ in V}$${\ Displaystyle T \ подмножество V}$${\displaystyle D=V\setminus T}$${\displaystyle p:V\rightarrow D}$
• ${\displaystyle \mathbf {H} }$является разделом, называемым информационным разделом,${\displaystyle D}$
• ${\displaystyle A(H)}$представляет собой набор действий, доступных для каждого набора информации, который образует раздел на набор всех действий .${\displaystyle H\in \mathbf {H} }$${\displaystyle {\mathcal {A}}}$
• ${\displaystyle a:V\setminus \{v^{0}\}\rightarrow {\mathcal {A}}}$- это раздел действий, связывающий каждый узел с одним действием , выполняя:${\displaystyle v}$${\displaystyle a(v)}$

${\displaystyle \forall H\in \mathbf {H} ,\forall v\in H}$, Ограничение на ON биекция, с множеством правопреемниками узлов .${\displaystyle a_{v}:s(v)\rightarrow A(H)}$${\displaystyle a}$${\displaystyle s(v)}$${\displaystyle s(v)}$${\displaystyle v}$

• ${\displaystyle {\mathcal {I}}=\{1,...,I\}}$является конечным множеством игроков, является (называемым специальным игроком) природой и является разделом игрока в информационном множестве . Пусть будет один игрок, который делает ход в узле .${\displaystyle 0}$${\displaystyle (\mathbf {H} _{i})_{i\in {\mathcal {I}}\cup \{0\}}}$${\displaystyle \mathbf {H} }$${\displaystyle \iota (v)=\iota (H)}$${\displaystyle v\in H}$
• ${\displaystyle \rho =\{\rho _{H}:A(H)\rightarrow [0,1]|H\in \mathbf {H} _{0}\}}$ семейство вероятностей действий природы, и
• ${\displaystyle u=(u_{i})_{i\in {\mathcal {I}}}:T\rightarrow \mathbb {R} ^{\mathcal {I}}}$ - функция профиля выплат.

Бесконечное пространство действия [ править ]

Может случиться так, что у игрока есть бесконечное количество возможных действий на выбор в конкретном узле принятия решения. Устройство, используемое для представления этого, представляет собой дугу, соединяющую два ребра, выходящих из рассматриваемого узла принятия решения. Если пространство действия представляет собой континуум между двумя числами, нижнее и верхнее ограничивающие числа помещаются в нижнюю и верхнюю часть дуги соответственно, обычно с переменной, которая используется для выражения выигрышей. Бесконечное количество узлов решений, которые могут возникнуть, представлены одним узлом, размещенным в центре дуги. Аналогичное устройство используется для представления пространств действий, которые, хотя и не бесконечны, достаточно велики, чтобы их невозможно было представить с краем для каждого действия.

Дерево слева представляет такую ​​игру либо с бесконечными пространствами действий (любое действительное число от 0 до 5000), либо с очень большими пространствами действий (возможно, с любым целым числом от 0 до 5000). Это будет указано в другом месте. Здесь предполагается, что это первая и, для конкретности, предполагается, что она представляет две фирмы, участвующие в конкуренции Штакельберга . Выигрыши фирмам представлены на левой стороне , с и в качестве стратегии , которые они принимают , и , и , как некоторые константы (здесь предельные издержки для каждой фирмы). Подыгры совершенных равновесия Нэша этой игры можно найти, взяв первый частную производную ^{[ править}${\displaystyle q_{1}}$${\displaystyle q_{2}}$${\displaystyle c_{1}}$${\displaystyle c_{2}}$^] Каждая функция выигрыша в отношении (фирмы 2) переменной стратегия последователя ( ) и найти свою лучший ответ функцию . Тот же процесс может быть проделан для лидера, за исключением того, что при расчете своей прибыли он знает, что фирма 2 будет воспроизводить вышеуказанный ответ, и поэтому его можно заменить в его задаче максимизации. Затем он может найти , взяв первую производную, уступив . Внесение этого в функцию наилучшего отклика фирмы 2 и является идеальным равновесием по Нэшу в подигре.${\displaystyle q_{2}}$${\displaystyle q_{2}(q_{1})={\tfrac {5000-q_{1}-c_{2}}{2}}}$${\displaystyle q_{1}}$${\displaystyle q_{1}^{*}={\tfrac {5000+c_{2}-2c_{1}}{2}}}$${\displaystyle q_{2}^{*}={\tfrac {5000+2c_{1}-3c_{2}}{4}}}$${\displaystyle (q_{1}^{*},q_{2}^{*})}$

См. Также [ править ]

• Аксиома определенности
• Идеальная информация
• Комбинаторная теория игр
• Самоподтверждающееся равновесие
• Последовательная игра
• Сигнализация
• Концепция решения

Ссылки [ править ]

• Харт, Серджиу (1992). «Игры в экстенсивной и стратегической формах». In Aumann, Роберт ; Харт, Серджиу (ред.). Справочник по теории игр с экономическими приложениями . 1 . Эльзевир. ISBN 978-0-444-88098-7.
• Бинмор, Кеннет (2007). Игра по-настоящему: текст по теории игр . Oxford University Press, США. ISBN 978-0-19-530057-4.
• Дрешер М. (1961). Математика стратегических игр: теория и приложения (Глава 4: Игры в развернутой форме, стр. 74–78). ISBN Rand Corp. 0-486-64216-X 
• Фуденберг Д. и Тирол Дж. (1991) Теория игр (Ch3 Extensive form games, pp67–106). Пресса MIT. ISBN 0-262-06141-4 
• Лейтон-Браун, Кевин; Шохам, Йоав (2008), Основы теории игр: краткое, многопрофильное введение , Сан-Рафаэль, Калифорния: Издательство Morgan & Claypool, ISBN 978-1-59829-593-1. 88-страничное математическое введение; в главах 4 и 5. бесплатные онлайн во многих университетах.
• Люс Р.Д. и Райффа Х. (1957). Игры и решения: введение и критический обзор. (Ch3: Extensive and Normal Forms, pp39–55). Wiley New York. ISBN 0-486-65943-7 
• Осборн MJ и Рубинштейн А. 1994. Курс теории игр (Ch6 Extensive game with perfect information, pp. 89–115). Пресса MIT. ISBN 0-262-65040-1 
• Шохам, Йоав; Лейтон-Браун, Кевин (2009), Многоагентные системы: алгоритмические, теоретико-игровые и логические основы , Нью-Йорк: Cambridge University Press , ISBN 978-0-521-89943-7. Исчерпывающий справочник с вычислительной точки зрения; см. главу 5. Загружается бесплатно в Интернете .

Дальнейшее чтение [ править ]

• Хорст Херрлих (2006). Аксиома выбора . Springer. ISBN 978-3-540-30989-5.В разделах 6.1, «Катастрофы в теории игр» и 7.2 «Измеримость (аксиома детерминированности)» обсуждаются проблемы расширения определения конечного случая до бесконечного числа вариантов (или ходов).

Исторические документы

• Нойман, Дж. (1928). "Zur Theorie der Gesellschaftsspiele". Mathematische Annalen . 100 : 295–320. DOI : 10.1007 / BF01448847 .
• Гарольд Уильям Кун (2003). Лекции по теории игр . Издательство Принстонского университета. ISBN 978-0-691-02772-2. содержит лекции Куна в Принстоне с 1952 г. (ранее официально не публиковались, но распространяются в виде фотокопий)