Computer Science МФТИ Changes    |    Index    |    Search
::: CooperativeGame :::
Parents: ViktoryaSavraeva?
 
  ACM . Agent . CooperativeGame # Edit # Attach # Diffs # Printable # More :::

Main
• Register
• Users
• Site Map

Curriculum

Agent Web
• projects

Algorithms

Web Learn

Image Kit

ProgTech

Publishing

КООПЕРАТИВНЫЕ ИГРЫ

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

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

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

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

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

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

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

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

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

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

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

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

v(0)= 0,

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

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

v(K+L)>=v(K)+v(L), если K, L из N, K*L не= 0,

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

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

v(K)+U(N\K)=U(N) (1)

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

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

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

x_1+x_2+...=U(N) (3)

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

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

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

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

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

x_i=U(i)+a_i, (i из N)_

причём

a_i>=0 a_1+a_2+...=U(N)-U(1)-U(2)-... (4)

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

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

U(K) + U(L) < U(K+L),

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

U(K) + U(L) = U(K+L),

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

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

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

U(1)+U(2)+... = U(N)

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

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

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

(U(1)+ a_1,U(2)+a_2,...,U(n)+a_n)

где

a_i>=0 Кооперативная игра с множеством игроков N и характеристической функцией U называется стратегически эквивалентной игрой с тем же множеством игроков и характеристической функцией U^1 , если найдутся такие k>0 и произвольные вещественные C_i ( i из N ), что для любой коалиции К из N имеет место равенство:

U^1(K)=k*U(K)+C_1+C_2+... (5)

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

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

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

U~U.

2. Симметрия , т.е.

если U=U^1 , то U^1=U .

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

если U=U^1 и U^1=U^2 , то U=U^2 .

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

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

пусть U=U_1 , т.е. выполняется (5), и x=(x_1,...,x_n) — дележи в условиях характеристической функции U ; рассмотрим вектор x^1 = (x_1^1, ..., x_n^1) , где x_1^1=k*x_i+C_i ; для него выполняется

x_i^1 = k*x_i + C_i>=k*U(i)+С_i=U_1^1(i) т.е. выполняется условие индивидуальной рациональности, и

x_1^1+x_2^1+...=k*x_1+C_1+k*x_2+C_2+...=k*(x_1^1+x_2^1+...)=k*U(N)+C_1+C_2+...=U^1(N)

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

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

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

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

U (i) = 0 ( i из N ),

U(N) = 1.

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

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

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

x_i>0 .

К числу важнейших понятий решения для кооперативных игр относится понятие C-ядра , определение которого опирается на отношение доминирования на множестве дележей. Это отношение определяется следующим образом. Пусть x и y два дележа, а K - некоторая коаллиция. Говорят, что x доминирует y по коаллиции S, если 1) x_i>y_ii из N , 2) x(K)<=U(K) . Второе условие означает, что распределение, соответствующее x , действительно может быть обеспечено коаллицией K . В этом случае говорят также, что коаллиция K блокирует дележ y .

Говорят, что x доминирует y , если найдется такая коаллиция K , что x доминирует y по коаллиции K .

Определение . С-ядром С(U) игры U называется множество всех ее недоминируемых дележей .

Пример . Пусть имеется (0,1)-редуцированная форма существенной игры трёх игроков с постоянной суммой (равной 1). Поскольку доминирование невозможно ни по одной из одноэлементных коалиций 1,2,3, а также по коалиции, состоящей из всех трёх игроков, то доминирование возможно только по одной из двухэлементных коалиций {1,2}, {1,3}, {2,3}. Для наглядности доминирования дележей введём понятие бароцентрических координат. Осями координат служат три оси x1, x2, x3, составляющие между собой одинаковые углы 60о, ось x3 находится на расстоянии единицы от точки пересечения осей x1 и x2 (рис.1), координаты точки x = (x1, x2, x3) - соответственно расстояния от этой точки до осей x1, x2, x3, взятые с такими знаками, как указано на рис.1. (Например, для точки x на рис.1. x1 < 0, x2 > 0, x3 > 0).

grafik11.GIF

В барицентрической системе координат всегда выполняется равенство

x1 + x2 + x3 = 1. (6)

В плоскости всегда имеется точка с координатами x1, x2, x3, удовлетворяющими равенству (6). По этому бароцентрическая система координат автоматически удовлетворяет одному из условий, определяющих исход игры трёх игроков. С другой стороны, поскольку игра в (0, 1)-редуцированной форме, то точка x должна находиться в заштрихованном треугольнике (см. рис. 2). Дележи x1, x2, x3 должны удовлетворять неравенствам

x1+x2<=U(1,2), x1+x3<=(1,3), x2+x3<=(2,3).

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

x1+x2=1-x3<=1=U(1,2), x1+x3<=1, x2+x3<=1.

Делёж x = (x1, x2, x3) доминирует дележ y = (y1, y2, y3)

по коалиции {1, 2}, если x1 > y1, x2 > y2;

по коалиции {1, 3}, если x1 > y1, x3 > y3;

по коалиции {2, 3}, если x2 > y2, x3 > y3,

т.е. если делёж y находится в одном из заштрихованных параллелограммов (за исключением трёх граничных прямых, проходящих через точку x) на рис. 3, то делёж x доминирует делёж y, а всякая точка находящаяся в не заштрихованных треугольниках, является предпочтительнее исхода x.

grafik22.GIF

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

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

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

f_1+f_2+...=U(S) i из S

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

2. Аксиома симметрии . Для любой перестановки P и i из N должно выполняться

f_p_i(pU)=f_i(U) ,

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

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

f_i(U'+U'')=f_i(U')+f_i(U'') ,

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

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

f(U)=(f_1(U),f_2(U),...,f_n(U)) ,

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

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

a1 = 10, a2 = 20, a3 = 30, a4 = 40.

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

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

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

{1; 2; 3; 4}.

Найдём вектор Шепли для этой игры.

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

f1=(t-1)!(n-t)!/n!=2!*1!/4!=1/12

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

f2=1/12+1/12+1/12=1/4

Аналогично получаем, что f3=1/4, f4=5/12.

В результате получаем, что вектор Шепли равен (1/12;1/4;1/4;5/12).

При этом, если считать, что вес голоса акционера пропорционален количеству имеющихся у него акций, то получим следующий вектор голосования

(1/10;2/10;3/10;4/10)

который, очевидно, отличается от вектора Шепли.

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

В статье использованы материалы лекций по "Теории игр" Коновалова А.П.(Одесский политехнический университет)

  • vdv-0403.rar: Лекции по "Теории игр" Коновалов А.П.

Attachment sort Action Size Date Who Comment
vdv-0403.rar manage 244.4 K 25 Dec 2004 - 08:11 ViktoryaSavraeva? Лекции по "Теории игр" Коновалов А.П.

Rambler's Top100 Rambler's Top100


# Edit menu  

Topic revision r1.7 - 25 Dec 2004 - 08:07 GMT - ViktoryaSavraeva?
Topic parents: ViktoryaSavraeva?
Copyright © 2003-2017 by the contributing authors.

Agent.CooperativeGame moved from Main.Article on 21 Dec 2004 - 08:31 by AndreyUstyuzhanin - put it back