Принципы оптимальности решения

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

Распределение выигрышей (дележ) игроков должно удовлетворять следующим очевидным условиям:

• • условие индивидуальной рациональности: x_i > о (г) для i е N, т. е. любой игрок должен получить выигрыш в коалиции не меньше, чем он получил бы, не участвуя в ней (в противном случае он не будет участвовать в коалиции);
• • условие коллективной рациональности (условие эффективности): Y ⁼ u (N), т. е. сумма выигрышей игроков должна соответствовать их воз-

i € JV.

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

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

Пусть, например, в процессе игры трех лиц образовалась коалиционная структура^[1], содержащая коалицию К = {1,2}, в которую входят игроки с номерами 1 и 2. При распределении дохода коалиции и ({1, 2}) игроки 1 и 2 получают суммы х_х и х₂ соответственно. Тогда, если игрок 1 недоволен таким распределением, он может сказать своему партнеру, что если его доля дохода не будет увеличена, то он сформирует коалицию L = {1,3}, где сможет рассчитывать на больший выигрыш. Если такая коалиция L может образоваться, т. е. если игроку 3 действительно выгодно вступать в коалицию с игроком 1, то такое заявление называется угрозой игрока 1 игроку 2.

В свою очередь игрок 2 может заявить игроку 1, что в случае подобных его действий он может предложить игроку 3 такую конфигурацию коалиционной структуры^[2], что игрок 3 получит больший доход, чем в I, а сам игрок 2 получит не меньше, чем в исходной К. Таким образом, игрок 2 выдвигает контругрозу, защищающую его долю х₂> и т. д. Если в результате такого переговорного процесса складывается некоторая коалиционная структура, то говорят о равновесии в угрозах и контругрозах. Такой подход позволяет получить определение переговорного множества как множества таких дележей, при которых для любой угрозы игрока i против любого другого игрока j существует контругроза игрока j против угрозы игрока i.

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

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

Дележ х доминирует дележ у, если существует такая коалиция К, для которой дележ х превосходит у для всех членов коалиции К (доминированием: над у по коалиции К):

Наличие доминирования х над у означает, что во множестве игроков N найдется коалиция, для которой х предпочтительнее у. В теории кооперативных игр поиск доминируемых дележей основан на условии предпочтительности, которое предполагает необходимость единодушия в предпочтении со стороны коалиции: если хотя бы одно из неравенств х? > y_i будет нарушено, г. е. если хотя бы для одного из членов коалиции К выигрыш в условиях дележа у будет не меньшим, чем в условиях дележа х, то можно будет говорить о предпочтении дележа х дележу у не всей коалицией К, а только теми ее членами, для которых соответствующее неравенство x_i > у₍ соблюдается.

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

Доказана следующая теорема. Если и, и и₂ — две стратегически эквивалентные характеристические функции, причем дележам х_{ и у_{ соответствуют дележи х₂ и г/₉, то из х_{ > у_{ следует х₂ > у₂.

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

Пример 6.1. Имеется (ОЛ)-редуцированная форма игры трех игроков. Поскольку доминирование невозможно ни по одной из одноэлементных коалиций 1, 2, 3, а также по коалиции, состоящей из всех трех игроков, то доминирование возможно только по одной из двухэлементных коалиций {1, 2}, {1, 3}, {2, 3}. Дележи x_v х₂, х₃ должны удовлетворять неравенствам.

Очевидно из условия дополнительности, что.

Дележ х = (х_р х₂, х₃) доминирует дележ у = (y_v у₂, у₃): по коалиции {1,2}, еслих_{ >у_vx₂>у₂; по коалиции {1,3}, если x_t > у _v х₃ > г/₃; по коалиции {2, 3}, если х₂ > у₂, х₃ > у₃.

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

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

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

• [1] 1,2}, {3
• [2] 1}, {2,3