Xl > О, /= 1,
где V является значением игры.
Для второго игрока задача записывается в виде
min max X а..у.,
1</т=1 IJ J п
У]> 0,7=Е>у = 1.
Запишем промежуточное соотношение
пппп
Тогда задача принимает вид
minv(5.10)
X a..yj<v, / = l,2,...,/w,
> 0, y= 1,
где V является значением игры.
Отметим, что задача для второго игрока (5.10) является двойственной к задаче для первого игрока (5.9). Задача для второго игрока может быть решена, например, стандартным симплекс-методом, а для первого игрока - двойственным симплекс-методом. Выбор метода определяется тем, какая из задач имеет меньше ограничений, что в свою очередь зависит от числа чистых стратегий каждого из игроков.
5.2.9. Определение бесконечной антагонистической игры. Естественным обобщением матричных игр являются бесконечные антагонистические игры (БАИ), в которых хотя бы один из игроков имеет
бесконечное количество возможных стратегий. Мы будем рассматривать игры двух игроков, делающих по одному ходу, и после этого происходит распределение выигрышей. При формализации реальной ситуации с бесконечным числом выборов можно каждую стратегию сопоставить определенному числу из единичного интервала, так как всегда можно простым преобразованием любой интервал перевести в единичный и наоборот.
Напоминание. Пусть Е- некоторое множество вещественных
Естественным обобщением матричных игр являются бесконечные антагонистические игры, в которых
стратегий
Всякая антагонистическая бесконечная игра двух игроков с непрерывной функцией выигрышей М (х,у) на единичном квадрате имеет решение (игроки имеют оптимальные смешанные стратегии).
чисел. Если существует число у та-хотя бы 0ДШ1 из игроков имеет бес- ое, что х < при всех хеЕ (при конечное количество возможных
этом у не обязательно принадлежит
£), то множество Е называется ограниченным сверху, а число у называется верхней границей множества Е. Аналогично определяется ограниченность снизу и нижняя граница множества Е. Обозначаются верхняя и нижняя границы соответственно через sup £ и inf £ соответственно.
Пример. Пусть множество Е состоит из всех чисел вида ~, « = 1,2,...
Тогда множество Е ограниченно, его верхняя грань равна 1, а нижняя О, причем О £, а 1 е Е.
Для дальнейшего изложения теории игр этого класса введем определения и обозначения: [0; 1] - единичный промежуток, из которого игрок может сделать выбор; х - число (стратегия), выбираемое игроком \\у - число (стратегия), выбираемое игроком 2; M(x, у) - выигрыш /-го игрока; G {XJMxMi)- игра двух игроков с ненулевой суммой, в которой игрок 1 выбирает число х из множества X, игрок 2 выбирает число у из множества 7, и после этого игроки 1 и 2 получают соответственно выигрыши Мх{х, у) и М2(х, у). Пусть G (X, Y,Kf) - игра двух игроков с нулевой суммой, в которой игрок 1 выбирает число х, игрок 2 - число у, после чего игрок 1 получает выигрыш М(х, у) за счет второго игрока.
Большое значение в теории БАИ имеет вид функции выигрышей М{х, у). Так, в отличие от матричных игр не для всякой функции Л/(х, у) существует решение. Будем считать, что выбоо огределенного числа иг-
роком означает применение его чистой стратегии, соответствующей этому числу. По аналогии с матричными играми назовем чистой нижней ценой игры величину
= max inf М{х, у) или = max min М{х, у\
X уX у
а чистой верхней ценой игры величину
Fj = min sup М(х, у) или = min max М(х, у).
Ухух
Для матричных игр величины Vi и V2 всегда существуют, а в бесконечных играх они могут не существовать.
Естественно считать, что если для какой-либо бесконечной игры величины Fl и Vi существуют и равны между собой (Fi = F2 = F), то такая игра имеет решение в чистых стратегиях, т.е. оптимальной стратегией игрока 1 есть выбор числаХо е Хи игрока 2 - числа>о е У, при которых Мо, У о) = F, в этом случае V называется ценой игры, а (х, у о) - седловой точкой в чистых стратегиях.
Пример. Игрок 1 выбирает число х из множества Х= [0; 1], игрок 2 выбирает число> из множества 7= [0; 1]. После этого игрок 2 платит игроку 1 сумму
М{х,у) = 2х-у\
Решение. Поскольку игрок 2 хочет минимизировать выигрыш игрока 1, то он определяет
min(2x-/) = 2x-1,
Т.е. при этому = 1. Игрок 1 желает максимизировать свой выигрыш и поэтому определяет
max(minM(x,>)) = max(2x -1) = 2 -1 = 1,
jcG X YjcG X
который достигается при х = 1.
Итак, нижняя цена игры равна Fi = 1. Верхняя цена игры
V, = min(min(2x -/)) = min(2- д;) = 2-1 = 1,
ДбУ XGxySY
Т.е. в этой игре Fi = F2= 1. Поэтому цена игры F= 1, а седловая точка
(1;1).