ИГР ТЕО́РИЯ

ИГР ТЕО́РИЯ, раз­дел ма­те­ма­ти­ки, изу­чаю­щий ма­те­ма­тич. мо­де­ли при­ня­тия ре­ше­ний в кон­фликт­ных си­туа­ци­ях. Под кон­фликт­ной си­туа­ци­ей, или про­сто кон­флик­том, по­ни­ма­ет­ся си­туа­ция, в ко­то­рой уча­ст­ву­ют разл. сто­ро­ны (на­зы­вае­мые иг­ро­ка­ми), имею­щие не­сов­па­даю­щие ин­те­ре­сы. Мн. яв­ле­ния эко­но­мич., со­ци­аль­но­го, пра­во­во­го, во­ен. ха­рак­те­ра со­дер­жат кон­фликт­ные си­туа­ции разл. слож­но­сти, по­это­му их ма­те­ма­тич. мо­де­ли, изу­чае­мые в И. т., весь­ма раз­но­об­раз­ны.

Классы игр, основные понятия и результаты

Опи­са­ние кон­фликт­ной си­туа­ции в ви­де иг­ры со­сто­ит в ука­за­нии, кто и как уча­ст­ву­ет в кон­флик­те, ка­ко­вы воз­мож­ные ис­хо­ды кон­флик­та, а так­же в ка­кой сте­пе­ни уча­ст­вую­щие в кон­флик­те сто­ро­ны за­ин­те­ре­со­ва­ны в его ис­хо­дах. Ка­ж­дая иг­ра ха­рак­те­ри­зу­ет­ся мно­же­ст­вом иг­ро­ков $I = \left\{ 1, ..., N \right\}$, се­мей­ст­вом мно­жеств $\left\{ X_i\right\}_{i∈I}$, на­зы­вае­мых стра­те­гия­ми, и се­мей­ст­вом функ­ций вы­иг­ры­ша иг­ро­ков$\left\{ H_i\right\}_{i∈I}$, за­дан­ных на пря­мом про­из­ве­де­нии $X = X_1 × ... × X_N$ и при­ни­маю­щих дей­ст­ви­тель­ные зна­че­ния. Иг­ра со­сто­ит в вы­бо­ре ка­ж­дым из иг­ро­ков $i ∈ I$ сво­ей стра­те­гии $x_i ∈ X_i$, в ре­зуль­та­те иг­ры иг­рок $i ∈ I$ по­лу­ча­ет вы­иг­рыш $H_i(x_1, ..., x_N)$. Пред­по­ла­га­ет­ся, что, вы­би­рая стра­те­гию, ка­ж­дый из иг­ро­ков стре­мит­ся по­лу­чить мак­си­маль­но воз­мож­ный вы­иг­рыш. Пред­по­ла­га­ет­ся так­же, что вы­бор стра­те­гии ка­ж­дым из иг­ро­ков не­из­вес­тен ос­таль­ным иг­ро­кам, по­это­му И. т. мож­но рас­смат­ри­вать как тео­рию при­ня­тия ре­ше­ний в ус­ло­ви­ях не­оп­ре­де­лён­но­сти.

