Имя материала: Справочник по математике для экономистов

Автор: В.И. Ермаков

10.7. смешанные расширения конечных бескоалиционных игр

Дана конечная бескоалиционная игра /"лиц

T = {SV    Sk,Sr, Щз),Hk(s),Hr(s)}, где Sv    Sk,Sr — конечные множества чистых стратегий игро-

г

ков, aHy(s),Hk(s),Hr(s), s є S = Y\_^k ~ функции вьшгрьппей

k=l

этих игроков.

Если в игре Г нет ни одной ситуации равновесия, то имеет смысл рассмотреть смешанное расширение этой игры.

Предположим, что игроки выбирают свои чистые стратегии случайным образом. Любое вероятностное распределение на множестве чистых стратегий того или иного игрока называется смешанной стратегией этого игрока. Таким образом, смешанная

293

стратегия игрока — это вектор, координаты которого соответственно равны вероятностям (частотам), с которыми игрок применяет свои чистые стратегии.

Вектор, размерность которого равна числу чистых стратегий игрока, является смешанной стратегией этого игрока тогда и только тогда, когда все координаты вектора неотрицательны, аих сумма равна единице.

Любой набор вида

ст = (o-j,ок,аг),

где ак (к = 1,2,г) — некоторая смешанная стратегия к-то игрока, называется ситуацией в смешанных стратегиях.

Если задана некоторая ситуация а = (ор ок,аг) в смешанных стратегиях, то тем самым указаны вероятности, с которыми тот или иной игрок выбирает свои чистые стратегии. В этом случае можно определить вероятность р (s) появления любой ситуации s = (sv sk,в чистых стратегиях (для этого достаточно перемножить вероятности применения игроками чистых стратегий sk,s^.

Обозначим через Нк(<з) математическое ожидание выигрыша (средний выигрыш) к-то игрока (к = 1, 2,г) в ситуации а = (av ок,стг). Тогда

Hk(o) = ^Hk(s)pa(s).

seS

Если Zj,Ег — множества смешанных стратегий игроков, то Нк(а) является функцией, определенной на множестве

 

*:=1

Бескоалиционная игра а* лиц

Г =     Ък,Ъг, Ща),Нк(о),ЯДо-)}

называется смешанным расширением конечной бескоалиционной игры

Г = {Sv    Sk,Sr, H,(s),Hk(s),Hr(s)}.

Основные свойства смешанных расширений:

Г. Смешанные расширения стратегически эквивалентных игр сами стратегически эквивалентны.

 

294

2°. Смешанное расширение антагонистической игры также является антагонистической игрой.

О Пример 1. Дана биматричная игра Г с платежными матрицами

 

Любая смешанная стратегия первого игрока имеет вид

 

гдер{ (/ = 1, 2, т) — вероятность, с которой первый игрок применяет г'-ю чистую стратегию.

Любая смешанная стратегия второго игрока имеет вид

o2 = (qv ->Qj> •••>?«)' где q. (j = 1, 2,и) — вероятность, с которой второй игрок применяет у-ю чистую стратегию.

Если -йГі(а), Й2(а) — математические ожидания выигрышей соответственно первого и второго игроков в ситуации о = (о,, а2), то

т  п    т п

Що) = ХХаі/^' н2(°) = XLV/ffy

i=l7=1         1=17=1

Смешанным расширением биматричной игры Г является бескоалиционная игра двух лиц

f = {Z1,Z2, ^(о),^)},

где

si = |°i = (Pi> •••» А» •••» Рт) I 2А =   Л - °»' =   2> WJ' Е2 = |ст2 = (ft- •■•» «у» ••■»?„) I Jjlj = Ъ 9j ^ 0,7 = 1,2,л j. •

О Пример 2. Дана бескоалиционная игра трех лиц Г = {Sv S2, Sy Щ*), H2(s), H3(s)}, в которой каждый из игроков имеет по две чистые стратегии, т.е. Si = {xvx2),  S2 = {yvy2),  S3 = {zvz2}.

 

295

Смешанным расширением игры Г является бескоалиционная игра

Г = {Zl5 Z2, Z3, ^(о), 7/2(а), Яз(о)},

где

Et =     = (pv р2) I^ +p2 = 1, ^ > 0, p2 > 0},

Z2 = {CT2 =     q2) ql + q2=l,ql> 0, o2 > 0},

I3 - {a3 - irv r2) гу + г2-,Гу> 0, r2 > 0},

Ще) - і/зд/j + Ipyqfo + Ір^2г2 + p2q2rx + 2p2q2r2,

