г г (рефлексивность); из Т ~Г следует Г Г (симметрия) ; изТ Т иТ" V следует Г" Г (транзитивность). Доказательство. Для доказательства рефлексивности достаточно в (1,3) положить /: * 1 и flf = 0.

Для доказательства симметрии заметим, что из (1.3) следует

причем, очевидно, 1 : > 0.

Наконец, для доказательства транзитивности выразим Г" ~ Г в виде Н" = кН + л, где к>0. Вместе с (1.3) это дает нам

Н" = ккН + ка + а,

причем кк>0. Тем самым Г" ~ Г. □

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

1.4.Другой вид эквивалентности затрагивает игроков и их стратегии. Определение. Игры Г = (х, у,Я>и Г=(х у,Я> называются изоморфными, если существуют такие однозначные отображения tti : х х и

72 : У У что H(7liX, 7Г2У) = Н(Х, у) .

Пара отображений тт = (tti, 7Г2) называется при этом изоморфизмом Г на Г.

Игры Г и г называются зеркально изоморфными, если существуют такие однооднозначные отображения тг i: х у и 7Г2: У х что Я (7Г2, j, 7rix) = -H(x,y).

Пара отображений тг = (tti, 7Г2) называетсязе/??са/7Ь«ьш изоморфизмом Г на Г.

Если тг - изоморфизм или зеркальный изоморфизм Г на Г, то принято писать Г= 7гГ. □

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

1.5.Отношение изоморфности игр, подобно отношению аффинной эквивалентности, является отношением эквивалентности.

Теорема. Изоморфность игр обладает свойствами рефлексивности, симметрии и транзитивности.

Доказательство. Рефлексивность изоморфности вытекает из того, что в качестве изоморфизма тг = (tti, 7Г2) можно в этом случае взять пару тождественных отображений. Симметрия следует из того, что одно-однозначные отображения имеют однооднозначные обращения, а транзитивность - из того, что композиция однооднозначных отображений также является однооднозначной.

Определение. Изоморфизм антагонистической игры на себя называется автоморфизмом. □

1.6.Нетрудно проверить, что если одна игра зеркально изо морфина, другой, то вторая игра зеркально изоморфна первой. Точно так же, если две игры зеркально изоморфны третьей, то они изоморфны между собой. Оба

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

Определение. Антагонистическая игра, зеркально изоморфная самой себе, называется симметричной.

Зеркальный изоморфизм симметричной игры на себя называется зеркальным автоморфизмом (или симметрией). □

В симметричной игре игроки имеют равные возможности, и одинаковое их использование приводит к одинаковым результатам.

1.7.Следующее соотношение между играми отражает диалектическую связь целого и части: одна игра может являться как бы частью другой.

Определение. Игра Гиз (1.2) называется подыгрой игры Г из (1.1), если х С X, у С у, а функция Я: х X у -> R является сужением функции Я.

Поскольку подыгра Гигры Г вполне определяется подмножествами х и у множеств стратегий игроков в игре Г, ее можно называть х X у-подыгрой игры Г. хХ у-подыгру игры Г иногда называют у-подыгрой, а х X у-подыгру - х"-подыгрой. □

1.8.В данной главе мы будем иметь дело лишь с такими антагонистическими играми Г из (1.1), в которых множества стратегий игроков х и у конечны.

Определение. Антагонистические игры, в которых каждый игрок имеет конечное множество стратегий, называются матричными играми.

Это название объясняется следующей возможностью описания игр такого рода. Составим прямоугольную таблицу, в которой строки соответствуют стратегиям первого игрока, столбцы - стратегиям второго, а клетки таблицы, стоящие на пересечении строк и столбцов, соответствуют ситуациям игры. Если поставить в каждую клетку выигрыш первого игрока в соответствующей ситуации, то получим описание игры в виде некоторой матрицы. Эта матрица называется матрицей игры или матрицей выигрышей. □

Процесс "игры в матричную игру" удобно представить себе следующим образом: задается матрица Л; игрок 1 выбирает некоторую строку этой матрицы, а игрок 2 - некоторый ее столбец. Эти выборы осуществляются игроками независимо друг от друга. После того как выборы произведены, игрок ] получает от игрока 2 выигрыш, равный числу, стоящему на пересечении выбранных строки и столбца. Разумеется, если это число отрицательное, то речь идет о фактическом проигрыше игрока 1.

Матричная игра полностью определяется своей матрицей выигрышей. Поэтому игру с матрицей выигрышей А мы будем обычно обозначать через или Г (Л). Если Л является тХ «-матрицей (т.е. имеет m строк и п столбцов), то будем говорить, что есть т X дг-игра.

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

1.9.В определении антагонистической игры в п. 1.1 множества стратегий X и у не бьши наделены какой-либо структурой; в частности, на них не вводилось отношение порядка. Сама же запись матрицы предполагает

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

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

1.10. Как это обычно бывает, имеются свойства игр, не зависящие от мощности множества стратегий. Некоторые из этих свойств, описанию которых посвящены параграфы 2-6 данной главы, будут нами установлены для произвольных антагонистических игр.

§ 2. ОПТИМАЛЬНОСТЬ В АНТАГОНИСТИЧЕСКИХ ИГРАХ

2.1.Целью теории антагонистических игр, как и теории любого класса игр, является выработка для таких игр достаточно естественных представлений об оптимальности ситуаций и стратегий игроков и установление зависимости между свойствами игр, с одной стороны, и свойствами оптимальных в сформулированном смысле ситуаций - с другой. Наиболее слабой формой такой зависимости можно считать признаки существования оптимальных ситуаций, т.е. реализуемости соответствующих понятий оптимальности, а наиболее сильной - пути (алгорифмы) их нахождения и перечисления.

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

Если игрок 2 имеет в игре Г = (х, у, Я> только одну стратегию jo (т.е. У ={Уо}), то оптимальной стратегией игрока 1 будет та его стратегия, для которой функция Н( ,уо): х -> R достигает на х своего максимума.

Такое положение дел усложняется лишь незначительно, если игрок 2 имеет более одной стратегии (у > 1), но можно говорить о случайном выборе им своей стратегии, т.е. об известном игроку 1 априорном вероятностном распределении Y на у.

Будем для наглядности считать, что множество всех стратегий игрока 2 конечно: у = {jl, . .., J,?). В этом случае вероятностное распределение V состоит в приписьшании каждому некоторой вероятности F(>.), причем Y(yi) + . . . + ¥(Уп) = 1. Тогда за выигрыш игрока 1 при выборе им своей стратегии х естественно принять ожидаемый выигрыш - математическое ожидание выигрыша

2 Y(y)H(x,y)

- и выбирать стратегию х так, чтобы максимизировать этот ожидаемый выигрыш.

Заметим, что случайный выбор стратегии игроком также можно понимать как некоторую его стратегию. Систематическое рассмотрение таких стратегий занимает важное место в теории игр. К этом вопросу мы вернемся в § 8.