Раздел x теория игр 10.1. бескоалиционные игры нескольких лиц
Раздел 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) — ситуация равновесия. #
Обсуждение Справочник по математике для экономистов
Комментарии, рецензии и отзывы