Й2(а) = р$хг2 + 2тіг + UWi + 1/W2> Що) = Iptfft + 2р$2г2 + p2qxr2, a = (cs1,G2,cs3). •

 

10.8. Ситуации равновесия в смешанных стратегиях

Дана конечная бескоалиционная игра г лиц

T = {SV    Sk,Sr, Hft),Щз),Hr(s)}.

Если gv    ак,gr — некоторый набор смешанных стратегий

игроков, аЙк(а) (к- 1, 2,г) — математическое ожидание выигрыша А:-го игрока в ситуации a = (a1;о~к,о~г), то

Йк(о)=   X Bk(s)-pa(s)> *<=ПА

 

296 где р (s) — вероятность появления ситуации s в чистых стратегиях при условии, что игроки придерживаются своих смешанных стратегий ст1;ск,ог.

Ситуация ст° = (Oj,a°k_v а°к, a°k+v ст°) в смешанных стратегиях называется приемлемой для к-то игрока, если для любой смешанной стратегии о~к этого игрока

#fc(o° || ак)<Йк(с°),

где

ст || ак= (стр    <sk_v ак, стш,стг).

Любую чистую стратегию sk к-то игрока можно отождествить со смешанной стратегией 1к этого игрока, в которой вероятность применения чистой стратегии sk равна единице, а вероятности применения всех остальных чистых стратегий равны нулю.

Ситуация ст° в смешанных стратегиях является приемлемой для к-то игрока тогда и только тогда, когда для всех чистых стратегий sk этого игрока

Йк(с° \їк)<Йк(а°).

Ситуация ст° называется ситуацией равновесия игры Г в смешанных стратегиях, если эта ситуация приемлема для всех игроков.

Принципиально важное значение в теории игр имеет следующая теорема.

Теорема Нэша. Любая конечная бескоалиционная игра г лиц имеет хотя бы одну ситуацию равновесия в смешанных стратегиях.

 

Основные свойства ситуаций равновесия в смешанных стратегиях:

Г. Ситуация ст° является ситуацией равновесия игры Г в смешанных стратегиях тогда и только тогда, когда ст° — ситуация равновесия смешанного расширения игры Г.

2°. Стратегически эквивалентные бескоалиционные игры имеют одни и те же ситуации равновесия в смешанных стратегиях.

3°. Если s° = (jj,sk,s0) — ситуация равновесия бескоалиционной игры Г в чистых стратегиях, то смешанные стратегии їу,...,!®,...,!® образуют ситуацию равновесия этой игры в смешанных стратегиях.

297

Если Г — биматричная игра с платежными матрицами А -- (а9)тхя кВ = (Ьу)тхя, то смешанные стратегии ст° = (pv р(, ...,/>„,), о2 = (qv ...,qj, —,q„)образуют ситуацию равновесия игры Г тогда и только тогда, когда

/ = 1,2,..

y=i «=U=i

,т,

 

(10.3)

 

В данном случае система неравенств (10.3) принимает вид fli ^ l#fli + 2/>2д2>

(10.4)

2^2 ^ + 2^2ff2> 2ру < 2pxqx + 1/>202,

р2 < 2р$х + lp2q2,

где ах = (pvp2), о2 = (qv q2) — смешанные стратегии соответственно первого и второго игроков. Из определения смешанных стратегий следует, что р2 = 1 - pv 0 <рх < 1, q2 = 1 - qv 0 < qx < 1. Тогда систему неравенств (10.4) можно записать в следующем виде:

(3^ - 2)(Л -1) > 0,

(10.5)

p1(3ql-2)>0,

(3Л-1)(?1-1)>0,

?1(3Л-1)>0,

те0<рх<1, 0<^< 1.

Система неравенств (10.5) имеет три решения:

а) Рх = 0, qx = 0;  6)^ = 1,^ = 1;  в) ^ = 1/3, ^ = 2/3.

Таким образом, ситуация а0 = (ах, а2) является ситуацией равновесия игры Г в смешанных стратегиях, если:

а) о° = (0; 1), а2° = (0; 1);  б) о? = (1; 0), о2° = (1; 0);

в) о1° = (1/3;2/3),о2° = (2/3; 1/3). •

 

298 10.9. Матричные игры: ситуация равновесия в смешанных стратегиях

