Теория Игр: Матричные Игры

Автор работы: Пользователь скрыл имя, 19 Апреля 2013 в 14:14, курсовая работа

Краткое описание

Теория игр — это математическая теория конфликтных ситуаций, т.е. таких ситуаций, в которых сталкиваются интересы двух или более сторон, преследующих различные цели.
Игра — это конфликтная ситуация, регламентированная определенными правилами, в
которых должны быть указаны:
• возможные варианты действий участников
• количественный результат игры или платеж (выигрыш, проигрыш), к которому при-
водит данная совокупность ходов
• объем информации каждой стороны о поведении другой.
Парная игра — игра в которой участвуют только две стороны (два игрока).
Парная игра c нулевой суммой — парная игра, в которой сумма платежей равна нулю,
т.е. проигрыш одного игрока равен выигрышу второго.
В зависимости от отношения каждого из игроков к значению функции выигрыша парные
игры подразделяются:
• Парная игра c нулевой суммой (антагонистическая) — парная игра, в которой сум-
ма платежей равна нулю, т.е. проигрыш одного игрока равен выигрышу второго.
• Неантагонистическая игра — парная игра,в которой игроки преследуют разные,
но не прямо противоположные цели.
2

Содержание

Общие сведения 2
1.1 Игры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Ходы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Стратегии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Матричная игра . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Следовая точка. Чистые стратегии 7
2.1 Примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Пример 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Пример 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3 Смешанные стратегии 9
3.1 Игра 2×2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.1.1 Примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Пример 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Пример 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.1.2 Геометрическая интерпретация . . . . . . . . . . . . . . . . . . . . 12
3.2 Игры 2×n и m×2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Пример 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1

Прикрепленные файлы: 1 файл

nikitin_i_k_metodichka_po_teorii_igr_matrichnye_igry.pdf

— 203.99 Кб (Скачать документ)
Page 1
Содержание
1 Общие сведения
2
1.1 Игры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.2 Ходы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.3 Стратегии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.4 Матричная игра . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2 Следовая точка. Чистые стратегии
7
2.1 Примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
Пример 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
Пример 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
3 Смешанные стратегии
9
3.1 Игра 2×2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.1.1 Примеры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Пример 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Пример 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.1.2 Геометрическая интерпретация . . . . . . . . . . . . . . . . . . . . 12
3.2 Игры 2×n и m×2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Пример 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1

Page 2

1. Общие сведения из теории игр
1.1. Игры
Теория игр — это математическая теория конфликтных ситуаций, т.е. таких ситуаций, в
которых сталкиваются интересы двух или более сторон, преследующих различные цели.
Игра — это конфликтная ситуация, регламентированная определенными правилами, в
которых должны быть указаны:
• возможные варианты действий участников
• количественный результат игры или платеж (выигрыш, проигрыш), к которому при-
водит данная совокупность ходов
• объем информации каждой стороны о поведении другой.
Парная игра — игра в которой участвуют только две стороны (два игрока).
Парная игра c нулевой суммой — парная игра, в которой сумма платежей равна нулю,
т.е. проигрыш одного игрока равен выигрышу второго.
В зависимости от отношения каждого из игроков к значению функции выигрыша парные
игры подразделяются:
• Парная игра c нулевой суммой (антагонистическая) — парнаяигра,вкоторойсум-
ма платежей равна нулю, т.е. проигрыш одного игрока равен выигрышу второго.
• Неантагонистическая игра — парная игра,в которой игроки преследуют разные,
но не прямо противоположные цели.
2

Page 3

1.2. Ходы
Ход —
• выбор одного из предусмотренных правилами игры действий
• осуществление этого выбора
Ходы бывают двух типов:
• Личный ход —
+ сознательный выбор одного из предусмотренных правилами игры действий
+ осуществление этого выбора
• Случайный ход — Случайным ходом называется выбор из ряда возможностей,
осуществляемый не решением игрока, а каким-либо механизмом случайного вы-
бора.
Ниже рассматриваются парные игры с нулевой суммой, содержащие только личные ходы.
У каждой стороны отсутствует информация о поведении другой.
3

Page 4

