77403-1 (612449)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Кооперативные игры

Кооперативные игры получаются в тех случаях, когда, в игре n игроков разрешается образовывать определённые коалиции. Обозначим через N множество всех игроков, N={1,2,...,n}, а через K любое его подмножество. Пусть игроки из K договариваются между собой о совместных действиях и, таким образом, образуют одну коалицию. Очевидно, что число таких коалиций, состоящих из r игроков, равно числу сочетаний из n по r , то есть , а число всевозможных коалиций равно

= 2ⁿ 1.

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

Функция , ставящая в соответствие каждой коалиции K наибольший, уверенно получаемый его выигрыш (K), называется характеристической функцией игры. Так, например, для бескоалиционной игры n игроков (K) может получиться, когда игроки из множества K оптимально действуют как один игрок против остальных N\K игроков, образующих другую коалицию (второй игрок).

Характеристическая функция называется простой, если она принимает только два значения: 0 и 1. Если характеристическая функция простая, то коалиции K, для которых (K)=1, называются выигрывающими, а коалиции K, для которых (K) = 0, проигрывающими.

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

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

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

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

Обозначим через _G характеристическую функцию бескоалиционной игры. Эта функция обладает следующими свойствами :

персональность

_G() = 0,

т.е. коалиция, не содержащая ни одного игрока, ничего не выигрывает;

супераддитивность

_G(KL) _G(K) + _G(L), если K, L N, KL ,

т.е. общий выигрыш коалиции не меньше суммарного выигрыша всех участников коалиции;

дополнительность

_G(K) + (N\K) = (N)

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

Распределение выигрышей (делёж) игроков должно удовлетворять следующим естественным условиям: если обозначить через x_i выигрыш i-го игрока, то, во-первых, должно удовлетворяться условие индивидуальной рациональности

x_i ( i ), для i N

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

= (N)

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

Таким образом, вектор x = (x₁, ..., x_n), удовлетворяющий условиям индивидуальной и коллективной рациональности, называется дележём в условиях характеристической функции .

Система {N, }, состоящая из множества игроков, характеристической функции над этим множеством и множеством дележей, удовлетворяющих соотношениям (2) и (3) в условиях характеристической функции, называется классической кооперативной игрой.

Из этих определений непосредственно вытекает следующая

Теорема. Чтобы вектор x = (x₁, ..., x_n) был дележём в классической кооперативной игре {N, },

необходимо и достаточно, чтобы

x_i = ( i ) + _i, (iN)

причём

_i 0 (iN)

= (N)

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

Кооперативные игры считаются существенными, если для любых коалиций K и L выполняется неравенство

(K) + (L) < (KL),

т.е. в условии супераддитивности выполняется строгое неравенство. Если же в условии супераддитивности выполняется равенство

(K) + (L) = (KL),

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

Справедливы следующие свойства :

1) для того чтобы характеристическая функция была аддитивной (кооперативная игра несущественной), необходимо и достаточно выполнение следующего равенства:

= (N)

2) в несущественной игре имеется только один делёж

{(1) , (2) , ... , (n) };

3) в существенной игре с более чем одним игроком множество дележей бесконечно

( (1) + ₁ , (2) + ₂ , ... , (n) +_n )

где

_i 0 ( i N ) , (N) — 0

Кооперативная игра с множеством игроков N и характеристической функцией называется стратегически эквивалентной игрой с тем же множеством игроков и характеристической функцией ¹ , если найдутся такие к 0 и произвольные вещественные C_i ( iN ), что для любой коалиции К N имеет место равенство:

¹(K) = k (K) +

Смысл определения стратегической эквивалентности кооперативных игр (с.э.к.и.) состоит в том что характеристические функции с.э.к.и. отличаются только масштабом измерения выигрышей k и начальным капиталом C_i . Стратегическая эквивалентность кооперативных игр с характеристическими функциями и ¹ обозначается так ¹. Часто вместо стратегической эквивалентности кооперативных игр говорят о стратегической эквивалентности их характеристических функций .

Справедливы следующие свойства для стратегических эквивалентных игр:

1. Рефлексивность, т.е. каждая характеристическая функция эквивалентна себе .

2. Симметрия, т.е. если ¹, то ¹.

3. Транзитивность, т.е. если ¹ и ¹², то ².

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

Отношение стратегической эквивалентности игр и их характеристических функций переносится на отдельные дележи :

пусть ¹ , т.е. выполняется (5), и x = (x₁, ..., x_n) дележи в условиях характерис- тической функции ; рассмотрим вектор x¹ = ( , ..., ) , где = k x_i+C_i ; для него выполняется

= k x_i + C_i k ( i ) + С_i = ¹( i );

т.е. выполняется условие индивидуальной рациональности, и

= = k + = k (N) + = ¹(N)

т.е. выполняется условие коллективной рациональности. Поэтому вектор является дележом в условиях ¹. Говорят, что делёж x¹ соответствует дележу x при стратегической эквивалентности ¹.

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

Всякая несущественная игра стратегически эквивалентна нулевой .

Определение. Кооперативная игра с характеристической функцией имеет (0,1)-редуцированную форму, если выполняются соотношения :

( i ) = 0 ( i N ),

(N) = 1.

Теорема. Каждая существенная кооперативная игра стратегически эквивалентна одной и только одной игре в (0,1)-редуцированной форме.

Сформулированная теорема показывает, что мы можем выбрать игру в (0,1)-редуцированной форме для представления любого класса эквивалентности игр. Удобство этого выбора состоит в том, что в такой форме значение (K) непосредственно демонстрирует нам силу коалиции S (т.е. ту дополнительную прибыль, которую получают члены коалиции, образовав её), а все дележи являются вероятностными векторами.

В игре в (0,1)-редуцированной форме дележём является любой вектор x = (x₁, ..., x_n), для которого

x_i 0 (i N) = 1.

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

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

Рассмотрим сначала классы игр в (0,1)-редуцированной форме для случая игр с нулевой суммой.

1. Игры 2-х игроков. Всякая кооперативная игра двух игроков с нулевой суммой является несущественной.

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

¹(1) = 0, ¹(2) = 0, ¹(1,2) = 1

По свойству дополнительности должно

¹(2) = ¹(1,2) ¹(1) = 1 0 =1,

что противоречит (*). А это значит, что наше предположение о существенности кооперативной игры двух игроков с нулевой суммой неверно.

Итак, класс кооперативных игр двух игроков с нулевой суммой ограничивается несущественными играми.

2. Игры 3-х игроков. Пусть характеристическая функция существенной игры в (0,1)-редуцированной форме, тогда

(1) = (2) = (3) = 0, (1,2,3) = 1.

По свойству дополнительности имеем :

(1,2) = (1,2,3) (3) = 1 0 =1,

(1,3) = (1,2,3) (2) = 1 0 =1,

(2,3) = (1,2,3) (1) = 1 0 =1,

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

3. Игры 4-х игроков. Рассмотрим все классы стратегической эквивалентности таких игр.

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

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

Список файлов курсовой работы