Поняття змішаних стратегій. Основна теорема матричних ігор. Результат гри як математичне очікування. Оптимальні стратегії. Рекомендації по порядку вирішення гри

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

В теории игр важное значение имеют смешанные стратегии. Введение смешанных стратегий означает разрешение применения вероятностного распределения в множестве стратегий.

Поскольку множества стратегий игроков Х и Y дискретны и конечны все вероятностные распределений на этих множествах просто конечным набором вероятностей. Если обозначить множество смешанных стратегий первого игрока S₁ а второго – S₂ :

, 1.1

, 1.2

и определение игры со смешанными стратегиями будет-.

Г=S₁,S₂,W(P,Q)},PÎS_1, QÎS₂ , 1.3

где функция выигрыша первого игрока в смешанных стратегиях имеет смысл математического ожидания

w(p,q)= 1.4

Чистые стратегии являются подмножествами множеств смешанных стратегий, т.е. вершинами симплексов и . Выбору i - той чистой стратегии первого игрока соответствует вектор Р с компонентами р_i = 1,р_k = 0 при k¹0 вектору j- той чистой стратегии второго игрока соответствует вектор Q с компонентами q_j = 1,q_l = 0 при l¹0.

Нижней ценой матричной игры в смешанных стратегиях называется величина

1.5

Верхней ценой матричной игры в смешанных стратегиях будет величина

1.6

Для модели игры в смешанных стратегиях (1.27) справедлива основная теорема матричных игр фон Неймана.

Любая матричная игра имеет цену в смешанных стратегиях, а игроки имеют оптимальные смешанные стратегии Р₀ и Q₀, т.е.

1.7

Доказательство теоремы следует из того, что выпуклая функция имеет седловую точку на компонентах S₁ и S₂. Очевидно, что функция W(P,Q) линейна по Р и Q и, следовательно, выпукло - вогнута.

Решить матричную игру - это означает найти все оптимальные стратегии и цену игры.

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

2.1

Из (2.1) и определения функции выигрыша W(P₁,Q) (1.28) сразу следует два данных свойства матричной игры:

а) если к элементам платежной матрицы А прибавить одно и тоже число d (обозначим новую матрицу А'), то игры

Г={S₁,S₂,A} 2.2

и

Г={S₁,S₂, } 2.3

будут иметь одни и те же оптимальные стратегии, но цена игры Г' изменится на d;

б) если все элементы платежной матрицы умножить на одно и тоже

число g >0, то игры {S₁,S₂,A} и {s₁,s₂,a'} имеют одни и те же оптимальные стратегии, но цена игры изменится в g раз.

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

Для формулировки других свойств оптимальных стратегий введем некоторые обозначения: если игроки используют чистые стратегии (i-ю первый игрок, j -ю второй) то значение функции выигрыша будем записывать так W(i,Q), W(P,j), W(i,j)

Непосредственно из (2.1) вытекает, что

W(i,Q₀)£C£W(P₀,j) 2.4

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

1) Проверить, нет ли седловой точки. Если она есть, то сразу определяется цена и частные, и, возможно, общее решение.

2) Понизить насколько возможно порядок игры.

3) Если получилась игра (2х2), (nx2), (2xm), то решить игру графически.

4) Решить игру, используя свойства оптимальных стратегий, теорему Шепли-Сноу или сведя ее к задаче линейного программирования.

5) Для нахождения частного приближенного решения можно использовать метод Брауна.