Матеша. Учебнометодическое пособие по разделу элементы теории игр

• Название: Учебнометодическое пособие по разделу элементы теории игр
• Анкор: Матеша
• Дата: 18.12.2019
• Размер: 432.03 Kb.
• Имя файла: gamestheory (1).pdf
• Тип: Учебно-методическое пособие; #100848

Сайт: www.resolventa.ru
, E-mail: [e-mail]
Сайт: www.resolventa.ru
, E-mail: [e-mail]
Доктор физико-математических наук, профессор
К. Л. САМАРОВ
МАТЕМАТИКА
Учебно-методическое пособие по разделу
ЭЛЕМЕНТЫ ТЕОРИИ ИГР
© К. Л. Самаров, 2009

Сайт: www.resolventa.ru
, E-mail: [e-mail]
Сайт: www.resolventa.ru
, E-mail: [e-mail]
2
СОДЕРЖАНИЕ
Теория игр…… ……………………...…………………………………...
3 1. Матричные игры с нулевой суммой. Платежная матрица игры.....
3 2. Нижняя и верхняя цена игры. Принцип минимакса….…………...
5 3. Игры с седловой точкой…………….. ……………………….……..
7 4. Игры без седловой точки…………………………. ………………..
8 5. Игры, повторяемые многократно. Смешанные стратегии………..
9 6. Аналитический метод решения игры типа 2 2
 .......................…..
11 7. Графический метод решения игр типа 2 n
 и
2
m ……………...
15
ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ ……………………………………….. 19
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ ………………………. 21
ЛИТЕРАТУРА ………………………………………………………………... 23

Сайт: www.resolventa.ru
, E-mail: [e-mail]
Сайт: www.resolventa.ru
, E-mail: [e-mail]
3
ЭЛЕМЕНТЫ ТЕОРИИ ИГР
1. Матричные игры с нулевой суммой. Платежная матрица игры
Во многих практических задачах возникают ситуации, когда требуется принять решение, не имея достаточной информации. Неизвестными могут быть как условия осуществления какой-либо операции, так и сознательные действия лиц, от которых зависит успех этой операции.
•
Ситуации, в которых сталкиваются интересы двух сторон и резуль- тат любой операции, осуществляемой одной из сторон, зависит от действий другой стороны, называются конфликтными.
•
Математическая модель конфликтной ситуации называется игрой, а математическая теория, помогающая принимать рациональные решения в конфликтной ситуации, − теорией игр.
•
Конфликтующие стороны называются игроками, а действия, кото- рые могут выполнять игроки, − стратегиями.
От реальной ситуации игра отличается тем, что в игре противники дей- ствуют по строго определенным правилам.
•
Матричной игрой называется игра, осуществляемая по следующим правилам:
1.
В игре участвуют два игрока;
2.
Каждый из игроков обладает конечным набором стратегий;
3.
Игра заключается в том, что каждый из игроков, не имея информа- ции о действиях противника, делает один ход (выбирает одну из своих стратегий). Результатом выбора игроками стратегий является выигрыш и проигрыш в игре.
4.
И выигрыш, и проигрыш выражаются числами.
•
Матричная игра называется игрой с нулевой суммой, если в этой иг- ре выигрыш одного игрока равняется проигрышу другого игрока.

Сайт: www.resolventa.ru
, E-mail: [e-mail]
Сайт: www.resolventa.ru
, E-mail: [e-mail]
4
Каждая матричная игра с нулевой суммой имеет платежную матрицу.
Для того чтобы построить эту матрицу, обозначим одного из игроков симво- лом A, а другого − символом B, и предположим, что
m
A
A
A
,
,
,
2 1

− стратегии, которые может применять игрок A, а
n
B
B
B
,
,
,
2 1

− стратегии, которые мо- жет применять игрок B.
•
Матричная игра, в которой у игрока A имеется
m
стратегий, а у иг- рока B −
n
стратегий, называется игрой типа
m n

Рассмотрим матрицу
11 12 1
21 22 2
1 2
n
n
mn
m
m
c
c
c
c
c
c
C
c
c
c













