5. бескоалиционные игры общие сведения icon

5. бескоалиционные игры общие сведения




Скачати 255.62 Kb.
Назва5. бескоалиционные игры общие сведения
Дата20.09.2012
Розмір255.62 Kb.
ТипДокументи



Наша справа”, №4’2000

5. БЕСКОАЛИЦИОННЫЕ ИГРЫ

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


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

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

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

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

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

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

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

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

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

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

, (5.1)

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

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

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

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

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

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

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

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

и ,

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

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

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

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

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

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

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

^

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


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

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

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

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

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

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

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

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





Рис. 5.1 Рис. 5.2

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

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

,

где , .

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

Для однородно аффинно эквивалентных игр ki=k, iN.

Очевидно, что для антагонистических игр понятия аффинной эквивалентности и однородной аффинной эквивалентности совпадают.

Теорема 1. Всякая бескоалиционная игра с постоянной суммой аффинно эквивалентна некоторой игре с нулевой суммой.

Теорема 2. Аффинно эквивалентные игры имеют одни и те же оптимальные по Парето ситуации.

Рассмотрим пример для нахождения ситуации оптимальной по Парето.

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

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

, .

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

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

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

^

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


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

, (5.3)

x

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

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

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

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

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

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

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

Если, кроме того, функции Н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 при применении смешанных стратегий равны:



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

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

. (5.4)

. (5.5)

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

В качестве примера рассмотрим биматричную игру «Торг».

Пример. Игра «Торг»

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

Платежные матрицы игроков имеют вид:







Игрок 2







В1 - покупка

В2 - отказ


Игрок 1

А1 – Высокая цена

10

5

0

0




А2 – Низкая цена

5

10

0

0

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

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

^

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


Рассмотрим вначале биматричную игру 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)

Неравенства (5.17) и (5.18) верны в случае, если а11 + а22 – а12 – а21 > 0. Если а11 + а22 – а12 – а21 < 0, то знак неравенства в соотношениях (5.17) и (5.18) необходимо поменять на противоположный.

Если величина а11 + а22 – а12 – а21 = 0, а а22 – а12  0, то (5.19) не имеет место, поэтому будет выполняться или (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.26) и (5.27) справедливы, если их знаменатель больше нуля. Если в11 + в22 – в12 – в21 < 0, то знак неравенства в выражениях (5.26) и (5.27) необходимо поменять на противоположный.

Для определения ситуаций, приемлемых одновременно как для первого, так и для второго игроков, удобно все найденные приемлемые ситуации представить на единичном квадрате (рис. 5.3).









Рис. 5.3


Для случаев, когда а11 + а22а12а21  0 и b11 + b22b12b21  0 приемлемые ситуации игроков 1 и 2 составляют трехзвенные зигзаги. Причем, ситуации равновесия во вполне смешанных стратегиях игрока 2 совпадают с поведением игрока 2 в матричной игре с матрицей выигрыша А, а поведение игрока 1 – с поведением игрока 1 в матричной игре с матрицей выигрышей В.

Таким образом, описанное равновесное поведение игроков оказывается ориентированным не столько на максимализацию собственного выигрыша, сколько на минимизацию выигрыша противника. Так, “антагонизм поведения” может возникнуть и при отсутствии “антагонизма интересов”.

В приведенном на рис. 5.3 решении игры три ситуации равновесия, соответствуют точкам R1, R2, R3.

Если бы зигзаги приемлемых ситуаций были одинаковой ориентации, как показано на рис. 5.4, то пересечение приемлемых ситуаций игрока 1 и игрока 2 состояло бы из одной точки R.




Рис. 5.4


При решении биматричных игр большей размерности необходимо решать большую систему линейных неравенств, определяемых выражениями (5.6), (5.7) и (5.8), (5.9), а затем таким же конечно-рациональным путем находить точки пересечения приемлемых ситуаций игрока 1 и игрока 2. Причем, любая конечная бескоалиционная игра имеет конечное и нечетное чисто ситуаций равновесия (решений игры). Поиск ситуаций равновесия в этом случае следует осуществлять с применением ПЭВМ.

