3.5. Принятие решений в условиях конфликта (элементы теории игр)

J(x,z)—» шах, ге (3.10)

х&Х

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

1{х,1)-ътах,хе X. (3.11)

Подобные конфликтные задачи ПР первоначально были формализованы как задачи анализа салонных игр, что придало всей терминологии несколько легкомысленное звучание. Так, обе противоборствующие сто­роны называются игроками, выбираемые ими альтернативы (соот­ветственно х и г) — ходами, правила выбора решений — стратегиями, значения функционалов У и I— выигрышами, а вся теория ПР с неопре­деленностью типа "активный партнер" — теорией игр. Иногда задачи ПР в условиях "природных" неопределенностей, которые мы рассматривали в предыдущем разделе, называют играми против природы.

Итак, пусть два субъекта А и Б, располагающие возможностью выбора, соответственно, элементов х £ X и стремятся к достижению своих

целей, представленных в виде (3.10), (3.11).

Расхождение между функционалами I и J определяет степень антагониз­ма игроков. В частном случае может оказаться, что У = -/ при любых х и г\ такую ситуацию, возникающую в игре двух субъектов, называют анта­гонистической, строго конкурентной или игрой с нулевой суммой (У +1 = = 0). Однако чисто антагонистическая ситуация является в известном смысле вырожденной. Наиболее типичен конфликт, в котором интересы игроков не совпадают, но и не строго противоположны.

Легко представить себе ситуацию, когда не два, а к игроков максимизи­руют свои выигрыши р/(х\ х², ..., i = 1, ..., к. В этом случае, например, для первого игрока, выбирающего решение х\ остальные х¹ будут со­ставлять фактор неопределенности z: р_х (х_}, z) —> max, z = (х², ..., х^А~).

х¹еХ

к

^Гр. =0, то мы по-прежнему говорим об игре с нулевой суммой, хотя

/=1

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

Итак, пусть две стороны А и Б стремятся к достижению своих целей: А : J(x,z) —> max, zeZ;

Б : /(x,z) —> max, хеХ.

zgZ

Оба лица, принимающие решения (ДПР), или оба "игрока", располагают возможностью выбора х и z соответственно. Далее для определенности будем полагать, что X с RZ с R"\ т. ел и z — числовые векторы соот­ветствующих размерностей.

Пример такой постановки задачи уже приводился — это пример В.4 из Введения ("дилемма заключенного"). Проводя рассуждения со стороны первого игрока (игрока А), легко установить, что оба функционала Jul задаются табл. 3.13.

На пересечении строки I и столбца у в табл. 3.13 стоит пара чисел (р, #), где р = ^х_ь Zy), q - 1(х_ь Гу). В данном примере, очевидно, требуется мини­мизировать функционалы / и /, а не максимизировать.

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

В связи с тем, что исход нашего выбора решения зависит от выбора иг­рока Б, необходимо сделать какие-то предположения о его возможном поведении в процессе решения задачи. Правомерность подобных пред­положений (гипотез) впрямую зависит от характера информированности сторон о поведении другой стороны.

При принятии решений в условиях риска (а подобные задачи, как уже говорилось, могут также относиться к теории игр — игр против приро­ды) мы, по существу, предполагали, что сторона Б ("природа") действует не целенаправленно. Мы предполагали, что каждый выбор z = z, (при дискретном множестве z) характеризуется своей вероятностью, т. е. мы могли оценить частоту появления тех или иных Z/ и в соответствии с этим строили свою стратегию поведения. Это одна из возможных гипотез. При игре с "думающим" противником, который преследует в процессе принятия своих решений вполне определенные цели, разумно прибегать к иным гипотезам, лучше отражающим существо такой задачи. По сути дела особым характером вводимых гипотез данный раздел теории ПР и выделяется в отдельную теорию — теорию игр.

Будем различать следующие основные гипотезы (случаи).

Гипотеза 1. Каждый из субъектов А и Б не имеет информации о выборе, сделанном второй стороной. Дополнительные гипотезы о характере по­ведения второго игрока отсутствуют. В этом случае можно поступать аналогично решению задачи в условиях полной неопределенности. Это, по существу, в точности тот же случай, и мы можем воспользоваться из­вестным принципом наилучшего гарантированного результата. Для субъекта А гарантированная оценка будет равна

J* = шах min J(x, z), (3.12)

хеХ zeZ

а для субъекта Б

/* = max min I(x, z). (3.13)

zeZ хвХ

Решая задачи максимизации (3.12), (3.13), мы находим и векторы х*, z*, реализующие соответствующие гарантированные оценки.

Пример 3.11. Дадим графическую иллюстрацию применения принципа гарантированного результата. Пусть J(x, z) = х² - z², I(x, z) = -J(x, z) и требуется минимизировать J и I. В результате мы имеем антагонистиче­скую игру:

J(x, z) = х² - z² —» min, z e Z; J(x,z) = -/(x,z) -x² -z² —» max, xeX.

zeZ

Будем считать, что X = Z = R есть множества всех вещественных чисел (здесь мы использовали то очевидное обстоятельство, что вместо поиска

минимума функции I можно искать максимум функции -/ = J).

J* = min max J(x, z).

X z

Обозначим

ф(х) = max/(x,z). (3.14)

Таким образом, для вычисления одного значения функции ср при фикси­рованном х необходимо решить задачу оптимизации (3.14). Получим

ф(х) = max(x² -z²) = x²,

г

Т. к. любой z Ф О приводит к уменьшению функции Теперь находим

min ф(х) = min х² = О,

X X

что достигается при х = 0. Таким образом, мы получим J* = 0 и при этом х* = 0. Это гарантированный результат, ибо при любом z мы будем иметь значение J не хуже (т. е. не больше), чем ноль, т. е. при любом z

/(х*, z) = /(0, z) = -z² < У⁰ = 0.

На рис. 3.3, а представлены линии постоянного уровня функционала /(х, z) на плоскости (х, z).

Вспомним, что линией уровня называется геометрическое место точек на плоскости, где /= С = const. Меняя постоянную С, мы будем получать различные линии уровня. Если функция зависит более чем от двух пере­

менных, то следует говорить не о линиях уровня, а о поверхностях уровня. На рис. 3.3, б изображена зависимость J(x, z) в трехмерном пространстве, имеющая характерный вид "седла". Можно считать, что соответствую­щая поверхность "склеена" из двух видов парабол:

У\ = У г = "Z².

При выборе гарантирующего решения х* = 0 мы при различных z будем всегда находиться на параболе А (рис. 3.3, б), обеспечивая выполнение неравенства / < J* = 0.

Гипотеза 2. Предполагаем, что субъект Б следует принципу максимина и выбирает z из условия (3.13):

Г = max min 1{х, z).

zeZ дгеА'

Тогда мы можем выбирать х согласно правилу

J (х, z*) —> max, (3.15)

где z* — гарантирующее решение второго игрока. Обозначим решение задачи (3.15) через х**. При этом оказывается, что

J* =J(xⁿ, z*)>j\ (3.16)

где J* — наша гарантированная оценка, получаемая по принципу мак­симина.

Упражнение. Доказать неравенство (3.16).

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

Пример 3.12. Игра с нулевой суммой задана с помощью табл. 3.14, где числа на пересечении строк и столбцов означают наш выигрыш, т. е. проигрыш игрока Б — нашего соперника.

Таблица 3.14. Игра с нулевой суммой

X

z₄

Наша гарантирующая стратегия х* = х₃, а гарантированная оценка J* = 2. (Если бы мы выбрали другое решение, отличное от л₃, то могли бы в зависимости от действий игрока Б получить и меньшее значение выигрыша, чем 2.) Аналогично для игрока Б (он в отличие от нас стре­мится минимизировать наш выигрыш, а тем самым и свой проигрыш) имеем z* = z₄, Г = 4. Действительно, игрок Б выбирает тот столбец, в котором максимальное число было бы наименьшим. В первом столбце максимальное число равно 8, во втором — 7, в третьем — 15 и в четвер­том — 4. Следовательно выбирая z* = z₄, игрок Б никогда не проиграет больше четырех условных единиц.

Если выбирать х** из условия

J{x,2*) —> шах ,

то мы получаем jc** = х₄, J(x** ,z*) = J* = 4> J* = 2. Таким образом, сле­дуя гипотезе 2, можно, вообще говоря, получить лучший результат по сравнению с принятием решений на основе принципа гарантированного результата.

Гипотеза 3. Мы теперь можем допустить, что субъект рассуждает точно так же, как и в предыдущем случае, т. е. использует не стратегию z*, а аналогичную стратегию z**. Поэтому мы можем это учесть и выбирать

оптимальное решение с учетом уже этой гипотезы:

** *** ***

J(x,z )—>max=>x ,J .

Гипотеза 4. Возможен другой сорт гипотез: мы по условиям игры знаем первый ход субъекта Б (он обязан сообщить его нам).

J{x,z) —> max . (3.17)

Условие (3.17) позволяет для каждого фиксированного z определить ис­комое значение х, т. е. задать функцию x(z).

Для этого случая мы также можем определить гарантированный резуль­тат J

J - min max J(x₉ z) = min J(x(z), z).

zeZ xgX zeZ

Результат J будет отличаться от значения J*, найденного согласно ги­потезе 1. Именно, во всех случаях будем иметь

J>J\ (3.18)

Таким образом, принятие гипотезы 4 вновь позволяет улучшить результат, полученный по принципу максиминного гарантированного результата.

Докажем неравенство (3.18), которое имеет вид

min max J(;t, z) > max min J(x, z).

zeZ xeX xeX zeZ

Для любых фиксированных x', z', очевидно, справедливо неравенство

ф₁(2^/)>ф₂(^^/), (3.19)

где

ф_{(z) = max J(x,Z);