Теория игр и исследование операций. Модели, алгоритмы, сложность: Конспект лекций, страница 21

3)  если игрок участвует одновременно в двух играх u и v, то можно считать, что игра одна с характеристической функцией u+v и  j_i(u+v)=j_i(u)+j_i(v).

Аксиомы 1)-3) однозначно определяют вектор Шепли:

Пример К1(прод):   u(0)=0=u({1,2,3}); u({i})=-2; u({1,2})=u({1,3})=u({2,3}) =2.

В сумме для j₁(u) будет 4 слагаемых: коалиции {1},{1,2},{1,3},{1,2,3}.
j₁=(-2-0)/(1*С₃¹)+(-2-(-2))/(2*С₃²)+(2-(-2))/(2*С₃²)+(0-)/(3*С₃³)=0,      j₂=j₃=0.

Недостатки вектора Шепли: а) относительная трудоемкость вычислений;

б) вектор Шепли может не принадлежать ядру, даже если ядро не пусто.

Пример К2: Пусть есть акционерное общество из 4-х акционеров. У них 23, 25, 26 и 26% акций соответственно. Выигрыш коалиции равен 1, если она обладает большинством акций; и 0 в противном случае. Найдем вектор Шепли.

Считаем j₁. Коалиции, где v(s) - v(s\{1})≠0: {1,2,3},{1,2,4},{1,3,4},{1,2,3,4}

j₁(u)=(1-1)/(3*C₄³)+(1-1)/(3*C₄³) +(1-1)/(3*C₄³) +(1-1)/(4*C₄⁴)=0.

Игрок 1 является «болваном». Для остальных игроков j₂=j₃=j₄= ¹/₃.

N-ядро (метод Шмайдлера).

Введем меру близости коалиции S и дележа t: эксцесс . Решая задачу ЛП, найдем дележи . Из них выберем дележи с наименьшим вторым по величине эксцессом и т.д. Решив несколько задач ЛП, получим единственный дележ, называемый N-ядром и обладающий свойствами:

1) если игрок i болван, то t_i=0;      2) если R(u)¹Æ, то N-ядроÎR(u).

Рассмотрим макроигру: два игрока независимо друг от друга выбирают коалицию и дележ, выигрыш = эксцессу. Ищем устойчивое по Нэшу решение: смесь коалиций + N-ядро. Можно решать задачу так: max l(S, t) – верхняя огибающая семейства функций. Исключимt_n и разобьем E(u) в Â^{n -1}  на области, в которых l(S, t) - линейна Þ решаем ЛП. Ее min на границе.

Окончание примера К1: E(u) ={(t₁,t₂,t₃): ∑t_i =0 & t_i³ v({i})=-2} ~  t₁+t₂+t₃=0 & t_i³-2

Считаем эксцессы, исключая t₃ =-t₁-t₂³ -2,

Симметрия по t₁,t₂ !!!

l̃(t)=max{0, |2+t₁|, |2+t₂|, |2-t₁-t₂|}=max{2+t₁, 2+t₂, 2-t₁-t₂},    т.к. t₁,t₂³-2  и  t₁+t₂£ 2.

Имеем   2+t₁³2+t₂ Û t₁³t₂ ,

2+t₁³2-t₁-t₂ Û t₂³-2t₁

 и   2+t₂³2-t₁-t₂  Û t₁³-2t₂.

min l̃(t) = min {2, 2, 2} = 2,

N‑ядро: argmin l̃(t) = (0,0,0).

Пример К3: Одномастка на троих. Позиция {(9,7,1),(8,4,2),(6,5,3)}. Ход 1-го.

E(u) ={(t₁,t₂,t₃) | ∑t_i = v({1,2,3})=3 & t₁³ v({1})=1 & t₂³ v({2})=1 & t₃³ v({3})=0}.

Считаем эксцессы, исключая t₃ =3-t₁-t₂³ 0,   t₁+t₂£3, t₁,t₂³1.

l̃(t)=max{ t₁-1, t₂-1, 3-t₁-t₂}  т.к. t₁,t₂³1 и  t₁+t₂£ 3 (симметрия t₁,t₂).