Лекция 1. Нормальная и развернутая формы игры

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

Теория игр условно делится на некооперативную и кооперативную части. В первой субъектом принятия решений служит индивид, во второй - группа или коалиция. В первой индивид характеризуется стратегиями и предпо­чтениями, во второй исходным материалом служат возможности коалиций. В первой индивиды принимают решения независимо (что не исключает пе­реговоров между ними), во второй допускается возможность обязывающих соглашений. Мы начнем и долгое время будем иметь дело с некооперативной частью. И лишь последние 5-6 лекций посвящены кооперативной теории.

Анализ конфликтной ситуации начинается с построения формальной мо­дели, т.е. превращения ее в игру. Есть несколько разных способов представления игры. Наиболее важные - развернутая (экстенсивная, или позиционная) и стратегическая (нормальная) формы, есть также Байесова форма. Начнем с более простой - нормальной формы.

Нормальная форма игры. Игра в нормальной (или стратегической) форме состоит из спецификации трех вещей:

1. Списка игроков,

2. Для каждого игрока задается список (множество) стратегий,

3. Для каждого профиля стратегий указывается профиль платежей (вы­игрышей) игроков.

Поясним смысл этих данных. Обозначим множество игроков через N. (Всюду ниже оно предполагается конечным и может быть отождествлено с

{1, 2,п}. Однако следует помнить, что такое упорядочение игроков - это некоторый волюнтаризм, и лучше представлять множество N неструктуриро-ваным.) Типичный игрок обозначается символом г. Далее, для каждого г £ N задается множество стратегий 5^; типичная стратегия - в^. Профиль страте­гий - это набор по стратегии для каждого игрока, т.е. вдг = (^ъ 52,вте); это элемент декартова произведения множеств .9 у = Х;^дч9;. Наконец, для каждого игрока указывается функция его выигрыша щ : 5дг —> К. (для про­стоты, можно считать, что выигрыш дается в рублях или долларах; позже мы вернемся к этому вопросу).

Неформально, каждый игрок выбирает некоторую стратегию 5^ £ ко­гда это сделают все, становится ясен его выигрыш Каждый игрок стремится получить выигрыш побольше. Основная трудность в том, что этот выигрыш зависит не только от его действий, но и от действий (стратегий) остальных игроков. И каждый игрок должен (или может) учитывать это в своем поведении. Можно сказать и так: в игре в нормальной форме игроки стратегически независимы, они могут выбирать любые стратегии, но остают­ся связанными через полезности. К центральному вопросу о том, как будут вести себя игроки, мы еще вернемся, а пока займемся чисто постановочной задачей.

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

1. Орлянка (или матч пенни)

 

и

t2

 

1,-1

-1,1

б2

-1Д

1,-1

Это пример игры с т.н. нулевой суммой. 2. Дилемма заключенных

 

и

t2

 

5,5

-1,6

б2

6,-1

0,0

Первые стратегии можно назвать "кооперативными", вторые - эгоистически­ми. К такой игре приводит простейший вариант дуополии, когда первые стра­тегии - высокие цены, а второй - низкие.

3. Семейный спор (или перекресток, или чикен)

 

и

\,2

 

5,4

б2

0,0

4,5

Неформально: первый игрок - муж, второй - жена. Первые стратегии - идти на бокс, вторые - в театр. Мужу больше хочется пойти на бокс, жене - в театр, но им лучше вместе.

В совсем утрированном виде эта игра превращается в игру координации ("встреча в Нью-Йорке") с таблицей

1—1

1—1

0,0

0,0

1—1

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

Вот простейшая позиционная игра. Игра начинается в позиции, где пер­вый игрок выбирает ход: вверх или вниз. Потом ходит второй - направо или налево, и игра заканчивается. Дерево игры выглядит так:

2 Я

(0,0) ^-^0—^— (2,0)

Более сложный пример представляет игра в крестики-нолики на доске 3 х 3. В начальной позиции у первого игрока 9 ходов, затем у второго по 8 ходов в каждой из этих 9 позиций, затем у первого игрока по 7 ходов в каждой из получающихся 72 позиций, и т.д.

Стратегии. Казалось бы, что в игре в развернутой форме действия од­ного игрока ограничивают возможности другого. Это действительно верно в отношении ходов. Однако если мы правильно определим понятие стратегии, мы получим стратегическую независимость и, тем самым, игру в нормаль­ной форме. Что назвать стратегией для позиционной игры? Каждый игрок в каждой позиции, которой он управляет, должен указать некоторый ход. Та­ким образом, у него "много" стратегий (прикиньте приблизительно, сколько их в игре "крестики-нолики"). Если все игроки выбрали по стратегии, то из каждой (нетерминальной) вершины выходит указанный ход, и можно дви­гаться от корневой вершины по этим отобранным стрелкам. В конце концов мы доберемся до конечной (терминальной) вершины (если дерево конечно, что молчаливо предполагается), а там указаны выигрыши.

Тем самым, по каждой позиционной игре можно канонически построить игру в нормальной форме.