=
,
у которой элементы
ij
c
(
)
1,2,..., ;
1,2,...,
i
m j
n
=
=
равны выигрышам игрока A
(и проигрышам игрока B) при применении игроками стратегий
i
A и
j
B
соот- ветственно.
•
Матрица C называется платежной матрицей игры.
Пример 1.1. Игра, называемая «Открывание пальцев», заключается в следующем. Два игрока одновременно из сжатого кулака правой руки откры- вают по нескольку пальцев. Общее количество открытых пальцев является суммой выигрыша, причем, если общее количество открытых пальцев четно, то выигрывает первый игрок, если же общее количество открытых пальцев нечетно, то выигрывает второй игрок.
Составить платежную матрицу игры.
Решение. Поскольку каждый из игроков может открыть 1, 2, 3, 4 или 5 пальцев, тоу каждого из нихимеется по 5 соответствующих стратегий: стра- тегии
5 2
3 4
1
,
,
,
,
A A A A A у первого игрока, и
5 2
3 4
1
,
,
,
,
B B B B B − у второго. Таким образом, рассматриваемая игра является матричной игрой типа 5 5
 , и можно составить таблицу выигрышей, в зависимости от стратегий, применяемых игроками (Таблица 2.1.1):

Сайт: www.resolventa.ru
, E-mail: [e-mail]
Сайт: www.resolventa.ru
, E-mail: [e-mail]
5
Т а б л и ц а 1.1 5
1 2
3 4
1 2
3 4
5 2
3 4
5 6
3 4
5 6
7 4
5 6
7 8
5 6
7 8
0 6
7 8
9 10
B
B
B
B
B
A
A
A
A
A
Из таблицы 1.1 следует, что платежная матрица игры имеет вид
2 3
4 5
6 3
4 5
6 7
4 5
6 7
8 5
6 7
8 9
6 7
8 9 10
C


















=
2. Нижняя и верхняя цена игры. Принцип минимакса
Рассмотрим матричную игру типа
n
m 
с платежной матрицей
11 12 1
21 22 2
1 2
n
n
mn
m
m
c
c
c
c
c
c
C
c
c
c













=
Если игрок A выберет стратегию
i
A , то все его возможные выигрыши будут элементами i - й строки матрицы C. В наихудшем для игрока A случае, когда игрок B применяет стратегию, соответствующую минимальному элементу этой строки, выигрыш игрока A будет равен числу
1
min
ij
j n
c
 
Следовательно, для получения наибольшего выигрыша, игроку A нужно выбирать ту из стратегий, для которой число
1
min
ij
j n
c
 
максимально.
•
Число
1 1
α =max min
ij
i m
j n
c
 
 

Сайт: www.resolventa.ru
, E-mail: [e-mail]
Сайт: www.resolventa.ru
, E-mail: [e-mail]
6 называется нижней ценой игры, а стратегия игрока A, соответствующая наибольшему из чисел
1
min
ij
j n
c
 
,
называется максиминной.
Таким образом, если игрок A будет придерживаться максиминной стра- тегии, то ему гарантирован выигрыш, не меньший, чем
α
, при любом пове- дении игрока В.
Проанализируем теперь платежную матрицу с точки зрения игрока B, заинтересованного в том, чтобы игрок A выиграл, как можно меньше.
Если игрок B выберет стратегию
j
B
, то все возможные выигрыши игро- ка A будут элементами j - го столбца платежной матрицы С. В наихудшем для игрока B случае, когда игрок A применяет стратегию, соответствующую
максимальному элементу этого столбца, выигрышигрока B будет равен чис- лу
1
max
ij
i m
c
 
Следовательно, игроку B нужно выбрать такую стратегию, для которой число
1
max
ij
i m
c
 
минимально.
•
Число
1 1
β =min max
ij
i m
j n
c
 
 
называется верхней ценой игры, а стратегия игрока B, соответствующая наименьшему из чисел
1
max
ij
i m
c
 
