Название: Математические модели принятия решений в экономике - Розен В. В.

Жанр: Экономика

Рейтинг:

Просмотров: 903

Лекция 17. кооперативные игры

• Коалиции. Характеристическая функция игры п лиц. Свойство супер­аддитивности. • Эквивалентность кооперативных игр. Величина ко­оперативного эффекта коалиции. • Сугцестеенные и несущественные игры. 0 — 1 редуцированная форма игры. • Дележи. Условия сущест­венности и несущественности игры в терминах дележей. • Задача 23. Рынок трех лиц.

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

Рассмотрим игру п лиц в нормальной форме (см. лекцию 15)

Г=- (17.1)

Определение. Коалицией в игре Г называется произвольное подмножество игроков S С I = {1,..., п}. В частности, одноэле­ментное множество {г}, состоящее из единственного игрока г, по определению считается коалицией. Допускается также пус­тая коалиция 0 и коалиция I, содержащая всех игроков.

Сформулируем основные предположения, касающиеся возмож­ностей кооперативного поведения игроков в игре Г.

Возможно образование любых коалиций.

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

Формально это условие означает, что множеством стратегий коалиции S является декартово произведение Xs = Yl Хі .

(3) Суммарный выигрыш, полученный всеми игроками коали-ри S, может быть распределен между ее членами любым спосо­бом-

Это условие включает, во-первых, «безграничную делимость» долезностей игроков и, во-вторых, возможность «передачи полез-дости» от одного игрока к другому (как говорят в теории игр — возможность «побочных платежей»).

Бели для игры Г предположения (1)-(3) приняты, Г становится ^оперативной игрой (точнее, кооперативной игрой с разрешен-ными побочными платежами). Основная проблема, возникающая в кооперативных играх, — введение для них понятия оптимально­го исхода, а также выяснение условий существования оптимальных исходов и разработка способов их нахождения.

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

множеством стратегий коалиции S является Yi -^м множеством

ies

стратегий коалиции /S является   Г| Xi и функция выигрыша ко-

i€lS

алиции S есть fs = £ /ь т0 цена построенной антагонистической

ies

игры определяется равенством

v(S) = sup    inf   fs(x,y), (17.2)

x£Xs y^xis

где

fs{x,V) = ^!г{х,у).

iES

Замечания 1. В случае, когда множества стратегий игроков ко­нечны, операторы sup и inf превращаются соответственно в max и min; Равенство (17.2) дает тогда нижнюю цену получающейся матричной иг­ры.

2. Суммирование выигрышей разных игроков имеет смысл лишь тог­да, когда они измеряют свои полезности в одной шкале. Поэтому, если Первоначально это условие не выполнено, то при переходе к коопера­тивному варианту игры необходимо «пересчитать» функции выигрыша "троков, приведя их к единой шкале.

Определение. Функция, которая каждой коалиции S С / СГГ1а вит в соответствие число v(S), определенное равенством (и 2) называется характеристической функцией игры Г. Пара (I,v), где I — множество игроков и v — характеристически функция игры Г, называется кооперативной игрой, поспгр0 емкой для игры Г.

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

Установим основные свойства характеристической функции игры п лиц.

Теорема 17.1. Характеристическая функция v обладает сле­дующими основными свойствами:

v(0) = 0 (персональность);

Если Si П S2 = 0, то v(Si) + v(S2) < v{Si U S2) (суперадди­тивность).

Доказательство. Свойство (1) очевидно из определения. Докажем (2). Пусть Si П S2 = 0. По определению супрему­ма для любого є > О найдутся такие стратегии xst Є Xsl и xs2 Є Xs2, что в любой ситуации у Є Х[ выполняются неравен­ства: fsAvllxsi) > '"(Si) - є, fs2(y\xs2) > v(s2) - £■ Определим стратегию xsi LI xs2 коалиции Si U S2, для которой ее г-я компо­нента совпадает с г-й компонентой стратегии , если г Є Si и с г-й компонентой стратегии xs2, если і Є S2 (такая стратегия су­ществует в силу условия Si П^2 = 0). Замечая, что j/||(a;5l Ua;s2) = = (j/H2^)!!2^ = (j/II^Si)!!^) получаем при произвольной ситуации У&Х,:

fSl(y\(x^UxS2))>v(Si)~e, (*) fs2(y\(xSlUxs2))>v(S2)-E. (**)

Складывая эти неравенства и учитывая, что fgt + fS2 = /sjuS2> получаем