Однако мы сразу видим, что ни одну из форм 1, 2, 3 нельзя представить как позиционную игру. Почему? Дело в том, что в этих играх игроки делают ходы одновременно, и никто не знает, кто какой выбрал ход. А в позиционных порядок ходов четко определен, и второй игрок знает, что сделал первый. Игроки в нормальной форме не знают, что выбрали другие. Чтобы учесть такое "незнание", нужно модифицировать развернутую форму игры, введя туда "информационные множества".

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

Но если игрок не может различить позиции, то и ходы, возможные в этих позициях, должны быть "одинаковыми". Более точно, для каждого инфор­мационного множества к должно быть указано соответствующее множество М(К) "ходов", а также для каждой вершины х £ к "реализация" множества

М(к) стрелками, выходящими из х. Находясь в любой позиции х £ /г, игрок выбирает ход т £ М(к). Грубо говоря, ход игрока должен быть одним и тем же во всех "неразличимых" для него позиций. Поэтому мы должны модифи­цировать понятие стратегии: это выбор хода для каждого информационного множества, контролируемого игроком. С учетом этого замечания мы опять по развернутой форме можем построить нормальную форму. И теперь уже любая игра в нормальной форме может быть представлена (неоднозначно!) игрой в развернутой форме. Мы оставляем без ответа тонкий вопрос - экви­валентны ли различные "развернутые" представления одной и той же "нор­мальной" формы.

Формальное описание игры в развернутой форме. После преды­дущих неформальных объяснений пора дать точное определение (а заодно и ввести обозначения, которыми мы будем дальше пользоваться) этого до­вольно запутанного понятия. Игра в развернутой форме состоит из четырех вещей: а) дерева игры Г, Ь) распределения вершин-позиций по игрокам, с) ин­формационных разбиений позиций каждого игрока, с!) выигрышей. Уточним каждый пункт.

a) Дерево игры Г состоит из (конечного) множества вершин (позиций) X и множества стрелок А С X х X. Множество стрелок, выходящих из вершины х, обозначается А(х). Кроме того есть выделенная "начальная" позиция (ко­рень дерева). Предполагается, что, выходя из корня и двигаясь по стрелкам, можно достичь любой позиции и притом единственным образом.

b) Порядок ходов. Вершина х £ X называется терминальной, если А(х) = 0. Множество терминальных вершин обозначим Т. Порядок ходов задается отображением ь : X \Т —>■ X, где N - множество игроков. Для игрока г £ N обозначим через Х,-ь = £-1(г) множество позиций, "контролируемых" данным игроком.

c) Информация. Для каждого игрока г задано разбиение множества Х^ на "информационные множества". Типичный элемент этого разбиения (то есть информационное множество) обозначается /г; а множество таких множеств как Щ. Таким образом А", = Ц/^//(// . Далее, для каждого к задано множество М(к) ходов (или их "меток"), доступных в информационном множестве к. Наконец, для каждой позиции х £ к задано отображение ах : М(к) —У А(х).

с!) Выигрыши. Для каждой терминальной вершины t £ Т указан вектор и(€) = (щ^)) £ М^. /-ия координата щ(€) этого вектора специфицирует вы­игрыш, который получает игрок г, если игра заканчивается в позиции 1.

Игра в нормальной форме, связанная с развернутой формой, определяется так. Множество стратегий г-го игрока - 5^ = Х/1€я^М(^)- Если все игроки определились со своими стратегиями, мы снова получаем, что из каждой (нетерминальной) вершины х выходит одна отмеченная стрелка ах{К), где к - это то единственное информационное множество, которое содержит X. И снова, двигаясь из корня по этим отмеченным стрелкам, мы добираемся до терминальной вершины и получаем профиль платежей.

Если разные вершины имеют разные информационные метки (то есть фак­тически если мы имеем дело с позиционной игрой), то говорят об игре с совер­шенной информацией. Это наиболее простые игры; такими являются шашки, шахматы, но не карточные игры.

Приведенная нормальная форма. Приведем удобный способ записи стратегий. До­пустим, что нам нужно записывать стратегии второго игрока. Тогда пометим символами 2, 2', 2" и т.д. все информационные множества этого игрока (желательно по мере удален­ности их от корня). Допустим, А, В, С,... - символы ходов в информационном множестве 2, а, Ь, с,... - в 2', а, /3,7,в 2" и т.д. Тогда стратегии второго игрока - это последователь­ности вида Ни-.... Аа/3... и т.п. Пользуясь таким представлением, вы не будете путаться между ходами и стратегиями и правильно представлять себе число последних.

Ясно, что в общем случае число стратегий "большое". Заметим, однако, что многие стратегии являются "эквивалентными". Рассмотрим, например, игру (в развернутой фор­ме), где первый игрок может пойти наверх (II), и тогда игра заканчивается, или пойти вниз и после этого ходит второй, затем снова первый и т.д. Формально у первого игрока имеется масса стратегий вида I..... где ... указывают его действия в "нижних" позициях (или информационных множествах). Но совершенно ясно, что ни на что эта специфика­ция "нижних" действий или ходов не влияет. В принципе, для многих вопросов достаточно было бы рассмотреть одну "склеенную" стратегию II.