1.3. Стратегии
Стратегия игрока — совокупность правил, определяющих выбор действий при каждом
личном ходе этого игрока в зависимости от ситуации, сложившейся в процессе игры.
В зависимости от числа возможных стратегий игры делятся на конечные и бесконечные.
• Бесконечная игра — игра, в которой хотя бы у одного одного из игроков имеется
бесконечное число стратегий.
• Конечная игра —игра,вкоторойукаждогоигрокаимеетсятолькоконечноечисло-
стратегий. Число последовательных ходов у любого из игроков определяет под-
разделение игр на одноходовые и многоходовые, или позиционные.
+ В одноходовой игре каждый игрок делает только один выбор из возможных
вариантов и после этого устанавливает исход игры.
+ Многоходовая, или позиционная , игра развивается во времени, представляя
собой ряд последовательных этапов, каждый из которых наступает после хода
одного из игроков и соответствующего изменения обстановки.
В одноходовой игре каждый игрок делает только один выбор из возможных вариантов и
после этого устанавливает исход игры.
Оптимальная стратегия игрока — стратегия, которая при многократном повторении иг-
ры обеспечивает данному игроку максимально возможный средний выигрыш (или, что то
же, минимально возможный средний проигрыш).
В теории игр все рекомендации вырабатываются исходя из предположения
о разумном поведении игроков. Просчеты и ошибки игроков, неизбежные в
каждой конфликтной ситуации, а также элементы азарта и риска в теории игр
не учитываются.
4

Page 5

1.4. Матричная игра
Матричная игра — одноходовая конечная игра с нулевой суммой.Матричная игра явля-
ется теоретико-игровой моделью конфликтной ситуации, в которой противники для до-
стижения диаметрально противоположных целей делают по одному выбору (ходу) из ко-
нечного числа возможных способов действий.В соответствии с выбранными способами
действий (стратегиями) определяется достигаемый результат. Рассмотрим на примере.
Пусть имеются два игрока A и B, один из которых может выбрать i-ю стратегию из m
своих возможных стратегий A
1
,A
2
,...A
m
, а второй выбирает j-ю стратегию из своих воз-
можных стратегий B
1
,B
2
,...B
m
. В результате первый игрок выигрывает величину a
ij
, а
второй проигрывает эту величину. Из чисел a
ij
, составим матрицу
A = (a
ij
) =





a
11
a
11
··· a
1n
a
21
a
22
··· a
2n
.
.
.
.
.
.
.
.
.
.
.
.
a
m1
a
m2
··· a
mn





Матрица A = (a
ij
),i = 1,m,j = 1,n называется платежной матрицей или матрицей
игры m × n.
В этой матрице строки всегда для стратегий выигрывающего (максимизирующего) иг-
рока A, то есть игрока, который стремится к максимизации своего выигрыша. Столбцы
отводятся для стратегий проигрывающего игрока B, то есть игрока, который стремится
к минимизации критерия эффективности.
Нормализация игры — процесс сведения позиционной игры к матричной
игре Игрой в нормальной форме — позиционная игра, сведенная к матрич-
нойигре Напомним,что,позиционнаямногоходоваяиграявляетсятеоретико-
игровой моделью конфликтной ситуации, в которой противники для дости-
жения своих целей последовательно делают по одному выбору (ходу) из ко-
нечного числа возможных способов действий на каждом этапе развития этой
ситуации.
Решение игры — нахождение оптимальных стратегий обоих игроков и определение це-
ны игры
Цена игры — ожидаемый выигрыш (проигрыш) игроков.
Решение игры может быть найдено либо в чистых стратегиях — когда игрок должен
следовать одной единственной стратегии, либо в смешанных , когда игрок должен c
определенными вероятностями применять две чистые стратегии или более. Последние в
этом случае называются активными .
5

Page 6

Смешанная стратегия одного игрока — вектор, каждая из компонент которого показы-
вает частоту использования игроком соответствующей чистой стратегии.
Максимин или нижняя цена игры — число
α = max
i
min
j
a
ij
Максиминная стратегия (строка) — стратегия, которую выбрал игрок, чтобы максими-
зировать свой минимальный выигрыш.
Очевидно, что при выборе наиболее осторожной максиминной стратегии игрок A обеспе-
чивает себе (независимо от поведения противника) гарантированный выигрыш не менее
α.
Максимин или верхняя цена игры — число
β = min
j
max
i
a
ij
Минимаксная стратегия (столбец) — стратегия, которую выбрал игрок, чтобы миними-
зировать свой максимальный проигрыш.
Очевидно, что при выборе наиболее осторожной минимаксной стратегии игрок B не дает
возможности ни при каких обстоятельствах игроку A выиграть больше, чем β.
Нижняя цена игры всегда не превосходит верхней цены игры
α = max
i
min
j
a
ij
⩽ min
j
max
i
a
ij
= β
Теоремма 1 (основная теорема теории матричных игр). Каждая конечная игра имеет по
крайней мере одно решение, возможно, в области смешанных стратегий.
6

Page 7

