Элементы теории игр Определения

Как должны организовать свой досуг супруги, чтобы получить максимальное удовольствие?



Рис. 2. Решение игры «Семейный спор»

На рис. 2: точка угрозы  точка  T (2, 2), отрезок AB  Парето-оптимальные решения, отрезок CD  переговорное множество. Единственная точка равновесия по Нэшу - точка T. Точки переговорного множества принадлежат прямой ₂ = 5 – ₁. Поэтому решение Нэша можно найти, исследовав на максимум функцию

H(₁) = (₁ – 2)( ₂ – 2) = (₁ – 2)( 3 – ₁).

Максимум этой функции достигается при ₁ = 2,5, следовательно, ₂ = 2,5. Соответствующая точка является серединой отрезка между точками A и B. Это означает, что в чистых стратегиях решения не существует. Заметим, что точка A соответствует ситуации, когда оба супруга идут на футбол, а точка B оба идут в театр. Можно доказать, что при многократном повторении игры оптимальным будет выбор каждой из этих двух ситуаций с вероятностью 0,5.

Упражнение 2 – игра «Зачёт»

У студента есть две стратегии подготовки к зачету: учить или не учить. У преподавателя есть две стратегии – поставить зачет или не зачет. При этом выигрыши игроков описываются матрицами:

Какие стратегии должны выбрать студент и преподаватель?

Антагонистические игры

Пусть интересы игроков диаметрально противоположны, то есть выигрыш первого игрока равен проигрышу второго, тогда если (s,t)  функция выигрышей игрока I, то выигрыш игрока II равен –(s,t). В этом случае игра называется антагонистической. Мы будем рассматривать антагонистические игры, в которых множества стратегий S и T конечны. В таких играх платежная функция представляет собой матрицу, а саму игру называют матричной. В матричной игре S = (s₁, s₂, …, s_m), T = (t₁, t₂, …, t_n), a_ij = (s_i, t_j), , . То есть матричная игра полностью описывается матрицей , которая называется платежной матрицей игры.

Примеры

1. Игра «Чёт-нечет»
   

Два игрока выбрасывают 1 или 2 пальца. Если сумма пальцев четная, то выигрывает первый, если сумма нечетна, то выигрывает второй (то есть выигрыш первого равен –1).

s_i = t_i = {выброшено i пальцев}, i = 1, 2;

2. Игра «Сравнение монет»
   

Два игрока выбрасывают по монетке. Если монетки выпадают обе вверх гербом или обе вверх решкой, то обе монетки забирает первый игрок (то есть выигрыш первого равен 1), в противном случае обе монетки забирает второй (то есть выигрыш первого равен –1).

Матрица этой игры совпадает с матрицей из первого примера.

3. Игра «Камень, ножницы, бумага»
   

Два игрока выбрасывают кулак («камень»), два пальца («ножницы») или ладонь («бумага»). Камень побеждает ножницы, ножницы побеждают бумагу, бумага побеждает камень. Побеждающий получает с другого монетку.

Пусть s₁ = t₁ = {«камень»}, s₂ = t₂ = {«ножницы»}, s₃ = t₃ = {«бумага»}.

4. Игра "Морра"
   

Два игрока показывают какое-либо количество пальцев и называют число (не обязательно равное количеству показанных пальцев). Если кто-то из игроков угадает сумму пальцев (назовет число, равное сумме), то этот игрок получает с другого выигрыш равный названному числу.

Построим матрицу игры для случая, когда можно показать один или два пальца.

s_ij = t_ij = {показано i пальцев, названо число j},

если i = 1, то j = 2, 3; если i = 2, то j = 3, 4;

5. Игра "Война"
   

Имеется две стороны – обороняющаяся (I) и нападающая (II). I выбирает вид оружия, II – вид самолета, который должен прорвать оборону противника. Вероятность поражения самолета задана таблицей (платежная матрица игры):

Нижнее и верхнее значение игры

