5. Бескоалиционные игры icon

5. Бескоалиционные игры




Скачати 125.07 Kb.
Назва5. Бескоалиционные игры
Дата09.09.2012
Розмір125.07 Kb.
ТипДокументи

5. Бескоалиционные игры

5.1. Общие сведения

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

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

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

Определение 1. Бескоалиционной игрой называется игра I игроков (I2), каждый из которых имеет множество стратегий , с функцией выигрыша Нi(), , где  – ситуация, задаваемая на множество  декартового произведения стратегий і.

Определение 2. Бескоалиционная игра называется игрой с постоянной суммой, если существует такое постоянное С, что , для всех ситуаций .

Класс антогонистических игр является классом игр двух лиц с нулевой суммой.

Определение 3. Конечная бескоалиционная игра двух игроков с ненулевой суммой называется бимоптричной игрой.

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

Для класса антогонистических игр принципом оптимальности является принцип максимина.

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

Определение 4. Ситуация  в игре называется приемлемой для игрока і, если для любой его стратегии і

, (5.1.)

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

Определение 5. Ситуация в игре, приемлемая для всех игроков, называется ситуацией равновесия по Нэшу (равновесной ситуацией).

Иными словами, ситуация  называется равновесной, если для любого игрока іІ и выполняется условие (5.1.).

Из определения видно, что ни один из игроков не заинтересован в отношении от своей стратегии, образующих в совокупности ситуацию равновесия.

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

Поэтому в бескоалиционной игре решение игры – это чаще, нахождение ситуаций равновесия.

Пример 1. Игра “Семейный спор”

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

и ,

где стратегии игрока 1: А1 – выбираю футбол; А2 – иду на балет; игрок 2: В1 – иду на футбол, В2 – балет.

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

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

Хотя стратегии (А1В1) и (А2В2) являются оптимальными, поскольку даны максимальные выигрыши, однако приносят игрокам не одинаковые выигрыши, поэтому не являются справедливыми.

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

Действительно, если игроки не сообщаются до игры и оба обладают твердыми характерами, т.е. первый игрок выбирает стратегию А1, а второй – В2, то в результате они оба проигрывают. Аналогичная ситуация получиться и в том случае, когда каждый из игроков имеет мягкий характер и решает уступить. Так сочетание устойчивости со справедливостью вступает в противоречие с сочетанием устойчивости и выгодности.

Лучшим для игроков в рассматриваемой игре является договорный вариант (А1В1) или (А2В2), причем справедливым решением будет их выбор одного из этих вариантов путем бросания монеты. Выпадение герба будет означать, например, что семейство идет на матч по футболу, а решки – на балет.

В антогонистической игре в отличие от биматричной смысла вести переговоры до игры и уславливаться о совместной плане действий.

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


5.2. Ситуации, оптимальные по Парето

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

Другой вариант устойчивости ситуации в большей степени, чем равновесность, отражающей черты ее выгодности, состоит в ее оптимальности по Парето* .

Определение 6. Ситуация 0 в бескоалиционной игре называется оптимальной по Парето, если не существует ситуации , для которой имеет место векторное неравенство

для всех іІ. (5.2.)

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

подчеркнем различие ситуации равновесия от ситуации, оптимальной по Парето: в первой ни один игрок, действуя в одиночку, не может увеличить свой собственный выигрыш; во второй, – все игроки, действуя совместно, не могут (даже нестрого) увеличить выигрыш каждого.

Вопросы об оптимальных по Парето ситуациях решаются в принципе проще, чем аналогичные вопросы о ситуациях равновесия.

Проиллюстрируем графический метод определения ситуаций оптимальных по Парето. На рис. 5.1. изображено множество возможных стратегий 12 двух игроков. Каждой точке  соответствует тачка на множестве Н значений функций выигрышей Н1() и Н2() (рис. 5.2).


Н1


А


С




В


Н1(12)



Н

Рис. 5.1. Рис. 5.2.


На рис. 5.2 дуга АСВ соответствует множеству ситуаций оптимальных по Парето, так как никакими совместными усилиями игроков, нельзя увеличить выигрыш одного из них, не уменьшив при этом выигрыш другого.

Таким образом, ситуации, оптимальные по Парето, определяются положением вектора Н() в множестве всех допустимых векторов выигрышей, а для выяснения вопроса о равновесности ситуации требуется учитывать еще и зависимость каждой из компонентов Ні(), а другой игры с НІ()+b, то эти игры имеют одни и те же оптимальные по Парето ситуации. Рассмотрим пример для нахождения ситуации оптимальной по Парето.

