Введение

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

Среди направлений теории игр особое место занимают кооперативные игры.

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

Каждая подобная задача описывается с помощью соответствующей игровой модели.

Кооперативное принятие решений

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

Обозначим через N множество всех игроков, причем игроков приня­то различать по их номерам, т.е. N={1,2,...,n}, а через S - любое его под­множество, которое является коалицией. Очевидно, что число коалиций,

состоящих из k игроков, равно числу сочетаний из n по k, то есть Скп, а число всевозможных коалиций равно:^[1]

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

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

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

Если для всех непересекающихся подмножеств А и В выполняется неравенство:

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

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

Характеристическая функция V называется простой, если она при­нимает только два значения: 0 и 1.

Если характеристическая функция V простая, то коалиции S, для которых V(S)=1, называются выигрывающими, а коалиции S, для которых V(S) = 0, - проигрывающими.^[2]

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

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

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

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

Основной принцип кооперативной игры без побочных платежей для двух игроков известен как решение Нэша.

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

Например, в некооперативной игре точкой угрозы могли бы быть максиминные платежи.

Нэш указал ряд допущений, при которых решение игры с торгом яв­ляется единственным.

Первое допущение - симметрия; предполагается, что решение не за­висит от того, какие номера присвоены игрокам.

Второе допущение - инвариантность относительно линейных преоб­разований; решение не зависит от монотонных линейных преобразований платежей.

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

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

При выполнении этих условий, единственным решением является пара платежей (Х1, Х2), которые максимизируют произведение превышений этих платежей над платежами при угрозе (Y1, Y2)

Задачи дележа прибыли в кооперативе

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

Очевидно, что даже в том случае, когда игра является существенной, нельзя сделать вывод, что игроки захотят объединяться, т.к. они не знают правил распределения дополнительного выигрыша, возникающего в результате объединения их в коалицию. Если в результате распределения выигрыш некоторого члена коалиции окажется меньше того выигрыша, который он получил бы, действуя самостоятельно, то он не захочет входить в данное объединение. Если вектор X = (x1, x2, ..., xn), удовлетворяет условиям:^[3]

то он называется дележом. В данном случае xi определяет выигрыш i-го игрока (i = 1,2,.,n), который он получит при распределении общего выиг­рыша между всеми членами коалиции.

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

Условие (5) называется условием коллективной рациональности. Оно означает, что игроки должны делить между собой реально возможный выигрыш.

Таким образом, вектор X = (xb x2, xn), удовлетворяющий услови­ям индивидуальной и коллективной рациональности, называется дележом в условиях характеристической функции V.

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

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

Теорема 2. Для того, чтобы вектор X = (xb x2, xn) был дележом в классической кооперативной игре (N,V) необходимо и достаточно выполнение условия:

Доказательство. Достаточность устанавливается проверкой условий индивидуальной и коллективной рациональности вектора X.

Необходимость. Положим

Из условия индивидуальной рациональности (4) следует, что ai > 0. Суммируя последовательно все равенства (7) и учитывая условия коллек­тивной рациональности (5) получим (6).

Теорема 3. В несущественной игре имеется только один дележ:

Во всякой существенной игре с более чем одним игроком множество де­лежей бесконечно.

Доказательство. В соответствии с теоремой (2) представим дележ X в виде:

В случае несущественной игры выполняется равенство (2), так что для дележа X остается единственная возможность: ai = 0 (i e N), и мы получаем дележ (8).

Если же игра существенна, то

и эта положительная разность может быть представлена бесконечным мно­жеством способов.

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

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

Дележ Х доминирует дележ Y по коалиции S (X > Y), если выполня­ются следующие соотношения:

Условие 1) означает, что дележ Х лучше дележа Y для всех членов коалиции S, т.е. отражает необходимость «единогласия» в предпочтении со стороны коалиции, а условие 2) означает реальную возможность коалиции S предложить каждому игроку, вошедшему в ее состав, величину выигрыша xi.

Доминирование возможно не по всякой коалиции. В частности до­минирование невозможно по коалиции, состоящей из одного игрока, а также по множеству всех игроков N.

Действительно, из следовало бы yi<xi<V(i), а это противоречит индивидуальной рациональности дележа Y.^[4]

что противоречит условию коллективной рациональности дележа Х.

Кооперативная игра (N, V) называется эквивалентной игре (N, V') {(N,V) ~ (N, V') или V ~ V}, если существует положительное число k и ве­щественные числа ci (i = 1,2, ...,n), такие, что для любой коалиции  выполняется равенство:

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

1.     рефлексивности: V ~ V;

2.     симметрии отношений: если V ~ V', то V' ~ V;

3.     транзитивности: если V ~ V' и V' ~ V'', то V ~ V''.

Доказательство. Положим:

Заключение

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

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

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

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

Доминирование возможно не по всякой коалиции. В частности до-минирование невозможно по коалиции, состоящей из одного игрока, а также по множеству всех игроков N.

Список литературы

1.     Веберова И.И. Методические указания по преддипломной практике и дипломированию для студентов специальности 230102 «Автоматизированные системы обработки информации и управления», 2010 г.

2.     Влацкая И.В., Нестеренко М.Ю., Полежаев П.Н. Модели поддержки принятия решений в условиях неопределенности, сводящиеся к кооперативным играм // Вестник ОГУ №9 (145)/сентябрь, 2012. С. 143-149

3.     Нестеренко М.Ю., Кириллов А.С. Разработка и анализ  высокопроизводительных параллельных алгоритмов решения кооперативных игр // Вестник ЮУрГУ, №17(234), 2011.с. 92-100

4.     Полежаев, П.Н. Экспериментальное исследование алгоритмов планирования задач для вычислительной грид-системы // Системы управления и информационные технологии.  2011.  №3.2 (45).  С. 266–270

5.     Турунтаев Л.П., Салмина Н.Ю. Оптимизация и математические методы принятия решения:  — Томск: Факультет дистанционного обучения, ТУСУР, 2010, 198 с.