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

Джон фон Нейман, известный по работам во множестве областей, является одним из наиболее выдающихся математиков XX века. Он начал научную деятельность в родном Будапеште, где изучал математику. Затем он переехал в Берлин, чтобы заниматься физикой, а позже в Цюрих, где изучал химию. С 1930 года он жил и работал в США. В Гёттингене под руководством Гильберта фон Нейман занимался теоретическими вопросами чистой математики, а также совместно с Гейзенбергом работал над началами квантовой теории. Он внес существенный вклад во многие сферы науки, в частности в теорию множеств, функциональный анализ, логику, теорию вероятностей, прикладную математику в экономике, квантовую физику и метеорологию.

Его интересы выходили за рамки чистой и прикладной математики и охватывали также столь различные области, как атомная физика, проектирование компьютеров, когнитивная психология и экономика. Одно из важнейших его достижений, относящееся к прикладной математике в экономике, — создание теории игр, которую он сформулировал в книге «Теория игр и экономическое поведение»», опубликованной совместно с экономистом Оскаром Моргенштерном в Принстоне в 1944 году. Этот труд считается фундаментальным в теории игр. Он ознаменовал создание теории игр, которая уже через несколько лет, начиная с 1950-х годов, стала находить применение в анализе множества реальных ситуаций.

Джон фон Нейман (справа) и Роберт Оппенгеймер, руководитель программы по созданию первой атомной бомбы, на этой фотографии 1952 года изображены рядом с самым быстрым и точным компьютером того времени.

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

Представим следующую игру для двух игроков: игрок А выбирает строку (F1, F2, F3), его соперник — столбец (Cl, С2, СЗ) из следующей платежной матрицы, при этом ни один из игроков не знает о выборе оппонента. Выбор игроков определит элемент матрицы (он находится на пересечении выбранных строки и столбца), который укажет, сколько евро должен заплатить второй игрок первому. Как должен действовать каждый игрок, чтобы увеличить свой выигрыш или уменьшить проигрыш?

Игрок А анализирует минимальные выигрыши в зависимости от совершенных ходов. Если он выберет F1, минимальный выигрыш равен -2, 2 для строки F2 и - 1 для строки F3. Наибольший из минимальных выигрышей (максиминное значение) равен 2. Если игра является определенной, нужно выбирать строку F2. Аналогично игрок Б анализирует наибольшие проигрыши в зависимости от совершенных ходов. Если он выберет С1, максимальный проигрыш равен 6, 7 — для столбца С2 и 2 — для столбца СЗ. Наименьший из максимальных проигрышей (минимаксное значение) равен 2. Если игра является определенной, нужно выбирать столбец СЗ.

Так как в этой игре максиминное и минимаксное значения совпадают и равны 2 евро, говорят, что игра является определенной, имеет цену 2 и имеет решение в чистых стратегиях: игрок А выберет F2, игрок Б — СЗ. Также говорят, что 2 является седловой точкой, или точкой равновесия (максимальное из минимальных значений совпадает с минимальным из максимальных).

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

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

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

Представим следующую ситуацию: в некой стране во время предвыборных дебатов внимание общественности привлекла постройка объездной магистрали вокруг столицы. Имеются два варианта: трасса может пройти севернее (С) или южнее (Ю) города. Две основные партии страны, А и Б, должны определить предвыборную программу и решить, за какой из вариантов они выступают. Также они могут избежать обсуждения и никак не касаться этого вопроса в предвыборной программе. Руководство обеих партий знает, что их сторонники поддержат любое решение, но остальное население будет склоняться к тому или иному варианту, и если обе партии сделают одинаковый выбор, избиратели воздержатся от голосования. По итогам предвыборных опросов, которые известны обеим партиям, были получены следующие результаты:

Так, если партия А предложит проложить магистраль севернее, а партия Б — южнее, партия А получит 45% голосов. Если же обе партии не будут затрагивать эту тему, партия А получит 35% голосов. Какие решения примут обе партии при заданных условиях?

Если руководствоваться приведенной матрицей, то выбор прост: партия А показывает наилучшие результаты, если будет поддерживать постройку трассы на юге. Именно этого варианта она и будет придерживаться. Аналогично партия Б заметит, что результаты партии А будут наихудшими (что устраивает партию Б), если Б будет избегать этой темы. Такой будет стратегия партии Б. Следовательно, игра имеет седловую точку (партия А голосует за постройку трассы на юге, Б избегает темы), цена игры — 45% голосов в пользу партии А.

Теперь предположим, что матрица имеет следующий вид: