47. Антагонистические игры.

Задача нахождения оптимальной стратегии в матричной антагонистической игре также сводится к линейному программированию.

В матричной антагонистической игре рассматривается ситуация, которую можно представить как противоборство двух игроков, каждый из которых располагает некоторым конечным набором действий. Эти действия (стратегии) могут быть пронумерованы и далее отождествлены со своими номерами. Пусть первый игрок (1) выбирает действие из множества , а второй (2) – из множества .

Если игрок (1) выбрал действие i, а игрок (2) выбрал действие j, то первый игрок получает выигрыш , а второй – проигрыш . Величины образуют платежную матрицу игры. Игра называется антагонистической или с нулевой суммой, так как выигрыш одного игрока является проигрышем другого (сумма выигрышей равна нулю).

Особое значение среди таких игр имеют вполне определенные игры.

В таких играх

Свойство определенности зависит от матрицы A. Например, игра с матрицей вполне определена и ее значение v = 4.

Игра с матрицей не определена: .

Для решения неопределенных игр вводят смешанные стратегии – вероятностные распределения на множествах стратегий игроков. Эти стратегии могут быть описаны векторами - для первого игрока и - для второго игрока, где - вероятность для первого игрока выбрать стратегию i, а - вероятность для второго игрока выбрать стратегию j.

Для векторов x, y при этом выполняются условия нормировки вероятностей: , , что мы можем записать в виде условий:

, .

Результат игры при этом определяется как среднее значение выигрыша и в пространстве смешанных стратегий игра является вполне определенной:

(1)

Рассмотрим игрока (1), имеющего в своем распоряжении вектор x. Выбрав какой-либо x, он может быть уверен в том, что получит в среднем по крайней мере

Оптимальный выбор x заключается при этом в нахождении

(2)

Симметричные рассуждения за второго игрока приводят к задаче

(3)

и равенство (1) утверждает, что при этом никто из игроков не получает одностороннего преимущества.

Задачи (2)-(3) могут быть переписаны в стандартной форме задачи линейного программирования:

(4)

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

или

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

48. Игры с ненулевой суммой и кооперативные игры.

49. Позиционные игры.

50. Графы. Основные определения. Задача о кратчайшем пути в графе. Алгоритм Форда.