5.2. Эволюционно устойчивые стратегии

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

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

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

Понятие равновесия, наиболее часто используемое в эволюционной теории игр, как уже отмечалось выше, было введено Мейнардом Смитом и Прайсом и впервые достаточно подробно изложено в книге Мейнарда Смита «Эволюция и теория игр» (Maynard Smith, 1982). Мейнард Смит исследовал поведение фенотипов (фенотип — совокупность всех признаков и свойств организма, сформировавшихся в результате его индивидуального развития). В частности, он изучал фенотип в популяциях, которые эволюционно устойчивы в том смысле, что они не могут быть «побеждены» («захвачены») другим фенотипом. Здесь «победа» означает, что какой-то другой тип поведения оказывается более успешным и агенты применяют его. Поскольку «тип поведения» переводится в теоретико- игровых терминах термином «стратегия», то речь, по сути дела, идет об эволюционно устойчивых стратегиях43.

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

Будем обозначать набор возможных стратегий (типов поведения) через S , а выигрыш агента, выбирающего стратегию х G S , в случае если его противник выбирает стратегию у , через и(х, у) . Предполагаем, что множество S — конечно. Любая стратегия из S называется чистой. Смешанная стратегия — это вероятностное распределение на множестве чистых стратегий.

Смысл ключевого понятия эволюционной теории игр — эволюционно устойчивой стратегии — состоит в следующем. Предположим, что индивиды (агенты) повторяющимся образом выбираются случайно из большой популяции, чтобы разыграть симметричную игру двух лиц (то есть игру Г = {{1, 2}, А, {щ, i = 1, 2}} , где А — множество стратегий и первого и второго игрока, причем и\(х,у) = и(х,у) и и2(ж,у) = и(у,х) для некоторой (непрерывной) функции и, и предположим, что первоначально все индивиды «генетически запрограммированы» играть определенную чистую или смешанную стратегию. Теперь «добавим» некоторую малую долю популяции, которая запрограммирована играть некоторую другую чистую или смешанную стратегию. «Укоренившаяся» стратегия называется эволюционно устойчивой, если для любой такой «мутантной» стратегии существует такой положительный «барьер вторжения», что если доля популяции

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

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

Какова же роль величины популяции? Здесь есть два элемента: один «механический», а другой — «стратегический». Во-первых, чтобы говорить о барьере вторжения (выражаемом в долях популяции), нужно, чтобы такой барьер превосходил 1 /га, где га — численность популяции.

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

Итак, предположим, что небольшая группа мутантов появилась в большой популяции индивидов, каждый из которых запрограммирован играть некоторую, одну и ту же, «укоренившуюся» стратегию х ? А (чистую или смешанную). Предположим, что все мутанты запрограммированы играть неко- торую другую (чистую или смешанную) «мутантную» стратегию у G А . Пусть доля мутантов в «пост-входной» популяции есть е G (0,1). Пары индивидов в этой биморфной (представлены две стратегии) популяции выбираются (повторяющимся образом) случайно, чтобы разыгрывать игру, причем все индивиды выбираются равновероятно. Следовательно, если некоторый индивид выбран разыграть игру, то вероятность того, что его оппонент будет играть «мутантную» стратегию у , есть е , а вероятность того, что будет играть «укоренившуюся» стратегию, есть 1 — ?. Выигрыш в матче (схватке) в такой биморфной популяции совпадает с выигрышем в матче с индивидом, играющим смешанную стратегию

w = еу + (1 — е)х G А.

Таким образом, «пост-входной» выигрыш для «укоренившейся» стратегии будет u(x,w) , а для «мутантной» стратегии — u(y,w) (и — непрерывная функция выигрышей). По- видимому, интуитивно ясно, что «сила эволюции» выступает против «мутантной» стратегии тогда и только тогда, когда «пост-входной» выигрыш меньше, нежели выигрыш «укоренившейся» стратегии, то есть

и(х,?у+ (1 - е)х) > и(у,?у+ (1 - е)х). (2.1)

Стратегия х G А эволюционно устойчива, если это неравенство выполнено для любой «мутантной» стратегии у ф х , при условии, что популяция мутантов достаточно мала.

Определение 5.2.1. Стратегия х G А называется эволюционно устойчивой, если для любой стратегии у ф х существует такой еу G (0,1), что неравенство (2.1) выполнено для любого е G .

Достаточно просто проверить, что ЭУС оптимальна против себя самой: если х не оптимальна против себя самой,

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

Приведенное выше определение можно переформулировать следующим образом.

Определение 5.2.1* х ? А называется эволюционно устойчивой, если (х,х) является равновесием по Нэшу игры Г и и(УтУ) < и(хтУ) для любого наилучшего ответа у на х (уф х ).

Пример. Рассмотрим следующую игру, которую можно интерпретировать по-разному. Ее (или ее модификации) иногда называют игрой «цыплята», или «ястреб-голубь».

Я Г

Я f (—2, —2) (2,0) \ Г \ (0,2) (1,1)/

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

Другая интерпретация состоит в следующем. Идет борьба, скажем, за наследство, оцениваемое в 2 единицы. Если никто не хочет уступать (оба ястреба), то борьба связана с серьезными затратами, например, судебными издержками. Если претенденты договариваются (оба голуби), то они делят наследство пополам. Наконец, если один уступает, то второй «получает все».

В этой игре три равновесия по Нэшу — (л, г), (г, я) и смешанное равновесие, когда «я» играется с вероятностью 1/3. Чтобы посмотреть на ЭУС, предположим, что агенты из некоторой популяции случайным образом взаимодействуют друг с другом. Предположим, что агенты не знают, какую стратегию использовать. Они просто начинают использовать какую-то стратегию или вероятностную смесь этих стратегий, и они приспосабливают свои стратегии, используя процесс обучения методом проб и ошибок. Есть два способа ввести процесс обучения. Либо мы можем представить себе, что некоторая часть р (0 < р < 1) популяции использует стратегию «я», а другая 1 —р использует «г», и предположить, что агенты переключаются с одной стратегии на другую в зависимости от результата использования той или иной стратегии. Второй вариант — мы можем предположить, что каждый индивид использует смешанную стратегию и приспосабливает вероятностную смесь на основе своего опыта использования каждой чистой стратегии (то есть увеличивает р, если «я» дает большую отдачу, и наоборот).

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

Как будет развиваться использование этих стратегий в процессе такого обучения? Рассмотрим ожидаемую отдачу от стратегии, когда вероятность встретить «я» есть р (либо потому, что такова доля популяции, использующая эту стратегию, либо потому, что такова средняя вероятностная стратегия, используемая агентами в популяции):

Е{я) = р(—2) + (1 — р)2 = 2 — Ар,

Е(г) = р(0) + (1-р)1 = 1-р.

Это означает, что выигрыш от «бытия ястребом» превышает таковой для голубя, если

2 — 4р > 1 — р или р < 1/3,

а тогда большее число агентов будет стремиться использовать «я», то есть р будет расти. Обратно, для «г» р > 1/3 и больше

агентов будет стремиться использовать «г», а значит, р будет уменьшаться. Следовательно, р= 1/3 определяет ЭУС.

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

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

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

Задача. Покажите, что в каждой симметричной игре, в которой у каждого игрока есть две чистые стратегии, а выигрыши, соответствующие четырем наборам стратегий, различны, существует смешанная стратегия, являющаяся эволюционно устойчивой. tttn Часть II Кооперативные игры Глава 6.

Элементы теории кооперативных игр tttk

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

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

aaan 6.1. Классические кооперативные игры

aaak sssn Классической кооперативной игрой, или кооперативной игрой с побочными платежами, называется пара Г = (I,v), состоящая из конечного множества I = {1, 2,..., п} и вещественной функции v : 244 —> IR, определенной на множестве всех подмножеств множества I, причем и(0) = 0. Элементы множества I называются игроками1, подмножества S С I — коалициями, а сама функция v — характеристической функцией игры Г .

Стандартная интерпретация состоит в следующем. Игроки из множества I могут объединяться в различные коалиции с целью так согласовать свои действия, чтобы получить максимальный выигрыш. Если образуется коалиция S, то известна величина v(S), которая и интерпретируется как тот максимальный суммарный выигрыш игроков из S, который они могут обеспечить себе, действуя совместно. При этом мы абстрагируемся от того, каким образом должны действовать игроки, чтобы обеспечить себе выигрыш v(S), то есть отыскание оптимальных действий игроков из S лежит вне данной модели. Кроме того, в определении классической кооперативной игры предполагается, что полезности игроков обладают свойством трансферабельности, то есть измеряются по одной шкале и могут передаваться от одного игрока другому без потерь и без ограничений (побочные платежи), поэтому такие игры называются также играми с трансферабельной полезностью, или, кратко, ТП-играми. В таком случае игрокам из каждой коалиции важно максимизировать суммарный выигрыш, так как в дальнейшем они могут распределять его между собой произвольным образом. Ниже, в разделе 6.2 мы рассмотрим игры более общей природы — игры без побочных платежей, или так называемые игры с нетрасферабельной полезностью.

Заметим, что характеристическая функция может иметь самое разнообразное происхождение. В частности, она может возникать при рассмотрении бескоалиционных игр. А именно, рассмотрим бескоалиционную игру Г = {/, {Zi}iej, {иг}ге/} (здесь мы отступаем от нашего традиционного обозначения множеств стратегий через Si, поскольку далее мы обозначаем буквой S коалиции). Предположим, что игроки, составляющие коалицию S С I, объединяют свои усилия в общих интересах. Какой наибольший суммарный выигрыш может обеспечить себе эта коалиция, независимо от того, каким образом действуют оставшиеся игроки, то есть игроки из I\S? Объединение игроков в одну коалицию означает, по сути дела, что они превращаются в единого игрока, для которого мы сохраним то же самое обозначение S . То, что они действуют совместно, означает, что стратегиями этого игрока являются всевозможные комбинации стратегий, составляющих эту коалицию игроков, то есть пространство стратегий Zs игрока S есть Zs = EL'es ^ • Следовательно, выигрыш игрока S есть

us{z) = Yhies ui(z) ?

Нас интересует тот наибольший выигрыш, который может обеспечить себе эта коалиция. Ясно, что в худшем для игрока S случае оставшиеся игроки могут тоже объединиться в коалицию I \ S с диаметрально противоположными интересами, то есть Uj\s(z) = —Us(z) ? В результате вопрос о нахождении наибольшего гарантированного выигрыша игрока S сводится к нахождению значения (если таковое существует) антагонистической игры Г5 = {Zs, Zj\s, Us} , или

max min Us{zs, zns),

Z.S Zl\s

где Zs , Zi\s — множества стратегий игрока S и I \ S соответственно, a Us — функция выигрышей игрока S (см. Раздел 1.8 Главы 1). Так определенный выигрыш игрока S зависит в конечном счете только от коалиции S (и, конечно, от самой исходной бескоалиционной игры Г), являясь ее функцией. Эта функция и есть характеристическая функция бескоалиционной игры Г , которая обозначается через up .

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

Далее мы будем часто говорить об игре v без указания множества игроков I. В случае необходимости мы будем обозначать множество игроков в игре с характеристической функцией v через Iv .

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

v(S) = f({i}) для любой коалиции S С I.

ies

В дальнейшем мы будем использовать сокращенную запись г;(г) и v(SUi) вместо и({г}) и u(S'U{i}) и т. д. соответственно.

Игра v называется супераддитивной, если для любых коалиций S и Т , таких что S ПТ = 0 , выполняется неравенство

v(SUT) > v(S) + v(T).

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

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

v(S и Г) + v(S П Г) > v(S) + v(T).

Заметим, что выпуклая игра является супераддитивной, так как и(0) = 0 .

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

Пусть К/ обозначает |/|-мерное эвклидово пространство, координаты которого заиндексированы элементами из множества I. Часто бывает удобно рассматривать вектор ж ? IR/ как несуществующую игру, определенную формулой

x(S) = Xj для всех S С I.

ies

Дележом в игре v называется вектор х ? IR/ , удовлетворяющий условиям групповой и индивидуальной рациональности, то есть: 1)

х(1) = v(I) и 2)

