Раздел x теория игр 10.1. бескоалиционные игры нескольких лиц
Раздел 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г,Щз),...,Нк(.*),...,Нг(*)},
( г Л
к=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° в игре нет ни одной ситуации равновесия. •
Обсуждение Справочник по математике для экономистов
Комментарии, рецензии и отзывы