Теорема о необходимых и достаточных условиях оптимальности смешанных стратегий. Метод сведения решения игр к решению задачи линейного программирования

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

Седловой точкой функции f(x,y), опред-ной на множ-ве X (множ-во стратегий первого игрока) Y(множество стратегий второго игрока), наз-ся пара () такая, что

Значение функции выигрыша в седловой точке называется ценой игры.

Т. [о необходимых и достаточных условиях оптимальности смешанных стратегий]

Пусть игра определена матрицей и ценой игры V. Для того, чтобы смешанная стратегия была оптимальной стратегией 1-го игрока выполнение следующего неравенства:

, (1)

Для того, чтобы смешанная стратегия была оптимальной стратегией 2-го игрока выполнение следующего неравенства:

(2).

Док-во: Рассмотрим с точки зрения 2-го игрока.

– оптимальная стратегия 1 игрока х ^* является первой координатой некоторой седловой точки ф-ции выигрыша М (х, у). Тогда по определению седловой точки:

, .

.

Так как это неравенство выполняется для , то оно выполняется и для k = 1..n.

Остается к=1,n. ЧТД.

Вып-ся (1):

, .

Выделим смешанную стратегию . Умножим каждое j неравенство на у_j и просуммируем. Эти у – неотр.

.

эта функция имеет седловую точку, выберем седловую точку (). Для нее вып-ся: . Следовательно

В таком случае (по следствию Т о седловой точке) для х, у , седловая точка х ^* – оптимальная стратегия для 1 игр. ЧТД.

СЛЕДСТВИЕ: Если для смешанных стратегий () и числа V одновременно выполняются (1) и (2), то () будут оптимальными стратегиями игроков, а V – цена игры.

Док-во: умножим (1) на y и просуммируем:

умножим (2) на x и просуммируем:

Получаем

Тогда по следствию Т о седловой точке точка () – седловая и – цена игры.

следует из того, что последнее неравенство выполняется для ; если подставить , то получим

ЧТД.

Метод сведения решения игр к решению задачи линейного программирования. (I метод)

Пусть игра определена матрицей и ценой игры V. По следствию теоремы

Если для смешанных стратегий () и числа V одновременно выполняются (1) и (2), то

– оптимальные стратегии игроков (*)

Требуется, чтобы V > 0. Если все a_ij > 0, то V > 0. Если $ a_ij < 0, то ко всем a_ij прибавляем |min a_ij |, тогда получим эквивалентные игры, то есть новое V = V +|min a_ij |, а стратегии те же.

1) Рассмотрим левую часть:

V > 0 необходимо здесь, чтобы не менялся знак, так как делим на V.

Обозначим , тогда

решение систем равенств и неравенств – задача оптимизации с целевой функцией, составленной с помощью одного равенства/неравенства и систем ограничений в виде других равенств/неравенств:

(1)

На max, потому что стратегия 2-го игрока

2) Рассмотрим правую часть (аналогично):

разделим на V > 0: (2)

Задачи (1) и (2) – двойственные, т.е. решение одной можно найти из решения другой (в последней симплекс-таблице в строке оценок). Значения линейных форм совпадут:

Обозначим некоторое число (3)

И в качестве возьмем (4)

Покажем, что – компоненты оптимальных смешанных стратегий игроков, а число V – цена игры с матрицей A.

– смешанные стратегии. Покажем оптимальность:

Умножив неравенства задач (1) и (2) на V получим (*) при полученных нами – оптимальное решение, а V – цена игры.

Алгоритм:

1. по матрице А составить (1) и (2)

2. найти решения

3. по (3) найти цену игры, по (4) оптимальные стратегии.