«Содержание 1 Introduction 2 1.1 Quotes............................................... 2 1.2 About..................................... ...»

Задачник для тигров

Тигр и все-все-все

20 апреля 2010 г.

Содержание

1 Introduction 2

1.1 Quotes............................................... 2

1.2 About............................................... 2 2 Поиск выигрышной стратегии 3 3 Начнем с конца! 7 3.1 Доллар Рубинштейна...................................... 4 За обратной индукцией. Комбинаторные игры 5 Разработка механизмов 6 Повторяемые игры 7 Статические игры 7.1 Игры с нулевой суммой..................................... 8 статические игры (а ля байесовские) 8.1 Аукционы............................................. 8.2 Коррелированное равновесие.................................. 9 динамические игры с несовершенной информацией 9.1 Передача информации

10 кооперативные игры 11 Эволюционные игры 12 Неразобрано! 13 Идеи проектов/курсовых/вопросы с неизвестным (кому?) ответом/конкурсы! 14 Решения 15 Названия концепций решения (Коковин) 16 Названия некоторых стратегий в повторяющейся дилемме заключенного 17 * Задачник для Тигров 1 Introduction Задачи взяты из различных источников, по возможности, указан автор.

В коллекцию (Леша разрешил!) перекочевали задачи из «Большого Задачника Игр» (С. Коковкин, А. Тонис, А. Савватеев и др.). Эти задачи отмечены так «БЗИ».

Если есть вопросы по этой коллекции - [email protected] 1.1 Quotes Ralph: When she put two potatoes on the table, the big one and the small one, you immediately took the big one without asking me what I wanted.

Norton: What would you have done?

Ralph: I would have taken the small one, of course.

Norton: You would? (in disbelief) Ralph: Yes, I would!

Norton: So, what are complaining about? You GOT the little one!

The Honeymooners, James Q. Wilson There are two important concepts in economics. The first is «Buy low, sell high», which is self-explanatory.

The second is opportunity cost, the highest valued alternative that must be sacrificed to attain something or otherwise satisfy a want. I discovered this concept as an undergraduate at Caltech. I was never very in to computer games, but I found myself randomly playing tetris. Out of the blue I was struck by a revelation: «I could be having sex right now.» I haven’t played a computer game since.

Introduction to Methods of Applied Mathematics, Sean Mauch Бюджетное ограничение следует называть принципом кота Матроскина: «Чтобы продать что-нибудь ненужное, надо сначала купить что-нибудь ненужное».

идея Юры Автономова Правильно хватать самый маленький кусок торта! Его можно съесть раньше, чем сестры доедят свои куски, и тогда успеешь взять еще и второй!

по мотивам «Делим по справедливости», Брамс In mastering the material in this book, you are going to have to do a lot of work. This will consist mainly of chewing a pencil or pen as you struggle to do some sums. Maths is like that. Hours of your life will pass doing this, when you could be watching the X-files or playing basketball, or whatever.

Michael D. Alder, An Introduction to Complex Analysis for Engineers Well of course I didn’t do any at first... then someone suggested I try just a little sum or two, and I thought «Why not?... I can handle it». Then one day someone said «Hey, man, that’s kidstuff - try some calculus»... so I tried some differentials... then I went on to integrals... even the occasional volume of revolution... but I can stop any time I want to... I know I can. OK, so I do the odd bit of complex analysis, but only a few times... that stuff can really screw your head up for days... but I can handle it... it’s OK really... I can stop any time I want...

[email protected] (Tim Bierman) 1.2 About Задачник не вызывает сонливости и не имеет противопоказаний.

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

Задачник оборудован тремя аварийными выходами: в передней, средней и хвостовой частях.

Отпускается без рецепта.

Срок годности не ограничен.

Не содержит мелких деталей, которые могут быть проглочены детьми до 3-х лет.

Предисловие:

Задачи упорядочены только по типу!

Условия задач кроме составителя комментировал Тигр - тотем теории игр.

Краткий словарь:

Nash Equilibrium, NE - равновесие по Нэшу. В задачнике этот термин используется максимально широко, в том числе и для игр с неполной информацией.

Subgame Perfect Nash Equilibrium, SPNE - равновесие по Нэшу совершенное в подыграх Weak Sequential Equilibrium - слабое секвенциальное равновесие Sequential Equilibrium, SE - секвенциальное равновесие Common knowledge of information - всеобщность знания Correlated Equilibrium - Коррелированное равновесие Многие задачи можно решать, руководствуясь только здравым смыслом. Т.е. если Вы все-таки так и не поняли, что такое равновесие по Нэшу, попытайтесь ответить на вопрос «Как бы я играл в эту игру?»

По умолчанию предполагается, что все сказанное в условии является всеобщим знанием.

Что означают пометки у задач?

[Т] - Трудная задача [О] - Особенная задача. У особенной задачи может быть смешное условие, а ее решение может кардинально изменить геополитическую обстановку в мире.

Маршруты для туристов (нужно разработать):

[Сюда также что-то типа: эти задачи (список) предлагались в курсе ВШЭ, т.е. несколько маршрутов для самостоятельного изучения] «Последний двоечник». Задачи для тех, кто хочет гарантировать себе один или, если повезет, два балла из десяти:

«PG-13» Parents strongly cautioned. Some material may be inappropriate for children under 13:

«NC-17» No one 17 and under admitted. May contain explicit sex scenes, and/or scenes of excessive violence:

«Для тех, кто и вправду крут». Тигр: По-моему, это задачи, которые составитель задачника не смог решить сам...

«Для прессы» Тигр: Подполковник Киселевич говорил, что любая аудитория делится на три части.

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

2 Поиск выигрышной стратегии Победит тот, кто ходит первым, стратегии особой не надо Неизвестный участник XXVI Турнира имени Ломоносова Здесь собраны задачи, связанные с нахождением оптимальной стратегии в играх с совершенной информацией, но без применения метода обратной индукции Задача 2.1.

С чего все начиналось...

Париж, Людовик XIV, 1654 год, высшее общество говорит о рождении новой науки - теории вероятностей. Ах, кавалер де Мере, «fort honnete homme sans etre mathematicien»... Тигр: «благородный человек, хотя и не математик». Старая задача, неправильные решения которой предлагались тысячелетиями (например, одно из неправильных решений предлагал изобретатель двойной записи, кумир бухгалтеров, Лука Пачоли) наконец решена правильно!

Два игрока играют в честную игру до шести побед. Игрок первым выигравший шесть партий (не обязательно подряд) получает 800 луидоров. К текущему моменту первый игрок выиграл 5 партий, а второй - 3 партии. Они вынуждены прервать игру в данной ситуации.

Как им поделить приз по справедливости?

Задача 2.2.

Джордж и Усама Усама бен Ладен (Usama bin Laden) прячется в одной из ста пещер. Каждую ночь он меняет пещеру, в которой находится, на одну из двух соседних. Джордж Буш младший (George Bush - jr) не видит перемещений Усамы. Каждый день Буш может направить отряд спецназа в одну из пещер.

Тигр: По-моему, это задача про ограниченную рациональность...

а) Конечны ли множества стратегий игроков?

б) Может ли Буш гарантировать поимку Усамы? Если Вы считаете, что да, то укажите оптимальную стратегию; если нет, то докажите.

Задача 2.3.

Chomp! (Shuh, 1952) Шоколадка разделена бороздками на дольки. Игроки ходят по очереди. За ход можно выбрать любую дольку. Выбрав дольку нужно съесть ее и все дольки расположенные выше и правее. Нижняя левая долька отравлена!

Тигр: Зачем же продукты портить, нельзя просто крестиком пометить?

а) Верно ли, что первый игрок выигрывает на прямоугольной шоколадке любых размеров?

б) Верно ли, что первый игрок выигрывает на первой четверти бесконечной шоколадки?

в) Найдите оптимальную стратегию на первой четверти бесконечной шоколадки.

Автор дополнения про бесконечную шоколадку - Роман Школлер Задача 2.4.

Джордж и Саддам Чтобы создать завод для производства оружия массового уничтожения инженеры Саддама должны работать 3 дня на одном месте (возможно с перерывами). Каждый день Саддам выбирает место, где будет работать команда инженеров. Каждую ночь Джордж выбирает одно из мест для бомбардировки. Все потенциальные места постройки завода прекрасно просматриваются со спутника.

При бомбардировке недостроенный завод полностью уничтожается. Ни один пилот не отправиться бомбить завод в ночь 13-го числа любого месяца.

Саддам выигрывает, если ему удается построить завод по производству оружия массового уничтожения. Джордж выигрывает, если не допустит этого. Может ли Саддам построить завод? Если да, то за какое время?

Задача 2.5.

Жадина![26] Двое по очереди берут камни из кучки в которой находится камней. На первом ходу разрешается взять любое число камней, но не всю кучку сразу. На последующих ходах нельзя брать больше камней, чем взял на предыдущем ходу противник. Кто выигрывает при правильной игре?

Задача 2.6.

«Шестиугольники»

Тигр: у студентов английское название «Нех» почему-то вызывает нездоровую реакцию...

Игровое поле поделено на правильные шестиугольники. Белые и черные ходят по очереди, занимая своей фишкой любой незанятый шестиугольник. Белые выигрывают, если им удается соединить непрерывной линией из своих фишек левую и правую сторону доски. Черные выигрывают, если им удается соединить верх и низ. Если правила остались не ясны, можно попробовать поиграть на http://www.mazeworks.com/hex7/ а) Докажите, что ничья в этой игре невозможна.

б) У какого игрока имеется выигрышная стратегия?

в) Никто на Земле не знает, как выглядит выигрышная стратегия в «шестиугольниках». Нашедшему 10 баллов по теории игр.

Задача 2.7.

Deep Blue Представим, что Вы играете партию в шахматы против компьютера. Сколько стратегий использует компьютер во время одной партии?

Задача 2.8.

Modified Nim.

This is a modified version of the game of Nim (in the following we assume that there is an unlimited supply of tokens.) Two players set several piles of tokens in a row. By turns each of them takes one token from one of the piles and adds at will as many tokens as he/she wishes to piles placed to the left of the pile from which the token was taken. Assuming that the game ever finishes, the player that takes the last token wins.

a) Prove that, no matter how they play, the game will eventually end after finitely many steps b) Find a winning strategy c) Do the same for another variant of the game in which the piles are arranged in several rows (not necessarily with the same number of piles each), and players are also allowed to add any number of piles with any number of tokens each to rows placed above the one containing the pile from which the token was taken.

d) Generalize the problem to n-dimensional arrangements (and solve it).

Задача 2.9.

Задача про выборы в совет директоров.

