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

В начале XX века начала складываться теоретическая основа современной теории игр, окончательно оформившейся в середине столетия. Авторство первой теоремы принадлежит логику Эрнсту Цермело (1871-1956). Он сформулировал и доказал ее в 1912 году. Эта теорема подтверждает, что любая конечная игра с полной информацией (например, шашки или шахматы) имеет оптимальное решение в чистых стратегиях, то есть в отсутствие элемента неопределенности. Эта теорема не описывает, как можно найти подобные стратегии.

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

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

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

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

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