Xi > г; (г) для всех i ? I.

Далее мы введем следующие обозначения:

IR5 = {х ? IRn : xi = 0 для г g S} , S С /;

X(v) = {ж ? IR/ : х(1) = v(I),Xi > г;(г) для любого г ? /} — множество дележей45 в игре v ;

= {ж ? IR^ : ж(/) = и(/)} — множество распределений (пред-дележей46) в игре v .

Если G — некоторый класс кооперативных игр (вообще говоря, не обязательно с побочными платежами), то под решением на G обычно понимается отображение F (однозначное или, быть может, многозначное), ставящее в соответствие каждой игре v ? G некоторый вектор или непустое множество F(v) в пространстве IR/ , которое называется решением или значением (в случае однозначности) игры v. Разумеется, отображение F должно обладать некоторыми определенными свойствами, чтобы «иметь право» называться решением. Компонентам Fi(v) вектора F(v) (в случае однозначности решения) или компонентам вектора х ? F(v) (в случае многозначности) можно давать различные интерпретации. Так, например, можно считать, что Fi(v) есть априорная оценка игроком i выгодности для него игры v . Можно считать Fi(v) в некотором смысле средним выигрышем игрока в игре. Можно также интерпретировать Fi(v) как «справедливую» долю игрока i в игре v . Выбирая ту или иную интерпретацию и формализуя интуитивные представления о тех свойствах, которыми должно обладать решение, то есть вводя те или иные аксиомы, можно получать различные отображения F.

