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

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

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

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

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

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

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

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

 

jt-i

Предположим, что Нк (s) (к = 1, 2, г) — выигрыш Д:-го игрока в ситуации sєS (если Нк (s)<Q, то к-й игрок проигрывает сумму, равную Нк Ш-

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

Любая бескоалиционная игра Г задается набором множеств чистых стратегий игроков Su Sk, .... Sr и функциями выигрышей этих игроков Я, (s),     Нк (s),     Н, (s), т. е.

r={Slt...,Sk       S„ Я, (s),     fyis)         #,(*)}.

 

О Пример. Имеется г производителей зерна, причем fc-й (Л = 1, 2, г) производитель зерна может производить зерно в объеме хк, ak^xk4ibk.

Зерно продается на рынке по сложившейся там цене р (у которая является убывающей функцией от совокупного предложения зерна у. Доход Л-го (к= 1, 2, г) производителя зерна равен

 

где ск (хк) — затраты к-го производителя на производство зері в объеме хк.

Если производители зерна не могут между собой договорит] ся, то каждый из них, независимо от других, выбирает объе производимого зерна хк. Значит,

Sk = {xkak^xk^bk)

 

является множеством чистых стратегий к-то производителя зерна.

Ситуация, складывающаяся на рынке зерна, характеризуется вектором s—(x,,     хк, .... хг), где xkeSk.

В рассматриваемом примере имеем бескоалиционную игру

Г={5,   Sk, .... S„ Я, (s) Нк (s),     Hr (s)},

 

где Sk={xkak^xk^bk}, Hk (s)=p ( £ xk] xk~ck (xk), s = (x{, xk,

.... x,y •

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

Г = {5„     Sk   S„ Hi (s),     Hk (s)      Hr {s)}

 

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

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

iHk(s) = d.

 

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

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

— {s!>      . ■■■> sL}, $2— {^її -і 4 •■■.-*„}.

Любая ситуация в биматричной игре Г имеет вид

s = (s, sj), seStt s]eS2.

Матрицы

где д^=Я, (jj, s\% Ьу=Нг{з, s)), i=, 2, m, j=, 2, и, называются платежными матрицами игры Г. Платежные матрицы А и В полностью определяют биматричную игру Г, т. е. Т = {А. В).

Биматричная игра Г={А, В) имеет следующую простую интерпретацию. Первый игрок выбирает номер строки і, второй игрок, независимо от первого, выбирает номер столбца j. После этого первый игрок получает выигрыш, равный аф а второй — выигрыш, равный by.

О Пример 1. Имеется два предприятия, которые выпускают

продукцию одного и того же назначения. Первое предприятие

может выпускать продукцию типов Аи Ah .... Ат с ценами

соответственно р    , pi       рт. Второе предприятие может выпу-

скать продукцию типов jt?i,..., Bp .... В„ с ценами соответственно

Ч          » Ч}. ■■■> Чп-

Если первое предприятие будет выпускать продукцию типа А{, а второе предприятие — продукцию типа Bp то сбыт найдут Сд единиц товара А<и d0 единиц товара типа Bp i=i, 2,т, 2, п.

Считая, что предприятия действуют независимо друг от друга, можно рассмотреть биматричную игру Г={А, В], где

 

/РС\--РСу... РСІЯ^

jqldn.:.qjdij...qndln

V

A =

Р£л...рРц ... pfi„ Prrfimi---Pnfirnj~- PnPm

 

I

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

г={5„ S2, я, 0), Н2 (л)}

является антагонистической, то для любой ситуации seS=Si x]s2 в этой игре справедливо равенство Н2 (s) = — Ht (s).

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

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

Если А = (а0)тхя — платежная матрица первого игрока в матричной игре^ Г, то матричную игру Г можно интерпретировать следующим образом. Первый игрок выбирает некоторую строку матрицы А, второй игрок — некоторый столбец этой матрицы. Если первый игрок выбрал і-ю строку, а второй игрок выбрал _/-й столбец, то второй игрок уплачивает первому игроку a,j единиц выигрыша, ф

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

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

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

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

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

ГС,Ац С,Ліз

A= c2ft21 сгИ12 CjAa c3a3, c3A32 с3л33 J

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

Если товар j-то (/ = ], 2, л) типа будет пользоваться спросом, то магазин от его реализации получит прибыль р}. Если же этот товар не будет пользоваться спросом, то убытки от его хранения составят qj.

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

 

А

 

-Чг Рг- ~Чг -о„ ~q„... р„

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

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

т={5„     Sk      S„ я, (s),     Нк (s),     Hf (s)},

где Su      Sk, .... Sr — множества чистых стратегий игроков,

а Н (s),     Нк (s),     Hr (s), seS= J}    — функции выигрышей

*-i

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

Рассмотрим некоторую ситуацию s = (slt sk^lt sk, sk+l, sr) в игре Г. Если £-й игрок вместо чистой стратегии sk применит чистую стратегию sk, а все остальные игроки оставят свои чистые стратегии без изменения, то возникнет новая ситуация

s II sk= (slt ■■■■> Sk-t, Sk, Sk+, S,).

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

я*(*1|^я,(*)-

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

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

 

J я^°11^я*(А (юл)

 

Hr(su\}sr)^Hr(s\%

К.

где seS         ts'keSk,....,s'reSr.

Неравенства (ЮЛ) показывают, что ни одному из игроков невыгодно отклоняться от ситуации равновесия, если другие игроки от нее не отклоняются. В частности, ситуация j=(j J, sj) является ситуацией равновесия в биматричной игре Г с платежными матрицами А = (а^тх„ и В=(ЬІ;)„Х„ тогда и только тогда, когда для ї=, 2,     m,        2, я

 

bif 4, by.

 

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

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

В ситуации s—(x, у) первый игрок получает сумму Я, (х, у)= — х2+ху, а второй игрок — сумму Н2 (х, j>)= — х2 + 2ху. Ситуация s= (1/4, 1/2) приемлема для первого игрока, так как

Я, (х, 1/2)--*г + х/2=-(х-1/4)2 + 1/16^1/16 = Я1 (V,, ЧгУ

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

Я2(7<, Vz)= -1/16+1/4 = 3/16, Я2 (1/4, 1)=-1/16 +1/2 = = 7/16>Н2(\% ЧгУ

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

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

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

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

Если sk (к=1, 2, г) — количество товара, производимого к-м предприятием, то общее количество товара на рынке равно

£ sk, а цена единицы товара max {[а — Ь ^£ sk^j], 0}.

При этих условиях можно рассмотреть бескоалиционную игру

Г-{5„    Sk       Sr. Я, (s),Як (з), :.. Яг

где

= 1 /o + Ci+C; + ... + Ct

~l       k+l Ckf

Sk = {sk 0^sk<oo}, Нк (j)=jtmax {[a-b (f, sk^], 0}-ckxk (k=l, 2,..., r). Положим для к — 1, 2, r a*

Вектор s0 = (s°t,     s°k         s°)> где

rak, если ak>0, (0, если а*^0,

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

В частности, если рассматриваются только четыре предприятия, причем а — 20, Ь=, А =4, с2 = 6, с3=10, с4 = 12, то ОС] = 8, a2 = 4, а3 = 0, я4= —8/5. Значит, в данном случае s° = (8,4, 0, 0) — ситуация равновесия. #

 

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