Пусть A – платежная матрица игры. Пусть игрок I выбрал стратегию s_iS. Его выигрыш зависит от стратегии, выбранной игроком II. Худший вариант для игрока I заключается в том, что игрок II выберет ту стратегию, при которой выигрыш игрока I минимален. В этом случае игрок I получит – это минимальный гарантированный выигрыш игрока I в случае выбора стратегии s_i. Естественно, при выборе i игрок I хочет получить как можно больший выигрыш:

.

Это число  называется нижним значением игры (или максимином). Смысл этого числа – минимальный гарантированный выигрыш игрока I.

Пусть игрок II выбрал стратегию t_jT. Его проигрыш зависит от стратегии, выбранной игроком I. Худший вариант для игрока II заключается в том, что игрок I выберет ту стратегию, при которой проигрыш игрока II максимален. В этом случае игрок II проиграет . Естественно, при выборе j игрок II хочет проиграть как можно меньше:

.

Это число  называется верхним значением игры (или минимаксом). Смысл этого числа –максимальный возможный проигрыш игрока II.

Стратегии s_i (t_j), для которых достигается  (соответственно ), называются максиминной (минимаксной) стратегиями.

В расмотренных выше примерах:

• Игра «Морра»:  = –2 <  = 2. Соответствующие стратегии s₂, t₂.
  
• Игра «Война»:  = 0,7 =  = 0,7. Соответствующие стратегии s₂, t₁.
  

Теорема 1 (о минимаксе и максимине).

Для любой матрицы A имеет место неравенство   .

Доказательство.

 i, j:

(1)

Рассмотрим максимум по i от (1). Поскольку правая часть от i не зависит, то получим

(2)

Рассмотрим минимум по j от (2). Поскольку левая часть от j не зависит (это уже число), то получим , что и требовалось доказать.

Седловые точки

Седловым элементом матрицы называется элемент, являющийся минимальным в своей строке и максимальным в своем столбце.

Ситуацию (s*, t*) назовем седловой точкой игры  = <S, T, >, если

 sS  tT ( s, t*)  ( s*, t*)  ( s*, t). (3)

Теорема 2 (критерий существования седловой точки).

Для того, чтобы матричная игра  = <S, T, > имела седловые точки необходимо и достаточно, чтобы были равны величины  и .

Доказательство.

Необходимость.

Пусть (s*, t*) – седловая точка, т. е. выполнено (3).

1. Так как ( s_i, t*)  ( s*, t*), а ( s*, t*) – число, то
   

,

а отсюда следует (берем минимум по j, от которого левая часть не зависит), что

(4)

2. Так как ( s*, t*)  ( s*, t_j), а ( s*, t*) – число, то
   

,

а отсюда следует, что

(5)

3. Объединяя (4) и (5), получаем   ( s*, t*)  .
   

Поскольку по теореме о минимаксе и максимине   , то  = .

Замечание 1.

В равенстве (3) s* и t* максиминная и минимаксная стратегии соответственно.

Достаточность.

Пусть выполнено  = , т. е. .

Обозначим

s*S : ,

t*T : .

Докажем, что (s*, t*) – седловая точка.



(а) (б)

Поскольку  = , то в последней цепочке все неравенства выполняются в виде равенств. Следовательно, получаем:

Из (а):  j

Из (б):  i

Последние два неравенства и дают (3).

Теорема доказана.


Следствие 1.

В качестве компонент седловой точки игры могут быть взяты независимо друг от друга стратегии (любые элементы множеств S и T), на которых достигается равенство  = .

Доказательство – в достаточности.

Стратегию s*S назовем оптимальной стратегией игрока I, если при некотором tT точка (s*, t) является седловой. Оптимальной стратегией игрока II назовем стратегию t*T, если для некоторой sS точка (s, t*) является седловой.

Следствие 2.

Значение платежной функции игры во всех её седловых точках одинаково.

Доказательство – в необходимости.