,
называется минимаксной.
Таким образом, если игрок B применяет минимаксную стратегию, то иг- рок A не может выиграть больше, чем  .
•
Принцип осторожности, заставляющий игроков придерживаться максиминной и минимаксной стратегий соответственно, называют «Прин-
ципом минимакса», а минимаксную стратегию и максиминную стратегию называют общим термином «Минимаксные стратегии».
Пример 2.1. Найти нижнюю и верхнюю цены игры с платежной матри- цей

Сайт: www.resolventa.ru
, E-mail: [e-mail]
Сайт: www.resolventa.ru
, E-mail: [e-mail]
7 3
2 1 4
10 4
3 10 2
4 1 2
C










=
−
Решение. В каждой строке платежной матрицы найдем наименьший элемент, и запишем его справа от матрицы. В каждом столбце платежной матрицы найдем наибольший элемент, и запишем его снизу от матрицы. В результате получим таблицу
3 2 1 4
1 10 4
3 10 3
2 4 1 2
2 10 4
3 10










−
−
Нижняя цена игры


α = max 1, 3, -2 3
=
Верхняя цена игры


β = min 10, 4, 3,10 3
=
3. Игры с седловой точкой
•
Игра называется игрой с седловой точкой, если ее нижняя и верх- няя цены совпадают, то есть выполняется равенство
1 1
1 1
α =max min
=min max
β
ij
ij
i m
j n
i m
j n
c
c
 
 
 
 
=
•
Для игры с седловой точкой общее значение нижней и верхней це- ны игры
α β
V =
=
называется ценой игры.
Замечание 1.
В Примере 2.1. нижняя и верхняя цены игры совпадают и равны 3, т.е. рассмотренная игра является игрой с седловой точкой.
Замечание 2. Максиминной стратегией в Примере 2.1. является стратегия
2
A , минимаксной стратегией является стратегия
3
B .

Сайт: www.resolventa.ru
, E-mail: [e-mail]
Сайт: www.resolventa.ru
, E-mail: [e-mail]
8
Рассмотрим теперь для игры с седловой точкой такой элемент платеж-
ной матрицы
0 0
i j
c
, который соответствует минимаксным стратегиям
0
i
A и
0
j
B . Этот элемент является одновременно минимальным в своей строке и максимальным в своем столбце, и выполняются неравенства
0 0
1 1
α =max
= min
= β
ij
i j
i m
j m
V
c
c
 
 
=
Следовательно, выполняется равенство
0 0
i j
c
V
= .
•
Элемент платежной матрицы
0 0
i j
c
называется седловой точкой.
Замечание 3. В Примере.2.1. седловой точкой является элемент
23
c пла- тежной матрицы. Этот элемент равен 3 и, конечно же, совпадает с ценой иг- ры.
4. Игры без седловой точки
Рассмотрим следующий
Пример 4.1. Найти нижнюю и верхнюю цены игры с платежной матри- цей
2 0
1 3
4 2
2 1
0 5
1 5
C














−
=
−
Решение. Действуя аналогично Примеру 2.1., получаем
2 0
1 1
3 4
2 2
2 1
0 2
5 1
5 1
5 4
5














− −
−
−
Нижняя цена игры


α = max -1, 2, -2,1 2
=
Верхняя цена игры

Сайт: www.resolventa.ru
, E-mail: [e-mail]
Сайт: www.resolventa.ru
, E-mail: [e-mail]
9