2. Игры с седловой точкой. Решение в чистых стратегиях
Игра с седловой точкой — игра, для которой
α = max
i
min
j
a
ij
= min
j
max
i
a
ij
= β
Для игр с седловой точкой нахождение решения состоит в выборе максиминной и мини-
макcной стратегий, которые являются оптимальными.,
Чистая цена игры — общее значение нижней и верхней цены игры
α = β = ν
2.1. Примеры
Пример 1
Найти решение в чистых стратегиях игры, заданной матрицей
A =


8 4 7
6 5 9
7 7 8


Решение: определим верхнюю и нижнюю цену игры. Для этого найдем минимальное из
чисел a
ij
в i-й строке
α
i
= min
j
a
ij
и максимальное из чисел a
ij
в j-м столбце
β
j
= max
i
a
ij
Числа α
i
(минимумы строк) выпишем рядом с платежной матрицей справа в виде доба-
вочного столбца. Числа β
i
(максимумы столбцов) выпишем под матрицей в виде доба-
вочной строки:
α
i
8 4 7 4
6 5 9 5
7 7 8 7
β
j
8 7 9
7

Page 8

Находим максимальное из чисел α
i
α = max
i
α
i
= 7
и минимальное из чисел β
j
β = min
j
β
j
= 7
α = β — игра имеет седловую точку. Оптимальной стратегией для игрока является стра-
тегия A
3
, а для игрока B — стратегия B
2
, чистая цена игры ν = 7
Пример 2
Задана платежная матрица:
A =




2 2 1 1 2
0 1 1 1 1
1 1 1 1 2
1 2 1 1 2




Найти решение игры в чистых стратегиях.
Решение:
2 2 1 1 2 1
0 1 1 1 1 0
1 1 1 1 2 1
1 2 1 1 2 1
β
j
2 2 1 1 2
α = β = 1. Игра имеет шесть седловых точек. Оптимальными стратегиями будут:
A
1
и B
3
или B
4
A
3
и B
3
или B
4
A
4
и B
3
или B
4
8

Page 9

3. Решение игры в смешанных стратегиях
При α ̸= β. случае, когда при выборе своих стратегий оба игрока не имеют информации
о выборе другого, игра имеет решение в смешанных стратегиях.
S
A
= (p
1
,p
2
,...,p
m
)—смешаннаястратегияигрокаA,вкоторойстратегииA
1
,A
2
,...,A
m
применяются о вероятностями
p
1
,p
2
,...,p
m
,
m

i=1
p
i
= 1, p
i
⩾ 0,i = 1,m
S
B
= (q
1
,q
2
,...,q
n
)—смешаннаястратегияигрокаB ,вкоторойстратегииB
1
,B
2
,...,B
m
применяются о вероятностями
q
1
,q
2
,...,q
m
,
n

i=1
q
i
= 1, q
i
⩾ 0,i = 1,n
Если:
S

A
— оптимальная стратегия игрока A ,
S

B
— - оптимальная стратегия игрока B ,
то цена игры —
ν =
n

j=1
m

i=1
a
ij
· p

i
· q

i
Следующая теорема дает ответ на вопрос, как найти решение для игр 2 × 2, 2 × n, m × 2
Теоремма 2 (как найти решение для игр 2 × 2, 2 × n, m × 2 ). Если один из игроков
применяет оптимальную смешанную стратегию, то его выигрыш равен цене игры ν вне
зависимости от того, с какими вероятностями будет применять второй игрок стра-
тегии, вошедшие в оптимальную (в том числе и чистые стратегии).
9

Page 10

3.1. Игра 2 × 2
Рассмотрим игру 2 × 2 о матрицей:
(
a
11
a
21
a
21
a
22
)
Пусть игра не имеет решения в чистых стратегиях. Найдем оптимальные стратегии S

A
и
S

B
. Сначала определим стратегию S

A
= (p

1
,p

2
). Согласно теореме, если сторона A бу-
дет придерживаться стратегии ν, то независимо от образа действий стороны B выигрыш
будет оставаться равным цене игры ν. Следовательно, если сторона A придерживается
оптимальной стратегии S

A
= (p

1
,p

2
), то сторона B может, не меняя выигрыша, приме-
нять любую из своих стратегий. Тогда при применении игроком B чистой стратегии B
1
или B
2
игроке получит средний выигрыш равный цене игры:
a
11
p

1
+ a
21
p

2
= ν ← при стратегии B
1
a
12
p

1
+ a
22
p

2
= ν ← при стратегии B
2
Принимая во внимание, что p

1
+ p

2
= 1:
p