Мы приведем определение ряда наиболее известных решений. Исторически первым и одним из наиболее важных понятий решения является решение, введенное JI. Шепли в его классической работе Shapley, 1953. Шепли рассматривал Fi(v) как априорную оценку игроком i выгодности для него игры v . Он предложил три аксиомы, которым должна удовлетворять функция F.

А1 (симметричность). Если г — такая перестановка множества Iv , что для любой коалиции S v(tS) = v(S) , то FTi(v) = Fi(v) для любого i ? Iv .

А2 (носитель). Если коалиция К — носитель игры v, то есть v(S) = v(S П К) для любой коалиции S , то ^kF{v) = V{K).

A3 (линейность). Если для всех S w(S) = v(S) + u(S) , то для всех i

F(w) = F(v) + F(u).

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

А2' Если игрок j в игре v таков, что v(S U j) = v(S) для любой коалиции S , то Fj(v) = 0 .

А2" ЯW = «(/)•

Последнюю аксиому называют условием групповой рациональности, или Парето оптимальности, или также эффективности. Игрок j из аксиомы А2' называется «болваном» в игре v . Этот игрок ничего не получает сам, так как v(j) = и(0) = О, и никак не влияет на выигрыш коалиции, к которой присоединяется. Таким образом, аксиома А2' требует, чтобы игрок, являющийся болваном, ничего не получал при распределении выигрышей. Аксиома А2" просто означает, что игроки делят между собой величину v(I) . Именно эту аксиому мы будем в дальнейшем называть аксиомой эффективности. Заметим, что для супераддитивных игр v(I) есть максимум того, что игроки могут получить суммарно. Аксиома A3 означает, что оценка игры, являющейся суммой двух игр, есть сумма оценок каждой из игр-слагаемых.