β = min 5, 4, 5 4
=
Замечание 1.
В Примере 4.1. нижняя цена игры отличается от верхней цены игры, следовательно, игра является игрой без седловой точки. Макси-
минной стратегией является стратегия
2
A . Минимаксной стратегией является стратегия
2
B .
Замечание 2. Для любой игры без седловой точки выполнено неравен- ство
α < β
5. Игры, повторяемые многократно. Смешанные стратегии
Если партнеры играют только один раз, то игрокам целесообразно при- держиваться принципа минимакса, как в игре с седловой точкой, так и в игре без седловой точки.
В случае многократного повторения игры с седловой точкой игрокам также целесообразно придерживаться принципа минимакса.
Если же многократно повторяется игра без седловой точки, то посто-
янное использование минимаксных стратегий становится невыгодным.
Действительно, в игре без седловой точки элемент платежной матрицы
0 0
i j
c
, соответствующий минимаксной стратегии игрока A, не обязан быть ми- нимальным в своей строке. Следовательно, игрок B, зная о том, что игрок A в следующей игре будет использовать минимаксную стратегию
0
i
A , может выбрать стратегию, отвечающую минимальному элементу строки
0
i . В ре- зультате выигрыш игрока A уменьшится от величины
0 0
i j
c
до величины
α
Аналогично может поступить и игрок A, неожиданно применив против игро- ка B стратегию, соответствующую максимальному элементу столбца
0
j .
Более того, доказано, что при многократно повторяемой игре без седло- вой точкиигроку A, для обеспечения среднего выигрыша, большего, чем
α
,
следует чередовать свои стратегии
2 1
,
, ,
m
A A
A . Игроку B для улучшения результата также целесообразно чередовать свои стратегии
2 1
,
, ,
n
B B
B .

Сайт: www.resolventa.ru
, E-mail: [e-mail]
Сайт: www.resolventa.ru
, E-mail: [e-mail]
10
По этой причине для многократно повторяемых игр без седловой точки вводится следующее определение.
•
В играх, которые повторяются многократно, каждая из стратегий
2 1
,
, ,
m
A A
A называется чистой стратегией.
•
Стратегия игрока A, обозначаемая
1 1
m
m
A
A
A
S
p
p


=




и состоящая в том, чтобы применять чистые стратегии
2 1
,
, ,
m
A A
A , чередуя их по случайному закону с частотами
1
,
,
m
p
p , называется смешанной
стратегией. Частоты
1
,
,
m
p
p удовлетворяют соотношению
1 2
1
m
p
p
p
+
+ +
= .
•
Чистые и смешанные стратегии игрока B определяются аналогич- но.
Замечание. Каждая чистая стратегия является частным случаем смешан- ной стратегии, когда одна из стратегий применяется с частотой 1, а все остальные − с частотой 0.
•
Смешанные стратегии, избранные игроками, называются опти-
мальными, если одностороннее отклонение любым игроком от своей опти- мальной стратегии может изменить средний выигрыш только в сторону, не- выгодную для этого игрока.
•
Совокупность, состоящая из оптимальной стратегии одного игрока и оптимальной стратегии другого игрока, называется решением игры.
•
Средний выигрыш V при применении обоими игроками оптималь-
ных стратегий называется ценой игры.
•
Стратегии, входящие с ненулевыми частотами в оптимальную стра- тегию игрока, называются полезными.

Сайт: www.resolventa.ru
, E-mail: [e-mail]
Сайт: www.resolventa.ru
, E-mail: [e-mail]
11
В 1928 году фон Нейманом была доказана основная теорема теории
игр, утверждающая, что каждая игра имеет, по крайней мере, одно решение, возможно, в области смешанных стратегий.
Поскольку все чистые стратегии являются частными случаями сме- шанных стратегий, то из основной теоремы теории игр можно получить
Следствие 1. Любая игра имеет цену.
Следствие 2. Цена игры удовлетворяет неравенству



 V
Следствие 3. Средний выигрыш остается равным цене игры, если один из игроков придерживается своей оптимальной стратегии, а другой игрок применяет свои полезные стратегии с любыми частотами.
6. Аналитический метод решения игры типа 2 x 2
Рассмотрим игру без седловой точки типа 2 x 2 с платежной матрицей
11 12 21 22
c
c
C
c
c






=
и найдем оптимальную стратегию
1 2
1 2
A
A
A
S
p
p


=




игрока A. Согласно следствию 3 из основной теоремы теории игр эта страте- гия обеспечивает игроку A выигрыш, равный цене игры V, даже если игрок B не выходит за пределы своих полезных стратегий. В данной игре обе чистые стратегии игрока B являются полезными, поскольку в противном случае игра имела бы решение в области чистых стратегий, т.е. была бы игрой с седловой точкой.
Отсюда вытекает, что неизвестные
1 2
,
,
p
p V
удовлетворяют следующей системе из трех линейных уравнений
11 21 1
2 12 22 1
2 1
2
,
,
1,
c p
c p
V
c p
c p
V
p
p





