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

Санкт-Петербургский государственный университет сервиса и экономики Старорусский филиал Реферат

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

Выполнила студентка группы № 26

Яшина Александра

Старая Русса

Содержание Введение

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

2. Решение кооперативной игры при помощи вектора Шепли Заключение Список использованной литературы

Введение

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

В данной работе рассматриваются коалиционные (кооперативные) игры. Так же приведено решение задачи при помощи аксиом Шепли.

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

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

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

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

Гибридные игры включают в себя элементы кооперативных и некооперативных игр. Например, игроки могут образовывать группы, но игра будет вестись в некооперативном стиле. Это значит, что каждый игрок будет преследовать интересы своей группы, вместе с тем стараясь достичь личной выгоды.

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

= 2ⁿ — 1.

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

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

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

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

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

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

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

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

Персональность: u_G—(Ж) = 0, т. е. коалиция, не содержащая ни одного игрока, ничего не выигрывает;

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

u_G (KИL) і—u_G—(K)—+—u_G—(L),—если—K,—L—М—N,—KЗL—№—Ж, т. е. общий выигрыш коалиции не меньше суммарного выигрыша всех участников коалиции;

Дополнительность:

u_G—(K)—+—u—(N\K)—=—u—(N)

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

x_i і—u (i), для i ОN

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

= u (N)

т.е. сумма выигрышей игроков должна соответствовать возможностям (если сумма выигрышей всех игроков меньше, чем? (N), то игрокам незачем вступать в коалицию; если же потребовать, чтобы сумма выигрышей была больше, чем? (N), то это значит, что игроки должны делить между собой сумму большую, чем у них есть). Таким образом, вектор x = (x₁,…, x_n), удовлетворяющий условиям индивидуальной и коллективной рациональности, называется дележём в условиях характеристической функции ?. Система {N, ?}, состоящая из множества игроков, характеристической функции над этим множеством и множеством дележей, удовлетворяющих соотношениям (2) и (3) в условиях характеристической функции, называется классической кооперативной игрой. Кооперативная игра с множеством игроков N и характеристической функцией? называется стратегически эквивалентной игрой с тем же множеством игроков и характеристической функцией ?¹, если найдутся такие к? 0 и произвольные вещественные C_i (i?N), что для любой коалиции К? N имеет место равенство:

u¹ (K) = k u (K) +

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

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

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

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

Одними из наиболее интересных способов решения коалиционных игр являются решения с применением аксиом Шелли.

2. Решение кооперативной игры при помощи вектора Шепли

Аксиомы Шепли:

1. Аксиома эффективности. Если S — любой носитель игры с характеристической функцией u, то

= u (S)

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

2. Аксиома симметрии. Для любой перестановки p и iОN должно выполняться (pu)—=—j_i—(u), т. е. игроки, одинаково входящие в игру, должны «по справедливости» получать одинаковые выигрыши.

3. Аксиома агрегации. Если есть две игры с характеристическими функциями uў—и—uўў, то

j_—i—(uў—+—uўў)—=—j_—i—(uў)—+—j_—i—(uўў),

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

Определение. Вектором цен (вектором Шепли) игры с характеристической функцией u называется n-мерный вектор

j_—(u)—=—(j₁—(u),—j₂—(u),…,—j_n—(u)),

удовлетворяющий аксиомам Шепли.

Существование вектора Шепли вытекает из следующей теоремы

Теорема. Существует единственная функция j, определённая для всех игр и удовлетворяющая аксиомам Шепли.

Определение. Характеристическая функция w_S (T), определённая для любой коалиции S, называется простейшей, если

w_S (T) =

Содержательно простейшая характеристическая функция описывает такое положение дел, при котором множество игроков S выигрывает единицу тогда и только тогда, когда оно содержит некоторую основную минимальную выигрывающую коалицию S. Вектор Шепли содержательно можно интерпретировать следующим образом: предельная величина, которую вносит i-й игрок в коалицию T, выражается как u—(T)——-u (T {i}) и считается выигрышем i-го игрока; g_{i (}T) — это вероятность того, что i-й игрок вступит в коалицию T {i}; j_i—(u) — средний выигрыш i-го игрока в такой схеме интерпретации. В том случае, когда u — простейшая,

Следовательно

где суммирование по T распространяется на все такие выигрывающие коалиции T, что коалиция T {i}не является выигрывающей.

Пример. Рассматривается корпорация из четырёх акционеров, имеющих акции соответственно в следующих размерах

a₁ = 10, a₂ = 20, a₃ = 30, a₄ = 40.

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

{2; 4}, {3; 4},

{1; 2; 3}, {1; 2; 4}, {2; 3; 4}, {1; 3; 4},

{1; 2; 3; 4}.

Найдём вектор Шепли для этой игры. При нахождении j₁ необходимо учитывать, что имеется только одна коалиция T = {1; 2; 3}, которая выигрывает, а коалиция T {1} = {2; 3} не выигрывает. В коалиции T имеется t = 3 игрока, поэтому

.

Далее, определяем все выигрывающие коалиции, но не выигрывающие без 2-го игрока: {2; 4}, {1; 2; 3}, {2; 3; 4}. Поэтому

.

Аналогично получаем, что,. В результате получаем, что вектор Шепли равен. При этом, если считать, что вес голоса акционера пропорционален количеству имеющихся у него акций, то получим следующий вектор голосования, который, очевидно, отличается от вектора Шепли. Анализ игры показывает, что компоненты 2-го и 3-го игроков равны, хотя третий игрок имеет больше акций. Это получается вследствие того, что возможности образования коалиций у 2-го и 3-го игрока одинаковые. Для 1-го и 4-го игрока ситуация естественная, отвечающая силе их капитала.

Заключение

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

1. Большая советская энциклопедия, 1978 г.

2. Теория игр — статья Миркина Б. Г. на портале «Экономика. Социология. Менеджмент» .