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

Раздел x теория игр 10.1. бескоалиционные игры нескольких лиц: Справочник по математике для экономистов, В.И. Ермаков, 2009 читать онлайн, скачать pdf, djvu, fb2 скачать на телефон Содержит материал, позволяющий анализировать экономические задачи и осуществлять расчеты. Отражены разделы линейной алгебры, математического программирования, сетевое программирование и планирование, обработка результатов измерений, статистический анализ.

Раздел 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° в игре нет ни одной ситуации равновесия. •

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

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

Обсуждение Справочник по математике для экономистов

Комментарии, рецензии и отзывы

Раздел x теория игр 10.1. бескоалиционные игры нескольких лиц: Справочник по математике для экономистов, В.И. Ермаков, 2009 читать онлайн, скачать pdf, djvu, fb2 скачать на телефон Содержит материал, позволяющий анализировать экономические задачи и осуществлять расчеты. Отражены разделы линейной алгебры, математического программирования, сетевое программирование и планирование, обработка результатов измерений, статистический анализ.