+
=
+
=
+
=

Сайт: www.resolventa.ru
, E-mail: [e-mail]
Сайт: www.resolventa.ru
, E-mail: [e-mail]
12 решение которой имеет вид
,
,
22 21 1
11 22 12 21 11 12 2
11 22 12 21 11 22 12 21 11 22 12 21
c
c
p
c
c
c
c
c
c
p
c
c
c
c
c c
c c
V
c
c
c
c
−

+
−
−


−

+
−
−


−


+
−
−

=
=
=
Аналогичным образом можно найти оптимальную стратегию
1 2
1 2
B
B
B
S
q
q


=




игрока B. В этом случае неизвестные
1 2
,
,
q q V
удовлетворяют системе урав- нений
11 12 1
2 21 22 1
2 1
2
,
,
1,
c q
c q
V
c q
c q
V
q
q





+
=
+
=
+
=
решение которой имеет вид
,
,
22 12 1
11 22 12 21 11 21 2
11 22 12 21 11 22 12 21 11 22 12 21
c
c
q
c
c
c
c
c
c
q
c
c
c
c
c c
c c
V
c
c
c
c
−

+
−
−


−

+
−
−


−


+
−
−

=
=
=
Применим теперь полученные формулы к карточной игре типа "веришь
- не веришь".
Пример 6.1. Имеются две карты: туз и двойка. Игрок А наугад берет одну из них. Если А взял туза, то он заявляет: "У меня туз" и требует у про- тивника рубль. Если же А взял двойку, то он может либо сказать: "У меня туз" и потребовать рубль, либо признаться, что у него двойка и заплатить рубль. Игрок В, если ему предлагают рубль, берет его. Однако, если у него требуют рубль, то В может либо поверить, что у А туз, и заплатить рубль, ли- бо не верить и потребовать проверки. Если в результате проверки окажется,

Сайт: www.resolventa.ru
, E-mail: [e-mail]
Сайт: www.resolventa.ru
, E-mail: [e-mail]
13 что у А действительно туз, то В платит 2 рубля. Если же выяснится, что у А была двойка, то А платит 2 рубля.
Найти оптимальные стратегии для каждого из игроков.
Решение. У игрока A есть 2 стратегии:
1
A − обманывать,
2
A − не обма- нывать. У игрока В тоже есть 2 стратегии:
1
B − верить,
2
B − не верить. Это позволяет найти все элементы платежной матрицы игры, вычислив средний выигрыш для каждой комбинации стратегий.
1.
Комбинация
1 1
B
A
(А обманывает, В верит).
Если А берет туза (вероятностью этого 0,5), то он требует рубль. В верит ему и платит. Если А берет двойку (вероятность этого также 0,5), то он обма- нывает и тоже требует рубль. В верит ему и платит. Средний выигрыш А ра- вен
11 1 0,5 1 0,5 1
c = 
+ 
=
2.
Комбинация
2 1
B
A
(А обманывает, В не верит).
Если А берет туза, то он требует рубль, а В не верит и после проверки платит 2 рубля. Если же А взял двойку, то он обманывает и тоже требует рубль. В не верит ему, и в результате А платит 2 рубля. Средний выигрыш А равен
( )
12 2 0,5 2 0,5 0
c = 
+ − 
=
3.
Комбинация
1 2
B
A
(А не обманывает, В верит).
Если А берет туза, то он требует рубль, В платит 1 рубль. Если А берет двойку, то он сообщает об этом и платит рубль. Средний выигрыш А равен
( )
21 1 0,5 1 0,5 0
c = 
+ − 
=
4.
Комбинация
2 2
B
A
(А не обманывает, В не верит).
Если А берет туза, то он требует рубль, В проверяет и платит 2 рубля.
Если А берет двойку, то он сообщает об этом и платит рубль. Средний выиг- рыш А равен
( )
22 2 0,5 1 0,5 0,5
c
= 
+ − 
=
Отсюда вытекает, что платежная матрица имеет вид
11 12 21 22 1
0 0
0,5
c
c
C
c
c




