WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 8 | 9 || 11 | 12 |   ...   | 15 |

В разделе 3.12 был рассмотрен случай, когда у исследователя Из рисунка 7 видно, что РДС и сильное равновесие Нэша явнет полной информации о типах игроков, однако, предполагалась ляются самыми сильными концепциями решения: из того, что сиполная информированность игроков о параметрах функций вытуация равновесна в доминантных стратегиях, следует, что она игрыша.

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

сколько оправдывается его логической простотой. «Золотой серединой» в некотором роде, является равновесие Нэша в смешанных 4.1. Принцип максимального стратегиях. Выше доказано (см. теорема 3) существование, по гарантированного результата крайней мере, одной равновесной ситуации для достаточно широПринцип максимального гарантированного результата кого класса игр. В то же время, эта концепция достаточно строгая:

(МГР) – это один из самых общих принципов принятия решений в множество равновесий Нэша обычно гораздо уже, чем можно поусловиях интервальной неопределенности. В соответствии с принлучить, удаляя доминируемые стратегии. Эти преимущества и опципом МГР неопределенность устраняется введением предположеределили популярность равновесия Нэша при решении приклад 85 ния, что неопределенные параметры принимают наихудшие для гией i-го игрока в игре с полной информированностью будет страЛПР значения. тегия Определения принципа МГР для очень широкого класса игр yi* Arg max[ min Ki ( y1,..., yn )].

yiAi y-i A-i можно найти в [21]. Приведем некоторые из них.

Для существования гарантирующей стратегии достаточно Пусть игровая ситуация с точки зрения i-го игрока определяограниченности функции выигрыша игрока и компактности ется вектором z = (yi,, r), yi Ai,, r, и его выигрыш множеств стратегий Ai и множеств типов игроков i [21], поэтому Ki = Ki(z) зависит от ситуации. Пусть yi Ai – действие i-го игроможно говорить, что гарантирующие стратегии существуют ка, и на момент принятия игроком решения о выборе стратегии «почти всегда».

ему известны значения параметров. Об остальных параЕще одним преимуществом МГР является то, что для вычисметрах информации не ожидается. Тогда принцип МГР предлагает ления гарантирующей стратегии игрока i достаточно знать только использование, так называемой, гарантирующей стратегии.

функцию его выигрыша, и не нужно знание функций выигрыша Определение 20: Гарантирующая стратегия i-го игрока – это других игроков.

стратегия, определяемая по формуле:

Недостатком МГР является его чрезмерная пессимистичность.

yi*( ) Arg max[min Ki ( yi,, r)].

yi Ai r МГР призывает игрока рассчитывать на наихудшее для него поведение противников. Это оправданно в случае антагониДругими словами, для того, чтобы найти гарантирующую стических игр, но, если игрок знает, что интересы противников стратегию i-го игрока, необходимо при фиксированных известных лишь ненамного отличаются от его интересов, предположение о параметрах найти минимум функции выигрыша по неизвестным том, что рациональные противники будут выбирать наихудшее для параметрам r, а затем максимизировать результат миниминего действие, не всегда адекватно.

зации выбором действия yi. Стратегия y* (), на которой i достигается максимум, и будет гарантирующей.

4.2. Байесовы игры, равновесие Байеса Вектор ( y* () )i N гарантирующих стратегий игроков назыi Если принцип МГР используется в случае интервальной невается максиминным равновесием.

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

игре в форме Байеса (или байесовой игре). Байесова игра форРассмотрим с этой точки зрения игру с неполной информацией.

мально определяется следующим образом [82].

Пусть имеется n игроков. Игрок i имеет тип ri i, принадПусть на момент принятия решения каждому игроку известен лежащий множеству возможных типов i данного игрока. Кажего тип ri i, неизвестны типы других игроков rj j (j i) и их дый игрок знает все множества {i}, а также функцию представстратегии. Если Ki(y1, …, yn, r1, …, rn) – функция выигрыша i-го лений, (или, иначе, вер) игрока pi(r-i|ri), описывающую плотность игрока, то его гарантирующей стратегией будет стратегия условной вероятности появления некоторого сочетания (профиля) типов других игроков в зависимости от типа игрока i. Функции y* (ri ) Arg max[ min Ki ( y1,..., yn, r1,...,rn )], i N.