В про­стей­шем слу­чае, ко­гда $N = 2$ и $H_1 = –H_2$, иг­ра на­зы­ва­ет­ся ан­та­го­ни­стич. иг­рой двух лиц; при этом, ес­ли мно­же­ст­ва стра­те­гий $X_1$ и $X_2$ ко­неч­ны, $X_1 = \left\{1, ..., m\right\}, \;X_2 = \left\{1, ..., n\right\}$, то иг­ра на­зы­ва­ет­ся мат­рич­ной иг­рой, по­сколь­ку функ­цию $H_1$, на­зы­вае­мую функ­ци­ей вы­иг­ры­ша пер­во­го иг­ро­ка, мож­но за­дать $m × n$ мат­ри­цей $$H=\begin{bmatrix} h_{11} & ... & h_{1m} \\ & ... & \\ h_{m1} & ... & h_{mn} \end{bmatrix},$$ где $h_{ij} = H_1(i, j),\; i = 1,\: ...,\: m, \: j = 1, ..., n$. Пер­вый иг­рок мо­жет га­ран­ти­ро­вать се­бе вы­иг­рыш, рав­ный $$v_1=\underset {i} {max}\: \underset {j} {min} \:h_{ij}$$ вы­би­рая стра­те­гию $i_0$, при ко­то­рой функ­ция $\text{min}_jh_{ij}$ при­ни­ма­ет макс. зна­че­ние. Ана­ло­гич­но, вы­би­рая стра­те­гию $j_0$, при ко­то­рой $\text{max}_ih_{ij}$ дос­ти­га­ет ми­ни­му­ма, вто­рой иг­рок га­ран­ти­ру­ет, что его про­иг­рыш не бу­дет пре­вы­шать $$v_2=\underset {j} {min}\: \underset {i} {max} \:h_{ij}.$$

Для лю­бой мат­рич­ной иг­ры $v_1 ⩽ v_2$.

Ес­ли $v_1 = v_2$, то па­ра $(i_0,\: j_0)$ пред­став­ля­ет со­бой сед­ло­вую точ­ку мат­ри­цы $H$, то есть для неё вы­пол­ня­ют­ся не­ра­вен­ст­ва $$h_{ij_0} ⩽ h_{i_{0}j_{0}} ⩽ h_{i_{0}j}$ при всех $i = 1,\; ...,\; m,\; j = 1,\; ...,\; n$. В этом слу­чае чис­ло назы­ва­ет­ся зна­че­ни­ем (ино­гда це­ной) иг­ры, стра­те­гии $i_0$ и $j_0$ на­зы­ва­ют­ся оп­ти­маль­ны­ми чис­ты­ми стра­те­гия­ми со­от­вет­ст­вен­но пер­во­го и вто­ро­го иг­ро­ков, па­ра оп­ти­маль­ных стра­те­гий на­зы­ва­ет­ся ре­ше­ни­ем иг­ры. Оп­ти­маль­ные чис­тые стра­те­гии су­ще­ст­ву­ют не для всех мат­рич­ных игр. Ес­ли та­ких стра­те­гий нет, то воз­мож­но­сти иг­ро­ков рас­ши­ря­ют и оп­ти­маль­ные стра­те­гии ищут в клас­се т. н. сме­шан­ных стра­те­гий, т. е. в мно­же­ст­ве стра­те­гий, яв­ляю­щих­ся рас­пре­де­ле­ния­ми ве­ро­ят­но­стей на мно­же­ст­вах чис­тых стра­те­гий; ина­че го­во­ря, стра­те­гия­ми яв­ля­ют­ся рас­пре­де­ле­ния $p = (p_1,\: ...,\: p_m),\; p_i ⩾ 0,\; i=1,\: ...,\: m,\; p_1 +\: ...\: + p_m = 1$, для пер­во­го иг­ро­ка и рас­пре­де­ле­ния $q = (q_1,\: ...,\: q_n),\; q_j ⩾ 0,\; j = 1,\: ...,\: n,\; q_1 +\: ...\: + q_n = 1$, для вто­ро­го иг­ро­ка. В ка­че­ст­ве вы­иг­ры­ша пер­во­го иг­ро­ка в этом рас­ши­ре­нии мат­рич­ной иг­ры рас­смат­рива­ет­ся ма­те­ма­тич. ожи­да­ние вы­иг­ры­ша ис­ход­ной иг­ры при вы­бо­ре иг­ро­ка­ми сме­шан­ных стра­те­гий $p$ и $q$

$$H(p,q)=\sum_{i=1}^{m}\sum_{j=1}^{n}h_{ij}p_iq_j.$$

