Нижняя и верхняя цена игры

Пример 5.

Задана платёжная матрица игры A, необходимо найти решение игры.

A =

В данной игре

V_* = max (min a_ij) = 3a_ij

V^* = min (max a_ij) = 4

Поскольку V_* < V^* - выполняется соотношение строгого неравенства, следовательно, седловая точка в игре отсутствует, ситуации равновесия не существует. Очевидно, что для данной игры рассмотренный выше подход к нахождению оптимального решения неприменим, а максиминная и минимаксная стратегия игроков не являются решением игры.

Приведённые выше примеры иллюстрируют тот факт, что антагонистические игры делятся на два класса:

· вполне определённые игры, т.е. те, в которых существует седловая точка, ситуация равновесия и решение игры в чистых стратегиях;

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

Найдем наилучшую стратегию игрока A, для чего проанализируем последовательно все его стратегии. Выбирая стратегию A_i, мы должны рассчитывать, что игрок B ответит на нее такой стратегией B_j, для которой выигрыш A будет минимальным. Поэтому среди чисел первой строки выбираем минимальное, обозначим его, запишем его в добавочный столбец. Аналогично для каждой стратегии A_i выбираем, т.е. α_i – минимальный выигрыш при применении стратегии A_i.

В примере 1:

α₁ = min {0, –1, –2} = –2;

α ₂ = min {1, 0, –1} = –1;

α ₃ = min {0, –1, –2} = 0.

Эти числа запишем в добавочном столбце. Какую же стратегию должен выбрать игрок A? Конечно же, ту стратегию, для которой α_i максимально. Обозначим. Это гарантированный выигрыш, который может обеспечить себе игрок A, т.е.; этот выигрыш называется нижней ценой игры или максимином. Стратегия A_i, обеспечивающая получение нижней цены игры, называется максиминной (перестраховочной). Если игрок A будет придерживаться этой стратегии, то ему гарантирован выигрыш ≥ α при любом поведении игрока B.

В примере 1. Это означает, что если A будет писать «3», то он хотя бы не проиграет. Игрок B заинтересован уменьшить выигрыш A. Выбирая стратегию B₁, он из соображений осторожности учитывает максимально возможный при этом выигрыш A. Обозначим. Аналогично при выборе стратегии B_j максимально возможный выигрыш A–; запишем эти числа в добавочной строке. Чтобы уменьшить выигрыш A, надо из чисел β _j выбрать наименьшее. Число называется верхней ценой игры или минимаксом. Это гарантированный проигрыш игрока B (т. е. он проиграет не больше, чем β). Стратегия игрока B, обеспечивающая выигрыш ≥ - β, называется его минимаксной стратегией.

	B1	B2	B3
A1		– 1	–2	–2
A2			–1	–1
A3

Принцип, диктующий игрокам выбор наиболее «осторожных» минимаксной и максиминной стратегий, называется принципом минимакса. Этот принцип следует из разумного предположения, что каждый игрок стремится достичь цели, противоположной цели противника.

Если α = β, т.е. минимакс совпадает с максимином, то такая игра называется игрой с седловой точкой. Седловая точка – это пара оптимальных стратегий (A_i, B_j). В примере 1 игра имеет седловую точку (А₃, B₃). В этом случае число α = β называется (чистой) ценой игры (нижняя и верхняя цена игры совпадают). Это означает, что матрица содержит такой элемент, который является минимальным в своей строке и одновременно максимальным в своем столбце. В примере 1 это элемент 0. Цена игры равна 0.

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

Пример 2. Первая сторона (игрок А) выбирает один из трех типов вооружения – А₁, А₂, А₃, а противник (игрок В) – один из трех видов самолетов: В₁, В₂, В₃. Цель В – прорыв фронта обороны, цель А – поражение самолета. Вероятность поражения самолета В₁ вооружением А₁ равна 0,5, самолета В₂ вооружением А₁ равна 0,6, самолета В₃ вооружением А₁ равна 0,8 и т.д., т.е. элемент a_ij платежной матрицы – вероятность поражения самолета В _j вооружением А_i. Платежная матрица имеет вид:

	Вид самолета
В1	В2	В3
Тип вооружения	А1	0,5	0,6	0,8
А2	0,9	0,7	0,8
А3	0,7	0,5	0,6

Решить игру, т.е. найти нижнюю и верхнюю цену игры и оптимальные стратегии.

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

	В1	В2	В3	α i
А1	0,5	0,6	0,8	0,5
А2	0,9	0,7	0,8	0,7
А3	0,7	0,5	0,6	0,5
β j	0,9	0,7	0,8	0,7 0,7

В добавочном столбце находим максимальный элемент = 0,7, в добавочной строке находим минимальный элемент = 0,7.

Ответ: = 0,7. Оптимальные стратегии – А₂ и В₂.

Пример 3. Игра в орлянку. Каждый игрок при своем ходе может выбирать одну из двух стратегий: орел или решка. При совпадении выбранных стратегий А получает выигрыш +1, при несовпадении B получает выигрыш 1 (т. е. А получает выигрыш –1). Платежная матрица:

	В1 (орел)	В2 (решка)
А1 (орел)		-1
А2 (решка)	-1

Найти нижнюю и верхнюю цену игры. Имеет ли игра седловую точку?

Решение.

	В1	В2
А1		-1	-1
А2	-1
			-1

α = -1, β = 1, т. е. А проиграет не больше 1, и B проиграет не больше 1. Так как α ≠ β, игра не имеет седловой точки. Положения равновесия в этой игре не существует, и оптимального решения в чистых стратегиях найти нельзя.

Седловая точка – это пара оптимальных стратегий (Ai, Bj). В этом случае число a=b называется (чистой) ценой игры (нижняя и верхняя цена игры совпадают). Это означает, что матрица содержит такой элемент, который является минимальным в своей строке и одновременно максимальным в своем столбце.

Проверяем, имеет ли платежная матрица седловую точку. Если да, то выписываем решение игры в чистых стратегиях.

Игроки	B1	B2	B3	B4	a = min(Ai)
A1
A2
b = max(Bi)

Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(a_i) = (0,5,0) = 5, которая указывает на максимальную чистую стратегию A₂.

Верхняя цена игры b = min(b_j) = (8,8,5,10) = 5.

Седловая точка (2, 3) указывает решение на пару альтернатив (A₂,B₃). Цена игры равна 5.

Дата добавления: 2014-01-15