=







 

=
,

Сайт: www.resolventa.ru
, E-mail: [e-mail]
Сайт: www.resolventa.ru
, E-mail: [e-mail]
14 и можно найти нижнюю и верхнюю цены игры:
1 2 1 2
α =max min
0
ij
i
j
c
   
=
,
1 2 1 2
β =min max
0,5
ij
i
j
c
   
=
Следовательно, игра не имеет седловой точки, и ее решение нужно ис- кать в области смешанных стратегий. Для этого воспользуемся формулами, полученными выше:
,
,
22 21 1
11 22 12 21 11 12 2
11 22 12 21 11 22 12 21 11 22 12 21 0,5 1
1,5 3
1 2
1,5 3
0,5 1
1,5 3
c
c
p
c
c
c
c
c
c
p
c
c
c
c
c c
c c
V
c
c
c
c
−


+
−
−


−

+
−
−


−



+
−
−

=
=
=
=
=
=
=
=
=
Следовательно, смешанная стратегия игрока A имеет вид
1 2
1 2
3 3
A
A
A
S




=




Далее получаем
,
22 12 1
11 22 12 21 11 21 2
11 22 12 21
,
0,5 1
1,5 3
1 2
1,5 3
c
c
q
c
c
c
c
c
c
q
c
c
c
c
−


+
−
−


−

+
−
−

=
=
=
=
=
=
1 2
1 2
3 3
B
B
B
S




=




Таким образом, оптимальным для А будет в одной трети случаев обма- нывать, а в двух третях случаев − не обманывать. Такая тактика обеспечит ему средний выигрыш, равный V = 1/3. Если бы А стал пользоваться своей максиминной стратегией, то его выигрыш был бы равен
α 0
=
Для В оптимальная стратегия − это в одной трети случаев верить А и платить ему рубль, а в остальных случаях требовать проверки. В этой ситуа-

Сайт: www.resolventa.ru
, E-mail: [e-mail]
Сайт: www.resolventa.ru
, E-mail: [e-mail]
15 ции его средний проигрыш составит 1/3 , тогда как при применении мини- максной стратегии он будет проигрывать в среднем
β 0,5
=
Значение V = 1/3 показывает, что рассмотренная игра выгодна для А и
невыгодна для В, поскольку, пользуясь своей оптимальной стратегией, A все-
гда может обеспечить себе положительный средний выигрыш.
7. Графический метод решения игр типа 2 n
 и
2
m
Рассмотрим игру типа 2 n
 с платежной матрицей






=
n
n
a
a
a
a
a
a
C
2 22 21 1
12 11


