Начала теории игр

В качестве введения в теорию игр мы расскажем о трех играх разного уровня сложности и на их примере объясним отдельные ключевые понятия, которые будут использоваться в этой и следующей главах. В этой теории применяется игровая терминология и речь идет об играх, игроках, партиях, стратегии, равновесной игре и так далее. Несмотря на это, читателю нужно понимать, что представленные задачи не обязательно соответствуют какой-либо реальной игре в том смысле, как в предыдущих главах. Нагляднее будет представлять ситуацию (противостояние) между двумя людьми или группами с установленными правилами, определяющими возможные действия. Оба игрока принимают решения одновременно (а не по очереди, как в играх, описанных в главе 2), никто из них не знает о решениях соперника. В результате принятых решений выигрывает тот или другой игрок. Далее мы будем называть подобные ситуации играми, участников будем именовать игроками. Под стратегией будем понимать решение, принятое игроком, а под выигрышем или проигрышем — последствия принятых игроками решений.

РОДОНАЧАЛЬНИКИ ТЕОРИИ ИГР

Уже в XVII веке такие ученые, как Христиан Гюйгенс (1629-1695) и Готфрид Вильгельм Лейбниц (1646-1716), предложили создать дисциплину, в которой бы использовались научные методы для изучения человеческих конфликтов и взаимодействий. Однако получить какие-либо значимые результаты по этой теме им не удалось. На протяжении всего XVIII века не было написано практически ни одной работы по анализу игр, которая бы имела подобную цель. Заслуживает упоминания письмо Джеймса Уолдгрейва от 1713 года, в котором приводится решение карточной игры для двух игроков под названием Le Her. Автор использовал способ, похожий на смешанную стратегию, и привел минимаксное решение. Несмотря на это, не было разработано ни теоретической базы, ни обобщений, чтобы подобный метод можно было применить в других случаях. В XIX веке многие экономисты создавали простые математические модели для анализа простейших конкурентных ситуаций. Среди них выделяется работа Антуана Огюста Курно «Исследование математических принципов теории богатства» (1838), в которой рассматривается случай дуополии и приводится решение, которое можно считать частным случаем равновесия Нэша. Тем не менее, теория игр как фундаментальная математическая теория появилась лишь в первой половине XX века.

Портрет Гэтфрида Вильгельма Лейбница, немецкого философа, который также занимался математикой.

Начнем рассказ об основах теории игр со следующего случая. Он очень прост и не представляет никакого интереса в качестве игры. Два игрока А и Б одновременно записывают число (1 или 2). Игрок Б должен заплатить игроку А сумму в евро, равную результату сложения двух записанных чисел. Очевидно, игра неравновесная (А всегда выигрывает), но тем не менее мы можем задаться вопросом: как должен действовать каждый игрок в соответствии со своими интересами? Для этого рассмотрим матрицу игры, так называемую платежную матрицу, в которой приведены возможные результаты:

Элементы матрицы обозначают сумму в евро, которую должен заплатить игрок Б игроку А при выборе соответствующей стратегии. Каждый игрок имеет два варианта действий, поэтому всего в матрице четыре элемента. Игра очень простая, и очевидно, что, действуя согласно своим интересам, А напишет 2, Б напишет 1, выигрыш игрока А составит 3 евро.

Проанализируем ходы игроков более подробно, чтобы увидеть, каковы варианты действий для каждого игрока. А не знает, какое число записал Б, но предполагает, что Б хочет платить как можно меньше. Поэтому если А напишет 1, то выиграет минимум 2 евро, если напишет 2 — выиграет минимум 3 евро. Говорят, что 3 (число в нижней левой ячейке матрицы) — это максиминное значение (максимальное среди минимальных). Аналогично Б предполагает, что А хочет получить наибольший выигрыш. Поэтому если Б запишет 1, то потеряет максимум 3 евро, если запишет 2 — потеряет максимум 4 евро. Говорят, что в этом случае 3 является минимаксным значением (минимальным среди максимальных). Если минимаксное и максиминное значения в игре находятся в одной и той же ячейке матрицы, как в нашем случае, то говорят, что игра имеет седловую точку. (Представьте себе седло, изображенное в форме двух пересекающихся кривых, в точке пересечения которой минимальное значение одной совпадает с максимальным значением другой. Эта точка пересечения и называется седловой.)

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

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

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