Например, рассмотрим следующую весьма простую игру трех лиц /={1,2,3}:

W(l) = 0, v{2) = i;(3) = 1, v(12) = v(13) = 1, i>(23) = 3, i>(123) = 3.

В этой игре носитель — это коалиция {2, 3}, игрок 1 — болван.

Перестановка, меняющая местами игроков 2 и 3, сохраняет игру без изменения. Поэтому, если значение Шепли (т.е. функция, удовлетворяющая приведенной системе аксиом) существует, то игрок 1 (в силу А2') должен получить 0, игроки 2 и 3 (в силу А1) — поровну, а суммарно (в силу А2") они должны получить 3, т.е. игроки 2 и 3 должны получить по 1.5.

Шепли доказал (доказательство приводится в разделе 6.5), что этим трем аксиомам удовлетворяет единственная функция Ф , называемая значением (или функцией, или вектором) Шепли, определяется следующим образом:

Ф,-(«)= ? B!(n"J"1)!K5u»)-t;(5)],

где s = 15* | — число игроков в коалиции S . В дальнейшем значение Шепли всегда будет обозначаться с помощью Ф .

Функцию Ф можно интерпретировать не только как оценку игры, но и как функцию, задающую средний выигрыш игроков при следующей вероятностной схеме. Равновероятно выбираем любого из игроков. Далее равновероятно выбираем любого из оставшихся игроков и присоединяем к уже выбранному. Продолжаем этот процесс, пока не исчерпаем все множество I. При этом, если игрок i был выбран именно после того момента, когда была уже образована коалиция S , то он получает выигрыш, равный величине, на которую возрастает выигрыш коалиции из выбранных игроков в результате его присоединения, то есть v(S U i) — v(S) .

Замечательное свойство значения Шепли, на котором основан целый ряд существенных обобщений значения Шепли и, в частности, определение многозначных аналогов значения Шепли (см. Pechersky, Sobolev, 1995), дает следующее предложение.

Предложение 6.1.1. (Кеапе, 1969). Значение Шепли совпадает с решением задачи минимизации функционала

Q(x, v)= (s - l)!(n - s - 1)!(и(5) - ж(5))2

на множестве распределений X*(v) .

Доказательство этого предложения можно найти в книге Печерский, Соболев, 1983. При доказательстве используется метод множителей Лагранжа, строгая выпуклость функции Q и проверяется выполнение всех аксиом Шепли. В частности, аксиома болвана однозначно определяет коэффициенты (s — 1)!(та- s - 1)!.

В качестве решения используются также и другие функции вида

Fi(v)= Е l(s,n)[v(SUi)-v(S)],

S:iгде 7(s,n) — некоторые коэффициенты. В частности, если 7(s, п) = 1/2™ , то получается так называемый вектор Банзафа (Banzhaf, 1965; Owen, 1975). Однако среди всех этих функций значение Шепли, безусловно, заслуживает наибольшего внимания, так как обладает многими важными свойствами. Так, например, значение Шепли обладает свойством (сильной) ковариантности, то есть если две игры v и v' таковы, что

v'(S) = cv(S) + a(S) для некоторых с > 0 и а ? IRn,

то

Фг(г/) = сФг(у)+аг.

Заметим также, что очень интересный класс решений представляет семейство значений наименьших квадратов, получающихся при минимизации функций, аналогичных приведенной выше функции Q , но с произвольными коэффициентами wntS > 0 (см., например, Ruiz, Valenciano, Zurzuelo, 1998).

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

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

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

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

Пусть хну — два дележа, a S — некоторая коалиция. Говорят, что х доминирует у по коалиции S , если

(1) Xi > yi для всех i ? S,

(2) <

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

Говорят, что х доминирует у, если найдется такая коалиция S,что х доминирует у по коалиции S .

Определение 6.1.1. С-ядром4 C(v) игры v называется множество всех ее недоминируемых дележей.

На самом деле нетрудно доказать, что C(v) = {ж G IR1 : х{1) = v(I), x(S) > v(S) для всех S С /}.

