Основные понятия и определения

1. Основные понятия и определения.

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

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

Коалицией в кооперативное игре называется всякое (любое) подмножество множества игроков.

Пример. Пусть I = {1,2,...i...n} - некоторое множество игроков. Коалициями будут: k₁ = {1,2,5,i};

k₂ = {i} = i;

k₃ = { } = Æ ;

k₄ = { 1,2,...n} = I.

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

Характеристической функцией v(k) называется наибольший выигрыш, уверенно получаемый коалицией k.

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

Задать характеристическую функцию этой игры.

I = { M, p₁, p₂ } - множество игроков игры. Тогда

v(Æ) = v(p₁, p₂) = v (p₁) = v (p₂)= v (M) = 0,

v (M, p₁, p₂) = v( M,p₁) = v( M, p₂) = C.

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

Свойства характеристической функции:

1. Персональность v_Г (Æ) = 0;

2. Супераддитивность v_Г (КÈL) ³ v_Г (К) + v_Г (L), где K,LÎI, KÇL = Æ;

3. Дополнительность v_Г (К) + v_Г (I\K) = v_Г (I) = C,

 где С - постоянная сумма выигрыша.

2. Дележи в кооперативных играх.

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

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

Пусть задана характеристическая функция v над множеством игроков I. Какие векторы дележей в этом случае допустимы?

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

x_i ³ v(i) Эгалитарный подход

 å x_i = v (I)  Утилитарный подход

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

Дележом в условиях характеристической функции v называется вектор х = ( х₁, х₂, ... х_n), удовлетворяющий условиям индивидуальной и коллективной рациональности.

Классической кооперативной игрой называется система < I, v >, включающая множество игроков I и характеристическую функцию v над этим множеством, а так же множество Х дележей в условиях этой характеристической функции.

Теорема. Для того, чтобы вектор х = ( х₁, х₂, ... х_n) был дележом в кооперативной игре < I, v >, необходимо и достаточно, чтобы

х_i = v (i) + a_i, a_i ³ 0, i Î I;

å a_i = v(I) - å v(i)

Нетрудно видеть, что компоненты вектора х удовлетворяют условию индивидуальной рациональности. Условие кооперативной рациональности

åx_i = å v (i) + v(I) - å v(i) = v(I) также выполняется.

a_i - это добавочный выигрыш игрока, получаемый за счет кооперации с другими участниками.

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

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

Существующая классификация делит все кооперативные игры, прежде всего, на существенные и несущественные.

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

v (КÈL) = v(К) + v(L), где K,LÎI, KÇL = Æ;

Существенными называются остальные игры.

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

Признак аддитивности характеристической функции задается теоремой:

Теорема. Для того, чтобы характеристическая функция была аддитивной, необходимо и достаточно, чтобы выполнялось равенство å v(i) = v(I).

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

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

( v(1), v(2),... v(n) ).

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

Это обьясняется тем, что в существенной игре обязательно существует

D = v(I) - å v(i) > 0,

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

Игроки так же делятся на существенных и несущественных (болванов), а множества игроков - на носителей игры и множества болванов.

Существенным называется игрок i, если существует такая коалиция К, что

v(K) + v(i) < v(KÈi).

Болваном называется игрок i, если для любой коалиции KÌI cправедливо

v(K) + v(i) = v( KÈi).

Допустим, L - множество болванов (несущественных игроков) и LÌK, тогда

v(K) = v(K\ L) + å v(i), а если K = L, то v(K) = å v(i).

Существенные игроки образуют множество носителей игры, NÌI. Признаком этого для коалиции К является:

v(K) = v(KÇN) + å v(i) _i Î_K\N.

Похожие работы

Теория принятия решений: математические методы для выбора специалиста на должность администратора сети

Скачать

16587

14

0

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

Математические методы в теории принятия решений

Скачать

22330

8

1

... максимизирующий выделенный критерий на множестве исходов, оценки которых по остальным критериям не ниже назначенных. Всякие задачи принятия решения является: Альтернативы (варианты, планы, допустимые альтернативы) Исходы (Результаты) Оптимальные решения (Наилучшие решения) Математическая модель ЗПР включает в себя формальное описание этих компонентов. X - множество допустимых альтернатив A ...

Теория принятия решений

Скачать

83422

1

0

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

Измерительные шкалы в математическом моделировании. Теория принятия решений

Скачать

13429

2

0

... , среднее распределение процентных отношений, дисперсия, стандартные отклонения, коэффициенты вариации Коэффициенты – j, c2, Чупрова, Спирмена, коэффициент корреляции Пирсона 2. Теория принятия решений Выбор любого управленческого решения всегда ограничен. Это объясняется необходимостью следовать определённым нормам поведения, которые и ориентируют руководителя. В зависимости от ...