i yi Ai y-iA-i, r-i -i выигрыша Ki = Ki (y1,...yn, r1,..., rn ) зависят как от действий Можно заметить, что приведенное определение подходит и для игр с полной информированностью – гарантирующей страте 87 2-й игрок yi Ai всех игроков, так и от их типов ri i, и известны всем игрокам.

1-й игрок Определение 21: Игра в форме Байеса задается следующей системой: {N;1,...,n; p1(),..., pn (); K1(),..., Kn ()}.



Рассмотренный выше пример «Аукцион» представляет собой 2-й игрок игру в форме Байеса. В этом примере каждый из двух игроков знает функцию выигрыша противника с точностью до некоторого параметра.

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

1-й игрок раздел 1.1) Ответ на этот вопрос дает концепция равновесия Байеса. Стратегией игрока i в данной игре будем считать распределение i =i (yi | ri ) условной вероятности выбора действия yi при условии, что тип игрока равен ri. Тогда равновесием Байеса B B считается такой набор стратегий (1B (.),2 (.),...,n (.)), что для любого игрока i и любого его типа ri i стратегия iB (.) максимизирует по i (.) функционал B Ki ( yi, y-i, ri, r-i ) pi ( r-i ri ) i ( yi ri ) ( y rj ) dy dr-i, j j Рис. 8. Игра с неполной информацией ji -i X представляющий собой ожидаемый выигрыш игрока i с учетом его Равновесие Байеса является обобщением равновесия Нэша в субъективного представления о типах других игроков.

смешанных стратегиях на случай байесовых игр. На самом деле, В этом определении решением считается, по сути, набор оно представляет собой равновесие Нэша игры, в которой неполсмешанных стратегий. Можно переопределить равновесие Байеса ная информация о целевых функциях игроков заменена на недля чистых стратегий. Тогда стратегией будем считать функцию полную информацию о ходе природы. Д. Харшаньи [75] предлоyi = i(ri), которая предписывает игроку действие yi в зависимости жил считать, что в начале байесовой игры природа (или другие от его типа ri i. В этом случае равновесие Байеса определяется внешние обстоятельства) определяет типы игроков. После этого B B набором стратегий (1B (), 2 (),...,n ()), таким, что для любого игроки должны, зная свой тип, но не зная типов противников, выбрать стратегию (см. рисунок 8).

игрока i и любого его типа ri i стратегия iB (ri ) максимизиПредставление этой игры в развернутой форме для двух игрорует по i функционал ков, каждый из которых имеет два возможных типа (r11, r12 для B Ki (r-i, ri,-i (r-i ),i ) pi (r-i | ri )dr-i.

первого игрока, r21, r22 - для второго), и два возможных действия -i (y11, y12 – у первого игрока, y21, y22 – у второго) приведено на рисунке 8. Для нахождения равновесий байесовой игры необходимо 89 y y y y y y r y, y r y y y r, y r y r, r y y y r y, r y y y y y y y построить игру в развернутой форме, аналогичную изображенной В примере 5 рассматривалась игра с биматрицей на рисунке. Далее, эту игру необходимо привести к нормальной [ сотр. эгоист.] форме с помощью процедуры, описанной в разделе 3.3, и для игры сотр. 10,10 - 5,15.

в нормальной форме найти множество равновесий Нэша в смеэгоист15, - 5 0, шанных стратегиях.

Такая схема построения байесового равновесия подходит Выше было показано, что единственное равновесие Нэша лишь для дискретных множеств типов игроков. Кроме того, необ- («эгоист.», «эгоист.») этой игры не оптимально по Парето. В то же ходимо, чтобы представления игроков были совместны, то есть, время, в реальной жизни подобные конфликты зачастую разчтобы существовало некоторое априорное вероятностное распре- решаются довольно эффективно. Дело в том, что на практике в деление p(r1,…, rn) типов игроков, из которого представления ка- подобных ситуациях у игроков имеются и другие способы повеждого игрока получались бы по формуле условной вероятности: дения, помимо одновременного выбора одной из двух своих стратегий. Модифицируем игру следующим образом: добавим кажpi (r-i | ri ) = p(r1,...,rn ) / p(ri, s-i ).

s-i дому игроку дополнительную стратегию «договор» и доопределим Зато для этого класса игр существование байесового равноматрицу выигрышей следующим образом:

весия следует непосредственно из теоремы о существовании рав[сотр. эгоист. договор] новесия Нэша.

