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

Эта платежная матрица говорит нам, что если игрок А выберет стратегию 2, а игрок В — стратегию 1, то в результате выигрыш первого составит 1, а проигрыш второго — 6. Если же игрок А выберет стратегию 1, а В — 2, то проигрыш первого составит 3, а выигрыш второго — 5. Ниже приведен еще один, более простой способ изображения платежной матрицы с такой же расшифровкой.

В1

В2

А1

10,2

-3,5

А2

1-6

4,8

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

Джон фон Нейман за чаепитием с выпускниками в Институте перспективных исследований Принстона (IAS) в ноябре 1947 года.

Бюст фон Неймана в Будапеште.

В 1944 году Оскар Моргенштерн (на фото) и Джон фон Нейман выпустили совместную работу Theory of Games and Economic Behavior («Теория игр и экономическое поведение·).

В1

В2

А1

9

-3

А2

-2

14

Эта матрица показывает, что если игрок А выберет первую стратегию, а игрок В — вторую, то первый потеряет 3, а второй выиграет 3, и так далее для остальных ячеек.

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

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

Предшественником фон Неймана в моделировании игр был французский математик Эмиль Борель (1871-1956), опубликовавший с 1921 по 1927 год серию работ по теории игр, целью которых было установить выигрышные стратегии вне зависимости от фактора удачи или психологического состояния игроков в момент принятия решений. Несмотря на то что их работы в чем-то схожи, фон Нейман всегда утверждал, что проводил свои исследования совершенно независимо от Бореля. Можно с точностью сказать, что математические результаты фон Неймана имеют более общий характер и отвечают на такие ключевые вопросы, которые никогда даже не поднимались в работах Бореля. Тем не менее некоторые ученые отстаивают важность его вклада и, говоря об этой схеме, называют ее теорией Бореля — Неймана.

ПЕРВАЯ ТЕОРЕМА О МИНИМАКСЕ

Для того чтобы установить выигрышную стратегию в игре, игроки должны отвечать двум требованиям.

1. Они оба должны быть рациональными.

2. Они оба должны выбирать свои стратегии, ориентируясь исключительно на личную выгоду.

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

В1

В2

B3

А1

-5

0

-2

А2

1

-3

-2

A3

3

8

-1

Она содержит три возможных выбора для каждого игрока. Предположим, что числа обозначают выигрыши или проигрыши в евро. Следовательно, речь идет об игре с нулевой суммой в ее нормальной форме. Проанализируем возможные стратегии игроков. Допустим, В выбирает первую стратегию. В таком случае лучшим вариантом для А будет третья стратегия: с ней он заработает 3 евро, тогда как с первой потеряет 5, а со второй выиграет всего 1. Если же В выберет вторую стратегию, то А тоже будет лучше следовать третьему варианту, так как он позволяет заработать больше всего. Наконец, если В выберет третью стратегию, то А проиграет в любом случае, но его проигрыш составит только 1 евро. Следовательно, для А лучшей стратегией, безусловно, будет третья, вне зависимости от выбора В.

У игрока В немного другая ситуация. Если А выберет первую стратегию, наилучшим вариантом будет В1. В случае А2, разумеется, следует выбрать В2, а в случае A3 В должен выбрать третью стратегию, так как с ней он потеряет меньше всего. При этом В не имеет ни малейшего понятия о том, как поступит А, и тем не менее он должен сделать свой выбор. Именно в этот момент строится следующее предположение: «А — рациональный игрок, и лучший вариант для него — A3; в этом случае ВЗ будет для меня выгоднее всего, и значит, я последую этой стратегии». Игрок В знает, что в противном случае он проиграет, и пытается свести этот риск к минимуму.

Исследуя эту схему, фон Нейман сделал следующее замечание: на каждой строке всегда есть число меньше остальных двух. Он назвал его минимальным значением. Например, в предыдущей таблице в первой строке стоят числа -5, 0, -2. Самое маленькое из них -5. Таким же образом, минимальное значение для второй строки -3, для третьей —1. Фон Нейман взял самое большое из этих трех чисел, —1 (из всех трех вариантов оно является минимальным проигрышем), и назвал его максимином.

Затем он проделал то же самое для столбцов, но наоборот. Найдем самое большое, то есть максимальное, число в каждом столбце. В первом это будет 3, во втором 8, в третьем -1. Теперь определим самое маленькое из них, минимакс, которым в этом случае будет -1. Таким образом, в этой игре максимин и минимакс совпали в -1. И не случайно, ведь именно это и утверждается в теореме фон Неймана: «В большинстве игр с двумя участниками и нулевой суммой максимин всех строк всегда совпадает с минимаксом столбцов», и оно будет значением игры при оптимальной стратегии для обоих игроков.

Этот результат, известный как первая теорема о минимаксе, был опубликован в статье 1928 года Ж теории стратегических игр». В ней фон Нейман заложил общие основы будущей теории игр. Важно подчеркнуть еще раз: для того чтобы удовлетворить условиям теоремы фон Неймана, оба игрока должны быть рациональными, заботиться исключительно о собственных интересах и очень тщательно анализировать свои возможные стратегии. Эти критерии выполняются не во всех играх. Например, если один из игроков — природа, то в силу вступают произвольные факторы, и этот противник, разумеется, не осуществляет никакого анализа.

БИТВА В МОРЕ БИСМАРКА

Теория игр имела и продолжает иметь тесную связь с так называемыми военными играми. Одним из первых случаев, когда она была применена на войне, стало сражение в море Бисмарка, состоявшееся 23 декабря 1942 года, в котором столкнулись стратегии американского генерала Джорджа Кенни и контр-адмирала Масатоми Кимуры. В конце боя были потоплены все транспортные суда и половина японских кораблей. Благодаря критерию минимакса командование США выбрало оптимальную стратегию и установило новую доктрину для разведывательных полетов. Японский флот должен был выйти из порта Рабаул на северо-востоке острова Новая Британия и направиться в порт Лае для подкрепления. У контр-адмирала Масатоми Кимуры было два варианта: выбрать северный маршрут, пролегавший по морю Бисмарка, где обычно были очень плохие климатические условия, или южный, с более благоприятными. Генерал Кенни должен был сконцентрировать все самолеты-разведчики на одном из этих двух маршрутов, учитывая при этом количество дней, которое ему потребовалось на бомбардировку, как только были бы замечены японские корабли. Применив к платежной матрице критерий минимакса, авторы стратегии выяснили, что при выборе северного маршрута предполагаемое количество дней для бомбардировки в любом случае равнялось бы 2, поэтому был сделан выбор в пользу следующей стратегии.