1
=
a
2
2−a
2
1
a
11
+a
22
−a
12
−a
21
p

2
=
a
1
1−a
1
2
a
11
+a
22
−a
12
−a
21
Цена игры:
ν =
a
22
a
11
− a
12
a
21
a
11
+ a
22
− a
12
− a
21
Аналогично находится оптимальная стратегия игрока B: S

B
= (q

1
,q

2
).
Принимая во внимание, что q

1
+ q

2
= 1:
q

1
=
a
2
2−a
1
2
a
11
+a
22
−a
12
−a
21
q

2
=
a
1
1−a
2
1
a
11
+a
22
−a
12
−a
21
3.1.1. Примеры
Пример 3
Найти решение игры c матрицей
A =
(
1 1
1 1
)
10

Page 11

Решение: игра не имеет седловой точки, так как α= -1, β = 1, α ̸= β. Ищем решение в
смешанных стратегиях. По формулам для p

и q

получаем p

1
= p

2
= 0.5 и q

1
= q

2
= 0.5,
ν = 0 Таким образом,
S

A
= (0.5, 0.5)
S

B
= (0.5, 0.5)
Пример 4
Найти решение игры c матрицей
A =
(
2 5
6 4
)
Решение: игра не имеет седловой точки, так как α= 4, β = 5, α ̸= β. Ищем решение в
смешанных стратегиях. По формулам для p

и q

получаем p

1
= 0.4, p

2
= 0.6 и q

1
= 0.2
q

2
= 0.8, ν = 4.4 Таким образом,
S

A
= (0.4, 0.6)
S

B
= (0.2, 0.8)
11

Page 12

3.1.2. Геометрическая интерпретация
Игре 2 × 2 можно дать простую геометрическую интерпретацию. Возьмем единичный
участок оси абсцисс, каждой точке которого поставим в соответствие некоторую сме-
шанную стратегию S = (p
1
,p
2
) = (p
1
, 1 − p
1
) причем вероятность p
1
стратегии A
1
будет
равна расстоянию от точки S
A
до правого конца участка, а вероятность p
2
, стратегии A
2
— расстоянию до левого конца.
.
.y
.x
.P

2
.S

A
.P

1
.B
1
.B

1
.a
11
.a
21
.N
.I
.I
.II
.II
В частности, левый конец участка (точка с абсциссой = 0) отвечает стратегии A
1
, правый
конец участка (x = 1) — стратегии A
2
На концах участка восстанавливаются два перпендикуляра к оси абсцисс:
• ось I − I — откладывается выигрыш при стратегии A
1
• ось II − II — откладывается выигрыш при стратегии A
2
Пусть игрок B применяет стратегию B
1
; она дает на осях I − I и II − II соответственно
точки с ординатами a
11
и a
21
. Проводим через эти точки прямую B
1
− B

1
. При любой
смешанной стратегии S
A
= (p
1
,p
2
) выигрыш игрока определяется точкой N на прямой
B
1
−B

1
, соответствующей точке S
A
на оси абсцисс, делящей отрезок в отношении p
2
: p
1
.
Очевидно, точно таким же способом может быть построена и прямая B
2
− B

2
, определя-
ющая выигрыш при стратегии B
2
.
12

Page 13

.
.y
.x
.P

2
.S

A
.P

1
.B
2
.B

2
.a
21
.a
22
.N
.I
.I
.II
.II
Необходимо найти оптимальную стратегию S

A
, т.е. такую, при которой минимальный
выигрыш игрока A (при наихудшем для него поведении игрока B ) обращался бы в мак-
симум. Для этого строиться нижняя граница выигрыша игрока A при стратегиях B
1
,B
2
,
т.е. ломаная B
1
NB

2
;. На этой границе будет лежать минимальный выигрыш игрока A при
любой его смешанной стратегии, точка N, в которой этот выигрыш достигает максимума
и определяет решение и цену игры.
.
.y
.x
.P

2
.S

A
.P

1
.B
2
.B

2
.B
1
.B

1
.N
.I
.I
.II
.II
Ордината точки N есть не что иное, как цена игры ν, ее абсцисса равна

2
, а расстояние
до правого конца отрезка равно

1
, т.е. расстояние от точки S

A
до концов отрезка равны
вероятностям

2
и

1
стратегий A
2
и A
1
оптимальной смешанной стратегии игрока A. в
данном случае решение игры определялось точкой пересечения стратегий B
1
и B
2
.
Ниже показан случай, когда оптимальной стратегией игрока является чистая стратегия
A
2
. Здесь стратегия A
2
(при любой стратегии противника) выгоднее стратегии A
1
,
13

