Название: Математические модели принятия решений в экономике - Розен В. В.

Жанр: Экономика

Рейтинг:

Просмотров: 903

Лекция 13. антагонистические игры

• Антагонистическая игра как математическая модель принятия ре­шения в условиях противоположности интересов • Матричные игры Нижняя и верхняя цена игры Устойчивое поведение и седловые точки Теорема о связи седловой точки с ценой игры • Смешанное расширение матричной игры Основные правила для функции выигрыша в смешан­ном расширении • Теорема фон Неймана и ее следствия • Задача 16 Профилактика нежелательного события

1. Продолжим системное описание задачи принятия решения (лекция 1): рассматривается некоторый объект управления, на ко­торый воздействует управляющая подсистема и среда. Управляю­щая подсистема всегда является целенаправленной, т.е. имеет опре­деленную цель и ее управление направлено на достижение этой цели. Поведение среды может носить как целенаправленный, так и случайный характер. Если среда ведет себя как целенаправ­ленная система, то такая ситуация принятия решения называется теоретико-игровой, а ее математическая модель игрой.

Неопределенность, существующая при выборе решения управ­ляющей подсистемой, возникает за счет воздействия среды на объ­ект управления. Однако следует различать неопределенность, име­ющую случайный (или стохастический) характер, и неопределен­ность, имеющую целенаправленный характер. В первом случае получаем ЗПР в условияхнеопределенности (или в условиях рис­ка), а во втором — в теоретико-игровых условиях. Если в ЗПР в условиях неопределенности (а также в ус ловиях риска) принятие ре­шения рассматривается как индивидуальный выбор альтернативы

иравляющеи подсистемой, то в теоретико-игровой модели приня-^.йе решения рассматривается как совместный выбор допустимых _іЛьТЄрнатив (стратегий), который производится управляющей под­системой и подсистемой, «олицетворяющей» среду. Поскольку при таком подходе различие между управляющей подсистемой и сре­дой — в плане их воздействия на объект управления — стирается, удобно говорить о двух управляющих подсистемах; в теоретико-йгровой терминологии эти управляющие подсистемы называются игроками.

В случае, когда цели управляющей подсистемы и среды про­тивоположны, получающаяся игра называется антагонистичес­кой Антагонистическая игра, для которой ее оценочная структура задается с помощью оценочной функции, может быть представле­на в виде (X, У, /), где X — множество стратегий игрока 1, Y — множество стратегий игрока 2, / : XxF-^M — целевая функция. При этом для игрока 1 функция / рассматривается как функция выигрыша, а для игрока 2 — как функция потерь.

2. Если в антагонистической игре множества стратегий игроков конечны, то такая игра называется матричной. Матричная игра обычно задается в виде матрицы А = \aJt\ (г — 1, п: j = 1. го), кото­рая называется матрицей выигрышей или платежной мат­рицей. В этом случае стратегии игрока 1 могут быть отождествле­ны с номерами строк, а стратегии игрока 2 с номерами столбцов платежной матрицы. Число о?г рассматривается одновременно как выигрыш игрока 1 и проигрыш игрока 2 в ситуации

Проанализируем, какие стратегии игроков в матричной игре можно рассматривать в качестве обоснованных Если принять за основу гипотезу крайней осторожности — гипотезу антагонизма (см. лекцию 8), то в качестве оценки стратегии ; игрока 1 выступа­ет его минимальный возможный выигрыш при использовании им

й стратегии, т.е. а, = mina^. Число аг представляет собой с со-

з

держательной точки зрения гарантированный уровень стратегии г (т.е. выбрав стратегию г, игроке имеет полную гарантию, что его выигрыш, независимо от того, какую стратегию выберет игрок 2, будет не меньше, чем аг). Наибольший гарантированный выигрыш Игрока / в данной игре таков:

= maxa, = maxmina^. (13-1)

*          » з

Число її] называется нижней ценой игры (или максимином), а стратегия, максимизирующая минимальный возможный вьіигрц^ игрока 1, т.е. стратегия г*, для которой аг» = v, — максиминноц стратегией игрока 1.