Если игра v выпукла, то значение Шепли игры v лежат в с-ядре игры v (Shapley, 1971). Заметим, что в случае, например, супераддитивности игры v вектор Ф(и) может даже не принадлежать непустому с-ядру. Более подробно о выпуклых играх см. раздел 6.6.

Классическим результатом о непустоте с-ядра кооперативных игр с побочными платежами является теорема, доказанная впервые О.Бондаревой (Бондарева, 1963), а затем, независимо, JI. Шепли (Shapley, 1967), утверждающая, что кооперативная игра имеет непустое с-ядро тогда и только тогда, когда она сбалансирована. Понятие сбалансированности вводится следующим образом (см., например, Розенмюл- лер, 1974) (см. также п. 6.3).

О, г ? S.

1, ieS

4The core.

5Часто в определении сбалансированности требуют, чтобы числа были положительными, однако это различие не является существенным.

Набор коалиций В С 21 называется сбалансированным, если найдутся такие неотрицательные5 числа ps , S G В , что PseS = е j где е = е1 = (1,1,..., 1) ? IR/ , a es — характеристический вектор коалиции S , то есть Кооперативная игра v называется сбалансированной, если для любого сбалансированного набора коалиций В имеет место неравенство

J2^sV(S)(Мы еще вернемся к понятию сбалансированности в разделе 6.3.)

Наряду с с-ядром существенную роль играет (сильное) е- ядро (или се -ядро) игры, определяемое для произвольного вещественного е следующим образом:

Ce(v) = {х G Ш1 : x(I) = v{I),x{S) > v(S)-e для всех S ф 0, /}.

Ясно, что С {у) = Со{у) . Кроме того, С?{у) Э С?'{у) , если ? > ?', причем включение строгое, если С?{у) ф 0 . Очевидно также, что С?{у) ф 0 для достаточно больших ? и, напротив, начиная с некоторого ? (быть может, отрицательного) становится пустым.

Определив с-ядро, невозможно не сказать несколько слов о так называемом наименьшем с -ядре47 (Maschler, Peleg, Shapley, 1979).

Наименьшее с-ядро LC(v) игры v —это пересечение всех непустых г-ядер игры v. Эквивалентно пусть ?o(w) — наименьшее ? такое, что С?{у) /0, т.е.

?0(и) = min max е(5*, ж), xex*(v)

причем ?o(w) может быть отрицательным. Тогда LC(v) = C?0(v)(v) . Иными словами, наименьшее с-ядро — это множество всех распределений, минимизирующих максимальный эксцесс.

С-ядро было введено Джиллисом (Gillies, 1952, 1959), а ?- ядро — Шепли и Шубиком (Shapley, Shubik, 1963, 1966). ?- ядро интерпретируется как множество эффективных распределений, которые не могут быть улучшены ни одной из коалиций при условии, что формирование коалиции требует «затрат» е (или вознаграждается «бонусом» —г, если е < 0). Наименьшее с-ядро комбинирует идею существования (непустоты) и единственности. Если с-ядро игры непусто, т. е. < 0, то наименьшее с-ядро — это «центрально расположенное» подмножество (или точка) с-ядра. Если с-ядро пусто, т.е. ?q > 0 , то наименьшее с-ядро может рассматриваться как «латентное» положение с-ядра.

Интересно также еще одно особое число:

?l(i;) = max (и (5) -

' ies

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

Следующее свойство е -ядра немедленно следует из определения: C?(v) Э X(v) тогда и только тогда, когда е > ?i(u) г-ядра, включая наименьшее с-ядро и само с-ядро, представляют собой компактные выпуклые многогранники, ограниченные не более чем 2п — 2 гиперплоскостями вида

Н% = {х е X*(v) : x(S) = v(S) -е}, S ф 0, /.

Все непустые г-ядра, за исключением наименьшего с-ядра, имеют размерность п — 1, т.е. размерность X*(v) . Размерность наименьшего с-ядра всегда не превосходит п - 2 .

Предложение 6.1.2. Если две игры (I,v) и (I,v') имеют совпадающие е -ядра, т. е.

Се{ъ) = Св,{ъ)фЪ,

то и все меньшие е -ядра совпадают, т. е.

с?_л«) = ')

для любого а > 0 . В частности, LC(v) = LC(v ) . Рассмотрение г-ядра оказывается очень полезным при рассмотрении к -ядра и га-ядра кооперативных игр (см. ниже).

На основе понятий угрозы и контругрозы дается определение переговорного множества: пусть х — дележ в игре v . •

Пара (у, S) , где S — коалиция, а у достижим для S, т.е. y(S) = v(S), называется угрозой i против j относительно х , если S Э г, но S^j и ук > ХкУк ? S. •

Пара (z,T) , где Т — коалиция, a z Г-достижим, называется контругрозой относительно угрозы (у, S) игрока i против j , если Т Э j , но Т^г и Zk > х^У k ? T\S , Zk > Ук У к ? Т П S .

Определение 6.1.2. Переговорным множеством48 называется множество дележей х таких, что для любой угрозы (у, S) игрока i против любого другого игрока j относительно х существует контругроза игрока j относительно

(:y,S)•

Предложение 6.1.3. Переговорное множество всегда непусто и содержит с -ядро.

Другими, чрезвычайно важными понятиями решения кооперативных игр являются понятия п-ядра49 и к -ядра50, а также их модификации — пред- га -ядро51 и пред- к -ядро52. Введенное Д.Шмайдлером понятие га-ядра игры (Schmei- dler, 1969) опирается на понятие эксцесса коалиции. Для классической кооперативной игры v стандартный эксцесс (или функция эксцесса) определяется естественным образом: e(S,x) = v(S) — x(S) . Величина e(S,x) называется эксцессом коалиции Sex и интерпретируется как мера неудовлетворенности коалиции распределением выигрышей, которое предписывается вектором х. Заметим здесь, что чем больше х , тем меньше эксцесс, и, тем самым, «меньше неудовлетворенность». В этом смысле мы можно говорить, что эксцесс монотонен по v и антимонотонен по х .

Пусть X — произвольное непустое замкнутое множество в IR^. Для любого х ? X и любой кооперативной игры v определим вектор в(х) следующим образом:

в(х) = (e(S1,x),e(S2,x),. ..,e(S2n,x)),

где различные эксцессы всех коалиций расположены в убывающем (невозрастающем) порядке. Компоненты вектора в(х) определены и непрерывны. Будем говорить, что в(х) лексикографически меньше, чем в (у) , и обозначать это как в(х) N -ядром игры v относительно множества X (и данного семейства эксцессов e(S, •), S С /), которое мы будем обозначать через N(X,v), называется множество тех векторов из множества X, для которых соответствующие вектора в минимальны относительно определенного лексикографического порядка, то есть

N(X, v) = {х ? X : в(х) <1ех в (у) для всех у ? X}.

Если X = X(v), то N(X,v) := N(v) называется п-ядром игры v. Если X = X*(v), то N(X,v) := PN(v) = N*(v) называется пред- п -ядром игры v .

Теорема 6.1.1. (Schmeidler, 1969; Kohlberg, 1971). Если X компактно или если оно замкнуто и х(1) < const для всех х ? X, то N(X,v) непусто. Если, кроме того, X выпукло, то N(X,v) состоит из одной точки и непрерывно зависит от характеристической функции. Важнейшим свойством га -ядра и пред- га -ядра является следующее следствие из этой теоремы.

Следствие 6.1.1. N-ядро игры v (и пред- га -ядро игры v ) одноточечно и лежит в с-ядре игры v, если оно непусто.

Докажем для примера одноточечность га-ядра.

Пусть v — ТП игра и х,у ? N(v) => Q(x) = Q(y) ? Мы покажем, что e(S,x) = e(S,y)\/S и в частности e(i,x) = e(i,y) => х = у. Пусть S* : e(S*,x) ф e(S*,y). Рассмотрим дележ z = -j(ж + у) . Обозначим через В\(х), . . ., Вк(х) разбиение множества всех коалиций такое, что S,S' ? Вк(х) e(S, х) = e(S , х) , т. е. MS ? Bk(x), e(S, х) = . Считаем

Oi\{x) > «2(ж) > ... > Oik{x) . Ясно, ЧТО Oik{x) = Oik (у) У к И \Bk{x)\ = \Bk{y)\ Ук . Но так как e(S*, х) ф e(S*, у) , то существует минимальное к* , для которого Вk* (х) ф Вk* (у) ? Если Вк* (ж) П Вк* (у) ф 0, то Bk.(z) = Вк* (ж) П Вк* (у) С Вк.(ж); если Вк. (ж) П Вк* (у) = 0 , то ак* (z) < ак* (ж) = ак* (у) .

В любом случае 0(z) Еще одно полезное свойство га-ядра дается следующим утверждением.

Предложение 6.1.4. Пусть и и v — две игры такие, что u(I) = v(I) и v(S) = u(S) + а для всех S ф I и некоторого числа а . Тогда N*(v) = N*(u) .

Интересно, что определение га-ядра можно дать в терминах угроз и контругроз (см. Osborne, Rubinstein, 1994). А именно, пусть ж — дележ в игре v .

Пара (S,y), состоящая из дележа у и коалиции S, называется угрозой относительно ж, если e(S, ж) > e(S,y) (то есть y(S)>x(S)).

Коалиция Т называется контругрозой относительно угрозы (S,y), если е(Т,у) > е(Т,х) (то есть ж (Г) > у(Т)) и е(Т,у) > e(S,x) .

Тогда га-ядром игры v называется такой дележ х , что для каждой угрозы (S, у) относительно х найдется контругроза.

К -ядро и пред- к -ядро исследовалось во многих работах начиная со статей М. Дэвиса и М. Машлера (Davis, Maschler, 1965), М. Машлера и Б. Пелега (Maschler, Peleg, 1966, 1967), М. Машлера, Б. Пелега и JI. Шепли (Maschler, Peleg, Shapley, 1972, 1979). В действительности, исторически к-ядро предшествовало га-ядру: один из неожиданных результатов статьи Maschler, Peleg, 1966 состоял в том, что если для произвольного е множество C?(v) П X(v) непусто, то к -ядро пересекает это множество (неожиданных потому, что определение к-ядра никак не опирается на понятие с-ядра). Исследуя именно этот факт, Шмайдлер и дал определение га-ядра, которое, с одной стороны, является «уникальной» точкой к -ядра, а с другой стороны, как оказывается, весьма тесно связано с концепцией г-ядра. (Говоря неформально, именно на некоторым образом сконструированном процессе трансформации непустого г-ядра построена геометрическая характеризация га-ядра (см. Maschler, Peleg, Shapley, 1979). При такой трансформации грани непустого г-ядра для достаточно большого е начинают равномерно с одинаковой скоростью (за счет уменьшения е) сдвигаться параллельно себе до тех пор, пока множество, ограничиваемое этими гранями, не станет пустым, либо не «отделится» от с-ядра. Далее некоторые грани сдвигать уже становится невозможным, поэтому продолжают сдвигать оставшиеся грани до тех пор, пока множество, ограничиваемое гранями, не станет пустым, либо не «отделится» от с-ядра. И так далее, пока не останется единственная точка. Эта точка и будет га-ядром.)

Пусть v — произвольная кооперативная игра. Обозначим для любых двух различных игроков i,j€.I через Tjj множество тех коалиций, которые содержат i, не не содержат j , то есть

Tij = {S:ScI,ieS,j^S}. Для каждого распределения х ? X*(v) определим «максимальное преимущество игрока i над j» следующим образом:

Sij(x) = ma xe(s,x).

Величину Sij(x) можно интерпретировать как максимум того, что игрок i может надеяться выиграть (минимум проиграть в случае отрицательности), если он отклонится от х и образует коалицию, которая не нуждается в согласии игрока j, в предположении, что другие участники этой коалиции удовлетворены тем, что им дает х . Игроки г и j находятся в равновесии для х, если Sij(x) = Sji(x).

Если вместо множества распределений X*(v) взять множество дележей X(v), то условие равновесия переписывается в виде двух неравенств:

К?(ж) - S3^X)][X3 - V(J)] < 0

и аналогичного неравенства с перестановкой i и j .

К-ядром K(v) игры v называется множество тех дележей х ? X(v), для которых любые два игрока находятся в равновесии. Пред-к-ядром K*(v) игры v называется множество тех пред-дележей х ? X*(v) , для которых любые два игрока находятся в равновесии, то есть

K*(v) = {Ж?М/:таxs:tes^s(v($) - х($)) =

= maxS:jeStfS(v(S) - x(S)),i,j ? Г, х{1) = v(I)}.

Предложение 6.1.5. К-ядро и пред-к-ядро всегда непусты. Для любой игры v имеет место равенство K(v) П C(v) = K*(v) П C(v) . Кроме того, к-ядро лежит в переговорном множестве.

Заметим, что к -ядро может иметь весьма своеобразное строение, как показывает пример 4 ниже.

Прежде чем привести некоторые примеры решений, необходимо отметить, что мы ничего не сказали относительно аксиоматического подхода к определению таких решений, как с-ядро, га-ядро, к -ядро и т.д. Мы отсылаем по этому поводу читателя к работам Maschler, 1992; Pechersky, Sobolev, 1995; Peleg, 1986, 1992 и многим другим. При этом необходимо подчеркнуть, что применение аксиоматического подхода оказывается чрезвычайно плодотворным. Мы остановимся на этом несколько подробнее в п. 6.4.

Приведем несколько простых примеров решений.

Пример 1. Простая игра. Кооперативная игра v называется простой, если v(S) принимает только значения О и 1 для любой коалиции S ф I и v(I) = 1; коалиции S, для которых v(S) = 1, называются выигрывающими. Игрок, принадлежащий всем выигрывающим коалициям, называется вето-игроком. Тогда a)

Если в игре нет вето-игрока, то C(v) = 0 (докажите!). b)

Если множество вето-игроков в игре v непусто, то с- ядро состоит из векторов выигрышей, дающих 0 всем остальным игрокам (докажите!).

Пример 2. Мажоритарная игра 3-х лиц. a)

Пусть I = {1, 2, 3} , v(I) = 1, v(S) = а ? [0,1] для любой коалиции S, состоящей из двух игроков, и г;(г) = 0 для любого i ? I. Тогда с-ядро C(v) непусто тогда и только тогда, когда а < 2/3 (докажите!). b)