Акционерное общество, капитал которого разделен на обыкновенных акций, проводит выборы совета директоров, в который войдут человек. Выборы проходят по кумулятивной системе: владелец акций получает при голосовании · голосов, которые он в любых пропорциях распределяет между теми кандидатами, которых он хочет видеть в совете директоров. Можно передавать кандидатам дробное количество голосов. После голосования составляется рейтинг кандидатов по убыванию количества набранных ими голосов, и в совет директоров попадают первые человек по рейтингу. При этом если на последние несколько мест претендует большее число кандидатов, набравших одинаковое количество голосов, то эти несколько мест распределяются между такими кандидатами случайным образом.

Сколько акций нужно иметь некоторому акционеру, чтобы гарантированно (вне зависимости от действий остальных акционеров) провести в совет директоров своих кандидатов?

Как изменится ответ, если акционер может передать кандидату только целое количество голосов?

Чему равно минимальное число акций при = 100, = 15, = 5?

Источник: Григорий Хацевич, Алексей Киселев.

Задача 2.10.

Гномы Злобный дракон поймал трех гномов. И решил поиграться с ними. Каждому гному он надевает с равными вероятностями черный или белый колпак.

Тигр: Значит дракон - это датчик случайных колпаков?

Гномы видят чужие колпаки, но не видят своих и не могут общаться после выдачи колпаков. Каждый гном может попытаться угадать цвет своего колпака, либо промолчать. Дракон отпустит гномов, если хотя бы один гном угадал цвет своего колпака, и никто не сделал ошибки. Если все одновременно промолчали, или кто-нибудь ошибся, то все гномы будут съедены. Перед игрой гномы могут договориться о стратегии игры.

а) Как им следует играть? Какова вероятность того, что они будут спасены?

б) Если от далекого спутника нужно получить один бит информации («да» или «нет»), то, отправив три бита, можно не бояться того, что природа «испортит» один из них. Постройте этот простой код.

Проведите аналогию с предыдущим пунктом. Тигр: Три гнома - три бита?

Идея этой задачи используется не только при космической связи. Чтобы неглубокие царапины на компакт диске не вызывали потерь данных при записи используется код Рида-Соломона.

Тигр: А как звали третьего гнома?

Задача 2.11.

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

Как следует играть гномам? Сколько гномов можно гарантированно спасти? Тигр: Кто последний к дракону?

Задача 2.12.

Вася и Петя поступили на испытательный срок на одну работу. Они не могут координировать свои действия. У Васи 4 разные рубашки, причем два раза подряд он в одной не ходит, у Пети 5 рубашек, причем 4 точно такие же, как у Васи. Петя не хочет появиться в такой же рубашке, как и Вася. Как ему себя вести?

Задача 2.13.

Парадокс гладиаторов [Winkler, ТО] На арене две команды гладиаторов, и. Каждый гладиатор обладает определенной силой, неизменной по ходу игры. В команде всего гладиаторов с силами { }, в команде - гладиаторов с силами { }. Игра проходит в виде последовательных турниров, в каждом из которых участвует по одному гладиатору от каждой стороны. Если в очередном турнире встречаются гладиаторы с силами и, то вероятность победы первого определяется величиной +. Гладиатор, проигравший турнир, выбывает из игры, выигравший - возвращается в команду. Исходы турниров независимы. Это означает, что гладиаторы не устают, но и не приобретают опыта. Стратегия команды предписывает, какого гладиатора выдвигать на очередной турнир в зависимости текущего состава команды. Игра ведется до полного выбывания из игры одной из команд.

а) Зависит ли вероятность победы команды от используемой стратегии? Если Вы считаете, что да, то укажите оптимальную стратегию; если нет, то докажите.

б) Допустим, что при выборе гладиатора для очередного турнира команда может учитывать не только свой собственный текущий состав, но и состав команды-соперника. Соответственно изменяется и понятие стратегии. Будет ли зависеть вероятность победы команды от стратегии в этом случае?

Задача 2.14.

Парадокс гладиаторов-вампиров. [Winkler, ТO] В отличие от обычного гладиатора, у победившего гладиатора-вампира сила увеличивается на силу побежденного им гладиатора-вампира. В остальном правила поединка такие же, как в предыдущей задаче.

Зависит ли вероятность победы команды от используемой стратегии?

Задача 2.15.

Игра в шахматы [Парадоксы, О] Маша и Саша играют в быстрые шахматы. У них одинаковый класс игры и оба предпочитают играть белыми, т.е. вероятность выигрыша белых > 0, 5. Партии играются до 10 побед. Первую партию Маша играет белыми. Она считает, что в следующей партии белыми должен играть тот, кто выиграл предыдущую партию. Саша считает, что ходить белыми нужно по очереди. При каком варианте правил у Маши больше шансы выиграть?

Задача 2.16.

О пользе гадания на кофейной гуще замолвите слово... [25] Маша пишет на бумажках два любых различных натуральных числа по своему выбору. Одну бумажку она прячет в левую руку, а другую - в правую. Саша выбирает любую Машину руку. Маша показывает число, написанное на выбранной бумажке. Саша высказывает свою догадку о том, открыл ли он большее из двух чисел или меньшее. Если Саша не угадал, то Маша выиграла.

а) Докажите, что у Саши не существует чистой стратегии, гарантирующей ему выигрыш более чем в 50% случаев;

б) Перед выбором руки и высказыванием догадки Саша может обратиться к потомственной гадалке в пятом поколении Глафире Лукитичне1. Глафира Лукитична называет наугад (ничего не зная о Маше!) одно из натуральных чисел причем каждое число имеет положительную вероятность быть названным2. Другими словами, действия Саши (выбор левой или правой руки и высказываемая вергарантия, снятие порчи и сглаза без греха и ущерба для здоровья, исправляет некачественную работу шарлатанов 2 Ну например, Глафира Лукитична в курсе геометрического или Пуассоновского распределения сия) могут зависеть от слов гадалки. Какую стратегию Саше следует выбрать, чтобы гарантировать себе (вне зависимости от действий Маши!) вероятность выигрыша строго более 50%?

в) Докажите, что услуги Глафиры Лукитичны эквивалентны использованию некоторой смешанной стратегии г) Утешьте Машу - найдите инфинум по Машиным стратегиям вероятности Сашиного выигрыша.

Тигр: А! Вот в чем дело! А я думал, почему столько гадалок вокруг...

Задача 2.17.

В несколько раз больше! [Binmore, О] Васе предлагают две шкатулки. И обещают, что в одной из них денег в два раз больше, чем в другой. Вася открывает наугад одну из них - в ней рублей. Вася может либо взять деньги, либо взять оставшуюся шкатулку. а) Правильно ли Вася считает, что ожидаемое количество денег в неоткрытой шкатулке равно 1 1 + 2 (2) = 1 1, и, поэтому, нужно изменить свой выбор?

б) Пусть в пару шкатулок кладут 3 и 3+1 рублей с вероятностью = 2. Вася выбирает наугад одну из шкатулок. Стоит ли ему изменить свой выбор, после того, как он открыл первую? Почему?

3 Начнем с конца!

Задача 3.1.

«Забери камень»

В кучке лежит 45 камней. Вася и Петя забирают камни из кучки по очереди. За один ход можно взять два, три или четыре камня. Вася ходит первым. Почетное прозвище «Тамерлан» получает взявший последний камень. Если в кучке остался один камень (ход по правилам сделать невозможно), то игра оканчивается ничьей.

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

а) Классифицируйте эту игру: статическая или динамическая, с полной или неполной информацией, с совершенной или несовершенной информацией;

б) Конечны ли множества стратегий игроков?

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

г) Кто станет Тамерланом при правильной игре?

д) Кто станет Тамерланом, если это почетное прозвище получает игрок, не взявший последний камень?

Задача 3.2.

«Забери камень-2»

В первой кучке - 6 камней, во второй - 7 камней. За один ход можно взять два камня или пять камней из любой кучки.

а) Какой игрок выигрывает, первый или второй, если цель игры - сделать ход последним?

б) Какой игрок выигрывает, если цель игры - не сделать ход последним?

Задача 3.3.

Разные игроки В кучке 121 камень. Игроки ходят по очереди. Первый игрок за один ход может взять 1 или 3 камня, а второй - 2 или 3 камня. Проигрывает тот, кто не может сделать ход по правилам. Кто выигрывает при правильной игре?

Задача 3.4.

Добрые пираты Полный золота торговый корабль был захвачен 3 абсолютно рациональными пиратами!

У пиратов есть строгая иерархия: капитан, первый помощник капитана, второй помощник и т.д.

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

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

Какой дележ будет реализован (предположим, что золото бесконечно делимо)?

Источник: Мулен.

Задача 3.5.

Злые пираты Торговый корабль с 100 золотых монет был захвачен 500 абсолютно рациональными пиратами!

У пиратов есть строгая иерархия: капитан, первый помощник капитана, второй помощник и т.д.

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

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

Какой дележ будет реализован (предположим, что золотую монету не делят на меньшие части)?

Источник: http://euclid.trentu.ca/math/bz/pirates_gold.pdf.

Задача 3.6.

Скрытый Тамерлан Два игрока стоят на расстоянии 1111 шагов. Они по очереди делают шаги навстречу друг другу.

Вася может делать либо два, либо три шага, а Петя - либо три, либо четыре. Тот, кто первым не может сделать ход, проиграл. Начинает Вася.

Кто выигрывает при правильной игре?

Задача 3.7.

Разделяй и опустошай!

Есть две коробочки. В каждой из них лежит некоторое количество фишек. Игроки ходят по очереди.

За один ход игрок выбрасывает содержимое одной из коробочек, и затем делит содержимое другой между двумя коробочками (как минимум одна фишка должна оставаться в каждой коробочке).

Проигрывает тот, кто не может сделать ход по правилам. Найдите все выигрышные позиции.

Задача 3.8.

Четыреста лет назад В 1612 г. в Лионе появилась книга поэта и математика Баше де Мезирьяка (Bachet? de Meziriac) «Занимательные и приятные числовые задачи» (Problemes plaisants et delectables qui se font par les nombres). В ней была предложена следующая игра. Двое по очереди называют числа от 1 до 10, выигрывает тот, кто первым доведет сумму до 100. Кто выигрывает при правильной игре?

Задача 3.9.

Цзяньшинцзы «Выбирание камней»

Древний Китай. Две кучки камней. Игроки ходят по очереди. За один ход можно забрать либо произвольное число камней из одной кучки, либо одинаковое число камней из обеих. В одной кучке 5, а в другой - 8 камней. Кто выигрывает при правильной игре?

Задача 3.10.

«Одинокий ферзь»

Шахматная доска (а1 - слева внизу, h8 - вверху справа). Одинокий раненый ферзь стоит на h5.

