- •2. Элементы теории игр
- •2.1. Введение
- •2.2. Стратегии. Нормальная форма игры
- •2.3. Ситуации равновесия
- •2.4. Антагонистические игры. Игры с нулевой суммой
- •2.5. Нормальная форма
- •2.6. Смешанные стратегии
- •2.7. Теорема о минимаксе
- •2.8. Вычисление оптимальных стратегий
- •2.9. Игры с ограничениями
- •2.10. Бесконечные игры
- •2.11. Игры на квадрате
- •2.12. Игры с непрерывным ядром
- •2.13. Вогнуто-выпуклые игры
- •2.14. Игры с выбором момента времени
2.2. Стратегии. Нормальная форма игры
В интуитивном понимании стратегия есть некоторый план разверты-
вания игры. Можно считать, что игрок говорит себе: ―Если случится то-то
и то-то, то я буду действовать так-то и так-то‖.
Определение. Стратегия i-го игрока есть некоторая функция, которая ста-
вит в соответствие каждому информационному множеству Si j этого игро-
ка некоторый индекс из I i j .
Будем обозначать множество всех стратегий i-го игрока через
i .
Вообще говоря, игрок принимает решение о своем ходе в игре обыч-
но в тот момент, когда надо делать этот ход. Однако с чисто теоретической
точки зрения можно абстрагироваться от такого практического ограниче-
ния и предполагать, что уже до начала игры каждый игрок решил, что он
будет делать в каждом случае. Т.е. предполагаем, что каждый игрок вы-
брал некоторую стратегию уже до начала игры.
Поскольку это так, то остается лишь произвести случайные ходы.
Более того, все случайные ходы можно объединить в один ход, результат
которого вместе с выбранными стратегиями определяет исход игры.
Нас, как и игроков, интересует, какие из стратегий являются наи-
лучшими с точки зрения максимизации доли каждого игрока в выигрыше:
i-й игрок стремится максимизировать i-ю компоненту функции выигрыша.
Так как результаты случайных ходов известны только в вероятност-
ном смысле, то естественно рассматривать математическое ожидание
функции выигрыша, определенное в случае, когда игроки используют дан-
ный n-набор стратегий, т.е данную ситуацию. Поэтому для описания ма-
тематического ожидания функции выигрыша при условии, что i-й игрок
применяет стратегию xi
ние:
i , можно использовать следующее обозначе-
(x1, x2 ,..., xn )
( 1( x1,..., xn ),
2
( x1,..., xn ),...,
n
( x1,..., xn ))
Функцию ( x1, x2 ,..., xn ) на множестве всех возможных значений x1 ,
…, x n можно выразить либо в форме соотношения, либо в виде n-мерной
таблицы n-мерных векторов. В случае n=2 эта запись сводится к матрице,
25
элементами которой являются пары вещественных чисел. Такая n-мерная
таблица называется нормальной формой игры.
Пример 2.2. Для игры в ―Орлянку‖ нормальной формой игры является
матрица
―Р‖
―О‖
―Р‖
―О‖
Здесь каждая строка соответствует стратегии игрока 1, а столбец − страте-
гии игрока 2.
Пример 2.3. Рассмотрим следующую игру. Случайно выбирается целое
число z с возможными значениями 1, 2, 3, 4, каждое с вероятностью 1/ 4 .
Игрок I, не зная результата этого хода, выбирает целое число x. Игрок II,
не зная ни z, ни х, выбирает целое число у.
Выигрыш определяется следующим образом:
( y z x z , x z y z ) ,
т.е. целью является выбор числа, по наболее близкого к z.
В этой игре каждый игрок имеет 4 стратегии: 1, 2, 3, 4, так как от
других чисел мало проку. Если игрок I выбирает 1, а, игрок II − 3, то выиг-
рыш будет равен (2, -2) с вероятностью 1/ 4 , (0,0) - с вероятностью 1/ 4 и
( 2, 2) с вероятностью 1/ 2 . Ожидаемый выигрыш тогда равен:
1 1 1
(1,3) (2, 2) (0,0) ( 2,2)
4 4 4
Подсчитав все значения, получим таблицу:
(
1 1
, ) .
2 2
1
2
3
4
1
2
3
4
Определение. Игра называется конечной, если число стратегий всех игро-
ков является конечным. Или. Игра называется конечной, если ее дерево
содержит только конечное число вершин.