Пусть теперь а = 1. Тогда с-ядро такой игры пусто. Можно показать, что переговорное множество этой игры состоит из единственного вектора (5,5,5) •

Действительно, предположим, что ж-дележ и (y,S) — это угроза i против j относительно х . Тогда S = {г, h}, где h — оставшийся игрок и yh < 1 — (т.к. уг- > жг- и y(S) = v(S) = 1). Для того чтобы у j нашлась контругроза на (у, S), мы должны иметь yh + Xj < 1. Следовательно, для того, чтобы х принадлежал переговорному множеству, необходимо, чтобы для всех игроков i,j,h было выполнено неравенство уь < 1 — Xj , как только у^ < 1 —жг- , а это означает, что 1 — жг- < 1 — или жг- > a;j для любых г и j , так что ж = (1,.

Пример 3. Взвешенная мажоритарная игра. Такая игра представляет собой простую игру v , для которой

(с\ — / если w(S) > q,

\ 0, в противном случае

для некоторого числа q и w G , где v(S) = Eies-"7® Для каждой коалиции S . Интерпретация такова: Wj — число голосов, имеющихся у игрока i, a q — число голосов, необходимых для победы. Взвешенная мажоритарная игра (ВМИ) является однородной, если w(S) = q для любой минимальной выигрывающей коалиции S (т. е. коалиции, не содержащей никаких выигрывающих коалиций). ВМИ является игрой с нулевой суммой, если для любой коалиции S либо v(S) = 1, либо v(I\S) = 1, но не одновременно. Предположим, что v — однородная ВМИ с нулевой суммой, в которой Wj = 0 для каждого игрока i, не принадлежащего ни одной минимальной

выигрывающей коалиции. Тогда N(v) = (^^ту, • • •,

Пример 4. Рассмотрим следующую игру семи лиц. г; (124) = и(235) = и(346) = v(457) = и(561) = v(672) = v(713) = 1,

v(S) = 1 для любой коалиции S , содержащей перечисленные выше коалиции,

v(S) = 0 в остальных случаях.

К -ядро состоит из 7 отрезков, соединяющих (1/7,1 /7,..., 1/7) с точками, в которых минимальная выигрывающая коалиция делит свой выигрыш поровну.

Определение 6.1.3. Однозначное решение монотонно, если увеличение v(I) при сохранении значений остальных S не уменьшает выигрыш ни одного из игроков.

Легко убедиться в том, что значение Шепли монотонно. Однако га-ядро этим свойством уже не обладает. Действительно, рассмотрим следующий пример (Maschler, 1992).

Пример 5. /={ 1,.. .,9}. Пусть ж = (1,1,1,2,2,2,1,1,1); v(S) = 6 для S G {123,14, 24, 34,15, 25, 35, 78}, v(S) = 9 для S е {12367,12368,12369,456}, v(I) = 12 , v(S) = — 1 в остальных случаях.

w(I) = v(I) + 1, w(S) = v(S). Тогда

N{v) = x, N(w) = (li,li,li,2|,2|,l|,li,li,li).

Пример 6. Задача о банкротстве. Любопытно, что задачи банкротства имеют очень давнюю историю. Приведем решение задачи банкротства, которая восходит к Талмуду (см. например, Aumann, Maschler, 1985; Maschler, 1992), где описана следующая ситуация. Три вдовы одного мужа предъявляют требования на имущество, оставшееся после смерти мужа, в размере 100, 200 и 300 единиц соответственно. Рассматриваются три случая, когда имущество оценивается в 100, 200 и 300 единиц.

Талмуд приписывает в первом случае распределение (335,335,335) , во втором — (50, 75, 75) и в третьем — (50, 100, 150). Оказывается, что если определить кооперативную игру для множества игроков (жен) I = {1, 2, 3} по формуле

u(S') = max{«имущество минус сумма требований членов» /\5'", 0},

то приведенные выше распределения являются га-ядрами соответствующих кооперативных игр.

Пример 7. (Littlechild, Owen, 1973). Предположим, что га авиакомпаний должны распределить затраты на строительство взлетно-посадочной полосы, причем для обслуживания самолетов, принадлежащих авиакомпании i, достаточно, чтобы длина взлетно-посадочной полосы была равна сг-. Будем считать, что затраты пропорциональны длине и, без ущерба для общности, что

Сп < Сп_ 1 < . . . < Ci.

Таким образом, если образуется коалиция S , то затраты этой коалиции есть c(S) = max8'es{c8'} . Можно проверить, что эта игра выпукла. Вектор Шепли w здесь оказывается следующим:

для всех г = 1,... ,п

причем мы считаем сп+1 = 0.

Иными словами, за ту часть полосы, которой пользуются все авиакомпании, все компании платят поровну. За «следующую» часть, которой пользуются га — 1 компании, они платят поровну, и т. д.