сотр. 10, 10 - 5, 15 5, эгоист.15, - 5 0, 0 0, ГЛАВА 5. КООПЕРАТИВНЫЕ ИГРЫ 15, 5 0, 0 10, договор Содержательно дополнительную стратегию можно проин5.1. Виды взаимодействия игроков терпретировать следующим образом: первый начальник, выбрав В предыдущих главах были рассмотрены некооперативные эту стратегию, предлагает второму заключить совместный договор игры, то есть игры, в процессе которых игроки не могут действо(обычно называемый в таких случаях положением о должностных вать совместно. При этом под совместными действиями может полномочиях), который бы регламентировал время, которое подразумеваться добровольный обмен между игроками информаподчиненный тратит на работы каждого начальника. В случае, цией о выбранных стратегиях, о функциях выигрыша, о других если второй начальник отвергнет договор, выбирая «эгоистичепараметрах игры, совместный выбор стратегий, передача игроскую» стратегию (ситуация («договор», «эгоист.»)), первый ками части выигрыша друг другу. Этот подход вполне оправдыначальник угрожает также применить «эгоистическую» стратегию, вает себя в целом ряде практически важных случаев. Однако, зачто приводит к нулевым выигрышам для обоих. Если второй частую способность игроков к совместным действиям является начальник выбирает безусловное сотрудничество (это ситуация неотъемлемой частью конфликтной ситуации. Примером подоб(«договор», «сотр.»)), договор будет подписан на условиях, более ных конфликтов являются задачи дележа (см. пример «Дележ в выгодных для первого начальника. Если же оба начальника оркестре»). Исследование этих задач требует учета переговорных одновременно выходят с инициативой подписания договора (сипроцессов между игроками. Для этого необходимо изменить мотуация («договор», «договор»)), их выигрыши равны выигрышам дель игры.





при одновременном сотрудничестве.

Пример 17. Парето-оптимальное равновесие в примере как результат кооперации игроков.

91 В этой игре уже две ситуации равновесия Нэша, («эгоист.», Игры, в которых игроки могут образовывать коалиции полез«эгоист.») и («договор», «договор»), причем вторая доминирует по ности, называются играми с трансферабельной полезностью (ТППарето первую. Кроме того, можно заметить, что, при «эгои- играми). В отличие от них, игры, в которых игроки могут образостической» стратегии второго начальника, первому безразлично, вывать только информационные коалиции, называются играми с «эгоистическую» ли стратегию выбирать, или «договор». Но если нетрансферабельной полезностью (НТП-играми). Исследование он выберет «договор», стратегия «договор» станет выгодной и ТП- и НТП-игр исторически происходило параллельно, однако, второму начальнику. Дело в том, что «эгоистическое» равновесие – теория НТП-игр технически гораздо сложнее, поэтому ниже это нестрогое равновесие Нэша, в отличие от «договорного». ограничимся рассмотрением только ТП-игр. С результатами теории НТП-игр можно ознакомиться в [46].

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

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

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

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

иная коалиция.

93 5.2. Переход от нормальной формы игры Супераддитивные игры представляют собой, в некотором рок игре в форме характеристической функции де, типичный случай. Действительно, пусть есть коалиции S и T с их выигрышами v(S) и v(T). Что мешает образующейся коалиции Игра в форме характеристической функции может быть построена на основе игры в нормальной форме. Так обычно и прихо- ST действовать так, как если бы такого объединения не сущестдится делать, потому что даже кооперативные игры обычно вовало Тогда полезность этой коалиции будет как минимум равна формулируются сперва в нормальной форме – перечислением сумме полезностей коалиций S и T, обеспечивая супераддитивстратегий игроков и их функций выигрыша. ность. Это – нестрогие рассуждения и, как будет показано ниже, они верны лишь при соответствующих предположениях.

Характеристическая функция определяет выигрыш, получаемый коалицией S (если в процессе игры такая коалиция обра- Классическая теория рассматривает, в основном, супераддизовалась) при рациональных действиях ее участников. Что пони- тивные игры. Главными вопросами, которые встают при их исмать в каждом конкретном случае под рациональными действиями следовании – это вопросы об условиях реализуемости и устойчиигроков, должно быть понятным из постановки игры в нор- вости максимальной коалиции и «справедливом» распределении мальной форме и выбранной модели рационального поведения выигрыша v(N) между игроками.

(см. главы 3 и 4).

Pages:     | 1 |   ...   | 8 | 9 || 11 | 12 |   ...   | 15 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.