Решение игр с помощью линейного программирования. Оптимальные стратегии игроков. Графическое решение

Страницы работы

6 страниц (Word-файл)

Фрагмент текста работы

Задача: Матричная игра задана следующей платежной матрицей :

Стратегии "B"

Стратегии "A"

B1

B2

B3

B4

B5

A1

1

-3

5

-7

9

A2

-2

4

-6

8

-10

Найти решение матричной игры, а именно:  - найти верхнюю цену игры;  - нижнюю цену игры;  - чистую цену игры;  - указать оптимальные стратегии игроков;  - привести графическое решение (геометрическую интерпретацию), при необходимости.


Шаг:1

Определим нижнюю цену игры - α

Нижняя цена игры α — это максимальный выигрыш, который мы можем гарантировать себе, в игре против разумного противника, если на протяжении всей игры будем использовать одну и только одну стратегию (такая стратегия называется "чистой"). Найдем в каждой строке платежной матрицы минимальный элемент и запишем его в дополнительный столбец ( Выделен желтым цветом см. Табл.1). Затем найдем максимальный элемент дополнительного столбца (отмечен звездочкой), это и будет нижняя цена игры.

Таблица 1

Стратегии "B"

Стратегии "A"

B1

B2

B3

B4

B5

Минимумы строк

A1

1

-3

5

-7

9

-7*

A2

-2

4

-6

8

-10

-10

В нашем случае нижняя цена игры равна: α = -7, и для того чтобы гарантировать себе выигрыш не хуже чем -7 мы должны придерживаться стратегии A1 Шаг:2

Определим верхнюю цену игры - β

Верхняя цена игры β — это минимальный проигрыш, который может гарантировать себе игрок "В", в игре против разумного противника, если на протяжении всей игры он будет использовать одну и только одну стратегию. Найдем в каждом столбце платежной матрицы максимальный элемент и запишем его в дополнительную строку снизу ( Выделена желтым цветом см. Табл.2 ). Затем найдем минимальный элемент дополнительной строки (отмечен плюсом), это и будет верхняя цена игры.

Таблица 2

Стратегии "B"

Стратегии "A"

B1

B2

B3

B4

B5

Минимумы строк

A1

1

-3

5

-7

9

-7*

A2

-2

4

-6

8

-10

-10

Максимумы столбцов

1+

4

5

8

9

В нашем случае верхняя цена игры равна: β = 1, и для того чтобы гарантировать себе проигрыш не хуже чем 1 противник ( игрок "B") должен придерживаться стратегии B1 Шаг:3 Сравним нижнюю и верхнюю цены игры, в данной задаче они различаются, т.е. α ≠ β, платежная матрица не содержит седловой точки. Это значит, что игра не имеет решения в чистых минимаксных стратегиях, но она всегда имеет решение в смешанных стратегиях. Смешанная стратегия, это чередуемые случайным образом чистые стратегии, с определенными вероятностями (частотами). Смешанную стратегию игрока "А" будем обозначать

SA =

A1

A2

p1

p2

где A1, A2 - стратегии игрока "A", а p1, p2 - соответственно вероятности (частоты), с которыми эти стратегии применяются, причем p1 + p2 = 1. Аналогично смешанную стратегию игрока "В" будем обозначать

SB =

B1

B2

B3

B4

B5

q1

q2

q3

q4

q5

где B1, B2, B3, B4, B5 - стратегии игрока "B", а q1, q2, q3, q4, q5 - соответственно вероятности, с которыми эти стратегии применяются, причем q1 + q2 + q3 + q4 + q5 = 1. Оптимальная смешанная стратегия для игрока "А" та, которая обеспечивает ему максимальный выигрыш. Соответственно для "B" - минимальный проигрыш. Обозначаются эти стратегии SA* и SB* соответственно. Пара оптимальных стратегий образует решение игры. В общем случае в оптимальную стратегию игрока могут входить не все исходные стратегии, а только некоторые из них. Такие стратегии называются активными стратегиями. Шаг:4 Из теории игр известно, что если игрок "А" в своей оптимальной смешанной стратегии использует не более чем N активных стратегий, то и оптимальная стратегия игрока "B" состоит не более чем из N активных стратегий. А в нашем случае у "А" активных стратегий две и поэтому оптимальная стратегия игрока "В" представляет собой случайную смесь двух из 5-х стратегий B1, B2, B3, B4, B5. Но каких именно? Ответить на этот вопрос нам поможет геометрическая

Похожие материалы

Информация о работе