10.7. смешанные расширения конечных бескоалиционных игр

10.7. смешанные расширения конечных бескоалиционных игр

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

Г = {5„ .... Sk Sr. Н (s) Нк {s Ht (*)},

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

игроков, a Hi (s), Hk(s), H,(s), seS=YSk — функции

выигрышей этих игроков. і Если в игре Г нет ни одной ситуации равновесия, то имеет! смысл рассмотреть смешанное расширение этой игры.

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

Таким образом, смешанная стратегия игрока — это вектор, координаты которого соответственно равны вероятностям (частотам), с которыми игрок применяет свои чистые стратегии.

Вектор, размерность которого равна числу чистых стратегий игрока, является смешанной стратегией этого игрока тогда и только тогда, когда все координаты вектора неотрицательны, а их сумма равна единице.

Любой набор вида

= (<*!, °к, ог

где «г* (к=1, 2, г) — некоторая смешанная стратегия к-го игрока, называется ситуацией в смешанных стратегиях.

Если задана некоторая ситуация о — (оак, ог) в смешанных стратегиях, то тем самым указаны вероятности, с которыми тот или иной игрок выбирает свои чистые стратегии. В этом случае можно определить вероятность р„ (s) появления любой ситуации s=(s}, sk, .... sr) в чистых стратегиях (для этого достаточно перемножить вероятности применения игроками чистых стратегий su sk, .... sr).

Обозначим через Я* (с) (к— 1, 2, г) математическое ожидание выигрыша (средний выигрыш) к-го игрока в ситуации 5 = (егь ак, сгД Тогда

Если Z], Z*, .... Zr — множества смешанных стратегий игроков, то Нк (а) является функцией, определенной на множестг

ве 2= П Z*.

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

f = £„ Z* Zf, Я, (ff), Я* (<т), Яг (<х)}

называется смешанным расширением конечной бескоалиционной игры

r={Sj5 Sk S„ Я, (s Rk (s), H, (*)}.

Основные свойства смешанных расширений.

1°. Смешанные расширения стратегически эквивалентных игр сами стратегически эквивалентны.

2°. Смешанное расширение антагонистической игры также является антагонистической игрой.

О Пример 1. Дана биматричная игра Г с платежными матрицами

Л = («(/)«*« И В=фі,)тхп.

Любая смешанная стратегия первого игрока имеет вид

0] = (рь Pi, ■-. Рт),

где р, (/=], 2, т) — вероятность, с которой первый игрок применяет г-ю чистую стратегию.

Любая смешанная стратегия второго игрока имеет вид

<г2 = (?ь Ям),

где qj (/=1, 2, п)— вероятность, с которой второй игрок применяет j-ю чистую стратегию.

Если Я| (сг), Я2 (ст) — математические ожидания выигрышей

соответственно первого и второго игроков в ситуации <т = сг(<т,,

с2), где о, = (ри ...,Pi, .... рт), a2 = (qlt qj q„J, то

flt ft ^ m Я

i-1 J-l i-1 j-l

Сметанным расширением биматричной игры Г является бескоалиционная игра двух лиц

r={2lt 2* (*)}.

где

/

т

Е, = {<тґ=(р,, ,.,tPi Рт) £ Pi=l,Pt^0t i=], 2,т),

If

X2={o2 = (ql, qj, .... qn) £ \%=1, ^0,>=1, 2, n}. •

О Пример 2. Дана бескоалиционная игра трех лиц Г={51,52,5,, Я, (д), Я2 (5), Я, і»},

в которой каждый из игроков имеет ло две чистые стратегии, т. е.

= х2), S2 = {yity2}, 53 = {z,,z2}. Значения функций выигрышей приведены в табл. 10.1.

Смешанным расширением игры Г является бескоалиционная игра

f ={Е„ Si, Zj, Я, (а), Н2 (а), Нъ {а)},

