Камень, ножницы, теорема. Фон Нейман. Теория игр - Коллектив авторов - Страница 14

Самолеты союзнической армии атакуют японский корабль во время сражения в море Бисмарка.

Кимура

Северный маршрут

Южный маршрут

Кенни

Северный маршрут

2

2

Южный маршрут

1

3

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

Джон фон Нейман

Логично было бы ожидать от ученого, решившего исследовать теоретические загадки игр, выбора в качестве модели шашек или шахмат. Фон Нейман был очень хорошо знаком с этими играми еще с детства. И тем не менее в статье 1928 года, в которой он доказал теорему о минимаксе, приводится тщательный анализ игры в... покер. Широко известно, что фон Нейман очень любил эту игру, хотя не всегда добивался в ней больших успехов. По его мнению, самым интересным аспектом покера был блеф, который делал выбор стратегии еще более сложным. В покере гораздо труднее математически установить оптимальную стратегию по сравнению с играми с двумя участниками и нулевой суммой. Несмотря на это фон Нейман придумал упрощенный вариант покера, который позволил ему включить эту игру в свои исследования.

СЕДЛОВЫЕ ТОЧКИ

Представим, что игроки А и В участвуют в игре со следующей платежной матрицей.

В1

В2

вз

А1

-3

-1

4

А2

3

0

1

A3

3

-1

-4

Когда игрок А выбирает стратегию 1, максимальный проигрыш имеет место, если стратегию 1 выберет и игрок В. Для А это означает потерю -3, что выделено жирным шрифтом в таблице ниже.

В1

В2

В3

А1

-3

-1

4

-3

А2

3

0

1

0

A3

3

-1

-4

-4

3

0

4

Следуя этой схеме, постепенно записываются максимальные потери при каждой стратегии. Теперь возьмем игрока А. Для него наименьшим из всех значений будет 0, что соответствует стратегии 2. Это значение фон Нейман назвал значением игры. Если оно равно 0, как в этом примере, игру называют справедливой. Для игрока В также минимальное значение в этом случае равно 0, что соответствует стратегии 2.

Заметим, что обе стратегии минимакса совпадают в одной ячейке таблицы (А2-В2). Ее значение является минимальным на строке и максимальным в столбце. Эту точку называют седловой. Ее может и не быть, но если она есть, то влияет на стратегию обоих игроков. В предыдущей таблице мы видим, что никому из игроков невыгодно менять стратегию. Это ситуация равновесия, при которой игра достигает оптимального результата, так как стратегия минимакс одного игрока совпадает с минимаксом другого. Если в игре есть седловая точка, можно утверждать, что в ней есть стабильная стратегия. Это конец игры.

Изобразить седловую точку легко, если мы представим себе седло с двумя перпендикулярными плоскостями. Обозначим плоскость, которая соединяет седло со стременами, через Л, а вторую, идущую от головы до хвоста, — В. Игрок, следующий в направлении Л, должен подняться, чтобы достичь максимума в седловой точке, а игрок В должен спуститься, чтобы достичь в той же точке минимума.

Исходя из этого фон Нейман определил седловую точку как точку матрицы, обладающую следующими характеристиками.

1. Она имеет минимальное значение на своей строке.

2. Она имеет максимальное значение в своем столбце.

ДЖОН ФОРБС НЭШ

Джон Форбс Нэш родился 13 июня 1928 года в Блюфильде, штат Вирджиния, США. Уже в очень раннем возрасте он проявил незаурядные способности к математике и оказался в числе десяти учеников его же возраста, получивших стипендию на учебу в Политехническом институте Карнеги.

Там он сначала изучал инженерное дело и химию, а позже понял, что его настоящее призвание — математика.

После института Нэш поступил в Принстонский университет. Там он заслужил восхищение сокурсников придуманной им настольной игрой, которая позже появилась в продаже под названием гекс. Увлечение играми было частью математических исследований Нэша. В 1950-е годы теория игр стала одной из самых интересных областей математики. Нэш внес ключевой вклад в первое экспериментальное изучение дилеммы заключенного (см. главу 5), а затем занялся играми с нулевой суммой, или некооперативными играми, в которых игроки преследуют прямо противоположные интересы. Одним из самых важных достижений ученого стало понятие так называемого равновесия Нэша. Впоследствии он основал на нем новую экономическую теорию, за которую получил Нобелевскую премию по экономике в 1944 году. Равновесие Нэша проявляется в ситуации, когда две стороны приходят на определенном этапе игры или в сделке к соглашению, нарушение или изменение которого причинит ущерб им обеим. Равновесие характеризует такую фазу игры, в которой ни один из ее участников не может увеличить выигрыш, изменив стратегию в одностороннем порядке.

Если во время игры участник А предположит, что В не поменяет стратегию и, следовательно, сохранит свою, и участник В, в свою очередь, тоже подумает, что Л сохранит стратегию, то говорится, что игра достигла равновесия Нэша, названного так в честь американского математика Джона Форбса Нэша (р. 1928). В конкретной игре равновесия Нэша может не быть, или оно может быть одно либо их окажется несколько.

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

Решка

Орел

Решка

1

-1

Орел

-1

1

Легко убедиться, что разница между минимальным из максимальных значений и максимальным из минимальных составляет два евро. Изучая ситуации такого типа, фон Нейман еще больше отточил свою теорию игр и ввел различие между чистыми и смешанными стратегиями. К первым относятся игры, в которых игрок выбирает одну и ту же стратегию во всех раундах. Если оба игрока выбирают один и тот же путь, все партии будут одинаковыми. Напротив, в играх со смешанными стратегиями игрок меняет свое поведение от раунда к раунду произвольным образом.

Например, он может определить свою стратегию в зависимости от подброшенной монеты. В статье 1928 года Джон фон Нейман привел математическое доказательство того, что в каждой игре с двумя участниками и нулевой суммой, в которой можно играть с чистыми или смешанными стратегиями, стратегия минимакс каждого из игроков всегда привела бы к стабильной ситуации, седловой точке. На этом результате основана общая теория игр. Наконец, теорема о минимаксе утверждает, что в каждой конечной игре с двумя рациональными игроками, нулевой суммой и с чистой или смешанной стратегией всегда есть решение. Фон Нейман считал эту теорему краеугольным камнем теории игр.