Бережная_Матметоды моделирования эк cистем

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

Аналогично определим по каждому столбцу матрицы ру = maxa^y,

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

Пример 9.8. Дана платежная матрица 3 x 4 , которая опреде­ ляет выигрыши игрока Л, Вычислить нижнюю и верхнюю цены за­ данной игры.

10 4 И 7

7 6 8 20

6 2 1 11;

Решение

Если игрок А выбирает первую стратегию, он может получить выигрыш в размере 10, 4, 11 или 7 д. е. в зависимости от выбран­ ной стратегии игроком В, При этом выигрыш игрока будет не мень­ ше aj = min{10; 4; 11; 7} = 4 д. е. независимо от поведения игрока В, Аналогично при выборе игроком А второй стратегии гарантиро­ ванный выигрыш «2 ^ niin{7; 6; 8; 20} = 6 д. е. При выборе игро­ ком А третьей стратегии выигрыш аз = min{6; 2; 1; 11} = 1 д. е.

Таким образом, минимальные значения а/, / = 1,3 опреде­ ляют минимально гарантированный выигрыш для игрока А,

330

если он выбирает соответствующую стратегию /. Величина maxtt/ =max{4; 6; l}=6 д.е. будет гарантированным выигрышем иг-

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

брав первую стратегию Pj, ифок В может проиграть не более чем Pi = max{10; 7; 6} = 10 д. е. независимо от выбора стратегии ифоком А. Аналогично рассуждая, получим следующие результаты (д. е.):

Р2 = max {4; 6; 2} = 6; Рз = max {И; 8; 1} = И; Р4 = тах{7; 20; 11} = 20.

Ифок В выбирает стратегию Р2, которая минимизирует его мак­ симальные проифыши:

Р = min р; = min{10; 6; 11; 20} = 6 д. е.

у

Величина Р = 6 д. е. будет гарантированным проифышем ифока В при любых стратегиях ифока А, Выбранная игроком В вторая стратегия называется минимаксной стратегией, а соответствующее ее значение проифыша Р2 = 6 д. е. будет верхней ценой ифы.

Следует отметить, что для любой матрицы А = ||д^у|| выполняет­ ся неравенство

Если Р = а, т. е. верхняя цена равна нижней цене ифы, то со­ ответствующие чистые стратегии называются оптимальными, а про ифу говорят, что она имеет седловую точку, Седловая точка явля­ ется минимальным элементом соответствующей строки и макси­ мальным элементом соответствующего столбца. Эта точка есть точ­ ка равновесия ифы, определяющая однозначно оптимальные стра­ тегии. Оптимальность здесь означает, что ни один ифок не стре­ мится изменить свою стратегию, так как его противник может на это ответить выбором другой сфатегии, дающей худший для пер­ вого игрока результат.

Величина С = Р = а называется ценой игры. Она определяет средний выифыш ифока А и средний проигрыш игрока В при ис­ пользовании ими оптимальных стратегий. В нашем примере цена ифы С = 6 д. е., оптимальная пара стратегий — ^^2 и В2.

Если в платежной матрице А все элементы строки А^ = {а^, Л/2,

..., aif^ не меньше соответствующих элементов строки Aj^ = (a^^j, aj^i^

331

..., Qj^f^y a no крайней мере один строго больше, то строка Ai назы­ вается доминирующей, а строка Aj^ — доминируемой.

Аналогичны понятия «доминирующий столбец» и «доминируе­ мая строка».

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

Пример 9.9. Для игры с платежной матрицей

|2 -3 5 Л = 4 -2 3 |б -1 4

найдите стратегии ифоков и цену игры.

Решение

Элемент 0^,2 = —1 является наименьшим в третьей строке и на­ ибольшим во втором столбце, т. е. он является седловой точкой. Поэтому цена игры С = - 1, а оптимальные стратегии игроков: первого — У4З, а второго — ^2-

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

В матрице А третья строка доминирует над второй, поэтому вторую можно изъять из платежной матрицы. В результате полу­ чится матрица

В матрице /Ij первый и третий столбцы доминируют над вто­ рым, следовательно, их можно изъять. В результате платежная ма­ трица принимает вид

в матрице А2 вторая строка доминирует. После вычеркивания получится матрица А^, состоящая из одного элемента:

Аъ = (-1).

Элемент матрицы А-^ и определяет решение нашей задачи.

332

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

где Р^ — вероятность выбора /-й стратегии игроком и удовлетворяет следу­ ющим условиям:

Pi > О, / = 1,/и;

т

(9.39)

/=1

Аналогично смешанная стратегия игрока В представляет собой вектор

где qj — вероятность выбора у-й стратегии игроком В — удовлетворяет сле­ дующим условиям;

(9.42)

Платежная матрица игры имеет следующий вид (табл. 9.8):

333

Игрок Л выбирает стратегию Pi так, чтобы максимизировать на­ именьший ожидаемый выигрыш по столбцам платежной матрицы, тогда как игрок В выбирает стратегию qj с целью минимизировать наибольший ожидаемый проигрыш по строкам. Математически кри­ терий минимакса при смешанных стратегиях может быть описан следующим образом. Игроке выбирает стратегию Р/, дающую

Когда стратегии Р^ и qj оптимальны, то выполняется строгое равенство между максиминным ожидаемым выифышем и мини­ максным проигрышем, а результирующее значение равно опти­ мальному (ожидаемому) значению игры.

Этот вывод следует из теоремы фон Неймана о минимаксе. Тео­ рема утверждает, что выражения (9.43), (9.44) имеют одно и то же значение M(PQ,QQ), называемое ценой игры. Если Р/^ и qf - опти­ мальные решения для обоих игроков, каждому элементу платежной матрицы ау соответствует вероятность Р/ . qj. Следовательно, оп­ тимальное ожидаемое значение игры

M{PoMo)=iiciij'P/^-q/. (9.45)

/=1у=1

Цена игры заключена между нижней и верхней ценами, т. е.

а < М{Ро, QQ) < р.

334

Решить конечную игру — это значит нужно найти векторы Р и Q (оптимальные стратегии), удовлетворяющие теореме о минимаксе, а следовательно, получить величину ожидаемого платежа М{Р^, Qo) - цену игры.

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

Решение игры обладает одним важным свойством: если игрок

Аиспользует свою оптимальную стратегию, а игрок В смешивает свои стратегии в любых пропорциях, то средний выигрыш игрока

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

мального из чисел тип.

Известно несколько методов нахождения оптимальных страте­ гий в играх двух лиц с нулевой суммой. Рассмотрим один из мето­

дов - метод линейного программирования для нахождения решения иг

Пусть игра m X « не имеет оптимального решения непосредст­ венно в чистых стратегиях, т. е. отсутствует седловая точка {аФ^). Оптимальное решение необходимо искать в области смешанных стратегий. Предположим, что все т стратегий игрока А полезные. Определим вероятности их применения в смешанной оптимальной стратегии. Обозначим эти вероятности через Р/, / = l,w, а цену иг­ ры - через М. Оптимальная смешанная стратегия игрока А опреде­ ляется из условия (9.43):

Поскольку при оптимальной стратегии средний выигрыш не меньше М при любой стратегии противника, то справедлива систе­ ма п неравенств:

335

/=i

Тогда задача отыскания оптимальной смешанной стратегии иг­ рока А может быть сформулирована в виде задачи линейного про­ граммирования.

Для этого необходимо максимизировать Z = М при ограниче­ ниях

т —

/=1

(9.49)

т

Введем новые неизвестные:

' Чтобы исключить возможность деления на нуль, увеличим це­ ну игры на положительное число С. Для этого достаточно ко всем элементам матрицы \\ау\\ прибавить одно и то же положительное число С, при этом все элементы a^j сделать положительными. Сле­ дует отметить, что эта операция не меняет искомых оптимальных стратегий, поскольку

Разделим левую и правую части неравенств (9.48) и (9.49) на Л/, получим:

maxi1/ = min—• = min{xi +X2 +... + x„]. M

336

Эта задача записывается как симметричная двойственная зада­ ча линейного профаммирования к задаче игрока A{9.S2), (9.53): максимизировать

где а,- - минимум в /-й строке; Ру — максимум ву-м столбце.

337

Нижняя цена игры равна максимину а = - 2, верхняя цена иг­ ры равна минимаксу Р = 2. Так как а ?^ Р, то седловая точка игры отсутствует, задача должна решаться в смешанных стратегиях.

Нижняя цена игры — число отрицательное (а = —2), поэтому, возможно, значение игры М не будет положительным. Число С, ко­ торое необходимо прибавить ко всем элементам матрицы, должно быть не меньше 2. Пусть С = 6. Тогда матрица принимает вид

Задача игрока В записывается в форме задачи линейного про­ граммирования

^шах = К, + Г2 + Уз + П

при офаничениях:

[юг,+ 9Г2+8}з+ ^4^1;

4Yi+UY2+5Yi+lOY4<l,

ЗУ,+ 8X2+3x3+12^4^1;

У;>0, у = 174.

Решая задачу симплекс-методом, получим:

i^3x = 0,16; У, = 0; У2 = 0; Уз = 0,12; У, = 0,04.

Таким образом, решением исходной задачи будет следующее:

0_Уз_0,12_

338

В нашем примере первая и вторая стратегии игрока В бесполез­ ны, так как qi = ^2^ = 0. При случайном чередовании третьей и четвертой стратегий с относительными частотами д^^ = 0,75 и ^4^ = 0,25 соответственно игроку В обеспечен средний выигрыш в размере М = 0,25.

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

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

Задачи

9.1. Для пяти проектов технических систем определены относи­ тельные единичные показатели технического совершенства конст­ рукции и коэффициенты весомости единичных показателей. Чис­ ленные значения единичных показателей и коэффициентов весо­ мости приведены в следующей таблице:

Относительные единичные показатели

Проведите ранжирование проектов технических систем по ком­ плексному критерию.

9.2. Одной из фирм требуется выбрать оптимальную стратегию по техническому обеспечению процесса управления производст­ вом. С помощью статистических данных и информации соответст-

339