Дана матричная игра Г с платежной матрицей А = (а.ртхп. Смешанные стратегии первого и второго игроков в игре Г имеют соответственно вид

Gx = (pv      -,Рт),   C2 = (°i> ->fy •••>?„)>

где

т п

^Pi = 1, Pi > О, і = 1,2,т; = 1, q3 > О, j = 1,2,п.

i=i j=i

Если Й^Оу, а2) — математическое ожидание выигрыша первого игрока в ситуации а = (ар а2), то

/и и i=ly=l

причем

#2(^,02) = ст2).

Ситуация а0 = , а2) является ситуацией равновесия матричной игры Г в смешанных стратегиях тогда и только тогда, когда

 

для любых смешанных стратегий o~v а2 первого и второго игроков.

Любая матричная игра имеет хотя бы одну ситуацию равновесия в смешанных стратегиях.

Смешанные стратегии а® и а2 соответственно первого и второго игроков являются оптимальными смешанными стратегиями этих игроков, если а0 - , ст2) — ситуация равновесия. Число Й^а®, а2) — цена матричной игры Г.

По платежной матрице А = (о^)тхи можно построить взаимно двойственные задачи линейного программирования:

л т

f = ^х/тах),  ф = ХуДгпіп),

7=1 1=1 л т

^aijXj < 1,   / = 1,2,т,  (10.6)   ^аі]Уі > !> J = l> 2> •••» и> (10-7)

7=1 i=l

ху>0,   у'=1,2,п;    yt>0, i=,2,...,m.

299

Задачи (10.6) и (10.7) обязательно имеют оптимальные решения, если все элементы матрицы А - (Оу)тх„ положительны.

Если же взаимно двойственные задачи (10.6) и (10.7) имеют соответственно оптимальные решения

являются оптимальными смешанными стратегиями первого и второго игроков в матричной игре Г с платежной матрицей А = (atj)mxn,

а число —-— = —  цена этой игры.

 

j=l i=l

В случае когда взаимно двойственные задачи линейного программирования (10.6) и (10.7) не имеют оптимальных решений, вместо игры Г можно рассмотреть матричную игру Г с платежной

матрицей А - (ау + к)тхп, где ац + к > 0, і = 1,2,т; j = 1,2,п, так

как в играх Г и Г одни и те же оптимальные смешанные стратегии игроков.

 

О Пример. Дана матричная игра Г с платежной матрицей

" 0   -2     7 4^ А= -1     1 4-2

, 2     0   -1 lJ

Прибавив к каждому элементу матрицы А число 3, получим матрицу

{Ъ   1   10 7^ 2   4    7 1 5   3    2 4

J

все элементы которой положительны. По матрице А построим взаимно двойственные задачи линейного программирования:

 

300

Подпись: (?=yl+y2+y3(min), ' 3Уі + 2у2 + 5у3 >1, Уі + 4y2 + Зу3 > 1, 10^+7^ + 2^ >1, ІУі + У2+ 4y3 * h y.>0,/=l,2, 3./= Xy+x2 + x3+ x4(max),

(10.10)

3xy + x2 + 10x3 + 7x4 < 1, 2xj + 4x2 + 7x3 +  x4 < 1, (10.9) 5xj + 3x2 + 2x3 + 4x4 < 1,

 

xy>0,; = l,2, 3,4;

Решив задачи линейного программирования (10.9) и (10.10), получим их оптимальные решения:

а0 = (0; 3/13; 0; 1/13),  р° = (0; 1/13; 3/13).

С помощью равенств (10.8) можно записать оптимальные смешанные стратегии в матричной игре Г. Получим, что o"j = = (0; 1/4; 3/4) — оптимальная смешанная стратегия первого игрока, а ст2 = (0; 3/4; 0; 1/4) — оптимальная смешанная стратегия второго игрока.

Цена игры Г с платежной матрицей А равна 13/4. Тогда цена исходной игры Г такова: (13/4) -3 = 1/4.*

 

Страница: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 | 101 | 102 | 103 | 104 | 105 | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | 121 | 122 | 123 | 124 | 125 | 126 | 127 | 128 | 129 | 130 | 131 | 132 | 133 | 134 | 135 | 136 | 137 | 138 | 139 | 140 | 141 | 142 | 143 | 144 | 145 | 146 | 147 | 148 | 149 | 150 | 151 | 152 | 153 | 154 | 155 | 156 | 157 | 158 | 159 | 160 | 161 | 162 | 163 | 164 | 165 | 166 | 167 | 168 | 169 | 170 | 171 | 172 | 173 | 174 | 175 | 176 | 177 | 178 | 179 | 180 | 181 | 182 | 183 | 184 | 185 | 186 | 187 | 188 | 189 | 190 | 191 | 192 | 193 |