^ Пример 2. Игра “Дилемма заключенного”.

Каждый из двух игроков располагает двумя стратегиями: А2 и В2 – стратегии агрессивного поведения, а А1 и В1 – миролюбивое поведение. Предположим, что “мир” (оба игрока миролюбивы) лучше для обоих игроков, чем “война” (один игрок агрессивный, а другой миролюбивый) выгоднее агрессору. Пусть матрицы выигрышей игроков 1 и 2 в данной биматричной игре имеют вид



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

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

Как видим, в отличие от примера 1 (игра “семейный спор”), где кооперация игроков была им выгодна, в этом примере кооперация не выгодна для игроков.


5.3. Состояние равновесия по Нэшу

Определение 7. Стратегии *і, в игре І лиц с ненулевой суммой называются оптимальными по Нэшу (решением по Нэшу или точкой равновесия по Нэшу), если для каждого

(5.3)



В рассмотренной игре “семейный спор” ситуации (А1В1) и (А2В2) являются решением по Нэшу, а в игре “дилемма заключенного” таковой является ситуация (А2В2).

Как и в играх двух лиц с нулевой суммой, игра І лиц с ненулевой суммой может не иметь решение по Нэшу в чистых стратегиях. Приведенное выше определение 7 решения по Нэшу в чистых стратегиях легко обобщается на случай смешанных стратегий путем подстановки смешанных стратегий вместо стратегии і 1,2, ....,І.

Дж. Нэшем было доказано существование ситуации равновесия в смешанных стратегиях для любой конечной бескоалиционной игры.

^ Теорема Нэша. В каждой бескоалиционной игре существует хотя бы одна ситуация равновесия в классе смешанных стратегий.

Если, кроме того, функции Нi() выпуклые вверх, то решение по Нэшу достигается в классе чистых стратегий.

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

Дж. Нэшем была доказана также следующая теорема.

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

Ее применение позволяет избежать отдельных ошибок при решении конечных бескоалиционных игр.

Одним из простых классов бескоалиционных игр ход решения которых поддается элементарному описанию являются биматричные игры.


5.4. Биматричные игры

Пусть в биматричной игре игрок 1 имеет m чистых Аі, , а игрок 2 == n чистых стратегий Вj, и в каждой ситуации (Ai, Bj) игрок 1 получает выигрыш aij, а игрок 2 – выигрыш bij. Значение обеих функций выигрыша игроков естественно представить в виде пары матриц



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


а11

b11


.........

a1n

b1n


........


.........


........

am1

bm1


.........

amn

bmn


где “северо-западное” число в каждой клетке обозначает выигрыш первого игрока, а “юго-восточное” – выигрыш второго игрока.

Смешанные стратегии X и Y, естественно, понимаются как векторы, причем

и .

Выигрыш игроков 1 и 2 при применении смешанных стратегий равны:



где Т – означает транспонирование, т.е. вектор строка записывается как вектор столбец.

Определение ситуации равновесия для случая биматричной игры приобретает следующую формулировку. Ситуация (X,Y) в биматричной игре с матрицами выигрышей А и В является равновесной, если

. (5.4.)

. (5.5.)

Очевидно, что при В = -А биматричная игра превращается в матричную.


5.5. Решение биматричных игр 2х2

Рассмотрим 2х2 биматричную игру с матрицами выигрышей

,

соответственно игроков 1 и 2. Как и в случае матричных игр, смешанные стратегии полностью описываются вероятностями p и q выбора игроками своих первых чистых стратегий (вторые чистые стратегии выбираются, очевидно, с вероятностями 1-p и 1-q.

Опишем порознь множество приемлемых ситуаций, для каждого из игроков и изобразим эти множества на единичном квадрате p,q, где p[0,1] и q[0,1].

Начнем с описания ситуаций, приемлемых в игре для игрока 1.

Приемлемость ситуации (X,Y) для игрока 1 в биматричной игре означает, что

(5.6)

(5.7)

где А1 и А2 – вектор строки, соответствующие первой и второй строке матрицы А, соответственно.

Подчеркнем, что эти условия приемлемости никак не связаны с матрицей В выигрышей игрока 2. Поэтому они будут совпадать с аналогичными условиями матричной игры с платежной матрицей А.

Приемлемость ситуации (X,Y) для игрока 2 означает, что

(5.8)

(5.9)

где В1 и В2 – вектор-столбцы, соответствующие первому и второму столбцу матрицы В, соответственно.

В общем случае, =Ip, 1 - pI, и рассмотрим три случая.

а) р = 1, (=|1,0|). Тогда выражение (5.6) превращается в тождественное равенство, а условием приемлемости данной ситуации для игрока 1 оказывается неравенство (5.7). Для рассматриваемого случая его можно записать как