Гибридная форма игры. Кроме нормальной и развернутой формы иногда быва­ет полезной гибридная форма. Взглянем на позиционную игру. Фактически в каждой позиции этой игры происходит как бы миниигра одного игрока, который выбирает ход. Остальные игроки в этот момент как бы не участвуют (или участвуют фиктивно). Идея состоит в том, чтобы в каждой (нетерминальной) позиции х разыгрывалась своя мини-игра в нормальной форме С(х) с множествами стратегий «^(ж), г е N. Единственная отличие состоит в том, что вместо отображения выигрышей тут задается отображение ах : Б^(х) —У А(х). То есть результат этой игры - следующая позиция на дереве игры Г.

Контрольный вопрос - как по гибридной игре построить игру в нормальной форме?

Кстати, то, что структура игры задается деревом, не так уж и важно. Важно только то, что двигаясь от корня по стрелкам, мы рано или поздно упираемся в терминальную вершину.

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

Некоторый "наблюдатель" интересуется "состоянием" природы; множество возможных состояний обозначим X. У него есть "прибор", который выдает некоторый сигнал или сооб­щение. Работа этого прибора описывается отображением / : X —У М, где М - множество возможных сообщений. Получив какой-то сигнал т, наблюдатель понимает, что "приро­да" находится в состоянии из подмножества /_1(т) С X. А сам прибор задает разбиение Р$ множества X на "информационные множества" /_1(т), т е М. (Реально все конечно сложнее - мы можем не знать точно функцию /. и сигналы воспринимать с искажениями, но пока отвлечемся от этого.)

Вместо разбиений Р (или приборов /) можно работать с отношениями эквивалентно­сти. Скажем, что состояния х и у эквивалентны ("неразличимы" прибором /, х ~ у), если /(х) = /(у). Тогда разбиение - это разбиение на классы эквивалентности. А сам "при­бор" можно восстановить как каноническое отображение X на множество X/ ~ классов эквивалентности.

Наконец, можно говорить в терминах Булевых алгебр. Подмножество А С X назо­вем измеримым, если оно составлено из некоторых информационных множеств (или, в терминах отношения эквивалентности, если х е А и у ~ х следует, что у & А). Измери­мые подмножества замкнуты относительно объединений, пересечений и дополнений, то есть образуют Булеву алгебру. Обратно, если дана Булева алгебра В подмножеств X. мы можем восстановить отношение эквивалентности ~, полагая х ~ у в том случае, если у принадлежит любому А е В, содержащему х.

Отображение д : X —У М' называется измеримым (относительно Булевой алгебры В), если /_1(т') е В для любого т! е Л/'. Легко понять, что д измеримо относительно алгебры В$.; построенной по прибору /, тогда и только тогда, когда д пропускается через /, то есть является композицией / с некоторым отображением М —у Л/'.

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

Мы предоставляем читателю модифицировать данное выше определение гибридной формы с учетом несовершенной информированности игроков.

Случайные ходы. Имеется еще один источник неопределенности игроков относительно состояния позиции - случай. Например, в карточных играх игроки обычно не знают карты партнеров (недаром их тщательно перетасо­вывают перед раздачей), и это тоже нужно отразить в описании игры. Одна­ко, в отличие от предыдущей неопределенности, эта неопределенность носит вероятностный характер и имплантируется сравнительно легко. Формально просто к списку игроков добавляется фиктивный игрок - природа, которая тоже выбирает свои ходы, но делает это не свободно, как обычные игроки, а с предписанными вероятностями.

Для примера рассмотрим следующую пародию на "покер". Первый игрок (Ваня) получает карту, которая в 1/6 случаев благоприятна для него. По­смотрев карту, он может либо "повысить ставку" (Д), либо "спасовать" (Р). Во втором случае игра заканчивается, и Ваня отдает второму игроку (Маше) 10 р. В первом случае Маша, не видя карты, может либо "принять повыше­ние" (г), либо тоже "спасовать" (р). Выигрыши Вани (так как игра с нулевой суммой) в различных ситуациях приведены на рисунке ниже

-10 -10

 

Здесь у Вани два информационных множества 1 и 1', а у Маши - одно (так как она не видит карту).

Можно ли по такой игре образовать нормальную форму? Со стратегиями особых проблем нет. Снова каждый игрок должен решить, как он ведет се­бя (какой ход выбирает) в каждом своем информационном множестве. Ваня должен решить - что он делает при хорошей карте (в позиции 1) и что - приплохой, в позиции V. Так что у него 4 стратегии: RR!, RP', PR' и РР'. У Маши - две стратегии: г и р.

А вот с выигрышами возникает некоторая проблема. Допустим, Ваня вы­брал стратегию RR', а Маша - г. Если карта хорошая, Ваня получает 90 р., если плохая - теряет 60 р. Как же оценить его выигрыш? Простейший выход - посчитать математическое ожидание 90 • 1/6 — 60-5/6 = —35. Аналогично можно заполнить остальные клеточки.

Однако насколько правильно брать математическое ожидание? К этому вопросу мы вернемся на лекции 3. А пока освоимся с лотереями.