close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
1
§ 3. Позиционные игры
1. Игры на графах.
Продолжим рассмотрение комбинаторных игр.
Ориентированный граф можно задать парой G = (X, F), где X — непустое
множество вершин, а F — функция следования, ставящая в соответствие каждой
вершине x ∈ X некоторое подмножество X: F(x) ⊂ X. Будем считать, что X —
множество позиций, а F(x) представляет собой позиции, в которые игрок может
перейти из x (т.е. F(x) — это множество непосредственных потомков позиции x).
Будем называть элементы F(x) следствиями, или, лучше, опциями позиции x.
Если F(x) пусто, т.е. у x нет опций, x называется терминальной позицией.
Зафиксируем начальную позицию x0 ∈ X и будем следовать правилам:
1) играют 2 игрока, 1-й игрок ходит первым, начиная в позиции x0 ;
2) ходы игроков чередуются;
3) в позиции x игрок, чья очередь ходить, должен выбрать позиции y ∈ F(x);
4) игрок, чья очередь хода пришлась на терминальную позицию, проигрывает.
Чтобы избежать бесконечного числа ходов, часто требуют выполнения условия:
5) для любой позиции x ∈ X найдется положительное целое n такое, что
всякий путь, начинающийся в x, имеет длину n.
Такие графы называются прогрессивно ограниченными. Если граф G при
этом конечный, то это условие эквивалентно тому, что в графе нет контуров (т.е.
ориентированных циклов).
Пример 1. Для игры вычитания при S = {1, 2, 3}
0
1
2
3
4
5
Функцией Шпрага-Гранди (Sprague-Grundy) графа (X, F) называется
функция g : X →
такая, что g(x) = min {n 0 : n g(y) ∀y ∈ F(x)}. Эту формулу
можно записать компактнее, если воспользоваться понятием mex (minimal excludant). Минимальный эксклюзив множества неотрицательных целых определяется как наименьшее неотрицательное число, не принадлежащее этому множеству.
Тогда g(x) = mex {g(y) : y ∈ F(x)}.
Функция Гранди определена рекурсивно, и априори не ясно, корректно ли
она определена, т.е. будет ли она однозначной и всюду определенной.
Теорема 1. Для прогрессивно ограниченных графов функция Гранди всюду
определена, однозначна и принимает конечные значения.
Доказательство. Пусть граф G = (X, F) прогрессивно ограничен. Тогда в силу определения для каждой вершины x ∈ X число l(x) = длине самого длинного
пути, начинающегося в x, является конечным. В частности, если x — терминальная вершина, l(x) = 0. Будем называть l(x) уровнем вершины x. Множество всех
вершин X разбивается на множества Xn = {x ∈ X : l(x) = n} вершин фиксированного
уровня.
2
Отметим одно свойство функции уровня l: если y ∈ F(x), то l(y) < l(x), т.е.
уровень опции меньше (хотя бы на 1) уровня позиции.
Покажем, что для любого x∗ g(x) однозначно вычисляется и < ∞. Пусть n =
∗
l(x ). Полагаем для x ∈ X0 g(x) = 0. Затем для i от 1 до n вычисляем для всех
x ∈ Xi g(x) по mex-правилу: g(x) = mex {g(y) : y ∈ F(x)}. Вычисление корректно,
т.к. для любой опции y ∈ F(x) уровень меньше i и, следовательно, функция Гранди
g(y) уже вычислена.
Теорема 2. g(x) = 0 ⇔ x есть P-позиция, g(x) 0 ⇔ x есть N-позиция.
Действительно,
1) если x — терминальная позиция, то g(x) = 0.
2) для каждой позиции x с g(x) = 0 все опции y имеют g(y) 0.
3) для каждой позиции x с g(x) 0 найдется хотя бы одна опция y с g(y) = 0.
Ясно, что функция Гранди содержит больше информации, чем просто разбиение на P- и N-позиции.
Пример 1. Функция Гранди для игры вычитания при S = {1, 2, 3}:
x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 . . .
g(x) 0 1 2 3 0 1 2 3 0 1 2 3 0 1 . . .
т.е. g(x) = x mod 4.
Пример 2. Рассмотрим ориентированный граф без контуров и для него построим функцию Гранди.
Пример 3. Игра “вычитание квадратов”. Это игра вычитания с множеством
S = {1, 4, 9, 16, . . .}. Граф игры несложно построить, так как у всех игр вычитания
графы аналогичны и имеют естественное представление в линейном виде. Вершины графа суть неотрицательные целые числа, стрелки из каждой вершины образуют конгруэнтные фигуры. Вместо графа можно начертить одномерную таблицу.
x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 . . .
Расставим в таблице метки P и N, соответственно тому, является ли позиция
x P- или N-позицией. Это можно сделать с помощью алгоритма, известного как
”решето Эратосфена”.
3
Функция уровня в данном случае не представляет интереса, так как l(x) = x;
интереснее функция удаленности r(x), определяемое правилами:
1) r(x) = 0, если x — терминальная позиция;
2) r(x) = 1 + min r среди всех возможных P-опций, если x — N-позиция;
3) r(x) = 1 + max r среди всех возможных опций, если x — P-позиция.
Удаленность полезна при поиске стратегии игры в проигрышной позиции,
максимизирующей число ходов при правильной игре противника, и тем самым
увеличивающей вероятность его ошибки.
Выпишем также значения функции Гранди g(x).
x
?
r
g
0
P
0
0
1
N
1
1
2
P
2
0
3 4 5
N N P
3 1 2
1 2 0
6
N
3
1
7
P
4
0
8 9 10 11 12 13 14 15 16 17 18 19 20 21 . . .
N N P N P N N P N P N N P N ...
5 1 4 3 6 7 3 4 1 8
1 2 0 1 0 1 2 0 1 0
2. Сложение игр. Эквивалентные игры.
Будем рассматривать нормальные беспристрастные игры без ничьих. Такие
игры полностью определяются своими правилами и начальной позицией.
Игру ним с начальной позицией, состоящей из одной кучи из n предметов,
обозначим ∗n.
Сумма G+H двух игр G и H определяется так: игрок может делать ход в
игре G или H, оставляя позицию в другой игре нетронутой. Ясно, что операция
сложения игр комутативна и ассоциативна.
Игру ним в позиции (m, n, k) можно записать как ∗m + ∗n + ∗k.
Существует нейтральный элемент, который можно складывать с любой игрой, не изменяя ее — это пустая куча в ниме ∗0: G + ∗0 = G. Но другие игры
тоже могут служить нейтральным элементом — а именно, любая игра с начальной
P-позицией.
Игры G и H называются эквивалентными, G ≡ H, если для всякой игры
J, G+J есть P-игра тогда и только тогда, когда H+J есть P-игра. Аналогично
можно сказать: G ≡ H, если для всякой игры J, G+J есть N-игра тогда и только
тогда, когда H+J есть N-игра.
Введенные понятия определяют на множестве нормальных беспристрастных
игр некоторую алгебраическую структуру. Справедливы следующие утверждения.
1. Если G ≡ H, то игры G и H одновременно являются P- или N-играми.
2. Две P-игры эквивалентны. (Однако неверно, что две N-игры эквивалентны).
3. G + G ≡ ∗0. (Это так называемый принцип копированния.)
4. Если любой опции игры G соответствует некоторая эквивалентная ей опция игры H, и наоборот (т.е. опции игр G и H эквивалентны), то игры G и H
эквивалентны.
Последние два утверждения очень важны. Во-первых, оказывается что множество игр, рассматриваемое с точностью до эквивалентности, образует группу по
сложению, потому что для каждой игры определена обратная игра −G = G. Более
4
того, равенство элемента своему обратному характерно только для сложения по
модулю 2, т.е. для циклической суммы ⊕. Следовательно, справедливо утверждение:
5. ∗n + ∗m ≡ ∗(n ⊕ m).
6. Если n = 2a +2b +2c +. . ., где a > b > c > . . . 0, то ∗n ≡ ∗(2a )+∗(2b )+∗(2c )+. . ..
Это утверждение называется принципом Бутона по имени математика, впервые проанализировавшего игру ним. Таким образом, мы приходим к известному
нам способу определить, к какому типу относится позиция в игре ним.
На минуту отвлечемся и рассмотрим модификацию игры ним.
Пример 1. Игра покер-ним. В добавление к правилам игры ним разрешим
игроку своим ходом не только брать предметы из некоторой кучи, но и класть
в нее предметы, которые у него накопились, в любом количестве.
Условие окончания игры в покер-ниме нарушено: игра может продолжаться
до бесконечности из-за повторения ходов, но если игрок в данной позиции может выиграть в обычный ним, то он может выиграть и в покер-ним. Когда его
противник забирает предметы, то он отвечает, как в обычном ниме, если же его
противник выкладывает предметы, то он тут же все эти предметы забирает, восстанавливая позицию. При этом запас предметов у его противника уменьшается,
что не позволяет тому затягивать игру до бесконечности.
Рассмотрим игру, в которой опции игрока 1 — игры, эквивалентные
∗0, ∗1, ∗2, ∗5, ∗9. Такую игру можно рассматривать как особую кучу игры ним из
3 предметов, которая может быть уменьшена до 0,1,2, или увеличена до 5 или
9. То, что мы говорили о покер-ниме, показывает, что дополнительная свобода
увеличения числа предметов не имеет значения.
Правило минимального эксклюзива. Если опции игры G эквивалентны
кучам нима, размеры которых образуют множество S :
опции G ≡ ∗s1 , ∗s2 , ∗s3 , . . . ;
S = {s1 , s2 , s3 , . . .},
то G эквивалентна куче, размер которой равен минимальному эксклюзиву множества S :
G ≡ ∗(mex S ).
Как видим, мы получили другой подход к функции Гранди: g(G) = mex S .
Если mex S = 0, G является P-игрой.
Пример 1. Игра Цзяньшинцзы (выбирание камней) или игра Витхофа(Wythoff). Имеется позиция — пара неотрицательных целых чисел (m,n). Ход
заключается в том, что можно
a) вычесть из одного числа положительное целое;
b) вычесть из обоих чисел одно и то же положительное целое.
Эта игра эквивалентна игре “раненый ферзь”: на шахматной доске ферзь из
позиции (m,n) может ходить вниз, влево или по диагонали влево-вниз. Выигрывает
тот, кто поставит его на поле (0,0).
Найдите P-позиции.
Пример 2. Игра кегли (Kayles). Нарисуем несколько рядов палочек (кеглей).
Каждый игрок своим ходом может зачеркнуть одну или две соседние палочки (т.е.
сбить одну или две соседние кегли).
5
Например, для позиции (3,4,3) игра может развиваться так:
||| |||| ||| → | |||| ||| → | | | ||| → . . .
Найдите функцию Гранди и P-позиции для n подряд стоящих кеглей.
3. Развернутая форма игры.
Комбинаторные игры являются подклассом позиционных игр. В позиционных
играх имеется
1) множество игроков;
2) множество возможных позиций игры, обычно конечное;
3) правила игры, определяющие для каждой позиции и каждого игрока, какие ходы возможны.
По сравнению с комбинаторными играми ограничений значительно меньше.
Если же сравнить со стратегическими играми, то при таком задании игры больше
внимания уделяется порядку ходов и той информации, которая при этом открывается игроку. Основной способ представления позиционной игры, называемый развернутой формой игры, — это дерево игры, являющееся направленным графом без
циклов с выделенной вершиной (корнем). Стрелки идут в направлении от корня.
Вершины изображают позиции игры; в каждой позиции один конкретный игрок
должен сделать (выбрать) ход — одну из стрелок, выходящих из данной вершины.
У каждой нетерминальной вершины ставится метка игрока, который в этой
позиции делает ход. В терминальных вершинах (где игра заканчивается) ставится
профиль выигрышей игроков. Каждая стрелка (ветвь дерева) помечается названием хода, который эта стрелка изображает.
Пример 1. Вот простейшая позиционная игра. Игра начинается в позиции,
где 1-й игрок выбирает ход: вверх или вниз (U или D). Затем ход делает 2-й
игрок, выбирая — влево или вправо (L или R).
(1,1)
U
I
D
(0,0)
L
II
R
(2,0)
Пример 2. Камень–ножницы–бумага.
I
К
Б
Н
II
К Н
0,0
Б
К Н
Б
1,-1 -1,1 -1,1 0,0 1,-1
К Н
1,-1 -1,1
Б
0,0
6
В развернутой форме игры нелегко изобразить одновременные ходы. Можно
их, однако, имитировать с помощью тайных ходов — предположим, что 1-й игрок
делает свой ход раньше 2-го, но его опция 2-му игроку неизвестна. Поэтому все
3 опции (камень–ножницы–бумага) объединяются в одну “кажущуюся” позицию,
или информационное множество 2-го игрока.
Пример 3. Упрощенный покер. Два игрока делают ставки, каждый по 1
доллару, — они кладут их в центр стола, образуя банк (или пот — pot) из $2.
Затем ход делает природа — игрок I получает одну карту, которая с вероятностью 14 выигрывающая и с вероятностью 34 проигрывающая. Игрок I видит, но не
показывает свою карту. Игрок II не получает карты. Затем игрок I может открыть (check) или повысить (bet). Если он открывает, то его карта открывается
— и если она выигрывающая, то забирает банк, выигрывая 1 $, иначе игрок II
забирает банк, а игрок I проигрывает $1. Если повышает, то добавляет в банк $2.
Затем 2-й игрок может пасовать (fold) или согласиться (call). Если он пасует,
то проигрывает $1 (1-й игрок забирает банк), если соглашается, то добавляет в
банк $2 и карта открывается.
N
выигр.
1/4
проигр.
3/4
I
I
bet
check
bet
check
II
-1
1
call
3
call
fold
1
-3
fold
1
Следует отметить, что дерево игры (иначе называемое деревом Куна) и граф
игры (иначе называемый граф Гранди), введенный для комбинаторных игр, — это
разные понятия. В графе игры представлены все возможные позиции; дерево игры
представляет все возможные розыгрыши игры.
Кроме того, есть еще два новых момента.
1. Случайные ходы — для их представления в теории к списку игроков добавляется еще один фиктивный игрок (условно называемый “природа” — Nature),
который тоже выбирает свои ходы, но делает это не так свободно, как обычные
игроки, а с предписанными вероятностями.
2. Когда игрок должен выбрать свой ход, он может не знать, в какой из
позиций игры он находится, потому что не знает, какой ход (ходы) был сделан
до этого. И все такие неразличимые для него позиции объединяют в одно информационное множество (на рисунках их обводят контуром или соединяют
пунктирной линией). Для игрока это одна и та же позиция, но реально они отличаются и дальнейшее развитие игры зависит от истинной позиции, а не от кажущейся. Но игрок делает свой выбор опций и дальнейшей стратегии, опираясь
на свое знание о кажущейся ему позиции (т.е. о том информационном множестве,
в котором он находится). Т.к. игрок не может различать позиции внутри одного
7
информационного множества, то и ходы, возможные в этих позициях, должны
быть одинаковыми (с точки зрения этого игрока). Значит, в любом информационном множестве h должно быть указано соответствующее множество M(h) ходов,
а игрок выбирает ход m ∈ M(h).
Итак, дерево Куна (дерево игры) — это дерево, в котором отмечены
1) все выигрыши игроков в терминальных вершинах;
2) все информационные множества;
3) все нетерминальные вершины — помечены номером игрока, чья очередь
ходить;
4) все стрелки (ветви) — помечены действием, которое выполняет игрок в
данной позиции, а также вероятностью действия, если это ход природы.
Игра, в которой все игроки знают дерево Куна игры, называется игрой с
полной информацией.
Игра, в которой каждый игрок помнит всю информацию, которую он знал на
предыдущих ходах, и в том числе помнит все ходы, которые он делал, называется
игрой с совершенной памятью.
Пример 4. Вот пример несовершенной памяти: игрок на 1-м ходе может
пойти влево (L) или вправо (R). После этого он забывает, что он делал на 1-м
ходе (но помнит, что сделал ход) и снова стоит перед выбором — пойти влево
(l)) или вправо (r). В этой игре есть 4 чистые стратегии: (L,l), (L,r), (R,l), (R,r)
с исходами a, b, c, d соответственно.
I
L
R
I
l
a
r
b
l
c
r
d
Формальное определение: игра в развернутой форме состоит из
1) дерева игры Γ, в котором имеется множество вершин (позиций) X и множество стрелок A ⊂ X × X; множество стрелок, выходящих из вершины x, обозначается A(x). Есть выделенная начальная позиция (корень дерева). Есть множество
терминальных вершин T = {x ∈ X : A(x) = ∅};
2) отображения порядка ходов: ι : X \ T → N (N — множество игроков), для
каждого игрока i ∈ N обозначается Xi = ι−1 (i) множество позиций, в которых он
делает ход;
3) разбиения на информационные множества каждого множества Xi : Xi =
h∈Hi h (h — одно информационное множество, Hi — семейство всех информационных множеств игрока i); для каждого h задано множество M(h) ходов, возможных
в данном информационном множестве; для каждой позиции x ∈ h задано отображение a x : M(h) → A(x);
4) множества векторов выигрышей u(t) = (ui (t))i∈N ∈ N для каждого t ∈ T ,
где ui (t) — выигрыш игрока i в терминальной позиции t.
8
Пример 5. Игра Конана Дойля. Шерлок Холмс намерен отправиться из Лондона в Дувр и затем на континент, чтобы спастись от профессора Мориарти, который его преследует. Сев в поезд, он после отхода поезда замечает на платформе
профессора Мориати. Ш.Х. допускает — и совершенно прав — что его противник,
который увидел его, может взять специальный поезд, чтобы догнать его. Перед
Ш.Х. альтернатива — или продолжать поездку в Дувр, или сойти в Кентербери, единственной промежуточной станции. Профессор М. достаточно умен, чтобы
предусмотреть те же возможности, и потому стоит перед тем же выбором. Оба
должны выбрать место выхода из поезда, не зная о соответствующем решении
другого. Если в результате они окажутся на одной платформе, то Ш.Х. может
считать себя с достоверностью убитым. Если Ш.Х. благополучно достигнет Дувр,
то может считать себя спасенным. (В рассказе Ш.Х. выходит на промежуточной
станции и победоносным взглядом провожает М., едущего на всех парах в Дувр.)
Данную игру можно представить в нормальной и развернутой формах.
M
C
D
H C −100
0
D 50 −100
Dover
Holms
D
-100
C
50
D
0
Moriarty
Canterbury
C
-100
Используя формулы для решения игр 2х2, получим значение игры v = −40
и оптимальные смешанные стратегии s∗ = (0.6, 0.4) для Ш.Х. и t∗ = (0.4, 0.6) для
Мориарти. Таким образом, Ш.Х. должен с вероятность 60% сойти в Кентербери,
а Мориарти с вероятностью 60% должен ехать в Дувр. В рассказе Конан Дойль
своим героям предписывает именно то поведение, которое, в согласии с нашим
анализом, наиболее вероятно.
Пример 5. Игра “Террорист”. В самолет, который летит из Майами в НьюЙорк, сел террорист. Он требует, чтобы пилот летел на Кубу, угрожая в противном случае взорвать самолет. Предположим, что террорист не может определить,
куда на самом деле летит самолет. Первый ход в этой игре делает пилот, выбирая
опции “Куба” или “Нью-Йорк”. В первом случае игра заканчивается, во втором
— террорист делает ход.
В предположении, что оба игрока рациональны, решение можно найти методом обратной индукции. В соответствии с этим методом игру анализируют с
9
Пилот
Куба
-1,1
Куба
-100,-100
нормальный
сумасшедший
Нью-Йорк
p
Пилот
Террорист
взорвать
N
Пилот
Нью-Йорк
-1,1
1,-1
не взр.
Куба
-1,1
1,-1
Нью-Йорк
-100,0
1-p
Куба
-1,1
I
Нью-Йорк
1,-1
конца. Террорист, оказавшись в Нью-Йорке, будучи рациональным, не будет взрывать бомбы, поскольку −1 > −100. Так что действия террориста можно однозначно
предсказать. Если рациональность террориста является общим знанием, то пилот,
просчитав действия террориста, будет выбирать уже из упрощенной ситуации, и
полетит в Нью-Йорк. Таким образом, исход игры несложно предсказать — пилот
полетит в Нью-Йорк, а террорист не будет взрывать бомбу.
В модификации этой игры террорист может быть отнесен к одному из двух
типов: “нормальный” и “сумасшедший”. Вероятность того, что террорист сумасшедший, равна p. Пилот не знает, с террористом какого типа он имеет дело,
но сам террорист знает свой тип. В игру, таким образом, добавляется игрок —
природа, чтобы показать случайный выбор типа террориста. Природа не имеет
целевой функции и не получает выигрыша.
Если пилот выберет Кубу, то получит -1, если Нью-Йорк, то ожидаемый
2
выигрыш 1 − 101p. (Если p < 101
, то −1 < 1 − 101p и пилот полетит в Нью-Йорк.)
4. [Исключение доминируемых стратегий].
[Вернемся к играм в нормальной форме]. Мы изучали отношение доминирования стратегий: стратегия x доминирует стратегию y, если для всякого профиля a ∈ A a[i : x] a[i : y]. Абсолютным является равновесие в доминантных
(доминирующих) стратегиях, более проблематичными будут равновесия Нэша и
максиминное.
Мы рассмотрим один прием уменьшения размеров стратегической матрицы,
основанной на понятии доминируемой стратегии. Доминируемая стратегия —
это стратегия, для которой найдется хотя бы одна доминирующая стратегия. Рациональный игрок не использует доминируемые стратегии, поэтому таковые, если
они есть, можно отбросить. В предположении общего знания о стратегиях и рациональности каждый игрок может отбросить доминируемые стратегии каждого
игрока.
Пример 1.
t1
t2
t3
s1 4, 3 2, 7
0, 4
s2 5, 5 5, −1 −4, −2
t1
t2
s1 4, 3 2, 7
s2 5, 5 5, −1
t1
t2
s2 5, 5 5, −1
t1
s2 5, 5
t2 t3; s2 s1; t1 t2.
Данный метод называется последовательным исключением строго доминируемых стратегий. Процесс последовательного исключения состоит в построении
10
последовательности множеств S i = S i0 ⊃ S i1 ⊃ . . . ⊃ S ik ⊃ . . . (∀i), где S ik+1 состоит из недоминируемых стратегий в игре (N, (S ik ), ui |S k ). Так как множество S i конечно, эта последовательность должна стабилизироваться на некотором множестве S i∞ . Игра называется разрешимой по доминированию, если все множества
S i∞ , i ∈ N состоят из единственной стратегии каждое.
В нашем примере все опирается на информационные гипотезы: решение 2го игрока применить стратегию t1 основано на уверенности, что 1-й игрок будет
применять стратегию s2; а в этом он уверен, потому что знает, что 1-й игрок
знает выигрыши 2-го игрока и понимает, что тот не будет применять стратегию
t3, а в этом случае для него лучше s2.
Подобное рассуждение, называемое обратной индукцией, проходит и в случае позиционных игр — вспомните пример “Террорист”. Абсолютно четко такой
алгоритм обратной индукции, называемый в случае позиционных игр алгоритмом
Цермело-Куна, применим к играм с совершеннной информацией, т.е. играм, в которых каждое информационное множество состоит из одной вершины. Тогда в
любой позиции игрок, делающий ход, полностью владеет ситуацией.
Рассмотрим предтерминальную вершину y. Пусть в ней делает ход игрок
i. Рациональный игрок должен сделать ход, максимизирующий его выигрыш ui .
Если есть несколько ходов с максимальным выигрышем, то процедура несколько
усложняется, но не будем сейчас рассматривать такой случай, потребовав, чтобы
выигрыши всех игроков во всех терминальных вершинах были разными. Сделаем
вершину y терминальной, поместив туда вектор выигрышей из той терминальной вершины, куда с большей для себя пользой пойдет игрок i. Таким образом,
повторяя этот шаг, мы сведем всю игру в начальную вершину.
Проиллюстрируем алгоритм на примере простейшей позиционной игры, рассмотренной нами ранее.
Пример 2.
(2,2)
(2,2)
U
U
I
I
D
(3,1)
L
II
D
R
(0,0)
(3,1)
Игрок 2 в предтерминальной вершине выберет ход l; поэтому игра сводится
к игре, в которой 1-й игрок выберет D, так что мы придем к решению (D, l).
Тем не менее остаются некоторые сомнения в правомочности рассуждений
такого типа. Это и сомнения в рациональном поведении игроков, и в общем знании
игры. Рассмотрим пример, в котором наглядно проявляется парадокс обратной
индукции.
Пример 3. “Сороконожка Розенталя”. Один меценат решил подарить университету миллиард долларов. Он приглашает президентов университетов Йелбриджа
и Харфорда и объявляет, что они должны разыграть следующую игру. Дерево
ее имеет вид
11
1
2
1
2
1
2
2
1
1
2
0,0
1,0
0,10
100,0
4
0,1000 10 ,0
6
0,10 5 10 ,0
0,10
7
10 8,0
0,10
9
На первом ходу меценат предлагает 1-му президенту 1 доллар, который тот
может принять или отказаться. В случае его отказа предложение переходит к
другому президенту, но с 10-кратным увеличением.
Применяя алгоритм обратной индукции, получаем, что каждому президенту
выгодно принимать предложение. Поэтому игра должна закончиться на 1-м ходе. Чувствуется, что здесь что-то не так. Например, рассмотрим последний возможный ход 1-го. Согласно алгоритму Цермело-Куна, он должен принять предложение, так как иначе на следующем ходу 2-й президент, будучи рациональным,
возьмет весь миллиард. Но если он действительно рациональный, то почему на
своем предыдущем ходу он отказался от 10 млн.? Ведь теперь 1-й президент не
оставит 2-му ничего!
1/--страниц
Пожаловаться на содержимое документа