Моклячук М.П., Ямненко Р.Є. Лекції з теорії вибору та прийняття рішень (на укр. языке)
Подождите немного. Документ загружается.
азавизначенняммаксимуму
f(x,y) ≤ max
x∈A
f(x,y).
Отже,
min
y∈B
f(x,y) ≤ max
x∈A
f(x,y). (2.2.2)
Оскiльки лiва частина нерiвностi (2.2.2) не залежить вiд
y,то
min
y∈B
f(x,y) ≤ min
y∈B
max
x∈A
f(x,y). (2.2.3)
А так як права частина нерiвностi (2.2.3) не залежить вiд
x,матимемо
max
x∈A
min
y∈B
f(x,y) ≤ min
y∈B
max
x∈A
f(x,y).
Зауваження. Можливiсть застосування тверджень теореми до матриць
базується на тому, що матрицю
A =
a
11
a
12
... a
1n
a
21
a
22
... a
2n
... ... ... ...
a
m1
a
m2
... a
mn
можна розглядати як дiйсну функцiю двох змiнних f(i,j), що визначена
для
i =1,2,...,m та j =1,2,...,n рiвнiстю f(i,j)=a
ij
.
Наслiдок. Нехай
A =
a
11
a
12
... a
1n
a
21
a
22
... a
2n
... ... ... ...
a
m1
a
m2
... a
mn
−
довiльна матриця. Тодi
max
i
min
j
a
ij
≤ min
j
max
i
a
ij
.
Доведення. Доведення випливає з теореми 2.2.1, якщо прийняти за A
множину перших m,азаB множину перших n додатних цiлих чисел.
Для того щоб сформулювати необхiдну i достатню умову того, що
виконується рiвнiсть (1), зручно ввести нове поняття з теорiї дiйсних
функцiй двох змiнних.
Означення 2.2.1. Нехай
f(x,y) – дiйсна функцiя, яка визначена для всiх
x ∈ A та y ∈ B.Точка(x
0
,y
0
),деx
0
∈ A та y
0
∈ B, називається сiдловою
точкою функцiї
f(x,y), якщо виконуються такi умови:
101
1. f (x,y
0
) ≤ f(x
0
,y
0
) для всiх x ∈ A;
2.
f(x
0
,y
0
) ≤ f(x
0
,y) для всiх y ∈ B.
Наприклад, функцiя
f(x,y)=y
2
− x
2
має сiдлову точку (0,0),тому
що для всiх дiйсних
x та y
0
2
− x
2
≤ 0
2
− 0
2
≤ y
2
− 0
2
.
Цей приклад не дивний, тому що гiперболiчний параболоїд звичайно на-
зивається сiдлоподiбною поверхнею. Однак потрiбно помiтити, що наше
визначення сiдлової точки не збiгається з поняттям, яке вживається в
диференцiальнiй геометрiї. Наприклад, вiдповiдно до нашого визначен-
ня, функцiя
f(x,y)=x
2
− y
2
не має сiдлової точки.
Теорема 2.2.2. Нехай
f(x,y) – дiйсна функцiя, що визначена для x ∈ A
та y ∈ B,iнехайiснують
max
x∈A
min
y∈B
f(x,y), min
y∈B
max
x∈A
f(x,y).
Тодi необхiдна i достатня умова того, що
max
x∈A
min
y∈B
f(x,y)=min
y∈B
max
x∈A
f(x,y)
полягає в тому, що функцiя f (x,y) має сiдлову точку. Крiм того,
якщо
(x
0
,y
0
) є сiдловою точкою функцiї f(x,y),то
f(x
0
,y
0
)=max
x∈A
min
y∈B
f(x,y)=min
y∈B
max
x∈A
f(x,y).
Доведення. Доведемо достатнiсть умови. Нехай (x
0
,y
0
) єсiдловоюто-
чкою функцiї
f(x,y).Тодiдлявсiхx ∈ A та y ∈ B:
f(x,y
0
) ≤ f(x
0
,y
0
); (2.2.4)
f(x
0
,y
0
) ≤ f(x
0
,y). (2.2.5)
З (2.2.4) випливає, що
max
x∈A
f(x,y
0
) ≤ f(x
0
,y
0
),
а з (2.2.5) випливає, що
f(x
0
,y
0
) ≤ min
y∈B
f(x
0
,y).
Таким чином,
max
x∈A
f(x,y
0
) ≤ f(x
0
,y
0
) ≤ min
y∈B
f(x
0
,y). (2.2.6)
Оскiльки
min
y∈B
max
x∈A
f(x,y) ≤ max
x∈A
f(x,y
0
)
i
max
x∈A
min
y∈B
f(x,y) ≥ min
y∈B
f(x
0
,y),
102
то ми маємо з (2.2.6), що
min
y∈B
max
x∈A
f(x,y) ≤ f(x
0
,y
0
) ≤ max
x∈A
min
y∈B
f(x,y). (2.2.7)
Але за теоремою 2.2.1 перший елемент нерiвностi (2.2.7) не менший за
третiй. Звiдси ми маємо, що всi три елементи рiвнi. Що i потрiбно було
довести.
Щоб переконатися в тому, що умова необхiдна, припустимо, що
x
0
∈
A
– це такий елемент множини A,приякому
min
y∈B
f(x,y)
має максимальне значення, а y
0
∈ B – елемент множини B,приякому
max
x∈A
f(x,y)
має мiнiмальне значення. Iнакше кажучи, нехай x
0
∈ A, y
0
∈ B вiдпо-
вiдно елементи множин
A та B, що задовольняють умовам
min
y∈B
f(x
0
,y)=max
x∈A
min
y∈B
f(x,y); (2.2.8)
max
x∈A
f(x,y
0
)=min
y∈B
max
x∈A
f(x,y). (2.2.9)
Покажемо, що
(x
0
,y
0
) – це сiдлова точка функцiї f(x,y).Оскiлькими
припускаємо, що
max
x∈A
min
y∈B
f(x,y)=min
y∈B
max
x∈A
f(x,y),
тo з (2.2.8)–(2.2.9) випливає рiвнiсть
min
y∈B
f(x
0
,y)=max
x∈A
f(x,y
0
). (2.2.10)
З визначення мiнiмуму маємо
min
y∈B
f(x
0
,y) ≤ f(x
0
,y
0
),
отже, враховуючи (2.2.10), одержуємо
max
x∈A
f(x,y
0
) ≤ f(x
0
,y
0
).
З останньої нерiвностi i з визначення максимуму ми маємо, що для всiх
x ∈ A
f(x,y
0
) ≤ f(x
0
,y
0
).
А це є умова 1) визначення сiдлової точки. Аналогiчно доводиться умова
2).
Зауваження. Сiдлова точка матрицi A = {a
ij
} –цепарацiлихчисел
(i,j) таких, що a
ij
одночасно є мiнiмум i-го рядка та максимум j-го
стовпця. Наприклад, матриця
21 11 31
32 0 4
103
має сiдлову точку (1,2), тому що 11 – це найменший елемент у першому
рядку i найбiльший елемент у другому стовпцi. Матриця
12 13 12
10 31 9
має двi сiдловi точки (1,1) та (1,3).Матриця
12 13 12
10 31 13
має лише одну сiдлову точку, тому що 12 не є максимумом третього
стовпця.
Використовуючи поняття сiдлової точки, з теореми 2.2.2 отримуємо
наступний наслiдок.
Наслiдок. Нехай
A =
a
11
a
12
... a
1n
a
21
a
22
... a
2n
... ... ... ...
a
m1
a
m2
... a
mn
.
Необхiдною i достатньою умовою того, що
max
i
min
j
a
ij
=min
j
max
i
a
ij
є iснування сiдлової точки матрицi A, тобто iснування пари цiлих
чисел
(i
0
,j
0
),дляякихa
i
0
j
0
є одночасно мiнiмумом свого рядка i ма-
ксимумом свого стовпця. Крiм того, якщо
(i
0
,j
0
) –цесiдловаточка
матрицi
A,то
max
i
min
j
a
ij
=min
j
max
i
a
ij
= a
i
0
j
0
.
З наслiдку ми бачимо, що спiввiдношення (2.2.1) справедливе тодi
iтiлькитодi,колиматриця
A має сiдлову точку. Тому, якщо матриця
матричної гри має сiдлову точку
(i
0
,j
0
) (у цьому випадку ми будемо
говорити, що сама гра має сiдлову точку), то для
P
1
краще вибрати
стратегiю
i
0
,адляP
2
краще вибрати стратегiю j
0
.Вiдповiднодоцього
назвемо
i
0
та j
0
оптимальнимивиборамивiдповiднодляP
1
та P
2
,а
величину
a
i
0
j
0
–цiноюгри(длягравцяP
1
).
Так, наприклад, матриця
−53120
5 546
−4 −20−5
має сiдлову точку (2,3), тому що 4 є мiнiмумом другого рядка i максиму-
мом третього стовпця. При грi з такою матрицею оптимальним вибором
для
P
1
єстратегiя2,адляP
2
– стратегiя 3. Цiна гри дорiвнює 4.
104
Отже, для того випадку, коли матриця прямокутної гри має сiдлову
точку, ми одержуємо теорiю, що вказує, як завжди краще грати в цю
гру. Однак у нас залишається ще питання про те, як грати у гру з
матрицею, наприклад,
1 −7
−12
,
яка не має сiдлової точки. Це питання буде розглянуто у наступному
роздiлi.
2.2.1. Контрольнi запитання i задачi для самостiйної роботи
1. Що називають стратегiєю гравця?
2. Що таке виграш гравцiв i як вони вимiрюються у грi?
3. Що таке матрична гра двох гравцiв з нульовою сумою?
4. Що таке нижня та верхня цiни гри яке спiввiдношення мiж цими
величинами?
5. Що називають сiдловою точкою для дiйсної функцiї двох змiнних?
6. Що таке сiдлова точка гри i як вона визначається?
7. Сформулюйте i доведiть теорему про еквiвалентнiсть властивостi
iснування сiдлової точки i рiвностi
max
x
min
y
f(x,y)=min
y
max
x
f(x,y).
8. Якi стратегiї називаються мiнiмаксною i максимiнною?
Задачi
1. Знайдiть сiдловi точки для матриць
A
1
=
13
−210
,A
2
=
3524
2611
,
A
3
=
2222
1234
,A
4
=
2222
2234
.
2. Знайдiть нижню та верхню цiни гри для таких матриць:
A
4
=
−12 5
21−3
401
,A
5
=
136
213
621
,
105
A
6
=
3 −137
−1930
,A
7
=
5231
−134−1
.
3. Покажiть, що якщо (x
1
,y
1
) i (x
2
,y
2
) – це сiдловi точки дiйсної
функцiї, то сiдловими точками також будуть
(x
1
,y
2
) i (x
2
,y
1
).Що
це означає стосовно матриць?
4. Два гравцi вибирають одне iз цiлих чисел вiд 1 до
n.Якщопер-
ший гравець вибрав число
x, а другий гравець вибрав число y,
то перший отримує
x − y одиниць виграшу при x ≥ y та платить
x + y одиниць виграшу при x<y. Знайдiть матрицю гри, нижню
та верхню цiни та сiдловi точки.
5. Два гравцi вибирають одне число з множини
{−1,0,1}.Якщопер-
ший гравець вибрав число
x, а другий гравець вибрав число y,
то перший отримує
x(x − y)+y(x + y) одиниць виграшу. Знайдiть
матрицю гри, нижню та верхню цiни та сiдловi точки.
6. Два гравцi мають по
n доларiв та предмет цiною c. Кожний гравець
пропонує
k доларiв за предмет (робить заявку в закритому конвер-
тi). Гравець, який запропонував бiльшу суму, отримує предмет i
платить iншому суму яку вiн запропонував. Якщо гравцi пропо-
нують однакову суму, то предмет призначається без компенсацiї
одному з гравцiв шляхом пiдкидання монети. Знайдiть матрицю
гри, нижню та верхню цiни та сiдловi точки.
7. Гра “five-finger Morra” (п’ятипальцева Морра). Кожен з двох грав-
цiв показує вiд одного до п’яти пальцiв та одночасно називає кiль-
кiсть пальцiв, якi, на його думку, покаже супротивник. Якщо один
iз гравцiв вгадує, то вiн отримує суму, що пропорцiйна кiлькостi
пальцiв, показаних ним та його супротивником. В усiх iнших ви-
падках – нiчия. Знайдiть матрицю гри, нижню та верхню цiни та
сiдловi точки.
8. Кожний з двох гравцiв показує вiд 1 до 5 пальцiв. Загальна кiль-
кiсть показаних пальцiв дiлиться на три. Якщо сума дiлиться на
3 без остачi, то нiяких виплат не призначається. Якщо остача до-
рiвнює 1, то гравець А отримує суму, шо рiвна кiлькостi пальцiв,
показаних ним та його супротивником. Якщо остача дорiвнює 2, то
гравець В отримує суму, шо рiвна кiлькостi пальцiв, показаних ним
та його супротивником. Знайдiть матрицю гри, нижню та верхню
цiни та сiдловi точки.
106
9. Гра полковника Блотто. Полковник Блотто має 4 полки, а його
противник – 3 полки. Противник захищає двi позицiї. Позицiя бу-
де зайнята полковником Блотто, якщо на нiй наступаючi полки
будуть чисельно переважати. Протиборчим сторонам потрiбно роз-
подiлити полки мiж двома позицiями. Визначимо виграш полков-
ника Блотто (гравця 1) на кожнiй позицiї. Якщо у нього на позицiї
полкiв бiльше, нiж у противника (гравця 2), то його виграш на
цiй позицiї дорiвнює числу полкiв противника плюс один (зайнят-
тя позицiї рiвносильне захопленню одного полку). Якщо у гравця 2
полкiв на позицiї бiльше, нiж у гравця 1, то гравець 1 втрачає усi
свої полки на цiй позицiї та ще одну одиницю (за втрату позицiї).
Якщо ж обидвi сторони мають однакове число полкiв на позицiї, то
має мiсце нiчия i жодна iз сторiн нiчого не отримає. Загальний ви-
граш гравця 1 дорiвнює сумi виграшiв на обох позицiях. Знайдiть
матрицю гри, нижню та верхню цiни та сiдловi точки.
10. Умова така ж, як i в попереднiй задачi, але у полководця, який
обороняє мiсто, є 3 полки, а у його противника – 2 полки.
11. Гравцi 1 i 2 вибирають цiлi числа
i та j вiд 1 до n,прицьому
гравець 1 виграє величину
|i − j. Гра антагонiстична. Знайдiть ма-
трицю гри, нижню та верхню цiни та сiдловi точки.
12. Дуель. Гравцi рухаються назустрiч один одному на 5 крокiв. Пiсля
кожного зробленого кроку гравець може вистрiлити або нi, але пiд
час гри вiн може вистрiлити лише один раз. Вважається, що ймо-
вiрнiсть того, що гравець влучить у свого суперника при пострiлi
на
k-му кроцi, дорiвнює k/5(k ≤ 5). Знайдiть матрицю гри, нижню
та верхню цiни та сiдловi точки.
13. Гравець
P повинен шукати гравця Q водномуiзмiсцьA, B, C,
D.ГравецьQ зараз знаходиться в A, але цiною 1 одиницi може
перемiститися в
B або C, а цiною 2 одиниць – в D. Цiна перемi-
щення виплачується гравцю
P пiсля закiнчення пошукiв. Також вiн
отримує додатковi 3 одиницi, якщо знаходить гравця
Q.Знайдiть
матрицю гри, нижню та верхню цiни та сiдловi точки.
14. Кожен iз двох гравцiв вибирає одне з чисел мiж 1 i 9. Якщо число,
вибране одним iз гравцiв, на одиницю бiльше, нiж число, вибране
iншим, то перший гравець програє 2 одиницi. Якщо вибiр одного
iз гравцiв бiльший хоча б на 2 одиницi, нiж у другого, перший
гравець виграє 1 одиницю. У випадку, коли вибори чисел спiвпа-
дають, гра закiнчується нiчиєю. Знайдiть матрицю гри, нижню та
верхню цiни та сiдловi точки.
107
15. Довести, що матриця A =(a
ij
)
m
i=1
n
j=1
має сiдлову точку, якщо a
ij
=
i − j
.
16. Двоє однаково влучних гравцiв, один з яких (гравець 1) озброєний
безшумною рушницею, а iнший (гравець 2) – звичайною, роблять
5 крокiв до мiшенi. Ймовiрнiсть влучити на
k-му кроцi рiвна k/5.
Кожен iз гравцiв має лише по однiй кулi в рушницi, i тiльки гра-
вець 1 може почути пострiл гравця 2. Той, хто першим влучає в
мiшень, отримує одиницю виграшу вiд свого суперника. Якщо жо-
ден з гравцiв не влучив або обоє влучили одночасно, виграш обох
дорiвнює нулю. Знайдiть матрицю гри, нижню та верхню цiни та
сiдловi точки.
17. Два гравцi мають по
n гривень i предмет вартостi c. Кожний гра-
вець робить заявку в запечатаному конвертi, пропонуючи
k гри-
вень (
k –цiлечисловiд1доn) за предмет. Той, хто запропонував
бiльшу суму, отримує предмет i платить iншому гравцевi запропо-
новану суму. Якщо обидва гравцi пропонують одну i ту ж суму, то
предмет призначається без компенсацiї одному з гравцiв шляхом
пiдкидання монети, таким чином, очiкувана частка кожного гравця
в цьому випадку рiвна. Знайдiть матрицю гри, нижню та верхню
цiни та сiдловi точки.
18. Два гравцi незалежно один вiд одного вибирають одне iз чисел 1,
2, 3. Гравець, який вибрав менше число, виграє одне очко, якщо ви-
бране ним число менше числа, вибраного суперником, бiльш нiж на
одиницю; якщо воно менше на одиницю, то вiн програє 2 очки. У
випадку однакового вибору чисел пiдрахунок очок не проводиться.
Знайдiть матрицю гри, нижню та верхню цiни та сiдловi точки.
19. Довести, що матриця
A =(a
ij
)
m
i=1
n
j=1
має сiдлову точку, якщо a
ij
=
b
i
+ c
j
.
20. Iз чисел 1, 2, 3, 4, 5 випадково вибирається яке-небудь одне, i двом
гравцям пропонується вказати верхню межу для вибраного числа.
Якщо вгадав лише один iз гравцiв, то вiн отримує одиницю вiд
суперника. Якщо вгадали обидва, то одиницю вiд суперника отри-
має той, чия верхня границя строго менша. В усiх iнших випадках
нiхто з гравцiв не отримує нiчого. Знайдiть матрицю гри, нижню
та верхню цiни та сiдловi точки.
108
2.3. ОСНОВНА ТЕОРЕМА МАТРИЧНИХ IГОР. ЗМIШАНI
СТРАТЕГIЇ ГРИ
Розглянемо гру, що задається матрицею виграшiв
+1 −1
−1+1
.
Оскiльки ця матриця не має сiдлової точки, то методи, якi були ви-
кладенi в попередньому роздiлi, недостатнi для того, щоб знайти опти-
мальнi стратегiї гравцiв
P
1
та P
2
у цiй грi. Крiм того, не має значення
чи вибере
P
1
першу стратегiю чи другу, тому що в обох випадках вiн
одержить 1 чи
−1.Зiншогобоку,якщоP
2
знає, який вибiр зробить
P
1
,тоP
2
може грати так, що P
1
змушений буде заплатити йому 1 (для
цього вiн повинен зробити протилежний вибiр). Таким чином, виявляє-
ться, що для
P
1
дуже важливо зробити так, щоб P
2
було важко угадати,
який вибiр вiн має намiр зробити. Один зi способiв, яким
P
1
може цього
досягти, є випадковий вибiр.
Припустимо, наприклад, що
P
1
вирiшує зробити свiй вибiр шляхом
пiдкидання монети, вибираючи стратегiю 1, якщо монета показує герб,
i вибираючи стратегiю 2, якщо вона показує решку. У цьому випад-
ку, оскiльки ймовiрнiсть того, що
P
1
вибере першу стратегiю, дорiвнює
1/2, i ймовiрнiсть того, що вiн вибере другу, дорiвнює 1/2, математи-
чне сподiвання виграшу для
P
1
увипадку,якщоP
2
вибирає свою першу
стратегiю, дорiвнює
1 ·
1
2
+(−1) ·
1
2
=0
iвонобудетакимже,якщоP
2
вибере стратегiю 2. Отже, якщо P
1
виби-
рає стратегiю таким способом, то математичне сподiвання його виграшу
дорiвнює нулю незалежно вiд того, що вибирає
P
2
.
Дiйсно, це єдиний спосiб, яким
P
1
може грати в таку гру без ризику
програшу навiть у тому випадку, якщо
P
2
довiдається, який вибiр вiн
збирається зробити.
Припустимо тепер, що гравець
P
1
застосовує метод випадкового ви-
бору, який визначає, що ймовiрнiсть вибору 1 дорiвнює
x iймовiрнiсть
вибору 2 дорiвнює
1 − x.Припустимо,щоP
2
знає,якийвипадковийме-
ханiзм застосовує
P
1
. Тодi математичне сподiвання виграшу гравця P
1
,
при умовi, що гравець
P
2
вибирає 1, дорiвнює
(+1) · x +(−1) · (1 − x)=2x − 1,
аякщоP
2
вибирає 2, то математичне сподiвання виграшу гравця P
1
дорiвнює
(−1) · x +(+1)·(1 − x)=1−2x.
109
Якщо x>
1
2
,то1 − 2x<0 i математичне сподiвання виграшу P
1
,якщо
P
2
вибирає 2, менше нуля. Якщо x<
1
2
,то2x − 1 < 0 i математичне
сподiвання виграшу
P
1
,якщоP
2
вибирає 1, менше нуля.
Звiдси випливає, що оптимальний варiант гри в цю гру для гравця
P
1
(i для P
2
) – вибирати 1 чи 2, кожне з ймовiрнiстю 1/2.Цiнагридля
гравця
P
1
(тобто математичне сподiвання його виграшу, якщо вiн грає
оптимальним способом) дорiвнює нулю.
Розглянемо гру з матрицею виграшiв розмiрностi
m × n
A =
a
11
a
12
... a
1n
a
21
a
22
... a
2n
... ... ... ...
a
m1
a
m2
... a
mn
.
Означення 2.3.1. Змiшаними стратегiями гравцiв у матричнiй грi з
матрицею виграшiв
A розмiрностi m × n називаються розподiли ймовiр-
ностей на множинах чистих стратегiй гравцiв. Множину всiх змiшаних
стратегiй першого гравця позначимо через
S
m
=
X =(x
1
,...,x
m
):x
i
≥ 0,
i
x
i
=1
.
Вiдповiдно множину всiх змiшаних стратегiй другого гравця позначимо
через
S
n
=
Y =(y
1
,...,y
n
):y
j
≥ 0,
j
y
j
=1
.
Iнодi ми будемо називати самi числа 1,2,...,m чистими стратегiями
гравця
P
1
,ачисла1,2,...,n – чистими стратегiями гравця P
2
.Очеви-
дно, що для
P
1
гра з чистою стратегiєю k еквiвалентна грi зi змiшаною
стратегiєю
X =(x
1
,...,x
n
),деx
k
=1i x
i
=0для i = k.Якщоперший
гравець застосував змiшану стратегiю
X =(x
1
,...,x
m
), адругийгра-
вець застосував змiшану стратегiю
Y =(y
1
,...,y
n
),товиграшпершого
гравця визначається математичним сподiванням
E
(X,Y )=
m
i=1
n
j=1
x
i
a
ij
y
j
.
Означення 2.3.2. Якщо для деяких X
∗
∈ S
n
, Y
∗
∈ S
m
та для всiх
X ∈ S
n
, Y ∈ S
m
виконується нерiвнiсть
E
(X,Y
∗
) ≤ E(X
∗
,Y
∗
) ≤ E(X
∗
,Y ),
то X
∗
,Y
∗
називаються оптимальними змiшаними стратегiями гравцiв
у матричнiй грi з матрицею виграшiв
A,аE(X
∗
,Y
∗
) називається цiною
гри. Як i ранiше, цiна гри позначається через
v.
110