Камень, ножницы, теорема. Фон Нейман. Теория игр. - [21]

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

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

ТЕОРИЯ ИГР И ТОПОЛОГИЯ

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

Топология — это область математики, изучающая свойства фигур, которые не меняются при трансформации — расширении, сжатии или растягивании (при условии, что при этом не совмещаются их разные точки и не создаются новые). Фигуры называются топологически эквивалентными, когда одну можно получить из другой при помощи трансформаций такого типа. Чтобы лучше понять, что происходит при этих трансформациях, представим себе некую эластичную плоскость (допустим, из резины или пластилина, довольно легко поддающихся деформации), на которую нанесен рисунок, например квадрат.

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

Особым подвидом такого типа трансформаций являются те, при которых остается неподвижная точка. У некоторых пространств это свойство сохраняется при любом виде непрерывной трансформации, и оно позволяет классифицировать различные виды поверхностей. Из всех теорем, затрагивающих это понятие, нужно выделить теорему о неподвижной точке Брауэра, которую сформулировал голландский математик Лёйтзен Эгберт Ян Брауэр (1881-1966). Теорема звучит сложновато, но ее можно легко объяснить. Представим себе, что мы плавно помешиваем ложкой в чашке с кофе. Согласно теореме Брауэра, как только кофе вернется в состояние покоя, в нем будет такая точка, которая окажется в том же самом положении, как когда мы его перемешивали. Из всех способов помешивания кофе есть один, при котором действие теоремы очевидно, — когда ложка движется вдоль стенок чашки. При таком круговом движении центр жидкости останется неподвижным — как глаз бури,— и именно он будет неподвижной точкой Брауэра.

Фон Нейман обнаружил тесную связь между теоремой о минимаксе и теорией неподвижных точек. Это помогло ему не только доказать свою теорему, но и годы спустя сделать важное дополнение теоремы неподвижных точек Брауэра.

ВОЙНА ПОЛОВ

Несмотря на свое немного устрашающее название, война полов — классический пример теории игр, примененной к повседневной жизни, который позволяет нам овладеть базовыми понятиями теории и прийти к определенным социологическим выводам. Оригинальная схема была представлена Робертом Данканом Люче и Говардом Рейфой в книге Games and Decisions («Игры и решения»). В игре участвует пара — мужчина и женщина, — они должны решить, как провести вечер воскресенья. Предлагается два варианта: пойти на футбольный матч или в кино. И у него, и у нее классические вкусы, так что с предпочтениями все понятно. Но добавляется еще одно условие, которое важнее личных предпочтений: провести вечер нужно вместе, а не отдельно, поскольку это один из немногих дней, когда можно побыть вдвоем. В таком случае его предпочтения будут стоять в следующем порядке.

1. Они вместе идут на матч.

2. Они вместе идут в кино.

3. Он идет на матч, а она в кино.

4. Он идет в кино, а она на матч.

На основе этого мы можем определить следующую платежную матрицу, где 1 обозначает лучший платеж, а 4 — худший.

	Она на футбол	Она в кино
Он на футбол	1, 2	3, 3
Он в кино	4, 4	2, 1

Эта матрица расшифровывается очень просто. Если они оба идут на матч, то он идет куда хочет, и одновременно проводит время с ней (первое условие); при этом она идет не туда, куда хочет, но проводит время с ним, а это второе условие. Если он идет на футбол, а она в кино, то каждый идет куда хочет, но отдельно друг от друга, а это для них обоих третий по предпочтительности вариант (3, 3).

Мы имеем дело с неповторяющейся игрой, то есть с такой, в которую играют только один раз, и в ней нельзя принимать решения исходя из прошлых стратегий. К тому же это игра с нетрансферабельной полезностью и некооперативная, так как предполагается, что в ней нельзя устанавливать предварительные соглашения типа «если ты пойдешь со мной в кино, я заплачу за твой билет».

Стратегия минимакса привела бы нас к следующей ситуации.

	Она на футбол	Она в кино
Он на футбол	1, 2	3, 3	3
Он в кино	4, 4	2, 1	4
	4	3

Самые большие потери для него составляют 3 и 4, поэтому его минимакс равен 3. Для нее — 4 и 3, и ее минимакс также равен 3. Это ситуация, в которой он идет на матч, а она в кино, где платежи составляют 3 и 3, что является лучшим вариантом для обоих. В данном случае стратегия минимакса не приводит к равновесию Нэша, так как один из игроков может поменять стратегию, чтобы получить больший выигрыш. Пока он в одиночестве идет на стадион, он может передумать и пойти в кино, получив таким образом больший платеж. Правда, при этом есть риск, что они оба передумают и понесут максимальные потери.