fs1us2(y\(xSl U xS2)) > v(Si) + v(S2) - 2є,

откуда

inf fs1us2(y\(xSl UiS2)) > v(Si)+v(S2),

^едовательно,

sup     inf fSlus2{y\x) > v(Si) + v(S2),

f>e. v(S1US2)>v(S1)+v(S2).

Свойство супераддитивности по индукции распространяется 8а любое число коалиций, а именно, для произвольного семейст­ва (Sk)k=Tr попаРно непересекающихся коалиций имеет место не­равенство

г          г г

5>(5*)<«(US*)- (17-3)

fc=l к=1

В частности, представляя произвольную коалицию S в виде семей­ства одноэлементных коалиций {г}, где г Є S, получаем

5>(i)<„(S). (17.4)

Свойство супераддитивности характеристической функции име­ет следующий содержательный смысл. Соединяя свои возможнос­ти, коалиции Si и 52 получат во всяком случае не менее того, что они получили бы в сумме, действуя порознь. Для непересекающихся коалиций Si и S2 разность v(Si U S2) — (v(Si) + v(S2)) есть неот­рицательное число, показывающее дополнительную выгоду, кото­рую получают коалиции Si и 52 от объединения в «единое целое». В частности, если эта разность равна нулю, то объединение коали­ций 5*1 и ^2 в одну коалицию Si U S2 не приносит этим коалициям никакой дополнительной выгоды.

Замечание. В теории игр рассматриваются также характеристи­ческие функции, не связанные непосредственно с игрой п лиц. А именно, под абстрактной характеристической функцией над множеством иг-Роков / = {1,тг} понимается произвольное отображение v, которое каж­дой коалиции S С / ставит в соответствие определенное число v(S). Если абстрактная характеристическая функция обладает указанными в теореме 17.1 свойствами персональное™ и супераддитивности, то па-Ра (I,v) называется кооперативной игрой. В конкретных случа-*х число v(S) имеет разный содержательный смысл, например, оно мо-*ет характеризовать силу коалиции; ее гарантированные возможности; *Вклад» в некоторое предприятие (как положительный, так и отрица­тельный); «уровень притязаний» и т.п. Примеры характристических функций, не связанных непосредственно с игрой Г общего вида, привеДр ны ниже.

2. Введем отношение эквивалентности кооперативных игр, рас сматриваемых над одним и тем же множеством игроков. Рассмот рим кооперативную игру {/, v). Зафиксируем положительное числс к > 0 и п чисел сг (i = 1, п). Положим

