Математическая модель игры.

В математических обозначениях «максимин для А» выражается mах_imin_j a_ij, аналогично, «минимакс для В» есть min_jmах_i a_ij, причем, очевидно, имеет место mах_i min_j a_ij £ min_jmах_ia_ij. В случае, когда имеет место равенство, т.е. mах_i min_j a_ij = min_jmах_i a_ij =а_i0j0, соответствующие чистые стратегии (i₀ для игрока А и j₀ для В) будут оптимальными, а про игру говорят, что она имеет седловую точку. Тогда а_i0j0 является значением игры. Легко видеть, что игра имеет седловую точку тогда и только тогда, когда в платежной матрице имеется элемент а_i0j0, наименьший для всех элементов своей строки i₀ и наибольший для всех элементов своего столбца j₀.

При отсутствии седловой точки невозможно получить оптимальное решение, пользуясь чистыми стратегиями. В этом случае для получения решения игры будем пользоваться смешанными стратегиями, которые заключаются в применении чистых стратегий с некоторыми частотами (вероятностями). Пусть р₁, р₂,.., р_n и q₁,q₂,..,q_m – наборы вероятностей, с которыми игроки А и В соответственно выбирают свои чистые стратегии. Естественно

=1, р_i , q_j ≥0 для всех i и j.

Если игрок А выбирает свои чистые стратегии с вероятностями р_i, то его ожидаемый выигрыш должен составить

a₁₁р₁+ a₂₁р₂+…+ a_n1р_n ,

при ответном выборе игроком В своей первой чистой стратегии,

a₁₂р₁+ a₂₂р₂+…+ a_n2р_n ,

при ответном выборе игроком В своей второй чистой стратегии, и т.д.

a_1mр₁+ a_2mр₂+…+ a_nmр_n

при выборе игроком В m-й чистой стратегии. С другой стороны, если игрок В выбирает свои чистые стратегии с вероятностями q_j, то его ожидаемый проигрыш должен составить

a₁₁q₁+ a₁₂q₂+…+ a_1mq_m ,

если игрок A выберет свою первую чистую стратегию, и т.д.

a_n1q₁+ a_n2q₂+…+ a_nmq_m,

при выборе игроком A n-й чистой стратегии.

Если игрок А выбрал стратегию (р₁,р₂,..,р_n) и при этом игрок В выбрал (q₁,q₂,..,q_m), то ожидаемый выигрыш игрока А (он же проигрыш игрока В) составит

g= .

Тогда игрок А при выборе р_i стремится максимизировать свой наименьший ожидаемый выигрыш по столбцам, тогда как игрок В выбирает q_j с целью минимизировать наибольший ожидаемый проигрыш по строкам. Справедлива теорема фон.Неймана, которую мы примем без доказательств, утверждающая, что для любой конечной игры существуют оптимальные стратегии игроков А (р₁*,р₂*,..,р_n*) и В (q₁*,q₂*,..,q_m*), при этом максимум наименьшего ожидаемого выигрыша игрока А совпадает с минимумом наибольшего ожидаемого проигрыша игрока В (обозначим это значение игры через g). Таким образом, математическую модель конечной игры для игрока А можно представить в следующем виде:

Найти такие р_i ≥0, для которых выполняются соотношения

р₁+р₂+…+р_n=1,

a₁₁р₁+ a₂₁р₂+…+ a_n1р_n ≥ g,

a₁₂р₁+a₂₂р₂+…+a_n2р_n≥g, (1)

……………………. ……

a_1mр₁+ a_2mр₂+…+ a_nmр_n≥ g,

и функция Z=g принимает максимальное значение.

Упростим полученную задачу, разделив все ограничения (1) на значение игры g > 0 и положив х_i =р_i/g для всех i. (Проведение аналогичных рассуждений для случая g ≤ 0 предоставляется читателю). В силу того, что

max g =min 1/g = min(р₁/g+р₂/g+…+р_n/g) = min(x₁+x₂+…+x_n)

задача принимает вид

минимизировать Z= x₁+x₂+…+x_n

при ограничениях

a₁₁x₁+a₂₁x₂+…+a_n1x_n ≥ 1,

a₁₂x₁+a₂₂x₂+…+a_n2x_n ≥ 1, (2)

……………………. ……

a_1mx₁+a_2mx₂+…+ a_nmx_n≥ 1,

x₁, x₂,…,x_n ≥ 0.

Мы получили задачу линейного программирования (Приложение).

Обратите внимание: строка ограничения формируется из столбца платежной матрицы!

Решая ее (например, симплекс–методом), находим оптимальное решение x₁*, x₂*,…,x_n*, откуда, разделив на Z*=x₁*+x₂*+…+x_n*, получаем оптимальную стратегию для игрока А (р₁*,р₂*,..,р_n*), которая заключается в применении i-й чистой стратегии с частотой р_i*= х_i*/ Z*.

Двойственная ЗЛП – максимизировать F=y₁+y₂+…+y_m→max;

при ограничениях

a₁₁y₁+ a₁₂y₂+ …+ a_1my_m ≤1;

a₂₁y₁+ a₂₂y₂+ …+ a_2my_m ≤1; (3)

…………………………..

a_n1y₁+ a_n2y₂+ …+ a_nmy_m ≤1;

y₁≥0; y₂≥0; … y_m ≥0.

Здесь строка ограничения формируется из строки платежной матрицы.

Решая данную ЗЛП, находим оптимальное решение у₁*, у₂*,…,у_m*, откуда, разделив на F*=y₁*+y₂*+…+y_m*, получаем оптимальную стратегию для игрока B (q₁*, q₂*,.., q_m*), которая заключается в применении j-й чистой стратегии с частотой q_j* = y_j*/ F*.

Затем находим цену игры g =1/Z*=1/F*.

Правила упрощения платежной матрицы:

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

Если каждый элемент платежной матрицы умножить на одно и то же число (не 0), то решение (р₁*,р₂*,..,р_m*) не изменится, а цена игры изменится ровно во столько же раз.

Если какая-либо строка платежной матрицы доминирует над другой строкой (или линейной комбинацией строк), то доминируемые строки не войдут в оптимальную смешанную стратегию и их можно удалить.

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

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

Пример 1. Рассмотрим тотализатор на ипподроме. Пусть выплаты в случае победы одной из трех лошадей относятся к ставке как 1:1, 3:1 и 4:1. Тогда платежная матрица игрока на скачках примет вид:

1 –1 –1 Если прибавить к каждому элементу матрицы число К, то

А=–1 3 –1 оптимальные стратегии не изменятся, а значение игры

–1 –1 4 увеличится на К. Для упрощения матрицы добавим

К=1, тогда получим:

2 0 0 В соответствие с (2) задача принимает вид:

А= 0 4 0 минимизировать Z= x₁+x₂+x₃

0 0 5 при ограничениях

2x₁+ 0x₂+0x₃ ≥ 1,

0x₁+ 4x₂+0x₃ ≥ 1,

0x₁+ 0x₂+5x₃≥ 1,

x₁, x₂,x₃ ≥ 0.

Легко заметить, что решение этой задачи:

x₁*=1/2, x₂*=1/4, x₃* =1/5.

Значение упрощенной игры 1/Z*=1/(x₁*+x₂*+x₃*)=20/19, откуда (при К=1) значение исходной игры равно 20/19 – 1 = 1/19,

р₁*=х₁*/Z*=10/19, р₂*=х₂*/Z*=5/19, р₃*=х₃*/Z*=4/19.

Таким образом, оптимальная стратегия игрока на скачках в данном примере заключается в смешанной стратегии делать ставки на всех трех лошадей в пропорции 10:5:4, при этом выигрыш игрока (игра имеет положительное значение!) будет равным 1/19 суммы его ставок, независимо от результата гонок. (Если цена игры отрицательна, то не следует в нее играть, так как даже при оптимальной стратегии гарантирован проигрыш, правда, минимальный).

Пример 2. Предлагается три варианта инвестиций в сельское хозяйство и прогноз получения доходов за год (дивиденды и повышение стоимости капитала) при различных перспективах на урожай.

Варианты инвестиций	Перспективы на урожай
хорошие	средние	плохие
1. АО «Сельхозтехника»
2. АО «Агроимпорт»
3. АО «Агроэкспорт»			–50

Доходы в платежной матрице приведены в процентах от вложенного капитала. Как распорядиться капиталом, чтобы получить наибольший доход? Искомые переменные р₁, р₂, р₃ определяют пропорции вложений. Заметим, что элементы первой строки платежной матрицы меньше средних арифметических соответствующих элементов второй и третьей строк, и она может быть удалена (первый вариант инвестиций заведомо неэффективен по сравнению с комбинацией второго и третьего вариантов – вкладывать деньги поровну во второй и третий проект). Получаем задачу линейного программирования

минимизировать Z= x₂+x₃

при ограничениях

0x₂ + 150x₃ ≥ 1,

100x₂+50x₃ ≥ 1,

250x₂ – 50x₃≥ 1,

x₁=0, x₂, x₃ ≥ 0.

Решая данную задачу стандартными средствами (см. Приложение 1) получим следующее решение

x₁*=0, x₂*=1/150, x₃* =1/150.

Значение игры 1/Z*=1/( x₁*+x₂*+x₃*)=150/2=75, откуда

р₁*=0, р₂*=х₂*/Z*=75/150=1/2, р₃*=х₃*/Z*=75/150=1/2.

Таким образом, оптимальной стратегией является вложение капитала равными долями во второй и третий варианты, при этом гарантированный доход составит 75%.