Лекция 21. Решения коалиционных игр

Коалиционные игры. Обобщая предыдущую конструкцию, введем по­нятие коалиционной игры, или игры в коалиционной форме.

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

Пример 1. Игра рынка. Пусть каждый участник г владеет некоторым на­чальным запасом ш(г), принадлежащим пространству товаров , и име­ет функцию полезности щ : —у К. Коалиция К может перераспреде­лить свои ресурсы (т.е. перейти к набору х(г) С К+, такому что х(К) := ^еА~ж(г) = ш(К)). Здесь У (К) = {щ(х({)), г £ К, х(К) = ш(К)} (или нормализация этого множества).

Пример 2. Марьяж. Имеется множество мужчин М и женщин ]У7 которые могут заключать браки (моногамные и гетеросексуальные). Считается, что у каждого участника есть функция полезности щ > 0 на множестве потенци­альных партнеров (например, если г £ М, то щ : \У —У К+). Полезность одиночки (для простоты) равна 0.

Как это представить коалиционной игрой? В качестве N возьмем объеди­нение множеств М п]У. Объясним сначала, как определить множество У(Х) для тотальной коалиции. Исходом естественно считать паросочетание неко­торых мужчин и женщин; остальные остаются холостыми. Формально паро­сочетание - это биекция // части мужчин М' С М и части женщин \У С И \ С каждым таким паросочетанием (матчингом) свяжем вектор хЙ £ Шм. "Мужские" координаты этого вектора равны ит(//(га)), если т £ М'. и равны 0 в противном случае. Аналогично задаются "женские" координаты: Х'ш = и-ш(^1(и))), если гш £ ]¥', и нулевые, если женщина гш одиночка. Нако­нец, множество У{Х) есть объединение множеств хЙ — К.+, когда [I пробегает все матчинги.

Аналогично определяется множество У (К) для произвольной коалиции

К С N. Нужно только Д7 и И ' заменить ни Д7 П /\' и И ' П /\\ В результате мы получаем коалиционную игру У.

Трансферабельные полезности. Сразу можно выделить один важный частный случай - случай т.н. трансферабелъных полезностей, или коопера­тивных игр с побочными платежами (в общем случае говорят про игры без побочных платежей). А именно, предположим, что в системе имеется без­гранично делимый и желательный товар - деньги, и что участники могут свободно передавать его друг другу. Более того, предположим, что полез­ность этого товара линейно входит в функцию полезности, так что добавле­ние единицы денег увеличивает полезность каждого на единицу. Тогда вместе с каждой точкой х в множество У (К) входит и любая точка у с той же сум­мой координат. Для краткости мы используем обозначения: х(К) = Тогда х £ У (К) и у £ Шк, х(К) > у (К) влечет, что у £ У (К). В случае трансферабельных полезностей вместо множеств У {К) задают числа

у(К) = та,хх(К): где х пробегает У (К).

В свою очередь,

У (К) = {х£ Шк,х(К) < у(К)}.

Таким образом, коалиционная игра с побочными платежами - это семей­ство у чисел (у(К),К С ./V), параметризованное коалициями К. Говорят также про игру в характеристической форме.

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

Как это естественно представить в виде игры в характеристической фор­ме? Под у(К) мы будем понимать издержки коалиции. Конечно, у(К) равно минимальным издержкам коалиции К. Пока коалиция мала, ей выгоднее не очищать сброс, и тогда у(К) = кпс, где к = \К\. Однако как только раз­мер коалиции станет больше, чем С/с, ей выгоднее очищать свои сбросы, и в этом случае у(К) = к(С + (п — к)с). Это пример т.н. симметричной (или анонимной) игры, так как у(К) зависит только от размера \К\ коалиции К.

Пример 4. Простые игры. Это когда у(К) = 0 или 1. Такие игры встре­чаются при анализе схем голосования. Обычно предполагается, что и(0) = 0, у(М) = 1, и у монотонна.

Пример 5. Игры, производства. Будем называть технологией функцию / : —У К, которая описывает, как ресурсы (в количестве I) преобразуются в выпуск (в денежной форме). Пусть каждый участник г владеет набором ре­сурсов а;(г). Тогда коалиция К владеет ресурсом ш(К) = Хлей'6^) и может получить у (К) = /(и(К)) денег. Получается коалиционная игра у.

Один более конкретный пример игры производства мы рассмотрим в сле­дующем примере.

Пример 6. Потоки в сетях. Сначала несколько общих понятий. Ориентированным гра­фом (орграфом) называется пара (V, А), где V - (конечное) множество вершин, а А С УхУ - множество стрелок или дуг. Нужно представлять, что речь идет о некой транспортной системе (дорог, трубопроводов и т.п.) Чтобы усилить эту трактовку, выделим две верши­ны, 5 - источник, ii / - сток.

Сетью называется орграф (V, А) вместе с функцией ф : А —у К+; ф(а) - это про­пускная способность "трубы" (I (г Л. Поток в такой сети - это отображение ф : А —У К_|_ (ф(а) - поток по трубе о), такое что для любой вершины у, отличной от 5 и I, сколько втекает, столько и вытекает; кроме того должно выполняться ограничение ф(а) < ф(а) на пропускные способности. Легко понять, что из источника вытекает столько же, сколько втекает в сток; эта общая величина называется величиной потока ф. Через /(ф) обозначим максимальное значение величины потока через сеть ф (коротко - максимальный поток).

 

Представим теперь, что каждый участник / владеет некоторыми стрелками (дугами, трубами). Его выигрыш - то, что он может перекинуть по своим трубам. Аналогично выигрыш коалиции К - тот максимальный поток, который можно перебросить по трубам, принадлежащим К. Формально можно представить, что участник / владеет сетью ф^, а коалиция - соответствующей суммой. И тогда у (К) = fi^n^K^i)- Так чт0 эт0 частный случай производственной игры.

Распределения. Вернемся к общим коалиционным играм. Распределени­ем (distribution) будем называть произвольный вектор х из M.N; допустимое распределение - вектор из V(N). Решение коалиционной игры должно указы­вать некоторое допустимое распределение, которое получается в результате рациональных действий (договоров) игроков. Снова тут нет однозначного ответа. Обычно теория идет по пути формулировки некоторых требований к решению, которые представляются разумными. Например, естественно тре­бовать, чтобы решение давало каждому игроку не меньше того, что он можетдобиться в одиночку (требование индивидуальной рациональности). Но ана­логичное требование можно высказать и по отношению к любой коалиции (если она может образоваться, что мы неявно предполагаем). Тут удобно ввести соответствующий язык.

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

X >к У, еСЛИ Х{ > у{  У г £ К.

Говорят, что распределение х доминирует распределение у, если найдется (непустая) коалиция К7 такая что х >к у и хк £ VГ(К).

Смысл этого в том, что коалиция К не согласится на вектор платежей у. если, действуя самостоятельно, она может получить более лучший для нее набор полезностей хк ■ Тут замешаны два разных свойства: чтобы х был лучше для коалиции К7 и одновременно, чтобы х был достижим коалицией К.

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