logo search
Теория игр

Стратегическая эквивалентность кооперативных игр

Игра I, V стратегически эквивалентна игре I, V’ , (V~V’), если k>0, c , i I: V’(K) = kV(K) + , k I.

Стратегическая эквивалентность обладает следующими свойствами:

Т. о. стратегическая эквивалентность является отношением, которое разбивает множество кооперативных игр на непересекающиеся классы, т. к. если V~V’, то дележу x = (x , x ,…,x ) соответствует делёж x’ = (x’ , x’ ,…,x’ ), где x’ = kx + c , i = .

Если V(K) = 0, k I, то игра I, V называется нулевой. Любая несущественная коалиционная игра эквивалентна нулевой игре.

В 0,1-редуцированной форме дележом может быть любой вектор x = (x , x ,…,x ), компоненты которого удовлетворяют условиям: а) x 0;

б) = 1.

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

  1. x V(i);

  2. x(I) = V(I);

  3. x 0, = 1.

При решении корпоративной игры необходимо найти единственно справедливый делёж. Для решения используется несколько предположений:

Введём отношение предпочтения дележей x >x (при коалиции k)

x x , i I x (I) = V(I)

Если для коалиции, то x (k) V(k), k I. Это условие практической реализуемости дележа.

Отношение дележей возможно не по всем коалициям.

  1. k = 1 — коалиция из одного игрока

x y , x V(i) — это условие противоречит условию индивидуальной рациональности.

  1. k = I — коалиция из всех игроков

x(I) > y(I) = V(I)

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

Доминирование дележей невозможно по следующим коалициям:

Пусть есть две стратегически эквивалентных игры V~V’ и некоторые два дележа и , которые будут доминировать, соответственно, дележам: > , >

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

Для несущественных игр отношение доминирования можно рассматривать на примере нулевой игры, а для существенных на примере 0,1-редуцированной игры.

Рассмотрим доминирование дележей существенной игры трёх лиц:

x = (x , x , x ) – вектор дележей, x V(i), x + x + x = 1

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

Например, в симплексе зафиксировано x = x (прямая, параллельная АВ, будет иметь положение в зависимости от V ).

Подмножество С множества допустимых значений, где выполняются условия:

  1. нет доминируемых дележей по любой коалиции из I;

  2. для любой коалиции k I выполняются условие x(k) V(k), k I, называют С-ядром кооперативной игры с характеристической функцией V(k).

Компоненты С-ядра должны удовлетворять некоторой конечной системе линейных неравенств.

Рассмотрим методику составления неравенств на примере игры трёх лиц.

Эти неравенства: V(1,2) x +x

V(1,3) x +x

V(2,3) x +x

К этим неравенствам добавляются ещё два неравенства индивидуальной групповой рациональности x V(1), x V(2), x V(3), x + x + x = 1

При приведении этой игры к 0,1-редуцированной форме, получаем:

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

x 0, I = 1,2,3

x + x c

x + x c

x + x c , c 0

Условие нахождения С-ядра рассмотрим на следующем примере:

Пусть есть три предприятия П , П , П .

П – Д , Д по 900 шт.

П – Д , Д по 700 шт.

П – М , М по 1000 шт.

Поступил заказ поставить комплект товаров (Д , М ) по 1000 шт. Каким образом скомплектовать этот заказ?

Другими словами, как распределить величину Д относительно П и П ?

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

Будем считать характеристическую функцию в единицах товаров.

V(П ) = V(П ) = V(П ) = V(П , П )

V(П , П ) = 1800

V(П , П ) = 1400

V(П , П , П ) = 2000

Перейдём к 0,1-редуцированной форме, тогда V(П ) = V(П ) = V(П )=0 V(П , П ) = 0

V(П , П ) = 0,9

V(П , П ) = 0,7

V(П , П , П ) = 1

Для дележей получим следующие неравенства:

. Это условие определяет С-ядро этой игры.

П оследнее неравенство определяет двумерный симплекс. Рассмотрим прямую x + x = 0,9. Это эквивалентно множеству точек, когда x = 0,1; x + x = 0,7; x = 0,3

— множество дележей, образует С-ядро этой игры. Любой делёж из этого ядра является наилучшим.

Например, x = 600 ед.

x = 200 ед.

x = 1200 ед.

Превышение x над x и x за счёт монополии; П и П придется доплачивать П , т. к. они не могут самостоятельно выполнить заказ.

Д = ,

М = 1000 ед.

П доплатит 150 ед., а П – 50 ед.

Более общим подходом к решению кооперативных игр является решение по Нейману-Моргенштерну. Н-М решения, как и с-ядро, определяют множество эквивалентных между собой решений.

Кроме С-ядра и Н-М решения для определения предпочтительного дележа используют вектор Шепли.