Осн. тео­ре­ма тео­рии мат­рич­ных игр, из­вест­ная как тео­ре­ма Ней­ма­на о ми­ни­мак­се, ут­вер­жда­ет, что в лю­бой мат­рич­ной иг­ре су­ще­ст­ву­ют оп­ти­маль­ные сме­шан­ные стра­те­гии $p^*$ и $q^*$ та­кие, что $$H(p, q^*) ⩽ H(p^*, q^*) ⩽ H(p^*, q)$$ для лю­бых $p$ и $q$, т. е. па­ра $(p^*,\: q^*)$ пред­став­ля­ет со­бой сед­ло­вую точ­ку функ­ции $H(p, q)$. Ве­ли­чи­на $v = H(p^*, q^*)$ назы­ва­ет­ся зна­че­ни­ем (или це­ной) иг­ры (в сме­шан­ных стра­те­ги­ях). Спра­вед­ли­вы ра­вен­ст­ва $$v_2=\underset {p} {max}\: \underset {q} {min} \:H(p, q)=\underset {q} {min}\: \underset {p} {max} \:H(p, q).$$

По­след­нее ра­вен­ст­во со­став­ля­ет со­дер­жа­ние тео­ре­мы о ми­ни­мак­се, яв­ляю­щей­ся од­ной из осн. тео­рем тео­рии игр.

Смысл оп­ти­маль­ных сме­шан­ных стра­те­гий со­сто­ит в сле­дую­щем. Пусть иг­ра по­вто­ря­ет­ся $t$ раз и пусть пер­вый иг­рок вы­би­ра­ет оп­ти­маль­ную сме­шан­ную стра­те­гию , т. е. в ка­ж­дой иг­ре он вы­би­ра­ет чис­тую стра­те­гию $i$ с ве­ро­ят­но­стью , $i = 1,\: ..., \:m$. Вы­иг­рыш пер­во­го иг­ро­ка в ка­ж­дой иг­ре – слу­чай­ная ве­ли­чи­на, ма­те­ма­тич. ожи­да­ние ко­то­рой ко­неч­но. Сред­нее зна­че­ние вы­иг­ры­ша $v_t$ за $t$ игр при рос­те $t$ в си­лу боль­ших чи­сел за­ко­на

и тео­ре­мы о ми­ни­мак­се в пре­де­ле бу­дет не мень­ше це­ны иг­ры, ка­кую бы сме­шан­ную стра­те­гию ни вы­брал вто­рой иг­рок. Это сред­нее зна­че­ние бу­дет стре­мить­ся к $v$ по ве­ро­ят­но­сти, ес­ли вто­рой иг­рок вы­бе­рет свою оп­ти­маль­ную сме­шан­ную стра­те­гию $q^*$.

Осн. ме­то­ды на­хо­ж­де­ния ре­ше­ния мат­рич­ных игр опи­ра­ют­ся на ис­поль­зо­ва­ние ме­то­дов ли­ней­но­го про­грам­ми­ро­ва­ния

.

Дру­гим боль­шим клас­сом ан­та­го­ни­стич. игр яв­ля­ют­ся ан­та­го­ни­стич. иг­ры, на­зы­вае­мые иг­ра­ми на еди­нич­ном квад­ра­те, в ко­то­рых мно­же­ст­ва чис­тых стра­те­гий пер­во­го и вто­ро­го иг­ро­ков пред­став­ля­ют со­бой сег­мент $[0, 1]$. К иг­ре на еди­нич­ном квад­ра­те мо­жет быть све­де­на лю­бая ан­та­го­ни­стич. иг­ра с мно­же­ст­ва­ми стра­те­гий обо­их иг­ро­ков, имею­щи­ми мощ­ность кон­ти­нуу­ма. Эти иг­ры за­да­ют­ся функ­ци­ей вы­иг­ры­ша $K(х, у)$, оп­ре­де­лён­ной на еди­нич­ном квад­ра­те. Сме­шан­ны­ми стра­те­гия­ми иг­ро­ков яв­ля­ют­ся функ­ции рас­пре­де­ле­ния $F(x)$ и $G(y),\; x ∈ [0,1],\; y ∈ [0,1]$. При дос­та­точ­но ши­ро­ких ус­ло­ви­ях на функ­цию $K(х, у)$ вы­иг­рыш пер­во­го иг­ро­ка при ус­ло­вии, что пер­вый и вто­рой иг­ро­ки при­ме­ня­ют со­от­вет­ст­вен­но сме­шан­ные стра­те­гии $F$ и $G$, по­ла­га­ет­ся рав­ным $$K(F,G)=\int_{0}^{1}\int_{0}^{1}K(x,y)dF(x)dG(y)$$

