Моклячук М.П., Ямненко Р.Є. Лекції з теорії вибору та прийняття рішень (на укр. языке)
Подождите немного. Документ загружается.
2.8. МНОЖИНА ВСIХ РОЗВ’ЯЗКIВ ГРИ
Нехай A =(a
ij
)
m
i=1
n
j=1
–матрицярозмiрностim ×n.НехайG –цегра
зматрицею
A.ПозначимочерезT
1
(G) множину оптимальних стратегiй
першого гравця, а через
T
2
(G) – множину оптимальних стратегiй дру-
гого гравця. Переконаємось, що множини
T
1
(G) та T
2
(G) мають просту
геометричну iнтерпретацiю – вони є опуклими оболонками скiнченної
кiлькостi точок у просторi
R
m
та R
n
вiдповiдно.
Теорема 2.8.1. Якщо
G –цегразматрицеюA,тоT
1
, T
2
–непо-
рожнi замкненi обмеженi опуклi пiдмножини просторiв
R
m
та R
n
вiдповiдно. Крiм того, кожний елемент множини T
i
,i =1,2, єопу-
клою лiнiйною комбiнацiєю елементiв множини
K(T
i
), де через K(T )
позначена множина всiх крайнiх точок множини T .
Доведення. Доведемо твердження для множини
T
1
(G). Для множини
T
2
(G) доведення аналогiчне.
З основної теореми матричних iгор випливає, що множина
T
1
(G) не-
порожня. Оскiльки
T
1
(G) є пiдмножиною множини S
m
,тодоситьпоказа-
ти обмеженiсть множини
S
m
, щоб довести обмеженiсть множини T
1
(G).
Обмеженiсть множини
S
m
очевидна, бо кожний елемент x =(x
1
,...,x
m
)
множини S
m
задовольняє умови
x
1
+ ···+ x
m
=1,x
i
≥ 0,i=1,...,m.
Звiдси
x
2
1
+ ···+ x
2
m
≤ 1.
Отже, множина S
m
належить гiперсферi радiуса 1 з центром у початку
координат. Тому вона обмежена.
Щоб переконатись у тому, що множина
T
1
(G) опукла, вiзьмемо будь-
якi елементи
X
(1)
,...,X
(r)
множини T
1
(G) i деякий елемент α =(α
1
,...,
α
r
) множини S
r
i переконаємось, що опукла комбiнацiя X
∗
= α
1
X
(1)
+
···+ α
r
X
(r)
елементiв X
(1)
,...,X
(r)
множини T
1
(G) належить T
1
(G).
Оскiльки
X
(1)
,...,X
(r)
належать множинi T
1
(G), то для будь-якого еле-
мента
Y множини S
n
виконуються нерiвностi
v ≤ E(X
(i)
,Y ),i=1,...,r.
Так як α
i
≥ 0, то з останньої нерiвностi отримаємо
α
i
v ≤ α
i
E(X
(i)
,Y ),i=1,...,r.
I, як наслiдок,
v = α
1
v + ···+ α
r
v ≤ α
1
E(X
(1)
,Y )+···+ α
r
E(X
(r)
,Y ).
Враховуючи, що
α
1
E(X
(1)
,Y )+···+ α
r
E(X
(r)
,Y )=E(X
∗
,Y ),
131
матимемо
v ≤ E(X
∗
,Y )
для кожного Y ∈ S
n
.Цеозначає,щоX
∗
належить множинi T
1
(G).Отже,
ця множина опукла.
Щоб переконатись у тому, що множина замкнута, вiзьмемо послi-
довнiсть
X
(1)
,X
(2)
,... елементiв множини T
1
(G),щозбiгаєтьсядоX
∗
.
Оскiльки множина
S
m
замкнута, то X
∗
∈ S
m
. Нам потрiбно показати,
що
X
∗
∈ T
1
(G).ОскiлькиX
(i)
∈ T
1
(G),тодлякожногоY ∈ S
n
справ-
джується нерiвнiсть
v ≤ E(X
(i)
,Y ).
Функцiя E(X,Y ) лiнiйна (i неперервна), тому з останньої нерiвностi ви-
пливає, що для кожного
Y ∈ S
n
v ≤ E(X
∗
,Y ).
Це означає, що X
∗
належить множинi T
1
(G).Отже,цямножиназа-
мкнута.
Теорема 2.8.2. Нехай G – гра з матрицею виграшiв A.НехайX ∈ T
1
,
Y ∈ T
2
, v = E(X,Y ).Длятого,щобX ∈ K(T
1
),Y ∈ K(T
2
) необхi-
дно i достатньо, щоб iснувала квадратна пiдматриця
B матрицi A
порядку r × r,такащо
c = I
r
(adjB)I
r
=0;
v =
det (B)
I
r
(adjB)I
r
;
˙
X =
I
r
(adjB)
I
r
(adjB)I
r
;
˙
Y =
I
r
(adjB)
I
r
(adjB)I
r
,
де
˙
X
– це вектор, який отримаємо з X, викреслюючи елементи, що
вiдповiдать викресленим рядкам матрицi
A при переходi до матри-
цi
B,
˙
Y
– це вектор, який отримаємо з Y , викреслюючи елементи,
що вiдповiдать викресленим стовпчикам матрицi
A при переходi до
матрицi
B, I
r
=(1,1,...,1) – одиничний вектор, adjB – приєднана
матриця, яка зададольняє спiввiдношення adj
B = b
−1
det B.
Теорему 2.8.2 можна сформулювати в такому виглядi.
Теорема 2.8.3. Нехай
G – гра з матрицею виграшiв A.НехайX ∈ T
1
,
Y ∈ T
2
, v = E(X,Y ).Длятого,щобX ∈ K(T
1
),Y ∈ K(T
2
) необхiдно
132
i достатньо, щоб iснувала невироджена квадратна пiдматриця B
матрицi A розмiрностi r × r,такащо
v =
1
I
r
B
−1
I
r
;
˙
X =
I
r
B
−1
I
r
B
−1
I
r
;
˙
Y =
I
r
(B
−1
)
I
r
B
−1
I
r
.
Доведення. Розглянемо гру з матрицею порядку m × n
A =
a
11
a
12
... a
1n
a
21
a
22
... a
2n
... ... ... ...
a
m1
a
m2
... a
mn
.
Щоб довести достатнiсть умов теореми припустимо, що iснує невиродже-
на квадратна пiдматриця
B матрицi A розмiрностi r ×r,яказадовольняє
умовам теореми, i нехай умови
X ∈ K(T
1
),Y ∈ K(T
2
) не виконуються.
Покажемо, що припущення
X/∈ K(T
1
) приводить до суперечностi. До-
ведення суперечностi припущення
Y/∈ K(T
2
) аналогiчне.
Нехай матриця
B знаходитьсяуверхньомулiвомукутiматрицiA,
тобто
B =
a
11
a
12
... a
1r
a
21
a
22
... a
2r
... ... ... ...
a
r1
a
r2
... a
rr
.
Якщо X =(x
1
,...,x
m
),то
˙
X =(x
1
,...,x
r
).ОскiлькиX ∈ S
m
,то
x
i
≥ 0 для i =1,...,m iтимбiльшеx
i
≥ 0 для i =1,...,r.Зумов
теореми випливає, що
r
i=1
x
i
=
˙
XJ
r
=
I
r
B
−1
J
r
I
r
B
−1
I
r
=1.
Тому
˙
X ∈ S
m
i x
i
=0для i = r +1,...,m. За припущенням X/∈ K(T
1
).
Отже, знайдуться не рiвнi мiж собою елементи
U =(u
1
,...,u
m
), W =
(w
1
,...,w
m
) множини T
1
(G) такi, що X =
1
2
(U + W ),тобтоx
i
=
1
2
(u
i
+
w
i
),i =1,...,m.Оскiлькиx
i
=0для i = r+1,...,m та u
i
≥ 0,i =1,...,m,
w
i
≥ 0,i =1,...,m,тоu
i
=0,w
i
=0,i = r +1,...,m.
Отже, матимемо
u
1
a
1j
+ ···+ u
r
a
rj
= u
1
a
1j
+ ···+ u
m
a
mj
,j = i,...,m.
Оскiльки U =(u
1
,...,u
m
) ∈ T
1
(G),то
u
1
a
1j
+ ···+ u
m
a
mj
≥ v,j = i,...,m.
133
З останньої рiвностi випливає, що
u
1
a
1j
+ ···+ u
r
a
rj
≥ v, j = i,...,r.
Аналогiчно показуємо, що
w
1
a
1j
+ ···+ w
r
a
rj
≥ v, j = i,...,r.
За умов теореми
˙
XB =
I
r
B
−1
B
I
r
B
−1
I
r
=
I
r
I
r
B
−1
I
r
= vJ
r
.
Тому
x
1
a
1j
+ ···+ x
r
a
rj
= v, j = i,...,r.
Оскiльки x
i
=
1
2
(u
i
+ w
i
),i =1,...,m,то
1
2
(u
1
+ w
1
)a
1j
+ ···+
1
2
(u
r
+ w
r
)a
rj
= v, j = i,...,r,
або
[u
1
a
1j
+ ···+ u
r
a
rj
]+[w
1
a
1j
+ ···+ w
r
a
rj
]=2v, j = i,...,r.
Як наслiдок, матимемо
[u
1
a
1j
+ ···+ u
r
a
rj
]=[w
1
a
1j
+ ···+ w
r
a
rj
]=v, j = i,...,r.
Останню рiвнiсть можна записати, як
UB = WB
або
(U −W )B =0.
Так як U,W – рiзнi вектори, то з останньої рiвностi випливає, що матри-
ця
B вироджена. Що суперечить умовам теореми.
З теорем 2.8.1 – 2.8.3 випливає, що справджується наступна теорема.
Теорема 2.8.4. Якщо
G –цегразматрицеюA, то множини K(T
1
),
K(T
2
) мають скiнченну кiлькiсть точок, а множини T
1
, T
2
єопуклими
оболонками цих точок. Отже,
T
1
, T
2
– це многогранники з вершинами
в точках, що утворюють множини
K(T
1
), K(T
2
).
Iз 2.8.1 – 2.8.4 теорем випливає такий алгоритм знаходження всiх
розв’язкiв матричної гри. Розглянемо по черзi кожну квадратну пiдма-
трицю
B матрицi A.ДлякожноїпiдматрицiB порядку r перевiримо
умови теореми 2.8.2, обчислимо
v,
˙
X,
˙
Y та перевiримо чи належать
˙
X,
˙
Y
множинi S
r
. Якщо нi, то цю пiдматрицю вiдкидаємо i беремо iншу пiдма-
трицю. Якщо
˙
X ∈ S
r
,
˙
Y ∈ S
r
, то утворюємо вектори X ∈ S
n
,Y ∈ S
m
,до-
даючи до
˙
X
,
˙
Y
нульовi координати, i перевiряємо умову X ∈ T
1
, Y ∈ T
2
.
Якщо нi, то переходимо до наступної пiдматрицi. Якщо так, то
X, Y
є розв’язком i згiдно з теоремою 2.8.2 X ∈ K(T
1
), Y ∈ K(T
2
). Таким
134
чином ми можемо знайти всi елементи множин K(T
1
), K(T
2
). Множини
всiх розв’язкiв
T
1
, T
2
– це опуклi лiнiйнi комбiнацiї елементiв множин
K(T
1
), K(T
2
).
Зауважимо, що немає необхiдностi розглядати одноелементнi пiдмно-
жини, бо вони дають розв’язок лише тодi, коли матриця має сiдлову
точку.
Приклад 2.8.1. Знайти всi розв’язки гри з матрицею виграшiв
A =
240
104
.
Матриця не має сiдлової точки. Розглянемо три пiдматрицi 2-го порядку
B =
24
10
,C=
20
14
,D=
40
04
.
1). Застосуємо твердження теореми 2.8.2 до матрицi B.Матимемо
adj B =
0 −4
−12
,
(adj B)
=
0 −1
−42
,
I
2
(adj B)=
−1 −2
,
I
2
(adj B)
=
−41
,
det (B)=−4,I
2
(adj B)I
2
= −3.
Пiдставимо отриманi результати у формули з теореми 2.8.2. Матимемо
v =
−4
−3
=
4
3
,
˙
X =
−1 −2
−3
=
1
3
2
3
,
˙
Y =
−41
−3
=
4
3
−
1
3
.
Оскiльки друга компонента вектора
˙
Y
вiд’ємна, то
˙
Y/∈ S
2
. Отже, матри-
ця
B не дає розв’язку гри.
2). Розглянемо матрицю
C.Отримаємо
v =
8
5
,
˙
X =
3
5
2
5
,
˙
Y =
4
5
1
5
.
Таким чином,
˙
X ∈ S
2
та
˙
Y ∈ S
2
.ПобудуємовекториX, Y :
X =
˙
X =
3
5
2
5
,Y=
4
5
0
1
5
.
135
Далi перевiримо нерiвностi, що визначають розв’язок гри
E
(X,1) =
3
5
· 2+
2
5
· 1=
8
5
= v,
E(X,2) =
3
5
· 4+
2
5
·0=
12
5
>v,
E(X,3) =
3
5
· 0+
2
5
· 4=
8
5
= v,
E(1,Y )=
4
5
·2+0· 4+
1
5
·0=
8
5
= v,
E(2,Y )=
4
5
·1+0· 0+
1
5
·4=
8
5
= v.
Отже, знайденi вектори X та Y дiйсно є розв’язком гри.
3). Розглянемо матрицю
D.Матимемо
v =2,
˙
X =
1
2
1
2
,
˙
Y =
1
2
1
2
.
Тому
˙
X ∈ S
2
та
˙
Y ∈ S
2
. Утворимо вектори X, Y :
X =
1
2
1
2
,Y=
0
1
2
1
2
.
При перевiрцi нерiвностей, що визначають розв’язок гри, знаходимо
E
(X,1) =
1
2
· 2+
1
2
· 1=
3
2
<v.
Тому знайденi вектори X та Y не є розв’язком гри.
Отже, гра має єдиний розв’язок:
v =
8
5
,X=
3
5
2
5
,Y=
4
5
0
1
5
.
Приклад 2.8.2. Знайти всi розв’язки гри з матрицею виграшiв
A =
210
012
.
Матриця не має сiдлової точки. Розглянемо три пiдматрицi 2-го порядку
B =
21
01
,C=
20
02
,D=
10
12
.
1). Застосуємо твердження теореми 2 до матрицi B.Матимемо
v =1,
˙
X =
1
2
1
2
,
˙
Y = 01.
Побудуємо вектори X, Y :
X =
˙
X =
1
2
1
2
,Y= 010.
136
Перевiривши нерiвностi, знаходимо, що знайденi вектори X та Y дiйсно
є розв’язком гри.
2). Для матрицi
C матимемо
v =1,X=
1
2
1
2
,Y=
1
2
0
1
2
.
Перевiривши нерiвностi, знаходимо, що знайденi вектори X та Y теж є
розв’язком гри.
3). Для матрицi
D матимемо
v =1,X=
1
2
1
2
,Y= 010.
Тобто такий же розв’язок, як i для матрицi B.
Отже, для цiєї гри множина
K(T
1
) мiстить лише один елемент X =
1
2
1
2
. Тому множина розв’язкiв T
1
складається лише з одного цього
елемента. Множина
K(T
2
) мiстить два елементи Y
1
=
1
2
0
1
2
, Y
2
=
010
. Множину розв’язкiв T
2
можна записати у виглядi
T
2
= α
1
010 + α
2
1
2
0
1
2
,α
1
≥ 0,α
2
≥ 0,α
1
+ α
2
=1,
або
T
2
=
1
2
α
2
α
1
1
2
α
2
,α
1
≥ 0,α
2
≥ 0,α
1
+ α
2
=1.
Приклад 2.8.3. Знайдемо всi розв’язки гри з матрицею виграшiв
A =
−13−3
203
210
.
Для цiєї матрицi
adj A =
−3 −39
66−3
27−6
.
Звiдки знаходимо
X =
1
3
2
3
0
,Y=
1
5
3
5
1
5
.
Iз 9 пiдматриць розмiрностi 2 × 2 лише одна дає розв’язок. Це матриця
B =
3 −3
03
,
для якої
X =
1
3
2
3
0
,Y=
0
2
3
1
3
.
137
Отже, гравець 1 має лише одну оптимальну стратегiю
X =
1
3
2
3
0
.
Гравець 2 має множину оптимальних стратегiй
T
2
= α
1
1
5
3
5
1
5
+ α
2
0
2
3
1
3
,α
1
≥ 0,α
2
≥ 0,α
1
+ α
2
=1.
2.8.1. Контрольнi запитання i задачi для самостiйної роботи
1. Яку геометричну iнтерпретацiю мають множини оптимальних стра-
тегiй гравцiв?
2. Сформулюйте i доведiть необхiднi та достатнi умови належностi
розв’язкiв множинам
K(T
1
), K(T
2
).
3. Опишiть алгоритм знаходження всiх розв’язкiв матричної гри?
4. Наведiть приклад матричної гри з бiльш, нiж одним розв’язком.
5. Чи може матрична гра мати нескiнченну кiлькiсть розв’язкiв?
Задачi
1. Знайти всi розв’язки iгор з матрицями виграшiв
A
1
=
210
012
,A
2
=
−13−3
203
210
,A
3
=
123
612
350
,
A
4
=
1 −1 −1
−1 −13
−12−1
,A
5
=
36
55
93
,A
6
=
64−619
103−5
202 3
−5 −216−35
.
2. Покажiть, що матричнi iгри мають єдиний розв’язок (a>b>c):
B
1
=
a 01
1 a 0
01a
,B
2
=
a 00
0 b 0
00c
.
138
3. Нехай G –гразматрицею
A =
ccc
c 34
c 51
.
При яких значеннях c множина T
1
буде нескiнченною?
При яких значеннях
c множина T
2
буде нескiнченною?
Покажiть, що цiна гри дорiвнює
c.
2.9. БIМАТРИЧНI IГРИ
Поняття антагонiстичної гри можна значно розширити. У конфлi-
ктнiй ситуацiї з двома учасниками їх iнтереси не завжди протилежнi.
Як модель такого конфлiкту визначимо гру двох осiб загального вигля-
ду. Нехай перший гравець має в своєму розпорядженнi стратегiї
x з
множини стратегiй
X, а другий гравець має в своєму розпорядженнi
стратегiї
y з множини стратегiй Y . Розглянемо гру в нормальнiй формi.
У такiй грi кожен учасник вибирає стратегiю, не знаючи вибору партне-
ра. Пара стратегiй
(x,y) називається ситуацiєю гри. Iнтереси першого
гравця характеризує функцiя виграшу
F (x,y), а другого – функцiя ви-
грашу
G(x,y), якi визначенi на множинi всiх ситуацiй X × Y .Кожен
гравець прагне, по можливостi, максимiзувати свою функцiю виграшу.
Таким чином, гра двох осiб в нормальнiй формi задається сукупнiстю
Γ=X,Y,F(x,y),G(x,y). В антагонiстичнiй грi поняття рiшення ми по-
в’язували з сiдловою точкою функцiї виграшу першого гравця. У довiль-
нiй грi двох осiб аналогом сiдлової точки є поняття ситуацiї рiвноваги.
Означення 2.9.1. Ситуацiя
(x
0
,y
0
) називається ситуацiєю рiвноваги
(рiвновагою Неша)гри
Γ,якщо
max
x∈X
F (x,y
0
)=F (x
0
,y
0
), max
y∈Y
G(x
0
,y)=G(x
0
,y
0
). (2.9.1)
Стратегiї
x
0
та y
0
, складовi ситуацiю рiвноваги, називатимемо рiвнова-
жними. Якщо обидва гравцi дотримуються ситуацiї рiвноваги, то одному
гравцю вiдхилятися вiд неї невигiдно.
Подивимось, як можна використовувати поняття рiвноваги Неша в
задачах приймання рiшень. В теорiї iгор, як i в багатьох iнших теорiях,
можна видiлити два пiдходи: нормативний i дескриптивний. Норматив-
ний пiдхiд полягає в тому, що теорiя дає рекомендацiї, як слiд дiяти в
тiй або iншiй конфлiктнiй ситуацiї. А при дескриптивному пiдходi теорiя
намагається описати, як насправдi вiдбувається взаємодiя мiж гравцями.
139
Спочатку теорiя iгор розвивалася як нормативна. Зараз ми обговоримо
поняття рiвноваги Неша саме з такої точки зору. В цьому випадку прави-
ло приймання рiшення можна сформулювати таким чином: у конфлiктнiй
ситуацiї, що описується грою в нормальнiй формi, кожному учаснику
слiд використовувати стратегiю, яка входить в рiвновагу Неша.
Ситуацiя рiвноваги в грi двох осiб може не мати тих властивостей, якi
характернi для сiдлової точки антагонiстичної гри. В антагонiстичнiй грi,
що має розв’язок, компоненти сiдловою точки являються максимiнною i
мiнiмаксною стратегiями гравцiв i, навпаки, будь-яка пара таких страте-
гiй утворює сiдлову точку. Таким чином, в антагонiстичнiй грi принцип
рiвноваги узгоджується з принципом оптимiзацiї гравцями своїх гаран-
тованих результатiв. Крiм того, в усiх сiдлових точках виграш першого
гравця один i той же i рiвний значенню гри. На жаль, в загальному
випадку ситуацiї рiвноваги не мають вказаних властивостей. Перекона-
ємося в цьому на прикладах. Перед цим дамо означення бiматричної
гри.
Означення 2.9.2. Гра двох осiб
Γ називається бiматричною,якщомно-
жини стратегiй гравцiв скiнченнi:
X = {1,...,m}, Y = {1,...,n},де
i ∈ X та j ∈ Y – стратегiї першого i другого гравцiв. Виграшi гравцiв
задаються двома матрицями
A = {F (i,j)}
m×n
= {a
ij
}
m×n
,B= {G(i,j)}
m×n
= {b
ij
}
m×n
.
Запишемо означення ситуацiї рiвноваги в термiнах бiматричної гри.
Означення 2.9.3. Ситуацiя
(i
0
,j
0
) бiматричної гри Γ називається ситу-
ацiєю рiвноваги (рiвновагою Неша), якщо
a
ij
0
≤ a
i
0
j
0
,i=1,...,m; b
i
0
j
≤ b
i
0
j
0
,j =1,...,n.
Тут елемент a
i
0
j
0
є максимальним в j
0
-му стовпцi матрицi A, а елемент
b
i
0
j
0
є максимальним в i
0
-му рядку матрицi B.
Чи завжди в грi двох осiб iснує ситуацiя рiвноваги? У загальному
випадку вiдповiдь – негативна, оскiльки, наприклад, в антагонiстичнiй
грi не завжди iснує сiдлова точка. Наведемо приклад неантагонiстичної
гри, що не має ситуацiї рiвноваги.
Приклад 2.9.1. Покупець (гравець 2) приходить на ринок за яблуками.
Продавець, що торгує яблуками (гравець 1), використовує пружинну
вагу. У нього є двi стратегiї:
1) чесно зважити 1 кг яблук;
2) пiдкрутити пружинки i обважити покупця на 200 грам.
Назвемо цi стратегiї “чеснiсть” i “обман” вiдповiдно.
Покупець також має двi стратегiї:
1) повiривши продавцю, заплатити грошi i пiти;
140