ГЛАВА IV. МЕТОД ПРИБЛИЖЕННОГО ОПРЕДЕЛЕНИЯ ЦЕНЫ ИГРЫ

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

Описываемый нами приближенный метод основан на следующих интуитивных соображениях. Допустим, что два человека играют ряд; партий данной игры, причем пи один из них не знает оптимальной стратегии (возможно, потому, что они не знают теории игры или потому, что матрица игры слишком велика, чтобы они смогли произвести необходимые вычисления), тогда может случиться, что каждый из них решает вести себя так, как если бы он имел дело с неодушевленным предметом, а не с разумным противником, то есть играть таким образом, чтобы максимально увеличить свой выигрыш, предполагая, что «будущее будет походить на прошлое». Если известно, что сделал каждый из игроков в первой партии, то этот принцип максимизации приведет к определенной последовательности партий игры. Для каждой партии этой последовательности можно вычислить верхнюю и нижнюю границы цены игры, а также приближенную охгкшальную стратегию для каждого игрока.

Не пытаясь давать подробное и точное описание этого способа в общем случае, мы объясним его лишь для некоторой игры с матрицей порядка 3x3.

Пусть дана игра с матрицей

Обозначим возможные стратегии для через А, В и С, считая, что выбор стратегии А означает выбор первой строки; выбор стратегии В — выбор второй и т. д. Аналогично стратегии игрока (три столбца) обозначим через , и . Предположим, что в первой партии выбирает , а выбирает . Во второй партии знает, что в первой партии выбрал А, и, поскольку он предполагает, что будет поступать так же и в будущем, он имеет дело со следующей ситуацией:

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

Поскольку наибольшее из этих чисел во второй партии выбирает В. Таким образом, после второй партии окажется, что выбрал один раз А и один раз В. Составим теперь таблицу (таблица 1), которая показывает, что было бы лучше выбрать в обеих партиях: поэтому он решает в третьей партии выбрать .

Аналогично, для мы получаем таблицу 2, которая показывает, что опять решает выбрать В.

Таблица 1

Таблица 2

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

Таблица 3

Продолжая эту таблицу, мы получаем таблицу 4.

Таблица 4. Первые восемь партий игры

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

Таблица 5. Партии от девятой до двадцатой

При этом новом условии мы можем продолжить таблицу 4 и получим таблицу 5.

Пусть — максимальное из чисел в строке таблицы, соответствующей выигрышу Из таблиц 4 и 5 мы имеем:

Пусть — максимальное число в i-й строке таблицы, соответствующей выигрышу , но с отрицательным знаком. Таким образом, из таблиц 4 и 5 мы имеем:

Для любой игры Г можно показать, что числа и , найденные таким способом, удовлетворяют неравенству

для всех i; здесь v — цена игры. Так, например, для нашей игры мы имеем:

Наиболее благоприятные из найденных таким образом неравенств:

и

Итак, мы получаем довольно хорошую апроксимацию для цены игры (которая на самом деле равна 1,85).

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

Приняв во внимание число выборов каждой чистой стратегии в i ступенях вышеописанного способа приближений, мы можем также найти апроксимацию для оптимальной стратегии. Так, мы видим, что в первых восьми строках таблиц 4 и 5 выбирает стратегию А один раз, стратегию В три раза, стратегию С четыре раза; следовательно, апроксимация оптимальной стратегии для будет . Пусть для каждого

есть найденная таким образом стратегия игрока ; аналогично, пусть

есть найденная аналогичным образом стратегия игрока . Итак,

(Можно проверить, что точные оптимальные стратегии будут

Можно показать, что если у имеется единственная оптимальная стратегия X, то последовательность

сходится к X; аналогично, если у имеется единственная оптимальная стратегия, то соответствующая последовательность сходится к ней. Если же имеет больше чем одну оптимальную стратегию, то может случится, что последовательность (1) не сходится. Можно, однако, показать, что в любом случае всякая сходящаяся подпоследовательность последовательности (1) сходится к оптимальной стратегии для .

Библиографические замечания

Описанный в этой главе способ отыскания приближенных решений прямоугольных игр был сформулирован в работе Брауна [17]. Сходимость процесса была доказана в работе Робинсона [96].