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

Автор работы: Пользователь скрыл имя, 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

Скачать полностью (165.64 Кб) Сколько стоит заказать работу?
Прикрепленные файлы: 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.
Также может быть решена игра m×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

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