Раненый ферзь может двигаться или влево, или вниз, или влево-вниз (на любое число клеток). Двое ходят раненым ферзем по очереди. Тот, кто переставит на а1 выиграл.

а) Кто выигрывает при правильной игре?

б) Найдите 10 отличий игры «Одинокий ферзь» от игры «Цзяньшинцзы»

Задача 3.11.

«Набери чет»

В кучке 135 камней, двое по очереди забирают себе от 1 до 4 камней. Выигрывает тот, кто к концу игры наберет четное число камней. Кто выигрывает при правильной игре?

Задача 3.12.

Развод [Брамс] Джон и Бэтти нужно поделить виллу, яхту, акции (Тигр: Контрольный пакет акций свечного заводика в Самаре) и машина. Они условились на следующей процедуре дележа: каждый забирает себе один предмет по очереди. Предпочтения выглядят так (в порядке убывания ценности):

Бэтти: яхта, вилла, акции, машина. Джон: вилла, акции, машина, яхта а) Найдите равновесие совершенное в подыграх, если очередность:

- Бэтти-Джон-Бэтти-Джон;

- Джон-Бэтти-Джон-Бэтти;

- Джон-Бэтти-Бэтти-Джон;

- Бэтти-Джон-Джон-Бэтти;

б) Изменим процедуру дележа. Джон и Бэтти одновременно называют предмет. Если их выборы различны, они получают то, что назвали; если нет, то предмет называется спорным и откладывается в особую кучу. Джон и Бэтти называют предметы до тех пор, пока остаются неподеленные предметы. Спорные предметы делят, как в предыдущем пункте, забирая по очереди. Найдите равновесия, совершенные в подыграх, для четырех вариантов очередности.

в) Во время дележа имущества Джон и Бэтти помирились, и решили культурно отдохнуть.

Предпочтения (снова в порядке убывания ценности).

Бэтти: театр, казино, бассейн, футбол. Джон: футбол, бассейн, казино, театр. Они по очереди вычеркивают нежелательную альтернативу, до тех пор, пока не останется только одна. Найдите равновесия по Нэшу, совершенные в подыграх, для четырех вариантов очередности.

Задача 3.13.

Рулетки [Binmore, О] Есть три рулетки: на первой равновероятно выпадают числа 2, 4 и 9; на второй - 1, 6 и 8; на третьей - 3, 5 и 7. Сначала первый игрок выбирает рулетку себе, затем второй игрок выбирает рулетку себе из двух оставшихся. После этого рулетки, выбранные игроками, запускаются, и случай определяет победителя. Победителем считается тот, чья рулетка покажет большее число. Победитель получает от проигравшего 100 рублей.

а) Нарисуйте дерево игры (можно со случайным ходом природы, можно и без - с усредненным выигрышем) б) Найдите совершенное в подыграх равновесие по Нэшу в) Каким игроком лучше быть в этой игре? Почему?

Тигр: сыр съедает вторая мышка?

Задача 3.14.

Рулетки [Binmore] Снова три рулетки, на этот раз с числами: 2, 4, 6 и 9; 1, 5, 6 и 8; 3, 4, 5 и 7. Игроки по очереди выбирают себе рулетки. Выигрывает, тот, чья рулетка покажет большее число. Если выпадает одинаковое число, то рулетки крутятся снова.

Найдите совершенное в подыграх равновесие по Нэшу Задача 3.15.

В игре два игрока. Сначала первый игрок выбирает R, затем второй игрок, зная выбор первого, выбирает R. Функции выигрыша имеют вид: = 2 + + 9, = 2 4 + 6 + 5.

а) Что представляет собой стратегия второго игрока?

б) Найдите равновесие по Нэшу, совершенное в подыграх;

в) Найдите хотя бы одно равновесие по Нэшу, не являющееся совершенным в подыграх.

Задача 3.16.

[Cheese-problem] В выборах участвуют человек. Каждый из них по очереди выбирает свою предвыборную позицию, число [0; 1], или отказывается от участия в выборах. Ноль означает крайне левую позицию, а единица - крайне правую. После того, как каждый выбрал свою позицию, определяется победитель (возможно несколько). Каждый избиратель выбирает того кандидата, ближе к которому он находится. Доля голосующих за кандидата определяется как длина отрезка его сторонников. Если несколько кандидатов заняли одинаковую позицию, то доля голосующих делится между ними поровну. Участие в выборах приводит к небольшим издержкам.

а) Найдите все равновесия по Нэшу, совершенные в подыграх, для = 2.

б) Попробуйте = 3 !

в) [Т] И, наконец, произвольное.

Тигр : первый решивший пункт «в» получит в приз головку сыра или 10 баллов по своему выбору.

Автор: вот такие сюрпризы есть у модели линейного города.

Задача 3.17.

Кортес [О] Кортес с бандой головорезов высадился на берегу. Кортес выбирает, нападать ли на деревушку или нет. Местная деревушка может либо сразу перейти в подчинение Кортеса, либо принять бой.

Если деревушка примет бой, то выбор появится у Кортеса: либо драться до победного конца, либо после первых потерь бежать на кораблях обратно. Ценность деревушки для Кортеса - одна единица, ценность собственных головорезов - 2 единицы. Если Кортес будет драться до конца, то деревушка будет взята, но большинство головорезов погибнет в бою. Для жителей деревушки - главное остаться в живых, сохранить при этом независимость, конечно, желательно.

а) Нарисуйте дерево игры и найдите обратно-индукционный исход.

б) Нарисуйте дерево игры и найдите обратно-индукционный исход в случае, если Кортес ограничил свои возможности - сжег корабли.

в) Объясните, почему ограничение собственных возможностей приводит к таким последствиям Задача 3.18.

Разборчивая невеста К принцессе случайным образом выстроилась очередь из женихов. Цель принцессы - выбрать самого богатого (даже второй по богатству жених королевства не устраивает принцессу). Женихи заходят по очереди. Когда заходит очередной претендент, принцесса узнает его годовой доход и должна либо выбрать его, либо перейти к следующему. Вернуться к предыдущему нельзя. Ничего про распределение доходов в королевстве неизвестно. Найдите - вероятность того, что принцесса выбрала самого богатого жениха, если известно, что она остановилась на -ом претенденте, доход которого был больше, чем у предыдущих претендентов. Обозначим - вероятность выигрыша принцессы в случае, если она пропускает первых женихов, а далее играет наилучшую стратегию.

Докажите, что не возрастает. Сравнив поведение и, ответьте на вопрос, какой вид имеет оптимальная стратегия. Как выглядит левее точки = ? Составьте разностное уравнение на правее точки =. Найдите lim 0 ( ). Тигр: Казалось бы, причем здесь ?

Казалось бы, причем здесь Березовский?

Задача 3.19.

«Лохотрон-2» [Martin Shubik] Несколько игроков участвуют в аукционе. По очереди они могут повышать последнюю названную цену на натуральное число рублей или отказываться от дальнейшей игры. Игра заканчивается, когда ни один игрок не хочет повышать цену. Приз ценностью рублей получает игрок предложивший наибольшую цену. Деньги платят два игрока: игрок назвавший наибольшую цену и игрок назвавший вторую по величине цену. У каждого игрока в распоряжении только рублей. Для однозначности предположим, что игрок предпочитает просто потерять рублей, нежели заплатить ( + ) рублей и выиграть рублей.

а) Найдите равновесие по Нэшу, совершенное в подыграх, для = 10, = 30 и = 2 ;

б) Найдите равновесие по Нэшу, совершенное в подыграх для произвольных, и Задача 3.20.

Добрая мама У мамы и у дочки есть в распоряжении суммы денег 100 и 10, соответственно. Дочка выбирает текущий объем потребления, все остальное она кладет в банк под ставку = 10% и получает деньги в следующем периоде. В следующем периоде расходы на потребление дочки складываются из ее сбережений и трансферта от ее мамы, размер которого определяет мама. Личная полезность дочери имеет вид = ln( ) + 0.7 · ln( · (1 + ) + ), где 0.7 - это дисконт фактор. Личная полезность мамы имеет вид: = (100 ) + ·, где > 0 - альтруистичность матери.

а) Найдите и, если решение о величине и мама и дочка принимают одновременно.

б) Являются ли найденные и Парето-оптимальными?

в) Найдите и, если сначала дочь принимает решение о значении, а затем, во втором периоде, мама, зная размер, выбирает.

г) Являются ли новые и Парето-оптимальными?

Hint: для проверки оптимальности можно рассмотреть градиенты полезностей Source: [3.11, Gintis] Задача 3.21.

Два игрока играют в теннис. Сейчас счет «ровно». Т.е. партия будет продолжаться до тех пор, пока один игрок не наберет отрыв в два очка. Победитель партии получит приз равный единице. При каждой подаче игроки одновременно выбирают уровень усилий. Если первый игрок выбрал уровень усилий 0, а второй игрок - уровень 0, то первый игрок выигрывает подачу с вероятностью. Уровень усилий вычитается из полезности игрока. Дисконтирование отсутствует.

а) Найдите оптимальные стратегии.

б) Обобщите игру на случай необходимости отрыва в очков Source: Lones Smith Задача 3.22.

Первоначально фишка расположена в узле А. Игроки по очереди могут двигать фишку на один ход в направлении, указанном стрелочкой. Тот, кто не сможет сделать очередной ход, проиграл. Кто выигрывает (первый или второй игрок) при правильной игре?

Задача 3.23.

Волшебная шкатулка- Количество денег в волшебной шкатулке постоянно увеличивается! Время дискретно. В момент времени {1; 2; 3;...; 100} там находится 2 · рублей. Каждый из двух игроков решает, когда ему потребовать деньги. Тот кто потребует деньги первым - получает сумму полностью, тот, кто потребует вторым - не получает ничего. Если требования поступают одновременно, то игроки делят сумму в шкатулке поровну. Если никто не потребует деньги к моменту = 100, то деньги сгорают. Найдите равновесия по Нэшу, совершенные в подыграх.

Источник: Osborne, 2.111.

Задача 3.24.

Счет в банке растет. В момент времени ( = 0, 1,..., ) его величина составляет 2 рублей. В каждый момент времени Муж и Жена независимо друг от друга выбирают, потребовать ли деньги, или нет. Если требует только один игрок, то он (она) забирает весь вклад. Если требуют оба, то вклад делится поровну. Если не потребовал никто, то начинается следующий период. Если никто так и не потребовал деньги к моменту, то каждый получает по рублей. Найдите SPNE.

Задача 3.25.

Тигры и волшебная антилопа На острове живут 99 тигров и одна вкусная волшебная антилопа.

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

Что будет происходить на этом острове?

Источник: forum on www.wilmott.com, brainteasers.

Задача 3.26.

