Игра в развернутой форме

Широкое представление игры в теории игр

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

Конечные игры в развернутой форме

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

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

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

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

Игра с полной информацией для двух игроков на игровом дереве (как определено в комбинаторной теории игр и искусственном интеллекте ) может быть представлена ​​как игра в развернутой форме с результатами (т. е. выигрыш, проигрыш или ничья ). Примерами таких игр являются крестики-нолики , шахматы и бесконечные шахматы . ^{[1] [2]} Игра на дереве expectminimax , как и в нардах , не имеет несовершенной информации (все информационные наборы являются синглтонами), но имеет ходы случая. Например, в покере есть как ходы случая (раздаваемые карты), так и несовершенная информация (карты, тайно удерживаемые другими игроками). (Binmore 2007, chpt. 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] Учитывая, что это одновременная / последовательная игра, у игрока 1 и игрока 2 есть по две стратегии . ^[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\subset 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}$, ограничение на является биекцией с множеством последующих узлов . ${\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) ( ⁠ ⁠ ${\displaystyle q_{2}}$ ) и найдя ее наилучшую функцию ответа , . Тот же процесс может быть выполнен для лидера, за исключением того, что при расчете его прибыли он знает, что фирма 2 будет играть в ответ выше, и поэтому это может быть подставлено в его задачу максимизации. Затем он может решить для ⁠ ⁠, взяв первую производную, что дает . Подставляя это в функцию наилучшего ответа фирмы 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}^{*})}$

Смотрите также

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

Ссылки

1. https://www.math.uni-hamburg/Бесконечные игры, Юрий Хомский (2010) Бесконечные игры (раздел 1.1), Юрий Хомский (2010)
2. "Бесконечные шахматы, PBS Infinite Series" PBS Infinite Series. Совершенная информация, определенная на 0:25, с академическими источниками arXiv :1302.4377 и arXiv :1510.08155.
3. Уотсон, Джоэл. (2013-05-09). Стратегия: введение в теорию игр . стр. 97–100. ISBN 978-0-393-91838-0. OCLC  1123193808.
4. Уотсон, Джоэл. (2013-05-09). Стратегия: введение в теорию игр . стр. 26–28. ISBN 978-0-393-91838-0. OCLC  1123193808.
5. Уотсон, Джоэл. (2013-05-09). Стратегия: введение в теорию игр . стр. 22–26. ISBN 978-0-393-91838-0. OCLC  1123193808.

• Харт, Серджиу (1992). "Игры в экстенсивных и стратегических формах". В Aumann, Robert ; Hart, Sergiu (ред.). Справочник по теории игр с экономическими приложениями . Том 1. Elsevier. ISBN 978-0-444-88098-7.
• Бинмор, Кеннет (2007). Игра по-настоящему: текст по теории игр . Oxford University Press US. ISBN 978-0-19-530057-4.
• Дрешер М. (1961). Математика стратегических игр: теория и приложения (Гл. 4: Игры в развернутой форме, стр. 74–78). Rand Corp. ISBN 0-486-64216-X 
• Fudenberg D и Tirole J. (1991) Теория игр (Глава 3 Игры в развернутой форме, стр. 67–106). MIT press. ISBN 0-262-06141-4 
• Лейтон-Браун, Кевин; Шохам, Йоав (2008), Основы теории игр: краткое междисциплинарное введение, Сан-Рафаэль, Калифорния: Morgan & Claypool Publishers, ISBN 978-1-59829-593-1. 88-страничное математическое введение; см. главы 4 и 5. Бесплатно онлайн. Архивировано 15 августа 2000 г. на Wayback Machine во многих университетах.
• Luce RD и Raiffa H. (1957). Игры и решения: введение и критический обзор. (Гл. 3: Расширенные и нормальные формы, стр. 39–55). Wiley New York. ISBN 0-486-65943-7 
• Osborne MJ и Rubinstein A. 1994. Курс теории игр (Гл. 6. Обширная игра с полной информацией, стр. 89–115). MIT press. ISBN 0-262-65040-1 
• Шохам, Йоав; Лейтон-Браун, Кевин (2009), Многоагентные системы: алгоритмические, игровые и логические основы, Нью-Йорк: Cambridge University Press , ISBN 978-0-521-89943-7. Подробный справочник с точки зрения вычислений; см. Главу 5. Можно бесплатно загрузить онлайн.

Дальнейшее чтение

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

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

• Нойманн, Дж. (1928). «Zur Theorie der Gesellschaftsspiele». Математические Аннален . 100 : 295–320. дои : 10.1007/BF01448847. S2CID  122961988.
• Гарольд Уильям Кун (2003). Лекции по теории игр . Princeton University Press. ISBN 978-0-691-02772-2.содержит лекции Куна в Принстоне с 1952 года (официально ранее не публиковавшиеся, но находящиеся в обращении в виде фотокопий)