Матричные игры
Предмет и задачи теории игр, терминология и классификация игр, их примеры. Принцип максимина в антагонистических играх, седловая точка. Эквивалентные задачи линейного программирования. Способы реализации случайного механизма выбора стратегий, их виды.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | учебное пособие |
| Язык | русский |
| Дата добавления | 05.05.2020 |
| Размер файла | 372,9 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
|
Bj Ai |
B1 |
B3 |
|
|
A1 |
5 |
3 |
|
|
A2 |
4 |
7 |
|
|
A3 |
4 |
3 |
В этой матрице стратегия А3 доминируется как стратегией А1, так и стратегией А2. Отбрасывая стратегию А3, окончательно получаем игру 2x2 с платежной матрицей
|
Bj Ai |
B1 |
B3 |
|
|
A1 |
5 |
3 |
|
|
A2 |
4 |
7 |
Эту игру уже упростить нельзя, ее надо решать рассмотренным выше алгебраическим или геометрическим методом.
Необходимо отметить, что отбрасывая дублируемые и доминируемые стратегии в игре с седловой точкой, мы все равно придем к игре с седловой точкой, т.е. к решению в чистых стратегиях. Но лучше сразу проверить, не обладает ли игра седловой точкой - это проще, чем сравнивать почленно все строки и все столбцы платежной матрицы.
Алгебраические методы решения матричных игр иногда производить проще, если использовать также следующие свойства матричных игр.
Свойство 1. Если ко всем элементам платежной матрицы прибавить (вычесть) одно и тоже число С, то оптимальные смешанные стратегии игроков не изменятся, а только цена игры увеличится (уменьшится) на это число С.
Свойство 2. Если каждый элемент платежной матрицы умножить на положительное число k, то оптимальные смешанные стратегии игроков не изменятся, а цена игры умножится на k.
Отметим, что эти свойства верны и для игр, имеющих седловую точку. Эти два свойства матричных игр применяются в следующих случаях:
1) если матрица игры наряду с положительными имеет и отрицательные элементы, то ко всем ее элементам прибавляют такое число, чтобы исключить отрицательные числа в матрице;
2) если матрица игры имеет дробные числа, то для удобства вычислений элементы этой матрицы следует умножить на такое число, чтобы все выигрыши были целыми числами.
Пример. Решить матричную игру 2х2 с платежной матрицей вида:
|
Bj Ai |
B1 |
B2 |
|
|
A1 |
0.5 |
-0.2 |
|
|
A2 |
0.1 |
0.3 |
Умножая все элементы платежной матрицы на 10, а затем прибавляя к ним число 2, получаем игру с платежной матрицей
|
Bj Ai |
B1 |
B2 |
|
|
A1 |
7 |
0 |
|
|
A2 |
3 |
5 |
Решая эту игру алгебраическим методом, получаем
; ;
; ;
.
В соответствии со свойствами 1 и 2, исходная матричная игра имеет те же оптимальные смешанные стратегии: и . А для получения исходной цены игры необходимо из полученной цены игры вычесть 2, а затем разделить на 10. Таким образом, получаем цену исходной игры: .
2.7 Решение игр 2xn и mx2
Как уже отмечалось в теореме об активных стратегиях, любая конечная игра mxn имеет решение, в котором число активных стратегий каждого игрока не превосходит, где . Следовательно, у игры 2xn или mx2 всегда имеется решение содержащее не более двух активных стратегий у каждого из игроков . Если эти активные стратегии игроков будут найдены, то игры 2xn и mx2 превращаются в игры 2x2, методы решения которых рассмотрены выше.
Практически решение игры 2xn осуществляется следующим образом:
1) строится графическое изображение игры для игрока А;
2) выделяется нижняя граница выигрыша и находится наибольшая ордината нижней границы (максимин), которая равна цене игры ;
3) определяется пара стратегий игрока В, пересекающихся в точке оптимума. Эти стратегии и являются активными стратегиями игрока В.
Таким образом, игра 2xn сведена к игре 2x2, которую более точно можно решить алгебраическим методом.
Если в точке оптимума пересекается более двух стратегий, то в качестве активных стратегий может быть выбрана любая пара из них.
Решение игры mx2 осуществляется аналогично. Но в этом случае строится графическое изображение игры для игрока В и выделяется не нижняя, а верхняя граница выигрыша (так как находится оптимальная смешанная стратегия игрока В), и на ней находится точка оптимума с наименьшей ординатой (минимакс).
Пример. Найти решение игры, платежная матрица которой имеет вид:
|
Bj Ai |
B1 |
B2 |
B3 |
|
|
A1 |
2 |
5 |
8 |
|
|
A2 |
7 |
4 |
3 |
Платежная матрица не имеет седловой точки, поэтому оптимальное решение должно быть в смешанных стратегиях. Строим графическое изображение игры для игрока А (рис.2.10)
Рис. 2.10
Точка N (максимин) является точкой оптимума. В этой точке пересекаются линии, соответствующие активным стратегиям В1 и В2 игрока В. Таким образом, исключая стратегию В3, получаем матричную игру 2x2 с платежной матрицей вида
|
Bj Ai |
B1 |
B2 |
|
|
A1 |
2 |
5 |
|
|
A2 |
7 |
4 |
Используя алгебраический метод решения этой игры, получаем точное решение
; ;
; ;
.
Ответ: ; ; .
Пример. Найти решение игры, платежная матрица которой имеет вид
|
Bj Ai |
B1 |
B2 |
|
|
A1 |
0 |
1 |
|
|
A2 |
4 |
2 |
|
|
A3 |
-1 |
4 |
|
|
A4 |
1 |
-3 |
|
|
A5 |
6 |
-2 |
|
|
A6 |
1,5 |
3 |
Платежная матрица не имеет седловой точки. Для сведения данной игры к игре 2x2 строим ее графическое изображение для игрока В (рис. 2.11).
Точка М (минимакс) является точкой оптимума. В этой точке пересекаются отрезки, соответствующие активным стратегиям А2, А6 и А3 игрока А. Таким образом, исключая стратегии А1, А4 и А5 и выбирая из трех активных стратегий две (например, А2 и А3 или А2 и А6), приходим к матричной игре 2x2. Выбор стратегий А3 и А6 исключен, так как в этом случае точка М перестанет быть точкой минимакса.
Рис.2.11
Пусть выбираются стратегии А2 и А3. Тогда игра 2x2 приобретает вид
|
Bj Ai |
B1 |
B2 |
|
|
A2 |
4 |
2 |
|
|
A3 |
-1 |
4 |
Оптимальные смешанные стратегии данной игры, а, следовательно, и исходной игры определяются следующими вероятностями:
; ;
; ;
.
Ответ: ; ; .
Другой вариант игры 2x2 получается, если использовать стратегии А2 и А6. В этом случае платежная матрица имеет вид
|
Bj Ai |
B1 |
B2 |
|
|
A2 |
4 |
2 |
|
|
A6 |
1,5 |
3 |
Тогда
; ;
; ;
.
Ответ: ; ; .
Естественно, что цена игры для обоих вариантов одинакова.
В заключение наметим общую схему решения матричных игр 2xn и mx2:
1. Определяется наличие седловой точки, т.е. возможность решения игры в чистых стратегиях. Если нижняя цена игры не равна верхней цене игры , то осуществляется поиск решения в смешанных стратегиях.
2. Производится упрощение матричной игры путем исключения дублирующих и доминируемых стратегий. Если упрощенная игра имеет размерность не 2x2, то переходим к этапу 3.
3. Строится графическое изображение игры и определяется две активные стратегии игрока, имевшего в исходной задаче число стратегий больше двух.
4. Решается матричная игра 2x2.
ТЕСТЫ
(В - Верно, Н - Неверно)
1. Если в игре 2xn нет оптимального решения в чистых стратегиях, то оптимальное решение в смешанных стратегиях содержит две активные стратегии у каждого из игроков.
2. В игре mx2 число активных стратегий в оптимальной стратегии каждого из игроков может быть равно или единице, или двум.
3. Оптимальное решение в игре двух лиц с нулевой суммой всегда является устойчивым независимо от того, смешанные или чистые стратегии используют игроки.
4. Если оптимальная цена матричной игры отрицательна, то конечный результат игры будет убыточным для игрока А.
5. Прибавление одного и того же числа ко всем элементам платежной матрицы не влияет на цену игры.
6. Умножение всех элементов платежной матрицы на одно и тоже положительное число не изменяет оптимальных стратегий игроков.
7. Цена матричной игры изменится, если из платежной матрицы исключить строки и столбцы, соответствующие дублирующим и доминируемым стратегиям.
8. Любая матричная игра 2xn или mx2 может быть сведена к игре 2х2.
Ответы: (1 - В; 2 - В; 3 - В; 4 - В; 5 - Н; 6 - В; 7 - Н; 8 - В).
ЗАДАЧИ
Решить следующие матричные игры:
|
1. |
8 |
1 |
7 |
2. |
-4 |
-8 |
-7 |
-3 |
3. |
5 |
1 |
3 |
||
|
3 |
0 |
7 |
-5 |
-9 |
-8 |
-4 |
7 |
8 |
2 |
|||||
|
4. |
6 |
13 |
19 |
25 |
19 |
15 |
16 |
18 |
5. |
3 |
3 |
4 |
5 |
|
|
19 |
25 |
19 |
18 |
16 |
12 |
13 |
15 |
5 |
4 |
3 |
3 |
|||
|
6. |
0,4 |
0,5 |
1 |
7. |
1 |
2 |
3 |
8. |
11 |
8 |
12 |
1 |
||
|
1 |
0,5 |
0,3 |
4 |
3 |
0 |
-7 |
-1 |
-8 |
2 |
|||||
|
9. |
10 |
-4 |
6 |
14 |
0 |
10. |
2 |
-6 |
10 |
-14 |
18 |
|||
|
0 |
10 |
4 |
4 |
12 |
-4 |
8 |
-12 |
16 |
-20 |
|||||
|
11. |
3 |
7 |
-1 |
11 |
-5 |
12. |
9 |
-5 |
7 |
1 |
-3 |
|||
|
6 |
2 |
10 |
-4 |
14 |
-10 |
4 |
-8 |
-6 |
2 |
|||||
|
13. |
24 |
0 |
18 |
21 |
14. |
7 |
9 |
0 |
||||||
|
9 |
18 |
9 |
3 |
6 |
0 |
10 |
||||||||
|
15. |
-1 |
8 |
7 |
6 |
3 |
1 |
||||||||
|
9 |
0 |
1 |
2 |
5 |
7 |
|||||||||
|
16. |
1 |
3 |
17. |
2 |
10 |
18. |
-3 |
-9 |
19. |
1 |
3 |
|||
|
5 |
7 |
4 |
8 |
-15 |
-21 |
5 |
7 |
|||||||
|
9 |
11 |
6 |
6 |
-27 |
-33 |
9 |
11 |
|||||||
|
8 |
4 |
|||||||||||||
|
10 |
2 |
|||||||||||||
|
20. |
-1 |
5 |
21. |
11 |
3 |
22. |
2 |
2 |
3 |
-1 |
23. |
4 |
8 |
|
|
-3 |
1 |
9 |
7 |
4 |
3 |
2 |
6 |
4 |
6 |
|||||
|
0 |
-3 |
10 |
5 |
6 |
4 |
|||||||||
|
-3 |
0 |
7 |
11 |
-2 |
12 |
|||||||||
|
1 |
-3 |
8 |
9 |
|||||||||||
|
5 |
-1 |
|||||||||||||
|
24. |
1 |
3 |
25. |
2 |
4 |
-2 |
8 |
26. |
1 |
2 |
27. |
5 |
9 |
|
|
1 |
4 |
3 |
6 |
5 |
-5 |
5 |
6 |
5 |
7 |
|||||
|
2 |
1 |
-7 |
9 |
7 |
5 |
|||||||||
|
-1 |
5 |
-4 |
-3 |
-1 |
13 |
|||||||||
|
2 |
1 |
|||||||||||||
|
28. |
3 |
8 |
12 |
29. |
0 |
8 |
30. |
-2 |
10 |
|||||
|
6 |
10 |
14 |
2 |
6 |
-6 |
2 |
||||||||
|
4 |
4 |
0 |
-6 |
|||||||||||
|
6 |
2 |
-6 |
0 |
|||||||||||
|
8 |
0 |
1 |
1 |
|||||||||||
|
2 |
-6 |
|||||||||||||
|
10 |
-2 |
2.8 Решение игр mхn. Эквивалентные задачи линейного программирования
Пусть имеется матричная игра mxn без седловой точки с матрицей выигрышей ||aij||. Допустим, что все выигрыши aij положительны (этого всегда можно добиться, прибавляя ко всем элементам матрицы достаточно большое число С; от этого, как уже отмечалось, цена игры увеличится на C, а оптимальные решения SA и SB не изменятся).
Если все aij положительны, то и цена игры при оптимальной стратегии тоже положительна, т.к. .
В соответствии с основной теоремой матричных игр, если платежная матрица не имеет седловой точки, то имеется пара оптимальных смешанных стратегий SA=||p1, p2, ..., pm|| и SB=||q1, q2, ..., qn||, применение которой обеспечивает игрокам получение цены игры .
Найдем вначале SA. Для этого предположим, что игрок В отказался от своей оптимальной смешанной стратегии SB и применяет только чистые стратегии. В каждом из этих случаев выигрыш игрока А будет не меньше, чем :
(2.25)
Разделив левую и правую часть каждого из неравенств (2.25) на положительную величину v и введя обозначения:
(2.26)
запишем неравенства (2.25) в следующем виде:
, (2.27)
где x1, x2, ... xm - неотрицательные переменные.
В силу того, что
p1+p2+...+pm=1,
переменные x1, x2, ... xm удовлетворяют условию
. (2.28)
Учитывая, что игрок А стремится максимизировать , получаем следующую задачу линейного программирования: найти неотрицательные значения переменных x1, x2, ... xm такие, чтобы они удовлетворяли линейным ограничениям - неравенствам (2.27) и обращали в минимум линейную функцию этих переменных:
min L(x)=x1+x2+ ... +xm. (2.29)
Из решения задачи линейного программирования находим цену игры и оптимальную стратегию Sa по формулам:
, (2.30)
, . (2.31)
Аналогично находим оптимальную стратегию SВ игрока В. Предположим, что игрок А отказался от своей оптимальной стратегии SA и применяет только чистые стратегии. Тогда проигрыш игрока В в каждом из этих случаев будет не больше, чем :
. (2.32)
Разделив левую и правую части каждого их неравенств (2.32) на положительную величину и введя обозначения:
, (2.33)
запишем неравенство (2.32) в следующем виде:
, (2.34)
где y1, y2, ..., yn - неотрицательные переменные.
В силу того, что q1+q2+...+qn=1, переменные y1, y2, ..., yn удовлетворяют условию
. (2.35)
Учитывая, что игрок В стремится минимизировать положительную цену v (свой проигрыш), получаем задачу линейного программирования: найти неотрицательные значения переменных y1, y2, ..., yn такие, чтобы они удовлетворяли линейным ограничениям (2.34) и обращали в максимум линейную функцию этих переменных:
max L(y)=y1+y2+ ... +ym. (2.36)
Эта задача является двойственной по отношению к задаче, представленной условиями (2.27) и (2.29).
Оптимальная стратегия SB=||q1, q2, ..., qn|| игрока В определяется из решения двойственной задачи линейного программирования по формулам:
, . (2.37)
Таким образом, оптимальные стратегии SA=||p1, p2, ..., pm|| и SB=||q1, q2, ..., qn|| матричной игры mxn с платежной матрицей ||aij|| могут быть найдены путем решения пары двойственных задач линейного программирования:
|
Прямая (исходная) задача |
Двойственная задача |
|
|
, , ; , . |
, , ; , . |
При этом
, (2.38)
.
Пример. Найти решение и цену матричной игры, платежная матрица которой имеет вид
|
Bj Ai |
B1 |
B2 |
B3 |
|
|
A1 |
1 |
2 |
3 |
|
|
A2 |
3 |
1 |
1 |
|
|
A3 |
1 |
3 |
1 |
Решение
1. Так как =1 не равно =3, то игра не имеет седловой точки.
2. В данной игре нет дублирующих и доминируемых стратегий.
3. Решаем игру путем решения пары двойственных задач линейного программирования.
Математические модели пары двойственных задач линейного программирования будут выглядеть следующим образом:
|
Прямая (исходная) задача: Найти неотрицательные переменные х1,х2,х3, минимизирующие функцию min L (x)=х1+х2+х3, при ограничениях: х1+3х2+х31; 2х1+х2+3х31; 3х1+х2+х31; xi0, . |
Двойственная задача: Найти неотрицательные переменные у1,у2,у3, максимизирующие функцию max L (x)=y1+y2+y3, при ограничениях: y1+2y2+3y31; 3y1+y2+y31; y1+3y2+y31; yj0, . |
Данные задачи решаются, например, симплекс - методом. Поскольку в двойственной задаче ограничения имеют вид ““, то эту задачу решать проще (не нужно вводить искусственные переменные). Оптимальное решение исходной задачи можно будет непосредственно получить из данных симплекс - таблицы для оптимального решения двойственной задачи.
Начальная симплекс - таблица двойственной задачи имеет вид
|
БП |
у1 |
у2 |
у3 |
у4 |
у5 |
у6 |
Решение |
|
|
у4 |
1 |
2 |
3 |
1 |
0 |
0 |
1 |
|
|
у5 |
3 |
1 |
1 |
0 |
1 |
0 |
1 |
|
|
у6 |
1 |
3 |
1 |
0 |
0 |
1 |
1 |
|
|
L |
-1 |
-1 |
-1 |
0 |
0 |
0 |
0 |
ведущий столбец
|
БП |
у1 |
у2 |
у3 |
у4 |
у5 |
у6 |
Решение |
|
|
у4 |
0 |
1 |
0 |
|||||
|
у1 |
1 |
0 |
0 |
|||||
|
у6 |
0 |
0 |
1 |
|||||
|
L |
0 |
0 |
0 |
ведущий столбец
|
БП |
у1 |
у2 |
у3 |
у4 |
у5 |
у6 |
Решение |
|
|
у4 |
0 |
0 |
1 |
|||||
|
у1 |
1 |
0 |
0 |
|||||
|
у2 |
0 |
1 |
0 |
|||||
|
L |
0 |
0 |
0 |
ведущий столбец
И, наконец, получаем симплекс-таблицу, которая соответствует оптимальному решению двойственной задачи:
|
БП |
у1 |
у2 |
у3 |
у4 |
у5 |
у6 |
Решение |
|
|
у3 |
0 |
0 |
1 |
|||||
|
у1 |
1 |
0 |
0 |
|||||
|
у2 |
0 |
1 |
0 |
|||||
|
L |
0 |
0 |
0 |
Оптимальное решение двойственной задачи линейного программирования следующее:
у1=; у2=; у3=; max L (y)= .
Находим оптимальную смешанную стратегию игрока В в соответствии с формулами (2.37) и (2.38):
;
.
Следовательно, .
Оптимальное решение исходной задачи находим, используя двойственные оценки, из симплекс - таблицы для оптимального решения двойственной задачи: коэффициент при начальной базисной переменной в оптимальном уравнении прямой задачи равен разности между правой и левой частями ограничения двойственной задачи, ассоциированного с данной начальной переменной.
Получаем x1=; x2=; x3=; max L (x)= .
Отсюда определим вероятности применения своих активных стратегий игроком А:
.
Следовательно: .
Таким образом, решение игры mxn сводится к решению задачи линейного программирования. Нужно заметить, что и наоборот, - для любой задачи линейного программирования может быть построена эквивалентная ей задача теории матричных игр. Эта связь задач теории матричных игр с задачами линейного программирования оказывается полезной не только для теории игр, но и для линейного программирования. Дело в том, что существуют приближенные численные методы решения матричных игр, которые при большой размерности задачи могут оказаться проще, чем симплекс - метод.
ТЕСТЫ
(В - Верно, Н - Неверно)
Если все элементы платежной матрицы в матричной игре положительны, то и цена игры положительна.
Любую матричную игру можно свести к паре двойственных задач линейного программирования.
В прямой задаче линейного программирования, к которой сводится матричная игра, целевая функция подлежит максимизации.
В обратной задаче линейного программирования, к которой сводится матричная игра, ограничения получаются со знаком «».
Цена матричной игры, получаемая из решения прямой и обратной задач может быть различна.
Ответы: (1 - В; 2 - В; 3 - Н; 4 - В; 5 - Н).
ЗАДАЧИ
Решить следующие матричные игры:
|
1. |
2 |
4 |
6 |
2. |
-7 |
4 |
2 |
3. |
-5 |
6 |
4 |
||
|
6 |
2 |
2 |
0 |
2 |
1 |
2 |
4 |
3 |
|||||
|
2 |
6 |
2 |
6 |
-5 |
-1 |
8 |
-3 |
1 |
|||||
|
4. |
1 |
3 |
2 |
5. |
2 |
1 |
0 |
6. |
4 |
6 |
1 |
||
|
3 |
1 |
3 |
1 |
2 |
1 |
4 |
4 |
1 |
|||||
|
2 |
3 |
1 |
0 |
1 |
2 |
1 |
1 |
6 |
|||||
|
7. |
-4 |
-6 |
-1 |
8. |
-2 |
-5 |
2 |
9. |
5 |
7 |
1 |
||
|
-4 |
-4 |
-1 |
-1 |
1 |
-5 |
5 |
5 |
1 |
|||||
|
-1 |
-1 |
-6 |
-2 |
-1 |
-2 |
2 |
2 |
6 |
|||||
|
10. |
2 |
6 |
4 |
11. |
3 |
6 |
9 |
12. |
0 |
1 |
2 |
||
|
6 |
2 |
6 |
9 |
3 |
3 |
2 |
0 |
0 |
|||||
|
4 |
6 |
2 |
3 |
9 |
3 |
0 |
2 |
1 |
2.9 Приближенный метод решения матричных игр mxn
Рассмотрим приближенный метод решения матричных игр - метод Брауна-Робинсон (метод итераций). Идея его заключается в следующем. Разыгрывается эксперимент, в котором игроки А и В поочередно применяют друг против друга свои чистые стратегии. Каждый из игроков стремится увеличить свой выигрыш, предполагая, что будущее будет походить на прошлое; при этом считается, что ни один из них не знает своей оптимальной стратегии.
Такой принцип приводит к некоторой последовательности партий игры, для каждой из которых можно подсчитать приближенные оптимальные стратегии каждого из игроков, а также верхнюю и нижнюю цены игры.
Вместо того, чтобы вычислять каждый раз средний выигрыш, можно пользоваться суммарным за все предыдущие ходы выигрышем и выбирать ту свою стратегию, при которой этот накопленный выигрыш максимален.
Доказано, что такой метод сходится: при увеличении числа партий средний выигрыш на одну партию будет стремиться к цене игры, а частоты применения стратегий - к их вероятностям в оптимальных смешанных стратегиях игроков.
Объясним этот метод на примере игры 3x3, платежная матрица которой приведена ниже. Игра начинается с произвольно выбранной стратегии игрока А, - например стратегии А1 (выбранные стратегии обозначаются звездочкой). Платежные элементы этой строки переписываются под платежной матрицей. Игрок В, предполагая, что будущее будет походить на прошлое, выберет стратегию В1, при которой его проигрыш минимален. Соответствующий этой стратегии проигрыш обозначен звездочкой. Платежные элементы стратегии В1 переписываются справа от платежной матрицы. Игрок А, также предполагая, что будущее будет походить на прошлое, выбирает стратегию А2 (наибольшее число обозначено звездочкой). Платежные элементы, соответствующие стратегии А2, прибавляются поочередно к элементам предыдущей строки, записанной под матрицей. Далее выбирается наименьший элемент суммарной строки. Ему соответствует стратегия В2. Тогда к столбцу, записанному справа от платежной матрицы, поочередно прибавляются платежные элементы стратегии В2. Этот процесс продолжается до тех пор, пока разрыв между нижней и верхней оценками игры станет небольшим. Если при выборе стратегий на некотором шаге есть несколько альтернатив, то выбирается любая из равноценных стратегий.
В рассматриваемом примере сделано 20 шагов. За эти двадцать шагов игрок А применил свою первую стратегию (количество звездочек в суммарных выигрышах, соответствующей первой стратегии) 7 раз; вторую - 8 раз; третью - 5 раз. Игрок В применил стратегию В1 восемь раз; вторую - 8 раз; третью - 4 раза. Следовательно, приближенные оценки оптимальных стратегий, полученные за 20 итераций, равны:
.
Эти оценки не так уж сильно отличаются от точного решения данной матричной игры, которое равно .
|
Bi Ai |
B1 |
B2 |
B3 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
||
|
A1 |
1 |
2 |
3 |
* |
1 |
3 |
5 |
8* |
9* |
10 |
12 |
14 |
17* |
20* |
|
|
A2 |
3 |
1 |
1 |
3* |
4* |
5 |
6 |
9 |
12* |
13* |
14 |
15 |
16 |
||
|
A3 |
1 |
3 |
1 |
1 |
4 |
7* |
8 |
9 |
10 |
13 |
16* |
17 |
18 |
||
|
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
||||||
|
1 |
1* |
2 |
3 |
21* |
22 |
24* |
25 |
27 |
29 |
31 |
32 |
33 |
36* |
||
|
2 |
4 |
3* |
4 |
19 |
22* |
23 |
26* |
27* |
28 |
29 |
32 |
35* |
36 |
||
|
3 |
7 |
4* |
5 |
19 |
20 |
23 |
24 |
27 |
30* |
33* |
34* |
35 |
36 |
||
|
4 |
8 |
7 |
6* |
||||||||||||
|
5 |
9* |
9 |
9 |
||||||||||||
|
6 |
10* |
11 |
12 |
||||||||||||
|
7 |
13 |
12* |
13 |
||||||||||||
|
8 |
16 |
13* |
14 |
||||||||||||
|
9 |
17 |
16 |
15* |
||||||||||||
|
10 |
18 |
13 |
18* |
||||||||||||
|
11 |
19* |
20 |
21 |
||||||||||||
|
12 |
20* |
22 |
24 |
||||||||||||
|
13 |
23 |
23* |
25 |
||||||||||||
|
14 |
24* |
25 |
28 |
||||||||||||
|
15 |
27 |
26* |
29 |
||||||||||||
|
16 |
30 |
27* |
30 |
||||||||||||
|
17 |
31 |
30* |
31 |
||||||||||||
|
18 |
32* |
33 |
32 |
||||||||||||
|
19 |
33* |
36 |
33 |
||||||||||||
|
20 |
36 |
37 |
34* |
Приближенную цену игры определяют как среднеарифметическое между нижней оценкой игры , равной минимально накопленному выигрышу игрока А, деленному на число шагов , и верхней оценкой игры , равной максимальному суммарному проигрышу игрока В, деленному на :
.
В рассматриваемом примере
.
Точная цена игры = 1,8.
Разрыв между и отражает неточность оценок относительно оптимальных смешанных стратегий. В примере составляет 2,8% от цены игры =1,8. Увеличивая число итераций , можно найти еще более точные оценки оптимальных смешанных стратегий.
Преимуществом итерационного метода решения матричных игр является то, что объем вычислений с увеличением размерности игры mxn растет существенно медленнее, чем в методах линейного программирования (в частности, в симплекс - методе).
2.10 Качественная оценка элементов платежной матрицы
Очевидной трудностью при использовании теории игр является задание элементов платежной матрицы с требуемой точностью. Вместе с тем эту задачу не нужно и переоценивать. Использование, например, свойств 1 и 2 из параграфа 2.6, позволяет находить оптимальные стратегии задавая лишь относительные значения элементов платежной матрицы. Например, если в платежной матрице имеется всего три различных значения элементов платежной матрицы, то в этом случае совершенно не важно, какое значение имеют наименьший и наибольший платежи. Единственно, что имеет значение - это относительное положение третьего платежа.
Таким образом, теория игр может дать важные результаты даже в тех случаях, в которых точные оценки платежей затруднены. В частности, имеется слабая форма оценки платежей, называемая упорядочением. Она заключается в расположении платежей по порядку их относительной величины. Существуют игровые ситуации, для которых не требуется ничего большего, чем определение порядка расположения платежей по величине. В других игровых ситуациях знание порядка платежей позволяет сделать частичные выводы относительно оптимальных стратегий и цены игры.
Пусть, например, платежи оцениваются как плохие (п); удовлетворительные (у), хорошие (х) или отличные (о), а матрица игры имеет вид
|
Bj Ai |
B1 |
B2 |
B3 |
B4 |
B5 |
i |
|
|
A1 |
П |
о |
х |
о |
х |
п |
|
|
A2 |
У |
у |
х |
о |
х |
у* |
|
|
A3 |
П |
х |
о |
о |
х |
п |
|
|
A4 |
У |
о |
о |
п |
о |
п |
|
|
j |
у* |
о |
о |
о |
о |
В этой игре ==, т.е. игра решается в чистых стратегиях. Игрок А должен придерживаться своей второй стратегии, а игрок В - стратегии В1. Цена игры - «удовлетворительно».
Пусть игра имеет седловую точку в клетке, отмеченной звездочкой.
|
B1 |
B2 |
B3 |
B4 |
B5 |
B6 |
||
|
A1 |
|||||||
|
A2 |
|||||||
|
A3 |
|||||||
|
A4 |
* |
||||||
|
A5 |
|||||||
|
A6 |
|||||||
|
A7 |
Так как седловая точка отмечает наименьшее число в этой строке и наибольшее число в столбце, то все остальные числа в данной строке (столбце) могут быть какими угодно, лишь бы число, отмеченное звездочкой, оставалось наименьшим в строке (наибольшим в столбце). Наконец, все остальные числа в матрице, которые не попали в строку и столбец, соответствующих оптимальным стратегиям, могут быть вообще какими угодно. Их значения не влияют ни на оптимальный способ ведения игры, ни на ее цену. Пример. Решить игру, платежная матрица которой имеет вид
|
Bj Ai |
B1 |
B2 |
B3 |
|
|
A1 |
п |
о |
у |
|
|
A2 |
х |
у |
х |
|
|
A3 |
п |
у |
о |
Как видно стратегия В1 доминирует стратегию В3, далее стратегия А1 будет доминировать стратегию А3, а, следовательно, исходную игру можно свести к игре 2*2:
|
Bj Ai |
B1 |
B2 |
i |
|
|
A1 |
п |
о |
п |
|
|
A2 |
х |
у |
у* |
|
|
j |
х* |
о |
Таким образом, игрокам не следует использовать стратегии А3 и В3. Так как =у не равняется =х, то игра не имеет седловой точки и должна решаться в смешанных стратегиях.
Частоты применения своих стратегий игроком А равны:
;
.
Частоты применения своих стратегий игроком В равны:
;
,
таким образом, частота применения стратегии А1 пропорциональна разности между “хорошо” и “удовлетворительно”, а стратегии А2 пропорциональна разности между “отлично” и “плохо”. Ясно, что стратегия А1 должна применяться реже, чем стратегия А2 независимо от того, какие упорядоченные числа будут приписаны этим понятиям.
Положение игрока В несколько более неопределенно. Он должен применять стратегию В1 с частотой пропорциональной разности между “отлично” и “удовлетворительно”, а стратегию В2 - с частотой, пропорциональной разности между “хорошо” и “плохо”. Здесь неясно, какая разность больше.
Хотя в данном примере мы не получили строгого решения, но полученное решение дает ориентацию, как следует себя вести в исходной слабо определенной ситуации.
2.11 Способы реализации случайного механизма выбора стратегий
Для реализации применения игроком его активных стратегий с оптимальными вероятностями (относительными частотами), необходимо иметь случайный механизм выбора стратегий.
Например, если оптимальная смешанная стратегия (относительные частоты 1:1), то для ее реализации можно использовать подбрасывание монеты: если выдает “герб”, то применяется первая стратегия, а если “решка”, - то вторая.
Игральную кость можно использовать при относительных частотах 1:5; 2:4; 1:1; 4:2; и так далее до 5:1.
Секундная стрелка часов может служить для выбора случайных чисел от 0 до 59, если только игрок не смотрел на часы недавно и не знает наперед, даже приблизительно, ответ.
Но на практике могут потребоваться любые сочетания чисел в качестве относительных частот. Механизмом, удовлетворяющим вышеуказанному требованию, является датчик случайных чисел R от 0 до 1 с равномерной плотностью вероятности.
Так как стратегии А1, А2, ..., Аm несовместны (в каждый момент, применяется лишь одна из этих стратегий) и образуют полную группу событий , то для реализации случайного механизма выбора стратегий поступают следующим образом. Делят интервал (0, 1) на m участков длиной p1, p2, ..., pm (рис. 2.12). На какой из участков попало число R - ту стратегию и следует в данной партии использовать.
Рис. 2.12
Возникает вопрос: а как же реализуется сам датчик случайных чисел R? Самый простой из датчиков случайных чисел (ДСЧ) - это вращающийся барабан, в котором перемешивается перенумерованные шары. Пусть, например, нам надо разыграть случайное число R от 0 до 1 с точностью 0.001. Заложим в барабан 1000 перенумерованных шаров и после, случайным образом выбранного одного из шаров, разделим его номер на 1000.
Можно поступить и иначе: вместо1000 шаров заложить только 10, с цифрами 0, 1, 2, .... , 9. Вынув случайным образом первый шар, получаем первый десятичный знак дроби. Вернув шар в барабан и прокрутив его, выберем случайным образом второй шар - его номер даст второй десятичный знак и т.д.
Можно доказать, что получаемые таким образом десятичные дроби будет иметь равномерное распределение от 0 до 1. Достоинством этого способа в том, что он может обеспечить любую точность задания числа R.
На практике широко применяются таблицы случайных чисел. Ниже приведен пример такой таблицы (рис.2.13). Числа сгруппированы лишь для удобства пользования таблицей. Можно начинать с любой точки таблицы, отсчитывать числа вверх или вниз, группировать числа.
Как использовать таблицу случайных чисел, чтобы получить желаемые относительные частоты? Возьмем в качестве примера оптимальную стратегию . Далее выбираем из таблицы любое однозначное случайное число. Если это число равно 0, 1, 2, 3 или 4, то используем в данной партии первую стратегию. Если число равно 5 и 6, то применяем вторую стратегию. Если это число равно 7, 8 и 9, то отбрасываем его и берем число под ним. Для следующей партии используется число ниже предыдущего.
|
11 |
16 |
43 |
63 |
18 |
75 |
6 |
13 |
76 |
74 |
40 |
60 |
31 |
61 |
52 |
|||
|
21 |
21 |
59 |
17 |
91 |
76 |
83 |
15 |
86 |
78 |
40 |
94 |
15 |
35 |
85 |
|||
|
10 |
43 |
84 |
44 |
82 |
66 |
55 |
83 |
76 |
49 |
73 |
50 |
58 |
34 |
72 |
|||
|
36 |
79 |
22 |
62 |
36 |
33 |
26 |
66 |
65 |
83 |
39 |
41 |
21 |
60 |
13 |
|||
|
73 |
94 |
40 |
47 |
73 |
12 |
3 |
25 |
14 |
14 |
57 |
99 |
47 |
67 |
48 |
|||
|
49 |
56 |
31 |
28 |
72 |
14 |
6 |
39 |
31 |
17 |
61 |
83 |
45 |
91 |
99 |
|||
|
64 |
20 |
84 |
82 |
37 |
38 |
60 |
52 |
93 |
41 |
91 |
40 |
27 |
72 |
27 |
|||
|
51 |
48 |
67 |
28 |
75 |
64 |
51 |
61 |
79 |
71 |
58 |
99 |
98 |
38 |
80 |
|||
|
99 |
75 |
62 |
63 |
60 |
41 |
70 |
17 |
31 |
17 |
40 |
68 |
49 |
99 |
48 |
|||
|
71 |
32 |
55 |
52 |
17 |
13 |
1 |
57 |
29 |
7 |
75 |
97 |
86 |
42 |
98 |
|||
|
65 |
28 |
59 |
71 |
98 |
12 |
13 |
85 |
30 |
10 |
34 |
55 |
63 |
98 |
61 |
|||
|
17 |
26 |
45 |
73 |
27 |
38 |
22 |
42 |
93 |
1 |
65 |
99 |
5 |
70 |
48 |
|||
|
95 |
63 |
99 |
97 |
54 |
31 |
19 |
99 |
25 |
58 |
16 |
38 |
11 |
50 |
69 |
|||
|
61 |
55 |
57 |
64 |
4 |
86 |
21 |
1 |
18 |
8 |
52 |
45 |
88 |
88 |
80 |
|||
|
78 |
13 |
79 |
87 |
68 |
4 |
68 |
98 |
71 |
30 |
33 |
0 |
78 |
56 |
7 |
|||
|
62 |
49 |
9 |
92 |
15 |
84 |
98 |
72 |
87 |
59 |
38 |
71 |
23 |
15 |
12 |
|||
|
24 |
21 |
66 |
34 |
44 |
21 |
28 |
30 |
70 |
44 |
58 |
72 |
20 |
36 |
78 |
|||
|
16 |
97 |
59 |
54 |
28 |
33 |
22 |
65 |
59 |
3 |
26 |
18 |
86 |
94 |
97 |
|||
|
59 |
13 |
83 |
95 |
42 |
71 |
16 |
85 |
76 |
9 |
12 |
89 |
35 |
40 |
48 |
|||
|
29 |
47 |
85 |
96 |
52 |
50 |
41 |
43 |
19 |
61 |
33 |
18 |
68 |
13 |
46 |
Рис.2.13
Часто желательно модифицировать этот способ. Например, в случае относительных частот 8:3 сумма чисел равна 8+3=11. Приходится применять двухзначные числа от 00 до 99. Но чтобы не отбрасывать числа от 11 до 99, разделим 99 на 11, получаем 9 (в общем случае это будет смешанная дробь). Далее умножаем 89=72 и 39=27. Теперь, если выбранное двухзначное число лежит в пределах от 00 до 71, используем первую стратегию, а если от 72 до 99, - то вторую. Число 99 будем отбрасывать.
Для получения R на ЭВМ применяются специальные датчики случайных чисел. Это могут быть как “физические датчики”, принцип действия которых основан на преобразовании случайных шумов, так и вычислительные алгоритмы, по которым сама машина вычисляет так называемые “псевдослучайные” числа. Один из самых простых алгоритмов вычисления псевдослучайных чисел состоит в следующем. Берут два произвольных n-значных числа a1 и a2 и перемножают их, и в полученном результате берут n средних знаков. Так получают число а3. Затем перемножают а2 и а3 и в полученном результате берут n средних чисел, получая число а4,и т.д. Полученные таким образом числа рассматриваются как последовательность двоичных дробей с n знаками после запятой. Такая последовательность дробей практически ведет себя как ряд случайных чисел R от 0 до 1.
В заключение изложения матричных игр отметим, что хотя само понятие смешанной стратегии требует многократного повторения партий игры, полученные результаты справедливы и к играм, которые играются только один раз, поскольку все изложения теории были выведены применительно к одной партии игры.
Качественно аргументировать этот тезис можно следующим образом: очевидно, что если противник узнает, какую мы выбрали стратегию, то предпримет ход, который будет иметь для нас наихудшие последствия. Поэтому единственным выходом является использование для выбора стратегии случайного механизма (жребия), результат которого противник не может предвидеть (хотя, конечно, ему может и повезти). Теория игр указывает характеристики (частоты применения стратегий), которыми должен обладать используемый случайный механизм.
ТЕСТЫ
(В - Верно, Н - Неверно)
Каждая матричная игра может быть представлена парой прямой и двойственной задач линейного программирования.
Преимуществом приближенного метода Брауна-Робинсона является то, что объем вычислений с увеличением размерности игры m*n растет существенно медленнее, чем в методах линейного программирования.
Теория игр не может дать результатов в тех случаях, когда элементы платежной матрицы заданы неточно (например, когда они только упорядочены).
Случайные числа выдаваемые датчиком случайных чисел, используемые для реализации оптимальных стратегий, должны быть распределены по равномерному закону.
Теория игр применима и для игр, которые играются только один раз.
Ответы: (1 - В; 2 - В; 3 - Н; 4 - В, 5- В).
ЗАДАЧИ
Решить матричные игры, имеющие платежные матрицы вида:
|
1. |
8 |
4 |
2 |
2. |
-1 |
1 |
1 |
3. |
1 |
2 |
-5 |
3 |
2 |
|
|
2 |
8 |
4 |
2 |
-2 |
2 |
-1 |
4 |
7 |
2 |
-4 |
||||
|
1 |
2 |
8 |
3 |
3 |
-3 |
5 |
-1 |
1 |
1 |
3 |
||||
|
4. |
0 |
-13 |
-1 |
5. |
1 |
0 |
-1 |
6. |
3 |
2 |
4 |
|||
|
13 |
0 |
-13 |
0 |
2 |
1 |
4 |
3 |
2 |
||||||
|
1 |
13 |
0 |
1 |
-1 |
3 |
2 |
4 |
3 |
||||||
|
7. |
3 |
6 |
0 |
8. |
3 |
0 |
7 |
9. |
203 |
403 |
103 |
|||
|
5 |
3 |
2 |
4 |
6 |
0 |
303 |
3 |
103 |
||||||
|
2 |
1 |
6 |
3 |
4 |
3 |
3 |
103 |
303 |
||||||
|
10. |
2 |
-11 |
1 |
11. |
7 |
5 |
4 |
12. |
16 |
0 |
14 |
|||
|
15 |
2 |
-11 |
1 |
3 |
7 |
6 |
6 |
16 |
||||||
|
3 |
15 |
2 |
2 |
7 |
4 |
6 |
12 |
2 |
||||||
|
13. |
0 |
1 |
1 |
14. |
-1 |
1 |
0 |
15. |
0 |
2 |
1 |
|||
|
1 |
0 |
1 |
0 |
-1 |
1 |
2 |
0 |
2 |
||||||
|
1 |
1 |
0 |
1 |
0 |
-1 |
1 |
2 |
0 |
|
18. |
1 |
6 |
2 |
5 |
19. |
6 |
0 |
1 |
2 |
20. |
4 |
3 |
3 |
2 |
2 |
6 |
|
|
5 |
1 |
6 |
2 |
0 |
3 |
1 |
0 |
6 |
0 |
4 |
2 |
6 |
2 |
||||
|
2 |
5 |
1 |
6 |
2 |
0 |
3 |
1 |
0 |
7 |
3 |
6 |
2 |
2 |
||||
|
21. |
0 |
-13 |
-3 |
22. |
9 |
6 |
12 |
23. |
2 |
7 |
3 |
6 |
|||||
|
13 |
0 |
-13 |
12 |
9 |
6 |
6 |
2 |
7 |
3 |
||||||||
|
1 |
13 |
0 |
6 |
12 |
9 |
3 |
6 |
2 |
7 |
||||||||
|
24. |
12 |
0 |
2 |
4 |
25. |
6 |
-10 |
4 |
26. |
104 |
304 |
4 |
|||||
|
0 |
6 |
2 |
0 |
-4 |
-4 |
6 |
204 |
-96 |
4 |
||||||||
|
4 |
0 |
6 |
2 |
-4 |
2 |
-8 |
-96 |
4 |
204 |
||||||||
|
27. |
3 |
1 |
4 |
1 |
6 |
28. |
2 |
3 |
1 |
4 |
29. |
-1 |
-2 |
-3 |
|||
|
6 |
3 |
1 |
4 |
1 |
1 |
2 |
5 |
4 |
-3 |
-1 |
-1 |
||||||
|
1 |
6 |
3 |
1 |
4 |
2 |
3 |
4 |
1 |
-1 |
-3 |
1 |
||||||
|
4 |
1 |
6 |
3 |
1 |
4 |
2 |
2 |
2 |
|||||||||
|
1 |
4 |
1 |
6 |
3 |
|||||||||||||
|
30. |
1/7 |
2/7 |
3/7 |
||||||||||||||
|
3/7 |
1/7 |
1/7 |
|||||||||||||||
|
1/7 |
3/7 |
1/7 |
3. ПОЗИЦИОННЫЕ ИГРЫ
3.1 Общие сведения
В общих играх число игроков может быть больше двух, некоторые ходы возможно являются случайными, игроки могут иметь по несколько ходов, причем информация о прошедшем может меняться от хода к ходу. Такие игры называются позиционными или играми в развернутой форме.
Пример. Выборы с правом вето.
Пусть три игрока (N=3) выбирают одного из четырех (G=4) кандидатов в президенты. Правило выбора таково: начиная с первого игрока, каждый игрок налагает вето на выбор одного из неотведенных кандидатов. Единственный оставшийся кандидат считается избранным. Функции выигрышей Ui для каждого из игроков в зависимости от выбранного в президенты кандидата имеют вид:
В развернутой форме данная игра может быть представлена в виде следующего дерева игры (рис. 3.1.), где около ветвей поставлены номера отводимых кандидатов, а у конечных вершин - номера победивших кандидатов. Если победил, например, кандидат под номером 4, то выигрыш первого игрока будет равен 7, а для второго и третьего игроков - 4.
Позиционные игры должны включать следующие элементы описания:
последовательность личных и случайных ходов игроков;
выборы, которые могут делать игроки при каждом личном ходе;
Рис.3.1
исходы случайных ходов и распределение вероятностей этих исходов;
информацию, доступную игрокам при выполнении личного или случайного хода;
правила окончания игры и подсчеты выигрыша игроков.
Число ходов в данной игре не фиксируется. В общем случае, оно зависит от последовательности выборов, исходов. Однако, правила должны гарантировать, что игра в конце концов закончится.
Относительно ходов правила игры имеют следующую структуру. Для первого хода правила указывают его вид. Если это личный ход, то правила перечисляют возможные варианты и указывают игрока, который делает выбор. Если это случайный ход, то перечисляются возможные варианты и обуславливаются вероятности их выбора.
Для последующих ходов правила определяют в зависимости от выбора и исходов предыдущих (-1) ходов, будет ли -й ход личным или случайным. Если ход личный, то перечисляются возможные варианты игрока, который будет делать выбор, и определяется информация о выборах и исходах при первых (-1) ходах, которой располагает игрок к моменту своего выбора.
Если ход случайный, то перечисляются возможные варианты и вероятности их выбора. Правила, наконец, определяют в зависимости от выборов и исходов в последовательности ходов, когда игра должна закончиться и выигрыш каждого из игроков.
3.2 Задание позиционной игры в виде дерева
Позиционные игры удобно задавать графически в виде дерева игры (рис.3.2.). Дерево состоит из вершин, соединенных между собой ветвями. Вершины дерева называют еще позициями игры, а его ветви - ходами игрока.
Рис.3.2
Основными свойствами дерева игры являются:
дерево содержит одну единственную начальную вершину (“корень” дерева), в которую не входит ни одна ветвь;
дерево имеет не менее одной вершины, из которой не выходит ни одна ветвь. Эти вершины называются конечными вершинами;
из корня дерева имеется единственный путь к каждой из остальных вершин дерева.
Вершина соответствует определенному состоянию игры перед очередным ходом. Каждую вершину занимает только один игрок, и ей присваивается номер, равный номеру игрока, который делает выбор.
Вершины, соответствующие случайным ходам, обозначают номером 0. Ветви, выходящие из вершины, изображают выборы, которые могут быть сделаны игроком при данном ходе. Вероятности выполнения случайного хода записывают у соответствующих ветвей. Возле конечных вершин дерева указываются исходы игры - значения выигрыша игроков (а в антагонистических играх - выигрыш первого игрока).
Партия начинается с корня (нижней вершины). Каждый ход есть изменение позиции, соответствующее перемещению из одной вершины на какую-нибудь из примыкающих верхних вершин. Число ветвей у вершины равно числу вариантов хода. Партия заканчивается при достижении одной из конечных вершин. Величина называется длиной дерева.
В зависимости от выбора игроков возможно столько различных партий игры, сколько конечных вершин у дерева.
Очевидно, если в игре нет случайных ходов, и каждый из игроков выбрал свою стратегию, то исход игры однозначно определен. Для игры со случайными ходами, результат партии становится случайной величиной, поэтому необходимо случайные выигрыши заменить их математическими ожиданиями. Как совокупность всех решений, которые должен принять игрок, можно описать как одно решение - выбор стратегии, так и совокупность случайных ходов, может быть заменена одним случайным испытанием Н.
В рассматриваемом примере (рис.3.2) случайное испытание Н может иметь следующие исходы:
Н=|(Г,3),(Г,2),(Р,3),(Р,2)|, с вероятностями , где Г - означает выпадение “герба”, Р - “решки”, а цифры 2, 3 соответствуют случайному выбору на четвертом ходу.
Игра, полученная путем усреднения случайных исходов, не полностью эквивалентна исходной игре, так как она характеризует не частный результат отдельной партии, а средние исходы большого числа партий.
Информация, доступная игрокам задается информационным разбиением вершин на множества Vi, называемые классами информации или информационными множествами. Если достигнута вершина vVi, то игроку, который должен ходить, указывается только класс информации, а не точное положение вершины v. Таким образом, в классы информации могут входить несколько вершин, неразличимых игроком, делающим выбор на данном ходе, т.е. игрок не в состоянии различить, какой из нескольких вершин соответствует состояние игры в данный момент времени.
В рассматриваемом примере класс информации V1 состоит из двух вершин. В том случае, когда всякий класс информации содержит только одну вершину, имеем игру с полной информацией (например, игра в шахматы). В играх с неполной информацией содержится хотя бы один класс информации с числом вершин не менее двух.
При вычерчивании дерева игры классы информации обводят замкнутой линией.
Игрок всегда знает, какому классу информации соответствует состояние игры в данный момент, но не знает конкретной вершины этого класса.
Классы информации (информационные множества) должны удовлетворять следующим условиям:
содержать вершины только одного игрока;
каждая вершина может принадлежать только одному классу информации;
вершины класса информации соответствуют только одному временному ходу;
из всех вершин, составляющих класс информации, может выходить только одинаковое количество ветвей.
Дерево, изображенное на рис.3.2., соответствует следующей игре:
Первый игрок выбирает одно из двух направлений (“налево” или “направо”). Ход “налево” оценивается тремя баллами, а “направо” - четырьмя. Затем бросается жребий (монета) и, если выпадает герб, второму игроку сообщается предыдущий выбор первого игрока. Если выпадает решка, то второй игрок знает лишь, что он находится в классе информации V1, но не знает, в какой из двух вершин этого класса он находится.
Второй игрок выбирает одно из двух направлений (“налево” или “направо”). Ход “налево” оценивается пятью баллами, а “направо” - двумя. Четвертый ход является опять случайным и состоит в выборе с равными вероятностями одного из направлений: “налево”, “направо”, которые оцениваются тремя и двумя баллами соответственно. Поскольку вероятности выбора направления при случайном ходе одинаковы (равны ), то их можно на графическом изображении дерева игры и не указывать.
Числа, выбранные в первом, третьем и четвертом ходах, складываются, и полученная сумма уплачивается вторым игроком первому, если она четная, в противном случае первый игрок платит второму.
Пространства Ф1 и Ф2 всех возможных стратегий игроков 1 и 2 в рассматриваемом примере следующие:
Ф1=|(3), (4)|;
Ф2=|(3,Г,5),(3,Г,2),(3,Р,5),(3,Р,2),(4,Г,5),(4,Г,2),(4,Р,5),(4,Р,2)|,
где первое число каждой стратегии в пространстве Ф2 соответствует выбору первого игрока, второе число - выпаданию герба или решки (“Г” - выпал “герб”; “Р” - выпала “решка”). Третья - выбору второго игрока пятерки или двойки.
Очевидно, что если в игре нет случайных ходов и каждый из игроков выбрал свою стратегию, то исход игры однозначно определен.
Описание позиционной игры в виде дерева позволяет глубже проанализировать ход игры. Вместе с тем, оптимальное поведение игроков легче определить для игры, заданной в нормальной форме (для двух игроков - в матричной форме), особенно в том случае, если игра содержит информационные множества и случайные ходы.
3.3 Решение позиционной игры с полной информацией
Решение позиционной игры с полной информацией легко решается в соответствии с теоремой Куна, утверждающей, что данная игра разрешима по доминированию, т.е. для каждого из игроков имеются доминирующие стратегии, которые и необходимо применять.
Для того, чтобы это продемонстрировать, рассмотрим описанную выше игру «Выборы с правом вето». Поскольку из всех вершин, предшествующих конечным, ходит игрок 3, то остальные игроки, зная его функцию выигрыша U3, могут легко предвидеть его решения. Это позволяет привести игру, изображенную на рис.3.1 к следующей:
Рис.3.3
Поскольку в новом дереве игрок 3 уже по существу не принимает решения, то финальная вершина определяется ходами игрока 2. Игрок 1, зная функцию выигрышей U2, может предвидеть поведение игрока 2. В итоге получается игра с одним участником - первым игроком и следующим деревом игры:
Рис.3.4
Поскольку для первого игрока желательна победа четвертого претендента, то он отклонит третьего претендента. Далее второй игрок вынужден будет отклонить второго претендента, а третий игрок - первого. Выигрыши игроков в данной игре равны 7, 4 и 4 соответственно.
Таким образом алгоритм решения позиционных игр с полной информацией, в соответствии с теоремой Куна, состоит в том, что начиная с последнего хода последовательно отбрасываются заведомо худшие для игрока, делающего этот ход, решения. После всех таких редукций получаем решение в чистых стратегиях.
3.4 Нормализация позиционной игры
Процесс сведения позиционной игры к игре в нормальной форме называют нормализацией игры. Любая позиционная игра может быть сведена к игре в нормальной форме, в которой каждый из игроков делает только по одному независимому ходу. Для нормализации игры нужно перечислить все возможные стратегии игроков и для каждой совокупности стратегий определить выигрыш игроков. Рассмотрим процесс нормализации позиционной игры на конкретном примере. Пусть игра задана деревом, показанном на рис.3.5.
Рис. 3.5
Первый игрок делает свой первый ход, выбирая правую или левую ветвь. Затем ход делает второй игрок, у которого в каждой вершине также имеется два выбора, после чего игра заканчивается.
В данной игре у первого игрока (игрока А) имеется две чистых стратегии: Ф1=/А1, А2/, где стратегия А1 - всегда выбирать левую ветвь; стратегия А2 - всегда выбирать правую ветвь. Второй игрок (игрок В) имеет больше стратегий:
Ф2=/В1,В2,В3,В4/,
где стратегия В1 - всегда выбирать левую ветвь;
стратегия В2 - всегда выбирать правую ветвь;
стратегия В3 - выбирать ветвь, которую выбрал игрок А;
стратегия В4 - выбирать ветвь, противоположную той, которую выбрал игрок А.
Матрица игры в этом случае имеет вид:
|
Bj |
|||||
|
Ai |
B1 |
B2 |
B3 |
B4 |
|
|
A1 |
4 |
-2 |
4 |
-2 |
|
|
A2 |
-2 |
3 |
3 |
-2 |
Очевидно, что исходная позиционная игра является игрой с полной информацией. Следовательно, она должна иметь седловую точку, а, следовательно, решение в чистых стратегиях.
Действительно, так как
;
.
и, следовательно, .
Поэтому SA=||1,0|| или SA=||0,1||, а SB=||0,0,0,1||. Цена игры v=-2.
Допустим, что в рассматриваемом примере второму игроку не сообщается выбор, сделанный первым игроком. Тогда в дереве игры на втором ходе появляется класс информации V1, содержащей две вершины второго игрока (рис.3.6)
Рис. 3.6
Количество чистых стратегий второго игрока по сравнению с первым случаем сократится до двух: Ф2=/В1,В2/,
где В1 - всегда выбирать левую ветвь;
В2 - всегда выбирать правую ветвь.
Процесс нормализации приводит к следующей платежной матрице:
|
Bj |
|||
|
Ai |
B1 |
B2 |
|
|
A1 |
4 |
-2 |
|
|
A2 |
-2 |
3 |
В новой игре №, т.е. седловая точка отсутствует. Решение игры в смешанных стратегиях имеет вид:
.
Уменьшение информации, имеющейся у второго игрока на момент принятия решения, привело к уменьшению его выигрыша с 2 до .
Итак для нормализации позиционной игры необходимо:
перечислить все возможные стратегии каждого из игроков (в таких играх, как шахматы, это пока неразрешимая задача);
определить исходы игры при всех возможных сочетаниях стратегий игроков (выборы стратегий делаются игроками одновременно и независимо).
В зависимости от количества игроков, а также значений их выигрышей путем нормализации позиционные игры можно свести к матричной или бескоалиционной, в частности, биматричной игре, каждые из которых решаются по-своему.
ТЕСТЫ
(В - Верно, Н - Неверно)
В позиционных играх каждый из игроков может делать по несколько ходов, причем информация о прошедшем может меняться от хода к ходу.
Позиционные игры не могут включать случайные ходы.
Дерево позиционной игры имеет не более одного корня и не менее одной вершины.
Из корня дерева позиционной игры к какой-нибудь его вершине могут быть несколько путей.
Если все классы информации позиционной игры содержат только по одной вершине, то такая игра является игрой с неполной информацией.
Классы информации должны содержать вершины только одного игрока.
Вершины класса информации могут соответствовать различным временным ходам.
Из всех вершин, составляющих класс информации, может выходить только одинаковое количество ветвей.
Любая позиционная игра может быть сведена к игре в нормальной форме.
Игры с полной информацией имеют седловую точку и решаются в чистых стратегиях.
Теорема Куна утверждает, что позиционная игра с полной информацией разрешима по доминированию.
Для нормализации позиционной игры необходимо перечислить все возможные стратегии каждого из игроков и определить все возможные исходы игры.
(Ответы: 1-В; 2-Н; 3-В; 4-Н; 5-Н; 6-В; 7-Н; 8-В; 9-В; 10-В; 11-В; 12-В.)
ЗАДАЧИ
І. Произвести нормализацию позиционных игр, у которых дерево игры имеет вид, приведенный ниже. У конечных вершин поставлен выигрыш первого игрока, а выигрыш второго игрока противоположен по знаку.
Варианты:
1.
2.
3.
4.
2. Нарисовать дерево следующей позиционной игры «Выбор с правом вето», у которой N игроков выбирают одного кандидата из множества , i N. Правило голосования таково: начиная с игрока 1, каждый игрок последовательно налагает вето на выбор кандидатуры одного из не отведенных кандидатов. Единственный оставшийся кандидат считается избранным. Заданы также функции выигрыша u1, u2, …, uN на множестве С, т.е. выигрыш каждого игрока в зависимости от того, какой кандидат победил. Найти решение, используя теорему Куна.
Варианты:
1. N =2;
u1={2,-5,4}; u2={-2,5,-4}
2. N =2;
u1={2,5,-4,-3,1}; u2={-2-3,4,3,-1}
3. N =3;
u1={1,2,-3,4}; u2={3,2,1,-5}; u3={-2,-3,-1,8}.
4. N =4;
u1={1,2,-2,-3,4}; u2={3,5,1,-7,6}; u3={2,4,-5,-1,1}; u4={2,3,4,1,6}.
4. БЕСКОНЕЧНЫЕ АНТАГОНИСТИЧЕСКИЕ ИГРЫ
4.1 Общие сведения
Если множество чистых стратегий хотя бы одного из игроков бесконечно, то игры называются бесконечными. Различие между конечными и бесконечными антагонистическими играми приводит к необходимости применять для исследования бесконечных игр более сложный математический аппарат, заменять линейно - алгебраические уравнения функционально - аналитическими, интегральными уравнениями, которые в благоприятных случаях сводятся к системам дифференциальных уравнений. Но, как и во всякой антагонистической игре, в бесконечной антагонистической игре принципом оптимального поведения игроков остается принцип «максимина».
Обозначим через Х и У - произвольные множества, элементы которых являются соответственно стратегиями игроков 1 и 2, а через Н(х, у) - функцию выигрыша игрока 1 в ситуации (х, у). Далее будем считать, что функция Н(х, у) непрерывна на пространстве ситуаций Х*Y и ограничена.
Принцип “максимина” может быть реализован тогда и только тогда, когда существуют и равны смешанные экстремумы:
max inf H(x,y) и min sup H(x,y).
xX; yY yY; xX
Для бесконечных антагонистических игр, в отличие от конечных, существование оптимальных смешанных стратегий не обязательно имеет место.
Пусть, например, X и Y принадлежат (0, 1), а функция выигрыша Н(х,у) = х + у. Очевидно, что если бы 1 и 0 входили в число возможных стратегий игроков, то ситуация (1, 0) соответствовала бы седловой точке. Поскольку эту ситуацию реализовать нельзя, то в описываемой игре можно говорить об оптимальности стратегии игроков «с точностью до произвольного ».
Определение 1. Ситуация в бесконечной антагонистической игре называется ситуацией - равновесия, если для любых стратегий х, у соответственно игроков 1 и 2 имеет место неравенство:
.
Точка , для которой выполняется это соотношение, называется - седловой точкой функции Н.
Определение 2. Стратегии и , составляющие ситуацию - равновесия в бесконечной антагонистической игре, называются - оптимальными стратегиями.
Этот термин отражает тот факт, что такие стратегии являются оптимальными “с точностью до ”. Именно, если отклонение от оптимальной стратегии никакой пользы игроку принести не может, то его отклонение от - оптимальной стратегии может увеличить его выигрыш, но не более чем на .
Теорема 1. Если при всяком , функция Н(х, у) имеет - седловые точки, то
.
Экстремумы и называются соответственно нижним и верхним значениями бесконечной антагонистической игры.
Как и в случае конечных игр, при отсутствии решения в чистых стратегиях, необходимо расширение стратегических возможностей игроков - введение смешанных стратегий.
Смешанными стратегиями в бесконечной антагонистической игре являются вероятностные распределения S(x) и S(y) на множествах их чистых стратегий Х и У. Пара таких вероятностных распределений является статистически независимыми.
Если и - смешанные стратегии игроков 1 и 2, то выигрыши Н(Х,у), Н(х,Y) и H(X,Y) являются по определению математическими ожиданиями:
Для смешанных стратегий в бесконечных антагонистических играх можно доказать теоремы, аналогичные тем, которые справедливы для смешанных стратегий в матричных играх. Покажем методику решения бесконечных антагонистических игр на отдельных примерах для наиболее простого случая - игр на единичном квадрате.
4.2 Решение выпуклых игр на единичном квадрате
Определение 3. Класс антагонистических игр, в которых х,у О [0,1] называются играми на единичном квадрате.
В играх на единичном квадрате любая ситуация (х,у) понимается как точка единичного квадрата.
Определение 4. Бесконечная антагонистическая игра на единичном квадрате называется строго выпуклой, если ее функция выигрыша Н(х,у) строго выпукла по у при любом х.
Решение выпуклых игр на единичном квадрате базируется на следующих основных теоремах [2].
Теорема 2. В строго выпуклой игре игрок 2 имеет единственную оптимальную стратегию у*, которая является чистой и является решением уравнения
, где - цена игры.
Теорема 3. Пусть в выпуклой бесконечной антагонистической игре на единичном квадрате с функцией Н(х,у) дифференцируемой по у при любом х, у* - оптимальная чистая стратегия игрока 2, а - цена игры. Тогда:
если у* = 1, то среди оптимальных стратегий игрока 1 имеется чистая стратегия , для которой y(,у) Ј 0;
если у* = 0, то среди оптимальных стратегий игрока 1 имеется чистая стратегия , для которой y(,у) і 0;
Подобные документы
Математическое программирование. Линейное программирование. Задачи линейного программирования. Графический метод решения задачи линейного программирования. Экономическая постановка задачи линейного программирования. Построение математической модели.
курсовая работа [581,5 K], добавлен 13.10.2008Теоретическая основа линейного программирования. Задачи линейного программирования, методы решения. Анализ оптимального решения. Решение одноиндексной задачи линейного программирования. Постановка задачи и ввод данных. Построение модели и этапы решения.
курсовая работа [132,0 K], добавлен 09.12.2008Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.
курсовая работа [1,1 M], добавлен 21.03.2012Применение методов линейного программирования для решения оптимизационных задач. Основные понятия линейного программирования, свойства транспортной задачи и теоремы, применяемые для ее решения. Построение первичного опорного плана и системы потенциалов.
курсовая работа [280,8 K], добавлен 17.11.2011Постановка задач линейного программирования. Примеры экономических задач, сводящихся к задачам линейного программирования. Допустимые и оптимальные решения. Алгоритм Флойда — алгоритм для нахождения кратчайших путей между любыми двумя узлами сети.
контрольная работа [691,8 K], добавлен 08.09.2010Общее понятие и характеристика задачи линейного программирования. Решение транспортной задачи с помощью программы MS Excel. Рекомендации по решению задач оптимизации с помощью надстройки "Поиск решения". Двойственная задача линейного программирования.
дипломная работа [2,4 M], добавлен 20.11.2010Понятие арифметического точечного пространства. Различные виды плоскостей в пространстве. Общая задача оптимизации. Геометрия задачи линейного программирования. Графический метод решения задачи линейного программирования при малом количестве переменных.
курсовая работа [756,9 K], добавлен 29.05.2014Методы решения задач линейного программирования: планирования производства, составления рациона, задачи о раскрое материалов и транспортной. Разработка экономико-математической модели и решение задачи с использованием компьютерного моделирования.
курсовая работа [607,2 K], добавлен 13.03.2015Оптимизационная задача линейного программирования. Виды задач линейного программирования. Принятие решений на основе количественной информации об относительной важности критериев. Выбор средств разработки. Программный комплекс векторной оптимизации.
дипломная работа [1,3 M], добавлен 27.03.2013Критерий эффективности и функции в системе ограничений. Общая постановка задачи линейного программирования. Составление математической модели задачи. Алгоритмы решения задачи симплексным методом. Построение начального опорного решения методом Гаусса.
курсовая работа [232,4 K], добавлен 01.06.2009