Ребенок выбирает действие R+. Доходы ребенка и родителей определяются этим действием, обозначим их () и () соответственно. Далее родители определяют величину трансферта. Полезность ребенка определяется как () +, полезность родителей, как min{() +, () }, т.е.

родители заботятся и о доходе ребенка.

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

Задача 3.27.

Два мушкетера сражаются на шпагах за Прекрасную Даму. Лишний раунд означает издержки равные 1. Дисконт фактор равен. Полезность от Дамы равна > 1 для обоих претендентов. Если мушкетер решает покинуть поле боя в момент времени при условии, что его конкурент готов продолжить бой, то полезности равны:

= (1 + + 2 +... + 1 ) - для покидающего = (1 + + 2 +... + 1 ) + - для готового продолжить схватку Если оба решают покинуть поле боя одновременно, то каждый получает платеж (Прекрасную Даму нельзя ни делить пополам, ни дисконтировать!) а) Рассмотрим профиль стратегий, в котором первый игрок не вступает в бой, а другой никогда не покидает поле боя. Является ли он равновесием по Нэшу, совершенным в подыграх? Просто равновесием по Нэшу?

б) Найдите симметричное равновесие по Нэшу в смешанных стратегиях и проверьте, является ли оно совершенным в подыграх.

Коммент: Позвольте Вас отдисконтировать?

Коммент2: Зачем второму дама, если он никогда не покидает поле боя?

Задача 3.28.

Русская рулетка [Т] Два гусара, одна дама, одна пуля в шестизарядном револьвере...

Сначала первый гусар выбирает, отправиться ли ему в кабак (тогда он получит полезность ноль, а дама достанется другому) или приставить револьвер к виску и нажать на курок. Смерть означает полезность равную минус единице (при этом дама, естественно, достается другому). Если гусар остается жив, то право и обязанность выбора кабак/стреляться переходит ко второму. Барабан револьвера при этом не перекручивается, т.е. вероятность смерти увеличивается. Ценность дамы для одного гусара, для другого -.

а) Найдите равновесия в зависимости от и.

б) Каким игроком лучше быть, первым или вторым, в зависимости от и.

Тигр: Настоящего джентльмена, конечно, интересует настоящая дама, 1, Задача 3.29.

Народ и правительство [О], Il faut que j’y songe encore На первом шаге правительство обещает уровень инфляции в следующем году. Затем народ определяет свои ожидания инфляции.

Тигр: Что больше или ?

На третьем этапе правительство выбирает уровень инфляции. Функция полезности правительства = 2 ( )2, где - потенциальный уровень выпуска. Тигр: А я и не знал, что правительство такое благородное!

Совокупное предложение задано функцией = + ( ). Константы, и - положительные.

Найдите равновесие по Нэшу и платежи, получаемые игроками в следующих ситуациях:

а) Население верит правительству, а правительство не обязано исполнять свои обязательства.

б) Население верит правительству, а правительство исполняет свои обязательства.

в) Функция полезности населения имеет вид = ( )2, а правительство исполняет свои обязательства.

г) Функция полезности населения имеет вид = ( )2, а правительство не обязано исполнять свои обязательства.

д) Какой должна быть величина штрафа за неисполнение обязательств, чтобы в пункте г) правительство было заинтересовано в их исполнении?

е) Сравните выигрыш правительства в случаях «в» и «г». Обратите внимание на то, что в случае «в» у правительства нет возможности нарушать обещание, а в случае «г» такая возможность появляется.

Задача 3.30.

Триэль Три человека решили стреляться. Они одновременно делают выстрел, каждый сам выбирает, в кого целиться. Если после первого выстрела в живых осталось больше одного человека, то выжившие снова одновременно стреляют недруг в недруга. Триэль продолжается до тех пор, пока в живых не останется один человек или пока все не погибнут. Первый попадает с вероятностью 0,9, второй - с вероятностью 0,5, третий - с вероятностью 0,1.

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

б) Найдите вероятность победы каждого игрока.

в) Решите задачу, если игроки делают выстрелы не одновременно, а в последовательности первыйвторой-третий-первый-второй...

Задача 3.31.

Быть или не быть?

Докажите или опровергните следующие утверждения а) В игре с полной и совершенной информацией вычеркивание нестрого доминируемых стратегий может привести к потере равновесия совершенного в подыграх.

Задача 3.32.

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

а) Кто в кого будет стрелять? Чему будет равна вероятность погибнуть для каждого?

б) Изменится ли ответ, если стрелять в воздух нельзя?

в) Как изменится ответ, если вероятность попадания равна ?

г) Как изменится ответ, если патроны не ограничены?

Задача 3.33.

Налоговая инспекция (или преступная группировка) выбирает размер налога на объем продаж.

Фирма выбирает объем продаж. Выигрыш фирмы определяется по формуле = (1 ) 2, выигрыш налоговой инспекции =.

а) Определите выигрыши игроков, если они принимают решения одновременнно.

б) Определите выигрыши игроков, если сначала принимает решение налоговая инспекция, а затем фирма.

в) Найдите Парето-оптимальную точку. Прокомментируйте.

Источник: Коковин.

Задача 3.34.

Обратно-индукционный исход и доминирование стратегий Есть дерево игры с полной совершенной информацией. К нему применили обратно индукционный метод и получили множество обратно индукционных исходов. Затем это дерево перевели в матричную форму и оказалось, что последовательным вычеркиванием строго доминируемых стратегий можно оставить только один исход.

Возможно ли, что ? Возможно ли, что = ?

Задача 3.35.

Передача информации в модели Курно.

Две фирмы по очереди выбирают объемы производства. Вторая фирма при выборе своего объема производства не знает объема, выбранного первой фирмой. После того, как обе фирмы произвели товар, рынок определяет цены в соответствии с функцией спроса () = 1, где = 1 + 2.

а) Что представляет собой стратегия второй фирмы? Найдите равновесие по Нэшу. Совпадает ли оно с равновесием по Нэшу совершенным в подыграх?

б) Предположим теперь, что первая фирма честно декларирует выбранный ею объем выпуска. Что представляет собой стратегия второй фирмы? Найдите равновесие по Нэшу, совершенное в подыграх.

Будут ли другие равновесия по Нэшу?

в) Сравните платежи второй фирмы в обоих вариантах модели. Почему наличие дополнительной информации снижает платеж второй фирмы? Почему не корректно рассуждение «Полученную информацию можно не учитывать, поэтому платеж не может упасть»?

Задача 3.36.

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

Тигр автору: Вы уверены, что он рациональный?

Второй игрок наблюдает действия первого, а затем игроки играют в одновременную игру:

а) Найдите все равновесия по Нэшу в одновременной игре;

б) Сформулируйте все стратегии игроков для игры в целом;

в) Найдите все равновесия по Нэшу;

г) Верно ли, что среди равновесий совершенных в подыграх будет равновесие, в котором первый игрок сжигает деньги?

Задача 3.37.

Обещания Сначала первый игрок выбирает, будет ли он правдиво декларировать свой будущий ход или не будет обещать ничего. После правдивой декларации или ее отсутствия первый и второй игроки играют в одновременную игру:

а) Найдите все равновесия по Нэшу в одновременной игре;

б) Сформулируйте все стратегии игроков для игры в целом;

в) Найдите все равновесия по Нэшу;

г) Найдите все равновесия, совершенные в подыграх Задача 3.38.

Две сверхдержавы Две сверхдержавы играют в одновременную игру и выбирают, нажимать ли красную кнопку запуска стратегических ядерных ракет, или нет. Тигр: Они доиграются... Матрица игры имеет вид:

а) Найдите все равновесия по Нэшу в этой игре;

б) Допустим, обе сверхдержавы создали системы раннего обнаружения запуска ядерных ракет. Если одна из сверхдержав не запустила ракеты, а другая - запустила, у незапустившей появляется возможность изменить свою решение. Отменить запуск по-прежнему нельзя. Найдите равновесия по Нэшу совершенные в подыграх в измененной игре;

в) Найдите равновесие в случае, если систему раннего обнаружения использует только одна из стран;

Задача 3.39.

Построить пример игры в развернутой и/или в нормальной форме, где или доказать, что это невозможно.

Источник: БЗИ, НГУ.

Задача 3.40.

Пираты. (Мулен, 1985,p.-85). Пусть на пиратском корабле 50 разного старшинства пиратов делят 100 кусков золота по следующему обычаю. Старший предлагает дележ – кому сколько. Если хотя бы половина команды (включая его) согласна, то так и будет, иначе его выбросят за борт, а оставшийся старшим предложит дележ, и так далее.

Предскажите, кто сколько получит, вплоть до младшего юнги (SPE, INDW).

Источник: БЗИ, НГУ.

Задача 3.41.

Камешки. Пусть Анна и Борис договорились, что из лежащих перед ними 10 камушков Анна возьмет 1 или 2, по желанию. Потом Борис 1 или 2, и так далее, а взявший последний камень проиграл.

Кто выиграет при идеальной игре обоих? Сохранится ли результат, если можно брать 1 или 2 или 3? Каков общий метод решения всех таких задач?

Источник: БЗИ, НГУ.

Задача 3.42.

Вариант игры Баше. В игре участвуют двое, ходя по очереди (первый, второй, первый и т. д.).