Теперь обратимся к игроку 2. Поскольку для него матрица, 4 представляет собой матрицу потерь, то оценкой стратегии j При принятии гипотезы антагонизма является максимум возможных при этой стратегии потерь, т.е. (З3   =  maxaj. Стратегия і*

г          J і

которая минимизирует максимальные возможные потери игрока 2 называется его минимаксной стратегией, а число

i>2 = min/?-' = min max а

З          3 г

(13.2)

— верхней ценой игры (или минимаксом). Имеет место следу­ющее правило.

Правило 13.1. В матричной игре нижняя цена не превосходит верхней цены: «і < «2. Если нижняя и верхняя цена игры совпада­ют, то число v = v = «2 называется ценой игры.

Действительно, при любых г = 1,п, j = l,m выполняется условие аг < а и j33 > а3, откуда аг < (З3. Пусть г* — максиминная стратегия игрока 1, j* — минимаксная стратегия игрока 2. Тогда vi — а,. < /З3" = v2.

Практическое правило для нахождения нижней и верхней цены матричной игры состоит в следующем. Добавим к платежной мат­рице А столбец {аг)г~Тп строчных минимумов и строку (/3J)J=y7^ столбцовых максимумов. Наибольшее из чисел аг будет нижней це­ной, а наименьшее из чисел j33 — верхней ценой. Этот способ про­демонстрирован на примерах, приведенных ниже. В примере 13.1 игра не имеет цены (v < v2), в примере 13.2 v = v2 = v — игра имеет цену.

Следующая наша задача — проанализировать «на устойчи­вость» ситуацию, в которой игрок 1 использует максиминную стра­^гйЮ, а игРок ^ — минимаксную стратегию. Например, в при- зере     такой ситуацией будет (2,1). Эта ситуация является Устойчивой, так как в ней игроку 2 выгодно отклонение от нее за- меной стратегии 1 на стратегию 2: в этом случае его потери умень- шатся с 5 до 3. При этом ситуация (2,1) перейдет в ситуацию (2, 2). Однако ситуация (2, 2) также неустойчива, так как в ней игроку 1 вь1ГОДНО заменить стратегию 2 на стратегию 1, в результате чего „гра переходит в ситуацию (1, 2). В этой ситуации выгодным явля- ется одностороннее отклонение игроку 2, которое приводит к ситуа- ций (1, !)■ Наконец, в последней ситуации одностороннее отклонение 0т нее выгодно игроку 1, которое осуществляется заменой страте- гии 1 на стратегию 2. В итоге игра возвращается в первоначальную ситуацию (2,1) и т.д. до бесконечности. Таким образом, в игре при- мера 13.1 выбор ситуации (2,1) приводит к «бесконечному блужда- нию»: (2,1) -> (2, 2) -4 (1, 2) -4 (1,1) —> (2,1) —5- ..., что является свидетельством «неудачных» совместных решений игроков.

Напротив, в игре примера 13.2 выбор ситуации (2, 2) (первой компонентой которой является максиминная стратегия игрока 1, а второй — минимаксная стратегия игрока 2) — устойчив, так как в этой ситуации ни одному из игроков невыгодно одностороннее от­клонение от нее. Учитывая, что игра примера 13.2 имеет цену, а игра примера 13.1 не имеет цены, можно связать наличие устой­чивых ситуаций в матричной игре с наличием у нее цены. Теперь дадим формальное доказательство этого важного факта. Приведем следующее определение.

Определение. Пусть Та — матричная игра с платежной матрицей А — \а3г\. Ситуация (io, jo) называется седловой точкой в игре Та, если при всех і = 1,п, j = l,m выполняется двойное неравенство:

af < < < al . (13.3)

Соотношение 13.3 можно пояснить следующим образом.

Правило 13.2. Ситуация (to,io) — седловая точка игры Гд тогда и только тогда, когда элемент а3°о является одновременно Наименьшим элементом своей строки и наибольшим элементом своего столбца.

Ясно, что устойчивые в матричной игре ситуации — это и есть ее седловые точки: одностороннее отклонение от седловой точки не выгодно ни одному из игроков.

Теорема 13.1 (связь седловой точки с ценой игры).

Пусть (го, Jo) — седловая точка игры Та- Тогда:

а)         го является максиминной стратегией игрока 1

б)         jo является минимаксной стратегией игрока 2;

в)         игра Г, имеет цену, причем исход в седловой точке совпа- дает с ценой игры а3°о = v

Пусть игра Та имеет цену v  Тогда любая ситуация (го. Jo) где го — максиминная стратегия игрока 1, a jo — минимаксная стратегия игрока 2, — является седловой точкой игры Гд

Доказательство. Для доказательства 1) рассмотрим фрагмент платежной матрицы А (табл 13 1), к которой добавлен столбец строчных минимумов (аг)г=т-^ и строка столбцовых максимумов (Д7) -г—.г' Учитывая правило 13 2, получаем следующие равенства

аго = а?", j330 = а?°. Имеют место следующие очевидные соотноше­ния (см. табл. 13.1):

a,

Из (*) следует, что го — максиминная стратегия игрока 1. а из (**) следует, что jo — минимаксная с тратегия игрока 2 Утверждения а) и б) установлены Далее, используя (*) и (**), имеем

vi = max аг = аго = а3°        v2 = mm (З3 = (З30 = а3°, і j

откуда «і = «2 = а3", что и заканчивает доказательство утвержде­ния 1)

Докажем 2). Пусть игра имеет цену: v = v2 = v. Обозначая через го максиминную стратегию игрока 1 и через j0 — минимакс­ную стратегию игрока 2, изобразим фрагмент платежной матрицы

При этом нижняя цена игры V = аго, верхняя цена игры v2 = /З30 ■ Покажем, что (го, Jo) — седловая точка игры Гд. Имеем

af < Р° =v2 = vx= аго < а?°,    < > а1о =     = v2 = /У0 >

Итак, соотношение (13 3) установлено, что и завершает доказатель­ство теоремы 13.1.

Отметим некоторые следствия доказанной теоремы

Следствие 1. В матричной игре наличие седловой точки эквивалентно наличию цены игры

Следствие 2. Истоды в седловых точках матричной игры совпадают между собой и совпадают с ценой игры

Положим X* - множество максиминных стратегий игрока 1, Y* — множество минимаксных стратегий игрока 2. Е — множество седловых точек в матричной игре Гд.

Следствие 3. Если игра Та имеет цену, то

E = X*xY*. (134)

Свойство 13.4 иногда называют свойством прямоуголъности

множества седловых точек

Сформулируем теперь основные выводы, получающиеся на ос­новании теоремы 13 1 и ук.   інных из нее следствий.

Если матричная игра ішіет цену, то в ней реализуются два принципа оптимальности принцип оптимальности стратегий (s качестве оптимальных выступают максиминные стратегии игрока 1 и минимаксные стратегии игрока 2), и принцип опти­мальности ситуаций (е качестве оптимальных ситуаций высту­пают седловые точки)  При этом оба принципа оптимальности оказываются согласованными между собой: если игроки выбцра. ют оптимальные стратегии, то возникающая ситуация являещ. ся оптимальной (т. е. седловой точкой); обратно — компонента, ми любой седловой точки служат оптимальные стратегии игро­ков. Кроме того, исход в любой седловой точке равен цене игры

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

Замечание. Хотя в любой матричной игре максиминная стратегия игрока 1 и минимаксная стратегия игрока 2 всегда существуют, их мож­но считать оптимальными только при наличии цены игры. Дело в том, что только в этом случае исход, гарантированный максиминной стра­тегией игроку 1, совпадает с исходом, гарантированным минимаксной стратегией игроку 2 (этот общий гарантированный обоим игрокам ис ход и есть цена игры). Если же в матричной игре нет цены, то всякий исход с, удовлетворяющий условию vi < с < г>2, не является гаранти­рованным исходом ни одного из игроков; тем самым игра становится неопр еде ленной.

Однако существует общий метод, который позволяет для всякой матричной игры обеспечить наличие в ней цены в некотором обобщенном смысле. Этот метод, состоящий в переходе к смешанным стратегиям, впервые был обоснован в теории игр фон Нейманом и Моргенштерном. Краткое изложение основных результатов, связанных с построением смешанного расширения матричной игры, содержится в следующем пункте.

3. По-прежнему будем обозначать через Та матричную игру с платежной матрицей А = ||а^|| (г = l,n; j = 1,тп). Множество смешанных стратегий игрока 1 (напомним, что смешанные страте­гии рассматривались в лекции 11), есть

Sn = {х = (хи...,хп) Є Mn : Xi>0, ^^=l},

і = 1

а множество смешанных стратегий игрока 2 таково:

m

Sm^{y = (yi,..-,ym)eRm: у3>0, ]>> = і}.

i=i

Применение в игре Гд игроком 1 смешанной стратегии х Є Sn может быть интерпретировано как проведение опыта, случайными исходами котрого являются элементы {1,.. . ,n}, причем Хі — ве­роятность выбора стратегии г. Аналогично интерпретируется при-менение в игре Гд смешанной стратегии у £ Sm игроком 2. Пред­положим теперь, что игрок 1 использует смешанную стратегию х, а игрок 2 — смешанную стратегию у. Тогда вероятность возник­новения ситуации (г, j) (т.е. вероятность того, что исходом первого опыта будет г, а исходом второго опыта является j) по теореме умножения вероятностей равна произведению хгу^. (Заметим, что здесь предполагается независимость выборов игроками 1 и 2 своих смешанных стратегий, т.е. каждый игрок производит выбор своего вероятностного вектора, не имея информации о выборе другого иг­рока.) Так как в ситуации выигрыш игрока 1 равен а, получа­ем, что при использовании игроками 1 и 2 смешанных стратегий х и у соответственно выигрыш игрока 1 становится случайной вели-

чиной вида £ =      1  . Будем считать математическое

\_хіУз (i=T^;j=T^) ожидание М£ этой случайной величины выигрышем игрока 1 в си­туации в смешанных стратегиях (х, у).

Итак, по матричной игре Гд построена новая игра Гд, в кото­рой множеством стратегий игрока 1 является множество вероят­ностных векторов Sn, множеством стратегий игрока 2 — множест­во вероятностных векторов Sm, а функция выигрыша определяется равенством

FA(x,y) = Mt=   Y1 (13-5)

г~ 1,...,п j = l,...,m

Заметим, что стратегия і — 1,п игрока 1 в игре Та может быть отождествлена с вероятностным вектором (0,. .., 1,. . ., 0) Є Sn,

а стратегия j  =  l,m игрока 2 — с вероятностным вектором

(0,..., 1,..., 0) Є Sm. Таким образом, игра Гд является расширени-з

ем игры Гд, которое получается расширением множеств стратегий игроков и продолжением их функций выигрыша. При этом первона­чальные стратегии игроков в игре Гд, рассматриваемые как стра­тегии в игре Гд, называются чистыми. Ситуация (х, у) Є Sn X Sm называется ситуацией в смешанных стратегиях в игре Гд.

Построенная игра Гд называется смешанным расширением игры Гд.

Рассмотрим основные правила для функции выигрыша в сме­шанном расширении матричной игры.

Правило 13.3 а) Если игрок 1 использует смешанную сгпра тегию х = [х,....хп) Є Sn, а игрок 2 — чистую страупеги^ j = 1,т, то значение функции выигрыша в полученной ситуацщ (x,j) равно взвешенной сумме элементов j-го столбца платежной матрицы с весами х,. . . ,хп соответственно:

п

FA{x,j) ^^х^. (13.6)

б) Если игрок 1 использует чистую стратегию г = Т~п а игрок 2 — смешанную стратегию у = {у,...,ут) Є Sm, ?По значение функции выигрыша в полученной ситуации (і,у) равно взвешенной сумме элементов г-й строки платежной матрицы с весами «/і,   ут:

т

Ра(Ьу) =Y,Vjal (13?)

Доказательство, а) В ситуации (x,j) исходом будет слу- 'аЛ      

чайная величина rjj =    1   (г = 1,п); ее математическое ожидание

хг

равно правой части формулы (13.6).

Правило 13.4 [разложение функции выигрыша по чистый стратегиям).

а) Значение функции выигрыша FA{x. у) есть взвешенная сумма

величин FA(x,j) с весами у3  (j = 1,т): FA(x.y) = VjFA{x,]). б) Значение функции выигрыша FA(x,y) есть взвешенная сумма

             п

величин FA(i,y) с весами хг  (г — 1,п): FA(x,y) = ]Р хгРА(г,у).

t=i

Доказательство, а) Используя правило 13.3 а), имеем

FA{x,y)=        (х'УзН = YlHx\%y3a'

.,    ,п   j =1 г —1

, ,т

п ТП

J=l       4=1 J=l

Лравило 13.5 [правило гарантирующей стратегии). Зафик-

сйрУеМ некотоРое число С.

а)         Пусть ї° Є S„ — смешанная стратегия игрока 1, для кото- рой Щт Лю^ой чистой стратегии j = 1,т игрока 2 выполняется ^равенство Fa(x°,j) > с. Тогда и при любой смешанной стра- тегии у Є Sm будет выполняться неравенство і<д(:г0,у) > с.

б)         Пусть у0 Є Srn — смешанная стратегия игрока 2, для ко- торой при любой чистой стратегии і = l,n игрока 1 выпол- няется неравенство Fx (г, у0) < С. Тогда и при любой смешан- ной стратегии х Є Sn игрока 1 будет выполняться неравенство

Теоретико-игровой смысл утверждения а) состоит в следующем. Бели стратегия х° гарантирует игроку 1 исход С против любой чистой стратегии игрока 2, то она гарантирует ему исход С также и против любой смешанной стартегии игрока 2. Аналогично интерпретируется утверждение б).

Доказательство, а) Пусть у = [у, ■ ■ -Ут) Є Sm. Умножая неравенство Fa(x°.j) > С на у3 > 0 и суммируя по j = 1,т, получаем

т т

По правилу 13.4,а) левая часть этого неравенства равна Fa{xq. у), а правая его часть равна С.

Правило 13.6 (правило наименьшего и наибольшего значения). Рассмотрим при произвольном фиксированном у0 Є Sm функцию Ра(х,у°) как функцию переменной х, определенную на множест­ве Sn.

Если функция Fa(x, у0) достигает наибольшего [наименьшего) значения при х = х°, то при любой чистой стратегии г Є Spx° выполняется условие і*д(г, У°) = Fa(x°, у0).

Замечание. Через Spx здесь и далее обозначается спектр смешан­ной стратегии х, т е множество номеров г — l,n, для которых хъ > О Спектр смешанной стратегии составляют те чистые стратегии, которые «используются» в ней с ненулевой вероятностью

Доказательство. Установим справедливость правила 13.6 Для наибольшего значения. Тогда для любого г — 1,п выполняется Неравенство

FA(i,y°)

Предположим, что для некоторого г' Є Sp ж0 имеет место стрОГо неравенство Fa (г', у0) < Fa (ж0, у0) Умножая обе части (13^ на       суммируя по г = 1,     , п и учитывая, что a:°FA(i',y0^ ^

< і»Faу0), получаем Е^(»,ї°) < 1>^дОЛу0) ЛеВая

1=1      t=i х

часть этого неравенства по правилу 13 46) равна Fa{x°, у0), прав^ его часть также равна Fa(x°, у°), и мы приходим к противоречию Аналогично формулируется правило наименьшего и наибольгце го значения функции Fx(:r0,y) при произвольном фиксированном

4. Рассмотрим теперь основной результат теории матричных игр — теорему фон Неймана, положившую начало современной теории игр

Теорема 13.2 (теорема фон Неймана) Для любой матричной игры Гд

max mm Fa (ж, у) = mm max Fa (ж, у)          (13 9)

xeSn yeSm      y€S,n xSSn

Другими словами в смешанном расширении любой матричной игры нижняя и верхняя цена игры совпадают Общее значение ле­вой и правой части (13 9) называется ценой игры Га в смешан­ных стратегиях и обозначается через vA

Укажем основную идею доказательства теоремы 13 2 В игре с пла­тежной матрицей А исход С 6 К называется гарантированным исходом игрока 1, если у игрока 1 существует такая смешанная стратегия х что при любой смешанной стратегии у игрока 2 выполняется неравен­ство Fa{x°, у) > с Исход с называется гарантированным исходом иг­рока 2, если у игрока 2 существует такая смешанная стратегия у0, что при любой смешанной стратегии х игрока 1 выполняется неравенство Fa(x,j/°) < с Если одно из этих неравенств выполняется как строгое то говорят, что исход с строго гарантируется игроку

Очевидно, что ни один исход С Є К не может одновременно строго гарантироваться игроку 1 и гарантироваться игроку 2 (тогда выполни лись бы неравенства Fa(x°,у°) > с и Рл(х°,у0) < С, что невозможно) Таким образом, множество строго гарантированных исходов игрока 1 и множество гарантированных исходов игрока 2 не пересекаются Утверж дение теоремы фон Неймана эквивалентно тому, что эти множества об­разуют покрытие действительной прямой, т е каждый исход С Є К либо строго гарантируется игроку 1, либо гарантируется игроку 2 В самом деле ясно что произвольный исход с Є К строго гарантируется игро­ку 1 тогда и только тогда, когда с < max mm Ра(х,у), гарантируется

mcv 2 тогда и только тогда, когда С > mm max Fa (х, у) Если бы вы

1іГрОЛ.Г        yeSm x

ляялось неравенство max mm Рл(х,у) < mm max Fa(x, у), то любой

схоД С-* включенный между ними, не являлся бы ни строго гарантиро-дляым исходом игрока 1, ни гарантированным исходом игрока 2

Для доказательства теоремы фон Неймана достаточно доказать, что в произвольной матричной игре нулевой исход либо строго гарантирует-игроку 1, либо гарантируется игроку 2 (так как переход от нулевого йСХОда к исходу С осуществляется прибавлением константы С ко всем элементам платежной матрицы) Далее, в силу правила 13 5, гарантиро ванность исхода игрока против произвольной смешанной стратегии дру foro игрока равносильна гарантированности этого исхода против любой чистой стратегии другого игрока Таким образом, утверждение теоремы фон Неймана сводится к тому, что для произвольной матрицы А имеет место одна из следующих двух альтернатив

(а) Существует такой вероятностный вектор х° Є S„, что для всех j = 1, т выполняется неравенство Fa(x°,j) > О,

(fl) Существует такой вероятностный вектор у0 Є Sm, что для всех г= 1,п выполняется неравенство Fa(i У°) < О

Это так называемая лемма о двух альтернативах Доказательство леммы основано на теореме об отделяющей гиперплоскости Неслож­но проверить (см , например, [4]), что первая альтернатива реализу ется, если выпуклая оболочка системы векторов (ei e^b1, ,bm), где ei, ,е„ единичные векторы пространства R" и b1, ,bm — векторы-столбцы матрицы А, не содержат нулевой точки, в противном случае реализуется вторая альтернатива

Замечание Цена va игры Та в смешанных стратегиях удовлетво ряет двойному неравенству

vl

где v — нижняя цена, v2 — верхняя цена матричной игры Та

Действительно, пусть г* — максиминная (чистая) стратегия иг­рока 1 в игре Та Тогда при любом j = 1, т выполняется неравен­ство FA(i*,j) > vi По правилу гарантирующей стратегии 13 5,а) отсюда следует, что при любой смешанной стратегии у Є Sm вы­полняется неравенство F^li* ,у) > vx, откуда mm Fa (г*, у) >

yesm

значит, max mm Fa (ж, у) > vi, т е va > щ Аналогично проверя-

x£Sny€Sm

ется неравенство г>д < v2 Таким образом, если матричная игра Гд Имеет цену в чистых стратегиях, то, согласно (13 10), цена игры Гд в чистых стратегиях и цена игры Гд в смешанных стратегиях сов падают

Из теоремы 13.2 вытекает ряд важных следствий, касающихСя оптимальных стратегий игроков и седловых точек в смешанном решении матричной игры. Понятие седловой точки в смешанном расширении игры Гд вводится аналогично понятию седловой точки матричной игры. А именно, она определяется как ситуация (ж0,)/1) в смешанных стратегиях, одностороннее отклонение от которои уменьшает (точнее, не увеличивает) выигрыш отклонившегося игрока FA(x,y°) < FA(x°,y°) < FA(x°,y) (х Є 5П, у Є Sm).

Далее, максиминные (минимаксные) стратегии игроков в сме­шанном расширении матричной игры определяют тем же спосо­бом, что и для матричной игры, — при замене оценочной функ­ции аг  = mina^ на оценочную функцию а(х) =   min FA(x,y)

3          y€Sm '

и оценочной  функции /З3   =   maxa^  на оценочную функцию

г

/3(у) = max FA(x, у). Максиминная смешанная стратегия х° игро-

x€Sn

ка 1 характеризуется равенством

q(x°) = тахй(ж) = max min FA(x,y) = vA, (13.11)

а минимаксная смешанная стратегия у0 игрока 2 — равенством

Р{у°) = min Щу) = min maxFA(x,y) = vA. (13.12)

