методичка Теория игр 2014. Методические указания и контрольные задания по дисциплине теория игр для студентовзаочников 2 курса, специальности 080100 семестр 4 Москва 2014

• Название: Методические указания и контрольные задания по дисциплине теория игр для студентовзаочников 2 курса, специальности 080100 семестр 4 Москва 2014
• Анкор: методичка Теория игр 2014.pdf
• Дата: 26.04.2017
• Размер: 1.28 Mb.
• Имя файла: методичка Теория игр 2014.pdf
• Тип: Методические указания; #5966
• страница: 5 из 8

A
A
v
v
. Из решения
*
y
можно легко получается оптимальная стратегия для игрока
B
:
)
2
/
1
,
4
/
1
,
4
/
1
(
*




A
B
v
y
y
. По четвертой таблице, исходя из принципа двойственности, можно также определить и решение первой задачи с

ограничениями (49). Именно,
25
/
9
)
3
(
4
*
1



x
(те. коэффициенты дополнительных переменных
4
y ,
5
y ,
6
y соответствуют оптимальному решению второй двойственной задачи,
25
/
7
)
3
(
5
*
2



x
, Поэтому
)
25
/
4
,
25
/
7
,
25
/
9
(
*

x
, что соответствует решению задачи 1. РАЗДЕЛ 2. БИМАТРИЧНЫЕ ИГРЫ
[2, гл, § 2], [3, гл, § 1-2], [4, гл, § 1-3], [5, гл, § 8-9], [6, гл, § 7-
11]. Предыдущие рассмотрения касались игр двух лиц, интересы игроков в которых были противоположны. Однако, на практике чаще встречаются ситуации, хотя интересы игроков не совпадают, но уже не являются противоположными (антагонистическими. Например, при встрече двух боевых единиц двух воюющих сторон их обоюдное стремление уничтожить друг друга не выражает антагонистического конфликта.
Биматричной игрой называется конечная бескоалиционная игра двух лиц, те. когда каждый из двух игроков имеет конечное число стратегий. Пусть игрок
A
имеет
m
стратегий, а игрок
B
–
n
стратегий. Тогда биматричную игру можно описать двумя матрицами выигрышей
A
и для игроков
A
и
B
:
1
B
2
B
n
B А
11
a
12
a А
21
a
22
a А
1
m
a
2
m
a
…
mn
a
1
B
2
B
n
B А
11
b
12
b А
21
b
22
b А
1
m
b или в виде матриц
 
n
m
ij
a
A


,
 
n
m
ij
b
B


(51) Здесь
ij
a – выигрыш игрока
A
, если он применит свою стратегию
i
A
, а игрок
B
– стратегию
j
B ;
ij
b – выигрыш игрока
B
в ситуации


j
i
B
A ,

Таким образом, если интересы игроков
A
и
B
не совпадают, ноне обязательно противоположны, получаются две платежные матрицы матрица
A
– матрица выплат игроку
A
, другая матрица
B
– матрица выплат игроку
B
. Поэтому название игры здесь совершенно естественно
– биматричная. Матричную игру можно считать частным случаем биматричной игры, когда матрица выплат игроку
B
противоположна матрице выплат игроку
A
:
ij
ij
a
b


или В общем случае биматричная игра – это игра с ненулевой суммой.
2.1. ПРИМЕРЫ БИМАТРИЧНЫХ ИГР Рассмотрим некоторые типичные конфликтные ситуации, приводящие к биматричным играм. Сначала укажем формализацию этих конфликтов, а позднее дадим рекомендации по их разрешению. Пример 1. Борьба за рынки Небольшая фирма (игрок
A
) намерена сбыть партию товара на одном из двух рынков, контролируемых другой, более крупной фирмой (игрок
B
). Для этого фирма
A
готова предпринять на одном из рынков определенные действия (например. провести рекламную кампанию. Господствующая на этих рынках фирма
B
может попытаться воспрепятствовать этому, приняв на одном из рынков предупредительные меры. Если фирмане встречает противодействия на рынке, то она его захватывает при наличии препятствий – терпит поражение. Будем считать для определенности, что проникновение фирмы
A
на первый рынок более выгодно, чем на второй. Естественно также считать, что борьба за первый рынок потребует вложения больших средств. Например, победа фирмы
A
на первом рынке принесет ей вдвое больший выигрыш, чем победа на втором рынке, но зато и поражение полностью ее разорит, а фирму
B
избавит от конкурента. Что касается второго рынка, то при поражении фирмы
A
ее потери будут не столь значительны, но и победа принесет немного. Таким образом, у фирмы
A
две стратегии
1
A – выбор первого рынка,
2
A – выбор второго рынка. Такие же стратегии и у фирмы
B
:
1
B – выбор первого рынка,
2
B – выбор второго рынка. Чтобы составить платежные матрицы игрок, нужны расчетные количественные показатели, которые мы приведем здесь в условных единицах









1 1
2 10
A
,









1 1
2 5
B
(52)

Из выписанных матриц видно, что если игроки выберут один и тот же рынок, то победа останется за игроком Пример 2. Дилемма узников Игроками являются два узника, находящихся в камере предварительного заключения по подозрению в совершении преступления. При отсутствии прямых улик возможность их осуждения в большей степени зависит оттого, заговорят они или будут молчать. Если оба будут молчать, то наказание им обоим составит ровно 1 год. Если оба сознаются, то получат срок 6 лет (признание учитывается как смягчающее обстоятельство. Если заговорит только один, а другой будет молчать, то заговоривший будет выпущен на свободу, а промолчавший получит максимально возможное наказание 9 лет. В этой биматричной игре каждый из игроков имеет две стратегии молчать (стратегии
1
A и
1
B
) или говорить (стратегии
2
A и
2
B
). При этом их выигрыши описываются так










6 0
9 1
A
,










6 9
0 1
B
(53) Пример 3. Семейный спор. Два партнера (мужи жена) договариваются совместно провести одно из двух мероприятий пойти на футбол (Фили в театр (Т. В случае осуществления первого из этих двух мероприятий (пойти на футбол) выигрыш первого партнера (игрок
A
) вдвое больше выигрыша второго (игрок
B
). Наоборот, в случае осуществления второго из этих двух мероприятий выигрыш игрока будет вдвое меньше выигрыша игрока В этой биматричной игре у каждого из игроков имеется по две стратегии (Ф, Т, при этом они заранее не договариваются, куда им пойти. Если они не встретятся, то это будет огорчением для обоих. Матрицы выигрышей здесь имеют такой вид







1 0
0 2
A
,







2 0
0 1
B
(54) Пример 4. «Студент-преподаватель». Пусть студент(игрок
A
) готовится сдать зачет (например, по теории игр. Игрок
B
– это преподаватель, который его принимает. У студента две стратегии подготовиться к сдаче зачета (+) и не подготовиться (–). У преподавателя также две стратегии поставить зачет (+) и не поставить зачет (–). В основу функций выигрышей положим следующие соображения выигрыш студента
(+)
(–)
(+) оценка заслужена очень обидно
(–) удалось обмануть оценка заслужена

выигрыш преподавателя
(+)
(–)
(+) все нормально был неправ
(–) дал себя обмануть опять придет Количественно это можно выразить, например, так








0 1
1 2
A
,









0 1
2 2
B
(55)
2.2. СМЕШАННЫЕ СТРАТЕГИИ. РАВНОВЕСИЕ ПО НЭШУ. В приведенных выше примерах описаны ситуации, в которых интересы игроков не совпадают. Поэтому необходимо найти такое компромиссное решение, которое в томили ином виде удовлетворяло бы обоих игроков. Таким образом, необходимо найти такую равновесную ситуацию, явное отклонение от которой одного из игроков уменьшило бы его выигрыш. Такая ситуация ранее была найдена в матричных играх она определялась седловой точкой (если, конечно, она существует. Рассмотрим биматричную игру в нормальной форме. Пусть игрок имеет
m
стратегий
i
A (
m
i
,
1

), а игрок
B
–
n
стратегий
j
B (
n
j
,
1

). Ситуация
)
,
(
*
*
j
i
биматричной игры называется ситуацией равновесия (равновесной по Нэшу) в чистых стратегиях, если
*
*
*
j
i
ij
a
a

для любых
m
i
,
1

и
*
*
*
j
i
j
i
b
b

для любых
n
j
,
1

. (56) Для того чтобы найти ситуацию равновесия по Нэшу в чистых стратегиях, необходимо найти в каждом столбце матрицы выигрышей игрока
A
максимальный элемент и подчеркнуть его. Аналогично, в каждой строке матрицы выигрышей игрока
B
нужно подчеркнуть максимальный элемент. Если в обеих матрицах будет подчеркнут элемент, стоящий на одном и том же месте, то его положение и определит ситуацию равновесия в игре. Заметим, что в биматричной игре (в отличие от матричной) выигрыши игроков, при наличии нескольких ситуаций равновесия, могут различаться. Пример. Найти все ситуации равновесия в биматричной игре
















3 5
2 1
4 5
1 2
4 3
2 4
1 5
3 2
A
,














6 3
7 8
2 6
6 3
4 5
5 4
7 4
5 В матрицах
A
и
B
подчеркнуты максимальные элементы, стоящие в столбцах и строках соответственно. Видно, что общий подчеркнутый элемент стоит в позиции (3, 3), те. здесь единственная ситуация

равновесия
3
*
A
A
i

,
3
*
B
B
j

и выигрыши игроков следующие
5

A
v
, В биматричных играх, как ив матричных, можно использовать принцип (строгого) доминирования для удаления заведомо невыгодных стратегий у игроков
A
и
B
. Как это делается, подробно описано в соответствующей литературе. Остановимся теперь на случае, когда игра не имеет ситуаций равновесия в чистых стратегиях. В матричных играх эта трудность была преодолена при помощи перехода к смешанному расширению игры, тек возможности еѐ многократного повторения и такому поведению игроков, при котором они чередуют свои чистые стратегии с определенными вероятностями для игрока
A
:
)
...,
,
,
(
2 1
m
p
p
p
x

– его смешанная стратегия, где



m
i
i
p
1 1,
0

i
p
,
m
i
,
1

; для игрока
B
:
)
...,
,
,
(
2 1
n
q
q
q
y

– его смешанная стратегия, причем



n
j
j
q
1 1,
0

j
q
, Смешанное расширение матричной игры привело к расширению возможности выплат в том смысле, что вычисляется средний выигрыш игроков
A
и
B
:




m
i
n
j
j
i
ij
A
q
p
a
y
x
H
1 1
)
,
(
, В биматричных играх также можно перейти к смешанному расширению игры, предполагая, что каждая игра может быть повторена в неизменных условиях. При этом средние выигрыши игроков
A
и определяются по их платежным матрицами) Ситуация
*}
*,
{
y
x
называется ситуацией равновесия (по Нэшу) в смешанных стратегиях биматричной игры, если для любых
x
и выполняются неравенства
*)
*,
(
*)
,
(
y
x
H
y
x
H
A
A

,
*)
*,
(
)
*,
(
y
x
H
y
x
H
B
B

(58) Эти неравенства означают, что если один из игроков отклонится от своей равновесной стратегии, то его выигрыш не увеличится. Теорема (Джон Нэш, 1950). Всякая биматричная игра имеет хотя бы одну ситуацию равновесия, возможно, в смешанных стратегиях. Рассмотрим далее решение биматричной игры размерности 2

2.

2.3. БИМАТРИЧНЫЕ ИГРЫ РАЗМЕРНОСТИ 2

2 В этом случае платежные матрицы игроков имеют вид







22 21 12 11
a
a
a
a
A
,







22 21 12 11
b
b
b
b
B
(59) Обозначим
p
p

1
,
p
p


1 2
,
q
q

1
,
q
q


1 2
, где
1
,
0


q
p
. Тогда из формул (57) получим
)
1
)(
1
(
)
1
(
)
1
(
)
,
(
22 21 12 11
q
p
a
q
p
a
q
p
a
pq
a
y
x
H
A








,
(60)
)
1
)(
1
(
)
1
(
)
1
(
)
,
(
22 21 12 11
q
p
b
q
p
b
q
p
b
pq
b
y
x
H
B








(61) Определим ситуацию равновесия, те. найдем пару чисел
)
,
(
*
*
q
p
,
1
,
0
*
*


q
p
, для которой одновременно выполняются неравенства
)
,
(
)
,
(
*
*
*
q
p
H
q
p
H
A
A

и а) Так как величины
p
и
q
могут принимать любые значения, то выполнение указанных неравенств равносильно выполнению неравенств





,
)
,
(
)
,
1
(
)
,
(
)
,
0
(
*
*
*
*
*
*
q
p
H
q
H
q
p
H
q
H
A
A
A
A
и б) Таким образом, для определения равновесной ситуации достаточно проверить неравенства (а) для двух чистых стратегий игроков
A
и Запишем средние выигрыши игроков в более удобной форме
,
)
(
)
(
)
(
)
,
(
22 22 21 22 12 22 21 12 11
a
q
a
a
p
a
a
pq
a
a
a
a
q
p
H
A









)
(
)
(
)
(
)
,
(
22 22 21 22 12 22 21 12 Положим
22 21 12 11
a
a
a
a
C




,
12 22
a
a



,
22 21 12 11
b
b
b
b
D




,
21 Используя эти обозначения, из формул (60)-(61) получим
22 22 21
)
(
)
,
(
a
q
a
a
p
Cpq
q
p
H
A






, а)
22 22 а) Из неравенств (б) и формул (60а)-(61а) следует, что








0
)
(
,
0
)
1
)(
(
p
Сq
p
Сq


и








0
)
(
,
0
)
1
)(
(
q
Dp
q
Dp


(62) Из неравенств (62) для игрока
A
имеем три случая если
0

p
, то для всех
1 0


q
имеем
0



Cq
; если
1

p
, то для всех
1 0


q
имеем
0



Cq
; если
1 0


p
, то для всех
1 0


q
имеем Если
0



C
, то решением будет являться весь единичный квадрат
]
1
,
0
[

p
,
]
1
,
0
[

q
, т.к. условия 1)-3) выполняются при всех
p
и
q

Если
0

C
,
0


, то выполняется либо условие 1), либо условие 2), те. решением является либо
0

p
, либо Если
0

C
, то получим следующие решения
1) если
0

p
, то С 2) если
1

p
, то С 3) если
1 0


p
, то
С
q


Если
0

C
, то решения будут следующие
1) если
0

p
, то С 2) если
1

p
, то С 3) если
1 0


p
, то
С
q


Графическая интерпретация множества решений игрока
A
: Риса
Рис.10б Для игрока
B
исследования решения аналогичны. Укажем их. Если
0


