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

↑

▷ Содержание

⇐ ПредыдущаяСтр 2 из 4Следующая ⇒

Опред. Кооперат. игра с характеристической функцией u имеет (0,1)-редуцированную форму, если выполняются соотнош.: u(i) = 0 (i Î N), u(N) = 1. Теорема. Каждая существенная кооперат. игра стратег. эквивалентна одной и только одной игре в (0,1)-редуцированной форме. Сформулированная теорема показывает, что мы можем выбрать игру в (0,1)-редуцированной форме для представления любого класса эквивалентности игр. Удобство этого выбора состоит в том, что в такой форме значение u(K) непосредственно демонстрирует нам силу коалиции S (т.е. ту дополнительную прибыль, которую получают члены коалиции, образовав еѐ, а все дележи являются вероятностными векторами. В игре в (0,1)-редуцированной форме дележѐм является любой вектор x = (x1,..., xn), для которого xi ³ 0 (i Î N) xi iÎN å = 1.

Свойства характеристической функции в 0,1-редуцированной коалиционной игре:

1. Всякая характеристическая функция является неотрицательной и неубывающей функцией.

2. Если K L, то v(K) + v(L/K) v(L)

3. Всякая характеристическая функция в игре из n игроков, I={1,2,…,n}, описывается 2n-1 числом параметров, а при приведении игры в 0,1-редуцированную форму накладывается n+1 дополнительных связей, и, следовательно, получается (2n - n - 2) свободных параметров.

16. Определение кооперативной игры (в форме характеристической функции). Основные свойства характеристической функции (супераддитивность, выпуклость). Игры существенные и несущественные.

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

Предположим, что имеется множество игроков K – Некоторое подмножество , состоящее из игроков.

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

Определение 1. Функция V, ставящая в соответствии каждой коалиции K наибольший выигрыш, называется характеристической функцией игры.

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

Определение 3. Если характеристическая функция V простая, то коалиции K, для которых V(K) = 1 называются выигрывающими, а для которых V(K) = 0 – проигрывающими.

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

1) персональность (коалиция, не содержащая ни одного игрока, ничего не выигрывает).

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

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

Обозначим через Xi выигрыш i-го игрока. И рассмотрим следующие два условия:

индивидуальная рациональность

коллективная рациональность

Определение 4. Вектор выигрышей X = (X1, ¼, Xn), удовлетворяющий условиям 1 и 2, называется дележом в условиях характеристической функции V.

Определение 5. Множество {N, V}, удовлетворяющее условиям 1 и 2, называется классической кооперативной игрой.

Теорема 1. Для того чтобы X = (X1, ¼, Xn) был дележом в классической кооперативной игре, необходимо и достаточно, чтобы

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

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

Рассмотрим следующие свойства:

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

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

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

17. Определение и основные свойства дележа в кооперативной игре. Понятие доминирования дележей. Вектор называется дележом в игре <N,v>, если выполняются условия

(коллективная рациональность);

xi≥v(i) для всех iÎN (индивидуальная рациональность).

В дальнейшем для краткости будем использовать следующее обозначение. Если x – дележ, а K – коалиция, то . В частности, x({i})=xi, x(N)=v(N).

Лемма. Множество дележей не пусто.

Доказательство. Определим вектор условиями x1=v(1),…,xn–1= v(n–1), . В силу свойства супераддитивности выполняется неравенство xn≥v(n), значит, этот вектор является дележом.

Лемма. В несущественной игре дележ единственный.

Доказательство. Если – дележ, то для всех iÎN выполняются неравенства xi≥v(i). Суммируя их, получим

(последнее равенство выполняется в силу несущественности игры). Значит, на самом деле все сложенные неравенства на самом деле являются равенствами, то есть единственный дележ – вектор (v(1),…,v(n)).

Дележ x доминирует дележ y по коалиции K, если выполняются условия

x(K)£v(K);

xi>yi для всех iÎN.

Если x доминирует дележ y по коалиции K, то будем писать .Лемма. Отношение доминирования по коалиции K обладает свойствами строгого порядкаДля любого дележа x не верно, что x y (антисимметричность);

Для любых дележей x,y,z из условий x y и y z следует отношение x z (транзитивность).

Доказательство. Лемма немедленно следует из того, что указанными свойствами обладает отношение «больше».

Лемма. Отношение x y не выполняется ни для каких дележей x и y.

Доказательство. Если x y, то xi>yi для любого iÎN. Суммируя эти равенства, получим (равенства выполняются в силу определения дележа). Получено противоречие.

Лемма. Отношение x y не выполняется ни для какого игрока i и ни для каких дележей x и y.

Доказательство. Если x y, то v(i)≥xi>yi≥v(i) (первые два неравенства выполняются в силу определения доминирования, а последнее – так как y – дележ). Получено противоречие.

Лемма. Если x y, то x lx+(1–l)y для любого lÎ[0,1].

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

Если дележ x доминирует дележ y, то будем писать x y.

Лемма. Если в некоторой игре найдутся дележи x и y такие, что x y и y x, то число игроков в этой игре не меньше пяти.

Доказательство. Если и , то коалиции K и L не пересекаются, так как если , то xi>yi>xi, что не возможно. В силу доказанного выше, каждая из этих двух коалиций содержит не менее двух игроков. Не ограничивая общности, можно считать, что K={1,2}, L={3,4}. Так как , то x1+x2£v({1,2}). Так как , то x3+x4<y3+y4£v({3,4}). Отсюда x1+x2 x3+x4<v({1,2})+v({3,4})£v(N). Если игроков кроме 1,2,3 и 4 нет, это противоречит определению дележа.

Познавательные статьи:



Техника прыжка в длину с разбега

Организация работы процедурного кабинета

Области применения синхронных машин

Оптимизация по Винеру и Калману