Игры с характеристическими функциями

  

                                       Игры с характеристическими

                                     функциями. 

           Природа и структура кооперативных игр n лиц

 

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

Объединение игроков  из S означает превращение их в единого игрока I, стратегией которого являются всевозможные совместные действия составляющих его игроков из S, а выигрышем - сумма выигрышей игроков i Î S. В худшем для объединённого игрока I случае игроки из I/S могут также объединиться в некоторого коллективного игрока II с интересами, диаметрально противоположными интересами игрока I. В результате коалиция S (как игрок I) может себе гарантировать выигрыш v(S), равный значению возникающей антагонистической игры. Иными словами v(S) - гарантированное математическое ожидание выигрыша игроков коалиции S, действующих совместно против объединённых игроков коалиции I/S. Мы будем предполагать, что значение v(S) существует для любой коалиции SÌI.

            Определение.  Кооперативной игрой n лиц  называется пара (I, v); где I = {1, 2, ..., n},  v(v(Æ) =  0) - функция, определённая на всех подмножествах SÌI. Функция v называется характеристической функцией.

Таким образом  кооперативную игру n лиц можно анализировать с помощью характеристической функции, область определения которой состоит из 2 возможных подмножеств множества I. Если для всех непересекающихся подмножеств S и T (S,TÌI и SÇT = Æ) выполняется неравенство

                                      v(S)  +  v(T)  £  v(SÈT) ,

то характеристическая функция называется супераддитивной. Это свойство содержательно выражает то обстоятельство, что объединение игроков в коалиции является целесообразным с точки зрения увеличения выигрыша, то есть условие v(S)  +  v(T)  £  v(SÈT) отражает разумность коллективистической точки зрения.

Методом математической индукции из неравенства v(S)  +  v(T)  £  v(SÈT) не трудно получить следующее неравенство:

                                                   k                              k

                                                   å v(Si) £  v ( ÈSi),

                                                     i=1                 i=1

 где Si - непересекающиеся коалиции. Следовательно,         å v ({i}) £ v(I).

                                                                                                   iÎI

В дальнейшем величина v ({i}) будет обозначатся через v(i).

Определение. Игра называется существенной, если  å v (i) < v(I).

                                                                                         iÎI

В противном  случае игра (I, v) называется несущественной.

Обозначим через  xi сумму, которую получит игрок iÎI при распределении полезности, имеющийся в распоряжении множества игроков I , и дадим следующее определение.

Определение. Дележом  называется вектор х = (х1, х2, ..., хn), удовлетворяющий условиям xi ³ v(i) для всех iÎI,           å xi = v(I).           

                                                                                                         iÎI

Условие (xi ³ v(i) для всех iÎI) называется условием индивидуальной рациональности и характеризует предположение, что, участвуя в коалиции, каждый игрок получает по меньшей мере столько, сколько он мог получить. Действуя самостоятельно и не заботясь о согласии каких-либо других игроков. В противном случае он в распределении х будет получать меньше, чем v(i), и тем самым это распределение не будет реализовано. Вполне обоснованно также условие å xi = v(I), так как в случае å xi < v(I) существует распределение x¢, при

                        iÎI                                                                        iÎI

котором каждый игрок iÎI получит больше, чем его доля xi . Если же  å xi  > v(I),

                                                                                                                                                                                                        iÎI

то игроки из I делят между собой нереализуемую полезность, и поэтому вектор x неосуществим. Следовательно, вектор х может считаться допустимым только при выполнении условия å xi = v(I), которое называется условием коллективной      

                                                                          iÎI

(или групповой  ) рациональности.

На основании  условий xi ³ v(i) для всех iÎI,  å xi = v(I) для  того  чтобы  вектор

                                                                                                                               iÎI

 х = (х1, х2, ..., хn) был дележом в кооперативной игре (I, v), необходимо и достаточно выполнение равенства         xi = v(i) + ai ,      iÎI,      

причём     ai ³ 0, iÎI,               å ai = v(I) - å v(i).

                                                                                     iÎI                            iÎI 

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

                                                    
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

                                Примеры  задач  решаемых

                            в кооперативных играх. 
 

Игра  «Землепользование». 

Данная полоса земли оценивается её владельцем (n1) , при использовании её в сельскохозяйственных целях, в 100000 $ . Один из её возможных будущих владельцев (n2) , планирует её промышленное использование и считает, что её стоимость - 200000 $ . Тот игрок (n3), который хочет продавать землю частями, оценивает её в 300000 $. Других покупателей нет. Тогда характеристическая функция задаётся в следующем виде:   v({1}) = 100000 ,  v({2}) = 0,  v({3}) = 0

                                                  v({1,2}) = 200000,  v({1,3}) = 300000 , v({2,3}) = 0     

                                                  v({1,2,3}) = 300000

 Требуется  узнать - состоится ли продажа,  и если - да, то кому и по какой цене.

Ответ: если покупатели не будут вступать в коалиции, то земля будет продана за 100000 $ первому игроку; если какие-нибудь два покупателя договорятся между собой, то земля будет продана коалиции, состоящей из 1 и 3 игрока, за 300000 $;

если же все покупатели создадут единую коалицию, то земля будет продана 1,2 и 3 игроку, за 300000 $. 

Игра  «Комитет Федерального Собрания»     

В комитет Федерального Собрания входят 3 члена Государственной  Думы и 3 члена Федерального Собрания Р.Ф. Решение принимается, если его поддерживает ³ 2 членов Думы и ³ 2 членов Федерального Собрания. Найти характеристическую функцию этой игры.

v(P) + v(T) = v(S)  , T ³ 2,  P ³ 2  Þ  v(S) = k , S ³ 4 , k - принятие решения. 

Ответ:   v(S) = k , S ³ 4 , k - принятие решения. 
 

Игра  «Озеро». 

Вокруг озера  расположено n предприятий. Мы допускаем, что обработка стоков перед их сбросом в озеро стоит предприятию В, а очистка воды для собственных нужд - kC, где k равно числу предприятий, не обрабатывающих свои отходы. Показать, что v(S) = - S n C ,если S £ B/C    v(S) = -S n C + S(SC-B) , если S ³ B/C , где S = çSï. 

В первом случае (v(S) = - S n C ,если S £ B/C) в коалицию вступили предприятия, которые договорились, чтобы не тратить деньги зря на очистку отходов, очищать воду только для своих нужд. Из условия S £ B/C вытекает, что это возможно только при В>C , иначе предприятиям было бы не выгодно вступать в подобную коалицию.

Во втором случае (v(S) = -S n C + S(SC-B) , если S ³ B/C) предприятия тратят деньги на очистку своих отходов, а также (если S>B/C) и на очистку воды для себя. Если подставить конкретные значения в решаемую задачу, то можно получить график v(S) из которого следует, что оптимальное количество предприятий вошедших в данную коалицию должно быть равно (n/2 + 1), то есть чуть больше половины.