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

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

Раздел x теория игр 10.1. бескоалиционные игры нескольких лиц

Предположим, что в некоторой конфликтной ситуации сталкиваются интересы г участников (игроков), каждый из которых имеет в своем распоряжении определенное множество возможных действий (ходов).

Возможные действия того или иного игрока называются чистыми стратегиями этого игрока.

Бескоалиционная игра г лиц состоит в следующем: каждый из г игроков выбирает свою чистую стратегию и выигрывает (проигрывает) определенную сумму в зависимости от того, какие чистые стратегии выбрали все игроки.

Обозначим через Sk (к = 1, 2,г) множество всех чистых стратегий к-то игрока в бескоалиционной игре Г. Вектор s = (sv sk,

5Г), где sk є Sk,k = 1,2,г, называется ситуацией в игре Г. Если S — множество всех ситуаций в игре Г, то S является декартовым произведением множеств Sv Sk,

s = f[sk.

k=l

Предположим, что Hk(s) (k = l, 2,r) — выигрыш к-то игрока в ситуации 5 є S (если Hk(s) < 0, тогда к-й игрок проигрывает сумму, равную Hk(s)).

Функция Hk(s), определенная на множестве іУвсех ситуаций в игре Г, называется функцией выигрыша k-то игрока.

Любая бескоалиционная игра Г задается множествами чистых стратегий игроков Sv Sk, Sr и функциями выигрышей этих игроков H^s),Hk(s),Hr(s):

r = {Sv    Sk,Sr, Щз),Hk(s),Hr{s)}.

 

282

Г--^,Sk,

5г,Щз),...,Нк(.*),...,Нг(*)},

( г Л

Подпись: хк ~ ск(хк)>   s — (XV
Подпись: Hk(s),...,Hr(s)}
где Sk = {хк ак<хк< bk),   Hk(s) = р

к=1 )

Хк' '"' Хг)' *

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

T = {Sv...,Sk,...,Sr,Hl(s),

называется конечной, если все множества чистых стратегии игроков Sv Sk,Sr конечны, и бесконечной, если хотя бы одно из этих множеств бесконечно.

Бескоалиционная игра называется игрой с постоянной суммой, если существует число d такое, что для всех ситуаций s є S в этой игре выполняется равенство

 

к=

В частности, игра Г является игрой с нулевой суммой, если для всех ситуаций s е S

Хвд = о.

к=1

283

10.2. Бескоалиционные игры двух лиц

Конечная бескоалиционная игра двух лиц называется бимат-ричной игрой. В биматричной игре

r = {Sl,S2,Hl(s),H2(s))

множества чистых стратегий игроков Sx и S2 являются конечными множествами, т.е.

*$1 = is\> •••» s\> •••» sm}'    ^2 = {^l> "•'      •"' Sn^'

Любая ситуация в биматричной игре Г имеет вид s=(s],sj),  s]eSv sfeS2.

Матрицы

 

 

Ґап .

■ (hi ■

■ <

 

Чі •

■ hj ■

•• к:

А =

аа .

■   "у ■

а-

in

, в =

Аі •

■ h ■

 

 

 

■   amj ■

 

 

 

 

l

mn j

где atJ - Hx(s), sj), by = H2(s), sj), і = 1,2,..., m;j = 1,2,..., n, называются платежными матрицами игры Г. Платежные матрицы А и В полностью определяют биматричную игру Г, т.е. Г = {А, В}.

Биматричная игра Г = {А, В} имеет простую интерпретацию: первый игрок выбирает номер строки /, а второй игрок, независимо от первого, — номер столбца j. После этого первый игрок получает выигрыш, равный atj, а второй — выигрыш, равный Ъ~.

О Пример. Имеется два предприятия, которые выпускают продукцию одного и того же назначения. Первое предприятие может выпускать продукцию типов Av А.,Ат с ценами соответственно pv р., рт. Второе предприятие может выпускать продукцию типов Вр    Bj,Вп с ценами соответственно qv    qJ}qn.

Если первое предприятие будет выпускать продукцию типа А., а второе предприятие — продукцию типа В}, то сбыт найдут с у единиц товарами dH.единиц товара В., i= 1, 2,m;j= 1, 2,п.

 

284

Бескоалиционная игра двух лиц с нулевой суммой называется антагонистической игрой. Если игра

r = {Sl,S2,Hl(s),H2(s)}

является антагонистической, то для любой ситуации s є S=Sx x S2 в этой игре справедливо равенство

 

В антагонистической игре то, что выигрывает один игрок, обязательно проигрывает другой игрок. В частности, если биматрич-ная игра Г = {А, В) является антагонистической, то В = -А.

Чтобы задать антагонистическую биматричную игру, достаточно указать только одну матрицу — платежную матрицу первого игрока. Антагонистическая биматричная игра называется матричной игрой.

Если А = (fly)m хп — платежная матрица первого игрока в матричной игре Г, то матричную игру Г можно интерпретировать следующим образом: первый игрок выбирает некоторую строку матрицы А, второй игрок — некоторый столбец этой матрицы. Если первый игрок выбрал і'-ю строку, а второй — j-й столбец, то