yeSm   yeS„, x£S„

Доказательство теоремы 13.1 переносится на случай смешанно­го расширения матричной игры практически без изменений (с заме­ной оценочных функций аг и (З3 на а(х) и /3(у)). Учитывая теорему фон Неймана, имеем следующий результат.

Теорема 13.3. (связь седловой точки с ценой игры в смешан­ном расгиирении матричной игры).

Пусть (х°;у°) — седловая точка в смешанном расширении матричной игры Гд. Тогда:

а)         х° — максиминная стратегия игрока 1;

б)         у0 — минимаксная стратегия игрока 2;

в)         исход в седловой точке равен цене игры.

Любая ситуация в смешанных стратегиях (х°,у°), где х° ~~ м.аксиминная стратегия игрока 1 и у0 — минимаксная стартегия игрока 2, является седловой точкой в смешанном расширении игры Гд.

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

Следствие 2. В смешанном расширении матричной игры ис­ходы во всех седловых точках совпадают и равны цене игры в сме­шанных стратегиях.

Следствие 3. Пусть X — множество максиминных стратегий ЙГрока 1, Y — множество минимаксных стратегий игрока 2, Е — множество седловых точек в смешанным расширении игры Га-

Тогда  _           _

£ = 1*хГ*. (13.13)

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

а)         Под оптимальной стратегией игрока 1 будем понимать его максиминную стратегию;

б)         под оптимальной стратегией игрока 2 будем понимать его минимаксную стратегию;

в)         под оптимальной ситуацией будем понимать седловую точку.

В этих терминах теорема 13.2 означает, что для класса матрич­ных игр введенные принципы оптимальности реализуются в сме­шанных расширениях этих игр. Следствие 3 показывает, что дан­ные принципы оптимальности согласованы между собой, а след­ствие 2 — что они согласованы с принципом оптимальности ис­ходов, согласно которому оптимальным исходом матричной игры является ее цена в смешанных стратегиях.

5. Задача 16. Профилактика нежелательного события.

Принимающий решение ожидает наступление одного из т не­желательных событий, не располагая никакими данными о вероят­ностях их наступления. В качестве нежелательных событий могут выступать, например, стихийные бедствия, неисправности в функ­ционировании технической или организационной системы, провер­ки со стороны контролирующего органа и т.п. Величина ущерба При наступлении события j равна q3 > 0 (j = l,m) и известна принимающему решение.

Имеется п профилактических действий, направленных на Уменьшение ущерба от нежелательных событий; пусть рг > 0 — стоимость г-го профилактического действия (г = 1,п). Если прини­мающий решение выбирает профилактическое действие г, а «при­рода» осуществляет событие j, то итоговые потери для принима­ющего решение будут выражаться некоторой величиной Ь? (г = ^ l,n; j — l,m). Для простоты будем считать что всякое профи-

7 Розен В В

193

лактическое действие либо сводит ущерб от нежелательного собы тия до нуля (защищает от последствий этого события), либо не ока зывает никакого влияния на величину ущерба (не защищает от ц0 следствий нежелательного события). Тогда потери в ситуации ({, jj составляют

:     I pi,  если действие г защищает от последствий события j I Pi + Qj — в противном случае.

В результате получаем матричную игру принимающего решение (игрок 1) с природой (игрок 2), причем матрица ||^|| является матрицей потерь для принимающего решение.

В данной матричной игре принимающий решение имеет шесть стратегий (не строить дамбу вообще или строить дамбу высоты Ы, і — 1,5); природа также имеет шесть стратегий (не осуществлять наводнение или осуществить наводнение j'-й категории, j = 1,5)-

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

где С — любая константа (в данном случае константа С может интерпретироваться как сумма, выделенная на строительство дам­бы, тогда выигрыш а представляет собой сэкономленную сумму). Взяв, например, С = 30, получаем матрицу выигрышей, заданную табл. 13.6.

В полученной матричной игре имеется единственная седловая точ­ка (Л5;5).

Итак, рассматриваемая матричная игра имеет седловую точ­ку в чистых стратегиях; стратегия г* = /15 является оптимальной (максиминной) стратегией игрока 1, а стратегия j* = 5 — опти­мальной (минимаксной) стратегией игрока 2. Цена игры в чистых стратегиях существует и равна 10 денежным ед.

7'

195