Рассмотрим с позиций стратегической эквивалентности несущественные игры.
Нулевой называется характеристическая функция, тождественно равная нулю. Кооперативная игра с множеством игроков I называется нулевой, если все значения ее характеристической функции равны нулю.
Теорема. Всякая существенная игра аффинно эквивалентна нулевой игре.
Следствие. Все несущественные игры с одним и тем же множеством игроков аффинно эквивалентны друг другу.
Таким образом, свойства любой несущественной игры можно изучать по эквивалентной ей нулевой игре. В нулевой игре все игроки безразличны к ее исходам, это случай полной незаинтересованности.
Для изучения существенных игр наиболее удобна a-b редуцированная форма, то есть такая, в которой v(i) = a, v(I) = b. Обычно используются варианты a=0, b=1 и a=1, b=0.
Теорема. Всякая существенная игра аффинно эквивалентна одно и только одной игре в 0-1 редуцированной форме.
То есть любую существенную кооперативную игру можно свести к редуцированной форме и в этом виде производить ее исследование и изучение. От существенной кооперативной игры к ее редуцированной форме можно перейти следующим образом. Для произвольной коалиции К:
v’(K) = ( v(K) - å iÎK v(i))/ ( v(I) - å iÎI v(i)) (3.1.)
Нетрудно видеть, что 0-1 редуцированная форма существенной кооперативной игры позволяет по характеристической функции сразу же судить об эффективности обьединения в коалицию (см.знаменатель), то есть в чистом виде рассматривать свойство супераддитивности.
Все дележи в 0-1 редуцированной форме должны отвечать условиям: xi ³0, так как v(i) = 0, но есть еще D, так как игра существенная å xi = v(I) = 1.
Пример. Дана кооперативная игра, I = {1,2,3,4}. Задана характеристическая функция: v(1) = -1; v(2) = v(3) = -2; v(1,2,4) = v(1,3,4) = 2; v(2,3,4) =1;
v(4)= v(1,2)= v(1,3) = v(1,4) = v(2,3)= v(2,4) = v(3,4) = v(1,2,3) = v(1,2,3,4) = 0;
Найти характеристическую функцию 0-1 редуцированной формы.
Воспользуемся формулой 3.1. В знаменателе выражения стоит постоянная величина v(I) - å iÎI v(i) = 0 - (-1-2-2) = 5. Остальные вычисления занесем в таблицу:
| К | 1 | 2 | 3 | 4 | 12 | 13 | 14 | 23 | 24 | 34 | 123 | 124 | 134 | 234 | 1234 |
| v’ | 0 | 0 | 0 | 0 | 0,6 | 0,6 | 0,2 | 0,8 | 0,4 | 0,4 | 1 | 1 | 1 | 1 | 1 |
4. Доминирование дележей.
Рассмотрим кооперативную игру Г = < I, v > и два дележа в этой игре: х = ( х1, х2, ... хn) и y = ( y1, y2, ... yn). Допустим, K Ì I - некоторая коалиция в игре.
Дележ х доминирует дележ у по коалиции К, если выполняются неравенства å iÎK хi £ v(К) и хi > yi , iÎ К. Доминирование дележа по коалиции К обозначается хñК у, х dom К y, или x Rк y.
Первое неравенство определения утверждает, что коалиция К способна обеспечить такой дележ, так как сумма выигрышей, получаемых членами коалиции не превышает ее максимального гарантированного выигрыша V(K). Второе означает, что каждый член коалиции К получает по дележу х больше, чем по дележу у ( именно в этом смысл доминирования). Иногда, определяя отношение доминирования, не указывают конкретно коалицию, а просто говорят, что дележ х доминирует дележ у (хñ у). Однако, при этом подразумевается, что существует коалиция К, по которой это доминирование имеет место, то есть справедливо хñК у.
Для коалиции К доминирующий дележ полезнее, чем доминируемый. Эта коалиция будет его отстаивать. Иной случай, когда с этим дележом не согласятся остальные игроки (входящие в множество I\K). Но коалиция К может сама обеспечить себе такой дележ, так как å iÎK хi £ v(К).
Следует отметить, что доминирование возможно по любой коалиции, кроме коалиции из одного игрока и из всех игроков. В первом случае К = {i} из определения следует, что хi £ v(i), что противоречит свойству индивидуальной рациональности дележа х ( х ³ v(i)).
В случае К = I из хi > yi следует , что åхi > åyi = v(I), то есть дележ х должен давать в сумме больше, чем гарантированный выигрыш для всех игроков.
Важно, что отношение доминирования дележей выполняется для аффинно эквивалентных кооперативных игр, то есть доминирование инвариантно относительно аффинной эквивалентности.
Теорема. Если v и v’ - аффинно-эквивалентные характеристические функции, причем дележам х и у в v соответствуют дележи x’ и y’ в v’, то из х ñК у следует х’ ñК у’.
Отношение доминирования выполняется для всех кооперативных аффинно эквивалентных игр и является свойством не одной игры, а всего класса эквивалентных игр. Поскольку, например, в несущественной игре всего один дележ, то для них понятие доминирования не имеет смысла. Существенные игры исследовать на доминирование можно используя 0-1 редуцированную форму.
Так как в кооперативной игре в качестве меры полезности выступает не выигрыш, а дележ, поэтому сравнение кооперативных игр сводится к сравнению векторов дележей. Множество дележей дает набор возможных решений, так как дележи отвечают условиям индивидуальной и коллективной рациональности. Но дележей много и они разные. Какой из них предпочесть? Это задача векторной оптимизации, а принцип оптимизации может быть самым разнообразным.
В достаточно общей модели принятия решения трудно сказать принимающему решение, какую альтернативу он должен выбрать или какая его стратегия является оптимальной. Главным в такой модели является прогноз действий партнеров, так как если он имеется, то остальное - сравнительно простая задача максимизации выгоды участника в условиях риска. Поэтому оптимальность в теории игр и понимается как ожидаемое, возможное. Оптимальными исходами называются исходы, возможные в условиях допустимых действий игроков и коалиций, совершаемых согласно их интересам.
Например,в игровой модели Шепли-Шубик, 1969 года (кооперация производства с обменом продуктами) или просто модели обменов, вопрос о том, как кооперировать, может быть заменен вопросом: какое понятие оптимальности следует применять для дележа прибыли?
Ответить на этот вопрос по заданной характеристической функции невозможно, поскольку ответ существенно зависит от дополнительных свойств модели. Например, правила дележа будут различными в зависимости от того, является ли правило обьектом переговоров между участниками кооперации или оно издается правительством в качестве закона и поэтому должно соблюдаться в принудительном порядке. В каждом из этих двух случаев существенными могут оказаться и другие условия. Может потребоваться такое правило, при котором партнеры по кооперации будут незаинтересованы скрывать друг от друга свои ресурсы ( делать их дефицитными для модели) или отказываться от запланированных поставок. Иногда приходится не забывать об элементарном требовании, чтобы никто не получал доли прибыли без соответствующего вклада в общий выпуск, и т.д.
В общем, принцип оптимальности с точки зрения приложений есть такое правило, какое нужно для решения рассматриваемой проблемы.
Рассмотрим в качестве принципов оптимизации устойчивость коалиционной структуры и принцип справедливости.
Эксцессом дележа х для коалиции К в условиях характеристической функции v называется разность
ev(x,K) = v(K) - å iÎK хi , колторая показывает, насколько может коалиция К увеличить свой выигрыш по сравнению с суммой, предлагаемой по дележу. Если эксцесс положителен, то соответственный дележ реализуем для данной коалиции, в этом случае дележ называется эффективным.
Если дележ не эффективен, то это значит, что сумма платежей превышает выигрыш коалиции. Коалиция увеличить его не может, поэтому неэффективный дележ оптимален по принципу устойчивости.
Дележ называется абсолютно неэффективным, если он не эффективен ни для какой коалиции.
Для игры с постоянной суммой эксцесс положителен и всегда эффективен.
Пример. Рассмотрим существенную игру трех лиц с постоянной суммой. С позиций доминирования в этой игре можно рассматривать только коалиции {1,2}, {1,3}, {2,3}. Пусть х = ( х1, х2, ... хn) и y = ( y1, y2, ... yn) - дележи и х dom 1,2 y . Из определения доминирования следует, что должно выполняться
х1+ х2 = 1 - х3 £ v(1,2) и х1 > у1 , х2> у2 .
Поскольку по свойству дополнительности для 0-1 редуцированной формы v(1,2) = v (1,2,3) - v(3) = 1 - 0 = 1, то неравенство x1 + x2 = 1 - x3 £ 1 всегда выполняется. Вторая группа неравенств из определения доминирования дележей и х1 > у1 , х2> у2 и условие ее выполнения лучше всего иллюстрируются графически.
Так как рассматривается 0-1 редуцированная форма, то
х1+ х2+ х3 = y1+ y2+ y3 = 1 и любой дележ в такой задаче можно представить как точку симплекса, задаваемую барицентрическими координатами.
Симплекс - простейший выпуклый многогранник данного числа измерений n. При n = 3 cимплекс - произвольный, в том числе неправильный тетраэдр. При n = 2 симплекс - произвольный треугольник, при n = 1 - отрезок, при n = 0 - одна точка, таким образом, n-мерный симплекс имеет n+1 вершину.