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

S₉ – число стратегий игрока, делающего первый ход.

= 9 ветвей, их нужно суммировать. Затем ходит соперник Þ умножаем.

                    S₉=9*S₇⁸,        S₇=7* S₅⁶,        S₅=5*S₃⁴,        S₃=3*S₁²,        S₁=1

S₉=9*(7*S₅⁶)⁸=9*7⁸*S₅^6*8=9*7⁸*5^6*8*S₃^4*6*8=9*7⁸*5^6*8*3^4*6*8*1^2*4*6*8

Теорема: Любая позиционная игра с полной информацией при сведении ее к матричной игре имеет седловую точку (т.е. решение в чистых стратегиях).

Практически это никогда не делается, т.к. число стратегий очень большое.

№16. Коалиционные игры.

При числе игроков больше двух задаются функции выигрыша всех игроков. Для игры трех лиц будем использовать обозначения без индексов: xÎX, yÎY, zÎZf_x(x,y,z), f_y(x,y,z), f_z(x,y,z). Максиминные стратегии игроков таковы: . При этом каждый игрок считает, что он один играет против всех остальных. Если игроки Y и X образуют коалицию и согласовывают все свои действия, их рассматривают как одного игрока со стратегиями w=(x,y)ÎW=XYи функцией выигрыша f_w(x,w) = f_y(x,y,z) + f_z(x,y,z). Максимальные выигрыши, на которые могут рассчитывать игроки y и z, играя в одиночку, и их коалиция, таковы: , ,

Лемма 1.  а) ,  б) .

Пусть . Для max.

Лемма 2. а) ,  б) .

Сложив два очевидных неравенства  и , получим . Теперь применим лемму 1а. Для max аналогично.

Лемма 3. ,  .

Лемма 4. .

Сложив два неравенства  и , получим . Лемма 2б здесь неприменима, т.к. в ней стоит знак «меньше». Однако первое слагаемое справа не зависит от z, а второе от  y. Дважды применив леммы 1б и 3, получим утверждение леммы 4.

Теорема. В коалицию вступать выгоднее, чем играть против всех:  υ_w ≥ υ_y + υ_z.

Имеем f_w(x,w) = f_y(x,y,z) + f_z(x,y,z). Взяв от суммы сначала minпо x (лемма 2а), а затем max по y, z (леммы 1б и 4), получим утверждение теоремы.

Всего в игре n лиц существует 2ⁿ коалиций. Пусть SÌN={1, 2,…, n}. Рассмотрим игру двух коалиций S и N\S. Выигрыш коалиции S определим так: . Легко показать, что .

Def:  Говорят, что коалиционная игра задана в редуцированной форме, если задана произвольная функция u: 2^N®Â, обладающая свойствами:

1) u(Æ)=0;      2) если S₁ÇS₂=Æ, то u(S₁+S₂)³u(S₁)+u(S₂).

Def:  Коалиционная игра существенна, если u(N)>åu({i}).

Если игра несущественна, то создавать коалиции не имеет смысла.

Def. Игра называется простой, если выигрыш любой коалиции равен 0 или 1.

Игрок i называется болваном, если, присоединяясь к любой коалиции S, он ничего ей не приносит (т.е. v(S) = v(S \ {i})). Очевидно, что его вес j_i(u)=0.

Def:  Коалиционная игра имеет постоянную сумму, если u(S)+ u(N\S)=C   "SÌN.

Пример К1. Есть 3 игрока,  u({i})=-2 "i,  u({1,2})=u({1,3})=u({2,3})=2, u({1,2,3})=u(0)=0.   Это игрa с нулевой суммой.

Дележи.

Def. Дележом называется вектор t=(t₁,…,t_n):   1) t_i³u({i})  "i,    2) åt_i=u(N).

Дележ t доминирует дележ t  по коалиции S (пишем t≻_st ), если:

1) t_i>t_i  "iÎS;             2) å t_i£u(S).

Пусть E(u)-множество всех дележей, а R(u)-ядро игры, т.е. множество дележей, не доминируемых никакими дележами ни по какой коалиции.

Теорема: Если игра - существенная с постоянной суммой, то R(u)=Æ.

Def. Множество дележей VÌ E(u) назовем НМ-решением игры, если оно:

1)  внутренне устойчиво, т.е. никакие два дележа из V не доминируют друг друга ни по какой коалиции;

2)  внешне устойчиво, т.е. для "tÏV    $tÎV и коалиция SÌN: t≻_st.

НМ-решение может быть не единственным или пустым при пустом ядре.

Пример К1: (продолжение) V={(1,1,2), (1,-2,1), (-2,1,1)};

Другое НМ-решение: V={(x₁,-x₁-a,a)}, x₁Î[-2,a], для  "aÎ[-2,-1].

Вектор Шепли.

Пусть игра задана в характеристической форме (задана функция u). Относительную силу игроков характеризует вектор Шепли j(u)=(j₁(u),…,j_n(u)):

1)  j(u) ÎE(u), т.е. является дележом;

2)  сила каждого игрока не зависит от нумерации, т.е. если в игре u номер игрока= i, в игре u' его номер=k_i, то j_ki(u')=j_i(u);