На столе лежит камней. В свой ход каждый из участников может изъять 2 камней ( = 0, 1, 2,...;

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

1. Пользуясь принципом Цермело, определите выигрышные и проигрышные позиции в игре. Для этого, например, можно исследовать несколько первых позиций и угадать закономерность. Обязательно обоснуйте свой ответ.

2. Опишите выигрышную стратегию игрока (в случае, если она у него есть). Когда выигрывает первый, а когда второй? Может ли быть ничья?

3. Пусть = 50 и Вам ходить. Ваши действия?

Источник: БЗИ, NES.

Задача 3.43.

Снова два участника ходят по очереди. Теперь на столе уже две кучки камней Вариант игры Ним.

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

Как и раньше, выигрывает тот, кто своим ходом оставляет пустой стол.

1. Опишите процесс последовательного определения выигрышных и проигрышных позиций в этой игре. Найдите выигрышные стратегии для малых и .

2. Пусть = 15, = 7 и Ваш ход. Как надо сыграть?

3. Тот же вопрос, если = 8 и = 13.

Источник: БЗИ, NES.

Задача 3.44.

Русская рулетка. Два офицера русской армии повздорили из-за одной барышни. Порешили так:

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

1. Формализуйте этот конфликт как игру с совершенной информацией, т. е., без информационных множеств. При этом считайте, что застрелившийся получает полезность 1, спасовавший — 0, а выигравший — соответственно, или, т. е. участники по-разному оценивают качества будущей спутницы жизни. Предполагается, что > 0 и > 0.

2. Решите игру по доминированию, используя алгоритм Цермело — Куна. Какими будут равновесные стратегии в зависимости от параметров и ? Удобно дать ответ в виде диаграммы в координатах (, ), на которой указаны соответствующие области. Граничные случаи (когда кому-то все равно, как действовать) рассматривать не надо.

Источник: БЗИ, NES.

Задача 3.45.

Когда алгоритм Цермело работает плохо.

в игре Не забыли про смеси?

Источник: БЗИ, NES.

Задача 3.46.

ных благ (например, запас продуктов питания в походе), который может потребляться периодов.

Полезность от разового потребления единиц продукта составляет. Индивидуум ценит будущее потребление наравне с настоящим, т. е. дисконтирование отсутствует. Как известно, в этом случае он стремится разделить продукт поровну между периодами.

Предположим теперь, что участников два, а не один, и потребляют они из одного запаса. В каждом периоде потребление происходит одновременно, т. е. игроки независимо выбирают, сколько съесть (но не более половины от имеющегося).

1. Представьте это в виде игры в развернутой форме. Как устроено дерево?

2. Как бы вы искали совершенное по подыграм равновесие в этой игре? Указание: изобретите что-нибудь типа функций Беллмана, найдите равновесные стратегии потребления и выведите рекуррентные соотношения на параметры. Является ли равновесие оптимальным по Парето?

3. Пусть = 3 и вначале имеется 290 единиц продукта. Какими будут равновесные траектории потребления?

Источник: БЗИ, NES.

Задача 3.47.

Делим пирог. Рассмотрим две модели “справедливой” дележки пирога между двумя соискателями.

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

2. Один режет пирог на две части и пишет на них “1” и “2”. Другой в это время, отвернувшись, говорит, какую часть ему выдать. Описать развернутую и нормальную форму. Как Вы думаете, может ли произойти неравный раздел? Как-нибудь обоснуйте свой ответ.

Источник: БЗИ.

Задача 3.48.

Крестики и нолики. Рассматривается игра в обычные “крестики-нолики” (3 3). Все ли знают ее правила? Для нас сейчас неважно, кто и когда в ней выигрывает, нас интересуют лишь различные формы, в которых может быть представлена игра. Для простоты можете считать, что терминальными позициями являются только те, в которых все 9 клеток заполнены, т. е. игра продолжается даже если уже ясно, кто выиграл.

1. Сколько позиций имеет игра, иными словами, сколько существует расстановок крестиков и ноликов, которые могут возникнуть по ходу игры (и в ее конце)?

2. Сколько вершин в дереве игры (в развернутой форме)? Сравните с п. 1.

3. Подсчитайте, хотя бы приблизительно, сколько стратегий имеется у каждого участника в каждом из рассмотренных представлений игры (см. пп. 1 и 2).

Источник: БЗИ.

Задача 3.49.

Захват рынка. Две фирмы и производят некоторый товар. В каждый момент времени = 1,..., 5 каждая фирма может произвести единицу товара либо ничего не производить. Затраты на производство равны 3, а цена продажи определяется числом активных фирм на рынке и составляет 6 2.

1. Опишите развернутую форму этой игры, стратегии участников и функции выигрыша. Сколько стратегий у каждой фирмы?

2. Те же вопросы, если, однажды выйдя с рынка, фирма уже не может вернуться.

Источник: БЗИ.

Задача 3.50.

Рабочий и управляющий.

работает, он теряет 1, а управляющий получает 3. Иначе рабочий ничего не теряет а управляющий теряет 1. Управляющий назначает рабочему зарплату.

1. Пусть рабочий и управляющий принимают свои решения одновременно. Нарисовать развернутую и нормальную форму. Внимание: правильно понять и формализовать игру — входит в задание!

2. Тот же вопрос для случая, когда рабочему известно, сколько ему будут платить. Как Вы думаете, чем кончится игра и кто сколько выиграет?

Источник: БЗИ.

Задача 3.51.

Веревки Одиссея: “commitment”, мультиперсонное представление, иррациональность. Одиссей подплывая на корабле к острову Сирен, хотел послушать их сладкое пение, но знал, что всякий слушающий бросается в воду, плывет к ним и не возвращается. Этого он не хотел. Он приказал матросам залепить уши воском, а его самого привязать к мачте. Так он услышал Сирен, но остался капитаном.

Составить игру, годящуюся для объяснения этой ситуации.

Источник: БЗИ.

Задача 3.52.

ема) вида ( ) = 9 и монополистом - старожилом в этой отрасли, с постоянными предельными издержками 1 (1 ) = 1 (проверьте, что монопольная цена = 5). Пусть потенциальный новичок входя в отрасль должен сделать невозвратные начальные капиталовложения = 1 и ожидает предельные издержки 2 (2 ) = 2. Пусть отрасль может просуществовать два периода (можно обобщить на ) и дисконта нет: прибыли сегодня и завтра равноценны, альтернативное вложение капитала невозможно. Старожил обещает новичку в случае входа добиться (повышением выпуска) снижения цены достаточно низко (< 2), чтобы заставить новичка прекратить производство, предполагая, что после этого новичок банкрот и во втором периоде можно сохранять монополию. Если же новичок войдет, то ожидается решение Штакельберга (т.е. SPE, ): лидер- страрожил установит выпуск раньше. Стоит ли верить этой угрозе или он блефует и можно входить? Обобщите задачу для различных 2 (2 ) = 2, = 1.

Источник: БЗИ, НГУ.

Задача 3.53.

Игра “Возьми или оставь” (“сороконожка” - повтор):

Пусть первый из двух игроков (Анна) может взять 4/5 общей прибыли (то есть $4 из $5 на ветви 1 ) на шаге 1, тогда игра закончится, а второму - Виктору - останется $1. Либо можно оставить банк на столе (1 ). На шаге 2 прибыль удваивается (например, ведущим), и черед 2-го выбирать:

взять ли 4/5 прибыли (то есть $8 из $10-и) и закончить тем самым игру, или оставить, и т.д. Предсказывая исход для конечной (скажем, по 3 хода каждого) игры по принципу SPE, PBE, или THPE мы увидим, что игра тривиально закончится на 1-м шаге 1 с выигрышами (1,4). А по принципу решения () она может дойти до конца с большой суммой прибыли. (Здесь – вероятность не ниже которой ожидается от любого хода, благодаря случайному поведению типа иррациональности).

Покажите, что > 1/7 достаточно для продолжения игры до конца (точнее, продолжения рациональных ходов до узла 3 ). Какое необходимо для этого же?

2)Пусть, ситуация изменилась: игрок Victor слышал, что Анна в подобной игре из 10-ти ходов сделала 1 иррациональный (невыгодный, ошибочный), и ожидает, соответственно, вероятность иррациональности около = 1/10. Аналогично, Анна слышала, что Виктор в подобной игре из 30-ти ходов сделал 2 иррациональных хода, она ожидает вероятность иррациональности = 2/30 (это окажется не то же, что 1/15!). Предположим, игроки считают рациональным брать банк, когда вероятность ошибки партнера больше 1/7 и ожидают от партнера такого же мнения. Очевидно, при такой “простоватой” рациональности, Анна на первом ходу ВОЗЬМЕТ (если не ошибется). Но если он ошибется, возьмет ли Виктор? Он может интерпретировать оставление Анной как ошибку, и тогда подправить свою субъективную вероятность ошибок А до величины (1+1)/(10+1)=2/11. Либо считать случившееся оставление рациональным ходом, и сделать отсюда вывод о текущих гипотезах ( =?) Анны относительно себя (Виктора). Независимо от того, верны ли эти гипотезы, выгодно ли теперь Виктору оставлять и пойдет ли игра до узла 3 ?

3)По сравнению с предыдущей ситуацией, оставим Виктора “простым”, а первого игрока предположим способным рассчитать предыдущую ситуацию. Станет ли он на первом шаге ОСТАВЛЯТЬ, независимо от своих гипотез о партнере (БЛЕФОВАТЬ)? Пойдет ли игра до 6-го хода?

4)Что если теперь оба игрока “сложные”, и В просчитывает возможность блефа первого (считающего второго простым), изменит ли это результат?

Источник: БЗИ, НГУ.

Задача 3.54.

В задаче "террорист"из учебника, рассмотрим, как выглядит SPE в более сложном случае: при совпадении некоторых значений выигрышей и/или при несовершенной информации о ходах. Случай “С"описанной игры возможен, если террорист — психически особенный человек (что с ними бывает):

ему все равно, жить или нет, но приятнее умереть или жить на Кубе. Тогда возникает много равновесий (все стратегии), но ни одного, поскольку множество IND итерационно (слабо) недоминируемых стратегий включает неэквивалентные исходы: = {(, ) (2, 1); (, ) (0, 1)}.

(здесь должна быть картинка но тех не ест вербатим) В случае “D"выигрыши различны, но неинформированность террориста позволяет ожидать от него любых ходов. В результате много равновесий (все стратегии), но ни одного, поскольку множество IND итерационно (слабо) недоминируемых стратегий включает неэквивалентные исходы:

Источник: БЗИ, НГУ.

Задача 3.55.

Вариация на тему игры Баше. В игре участвуют двое, ходя по очереди (первый, второй, первый,...).

На столе лежит камней. В свой ход каждый из участников может взять либо столько же камней, сколько было взято его партнером на предыдущем ходу, либо на один больше. На первом ходу можно брать один или два камня. Кто не может продолжать игру по правилам (из-за недостатка камней), тот проиграл.

Опишите процесс последовательного определения выигрышных и проигрышных позиций в этой игре. Найдите выигрышные стратегии для малых.

Пусть = 14 и ваш ход. Как надо играть?

Тот же вопрос, если = 18.

Замечание. В данной задаче авторам неизвестно короткое доказательство для расположения выигрышных и проигрышных позиций при произвольном. Восполните пробел!

Источник: НМУ, экзамен 2004, Леша Савватеев.

Задача 3.56.

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

Пользуясь принципом Цермело, определите выигрышные и проигрышные позиции в игре. Для этого, например, можно исследовать несколько первых позиций и угадать закономерность. Обязательно обоснуйте свой ответ.

Опишите выигрышную стратегию игрока (в случае, если она у него есть). Когда выигрывает первый, а когда второй?

Пусть = 98, = 100 и вам ходить. Ваши действия?

Источник: НМУ, экзамен 2004, Леша Савватеев.

Задача 3.57.