и справедлива теорема о минимаксе $$\underset {F} {max}\: \underset {G} {min} \:K(F, G)=\underset {G} {min}\: \underset {F} {max} \:K(F, G),$$

т. е. су­ще­ст­ву­ют зна­че­ние иг­ры $v$ и оп­ти­маль­ные сме­шан­ные стра­те­гии обо­их иг­ро­ков. Су­ще­ст­ву­ют иг­ры на еди­нич­ном квад­ра­те, для ко­то­рых тео­ре­ма о ми­ни­мак­се не­спра­вед­ли­ва.

Класс игр, в ко­то­рых иг­ро­ки при­ме­ня­ют свои стра­те­гии од­но­крат­но и не­за­ви­си­мо от вы­бо­ра про­тив­ни­ка, вклю­ча­ет в се­бя и иг­ры, осу­ще­ст­в­ляе­мые пу­тём по­сле­до­ва­тель­но­го вы­пол­не­ния хо­дов уча­ст­ни­ка­ми. В та­ких иг­рах вы­бор стра­те­гии иг­ро­ка со­сто­ит в ука­за­нии вы­бо­ра по­оче­рёд­но вы­пол­няе­мых хо­дов на ос­но­ва­нии све­де­ний, быть мо­жет не­пол­ных, о пре­ды­ду­щих хо­дах обо­их иг­ро­ков, т. е. на ос­но­ва­нии све­де­ний о те­ку­щей по­зи­ции иг­ры, в ко­то­рой при­ни­ма­ет­ся ре­ше­ние. Та­кие иг­ры на­зы­ва­ют­ся по­зи­ци­он­ны­ми. Ес­ли при при­ня­тии ре­ше­ния об оче­ред­ном хо­де иг­ро­ку из­вест­ны все пре­ды­ду­щие хо­ды обо­их иг­ро­ков, то та­кая иг­ра на­зы­ва­ет­ся иг­рой с пол­ной ин­фор­ма­ци­ей.

В ка­че­ст­ве при­ме­ра по­зи­ци­он­ной иг­ры с пол­ной ин­фор­ма­ци­ей мож­но при­вес­ти шах­ма­ты. Т. к. пра­ви­ла вы­бо­ра хо­да в лю­бой по­зи­ции иг­ры из­вест­ны, в прин­ци­пе мож­но вы­пи­сать все стра­те­гии обо­их иг­ро­ков в иг­ре и ука­зать ре­зуль­тат ка­ж­дой пар­тии, све­дя т. о. эту иг­ру к мат­рич­ной фор­ме. Тео­ре­ма Цер­ме­ло – Ней­ма­на ут­вер­жда­ет, что все по­зи­ци­он­ные иг­ры с пол­ной ин­фор­ма­ци­ей име­ют ре­ше­ние в чис­тых стра­те­ги­ях. Для шах­мат это оз­на­ча­ет, что ес­ли при­пи­сать по­бе­де пер­во­го иг­ро­ка вы­иг­рыш, рав­ный 1, ничь­ей – вы­иг­рыш, рав­ный 0, и по­ра­же­нию – вы­иг­рыш, рав­ный –1, то та­кая иг­ра име­ет зна­че­ние в чис­тых стра­те­ги­ях, рав­ное 1, 0 или –1, но ис­тин­ная ве­ли­чи­на это­го зна­че­ния не­из­вест­на.