^

5.5. Пример решения биматричной игры


Формулировка игры “Борьба за рынки”

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

Пусть проникновение игрока 1 на первый рынок более выгодно для него, чем проникновение на второй, но борьба за первый рынок требует больших средств. Например, победа игрока 1 на первом рынке принесет ему вдвое больший выигрыш, чем на втором, но зато поражение на первом рынке полностью его разоряет (проигрыш равен 10), а игрока 2 избавляет от конкурента (выигрыш равен 5).

Описанная биматричная игра может быть задана матрицами выигрышей



Решение игры. В соответствии с выражениями (5.6) и (5.7) приемлемыми ситуациями для игрока 1 будут те, которые удовлетворяют условиям



Рассмотрим три случая:

а) р=1 (X=|1, 0|). В соответствии с выражением (5.10) имеем



Откуда .

б) р = 0 (X=|0, 1|). В соответствии с выражением (5.11) имеем



или .

в) 0 р1 (X=|р, 1 – р|). В соответствии с выражением (5.12) или в развернутом виде (5.19) получаем



Приемлемые ситуации для игрока 2 в соответствии с выражениями (5.26), (5.27) и (5.27) следующие:

а)

б)

в)

Множества всех приемлемых ситуаций игрока 1 и игрока 2 изображены на рис. 5.5 (для игрока 2 соответствующее множество показано пунктиром).







Рис. 5.5

Зигзаги приемлемых ситуаций пересекаются в единственной точке , которая и оказывается единственной ситуацией равновесия. Эта ситуация равновесия является ситуацией равновесия в смешанных стратегиях. Таким образом, оптимальными стратегиями по Нэшу являются и . При этом цена игры для игрока 1

.

Цена игры для игрока 2

.

^

5.6. Метастратегии и метарасширения


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

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

Определение 9. В бескоалиционной игре всякая функция Fkij : Xk  Xj (которая исходя из стратегии Xk игрока k определяет стратегию Xj игрока j называется метастратегией игрока j (в ответ на стратегию игрока k).

Содержательно всякую метастратегию Fkij можно понимать как способ выбора игроком j некоторой своей стратегии в зависимости от получаемой им информации о стратегии, выбираемой игроком k. Если рассматривать ситуацию в бескоалиционной игре как некоторое соглашение, некоторый договор между игроками, а общую стратегию – как принимаемое на себя в договоре обязательство, то метастратегию можно понимать как своего рода условное обязательство: “в случае если игрок k поступит так-то, я, игрок і, выбираю такую-то свою стратегию, а если этак-то, то такую-то”.

Очевидно, множество всех метастратегий і в ответ на стратегию k можно изобразить в степени множеств .

Определение 10. Бескоалиционные игры G, с тем же множеством игроков N, что и игра  называется метаигрой над игрой  (метарасширением игры Г), если для некоторых j, kN



и для любой метастратегии yiYi и любого игрока іI

,

где xk – стратегия игрока k, входящая в ситуацию , Н – функция выигрышей в игре Г.

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

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

Теорема 3. Каждая конечная бескоалиционная игра двух лиц имеет в своем первом метарасширении ситуации равновесия.

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

Теорема 4. Каждая конечная бескоалиционная игра двух лиц имеет в своем третьем метарасширении ситуацию, которая является одновременно ситуацией равновесия и оптимальной по Парето.

Пример. Биматричная игра 2х2 имеет следующие матрицы выигрышей игроков А и В:



В соответствии с выражениями (5.17), (5.18) и (5.19) находим приемлемые ситуации (X,Y) игрока 1:

а) (q может быть в любом интервале [0, 1];

б) (ситуация невозможна);

в) (ситуация невозможна).

В соответствии с выражениями (5.25), (5.27) и (5.28) находим приемлемые ситуации (X,Y) игрока 2:

а) (р может быть любым в интервале [0, 1];

б) (ситуация невозможна);

в) (ситуация невозможна);