,
ипроведем через точку (1; 0) координатной плоскости Oxy прямую l, перпен- дикулярную оси абсцисс. После этого для каждой из стратегий
i
B
(
)
1,2,...,
i
n
=
проведем прямую
( )
(
)
1 2
1
:
i
i
i
i
b
y
a
a
a
x
+
−
=
,
соединяющую точку
)
;
0
(
1i
a
на оси Оу с точкой
)
;
0
(
2i
a
на прямой l. Ось Оу отвечает за стратегию
1
A , а прямая l − за стратегию
2
A .
Если игрок А применяет смешанную стратегию
1 2
1 2
A
A
A
S
p
p


=




,
y
x
M
l
i
b
i
a
2
i
a
1 2
p
1
p
i
b
1
)
(
2
A
)
(
1
A
O
y
x
M
l
n
b
2
p
1
p
3
b
1
)
(
2
A
)
(
1
A
O
2
b
1
b
n
b
3
b
N
V
1
b
2
b

Сайт: www.resolventa.ru
, E-mail: [e-mail]
Сайт: www.resolventa.ru
, E-mail: [e-mail]
16 то его выигрыш в случае, если противник применяет чистую стратегию
i
B , равен
2 2
2 1
2 2
1 1
)
1
(
p
a
p
a
p
a
p
a
i
i
i
i
+
−
=
+
, и этому выигрышу соответствует точка М на прямой
i
b с абсциссой
2
p
x =
Ломаная
3 1
MNb
b
, отмеченная на чертеже жирной линией, позволяет определить минимальный выигрыш игрока А при любом поведении игрока
В. Точка N, в которой эта ломаная достигает максимума, определяет ре-
шение и цену игры. Ордината точки N равна цене игры V, а ее абсцисса
2
p − частоте применения стратегии
1
A
в оптимальной смешанной стратегии игро- ка А.
Далее непосредственно по чертежу находим пару "полезных" стратегий игрока В, пересекающихся в точке N (если в точке N пересекается более двух стратегий, то выберем любые две из них). Пусть это будут стратегии
i
B и
j
B
. Поскольку выигрыш игрока А, если он придерживается оптималь- ной стратегии, не зависит от того, в каких пропорциях игрок В применяет эти стратегии, то неизвестные
1 2
,
,
p
p V
определяются из системы уравнений
1 2
1 2
1 2
1 2
1 2
,
,
1.
i
i
j
j
a p
a p
V
a p
a p
V
p
p





+
=
+
=
+
=
Частоты
2 1
, q
q
в оптимальной стратегии






=
0 0
0 0






j
i
j
i
B
q
q
B
B
S
игрока В определяются из соотношения
)
1
(
;
)
1
(
1 1
i
j
i
j
i
i
q
q
V
q
a
q
a
−
=
=
−
+
Замечание. Иногда точка N не является пересечением двух стратегий, а попадает на одну из прямых х = 0 или х = 1 . В этом случае решением игры будут соответствующие чистые стратегии.

Сайт: www.resolventa.ru
, E-mail: [e-mail]
Сайт: www.resolventa.ru
, E-mail: [e-mail]
17
Для игры
2
m решение находится совершенно аналогично. Действи- тельно, поскольку выигрыш игрока А одновременно является проигрышем игрока В, то для решения задачи нужно построить ломаную, соответствую- щую верхней границе выигрыша игрока А, а затем найти на ней точку с ми-
нимальной ординатой.
Пример 7.1. Пусть игра задана матрицей






=
7 2
3 6
3 9
5 1
C
Найти оптимальные стратегии игроков и определить цену игры.
Решение.
Проведем прямые
i
b , и построим ло- маную линию
3 1
b
NM
b
, соответствую- щую нижней границе выигрыша. Точка
N, в которой эта ломаная достигает максимума, является пересечением прямых
( )
1
:
1 5
b
y
x
= + и
( )
2
:
5 2
b
y
x
= −
Вычислив координаты точки
N:
7
/
27
,
7
/
4 0
0
=
=
y
x
, получаем опти- мальную стратегию игрока А
1 2
3 4
7 7
A
A
A
S




=





и цену V = 27/7. Так как точка N является пересечением прямых
1
b и
2
b , то полезными стратегиями игрока В будут стратегии
1
B и
2
B . Найдем частоты их применения
1
q и
2
q , зная, что выигрыш равен цене игры, если игрок В применяет оптимальную стратегию, а игрок А - любую из своих полезных стратегий, например, стратегию
1
A
:

=
=
−
+
7
/
27
)
1
(
5 1
1
V
q
q
7
/
5 1
,
7
/
2 1
2 1
=
−
=
=
q
q
q
y
x
M
l
1
)
(
2
A
)
(
1
A
O
N
4/7 3/7 9
5 3
1 7
6 3
2 0
y
0
x
3
b
2
b
4
b
1
b

Сайт: www.resolventa.ru
, E-mail: [e-mail]
Сайт: www.resolventa.ru
, E-mail: [e-mail]
18
Ответ.
7
/
27
;
0 0
7
/
5 7
/
2
;
7
/
3 7
/
4 4
3 2
1 2
1
=






=






=
V
B
B
B
B
S
A
A
S
B
A
Пример 7.2. Пусть игра задана матрицей












=
10 0
8 6
6 9
2 11
C
Найти оптимальные стратегии игроков и определить цену игры.
Решение.
Воспользовавшись тем, что игрок B располагает двумя чистыми стратегия- ми, построим прямые
i
a , соответству- ющие выигрышам игрока А при чистых стратегиях
i
A , и ломаную линию
4 1
PNMa
a
, огибающую график сверху.
Эта ломаная достигает минимума в точке
)
,
(
0 0
y
x
N
, которая является пе- ресечением прямых
( )
2
:
9 3
a
y
x
= − и
( )
3
:
6 2
a
y
x
= +
Следовательно,
0 0,6;
7,2
x
V
=
=
, и оптимальной стратегией игрока В явля- ется стратегия
1 2
0, 4 0,6
B
B
B
S


=




Цена игры
7,2
V =
. Полезными стратегиями игрока А являются стратегии
2
A и
3
A . Найдем их частоты
2
p и
3
p :
;
5
/
2
:
5
/
36
)
1
(
6 9
2 2
2
=
=
−
+
p
p
p
5
/
3 1
2 3
=
−
=
p
p
Ответ.
5
/
36
;
5
/
3 5
/
2
;
0 5
/
3 5
/
2 0
2 1
4 3
2 1
=






=






=
V
B
B
S
A
A
A
A
S
B
A
x
P
l
1
O
N
3/5 2/5 11 9
6 1
B
10 8
6 1
0
y
0
x
1
a
2
a
3
a
4
a
M
2
B
y

Сайт: www.resolventa.ru
, E-mail: [e-mail]
Сайт: www.resolventa.ru
, E-mail: [e-mail]
19
ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ
1. Что называется игрой?
2. Что называется матричной игрой?
3. Что называется матричной игрой типа
m n

?
4. Какая игра называется игрой с нулевой суммой?
5. Что называется чистой стратегией?
6. Что называется нижней ценой игры?
7. Что называется верхней ценой игры?
8. Что называется ценой игры?
9. В чем состоит принцип минимакса?
10. Какая игра называется игрой с седловой точкой?
11. Что называется седловой точкой?
12. Что называется смешанной стратегией?
13. Что называется решением игры в смешанных стратегиях?
14. Что называется полезной стратегией?
15. Что утверждает основная теорема теории игр?
16. В чем состоит схема аналитического решения игры типа 2 2
 ?
17. В чем состоит схема графического решения игры типа 2 n
 ?
18. В чем состоит схема графического решения игры типа
2
m ?

Сайт: www.resolventa.ru
, E-mail: [e-mail]
Сайт: www.resolventa.ru
, E-mail: [e-mail]
20
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ
1.
При помощи аналитического метода найти решение игры, заданной пла- тежной матрицей
8 5
4 6







2.
При помощи графического метода найти решение игры, заданной пла- тежной матрицей
0 5 3 4 5
3 5 4







3.
При помощи графического метода найти решение игры, заданной пла- тежной матрицей
0 4
4 0
1 3
4 1















Сайт: www.resolventa.ru
, E-mail: [e-mail]
Сайт: www.resolventa.ru
, E-mail: [e-mail]
21
ЛИТЕРАТУРА
Основная:
1. Вентцель Е.С. Исследование операций: Задачи, принципы, методология.
Учебное пособие - М.: Дрофа, 2004.
2. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслужи- вания. – М.: КомКнига, 2005.
3. Колемаев В.А., Калинина В.Н. Теория вероятностей и математическая статистика: Учебник. – М.: ИНФРА-М, 2002.
4. Оуэн Г. Теория игр. – М.: Вузовская книга, 2004.
Дополнительная:
5. Афанасьев М.Ю., Багриновский К.А., Матюшок В.М. Прикладные за- дачи исследования операций. Учебное пособие. – М.: ИНФРА-М, 2006.
6. Ивницкий В.А. Теория сетей массового обслуживания. – М.: Физмат- лит, 2004.
7. Кремер Н.Ш. Теория вероятностей и математическая статистика.
Учебник. – М.: ЮНИТИ-ДАНА, 2001.
8. Протасов И.Д. Теория игр и исследование операций. Учебное пособие. –
М.: Гелиос АРВ, 2006.
9. Таха Х.А. Введение в исследование операций. – М.: ВИЛЬЯМС, 2007.