Теория игр, рафический метод в теории игр (стр. 2 из 4)

Таким образом, для любой стратегии Yj игрока P2 наибольший его проигрыш равен βj. В интересах игрока P2 выбрать стратегию с минимальным показателем неэффективности. Наименьшее из чисел βj обозначим β:

Число β называется верхней ценой игры в чистых стратегиях, а стратегия Yj0, которая максимизирует показатель неэффективности βj называется минимаксной стратегией игрока P2.

Теорема 3. Для элементов платежной матрицы имеют место неравенства:

и, следовательно, нижняя цена игры не больше ее верхней цены в чистых стратегиях: .

Пример. Найти решение игры, заданной платежной матрицей.

Решение:

Решим игру. Пусть

– оптимальная стратегия первого игрока, – оптимальная стратегия второго игрока, v – цена игры.

Рассмотрим матрицу

min

max(-1,-2,4)=4=

max 6 7 4 10

min (6,7,5,10)=5=

- нижняя цена игры.

- верхняя цена игры.

- максиминная стратегия, - минимаксная стратегия

Если

то элемент называется седловым элементом матрицы

A=

Теорема 4. (о разрешимости матричной игры в чистых стратегиях) Если платежная матрица A имеет седловой элемент

, то матричная игра имеет решение в чистых стратегиях, при этом оптимальной стратегий первого игрока является Xi0 чистая стратегия, а для второго – Yj0 чистая стратегия, а цена игры v = .

Пример. Найти решение игры, заданной платежной матрицей A=

Решение:

Решим игру. Пусть

-оптимальная стратегия первого игрока, - оптимальная стратегия второго игрока, v – цена игры.

Рассмотримматрицу

min

max 2 3

v= =2 цена игры v = 2 , существует седловой элемент = , тогда решение в чистых стратегиях имеет вид:

оптимальная стратегия первого игрока:

оптимальная стратегия второго игрока:

Ответ: оптимальные стратегии игроков

; , цена игры v =2 .

4.Принцип доминирования

Рассмотрим игру с платежной матрицей

A=

.

Если

,то говорят, что j-ая строка доминируется i-ой строкой, при этом i-ая строка называется доминирующей для первого игрока P1; j-ая строка – доминируемой строкой для P1.

Если

, то говорят, что i-ый столбец доминируется j-ым столбцом, при этом j-ый столбец называется доминирующим для второго игрока P2; i-ый столбец – доминируемый для P2. Доминируемую для игрока P1 строку и доминируемый для P2 столбец можно вычеркнуть (удалить).

Пример. Упростить платежную матрицу A=

, используя принцип доминирования.

Решение.

1 способ:

, т.к. - доминирующая строка, -

доминируемая строка

(1)

2 способ:,

(1)

5.Решение матричной игры 2×2 в смешанных стратегиях

Решить игру с платежной матрицей

Платежная функция

Решить игру с платежной матрицей

Положим

. Тогда

. Тогда

Если - оптимальная стратегия первого игрока, то по определению

решения матричной игры

Если игра с нулевой суммой, то ( -цена игры).

Решая систему, получим

.

Аналогично для второго игрока:

Тогда

Тогда

Если

- оптимальная стратегия второго игрока.

Если игра с нулевой суммой, то ( -цена игры).

Решая систему, получим

.

Пример. Найти решение игры заданной платежной матрицей A=

.

Решение:

Решим игру. Пусть

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

Ответ: оптимальные стратегии игроков

, цена игры .

Геометрическое решение игры

1.Решение игр с платежной матрицей 2×n

Решить игру с платежной матрицей A=