Для наглядности на рис. 5.6 изображены зигзаги, описывающие и невозможные ситуации за пределами допустимых изменений вероятностей p,q).




Рис. 5.6

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

Множество всех реализуемых векторов выигрышей для рассматриваемой игры имеет вид, изображенный на рис. 5.7.


Рис. 5.7

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

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

Первая метастратегия игрока 2 состоит в выборе им своей второй стратегии в ответ на вторую стратегию игрока 1 и первой стратегии в ответ на первую.

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

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

ТЕСТЫ


(В – Верно, Н – Неверно)


  1. В бескоалиционных играх могут рассматривать конфликты двух и более игроков.

  2. В бескоалиционных играх могут рассматриваться конфликты только с нулевой суммой.

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

  4. В бескоалиционных играх принцип максимина не всегда является принципом, по которому находится решение игры.

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

  6. В бескоалиционных играх как оптимальные следует квалифицировать не действия того или иного игрока, а совокупность действий всех игроков.

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

  8. Игроку в бескоалиционной игре может быть выгодным информировать противника о своей стратегии.

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

  10. Ситуации равновесия не отличаются от ситуаций оптимальных по Парето.

  11. Ситуации оптимальные по Парето находить труднее, чем ситуации равновесия в той же бескоалиционной игре.

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

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

  14. Любая конечная бескоалиционная игра имеет конечное и четное число ситуаций равновесия.

  15. Метастратегия понимается как способ выбора игроком j своей стратегии в зависимости от получаемой им информации о стратегии, выбираемой игроком k.

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

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


(Ответы: 1 – В; 2 – Н; 3 – В; 4 – В; 5 – В; 6 – В; 7 – В; 8 – В; 9 – Н; 10 – Н; 11 – Н; 12 – В; 13 – В; 14 – Н; 15 – В; 16 – В; 17 – В.)

ЗАДАЧИ



І. Найти ситуации оптимальные по Парето и ситуации устойчивые по Нэшу для следующих биматричных игр:

1.

2.

3.

4.

5.

6.

7.

8.

ІІ. Решить бескоалиционную игру “Экологический конфликт”.

Формулировка игры. Два промышленных предприятия (А и В), расположенные вблизи обширного водоема, берут из него воду для технических нужд и после использования сбрасывают ее обратно в водоем. Если суммарный объем сбрасываемой (загрязненной) воды не превышает некоторого предела , то происходит ее естественное очищение, и общий водный ресурс сохраняется. Если же указанный предел нарушен, то загрязненность водоема интенсивно растет. Возникает проблема его восстановления за счет предприятий и уплаты штрафов, общая стоимость чего составляет .

Чтобы избежать неприятных последствий, приходится строить очистные сооружения, состоящие из отдельных стандартных блоков, рассчитанных на определенные объемы пропускаемой через них воды (пусть каждый блок восстанавливает 25% используемой воды). Затраты на приобретение, монтаж и эксплуатацию одного блока равны С.

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

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

Пусть количество воды, потребляемой каждым предприятием в его технологическом цикле равно единице (100 т, 10 цистерн, и т.д.). Количество очищаемой воды составляет 1 – х на предприятии А; 1 – y на предприятии В, где чистые стратегии игрока А = |0; 0,25; 0,5; 0,75; 1|, в зависимости от числа применяемых очистных блоков. Чистые стратегии игрока В = |0; 0,25; 0,5; 0,75; 1|.

Расходы предприятия А составляют:

4С(1 – х), если х + у  ;

4С(1 – х) + , если х + у  ,

а расходы предприятия В –

4С(1 – у), если х + у  ;

4С(1 – у) + , если х + у  .

Данные формулы позволяют составить платежные матрицы игроков А и В. Для случая имеем

В

А


В4


В3


В2


В1


В0


А4









4С+

2С+

4С+

С+

4С+




А3





3С+

3С+

3С+

2С+

3С+

С+

3С+




А2

2С+

4С+

2С+

3С+

2С+

2С+

2С+

С+

2С+




А1

С+

4С+

С+