i/(S)=MS)+5>- (17.5,

гЄ-S

Убедимся, что v' — также харктеристическая функция, т.е. что она удовлетворяет условиям теоремы 17.1.

г/(0) = Ь(0) + J2 сг = 0 + 0 = 0 (персональность).

Установим супераддитивность функции г/. Для любых двух непересекающихся коалиций Si, 52 С / имеем

г/(51и52)-(г,'(51)+«,(52))= (b(S!US2)+   £   с)-

- (kv(Si) +      сг +kv(S2) + 53 Сг) = = k{v{Si U S2) -      ) - u(S2)) > 0.

Определение. Две коопертивные игры (I,v) и (I,v') называ­ются эквивалентными, если существует положительное число к > 0 и п чисел сг (г = 1,п), при которых выполняется равенст­во (17.5).

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

За счет подбора констант к > 0 и сг (і — 1,п) можно от за­данной кооперативной игры (/, и) перейти к эквивалентной ей ко­оперативной игре с теми или иными дополнительными свойствами. В частности, полагая к = 1 и сг = —v(i), получаем эквивалентную игру с характеристической функцией v°, имеющей следующий вид-

v°(S) =v(S) -^у(г). (17.6)

Согласно (17.4), функция г;0 неотрицательна, т.е. v°(S) > 0 для любой коалиции S С I. С другой стороны, любая неотрицатель-лая супераддитивная функция множества и (5) является изотон­ии, так как условие S2 2 Si влечет S2 = Si U (S2 Si), откуда и(5г) > u{Si) + u(S2 Si) > u(Si). Таким образом, для характерис­тической функции va

Si С S2   =>  v°{Si) < v°{S2). (17.7)

Для фиксированной коалиции SCI неотрицательное число v°(S) = v(S) — ^2 v{i) будем называть величиной кооператив-

ного эффекта коалиции S в игре (I,v). Число v°(S) показывает тот дополнительный выигрыш, который получают игроки г Є 5 при объединении их в коалицию. В терминах кооперативного эф­фекта условие (17.7) формулируется следующим образом: при уве­личении коалиции величина кооперативного эффекта возрастает (не уменьшается).

3. Охарактеризуем кооперативные игры, в которых не возника­ет кооперативного эффекта.

Теорема 17.2. Для кооперативной игры (I, v) следующие усло­вия эквивалентны между собой:

(а)        Характеристическая функи,ия v аддитивна (т. е. для лю- бых двух непересекающихся коалиций Si,S2 выполняется условие v{S1US2) = v(S1) + v(S2));

(б)        v(S) =  для любой коалиции S С I;

(в)        v{l) = £>(,).

гЄІ

Доказательство. Из (а) следует (б), так как в предположе­нии (а) имеем

v(S)=v({J{i})=^v(i).

Далее, так как (в) есть частный случай (б), то из (б) следует (в). Остается проверить, что из (в) следует (а). Докажем равносиль­ную импликацию: из отрицания условия (а) следует отрицание Условия (в). Отрицание условия (а) означает, с учетом суперад-Дитивности функции v, что для некоторых непересекающихся коа­лиций Si и S2 выполняется неравенство v(Si U S2) > v(Si) + v(S2).

Используя это неравенство и (17.4), получаем v°(S1US2)=v(S1US2)-   £ =

ieSiUS2

= 1,(5! U S2) - ( £ v(i) + E ^ > 1,(5! U S2) - (u(5i) + v(S2)) > 0.

Таким образом, для коалиции Si U S2 величина кооперативного эффекта оказывается строго положительной, тогда в силу его изотонности тем более v°(I) > 0, т.е. v(I) > ^2v(i). Последнее

ієі

неравенство есть отрицание условия (в).

Кооперативная игра (I, v), удовлетворяющая одному из эквива­лентных между собой условий (а), (б), (в) теоремы 17.2, называ­ются несущественной. Наиболее простым для проверки являет­ся условие (в). Условие (а) имеет чисто математический характер. Условие (б) с помощью функции v° может быть переписано в виде г>°(5) = 0; оно означает, что для любой коалиции S величина ее кооперативного эффекта равна нулю.

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

Определение. Говорят, что кооперативная игра (I, v) имеет 0 — 1-редуцированную форму, если:

v(i) = 0 для всех і Є /;

v(I) = 1.

Теорема 17.3. Каждая существенная кооперативная игра эквивалентна некотрой кооперативной игре, имеющей 0 — 1-реду­цированную форму.

Доказательство. В, силу условия существенности игры, выполняется неравенство

<1) "1>(г') >0-

Положим

v*(S)=kv(S) + Y^Ci>0,

i&S

ф к — l/(v(I) — Ylv(i)), Сі = —kv(i). Тогда игра (I,v*) эквива-іЄЙтна игре (I,v), причем

v* (і) = kv(i) + Сі — 0; /(7) = kv{I) + £ сі = kv(I) - к Y v(i) = к(у(Г) - £        = 1.

ієі        iel ієі

Замечание. В явном виде характеристическая функция v*         может быть представлена в виде

v(S) - £

«*(S)=   m   'У (Л-      (17-8)

Правая часть равенства (17.8) имеет следующий содержательный смысл: она показывает отношение величины кооперативного эффекта для коали­ции S к величине кооперативного эффекта для коалиции I всех игроков. Так как при увеличении коалиции коопертивный эффект возрастает, это отношение не превосходит единицы.

4. Рассмотрим кооперативную игру (7, v). Будем интерпретиро­вать число v(S) как сумму, гарантированно получаемую коалици­ей S. Тогда коалиция 7 всех игроков может гарантированно полу­чить сумму v(7) и затем распределить ее любым способом между всеми игроками. Всякое такое распределение будем трактовать как возможный исход игры (I,v). Формально указанное распределение есть вектор х — (х,... ,хп) Є Rn, і-я компонента которого по­нимается как сумма, которая достается игроку і Є 7. Вопрос, ка­кой исход кооперативной игры (7, v) следует считать оптимальным («Правильным», «справедливым»), будет рассмотрен в следующей лекции, а сейчас укажем некоторые предварительные условия оп­тимальности исхода. Как уже было показано при изучении коопера­тивного решения биматричной игры (см. лекцию 16), безусловны­ми требованиями, предъявляемыми к оптимальному исходу, явля­ются требования индивидуальной и коллективной рациональности. В рассматриваемом случае эти требования принимают следующий вид.

(AI) хі > v(i) для всех і Є 7 (индивидуальная рациональность); (А2) ^2 xi — V{I) (коллективная рациональность).

Замечание. Требование индивидуальной рациональности озна^ ет, что игрок г получает при распределении х не меньше той велц,С) ны, которую он может получить гарантированно, действуя в одиночк-, Поясним требование коллективной рациональности. Предположим, Чт ^2 xi < V{I)- Тогда разность а = v(I) — £ х, будет положительной. Р^ц

гЄІ іЄІ

СМОТрИМ П ПОЛОЖИТеЛЬНЫХ чисел Єї ,...,£„, ДЛЯ которых £!+■•■+£„ =: „

Распределение у = (уі, . . . ,у„), где у, = хг + є,, более выгодно, чем ра, пределение х, для всех игроков г Є Г, тем самым распределение х не будет удовлетворять условию оптимальности по Парето. Если же £ ж, >

то такой вектор х не достижим для коалиции /. Таким образом, в этоц случае игроки «делят больше, чем имеют».

Определение. Вектор i€R", удовлетворяющий условиям ин­дивидуальной и коллективной рациональности, называется деле­жом в кооперативной игре (I,v).

Итак, при поиске оптимального исхода кооперативной игры (I, v) мы должны ограничиться только теми распределениями, ко­торые являются дележами. Рассмотрим вначале некоторые фор­мальные свойства дележей. Из условий (А1) и (А2) следует такое правило.

Правило 17.1. Для того чтобы вектор х = (х,... ,хп) Є Rn был дележом в кооперативной игре (I,v), необходимо и достаточ­но, чтобы он был представим в виде

п

xl = v(i) + al,   где   аг > 0,   ^ аг = v(I) - ^ v(i). (17.9)

1=1 г£І

Пояснение. Числа а\% имеют прозрачную интерпретацию: аг — это добавка игроку 1 к его гарантированной сумме v(і) при разде­ле «дополнительной прибыли», возникающей в результате коопера­тивного эффекта.

Приведем несколько следствий, вытекающих из правила 17.1.

Следствие 1. Всякая несущественная кооперативная игра имеет единственный дележ: х = (г>(1),. .., v(n)).

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

Следствие 2. Всякая существенная кооперативная игра име-efn бесчисленное множество дележей.

Следствие 3. Для кооперативной игры в 0 — 1-редуцированной форме вектор х = (х,. .. ,хп) Є К" является дележом тогда и

только тогда, когда хг > 0  (г = 1,»г),      ж, = 1.

1=1

Таким образом, для игры в 0 — 1-редуцированной форме мно­жество ее дележей совпадает с множеством Sn n-компонентных ве­роятностных векторов. В этом случае содержательный смысл г-й компоненты вектора х — это доля г-го игрока при распределении общей полезности, принятой за единицу.

5. Задача 23. Рынок трех лиц.

Рассмотрим классическую модель рынка, в которой участвует один продавец и два покупателя. Предположим, что у продавца име­ется неделимый товар (например, компьютер), который он оцени­вает в рденежных ед., а первый и второй покупатели оценивают этот товар в q и г денежных ед. соответственно (считаем q < г). Необходимое условие участия всех троих в сделке — выполнение неравенств р < q и р < г.

Итак, р < q < г. Проанализируем эту ситуацию как игру, считая продавца игроком 1, первого покупателя — игроком 2 и второго покупателя — игроком 3. Характерной особенностью этой игры является возможность совместных действий игроков, т.е. возможность образования в ней коалиции (коалиция продавца с покупателем интерпретируется как сделка между ними).

Построим характеристическую функцию этой игры, рассматри­вая v(S) как гарантированную прибыль коалиции S; при этом при­быль коалиции считается равной сумме прибылей всех ее участ­ников. Очевидно, что прибыль возможна лишь для коалиции, содержащей продавца, поэтому и(2) = v(3) = v({2, 3}) = 0. Далее, v(l) = 0, так как продавец, действуя в одиночку, не может обес­печить себе никакой прибыли. Найдем теперь і>({1,2}). Создание Коалиции {1, 2} означает, что игроки 1 тл 2 вступают в сделку, т.е. продавец (игрок 1) продает товар первому покупателю (игроку 2). Сделка «устраивает» обоих игроков только в том случае, когда це­на продажи s заключена между р и q, т. е. р < s < q.B этом случае Прибыль продавца равна s — р (так как он оценивал свой товар