Это свойство называется равноценностью, а число v = ( s*, t*) называется ценой игры. Смысл цены игры – это минимальный гарантированный выигрыш игрока I и максимальный неизбежный проигрыш игрока II.


Игры с седловой точкой называют вполне определенными. Совокупность оптимальных стратегий называют решением игры.

Решение игры обладает следующим свойством. Если один из игроков придерживается своей оптимальной стратегии, а другой отклоняется от своей оптимальной стратегии, то для игрока, допустившего отклонение, это никогда не может оказаться выгодным: в лучшем случае выигрыш/проигрыш остается неизменным, в худшем – выигрыш уменьшается, проигрыш – увеличивается.

Игра "Война" имеет седловую точку, то есть является вполне определенной. Остальные игры – игры без седловых точек. Решение этих игр существует, но оно указывает не оптимальную стратегию, а вероятности, с которыми следует выбирать ту или иную из возможных стратегий.

Упражнение 3

Платежная матрица игры имеет вид . Найдите верхнее и нижнее значение игры, максиминную и минимаксную стратегии. Является ли эта игра вполне определенной? Если да, то укажите цену игры и оптимальные стратегии игроков.

Решения задач

Упражнение 1

Обозначения ходов игры: . Если после анализа окажется, что ход игроку невыгоден (поскольку следующим ходом выигрывает другой игрок), то будем изображать этот ход пунктирной линией.

1) Если первый игрок утроит какую-нибудь кучку, то выиграет второй:



Поэтому при правильной игре такой ход первый игрок делать не будет.

2) Значит, первым ходом первый игрок добавит два камня в какую-нибудь кучку. Если после этого второй игрок утроит количество камней в какой-нибудь кучке, то первый игрок сможет сделать следующий ход так, чтобы выиграть:



Поэтому при правильной игре такой ход второй игрок делать не будет. Значит, ход второго игрока будет заключаться в добавлении двух камней в какую-нибудь кучку:



3) Дальнейший анализ игры показывает, какие ходы являются невыгодными для второго игрока (поскольку приведут к выигрышу первого игрока).



Заметим, что какой бы ход ни сделал первый игрок, выиграть на третьем ходе он не сможет (при правильной игре второго игрока). А четвертый ход второй игрок всегда может выбрать так, чтобы выиграть, причём утроение камне во второй кучке всегда ведёт к выигрышу.

Таким образом, при правильной игре всегда побеждает второй игрок. Для этого его первый ход должен быть таким:

1. если первый игрок утроил количество камней в какой-нибудь кучке, то второму следует также утроить количество камней в той же кучке;
   
2. если первый игрок добавил два камня в какую-нибудь кучку, то второму следует добавить два камня в другую кучку, а после любого хода первого игрока утроить количество камней во второй кучке;
   

Упражнение 2

Точка угрозы (2, 2) является точкой равновесия по Нэшу. Это единственная точка в переговорном множестве, поэтому она является решением. Оптимальные стратегии игроков: студенту – выучить предмет, а преподавателю – поставить зачет 

Упражнение 3

Матрица имеет седловую точку a₅₃ = 36. Поэтому игра является вполне определенной. Цена игры равна 36 (это же значение является верхней и нижней ценой игры). Оптимальными являются: для первого игрока максиминная стратегия (с номером 5), а для второго  минимаксная (с номером 3).

Литература

1. Вентцель Е. С. Элементы теории игр. – М.: Высш. шк., 1986.
   
2. Замков О. О., Толстопятенко А. В., Черемных Ю. Н. Математиченские методы в экономике: Учебник/ Под общ. ред. д. э. н., проф. А. В. Сидоровича; МГУ им. М. В. Ломоносова. – 4-е изд., стереотип. – М.: Издательство «Дело и Сервис», 2004. – 368 с. – (Учебники МГУ им. М. В. Ломоносова).
   
3. Берж К. Общая теория игр нескольких лиц