I, = {о-,=<рь pi) J Pl -f p2 = I, p, > 0, p2 > 0}, 22={<72 = (<?], ft)I ft+ft=l, qi>0, ft$=0}, l3={ffj=(r,, r2)| r, + r2=l, r^O, r2>0}, Я, (<т)= 1 * r,+2pi<7i/-2+l Pi ftr2+l •ргЧгГ+2-ргЧгГ2, H2 (cr)=l pr<?rr2 + 2p, c72r, + l p2ft r, + l p2q2r2, Яъ (tr)== 1 рг q2 r, + 2ps' ft" r2+1 p2' ft ' r2, <*=(<fn °i, <fi)10.8. Ситуации равновесия в смешанных стратегиях

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

r={slt.... Sk, .... 5,. Hi 00, Нк (j), Н, (з)}.

Если ег,, ,.у u/t, .... trr — некоторый набор смешанных стратегий

игроков, а Hk(a) (к = , 2 г) — математическое ожидание

выигрыша k-го игрока в ситуации ст=((іь ак, ег,), то

Як(о)= £ я* (5)

Г

« П s/t

fc-1

где Р, (s) — вероятность появления ситуации s в чистых стратегиях при условии, что игроки придерживаются своих смешанных стратегий аъ ак, аг.

Ситуация ег° = (сг", ak_u а°к, а°к+и сг?) в смешанных стратегиях называется приемлемой для к-го игрока, если для любой смешанной стратегии ок этого игрока

Нк(с° ||<rt)<fffc<<r0),

где

е°\<тк=(о*и cl-i, ск, е°к+ ,аГ).

Любую чистую стратегию sk к-го игрока можно отождествить со смешанной стратегией sk этого игрока, в которой вероятность применения чистой стратегии sk равна единице, а вероятности применения всех остальных чистых стратегий равны 0.

Ситуация ff° в смешанных стратегиях является приемлемой для к-го игрока тогда и только тогда, когда для всех чистых стратегий sk этого игрока

Hk(o°\sk)^Hk(a°).

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

Принципиально важное значение в теории игр имеет следующая теорема.

Теорема Нэша. Любая конечная бескоалиционная игра г лиц имеет хотя бы одну ситуацию равновесия в смешанных стратегиях.

Основные свойства ситуаций равновесия в смешанных стратегиях.

1°. Ситуация ст° является ситуацией равновесия.игры Г в смешанных стратегиях тогда и только тогда, когда а0 — ситуация равновесия смешанного расширения игры Г.

2°. Стратегически эквивалентные бескоалиционные игры имеют одни и те же ситуации равновесия в смешанных стратегиях.

3°. Если s°=(si, st, .... s?) — ситуация равновесия бескоалиционной игры Г в чистых стратегиях, то смешанные стратегии s°„ J", .... j, образуют ситуацию равновесия этой игры в смешанных стратегиях.

Если Г — биматричная игра с платежными матрицами А = (ац)тхя и В=(Ьу)„хп, то смешанные стратегии о = (ри -,Р„

Рт), а=(Чі 4j. ■•■> Яп) образуют ситуацию равновесия игры

Г тогда и только тогда, когда

(10.3)

О Пример. Дана биматричная игра Г с платежными матрицами

В данном случае система неравенств (10.3) принимает вид

f

4i^lPiq + 2p2qi, 2q2^lp,qt+2p2q2, 2pl^2plql+p2q1, (Ю.4) Рг*і2рЯ+ріЧг,

где Oi — ipi, pi), o2 — (q, q2) — смешанные стратегии соответственно первого и второго игроков. Из определения смешанных стратегий следует, что рг=-р, 0</7,<1, q2 = -q, 0<?,«£1.

Тогда систему неравенств (10.4) можно записать в следующем виде: (3?1-2)О,-1)>0,

Л (3?t-2)>0, '(Зл-1)(?і-1)>0, (Ю.5) <?, (3^-1)^0,

где 0</?,<1, 0^о,< 1.

Система неравенств (10.5) имеет три решения: a) Pi=Q, 0і = О; б) р, = 1, = в) />, = 7ї> 9, = 2/зТаким образом, ситуация сг°=(er?, а) является ситуацией равновесия игры Г в смешанных стратегиях, если:

a) ff? = (0, 1), aj = (0, 1); б) fff=(l, 0), ff2 = (l, 0); в) <т?=

10.9. Матричные игры и ситуации равновесия в смешанных стратегиях

Дана матричная игра Г с платежной матрицей A = (at)mxn. Смешанные стратегии первого и второго игроков в игре Г имеют соответственно вид

<7i = (Pi» Ри Р* Ог = (Чи —. Ч> Чи),

где

т п

£ />,= 1,/>,>0, /=1, 2, m; £ qj= q^OJ^], 2, .... п.

i-i >-i

Если Я! (сг,, аг) — математическое ожидание выигрыша первого игрока в ситуации а=(ои а2)> то

т л

Я) (<т,, <т2) = £ S а!/£-4 (Яї (ті, сг2)= Я, ((ть <т2)). i-i >-і

Ситуация ff° = (ff?, сг?) является ситуацией равновесия матричной игры Г в смешанных стратегиях тогда и только тогда, когда

я, *2)

для любых смешанных стратегий <Ті, а2 первого и второго игроков.

Любая матричная игра имеет хотя бы одну ситуацию равновесия в смешанных стратегиях.

Смешанные стратегии ff° и а соответственно первого и второго игроков являются оптимальными смешанными стратегиями этих игроков, если <т°=(<7ь ай2) — ситуация равновесия. Число Н, (a J, а — цена матричной игры Г.

По платежной матрице А = (аі;)т * „ можно построить взаимно двойственные задачи линейного программирования

я

/= Е xj (max); j-i

я

£ a^xj^l, i'=l, 2, m; (10.6) >i

Xj^0,j=l, 2, л;

<p=£^(min);

£ я^,>1,;=1, 2,n, (10.7) >>і5ї0, i"=l, 2, m.

Задачи (10.6) и (10.7) обязательно имеют оптимальные решения, если все элементы матрицы А — (а^)т к „ положительны.

Если же взаимно двойственные задачи (10.6) и (10.7) имеют соответственно оптимальные решения

«° = (*ї, *5)иГ = (у?,'...,у? J°),

являются оптимальными смешанными стратегиями первого и второго игроков в матричной игре Г с платежной матрицей

А = (ау)„х„, а число —'—=— цена этой игры.

£>; Ьг j-i .-і

В случае, когда взаимно двойственные задачи линейного программирования (10.6) и (}0.7) не имеют оптимальных решений, вместо игры Г можно рассмотреть матричную игру Ґ с платежной матрицей Л = (а¥+к)тУ(я, где au+k>§, i=, 2, ...

m,j— 1,2,л, так как в играх Г и Ґ одни и те же оптимальные смешанные стратегии игроков.

О Пример. Дана матричная игра Г с платежной матрицей

(

0 -2 7 -1 1 4-2 2 0-1 1,

Прибавив к каждому элементу матрицы А число 3, получим матрицу

/= х, + х2+х3+*4 (max); <р =_у, +у2 +у3 (min);

Зх, + х2+10хз + 7х4^1; С Зуі + Іуі + Sy^l,

2xi+4x2+lxj + x4<:l; (10.9) J yt+4y2 + 3y3^,

5х, + Ъх2+2хз+4х4^], ) 10у1+7у2+2у3^І,

Xj&0,7= 1,2, 3, 4;

j>(>0, i«l,2, 3.

(10.10)

Решив задачи линейного программирования (10.9) и (10.10), найдем оптимальные решения этих задач:

я° = (0, 3/13, 0, 1/13), £°=(0, 1/13, 3/13).

С помощью равенств (10.8) можно записать оптимальные смешанные стратегии в матричной игре Г. Получим, что <гЧ=(0, lU, г1д — оптимальная смешанная стратегия первого игрока,

а Ст2 = (0, 3j4, 0, lJ4) — оптимальная смешанная стратегия второго игрока.

Цена игры Г с платежной матрицей А равна 13/«. Тогда цена исходной игры Г такова: 1/А (13Д—3). ф