По­треб­но­сти на­хо­ж­де­ния оп­ти­маль­но­го управ­ле­ния в кон­фликт­ных си­туа­ци­ях при­ве­ли к раз­ви­тию тео­рии по­зи­ци­он­ных игр с не­пре­рыв­ным вре­ме­нем, на­зы­вае­мых диф­фе­рен­ци­аль­ны­ми иг­ра­ми. В диф­фе­рен­ци­аль­ной иг­ре пред­по­ла­га­ет­ся, что дви­же­ние управ­ляе­мой сис­те­мы опи­сы­ва­ет­ся урав­не­ни­ем $$\frac {dx}{dt}=f(t,x,u,v)$$ ,

где $t$ – вре­мя, $x$ – фа­зо­вый век­тор, $f(t, x, u, v)$ – не­ко­то­рая функ­ция, $u = u(t, x(t))$ и $v = v(t, x(t))$ – управ­ляю­щие стра­те­гии пер­во­го и вто­ро­го иг­ро­ков. В мо­мент вре­ме­ни $t$ иг­ро­ки рас­по­ла­га­ют ин­фор­ма­ци­ей о те­ку­щей по­зи­ции $(t, x(t))$. Вы­иг­рыш (пла­та) в диф­фе­рен­ци­аль­ной иг­ре за­да­ёт­ся не­ко­то­рым функ­цио­на­лом $c(x(t),\; u(t),\; v(t))$, пер­вый иг­рок стре­мит­ся до­бить­ся ми­ни­маль­но воз­мож­но­го, а вто­рой – мак­си­маль­но воз­мож­но­го зна­че­ния функ­цио­на­ла. Спе­ци­фи­ка диф­фе­рен­ци­аль­ных игр не по­зво­ля­ет ог­ра­ни­чить класс до­пус­ти­мых стра­те­гий $u(t,\: x(t)),\: v(t, x(t))$ глад­ки­ми функ­ция­ми и ис­поль­зо­вать для на­хо­ж­де­ния тра­ек­то­рии $x(t)$ из­вест­ные ме­то­ды тео­рии обык­но­вен­ных диф­фе­рен­ци­аль­ных урав­не­ний. При не­ко­то­рых ус­ло­ви­ях на функции, вхо­дя­щие в оп­ре­де­ле­ние диф­фе­рен­ци­аль­ной иг­ры, иг­ра име­ет зна­че­ние и оп­ти­маль­ные стра­те­гии. Во 2-й пол. 20 в. глу­бо­кие свя­зи диф­фе­рен­ци­аль­ных игр с тео­ри­ей оп­ти­маль­но­го уп­рав­ле­ния бы­ли ус­та­нов­ле­ны Л. С. Пон­тря­ги­ным

, под­ход к диф­фе­рен­ци­аль­ным иг­рам как к по­зи­ци­он­ным иг­рам с не­пре­рыв­ным вре­ме­нем раз­ра­батывался рос. ма­те­ма­ти­ком Н. Н. Кра­сов­ским. Для на­хо­ж­де­ния ре­ше­ний диф­фе­рен­ци­аль­ных игр мо­жет быть ис­поль­зо­ва­но ди­на­ми­че­ское про­грам­ми­ро­ва­ние

 >>

.

