Хорди Деулофеу - Дилемма заключенного и доминантные стратегии. Теория игр

Теперь максиминным значением является -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 году. Эта теорема подтверждает, что любая конечная игра с полной информацией (например, шашки или шахматы) имеет оптимальное решение в чистых стратегиях, то есть в отсутствие элемента неопределенности. Эта теорема не описывает, как можно найти подобные стратегии.

Примерно в 1920 году великий математик Эмиль Борель заинтересовался бурно развивающейся теорией и представил идею о смешанной стратегии (в которой фигурирует элемент случайности). Вскоре над этой темой начал работать Джон фон Нейман, и в 1928 году он сформулировал и доказал теорему о минимаксе. Очень скоро эта теорема стала ключевым элементом в дальнейшем развитии теории игр. Теорема фон Неймана гласит, что в конечной игре для двух игроков А и Б существует среднее значение, обозначающее возможный выигрыш игрока А и Б, если оба игрока действуют разумно, то есть пытаются увеличить выигрыш (или уменьшить проигрыш).

Французский математик Эмиль Борель, автор множества исследований по теории вероятностей.

Игры, которые мы проанализировали в прошлом разделе, являются простыми по нескольким причинам: в них участвуют два игрока, у каждого из них только два возможных хода (платежная матрица всегда имеет размеры 2X2). Кроме того, это игры с нулевой суммой, так как сумма выигрышей обоих игроков всегда равна нулю (проигрыш понимается как отрицательный выигрыш). В каждой партии нужно выбрать всего лишь один из двух возможных ходов. Каждый игрок может придерживаться оптимальной для себя стратегии в соответствии с правилами игры. В этом случае игра будет определена и результат будет равен цене игры (как в первом примере предыдущего раздела). Мы увидели, что этот результат является решением игры, если речь идет об игре с седловой точкой, то есть если один из элементов матрицы является одновременно максиминным (максимальным значением среди минимальных в каждой строке) и минимаксным (минимальным значением среди максимумов в каждом столбце). Если седловая точка отсутствует, мы не можем вести речь о чистых стратегиях, и следует применять смешанные стратегии, в которых используются случайные события и которые нужно сохранять в тайне от соперника. В случаях, когда платежная матрица симметрична, стратегией является полностью случайный выбор (как было показано в примере 2). В ином случае даже при использовании случайной стратегии выбор хода должен производиться в соответствии с определенным соотношением (что показано в примере 3).