Теория игр. Оуэн (1971) (Теория игр. Оуэн (1971).djvu), страница 40

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

Прежде всего обозначим через и,' наибольшую полезность, которую может гарантировать себе игрок !, даже если Гя. Х. Модификации понятия игра против него объединились все остальные игроки. Тогда о(М) является не числом, а множеством всех дележей, т. е. множеством всех п-векторов (хь ..., х,), которые могут получить игроки из У, действуя совместно. Тогда, в сущности, множество о(5) будет состоять из всех таких векторов х, что коалиция 5 может гарантировать своим членам соответствующие компоненты х. (Например, множество о(И) будет состоять из всех таких векторов х, что х, ~иг) В силу возможности лотерей ясно, что каждое множество о(5) выпукло; не очевидно, что эти множества должны быть замкнуты, но мы сделаем также и это предположение, которое кажется вполне разумным. Х.2.1. Определение, Игрой и лиц без побочных платежей мы называем пару (о, Н), где Н вЂ” компактное выпуклое подмножество йгн, а о — функция, которая каждому подмножеству 5 множества У = (1,..., и) ставит в соответствие подмножество из )сн, удовлетворяющее условиям (!) о(5) замкнуто и выпукло; (В) если хеп о(5) и у, ( х, для всех 1~ 5, то уев о(5); (ш) если 5ДТ= 8, то о(5)() о(Т) ~ о(50 Т); (1ч) о(5) Ф 8 для всех 5с: Лт; (ч) х я о(У)тогда и только тогда, когда хну для некоторого уяН.