(5.10)

б) р = 0 (=|1,0|). В этом случае выражение (5.7) превращается в тождественное равенство, а условием приемлемости данной ситуации для игрока 2 оказывается неравенство (5.6). Для рассматриваемого случая оно имеет вид

(5.11)

в) 0 р 1 (=Ip, 1 - pI). В этом случае оба неравенства (5.6) и (5.7) превращаются в равенство, и условием приемлемости становится

(5.12)

Опишем ситуации приемлемости (5.10), (5.11) и (5.12) в более явном виде.

Так как



то соотношения (5.10), (5.11) и (5.12) можно соответственно записать как

(5.14)

(5.15)

(5.16)

Таким образом, приемлемые для игрока 1 ситуации (X,Y) могут быть одного из трех типов:

(5.17)

(5.18)

(5.19)

Если величина а11 + а22 – а12 – а21 = 0, а а22 – а12  0, то (5.9) не имеет место, поэтому будет выполняться или (5.17) и (5.18), и притом со знаком строгого неравенства.

Если же а11 + а22 – а12 – а21 = 0 и а22 – а12 = 0, то все условия (5.17), (5.18) и (5.19) выполняются тождественно, и приемлемыми для игрока 1 будут вообще все ситуации.

Описание ситуаций приемлемости в более ясном виде для игрока 2 получаем аналогично из неравенств (5.8) и (5.9).

В общем случае Y=|q, 1-q|. Для трех случая получаем:

а) q=1 (Y=|1,0|). В этом случае приемлемость ситуации (X,Y) равносильна неравенству

(5.20)

или в более явном виде

|p, 1-p|

. (5.21)

б) q=0 (Y=|0,1|). В этом случае приемлемость ситуации (X,Y) определяется неравенством

(5.22)

или в более явном виде

. (5.23)

в) 0q1 (Y = |q,1–q|). Условие приемлемости

(5.24)

в развернутом виде

(5.25)

Таким образом, приемлемые для игрока 2 ситуации (X,Y) могут быть одного из трех типов:

(5.26)

(5.27)

(5.28)


* В. Парето – итальянский экономист.




Схожі:

5. Бескоалиционные игры icon5. Бескоалиционные игры
Антагонистические игры, которые рассматривались в предыдущих главах книги, описывают конфликты частного вида, которые не всегда адекватны...
5. Бескоалиционные игры icon5. Бескоалиционные игры
Антогонистические игры, которые рассматривались в предыдущих главах книги, описывают конфликты частного вида, которые не всегда адекватны...
5. Бескоалиционные игры icon5. бескоалиционные игры общие сведения
Антагонистические игры, которые рассматривались в предыдущих главах книги, описывают конфликты частного вида, которые не всегда адекватны...
5. Бескоалиционные игры icon5. бескоалиционные игры общие сведения
Антагонистические игры, которые рассматривались в предыдущих главах книги, описывают конфликты частного вида, которые не всегда адекватны...
5. Бескоалиционные игры iconДокументи
1. /возрастная психология/Абрамова Г. практикум по возраст психологии.doc
2. /возрастная...

5. Бескоалиционные игры iconДокументи
1. /возрастная психология/Абрамова Г. практикум по возраст психологии.doc
2. /возрастная...

5. Бескоалиционные игры iconДокументи
1. /возрастная психология/Абрамова Г. практикум по возраст психологии.doc
2. /возрастная...

5. Бескоалиционные игры iconДокументи
1. /возрастная психология/Абрамова Г. практикум по возраст психологии.doc
2. /возрастная...

5. Бескоалиционные игры iconДокументи
1. /возрастная психология/Абрамова Г. практикум по возраст психологии.doc
2.
5. Бескоалиционные игры iconДокументи
1. /возрастная психология/Абрамова Г. практикум по возраст психологии.doc
2.
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи