3.6. Основные понятия теории игр

Постановка задачи принятия решений следующая:

В задаче полагается, что фактором неопределенности управляется «разумным» противником. Его цели выражаются аналогично (3.31):

Такая задача (неопределенность типа «активный партнер») относится к теории игр. Противоборствующие стороны будем называтьигроками; выбираемые противниками альтернативы (xиz)—ходами; правила выбора решений—стратегиями; значения функционаловJиI—выигрышами.

Расхождение между функционалами JиIопределяет степень антагонизма игроков. Может оказаться, чтоJ= –Iпри любыхxиz. Такую игру будем называть антагонистической, строго конкурентной, игрой с нулевой суммой (J+I= 0). Такая антагонистическая ситуация является вырожденной. Более типичен конфликт, в котором интересы игроков не совпадают, но и не строго противоположны.

Представим ситуацию, когда не два, а kигроков максимизируют свои выигрышиp_i(x¹, x²,…, x^k),i=1,…,k.

Пусть для первого игрока, выбирающего решение x¹, остальные составляют фактор неопределенностиz:p_i(x¹, z). Если=0, то мы говорим об игре с нулевой суммой. Будем рассматривать игры двух лиц А — (3.31) и Б — (3.32). В общем случае,X,Z— векторные пространства разных размерностей. Представим задачу в виде таблицы (рис.3.2).

Рис. 3.2. Постановка задачи игры для двух игроков.

На пересечении строки iи столбцаjстоит пара чисел (p,q), гдеp=J),q=I), с точки зрения игрока А. Функционалы требуется либо максимизировать, либо минимизировать, в зависимости от постановки задачи. В дальнейшем рассматриваем задачи с позиции игрока А. При принятии решений в условиях риска (подобные задачи могут быть отнесены к теории игр), предполагалось, что сторона Б — это внешние факторы («природа»). При игре с «думающим» противником введем гипотезы суть которых выделяет в теории ПР отдельную теорию — теорию игр. Будем различать следующие основные гипотезы.

1. Пусть каждый из субъектов А и Б не имеет информации о выборе противоположной стороны. Будем поступать аналогично задаче принятия решений в условиях полной неопределенности.

Для субъекта А:

Для субъекта Б:

Рис. 3.3. Линии постоянного уровня (J =20,J =10,J =0)

где z^* — гарантирующее решение игрока Б. Обозначим решение задачи (3.33) через x^**. Оказывается что

где — гарантированная оценка субъекта А, получаемая по принципу максмина (3.33). Неравенство (3.35) может быть строгим, тогда, следуя гипотезе 2 можно получить выигрыш, выбираяx^**, а не x^*.

Рассмотрим пример, игру с нулевой суммой (таблица 3.3).

На пересечении строки и столбца стоит значение критерия (выигрыш игрока А, или проигрыш игрока Б).

Минимаксная гарантирующая стратегия игрока А — x^*= x₃, гарантированная оценка . Если бы игрок А выбрал другое

Таблица 3.3

Игра с нулевой суммой

X	Z
	z1	z2	z3	z4
x1	5	-10	9	0
x2	6	7	8	1
x3	8	7	15	2
x4	3	4	-1	4

решение, отличное от x₃, то мог, в зависимости от действий игрока Б, получить и меньшее значение выигрыша. Игрок Б (игра с нулевой суммой) стремится минимизировать наш выигрыш, тем самым и свой проигрыш. Т. е. игрок Б выбирает столбец, в котором максимальное число было бы наименьшим. Максминный критерий дает ,. Игрок Б не проиграет больше четырех условных единиц. Если игрок А выберетx^** из условия то получитx^**= x₄, . В общем случае на основе гипотезы 2 можно получить лучший результат.

3. Допустим, что игрок Б поступает согласно гипотезе 2, т. е. использует стратегию . Игрок А с учетом этого выбирает оптимальное решение.

4. Пусть игрок А знает первый ход игрока Б. Тогда решение игрока А — x = x(z). Для каждого фиксированного z, можно определить искомое значение x, решая задачу оптимизации:

Можно определить гарантированный результат :

Результат будет отличаться от, найденного согласно гипотезе 1. Будем иметь:

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

Доказательство (3.38). Неравенство (3.38) имеет вид:

Для любых двух фиксированных , справедливо неравенство:

где ,.

Пусть ,.

Тогда: .

Таким образом (3.40) доказано. Поскольку могут быть любыми, выберем;. Подставим эти значения в (3.40), получим (3.39).

Рассмотрим игру (таблица 3.3). . Дляимеем:.

5. Пусть Б знает ход А. Естественно предположить, что Б будет придерживаться стратегии z = z(x), которая является решением оптимизационной задачи:

(согласно гипотезе 4). Сохраняем допущение, что субъект А сообщил свой ход субъекту Б, а также допущение об использовании субъектом Б стратегии z(x). Это позволяет субъекту А воздействовать на выбор субъекта Б, чтобы он в максимальной степени соответствовал целям субъекта А. Выбор субъекта А:

Если максимум (3.41) достигается не в одной точке z, а на некотором множестве M(x), то гарантированный результат определяется как:

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