второй игрок уплачивает первому игроку а.. единиц выигрыша. •

и

О Пример. Фермер может посеять одну из трех культур Av А2 или Ау Так как урожаи этих культур во многом зависят от погоды, то можно рассмотреть игру двух лиц: фермера и природы.

Первый игрок (фермер) имеет три чистые стратегии: посеять культуру Ау, посеять культуру А2 или посеять культуру Ау

Будем считать, что второй игрок (природа) также имеет три чистые стратегии: погода засушливая (Вх), нормальная (В2) или дождливая (ВЛ. Естественно предположить, что на основании опыта известна урожайность той или иной культуры в зависимости от погодных условий.

285

Пусть hy (і = 1, 2, 3;у = 1, 2, 3) — урожайность (количество центнеров, полученных с одного гектара) культуры А. при погодных условиях В., а с. (/ = 1,2, 3) — прогнозируемая цена одного центнера культуры А..

Если фермер намерен получить наибольший доход при самых неблагоприятных погодных условиях, то имеет место матричная игра с платежной матрицей

А =

 

С3Л32

С3Л33У

О Пример. На складе торговой организации имеется п типов одного товара. В магазин должен быть завезен только один из и типов товара. Требуется выбрать тот тип товара, который целесообразно завезти в магазин.

Если товару'-го типа (у = 1, 2,и) будет пользоваться спросом, магазин от его реализации получит прибыль р.. Если же этот товар не будет пользоваться спросом, убытки составят q..

В условиях неопределенного покупательского спроса данная задача сводится к матричной игре, в которой первый игрок — магазин, а второй игрок — покупательский спрос. Каждый игрок имеет по п чистых стратегий. Завоз г-го товара — г-я стратегия первого игрока, спрос на у-й товар — у-я стратегия второго игрока. Платежная матрица игры имеет вид

 

 

А =

Pi

-9i Pi

-їх

-92

 

PnJ

10.3. Ситуации равновесия в бескоалиционных играх

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

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

г

a Hx(s),Hk(s),    Hr(s),  s є S = Y\_Sk> ~ функции выигрышей этих игроков. 286

Рассмотрим некоторую ситуацию

s = (sv    skV sk, sk+l,

в игре Г. Если к-й игрок вместо чистой стратегии sk применит чистую стратегию s'k, а все остальные игроки оставят свои чистые стратегии без изменения, то возникнет новая ситуация

s II Sk~ (SV      Sk-V Sk> Sk+V S)-

Говорят, что ситуация s є S приемлема для к-то игрока, если при любой чистой стратегии s'k этого игрока справедливо неравенство

Hk(s\s'k)<Hk(s).

Ситуация s° є S, приемлемая одновременно для всех игроков, называется ситуацией равновесия в бескоалиционной игре.

Ситуация 5° є Sявляется ситуацией равновесия в бескоалиционной игре Г тогда и только тогда, когда

Я^0 || ф < Щ*°),

 

■ Hk(s° || s'k) < Hk(s°), (10.1)

 

Hr(s° I s'r) < Hr(s°),

mes[e Sp ...,s'ks Sk, ...,s're Sr.

Неравенства (10.1) показывают, что ни одному из игроков невыгодно отклоняться от ситуации равновесия, если другие игроки от нее не отклоняются. В частности, ситуация s = (s4, sj) является ситуацией равновесия в биматричной игре Г с платежными матрицами А = (a.) v „ и В = (b.) v „ тогда и только тогда, когда для

If /71 / FI    II fit л Л

г"=1,2, ...,«;/= 1,2, ...,и

avj * ар

W £ V

Важнейшей задачей в теории бескоалиционных игр является задача отыскания ситуаций равновесия. Однако далеко не каждая бескоалиционная игра имеет хотя бы одну ситуацию равновесия.

 

287

О Пример 1. Первый игрок выбирает некоторое число х є [0,1], второй игрок, независимо от первого игрока, выбирает число у є [0,1].

В ситуации s = (х, у) первый игрок получает сумму Нуіх, у) = = -х2 + ху, а второй игрок — сумму Н2(х, у) = -х2 + 2ху.

Ситуация s = (1/4; 1/2) приемлема для первого игрока, так как

Щ{х, 1/2) = -X2 + х/2 = -(х - 1/4)2 + 1/16 < 1/16 = Щ1/4, 1/2).

Однако эта ситуация не является приемлемой для второго игрока, так как

Я2(1/4, 1/2) = -1/16 + 1/4 = 3/16,

Я2(1/4, 1) = -1/16 + 1/2 = 7/16 > Я2(1/4, 1/2).

С другой стороны, нетрудно проверить, что ситуация s° = (1/2; 1) является ситуацией равновесия в данной игре. •

О Пример 2. Имеется г предприятий, которые выпускают товар одного вида. Цена единицы товара зависит от общего количества Р этого товара на рынке и равна тах{а - РЬ; 0}, где аиЬ — положительные числа.

Себестоимость единицы товара для к-то предприятия (к =1,2, ...,/•)равнаск,причемсх<сг< ...<сг<а.

Предполагается, что производственные мощности предприятий не ограничены и они независимо друг от друга выбирают количество производимого товара. Цель каждого предприятия — получить наибольшую прибыль.

Если s, (к= 1, 2,г) — количество товара, производимого к-м

К г

предприятием, то общее количество товара на рынке равно ^sk,

 

а цена единицы товара max-! а - b^sk; 0

При этих условиях можно рассмотреть бескоалиционную игру r = {Sv    Sk,Sr, Щз),Hk(s),Hr(s)},

где

^=К|0<^<оо},

Hk(s) - sk rnaxja - b^sk; 0 j - ckxk  (k - 1,2,r).

 

288

Положим для к - 1, 2,г

-с,

1 ( а + Су + с2 +... + ск ^

к +

ВеКТОр 5° = (Sy,     s°k,s°r), где

 

Si. =

їак, еслиос^. > О, [О,    если ак < О,

является ситуацией равновесия в игре Г.

В частности, если рассматриваются только четыре предприятия, причем а = 20, Ъ = 1, с, = 4, с2 = 6, с3 = 10, с4 = 12, то о^ = 8, ос2 = 4, а3 = 0, а4 = -8/5. Значит, в данном случае s° = (8; 4; 0; 0) — ситуация равновесия. •

10.4. Ситуации равновесия в антагонистических играх

Дана антагонистическая игра

Г= {Sv S2, HyiSy, s2), H2(Sy, s2)},

где Sy, S2 — множества чистых стратегий игроков, a Hy(Sy, s2) и H2(Sy, s2), Sy є Sy, s2 є S2, — функции выигрышей этих игроков, причем H2(Sy, s2) = -Hy{Sy, s2).

Основные утверждения о ситуации равновесия в антагонистических играх:

Г. Ситуация (Sy, s2) является ситуацией равновесия в антагонистической игре Г тогда и только тогда, когда (Sy, s2) — седловая точка функции выигрыша Hy{Sy, s2), т.е. для любых чистых стратегий Sy є SyHS2s S2 выполняется неравенство

Hy(sy, s°2) < Hy(s°y, s°2) < Hy(s°y, s2). (10.2)

Из неравенства (10.2), в частности, следует, что для любых ситуаций равновесия (Iy,s2) и (Sy, s2) в антагонистической игре Г имеет место равенство

Ну(їу°,ї2°) = Ну(зї,з02).

Если (Sy, s2) — ситуация равновесия в антагонистической игре Г, то Sy называется оптимальной чистой стратегией первого игрока, s2 — оптимальной чистой стратегией второго игрока, а число Hy(Sy, j2) — ценой игры Г.

289

2°. Если в антагонистической игре Г первый игрок применяет свою чистую стратегию sv то в любом случае он выиграет не меньше, чем inf /^(jjjSj). Поэтому первый игрок постарается

выбрать свою стратегию так, чтобы inf H^s^s^ был как можно

S2^S2

больше.

Второй игрок, применяя свою чистую стратегию s2, проиграет не больше sap H^s^s^. Поэтому второй игрок попытается

выбрать свою стратегию s2 так, чтобы sup Hfa, s2) был как можно

меньше.

Для любой антагонистической игры Г справедливо неравенство

sup(inf H](sbs2))< inf {sap Hy{sbs2)).

 

