Многошаговые задачи выбора решений

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

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

Пример 2.8 (задача инспектированияПредлагаемый пример подобен задаче, описанной в книге: Оуэн Г. Теория игр. М.: Мир, 1971. ). Пусть сторона P1 ( нарушитель ) заинтересована в совершении некоторого запрещенного действия. При этом нарушение может быть совершено в один из N>1 периодов времени. Примерами таких действий могут быть ухудшение экологического состояния (сброс мусора или слив загрязненных вод), продажа партии бракованного товара, несоблюдение предписанных норм при строительных работах и т.п.

Сторона P2 ( инспектор ), задачей которой является предотвращение запрещенных действий, может осуществить единственную инспекцию в один из этих N периодов времени.

Отношения сторон являются антагонистическими, причем выигрыш нарушителя равен 1, если совершенное им нарушение не было обнаружено. Установление инспектором факта нарушения (что возможно лишь в том случае, если инспекция проводится в тот же период времени, что и запрещенное действие) ведет к потерям нарушителя, которые оцениваются как величина, равная - 1.

Операция завершается либо совершением запрещенного действия, либо проведением инспекции. Допускается, что в течение всех N периодов сторона P1 воздерживалась от нарушений, а сторона P2 - от инспекций. В этом случае выигрыш нарушителя равен нулю.

Для иллюстрации условий задачи на рис. 2.12 представлено дерево описанной игры, соответствующее случаю N=2. Символы Н и И маркируют(правые) дуги дерева, соответствующие совершению нарушения (Н) стороной P1 и проведению инспекции (И) стороной P2. Дуги без маркировок представляют альтернативные варианты (т.е. отказы сторон от совершения действий). Одноэлементные информационные множества стороны P1 обозначены пунктирными кружками, а двухэлементные множества стороны P2 - пунктирными прямоугольниками. Множества нумеруются снизу вверх (на рисунке номера множеств не указаны).

Отметим, что наличие двухэлементных множеств (отражающих неинформированность инспектора о действиях нарушителя) свидетельствует о том, что рассматриваемая задача не является игрой с полной информацией (см. определение в лекции 8).

Описанному дереву сопоставим $$4\times 4$$ матрицу игры, представленную в табл. 2.11. Символы О входят в двухсимвольные пары, обозначающие стратегии сторон, и соответствуют отказам от действий. Первые две строки и два столбца матрицы повторяют друг друга, что является следствием дублирования стратегий (см. замечание в лекции 9).

Найдем решение этой игры в смешанных стратегиях x, $$y\in S_4$$, полагая (в связи с отмеченным дублированием), что$$x_1 = y_1 = 0.$$ Равенства (13.1) позволяют записать условия нормировки для распределений x и y в виде отношений$$x_2 + x_3 + x_4 = y_2 + y_3 + y_4 = 1.$$

Из (11.18), (12.18) и определения смешанных стратегий (см. лекцию 11) следуют неравенства$$M(x(i),y) \le v \le M(x, y(j)),\quad 1 \le i,\ j \le 4.$$ для оптимальных смешанных стратегий x, $$y\in S_4$$, цены игры v и смешанных стратегий x(i) и y(j), представляющих чистые стратегии сторон P1 и P2 соответственно с номерами i и j. Для матрицы из табл. 2.11 условия (13.3) эквивалентны неравенствам$$M(x, y(2)) = - x_2 + x_3 + x_4 \ge v,$$ $$M(x, y(3)) = x_2 - x_3 + x_4 \ge v,$$ $$M(x, y(4)) = x_2 + x_3 \ge v,$$ $$M(x(2), y) = - y_2 + y_3 + y_4 \le v,$$ $$M(x(3), y) = y_2 - y_3 + y_4 \le v,$$ $$M(x(4), y) = y_2 + y_3 \le v,$$ при выводе которых учтено допущение (13.1).

Из (13.4), (13.5) и условий (13.2) следуют неравенства$$2 x_2 \le 1 -v,\qquad 2 x_3 \le 1 -v,$$ которые в сочетании с (13.6) дают отношения$$v \le x_2 + x_3 \le 1 -v,$$ приводящие к оценке$$v \le \frac{1}{2}.$$ Аналогично, из (13.7), (13.8) и (13.2) следуют неравенства$$2 y_2 \ge 1 - v,\quad 2y_3 \le 1 -v,$$ которые в сочетании с (13.9) дают отношения$$1 - v \le y_2 + y_3 \le v,$$ приводящие к оценке, обратной (13.12). Следовательно,$$v = \frac{1}{2}$$ и, согласно (13.1), (13.2) и (13.10), (13.11),$$x_1 = 0,\quad x_2 = \frac{1}{4},\quad x_3 = \frac{1}{4},\quad x_4 = \frac{1}{2}.$$ Аналогично, из (13.1), (13.2) и (13.13)-(13.15) вытекают оценки$$y_1 = 0,\quad y_2 = \frac{1}{4},\quad y_3 = \frac{1}{4},\quad y_4 = \frac{1}{2}.$$

Таким образом, согласно оптимальным смешанным стратегиям из (13.16), (13.17), вероятность совершения действия (нарушения или проверки) в любом из двух периодов равна $$\frac{1}{4}$$. Соответственно, полная вероятность отказа от совершения действия равна $$\frac{1}{2}$$.

Заметим, что с увеличением числа периодов N количество чистых стратегий каждой из сторон растет экспоненциально и определяется величиной 2N, а это неизбежно затрудняет как сведение игры к нормальной форме, так и анализ соответствующей матрицы (уже при не очень больших значениях N ). Непосредственное рассмотрение многошагового процесса выбора, которое мы проведем ниже, оказывается более простым.

В случае, когда N=1, игре соответствует $$2\times 2$$ матрица, представленная в табл. 2.12 и не имеющая седловых значений. Следовательно, эта игра имеет решение в смешанных стратегиях и, согласно (11.10), ей соответствует цена$$v_1 = \frac{1}{3}.$$