Дуэль. Трое захотели в жёны одну и ту же девушку. Решили драться на дуэли. Дуэль протекает так: каждый период времени каждый из дуэлянтов выбирает, стрелять ли в воздух, либо в одного из своих соперников (т.е. 3 стратегии у каждого). Первый промахивается с вероятностью, второй — с вероятностью, третий — с вероятностью. Если после пальбы остался в живых более, чем один человек, то дуэль продолжается. Падший мёртвым получает 0, единственный живой — 1. Найдите равновесие, совершенное на подыграх. Может ли быть задача разрешена по доминированию? При каких значениях параметров? (Это очень громоздкая и сложная задача. Частичные решения будут частично оценены, конечно.) Источник: НМУ, экзамен 2004, Леша Савватеев.

Задача 3.58.

Вариация на тему игры с гранатой а) Укажите, сколько стратегий у каждого игрока;

б) Приведите пример профиля стратегий, приводящего к игре, и.

в) Переведите игру в матричную форму;

г) Найдите равновесия по Нэшу;

д) Укажите, какие из найденных равновесий по Нэшу являются совершенными в подыграх.

Задача 3.59.

В саду растут четыре дерева:

(3;2) (-1;-1) Найдите все равновесия по Нэшу;

Найдите все равновесия по Нэшу, совершенные в подыграх;

Задача 3.60.

Меньше подыгр - легче считать!

а) Укажите, сколько стратегий у каждого игрока;

б) Переведите игру в матричную форму;

в) Найдите равновесия по Нэшу;

г) Укажите, какие из найденных равновесий по Нэшу являются совершенными в подыграх.

3.1 Доллар Рубинштейна Задача 3.61.

Равновесия по Нэшу в модели Рубинштейна Саша и Маша делят доллар по Рубинштейну. Т.е. сначала Маша предлагает свой вариант дележа, затем Саша соглашается или нет, если он не соглашается, то предлагает свой вариант и т.д. Доллар можно поделить в любой пропорции.

а) Приведите примеры равновесий по Нэшу, в которых:

- Маша предлагает поделить доллар поровну на первом шаге, а Саша соглашается - Маша предлагает весь доллар Саше на первом шаге, а Саша соглашается.

- Игра оканчивается на втором шаге б) Какие из Ваших примеров являются равновесиями, совершенными в подыграх?

Задача 3.62.

Делим неделимый доллар! [Binmore, О] Рассмотрите модель Рубинштейна с неделимым долларом (дисконт факторы игроков могут быть различными). Теперь либо весь доллар достается Саше (второму игроку), либо весь - Маше.

а) Постройте примеры совершенных подыгровых равновесий по Нэшу, в которых:

- Доллар достается Маше на первом шаге - Доллар достается Саше на первом шаге - Доллар достается Саше на втором шаге Задача 3.63.

Делим чуть-чуть делимый доллар Рассмотрите модель Рубинштейна, в которой доллар можно поделить только в пропорциях (1 : 0), (0 : 1), (0, 7 : 0, 3) и (0, 4 : 0, 6).

Постройте примеры совершенных подыгровых равновесий по Нэшу, в которых:

- Доллар будет поделен в соотношении (0, 7 : 0, 3) на первом шаге - Доллар будет поделен в соотношении (0, 4 : 0, 6) на первом шаге - Доллар будет поделен в соотношении (0, 7 : 0, 3) на втором шаге Задача 3.64.

[LSE, 1998] Саша и Маша делят доллар Рубинштейна. Сначала вариант дележа предлагает Саша, если Маша не согласна, то предлагает она. Если и Саша не одобряет машин дележ, то оба игрока получают нулевые платежи. Маша нетерпелива, ее дисконт фактор равен 2. а) Найдите равновесие по Нэшу, совершенное в подыграх;

б) Найдите все равновесия по Нэшу;

в) Решите задачу в предположении, что на своем ходе Маша не может запросить себе долю больше той, что Саша запросил себе на первом ходе.

Задача 3.65.

Рассмотрите следующий вариант модели Рубинштейна.

У обоих игроков одинаковый дисконт-фактор. Число периодов неограничено. Если игрок соглашается с предлагаемым дележом, то игра окончена. Если игрок не соглашается с предлагаемым дележом, то с вероятностью 1 > > 0 игра оканчивается и никто не получает ничего, а с вероятностью (1 ) - продолжается.

Найдите равновесие по Нэшу, совершенное в подыграх Задача 3.66.

[SPE в непрерывной игре: Дележ убывающего пирога].

(A.Rubinstein, 1959, see also H.Varian “Microec.Analysis").

Уезжая из дома, мать оставила двум жадным сыновьям пирог, с таким условием. Сначала Андрей предложит дележ Борис предложит дележ 2 [0, 1] (свою долю). Если Андрей не согласен, он через час предложит новый дележ 3 [0, 1], и так далее. Но с каждым часом полезность пирога убывает (возможно, от нетерпения и от засыхания пирога) некоторым темпом, то есть через час остается (0, 1) для Андрея и (0, 1) для Бориса. То есть, если, скажем, на третьей итерации они согласились на дележ (3, 3 ); 3 +3 = 1, то полезность Андрея от него будет (3 ) = 3, Бориса — (3 ) = 3.

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

Для простоты будем считать этой непрерывной по стратегиям игры:

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

Упражнение. Предположите, что дисконты (“кофициенты терпения") Андрея и Бориса разные, как и в чью пользу (терпеливого ли) изменится решение? Обобщите решение для произвольнапример, переходом к пределу. (Проверьте ного числа периодов Т, и для бесконечного Источник: БЗИ, НГУ.

Задача 3.67.

Модель Рубинштейна. Мама испекла пирог, и оставила его в духовке своим двум сыновьям. Потом она ушла в магазин на 3 часа, и наказала: каждые полчаса, начиная с момента закрытия за ней двери, пытаться делить пирог по принципу «один делит, другой одобряет». Если не одобряет, то пирог полчаса остывает в печи, а потом снова. Начинает предлагать старший сын, затем — по очереди.

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

Найти равновесие, совершенное на подыграх;

Что, если мама ушла навсегда?

Источник: НМУ, экзамен 2004, Леша Савватеев.

4 За обратной индукцией. Комбинаторные игры Задача 4.1.

Функция Шпрага-Гранди (Sprague-Grundy function, Nim-value) Автор: Эта большая задача предназначена для тех, кто хочет познакомиться с комбинаторной теорией игр.

Тигр: И для тех, кто хочет научиться быстро находить выигрышную позицию с помощью заклинания Шпрага-Гранди.

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

В комбинаторной игре с обычными правилами выигрывает игрок сделавший последний ход. В комбинаторных «поддавках» игрок, сделавший последний ход, проигрывает.

Назовем схемой игры ориентированный граф, необязательно дерево, где узлы изображают возможные позиции в игре, а ребра поясняют из какой позиции в какую можно попасть. Схема игры не совпадает с деревом игры! Схема игры в отличие от дерева не сохраняет путь, которым игроки попали в заданную позицию! а) Пусть у одного из игроков есть выигрышная стратегия (стратегия - это предписание, какой делать в зависимости от того, какие ходы были сделаны до этого). Докажите, что у него есть выигрышная стратегия, которая является функцией только от текущей позиции, и не учитывает того, каким путем она была достигнута.

Назовем -позицией, позицию выигрышную для игрока, чей ход предшествовал этой позиции (Previous player). Назовем -позицией, позицию выигрышную для игрока, который ходит из этой позиции (Next player).

б) В кучке лежит 10 камней. За один ход можно забрать 1 или 3 камня. Изобразите схему игры.

Найдите -позиции и -позиции.

в) Докажите, что при обычных правилах в комбинаторной игре верно три утверждения.

Любая терминальная позиция является -позицией. Любая позиция предшествующая -позиции является -позицией.

Любая позиция следующая за -позицией является -позицией.

Итак, магическое заклинание! Фунция Шпрага-Гранди! ()!

В конечной игре функция Шпрага-Гранди присваивает каждому узлу целое неотрицательное число.

Всем терминальным узлам присваивается ноль. Если у всех позиций, следующих за позицией, функция уже посчитана, то значение функции в позиции равно минимальному целому числу не равному последующим значениям. Например, за следуют четыре позиции, на которых функция Шпрага-Гранди равна 0; 1; 2 и 5 соответственно. Значит () = 3. Формально, если () - множество узлов, следующих за узлом, то () = min { N {0} : () = ()}. г) Посчитайте функцию Шпрага-Гранди для пункта «б»;

д) Докажите, что функция Шпрага-Гранди равна нулю в -позициях и отлична от нуля в позициях. В доказательстве можно воспользоваться результатами пункта «в»;

е) Верно ли, что любой ход из -позиции уменьшает функцию Шпрага-Гранди?

ж) Верно ли, что в любой -позиции существует такой ход, который понижает функцию ШпрагаГранди на любое возможное натуральное число?

Если есть несколько комбинаторных игр, то их можно сложить!

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

е) Пример игры-суммы. Имеется три кучки - по 5, 7 и 9 камней. Из первой можно брать 1 или камня, из второй - 2 или 3 камня, из третьей - 3 или 4 камня. За один ход камни можно брать только из одной кучки. Игроки ходят по очереди. Данная игра является суммой трех игр. Догадайтесь каких! Для каждой из игр слагаемых рассчитайте функцию Шпрага-Гранди.

Функция означает «исключающее или» в двоичной записи. Пример:

ж) Вычислите 17 9, 6 5 и 7 19 Позиция в игре-сумме определяется позицией в каждой из игр-слагаемых.

Теорема Шпрага-Гранди В игре-сумме функция Шпрага-Гранди однозначно определяется функциями Шпрага-Гранди игр-слагаемых по правилу: (1, 2,..., ) = 1 (1 ) 2 (2 )... ( ). з) Пользуясь теоремой и зная значения функции Шпрага-Гранди в играх-слагаемых, найдите значение функции Шпрага-Гранди в игре из пункта «е»; Отлично ли оно от нуля? Кто выигрывает, первый или второй игрок?

и) Найдите выигрышный ход! Воспользуйтесь тем, что выигрышный ход должен переводить позицию в -позицию, т.е. обнулять значение функции Шпрага-Гранди.

Задача 4.2.

Доказательство теоремы Шпрага-Гранди [Т] Теорема:

В игре-сумме функция Шпрага-Гранди однозначно определяется функциями Шпрага-Гранди игрслагаемых по правилу: (1, 2,..., ) = 1 (1 ) 2 (2 )... ( ). Доказательство:

Пусть (.) - функция в игре-сумме, определяемая согласно теореме. а) Докажите, что в терминальных узлах игры-суммы функция () действительно равна нулю. Пусть - некая позиция в игре-сумме, т.е. = (1, 2,..., ) и () =. Рассмотрим произвольное число <. Нужно доказать, что за позицией существует позиция, такая что ( ) =. Так как <, то двоичная запись этих чисел различна. Пусть первое различие в двоичной записи находится на -ом месте.

