Формальное представление игр

В течение одной партии (однократном осуществлении игры) каждый игрок Pi может придерживаться одной из возможных линий своего поведения si (стратегий), выбирая si из некоторого заданного множества Si. В результате таких выборов складывается некоторый набор стратегий всех игроков называемый ситуацией.

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

Таким образом, формальное определение игры сводится к заданию трех классов множеств:

а) множества игроков;

б) совокупности множеств стратегий каждого из игроков

в) совокупности функций выигрыша каждого из игроков

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

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

Матричная игра описывается следующим образом.

- В игре участвуют 2 игрока: допустим, игроки А и В.

- Каждый из игроков располагает конечным набором стратегий: А1,…, Аm и В1,…, Вn - возможные стратегии игроков А и В (в этом случае говорят, что игра имеет размерность mхn).

Такая игра называется игрой mxn. Исход каждой партии завершается выигрышем одного из игроков.

Обозначим aij - выигрыш игрока А, если он использует стратегию Аi, а игрок В стратегию Вj. Тогда выигрыш игрока В очевидно равен bij=- aij, так как игра с нулевой суммой. Поэтому в дальнейшем будем рассматривать лишь выигрыш одного из игроков. Если игра содержит кроме личных и случайные ходы, то выигрыш aij есть величина случайная, зависящая от исходов всех случайных ходов. В этом случае оценкой ожидаемого выигрыша является математическое ожидание случайного выигрыша. В дальнейшем будем обозначать aij как сам выигрыш (в игре без случайных ходов), так и его математическое ожидание (в игре со случайными ходами).

Очевидно, задание такой игры эквивалентно заданию всех значений функции выигрыша одного из игроков (например, игрока А) в виде так называемой платежной матрицы или матрицы игры:

Таким образом, матричная парная игра с нулевой суммой, задаваемая матрицей -||aij||_mxn, элементы которой определяют выигрыш первого игрока (и соответственно проигрыш второго), если первый игрок выберет i-ю строку (i-ю стратегию), а второй игрок – j-й столбец (j-ю стратегию). Матрица ||aij||_mxn называется платежной матрицей или матрицей игры.

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