Тема 6. Лекция 14. Кооперативные игры. Виды взаимодействия игроков. Характеристическая функция игры. Дележ. Доминирование дележей. С-ядро.

1. Виды взаимодействия игроков

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

Пример. Парето-оптимальное равновесие в примере 5 как результат кооперации игроков.

В примере 5 рассматривалась игра с биматрицей

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

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

В этой игре уже две ситуации равновесия Нэша, («эгоист.», «эгоист.») и («договор», «договор»), причем вторая доминирует по Парето первую. Кроме того, можно заметить, что, при «эгои­стической» стратегии второго начальника, первому безразлично, «эгоистическую» ли стратегию выбирать, или «договор». Но если он выберет «договор», стратегия «договор» станет выгодной и второму начальнику. Дело в том, что «эгоистическое» равновесие - это нестрогое равновесие Нэша, в отличие от «договорного».

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

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

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

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

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

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

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

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

2. Переход от нормальной формы игры к игре в форме характеристической функции

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

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

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

Характеристической функцией игры п лиц называется вещественнозначная функция v(S), определенная на подмножествах , такая, что .

Характеристическая функция называется супераддитивной, если

(14)

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

Супераддитивные игры представляют собой, в некотором роде, типичный случай. Действительно, пусть есть коалиции S и Т с их значениями v(S) и v(Т). Что мешает образующейся коалиции действовать так, как если бы такого объединения не существовало? Тогда полезность этой коалиции будет как минимум равна сумме полезностей коалиций S и Т, обеспечивая супераддитивность. Это - нестрогие рассуждения и, как будет показано ниже, они верны лишь при некоторых предположениях.

Классическая теория рассматривает, в основном, супераддитивные игры. Главными вопросами, которые встают при их ис­следовании - это вопросы об условиях реализуемости максимальной коалиции и «справедливом» распределении выигрыша v(N) между игроками.

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

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

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

(15) , где

- вектор действий участников коалиции S.

Можно заменить чистые стратегии на смешанные. Тогда v(S) будет в точности совпадать с решением антагонистической игры двух лиц - коалиции S и коалиции N\S .

Введенная таким образом характеристическая функция супераддитивна.

Несмотря на удобство использования максимина (то есть применения принципа МГР) для построения характеристической функции, дополнительная информированность игроков может сделать более логичным использование других концепций равно­весия. Обратим внимание на то, что переговорный процесс должен сопровождаться передачей игроками друг другу информации о своих функциях выигрыша, поскольку подобные данные могут оказывать существенное влияние на структуру коалиций. В связи с этим можно предположить, что к моменту окончательного выбора коалиции каждый игрок (а, значит, и любая коалиция) будет обладать информацией о целевых функциях всех остальных игроков (а, значит, и всех возможных коалиций). В этих условиях коалиция S должна ожидать от остальных игроков действий, на­правленных на максимизацию их функций полезности, а не действий, наихудших для коалиции S, как предписывает максимин (напомним, что в играх с произвольной суммой минимаксная стратегия второго игрока может не совпадать с наихудшим, с точки зрения первого игрока, его поведением).

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