25. Определение характеристической функции. Её свойства.

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

Опр. Характерная функция является удовлетворенным неравенством:

Если неравенство Аи В не пересекаются, (А В ) V(A B) V(A)+V(B) (1) Неравенство (1) означает, что в результате образование новой коалиции, выигрыш может только увеличиваться. Требование (1)является логичным, так как создание коалиций было бы бессмысленным, если бы величина выигрыша уменьшается с увеличением числа игр коалиций.

Характеристика функций называется просто если она принимает 2 значения (0 и 1). При этом если V(S)=1, то коалиция S называется выигрыш. Если же V(S)=0, то коалиция S проигрыши.

При создании теории ввели ряд допущений:

1)симметрия

2)режим не зависит от много точных линейных преобразований.

3) режим не должен изменится, если исключить возможные выборы, которые не используют.

Теорема:

Характеристическая функция является аддитивной когда и только тогда, когда выполняется равенство.

(3), где

V(i)- выигрыш игрока с номером i

V(N)-выигрыш коалиции, соответствующей из все N игроков.

Доказательство: чтобы получить формулу (3)нужно показ умножить на имеющей на пересечение и принять формулу (2).

Возьмем две не переменные множители

S и L не пересекаются

S L= , тогда

V (S)+V(L) V(S L)

V(S) (1`)

V(L)(2`)

(3`)

Отсутствие А \В – разность 2 множителей, которые состоят их элементов принадлежит множеству А и не принадлежит множителю В.

V(S L)+V (N \S L) V(N)

V(N)=

Если сложить неравенство (1`)+(2`)+(3`), то в левой части получится

V(N )= ) V(S)+ V(L)+V(N\S L) V(N) (4`)

Все неравенства должны быть равенствами.

Теорема доказана.

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

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

Дележом называется вектор, который состоит из n- компонентов. X=(x1,х2…х_n), вектор которой удовлетворяет условия:

- (1*)

- (2*)

(1*)условие индивидуальной рациональности

(2*) условие коллективной рациональности

Объединяться выгодно только в том случае, если каждый игрок, входящий в коалицию получит не меньший выигрыш (1*)

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

Система, состоящая из множества игроков N, ХФ≠V и множества дележей, удовлетворяющих коллективно-рациональностный, называется классической кооперативной игрой.

Вектор X=(x1,х2…х_n) является дележом в кооперативной игре тогда и только тогда, когда выполняются условия:

(1)

(2)

(3)

Доказательство: Если выполняются условия 1-3, то легко проверяется 2 условие из определения дележа. Обратно, если вектор Х является дележом, то достаточно положить , тогда условия 1 и 3 будут выполнены.

Формула характеристической функции:

V(S)- старая, заданная характеристическая функция

V’(S)- новая, которую требуется построить характеристическая функция

S- коалиция

27. 0-1 редуцированная форма кооперативной игры.

Кооперативная игра (IV,V) игра если в0-1, редуцированной форме, если V(i)=0 ; i=1,2,…,n; V(N)=1

Выигрыш отдельного игрока, если он играет один -0, а если коалицией то 1.

Теорема.

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

Доказательство.

Дана игра (IV,V) будем искать игру эквивалентную данной (IV/V^”) ~(IV,V), которая к тому же является в игре 0-1 редуцированной форме. Составим уравнение:

V´(i)= KV(i) + C_i=0 i=1,2,…,n условие эквивалентности

V´(N)=KV(N)+ =1 (n+1)

Всего записано n+1 уравнение

Сложим первые n уравнения

Полученное равенство вычтем из уравнения n+1. Получим :

Кооперативная игра существенная, то []>0 (непонятное слово) обе части можно поделить на эту скобку

Зная K найдем неизвестные C_i= - KV(i)=>

Найдем характеристическую функцию

Для следующей игры найти эквивалентную, которая представлена в 0-1 редуцированной форме. Найти: V’ V(S)-стадия задания характеристическая форма V’(S)- новая, требуется построить S-коалиция

Исходные данные:

V(1)=100 V(1,2)=300 V(1,2,3)= 550

V(2)=150 V(1,3)=350

V(3)=300 V(2,3)=420

V’ (1) = V’ (2) = V’ (3) =0 V’(1,2,3)=1

28. Доминирование дележей.

29. С-ядро кооперативной игры.

Естественно положить в основу анализа кооперативной игры принцип оптимального распределения максимального выигрыша u(S) между сторонами  .

Реализация этого принципа приводит к рассмотрению С-ядра − множество недоминируемых «вполне устойчивых» дележей кооперативной игры.

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

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

xi ³ u(i), для i ÎN (1)

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

= u(N) (2)

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

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

Делёж x доминирует y, если существует такая коалиция S, для которой делёж x доминирует y. Это доминирование обозначается так: x > y.

Наличие доминирования x > y означает, что в множестве игроков N найдётся коалиция, для которой x предпочтительнее y. Соотношение доминирования возможно не для всякой коалиции. Так невозможно доминирование по коалиции, состоящей из одного игрока или из всех игроков.

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

Для того чтобы делёж x принадлежал с-ядру кооперативной игры с характеристической функцией u, необходимо и достаточно, чтобы для любой коалиции S выполнялось неравенство  .

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