В слу­чае не­ан­та­го­ни­стич. игр прин­цип оп­ти­маль­но­сти транс­фор­ми­ру­ет­ся в тре­бо­ва­ние при­ем­ле­мо­сти си­туа­ций. Си­туа­ция (на­бор стра­те­гий) $x = (x_1,\: ...,\: x_N)$ в не­ан­та­го­ни­стич. иг­ре на­зы­ва­ет­ся при­ем­ле­мой для коа­ли­ции (груп­пы иг­ро­ков) $K ⊂ I$ или, ина­че, $K$-оп­ти­маль­ной, ес­ли от­кло­не­ние иг­ро­ков из $K$ от сво­их стра­те­гий не улуч­ша­ет си­туа­цию с точ­ки зре­ния коа­ли­ции $K$. При этом не­улуч­ше­ние мо­жет по­ни­мать­ся по-раз­но­му: как не­уве­ли­че­ние вы­иг­ры­ша для всех иг­ро­ков, вхо­дя­щих в $K$; не­уве­ли­че­ние сум­мар­но­го вы­иг­ры­ша всех иг­ро­ков из $K$; воз­мож­ность уве­ли­че­ния вы­иг­ры­ша од­них иг­ро­ков из $K$ лишь за счёт умень­ше­ния вы­иг­ры­ша др. иг­ро­ков из $K$. Для коа­ли­ции $K$ си­туа­ция, об­ла­даю­щая по­след­ним из пе­ре­чис­лен­ных свойств, на­зы­ва­ет­ся оп­ти­маль­ной по Па­ре­то. Си­туа­ция, при­ем­ле­мая для ка­ж­дой коа­ли­ции из не­ко­то­ро­го на­бо­ра коа­ли­ций $𝓚 = {K_1,\: ...,\: K_m}$, на­зы­ва­ет­ся $𝓚$-ус­той­чи­вой. Ес­ли $𝓚$ со­сто­ит из всех отд. иг­ро­ков мно­же­ст­ва $I$, то $𝓚$-ус­той­чи­вая си­туа­ция на­зы­ва­ет­ся рав­но­вес­ной по Нэ­шу. Эти по­ня­тия на­хо­дят ши­ро­кое при­ме­не­ние при ана­ли­зе ма­те­ма­тич. мо­де­лей кон­фликт­ных си­туа­ций в эко­но­ми­ке.

Исторический очерк

Отд. со­об­ра­же­ния по по­во­ду ма­те­ма­тич. опи­са­ния кон­фликт­ных си­туа­ций вы­ска­зы­ва­лись на­чи­ная с 17 в. мн. учё­ны­ми. В кон­крет­ных иг­рах сме­шан­ные стра­те­гии поя­ви­лись в нач. 18 в. Ряд по су­ще­ст­ву тео­ре­ти­ко-иг­ро­вых ут­вер­жде­ний в эк­ви­ва­лент­ной фор­ме был по­лу­чен в разл. раз­де­лах ма­те­ма­ти­ки, напр. П. Л. Че­бы­ше­вым

в тео­рии при­бли­же­ния функ­ций. В 1911 Э. Цер­ме­ло

 >>

опи­сал тео­ре­ти­ко-иг­ро­вой под­ход к шах­мат­ной иг­ре. В 1921 Э. Бо­рель

 >>

ввёл по­ня­тие чис­тых и сме­шан­ных стра­те­гий в мат­рич­ных иг­рах, од­на­ко в пол­ном объ­ё­ме тео­ре­му о ми­ни­мак­се он не до­ка­зал. Эта тео­ре­ма тео­рии мат­рич­ных игр бы­ла до­ка­за­на Дж. фон Ней­ма­ном

 >>

в 1928. Он опуб­ли­ко­вал ст. «К тео­рии стра­те­ги­че­ских игр» (1928), со­дер­жа­щую осн. идеи совр. И. т., од­на­ко до 1944 эти идеи не по­лу­чи­ли ши­ро­ко­го рас­про­стра­не­ния. Их де­таль­ной раз­ра­бот­ке по­свя­ще­на кни­га Дж. фон Ней­ма­на и О. Мор­ген­штер­на

 >>

«Тео­рия игр и эко­но­ми­че­ское по­ве­де­ние». По­сле вы­хо­да этой кни­ги И. т. во­шла в чис­ло раз­де­лов современной ма­те­ма­ти­ки и ста­ла раз­ви­вать­ся как из по­треб­но­стей её эко­но­ми­ческих, со­ци­аль­ных, пра­во­вых, во­ен­ных и др. при­ме­не­ний, так и в си­лу сво­их внутр. по­треб­но­стей. В СССР И. т. раз­ви­ва­лась в осн. ле­нинградской шко­лой тео­рии игр, создан­ной рос. ма­те­ма­ти­ком Н. Н. Во­робь­ё­вым.