б) Рассмотрите число =. Что там находится на -ом месте? Какова длина двоичной записи этого числа? Чему равно ? в) По определению = 1 (1 ) 2 (2 )... ( ). Так как на -ом месте в числе содержится 1, то существует такая игра, что ( ) в двоичной записи содержит 1 на -ом месте. Для простоты пусть = 1. Докажите, что 1 (1 ) < 1 (1 ).

Следовательно, в этой игре существует ход, переводящий позицию 1 в 1, что 1 (1 ) = 1 (1 ). г) Тогда (1, 2,..., ) = 1 (1 ) 2 (2 )... ( ) =... =... =. Заполните пропуск.

Т.е. у любой позиции есть следующая с любым меньшим значением функции (.).

д) Докажите самостоятельно, что ни у одной позиции нет следующей с таким же значением функции (.).

Теорема доказана!

Тигр: Во многих последующих задачах этого раздела шаманам придется потрясти бубном и произнести заклинания Шпрага-Гранди!

Задача 4.3.

Ним Ласкера Решите задачу, предложенную Эммануилом Ласкером, чемпионом мира по шахматам с 1894 по 1921, в книге Brettspiele der Volker (1931). Тигр: Не будем смешивать шахматы и теорию игр!

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

а) Постройте функцию Шпрага-Гранди для одной кучки из камней;

б) Определите выигрышный ход в ситуации с тремя кучками из 2, 5 и 7 камней.

Задача 4.4.

Очень простая задача?

Есть кучка из камней. За ход ее можно разделить на две непустые кучки. Проигрывает тот, кто не может сделать ход.

а) Кто выигрывает при правильной игре в зависимости от ?

б) Является ли в этой игре функция Шпрага-Гранди периодической?

Тигр: Осенью 2004 года эта задача была по ошибке объявлена очень трудной (якобы ее решение вообще не было известно), было обещано 10 баллов за ее решение. Никто даже не попытался...

в) Попытайтесь ответить на вопросы «а» и «б» если делить можно на две непустые неравные кучки;

Автор: Именно решение пункта «в» неизвестно ни одному из нескольких миллиардов жителей планеты Земля...

Задача 4.5.

Rayles На плоскости нарисованы точки. За один ход разрешается провести замкнутую кривую проходящую через одну или две из отмеченных точек, но не пересекающую и не касающуюся уже проведенных кривых. Проигрывает тот, кто не может сделать ход.

а) Докажите, что эта игра эквивалентна игре с кучками камней по правилам: За один ход можно брать из кучки один или два камня, и, при желании, разделять ее на две кучки.

б) Определите правильный ход в ситуации:

Задача 4.6.

Похоже на Ним Ласкера!

На плоскости нарисовано точек. За один ход разрешается провести замкнутую кривую, проходящую через несколько отмеченных точек, но не пересекающую и не касающуюся уже проведенных кривых. Проигрывает тот, кто не может сделать ход.

Кто выигрывает на рисунке задачи Rayles? Если первый игрок, то определите выигрышный ход.

Задача 4.7.

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

а) Кто выигрывает, если имеется две кучи из 11 и 22 камней?

б) Кто выигрывает, если имеется 5 куч камней из 6, 7, 8, 9 и 10 камней?

в) Докажите что любая сумма конечных комбинаторных игр - это Ним с определенным количеством кучек!!! Количество кучек равно количеству слагаемых. Чему соответствует количество камней в кучках?

Задача 4.8.

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

а) Докажите, что данная игра эквивалентна игре Ним (см. задачу 1.13.), где кучкам камней соответствуют ступеньки с нечетными номерами. Тигр: А что, четные вообще никак не влияют?!

Игра «Ним», вероятно, появилась в Китае, однако название считается немецким (от глагола nimm - «брать»).

Первое европейское упоминание относится к 15 веку.

б) Кто выигрывает в позиции [6, 7, 5, 0, 4, 1]? (На первой ступеньке лежит 6 камней, на второй - камней и т.д.) в) Кто выигрывает в позиции [1, 0, 0, 2, 4, 0, 5]?

Задача 4.9.

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

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

Кто выигрывает в этой игре?

Тигр: Спонсор задачи РосАгроПром!

5 Разработка механизмов Задача 5.1.

Система наказаний [Game theory at work] На маленькой фирме работает 10 человек. Каждый из них может работать либо старательно, либо «спустя рукава». Ни один работник не хотел бы быть уволенным. Работодатель видит качество работы каждого сотрудника и заинтересован в том, чтобы все работали старательно. Проблема заключается в том, что уволить можно не более чем одного сотрудника. Этот факт прекрасно известен работникам, они понимают, что если все будут плохо работать, то уволят только одного. Как построить систему угроз увольнений, чтобы каждый работал старательно?

Задача 5.2.

О Попе и работнике его Балде Поп нанял Балду, чтобы тот предсказал ему погоду. Дождь будет с вероятностью. Благодаря народным приметам Балда точно знает. Поп величину не знает. Балда выдает Попу свою оценку вероятности дождя завтра.

а) Как будет вести себя Балда, если Поп выплачивает ему награждение по принципу: если дождь действительно был, то выплачивается, если дождя не было, то 1 ?

б) Поп решил заставить Балду выдавать точные оценки. В случае дождя Поп платит (), и (1 ) в случае сухой погоды. Какую следует выбрать Попу?

Подсказка: при решении задачи Поп столкнется со странным дифференциальным уравнением, у которого много решений, но 9-ти классов церковно-приходской школы ему вполне должно хватить для подбора частного решения Задача 5.3.

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

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

Какую зарплату в результате получит хитрый король и сколько голосований ему потребуется?

Задача 5.4.

3 people in a room would like to find out what is the average of their salaries, without disclosing their individual salaries to each other. Найдите способ это сделать.

Задача 5.5.

Покер в чате Трое заядлых игроков в покер сидят в чате. Предложите процедуру раздачи карт, при которой каждый игрок знает свои карты и не знает карт соперника. Игроки абсолютно рациональны и обладают безграничными вычислительными возможностями, поэтому использование кодов с открытым ключом (типа RSA) недопустимо. В чате можно посылать сообщения, адресованные как всем сразу, так и конкретному лицу.

Задача 5.6.

Пираты делят золото[10] Есть золотой песок и три пирата, но нет весов.

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

Предложите конечную процедуру справедливого дележа, при которой у пиратов не было бы зависти (каждый считал бы, что его часть не меньше, чем у других). Задача 5.7.

Есть три брата и куча рутинной работы по дому, определенная мамой. Здесь работа - антиблаго.

Придумайте процедуру дележа, при которой ни один брат не завидовал бы ни одному другому.

Зависть появляется, если брат считает, что у другого работы меньше, чем у него самого.

Уточнения:

Мнения братьев субъективны (т.е. даже дележ, где каждый получает ровно по одной третьей работы, может вызывать зависть у каждого брата). Мнения братьев рациональны (часть меньше целого, транзитивность).

Каждый брат умеет: а) делить работу на любое количество равных (по своему мнению) частей, б) сравнивать объемы работ (по своему мнению), в) при наличии двух неравных объемов работ - от большего объема работ отделять часть так, чтобы он сравнялся с меньшим[12].

Задача 5.8.

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

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

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

Источник: Макс Петроневич.

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

Примо Леви «Воспоминания смертника» пишет, что именно так делились пайки хлеба в концентрационном лагере «Аушвиц» в Польше во время Второй Мировой войны.

Гесиод в книге «Теогония» (700 лет до н.э.) описывает именно такой способ деления куска мяса между Прометеем и Зевсом (Прометей делил, Зевс выбирал).

Тигр: А у нас верхняя палата вносит законопроект, потом нижняя голосует, какой ей больше нравится...

Кодекс поведения пиратов обычно включал принцип «нет жертвы - нет платы». Заранее оговаривались доли, которые получал каждый член команды.

Сначала оплачивали работу хирурга (200-250 песо), корабельного плотника (100-150 песо), компенсации за увечья (600 песо за потерю правой руки, 500 - за потерю левой руки или правой ноги, 400 - за левую ногу и 100 - за глаз или палец). Остальное делилось на равные доли, причем капитан получал 5-6 долей, помощник - 2 доли, рядовые члены команды - по одной доли, юнга - половину доли.

Попытки присвоить сверх своей доли строго карались[4].

6 Повторяемые игры - Доктор, доктор, мы его потеряли!!!

- Ну, не надо так переживать, у нас их еще целая палата.

Задача 6.1.

Достижимые платежи Матрица базовой игры имеет вид: 1 (4; 1) (4; 0).

а) Изобразите графически, какие платежи достижимы в повторяемой игре;

б) Определите, являются ли достижимыми платежи (4; 2), (3, 5; 0, 5), (5; 2) и (5; 3).

в) Какие из указанных платежей могут быть реализованы на множестве смешанных стратегий?

г) [Т] Для каждого достижимого платежа придумайте «умную» стратегию, которая реализует данный платеж. Тигр: Насколько умную?

Задача 6.2.

Средний и дисконтированный платежи Рассмотрим повторяемую игру, в которой базовая игра задана матрицей (2; 1) (4; 4). Дисконт фактор = 3. Запишем несколько стратегий игроков:

: в любой партии делать ход ;

: в любой партии делать ход ;

: в партиях с нечетными номерами делать ход, в партиях с четными номерами делать ход ;

: в партиях с нечетными номерами делать ход, в партиях с четными номерами делать ход.

а) Определите дисконтированный и средний платеж первого и второго игроков для следующих профилей: (; ), (; ) и (; ).

Задача 6.3.

Повторяемая дуополия Бертрана Дуополия Бертрана (т.е. фирмы назначают цену) повторяется бесконечное число раз. Предельные издержки обеих фирм равны нулю. Рыночный спрос описывается функцией = max {, 0}, где > 0 и > 0. Весь спрос достается фирме, назначающей наименьшую цену; если фирмы назначили одинаковую цену, то спрос делится между ними поровну.

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

б) Как изменится ответ, если число фирм будет равно ?

Задача 6.4.

Стратегии переключения и кнута и пряника Матрица базовой игры имеет вид: (2; 1) (4; 0). Заметим, что хотя в базовой игре,, и являются стратегиями игроков, в повторяемой игре это не стратегии, а всего лишь ходы!

а) Сформулируйте стратегии переключения для обоих игроков;

б) Сформулируйте стратегии кнута и пряника для обоих игроков;

в) Найдите, при каких значениях дисконт фактора стратегии переключения будут составлять совершенное подыгровое равновесие по Нэшу;

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

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

Задача 6.5.

Стратегии переключения и кнута и пряника Матрица базовой игры имеет вид: (1; 2) (10; 0). а) Сформулируйте стратегии переключения для обоих игроков;