В этом определении условие (!1) есть условие монотонности: если коалиция 5 может гарантировать своим членам х, то она, конечно, гарантирует им меньшую величину у. Условие (ш) есть условие супераддитивностн в новой терминологии. Условие (ч) гарантирует, что множество о(!У) не будет слишком большим; это условие вместе с условием (ш) (если положить Т = йт' 5) гарантирует, что множество о(5) не будет слишком большим. Основываясь на этом определении дележей и характеристической функции, можно определить отношение доминирования. Так, х) у, если существует такая непустая коалиция 5, что хг)у, для ! я 5 и х е= о(5).

НМ-решения и ядро определяются после этого точно так же, как н в случае побочных платежей. Решениям в играх без побочных платежей было посвящено несколько работ. Стирнз (Х. 14) показал, что все игры трех лиц имеют по крайней мере одно решение; кроме того, эти решения были классифицированы. Однако вопрос о существовании решений в произвольных играх был решен отрицательно: Стирнз (Х. 15) привел пример игры семи лиц, не имеющей решений.

Ядру в играх без побочных платежей также было посвящено несколько работ. В сущности, вектор хев о(Л~) принадлежит ядру, Х. А Игры, заданные в форме функции разбиения 205 если для каждой коалиции 5 и каждого у ~ о(5) существует такое 1 еи 5, что хг ~ уь Можно также рассматривать такие игры в нормальной форме, а не в форме характеристической функции. Рассматривая бескоалиционные игры, мы определяли ситуацию равновесия как такой набор п стратегий, что ни один игрок не мог выгадать односторонним изменением своей стратегии. Теперь мы можем определить сильно равновесную ситуацию как такой набор п стратегий (которые могут, если это необходимо, выбираться совместно), что не существует коалиции 5, которая может увеличить полезность всех своих членов, если остальные игроки придерживаются своих первоначальных стратегий.

Однако это определение слишком сильно; большинство игр не имеет сильно равновесных ситуаций. Ауманн [Х. Ц рассматривал эти игры в предположении, что они разыгрываются повторно бесконечное число раз. Такой подход приводит к «сверхигре»; далее в этой сверхигре применяются такие стратегии, в которых, вообще говоря, фактический ход в каждой партии исходной игры зависит от исходов предыдущих игр, Затем, как только что было описано, в этой сверхигре определяются сильно равновесные ситуации. К сожалению, многие игры не имеют сильно равновесных ситуаций даже в этом более слабом смысле, Наконец, для этих игр было определено понятие значения.

Для этого было предложено несколько схем. Шепли [Х.!3) сначала находит вектор Шепли, сделав предположение, что могут производиться побочные платежи. Далее, если это значение можно получить без использования побочных платежей, то Шепли предлагает его в качестве значения исходной игры. На остальные игры значение обобщается введением требования, состоящего в том, что значение должно быть инвариантно относительно линейных преобразований функции полезности любого игрока. Этого оказывается достаточно, чтобы определить значение для любой игры. Харшаньи [Х.

4, Х. 5) приводит две модели сделок (одна из которых является модификацией друхдй), основанных на обобщении аксиом Нэша для кооперативных игр двух лиц. Исбелл [Х. 6) предполагает, что пространство полезностей каждого игрока ограничено (имеет внд [О, Ц). Он использует схему сделок, которая сохраняет отношения полезностей.

Миясава [Х. 10) также предлагает обобщение модели Нэша. Селтен [Х. 12) исследует с аксиоматической точки зрения несколько схем, определяющих значение. Х.З. ИГРЫ, ЗАДАННЫЕ В ФОРМЕ ФУНКЦИИ РАЗБИЕНИЯ Одно из предположений, сделанных в самом начале нашего определения характеристической функции фон Неймана †Моргенштерна, состояло в том, что когда образуется коалиция 5, мы Гл. Х. Модификации понятия игры 206 должны рассматривать наихудший для нее исход.

Таким образом, мы допускаем возможность того, что образуется дополнительная коалиция У ',о. Хотя это предположение разумно с точки зреннтк принципа минимакса, тем не менее ясно, что во многих случаях коалиция М ', 5 образована не будет из-за трудностей общения личных антипатий между игроками, отсутствия побудительных мотивов или же по многим другим причинам. Что произойдет тогда в предположении, что коалиция ЛГ~Я не будет образована? Ясно, что величина, которую коалиция 5 может получить, будет зависеть от конкретной коалиционной структуры.

Так, в игре голосованик коалиция, имеющая меньше абсолютного большинства голосов,выиграет, потому что ее противники не смогут прийти к соглашению, а некоторые могут вовсе не голосовать. Эти соображения приводят. нас к идее об игре в форме функции разбиения. Х. 3.1. О п р е д е л е н и е. Игра в форме функции разбивнитс есть функция о, которая каждому разбиению 9т = (Рь..., Ри) множества М ставит в соответствии Й-вектор о~=(о~(Р,), о~(Рт), ..., ов'(Р )). Таким образом, функция разбиения задает величину, которую получит каждая коалиция в У' в предположении, что достигнуто разбиение (коалиционная структура) У.

Однако, как и в теории фон Неймана — Моргенштерна, мы интересуемся максимальной величиной, которую может гарантировать себе коалиция 5, что бы ни делали остальные игроки. Эта величина определяется формулой (!0.3.1) и(я) = ппп оя'(В). в о. я' Нужно заметить, что функция множества и необязательно супераддитивна.

Этот факт обьясняется тем, что в некоторых случаях коалиции между антагонистическими группами фактически могут ослаблять эти группы. Понятие дележа должно быть модифицировано: Х.3.2. Определение. Дележ в игре и лиц, заданной в форме функции разбиения о, есть и-вектор х = (хь...,х„), удовлетворяющий условиям (1) х, ~ и((т)); (И) ~ х,= ~ ов'(о) для некоторого у. с-1 в гт Таким образом, в этих играх компоненты дележа не всегда имеюг одну и ту же сумму. Понятие доминирования также несколько мни ияется. Х.

8. Игры, заданные е форме функции разбиения , 207 Х.З.З. О яр еде ление. Говорят, что дележ х доминирует дележ у по коалиции 5 (обозначение: х)зу), если выполнены условия (() хг) уг для (я В. (й) Х хг йи(Я); гаэ (й!) существует такое У, что о ~У и и :Е~ х;= ~ вге(Г). таге Первые два условия те же самые, что и раньше; третье, новое условие, называется условием реализуемости.

Мы могли бы сказать, что в общем случае каждое разбиениеУ дает различное значение сумме Х ого(о)=)(У~!. 3 аге 'Тогда игры фон Неймана — Моргенштерна могут рассматриваться как вырожденный специальный случай, в котором при образовании любой коалиционной структуры сумма' полезностей, получаемых игроками, всегда одна и та же. Далее, мы видели, что игры фон Неймана — Моргенштерна очень часто имеют значительное число НМ-решений. Оказывается, что эта неоднозначность НМ-решений есть следствие именно вырожденности характеристической функции.

Действительно, мы имеем следующую теорему. Х. 3.4. Т е о р е м а. Если о — такая игра четырех лиц, что для всех разбиений числа зУ)( различны то о имеет единственное релиение. Эту теорему мы докажем ниже, Однако нам необходимо прежде всего заложить фундамент доказательства, Мы будем говорить, что коалиция 5 эффективна для дележа х, если ~ х,~и(5), 1яэ и строго эффективна, если ~ х,(и(Я). ем Э Х. 3.5. Л е м м а.

Никакой дележ х не может доминировать другой дележ у по коалиции (г), состоящей из одного игрока. Д ока за тель ство. Если х) ~г1 у, то мы должны иметь уе и„ -т. хе лв и((г)). Но зто означает, что у не является дележом. Гл Х. Модификации понятия игры Х.3.6. Л е м ма. Если х>ау и у; ~ г, для всех Е е= 5, то х>вг. Доказательство очевидно. Х.3.7. Лемма.

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