Платежная матрица. Верхняя и нижняя цена игры.

Рассмотрим парную конечную игру:

Игрок А имеет m стратегий A₁, A₂,…,A_m.

Игрок В имеет n стратегий B₁, B₂,…,B_n.

Размерность игры m´n.

В результате выбора игроками любой пары стратегий A_i и B_j (i=1,2,…m; j=1,2,…n) однозначно определяется исход игры, то есть выигрыш игрока А a_ij и проигрыш игрока В -a_ij.

Матрица P=(a_ij) (i=1,2,…m; j=1,2,…n), элементами которой являются выигрыши, соответствующие стратегиям A_i и B_j, называется платежной матрицей или матрицей игры. Общий вид матрицы:

Таблица 1

	B1	B2	…	Bn
A1	a11	a12	…	a1n
A2	a21	a22	…	a2n
…	…	…	…	…
Am	am1	am2	…	amn

Строки этой таблицы соответствуют стратегиям игрока А, столбцы - стратегиям игрока В.

Пример 17. Игра "Поиск"

Игрок А может спрятаться в одном из убежишь I или II. Игрок В ищет игрока А. Если найдет, то получает от А штраф $1, если не найдет, то платит игроку А $1.

Стратегии игрока А:

А₁ - игрок А прячется в убежище I;

А₂ - игрок А прячется в убежище II.

Стратегии игрока В:

В₁ - игрок В ищет в убежище I;

В₂ - игрок В ищет в убежище II.

Если игрок А в убежище I и В его обнаружил (стратегия A₁B₁), то платит штраф $1 (а₁₁=-1). Аналогично для стратегии A₂B₂ а₂₂=-1.

Если А в убежище I, а В его не обнаружил (стратегия A₁B₂), то игрок А получает $1 (а₁₂=1). Аналогично для стратегии A₂B₁ а₂₁=1.

Размерность игры 2´2.

Платежная матрица игра, матрица размером 2´2:

-1
	-1

Рассмотрим игру m´n с матрицей Р=(а_ij) размером m´n.

Определим наилучшую стратегию игрока А среди стратегий A₁, A₂,…,A_m.

Выбирая стратегию А_i, игрок А рассчитывает, что В выберет стратегию В_j, для которой выигрыш А минимален (игрок В вредит А).

Обозначим - минимальный выигрыш игрока А, при выборе им стратегии A_i, для всех возможных стратегиях В.

- минимальное число в i-ой строке платежной матрицы.

Среди всех возможных выберем максимальное:

- нижняя цена игры (максимин) - максимальный гарантированный выигрыш игрока А.

Стратегия, соответствующая максимину называется максиминной стратегией.

Игрок В заинтересован в том, чтобы уменьшить выигрыш игрока А. Выбирая стратегию В_j, игрок В максимально возможный при этом выигрыш игрока А. Обозначим - самый большой элемент в столбце j. Тогда

- верхняя цена игры (минимакс) - минимальный гарантированный выигрыш игрока В.

Стратегия, соответствующая минимаксу называется минимаксной стратегией.

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

Найдем верхнюю и нижнюю цену игры "Поиск".

Следовательно, игрок А может выбирать любую стратегию А₁ или А₂, они обе масиминны. Нижняя цена игры равна -1.

Любая стратегия игрока В минимаксна и верхняя цена игры равна 1.

Если верхняя цена игры равна нижней цене игры, то - чистая цена игры. Минимаксные стратегии, соответствующие чистой цене игры, называются оптимальными, а их совокупность - оптимальным решением или решением игры. Игрок А получает гарантированный, не зависящей от стратегии игрока В выигрыш , а игрок В добивается минимального гарантированного, не зависящего от выбора А, проигрыша .

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

Пара чистых стратегий A_i B_j дает оптимальное решение игры тогда и только тогда, когда a_ij - максимум в своем столбце и минимум в своей строке. Такая ситуация, если она существует, называется седловой точкой.

Пусть А^* В^* - пара чистых стратегий при которых достигается решение игры в задаче с седловой точкой. Введем функцию выигрыша игрока. P(A_i,B_j)=a_ij. Тогда, из условия оптимальности в седловой точке выполняется неравенство P(A_i,B^*)£ P(A^*,B^*)£ P(A^*,B_j), которое справедливо для всех i=1,2,…m; j=1,2,…n.

Пример.

Найти верхнюю и нижнюю цену игры.

0,5	0,6	0,8
0,9	0,7	0,8
0,7	0,6	0,6

Имеет ли игра седловую точку?

Решение:

Найдем минимумы по строкам и максимумы по столбцам. Среди минимумов найдем максимум max(0,5;0,7;0,6)=0,7 Минимксная стратегия А₂. Среди максимумов найдем минимум min(0,9;0,7;0,8)=0,7 Максиминная стратегия В₂.

	В1	В2	В3
А1	0,5	0,6	0,8	0,5
А2	0,9	0,7	0,8	0,7
А3	0,7	0,6	0,6	0,6
	0,9	0,7	0,8

Таким образом , следовательно игра имеет седловую точку а₂₂, соответствующую стратегии А₂В₂ (решение игры) и чистая цена игры .

Задания.

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

1.

0,3	0,6	0,8
0,9	0,4	0,2
0,7	0,5	0,4

2.

3.

4.

5.

6.

Дата добавления: 2015-11-16