Редуцированная форма кооперативной игры

Кооперативная игра (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 выполнялось неравенство .

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