10.10. классические кооперативные игры

10.10. классические кооперативные игры

Пусть К — некоторое конечное множество. Элементы множества К будем называть игроками.

Функция v, определенная на множестве всех подмножеств множества К, называется характеристической функцией множества К, если v (0)=О (0 — пустое множество).

Если v — характеристическая функция множества игроков К, то каждому подмножеству Q множества К поставлено в соответствие число v (Q), равное выигрышу, который могут получить игроки множества Q, действуя совместно.

Характеристическая функция v множества К называется супераддитивной, если для любых непересекающихся подмножеств Р и Q множества К

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

Свойство супераддитивности характеристической функции означает, что суммарный выигрыш непересекающихся коалиций Р и Q не превосходит выигрыша, который могли бы получить игроки, объединившись в коалицию Р [J Q.

Если имеется супераддитивная характеристическая функция v некоторого конечного множества К, то говорят, что задана классическая кооперативная игра Г = {К, v}.

О Пример 1. Пусть К— конечное множество, a b — некоторое число.

Чтобы задать характеристическую функцию v множества К, достаточно для любого подмножества Q множества К положить

v(Q) = Q,

где |б1 — число элементов множества Q. Характеристическая функция v супераддитивна, так как для любых двух непересекающихся подмножеств Р и Q множества К имеет место равенство

V

(PjQ)=v(P) + v(Q). •

О Пример 2. Имеется множество А = {а,, а,, .... а,) продавцов некоторого товара и множество B={b , bjt bm) покупателей этого товара.

Продавец о, 0 = 1, 2, /) может продать xt единиц товара, а покупатель bj (j=l, 2, т) собирается приобрести у} единиц

этого товара.

Супераддитивную характеристику функции множества К= A J В можно задать, если для каждого подмножества Q множества К положить

Г = {5„ ...,Sk,

: Sn я, is), Hk is), H, is)}.

Можно считать, что К={1, к, .... г) — множество игроков в игре Г. Если Q — некоторое подмножество множества игроков К, то любую ситуацию

г

s = (s„ sk, .... sr)e П Sk

кможно представить в виде

где se П Sk, se Y[ SkkeQ keKQ

Если положить

v(Q)= max ( min £ Hk(s,f)l

U П Sk JE П Sk k*Q J

то тем самым будет определена супераддитивная функция множества игроков К. Щ

Если дана некоторая кооперативная игра Г={К, v}, то коалиция К, объединяющая всех игроков, может обеспечить себе выигрыш, равный v (К).

Основная задача в классической теории кооперативных игр — найти распределение выигрыша v (К) между игроками, которое устраивало бы всех игроков.

Если все игроки кооперативной игры Г = {К, v) пронумерованы, то можно считать, что К={1, 2,г}. В этом случае выигрыш коалиции, состоящей из одного Jk-ro игрока, будет равен v (к) (к =1,2, г). Тогда

v ... + v (к)+ ... + v (r)^v (К).

Кооперативная игра Г = {К, v) называется существенной, если v(l) + ... + v(k)+...+v(r)<v(K), и несущественной, если

v (1) + ... + * (*) + ... + » (г) = 11 (К).