3°. Антагонистическая игра Г имеет хотя бы одну ситуацию равновесия тогда и только тогда, когда существуют max( inf H^s^s^), птт(8ирУУ1(51,л,2))иони равны между собой.

4°. Для того чтобы ситуация s° = s2) являлась ситуацией равновесия в антагонистической игре Г, необходимо и достаточно, чтобы выполнялось равенство

inf Щ^,^) = sup Hfasl).

s2eS2 ^eij

О Пример. Первый игрок выбирает некоторое число х є [0, 1], второй игрок, независимо от первого, выбирает число у є [0,1].

В ситуации s = (х, у) второй игрок уплачивает первому игроку выигрыш, равный (х-у)2.

Рассмотрим антагонистическую игру

r={S1,S2,Hl(?c,y),H2(?c,y)},

где

^ = {х|хе [0,1]}, S2 = {yye [0,1]}; Щ(х, у) = (х- у)2,  Щх, у) = -Щх, у).

Так как

inf        у) = inf (х - у)2 = 0,

ysS2 У^2

290

то

max( inf Hx(x, у)) = 0.

С другой стороны,

„,    .       ,      ,2   fa-У) если0<^<1/2, sapHx(x, у) = sup(x - у) =

xsSi    xsSx   [у s    ЄСЛИ1/2 < у < 1.

Поэтому

min(supir1(x, у)) = 1/4.

 

Так как

max( inf Hx{x, у)) Ф min(sup Нх(х, у)),

 

то согласно утверждению 3° в игре нет ни одной ситуации равновесия. •

 

Страница: | 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 |