Page 14

.
.y
.x
.P

2
.B
2
.B

2
.B
1
.B

1
.ν = a
21
.I
.I
.II
.II
.S

A
= A
2
.
.y
.x
.P

2
.B
2
.B

2
.B
1
.B

1
.ν = a
21
.I
.I
.II
.II
.S

A
= A
2
Правее показан случай, когда заведомо невыгодная стратегия имеется у игрока B. Гео-
метрическая интерпретация дает возможность наглядно изобразить также нижнюю цену
игры α и верхнюю β
.
.y
.x
.P

2
.S

A
.P

1
.B
2
.B

2
.B
1
.B

1
.N
.α = a
22
.β = a
21
.I
.I
.II
.II
На том же графике можно дать и геометрическую интерпретацию оптимальных страте-
гий игрока B . Нетрудно убедиться, что доля q

1
стратегии B
1
оптимальной смешанной
стратегии S

B
= (q

1
,q

2
) равна отношению длины, отрезка KB
2
к сумме длин отрезков
KB
1
и KB
2
на оси I − I:
.
.y
.x
.P

2
.S

A
.P

1
.B
2
.B

2
.B
1
.B

1
.K
.L
.N
.I
.I
.II
.II
14

Page 15

q

1
=
KB
2
KB
2
+ KB
1
или
q

1
=
LB

2
LB

2
+ LB

1
Оптимальную стратегию S

B
= (q

1
,q

2
) можно найти и другим способом, если поменять
местами игроков B и B, а вместо максимума нижней границы выигрыша рассмотреть
минимум верхней границы.
.
.y
.x
.q

2
.S

B
.q

1
.A
2
.A

2
.A
1
.A

1
.N
.I
.I
.II
.II
15

Page 16

3.2. Игры 2 × n и m × 2
Решение игр 2 × n и m × 2 основывается на следующей теореме.
Теоремма 3. У любой конечной игры m × n существует решение, в котором число ак-
тивных стратегий каждой стороны не превосходит наименьшего из чис->ел m и n.
Согласно этой теореме у игры 2 × n всегда имеется решение, в котором каждый игрок
имеет не более двух активных стратегий. Стоит только найти эти стратегии, и игра 2 × n
превращается в игру 2 × 2, которая решается элементарно. Нахождение активных стра-
тегий может выполняться графическим способом:
1) строится графическая интерпретация;
2) определяется нижняя граница выигрыша;
3) выделяются на нижней границе выигрыша две стратегии второго игрока, которым
соответствуют две прямые, пересекающиеся в точке с максимальной ординатой (ес-
ли в ней пересекаются более двух прямых, берется любая пара) — эти стратегий
представляют собой активные стратегии игрока B.
Таким образом, игра 2 × n сведена к игре 2 × 2.
Также может быть решена игра 2, с той разницей, что строится не нижняя, а верхняя
граница выигрыша и на ней ищется не максимум, а минимум.
Пример 5
Найти решение игры
A =
(
7 9 8
10 6 9
)
Решение: используя геометрический метод, выделяем активные стратегии. Прямые B
1

B

1
, B
2
− B

2
и B
3
− B

3
соответствуют стратегиям B
1
, B
2
, B
3
. Ломаная B
1
NB
2
— нижняя
граница выигрыша игрока . Игра имеет решение S∗
A
= (
2
3
,
1
3
); S∗
B
= (0.5;0.5;0); v = 8.
16

Page 17

.
.y
.x
.P

2
.S

A
.P

1
.B
1
.B

1
.B
2
.B

2
.B
3
.B

3
.N
.I
.I
.II
.II
17

Page 18

Предметный указатель
игра, 2
2 × 2, 10
2 × 2, 9
геометрия, 12
примеры, 10
2 × n, 9, 16
m × 2, 9, 16
бесконечная, 4
в нормальной форме, 5
конечная, 4
многоходовая, 4
одноходовая, 4
матричная, 5
парная, 2
c нулевой суммой, 2
антагонистическая, 2
неантагонистическая, 2
решение, 5
в смешанных стратегиях, 5, 9
в чистых стратегиях, 5
с седловой точкой, 7
цена, 5
верхняя, 6
нижняя, 6
чистая, 7
максимин, 6
матрица
игры, 5
платежная, 5
минимакс, 6
нормализация игры, 5
стратегия, 4
максиминная, 6
минимаксная, 6
оптимальная, 4
смешанная, 5
теория игр, 2
ход, 3
личный, 3
случайный, 3
чистая цена игры, 7
18

Информация о работе Теория Игр: Матричные Игры