3С+

С+

2С+

С+

С+

С+




А0



4С+



3С+



2С+



С+






Индекс при чистых стратегиях игроков указывает на количество используемых очистных блоков (например ^ А3 – предприятие А использует 3 очистных блока; В0 – предприятие В не использует ни одного очистного блока).

Найти ситуации оптимальные по Парето и ситуации равновесия по Нэшу при следующих исходных данных:

9. С  ; 10. С  ;

11. 5С = ; 12. 5С = ; ;

13. 4С = ; ; 14. 2С = ; ;

15. 2С = ;; 16. С = 3; ;

17. С = 2; ; 18. С = ; ;

19. С = ; ; 20. С = 4; .

ІІІ. Найти множества всех ситуаций оптимальных по Парето в следующих биматричных играх:

21.

22.

23.

24.

25.

26.

27.

28.

^

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ





  1. Вентцель Е.С. Исследование операций. – М.: Наука, 1980. – 206 с.

  2. Воробьев Н.Н, Теория игр для экономистов-кибернетиков. – М.: Наука, 1985. – 272 с.

  3. Мулен Э. Теория игр с примерами из математической экономики. – М.: Мир, 1985. – 200 с.

  4. Морозов В.В. Сухарев А.Г., Федоров В.В. Исследование операций в задачах и упражнениях. М.: Высшая школа, 1986. – 287 с.

  5. Ермольев Ю.М., Ляшко И.И., Михалевич В.С. Тюптя В.И. Математические методы исследования операций. – К.: Выща школа, 1979. – 312 с.

  6. Таха Х. Введение в исследование операций. Кн.2. – М.: Мир, 1985. – 479 с.

  7. Костевич Л.С., Лапко А.А, Теория игр. Исследование операций. – Минск: Вышэйшая школа, 1982. 229 с.




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


 Київський інститут інвестиційного менеджменту

Схожі:

5. бескоалиционные игры общие сведения icon5. бескоалиционные игры общие сведения
Антагонистические игры, которые рассматривались в предыдущих главах книги, описывают конфликты частного вида, которые не всегда адекватны...
5. бескоалиционные игры общие сведения icon3. позиционные игры общие сведения
В общих играх число игроков может быть больше двух, некоторые ходы возможно являются случайными, игроки могут иметь по несколько...
5. бескоалиционные игры общие сведения icon3. позиционные игры общие сведения
В общих играх число игроков может быть больше двух, некоторые ходы возможно являются случайными, игроки могут иметь по несколько...
5. бескоалиционные игры общие сведения icon5. Бескоалиционные игры
Антогонистические игры, которые рассматривались в предыдущих главах книги, описывают конфликты частного вида, которые не всегда адекватны...
5. бескоалиционные игры общие сведения icon5. Бескоалиционные игры
Антагонистические игры, которые рассматривались в предыдущих главах книги, описывают конфликты частного вида, которые не всегда адекватны...
5. бескоалиционные игры общие сведения icon5. Бескоалиционные игры
Антогонистические игры, которые рассматривались в предыдущих главах книги, описывают конфликты частного вида, которые не всегда адекватны...
5. бескоалиционные игры общие сведения icon3. Позиционные игры Общие сведения
Число ходов в данной игре не фиксируется, оно зависит от последовательности выборов исходов. Однако, правила должны гарантировать,...
5. бескоалиционные игры общие сведения icon3. Позиционные игры Общие сведения
Число ходов в данной игре не фиксируется, оно зависит от последовательности выборов исходов. Однако, правила должны гарантировать,...
5. бескоалиционные игры общие сведения icon4. бесконечные антагонистические игры общие сведения
Но, как и во всякой антагонистической игре, в бесконечной антагонистической игре принципом оптимального поведения игроков остается...
5. бескоалиционные игры общие сведения icon4. Бесконечные антогонистические игры Общие сведения
Но как и во всякой антогонистической игре, в бесконечной антогонистической игре принципом оптимального поведения игроков остается...
Додайте кнопку на своєму сайті:
Документи


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