б) Сформулируйте стратегии кнута и пряника для обоих игроков;

в) Найдите, при каких значениях дисконт фактора стратегии переключения будут составлять совершенное подыгровое равновесие по Нэшу;

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

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

Задача 6.6.

Повторяемая игра Стратегия формулируется так:

Играть ход в четных партиях и ход - в нечетных до тех пор, пока исходом игры является (; ) или (; ). Если произойдет исход, отличный от (; ) или (; ) всегда далее играть ход.

Стратегия формулируется так:

Играть ход в четных партиях и ход - в нечетных до тех пор, пока исходом игры является (; ) или (; ). Если произойдет исход, отличный от (; ) или (; ) всегда далее играть ход.

а) При каких значениях дисконт фактора пара стратегий ( ; ) является равновесием по Нэшу?

б) Совершенным подыгровым равновесием по Нэшу?

Задача 6.7.

Коровы В деревне живут пять крупных фермеров. Каждый фермер решает, сколько коров купить. Тигр: Как специалист, уверяю: коровы бесконечно делимы, непрерывны, а, если помыть лапы перед обедом, то и всюду дифференцируемы!

пасется более ста коров, то ни одна корова не дает молока. Если пасется коров, < 100, то каждая приносит = 10 0, 1 литров молока.

а) Найдите равновесие по Нэшу и оптимальные по Парето точки в этой игре;

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

в) Существует ли такой дисконт фактор и совершенное подыгровое равновесие по Нэшу, что каждый год только один из фермеров покупает коров?

Тигр: Редактор сказал, что дисконт-фактор пишется через дефис.

Автор: Пусть сам задачник составляет!

Задача 6.8.

Как велик соблазн?

Следующая игра повторяется два раза (величина > 3 ):

Первый игрок придерживается стратегии:

Второй игрок придерживается стратегии:

В первой партии сыграть 1. Если в первой партии был сыгран исход (1 ; 1 ) или оба игрока отклонились от этого исхода, то сыграть 2. Если в первой партии от исхода (1 ; 1 ) отклонился первый игрок, то сыграть 4. Если в первой партии от исхода (1 ; 1 ) отклонился второй игрок, то сыграть 3. а) Найдите все равновесия по Нэшу в чистых стратегиях в базовой игре;

б) Формализуйте стратегию второго игрока (по примеру стратегии первого);

в) При каких указанная пара стратегий будет совершенным подыгровым равновесием по Нэшу?

Просто равновесием по Нэшу?

Задача 6.9.

Фиктивная игра (fictitious play) [Sloth, TO] Рассмотрите игру:

а) Найдите все равновесия по Нэшу в этой игре.

Для краткости будем обозначать стратегии игроков одним числом - вероятностью выбора первой стратегии. Т.е. профиль стратегий задается парой чисел = (; ), где - вероятность, с которой первый игрок выбирает стратегию 1, а - вероятность выбора стратегии 1 вторым игроком. Функции наилучшего ответа обозначим 1 () и 2 () соответственно (если первый игрок безразличен между двумя стратегиями, то 1 () = 2 ). Назовем начальной теорией игры профиль 0 = (0 ; 0 ) = 1 ;. «Не знаешь, как сыграть - подбрось монетку».

б) Найдите наилучший ответ каждого игрока на данную теорию игры.

Обозначим этот ответ (0 ). Теорией игры после первого раунда (one-round updated theory) назовем среднее между начальной теорией и наилучшим ответом на нее. Так могут думать игроки после первого опыта игры: 1 = 1 0 + 2 (0 ). Аналогично, теория игры после -го раунда формируется по принципу: = +1 1 + +1 1. Игроки придают больший вес более длительному прошлому и делают поправку на оптимальный{ } ответ.

в) Сходится ли последовательность ? Если да, то к чему?

г) К чему будет сходиться при других начальных теориях игры?

д) Пусть стратегия -го игрока = lim приписывает положительный вес чистой стратегии. Докажите, что - наилучший ответ на бесконечное количество теорий. Т.е. существует подпоследовательность теорий, такая, что - наилучший ответ на любую из них.

е) Пользуясь предыдущим результатом, докажите, что - наилучший ответ на. Верно ли, что из этого следует, что - равновесие по Нэшу?

ж) Обобщите Ваше доказательство на случай произвольной игры (2 2).

з) Рассмотрите игру (Shapley’s Shimmy). Нарушается ли сходимость в данном случае? Почему?

Задача 6.10.

Какая стратегия лучше?

С помощью компьютера проведите симуляцию, определяющую, какая стратегия в классической дилемме заключенного лучше, «Зуб за зуб», стратегия переключения, стратегия кнута и пряника, случайная стратегия и т.д. Имеется поле размером некоторого размера (например, 100 100 ), в каждой ячейке которого живет индивид, играющий определенную стратегию. Между индивидом и его соседями проводятся фиктивные партии, и определяется победитель, получивший наибольший дисконтированный платеж. Индивид перенимает стратегию самого удачного своего соседа. По очереди перебираются все клетки и начинается следующий раунд.

В начале игры стратегии предписываются случайным образом.

Мелкие детали, отсутствующие в условии, придумайте самостоятельно.

Тигр: А лично мне интересно кто же, все-таки, победил в битве полов?

Задача 6.11.

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

Задача 6.12.

[LSE, 1996] Базовая игра повторяется два раза без дисконтирования. Может ли платеж (4; 4) быть получен в первой партии в совершенном подыгровом равновесии по Нэшу? Если да, то укажите соответствующий профиль стратегий.

Задача 6.13.

[LSE, 2002] Базовая игра повторяется неограниченное число раз с дисконт фактором, одинаковым для обоих игроков.

Стратегия Начать игру в фазе 1:

Сделать ход. Если исходом партии стал (; ), то вернуться к фазе 1, иначе перейти к фазе Фаза 2: Играть ход в каждой партии.

Стратегия Начать игру в фазе 1:

Сделать ход. Если исходом партии стал (; ), то вернуться к фазе 1, иначе перейти к фазе.

Фаза :

Сделать ход. Если исходом партии стал (; ), то вернуться в фазу 1, иначе перейти к фазе 2.

Фаза 2: Играть ход в каждой партии.

а) При каких профиль стратегий (; ) - равновесие по Нэшу, совершенное в подыграх?

б) При каких профиль стратегий ( ; ) - равновесие по Нэшу, совершенное в подыграх?

Задача 6.14.

Рассмотрим повторяемую игру с дисконт-фактором и матрицей базовой игры вида Комментарий: и - это ходы, а не стратегии; стратегия в повторяемой игре - это указание игроку, какой ход делать в партии с номером в зависимости от того, что случилось в предыдущих партиях. Подыгра - это все партии, следующие за заданной предысторией. Дисконтированные платежи игроков в подыгре обычно рассчитывают на момент вступления игроков в игру.

Петя (первый игрок) использует следующую стратегию: В 1-ой партии сделать ход ;

- сделать ход, если - нечетное число;

- скопировать ход противника в ( 1) -ой партии, если - четное число.

Вася (второй игрок) использует следующую стратегию:

В 1-ой партии сделать ход ; Во 2-ой партии сделать ход.

В -ой партии ( 3 )скопировать ход противника в ( 2) -ой партии.

а) Выпишите исходы первых 9-и партий. Найдите дисконтированный платеж первого игрока в игре в целом.

б) Допустим, что игра была начата другими игроками, которые сыграли в первых трех партиях последовательность исходов {(), (), ()}. Петя и Вася продолжают игру начиная с 4-ой партии, используя свои стратегии. Какие исходы будут сыграны в партиях №4-9?

в) Как сыграют Петя и Вася в подыгре, начинающейся после {(), ()} ? Выпишите исходы партий №3-9. Найдите дисконтированный платеж Васи в подыгре.

г) Как сыграют Петя и Вася в подыгре с предысторией {(), (), ()} ? Найдите дисконтированный платеж Пети игрока в подыгре.

Комментарий: вопросы «б» и «в» спрашивают об одном и том же, просто по-разному сформулированы Задача 6.15.

Рассмотрим повторяемую игру с дисконт-фактором = 0, 5 и матрицей базовой игры вида Петя (первый игрок) и Вася (второй игрок) используют одинаковую стратегию: В 1-ой партии сделать ход ;

В -ой партии ( 2 ):

- сделать ход, если во всех предыдущих партиях противник делал ход ;

- сделать ход, если хотя бы в одной предыдущей партии противник сделал ход ;

Эта стратегия называется «наивной стратегией переключения» («naive grim trigger»).

а) Какие исходы будут происходить в партиях? Рассчитайте платежи игроков.

б) Может ли Петя, используя другую стратегию, получить больший платеж?

в) Верно ли, что указанная пара стратегий является равновесием по Нэшу?

г) Как сыграют Петя и Вася в подыгре с предысторией {(), (), ()} ?

д) Рассчитайте платежи игроков в этой подыгре.

е) Может ли Вася увеличить свой выигрыш в рассматриваемой подыгре?

ж) Является ли указанная пара стратегий равновесием по Нэшу, совершенным в подыграх?

Задача 6.16.

Рассмотрим повторяемую игру с дисконт-фактором и матрицей базовой игры вида Петя (первый игрок) использует следующую стратегию: В 1-ой партии сделать ход ;

В -ой партии ( 2 ):

- сделать ход, если во всех предыдущих партиях был сыгран исход () ;

- сделать ход, если хотя бы в одной предыдущей партии не был сыгран исход () ;

Эта стратегия называется «стратегией переключения» («grim trigger»).

Вася (второй игрок) также использует стратегию переключения.

Рассмотрим три подыгры: 1 - подыгру с предысторией {(), (), ()}, 2 - подыгру с предысторией {(), (), (), ()} и 3 - подыгру с предысторией {(), (), ()}. а) Какие исходы будут происходить в самой игре ?

б) Какие исходы будут происходить в подыгре 3 ?

в) Какие исходы будут происходить в подыгре 1 ?

г) Выгодно ли Пете в одиночку использовать другую стратегию в подыгре 1 ? Васе?

д) Какие исходы будут происходить в подыгре 2 ?

е) Выгодно ли Пете в одиночку использовать другую стратегию в подыгре 2 ? Васе?

ж) [Т?] Для данной игры докажите следующее утверждение: Если при данном пара стратегий переключений равновесна по Нэшу, то она также является равновесием по Нэшу, совершенным в подыграх.

Задача 6.17.

Рассмотрим повторяемую игру с дисконт-фактором и матрицей базовой игры вида Некоторые стратегии можно записывать в алгоритмической форме. Рассмотрим пример. Стратегия первого игрока имеет вид:

Начать 1-ую партию в состоянии 1.

В состоянии 1 сделать ход.

Из состояния 1 перейти в: