Дилемма заключенного и доминантные стратегии. Теория игр - [27]
Число, соответствующее седловой точке (в нашем случае 3 евро), называется ценой игры. Оно достигается всякий раз, когда каждый игрок действует в соответствии со своей оптимальной стратегией. Если один из игроков сделает иной ход (использует иную стратегию), то противник сможет повысить цену игры, выиграв больше или потеряв меньше в зависимости от того, о каком из игроков идет речь. Также говорят, что для этой игры существует чистая стратегия.
Теперь представим себе другую игру с теми же правилами, но с другой платежной матрицей: если оба игрока записывают одинаковое число, А выигрывает 1 евро, если же числа отличаются, Б выигрывает 1 евро.
Теперь максиминным значением является -1 (оба минимальных значения равны -1), минимаксным значением для Б является 1 (оба максимума равны 1). Эта игра не имеет седловой точки, следовательно, не существует одной чистой стратегии. Если А будет использовать некую стратегию (например, всегда будет записывать 1), о которой будет известно Б, он всегда будет записывать 2 и всегда будет выигрывать 1 евро. Так как эта игра очень простая и симметричная, оптимальной стратегией будет любая, при которой игрок будет чередовать двойки и единицы так, чтобы соперник не смог определить его стратегию. Для этого оптимальной стратегией будет записывать числа наудачу. Например, можно бросать монету и записывать 1, если выпадает решка, и 2, если выпадает орел. В этом случае нельзя говорить о чистых стратегиях, так как стратегию нельзя определить заранее из-за вмешательства случайных событий. Когда оптимальная стратегия содержит элемент неопределенности и должна держаться в секрете, такую стратегию называют смешанной.
Два приведенных нами примера соответствуют двум простым случаям, которые можно назвать крайними: в первом случае для игры определена чистая стратегия, так как оптимальные стратегии для каждого из игроков приводят к одному и тому же результату. Этот результат называется ценой игры. Во втором случае, напротив, любая заранее определенная стратегия не обязательно приведет к лучшему результату, и единственным способом обеспечить максимальный выигрыш является использование случайной стратегии, которая называется смешанной.
Рассмотрим третью игру. Она похожа на две предыдущие, но определить оптимальные стратегии для каждого игрока будет сложнее. Как и в прошлых примерах, каждый игрок может записать одно из двух чисел: А может записать 1 или 8, Б может записать 2 или 7. Если четность обоих чисел совпадает (они оба четные или оба нечетные), А выигрывает сумму, равную записанному им числу. Если же одно из чисел четное, а другое — нет, победа остается за игроком Б, который выигрывает сумму, равную записанному им числу. Платежная матрица этой игры выглядит так:
Заметим, что элементы матрицы обозначают выигрыши игрока А. Поэтому в случае победы игрока Б элемент матрицы является отрицательным и отражает проигрыш игрока А. Может показаться, что игра равновесная (А может выиграть 1 или 8 евро, Б — 2 или 7 евро), но седловой точки не существует: максиминное значение равно -2 (-2 > -7), минимаксное равно 1 (1 < 8). На самом деле если в платежной матрице 2x2 числа вдоль одной диагонали больше, чем вдоль другой, седловой точки не существует, поэтому для такой игры нет оптимального решения. Однако имеется важное отличие этой игры от предыдущей. В предыдущей игре наилучшим вариантом было использование случайных стратегий обоими игроками, в этом случае выигрыши уравнивались. Здесь же игрок Б имеет шансы на победу. Оптимальная стратегия для каждого игрока по-прежнему предусматривает случайные действия, но не является полностью случайной, так как каждый должен принимать решения, соблюдая определенные соотношения. Решением игры в этом случае является использование смешанных стратегий обоими игроками. О том, как определить результаты этой игры, то есть об оптимальной стратегии для каждого игрока и о средней цене игры, мы поговорим несколько позже.
Читатель уже заметил, что мы представили различные игры в виде матриц, в которых содержатся различные стратегии для первого игрока (строки матрицы) и второго игрока (столбцы). Подобным представлением, которое известно как нормальная форма игры, обычно описывают игры для двух игроков, совершающих ходы одновременно. Такие случаи составляют большинство из рассматриваемых в теории игр. Также существует и другое представление, называемое экстенсивной формой, когда все возможные ходы представлены в виде дерева. Оно больше подходит для игр, в которых соперники совершают ходы по очереди. К подобным играм относится большинство описанных в главе 2.
В начале XX века начала складываться теоретическая основа современной теории игр, окончательно оформившейся в середине столетия. Авторство первой теоремы принадлежит логику Эрнсту Цермело (1871-1956). Он сформулировал и доказал ее в 1912 году. Эта теорема подтверждает, что любая конечная игра с полной информацией (например, шашки или шахматы) имеет оптимальное решение в чистых стратегиях, то есть в отсутствие элемента неопределенности. Эта теорема не описывает, как можно найти подобные стратегии.
