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

Мосты Цезаря: “commitment”. Цезарь с войском переправился по наведенным мостам через реку на сторону неприятеля, войско Цезаря приготовилось к бою. Неприятель приготовился к бою. Цезарь сжег за собой мосты. Увидев это, неприятель бежал.

Составить две игры, годящихся для объяснения этой ситуации: 1)С полной информацией о целях трех игроков: Цезарь, войско Цезаря, неприятель. 2)С двумя игроками (Цезарь, неприятель), неполной информацией и выявлением целей Цезаря через его поведение.

(Сходная ситуация “commitment” возникает при кредите с залогом).

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

Задача 9.33.

Залог или клятва: “commitment”.

Пусть, популяция российских бизнесменов имеет обыкновение просить кредит размером в $ 100 на год в банке, и при гарантии возврата банк готов бы давать кредит под 5%. Пользование кредитом приносит среднему бизнесмену в год %. В среднем, четверть бизнесменов кредит без залога не отдают. Оставляя в гараже банка свой джип ценой в $ 120 в залог на год, бизнесмен имеет потерю полезности, равную 10% годовых. Половина бизнесменов джипов не имеют, им оставить нечего. Но половина из всех (поровну среди джипо-владельцев и безлошадных) известны как истые мусульмане, каждый может поклясться Аллахом, что кредит отдаст, и клятвы эти всегда исполняются.

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

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

Задача 9.34.

[Цена репутации (клятва)] Предположим, религиозный ростовщик в средневековом Багдаде не считает богоугодным зарабатывать на каждой сделке больше 1 процента и не ограничен в деньгах.

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

(Вариант: Мусульмане имеют неудовольствие от нарушение клятвы размером в % годовых, иудеи – в % годовых, христиане – в % годовых. Кто из купцов почем получает кредит (если получает)?) Источник: БЗИ.

Задача 9.35.

Стратегическое лидерство в состязаниях. Трое соискателей А, B, C ведут борьбу за приз, ценность которого равна 1. Они последовательно выбирают свои уровни усилий,, (сначала выбирает A, потом B, потом C). Вероятность для участника выиграть приз равна + +. Считаем, что для каждого соискателя затраты усилий в размере эквивалентны потере денежных единиц. Участники нейтральны к риску. Опишите, как устроена развернутая форма игры, и найдите равновесие (не только равновесные уровни усилий, но и стратегии участников!) при следующих информационных предположениях, являющихся общим знанием:

a) Каждый участник знает все, что происходило до его хода.

b) Участники В и С знают, С не знает.

c) Участник С знает больше никто ничего не знает.

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

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

Задача 9.36.

Маленькие семейные радости. У мужа на работе предстоит веселая вечеринка. Жена обещает мужу семейный скандал, если он напьется. Во время вечеринки муж может с вероятностью влюбиться в молодую сотрудницу. После этого он должен решить, напиваться ему или нет. Если он не напьется, то его выигрыш равен нулю; выигрыш жены в этом случае тоже равен нулю. Если муж напьется, жена должна решить, сидеть тихо или же устроить скандал. Если учинить скандал влюбленному мужу, то он уйдет к молодой сотруднице. Тогда выигрыши мужа и жены равны (1, 3); учинив скандал просто пьяному мужу, жена и муж получают по 1. Если сидеть тихо, то выигрыш жены равен 2; выигрыш влюбившегося мужа при этом равен 3 (ему стыдно), а просто пьяного мужа равен 5.

Формализуйте игру в развернутой форме.

Найдите все сильные секвенциальные равновесия.

А что, если влюбиться может только пьяный муж?

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

Задача 9.37.

Вариации на тему «чет-нечет», «matching pennies»

Тигр: Молчите, поручик Ржевский!

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

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

б) Сначала первый игрок подбрасывает монетку (результат подбрасывания не доступен второму игроку). Если монетка выпала на орла, то игроки играют в классический «чет-нечет». Если монетка выпала на решку, то играется «чет-нечет», но первый игрок обязан назвать четное число.

в) Перед игрой в «чет-нечет» первый игрок подбрасывает игральную кость (второй игрок не знает результат подбрасывания). Если кость выпадает на 1 или 2, то играется классический «чет-нечет».

Если кость выпадает на 3, 4, 5, 6, то размер выигрыша в случае четной суммы устанавливается равным двум рублям (размер выигрыша при нечетной сумме остается равным одному рублю).

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

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

9.1 Передача информации Главное не война - главное - маневры!

Задачи, где самое важное понять как передается информация между игроками...

Задача 9.38.

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

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

После этой новости они собирались за сакэ еще шесть раз. Больше ни разу они уже не собрались:

все покончили собой...

а) Сколько самураев рода Цзы охраняло князя? Тигр: Без сакэ не разобраться! б) То, что сообщил служитель замка, было известно всем самураям рода Цзы! Раз все они покончили собой, значит все были виновны, значит каждый знал о вине своих сородичей. Что же нового5 содержало сообщение служителя о том, что хотя бы один из них виновен?

в) Смогли бы самураи установить свою виновность, если бы виновны были не все?

Задача 9.39.

Колпаки (см. R.Myerson). Царь решил испытать своих четырех мудрецов. Он приказал им закрыть глаза и из мешка, где было много черных и белых колпаков, вынул случайным образом и надел на мудрецов 4 колпака. Сказал им открыть глаза, сообщил, что в мешке были черные и белые и спросил: может ли кто наверняка угадать на себе колпак глядя на других? "Нет - это невозможно сказали мудрецы (и были правы). А случилось, что все колпаки белые. "А ведь среди одетых есть белый колпак, тогда что вы о себе скажете? сказал царь. Мудрецы промолчали. Ведь ничего нового он не сообщил: каждый уже видел троих соседей в белом. "Помолчите минуту, потом можно говорить сказал царь. Но и во второй раз они молчали. И когда третий раз он предложил говорить - молчали. А вот на четвертый раз каждый сказал, что он в белом колпаке, и однозначно объяснил это, и царь всех наградил. 1)Объясните решение (SPE). В чем новизна поступившей от царя информации? 2)Покажите, что так же решается задача для любого числа мудрецов и любого варианта выпавших черных/белых колпаков: кто-то определит свой колпак и скажет. 3)Покажите, что если выпали неодинаковые колпаки, то более слабой подсказки царя: "колпаки неодинаковы достаточно для разрешения игры НЕ ПРИ ВСЯКОМ числе черных и белых.

(=предыдущую игру можно как=Конкурс. (тема "общее знание") Трое или четверо студентов закрывают глаза и экзаменатор кладет на голову каждому белый платок. Известно, что платки бывают красные или белые. Разрешается открыть глаза. Угадать цвет платка на себе невозможно. Но когда экзаменатор скажет: "среди вас есть белый платок угадать возможно (хотя он ничего нового каждому не сообщил). Потом командует: закрыть глаза, открыть глаза (чтобы были этапы).

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

Ребенок и папа видят, как мама кладет банан в одну из двух коробок на столе. Потом мама выходит из комнаты.

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

Ребенок ответит, что в той коробке, куда его переложили. Зачем искать банан там, где его нет? И только примерно к трем годам ребенок понимает, что всеобщности знания нет, и... может лгать.

10 кооперативные игры Задача 10.1.

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

Задача 10.2.

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

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

Задача 10.3.

«So long sucker» [1950, Nash, Shapley, Hausner, Shubik] Тигр: в эту игру обязательно нужно сыграть!

Автор: И еще ей неплохо бы придумать цензурное название 1. Игра для четырех игроков.

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

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

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

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

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

7. Убитые фишки помещаются в «коробку мертвых»

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

9. Игрок терпит поражение и выбывает из игры, если он не может сделать ход, т.е. если у него не осталось фишек в собственности. Поражение не является окончательным, пока остальные игроки официально не отказались от передачи пленников (правило 8). Если игрок выбыл из игры, то ход возвращается к тому игроку, который передал выбывшему право хода. (Если это приводит к поражению последнего, то ход возвращается еще на шаг назад и т.д.) 10. Фишки выбывшего игрока остаются в игре пленниками, но игнорируются при определении порядка хода (правило 5). Если башня взята с помощью двух фишек выбывшего игрока, то вся башня убивается, а ход возвращается как в правиле 9.

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

12. Разрешены любые переговоры, кроме сговоров до игры или переговоров вдали от игрового поля.

В правилах нет никаких штрафов за неисполнение взятых обязательств.

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

McCarthy’s revenge rule: «When fatally double-crossed, try to damage the double-crosser as much as possible before your demise.»

«We had married couples going home in separate cabs»

«‘So Long Sucker,’ A Four-Person Game». In M. Shubik (ed.) Game Theory and Related Approaches to Social Behavior, John Wiley & Sons, Inc., New York.

Задача 10.4.

Подземные музыканты. Оркестр из трех музыкантов (,, ) играет в подземном переходе.

Поодиночке они могли бы заработать, соответственно, 6, 18 и 30 рублей в час. Играя по двое, они бы получили: и — 36, и — 48, и — 54. А вместе они имеют 72.

1. Будет ли отвергнут равный дележ, и если будет, то какими коалициями?

2. Найдите ядро игры, т. е. все дележи, которые не будут отвергнуты.

3. Является ли игра супераддитивной? Супермодулярной?

4. Найдите все точки Вебера и вектор Шепли. Что из найденного принадлежит ядру?

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

Задача 10.5.

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

1. Найдите ядро этой кооперативной игры.

2. Пусть вдобавок имеется еще президент, одобрение которого обязательно. Сколько он получит в ядре? В векторе Шепли?

3. А потом две палаты объединили. Теперь нужно просто 4 голоса из 6 плюс президентское одобрение. Вроде бы, парламент стал сильнее, так как больше выигрывающих коалиций, чем в 2.

Как изменилась “зарплата” президента?

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

Задача 10.6.

Назовем кооперативную игру с трансферабельной полезностью симметСимметричные игры.

если выигрыш () коалиции зависит только от ее численности = ||. Без ограничения ричной, общности считаем, что ( ) =. Какой должна быть функция () для того, чтобы ядро было непустым? чтобы игра была супермодулярной?

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

Задача 10.7.

Строительство дороги. Четыре поселка,,, расположены на берегу большого озера (см.

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

1. Для каждой коалиции найдите минимальную протяженность нужной ей дороги. Опишите ядро игры. Является ли игра супермодулярной?

2. Пусть поселки равноправны в переговорном процессе, а затраты делятся, исходя из вектора Шепли. Сколько километров дороги должен профинансировать каждый поселок?

3. Пусть,,, — число жителей в поселках, причем не обязательно = = =.

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

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

Задача 10.8.

Охрана. Имеется 6 производителей,,,,,, каждый из которых может заработать $1, и два охранника и, не производящих ничего. Коалиция получает суммарную выручку ее участников, но только в том случае, если среди них есть хотя бы один охранник. Иначе приходят грабители и все забирают. Сколько нужно платить охранникам? Ответьте на этот вопрос с точки зрения ядра и вектора Шепли.

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

Задача 10.9.

Ядро экономики. Алиса, Берта и Виола имеют по единице товара, который оценивают, соответственно, в 3, 6 и 8 долларов. Густав, Даниил, Евгений и Жорж могли бы купить по единице этого товара и готовы заплатить за него, соответственно, 2, 4, 7 и 9 долларов.

1. Формализуйте эту ситуацию в виде кооперативной игры с побочными платежами (задайте выигрыши коалиций).

2. Пусто ли ядро этой игры?

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

Задача 10.10.

вуют игроки 1, 2, 3. Выигрыши коалиций заданы следующим образом:

1. Найдите разложение этой игры по базису из элементарных игр, {1, 2, 3}.

2. Как из найденного разложения получить вектор Шепли?

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

Задача 10.11.

Rendez-vous-2. Джон и Мэри живут на одной улице (см. рис.) и по умолчанию встречаются у фонтана (0 ). Они могут договориться о встрече в любом другом месте улицы. Полезность участника равна (со знаком минус) расстоянию, которое ему нужно пройти.

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

2. Пусть — место встречи, соответствующее решению Нэша этой задачи торга. Найдите как функцию от 0 R и постройте ее график.

3. Тот же вопрос для — решения Калаи—Смородински.

4. А что можно сказать про эгалитарное и утилитарное решения?

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

Задача 10.12.

почтения участников задаются функциями полезности, соответственно, 1 = и 2 = min, 2.

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

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

3. Указать на тех же рисунках распределение товаров и пару выигрышей, соответствующие общему равновесию в данной экономике обмена. Сравнить результаты пунктов 1–3 и прокомментировать.

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

Задача 10.13.

Toetjes.

Остался последний кусочек пирога. три брата не знают как его поделить. Папа спрашивает «Сколько стоил пирог в магазине?» Сначала отвечает старший сын, затем средний, затем младший. Называть одинаковые цены нельзя. Для простоты будем считать, что деньги бесконечно делимы, а стоимость пирога - случайная величина равномерная на [0; 1].

Найдите вектор Шепли6 и ядро.

Источник: [14].

Задача 10.14.

Совет безопасности ООН состоит из пяти постоянных и десяти переменных членов. Никакое решение не может быть принято без одобрения со стороны всех постоянных членов, но и без 10 голосующих «за» тоже. Коалиция выигрывет, если удовлетворяет обоим требованиям. Найти распределение сил, в соответствии с ядром и с вектором Шепли. Является ли игра супермодулярной?

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

Задача 10.15.

Семейные вечера. По вечерам семья любит слушать музыку. Мама обожает Аллу Пугачеву (точка на прямой), сын больше всего любит группу Чайф (точка 0.5 на той же прямой), а папа тащится от Шнура из группы «Ленинград» (точка 1 на прямой). Удовольствие от музыки равно 1 минус расстояние от нее до своей любимой музыки. Установка воспроизводящего устройства требует 1 издержек.

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

Формализуйте эту ситуацию как коалиционную игру с побочными платежами. Является ли игра супераддитивной? Супермодулярной?

Опишите ядро этой игры.

Можно считать, что цена коалиции - это супремум достижимых коалицией платежей.

Найдите вектор Шепли этой игры. Лежит ли он в ядре? Какая музыка будет играть? Кто сколько вносит на воспроизводящее устройство?

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

Задача 10.16.

Нефть из Ирака следует в США многими путями, возможно переплетаясь по пути (строго говоря, есть граф нефтепроводов, и нигде посередине нефть качать нельзя). У каждого нефтепровода существует максимальная пропускная способность. Каждый из нефтепроводов контролируется одним из бандитских формирований. США готово платить за нефть пропорционально мощности потока.

Доказать, что бандиты всегда могут договориться, не развязывая войны.

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

11 Эволюционные игры Задача 11.1.

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

по очереди каждая особь... (?) 12 Неразобрано!

13 Идеи проектов/курсовых/вопросы с неизвестным (кому?) ответом/конкурсы!

Задача 13.1.

A.Savvateev Дуополия Бертрана с неодинаковыми издержками, и/или с ограничением целочисленности цены. Найти все Нэшевские равновесия. Какие еще могут быть равновесия?

Задача 13.2.

Приведите пример игры без условия Куна, в которой не существует секвенциального равновесия даже в смешанных стратегиях. (Эта задача довольно зыбкая; ответ мне неизвестен, да и понятие решения там плохо определимо. Однако, если кто продемонстрирует блестящий пример, заработает двойной бонус.) Источник: НМУ, экзамен 2004, Леша Савватеев.

Задача 13.3.

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

Задача 13.4.

Конкурс. Аукцион «Лохотрон». На столе лежит 100 руб. - дар экзаменатора. Любой желающий участвовать в розыгрыше этой купюры вносит на стол 1 рубль (безвозвратно). Желающие продолжать розыгрыш вносят еще по 1. И т.д. Победитель забирает все (возместив экзаменатору 100) и получает "отл.". Призером также является - первым подавший корректную модель игры.

Задача 13.5.

Конкурс. («общее знание») Трое или четверо из занявших лучшие места в другом конкурсе закрывают глаза и экзаменатор кладет на голову каждому белый платок. Известно, что платки бывают красные или белые. Разрешается открыть глаза. Угадать цвет платка на себе невозможно. Но когда экзаменатор скажет: "среди вас есть белый платок угадать возможно (хотя он ничего нового каждому не сообщил). Вигрывает угадавший первым и объяснивший. Призером также является - первым подавший корректную модель игры.

14 Решения 2.1. 100 к 2.2. Джордж может поймать Усаму. Пройдемся подряд по всем пещерам, дважды осмотрим последнюю и пройдемся в обратном порядке.

2.3.

2.4. Саддам. За месяц Саддам может построить одну треть завода. За 13 месяцев у него будет третей завода. Начнем их достраивать. Их тут же разрушают, но 13-ую треть мы достраиваем и 13, и 14 числа. Завод готов.

2.5.

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

2.8. a) Количество камней в самой правой кучке не может расти. Далее по индукции - допустим игра на кучках всегда заканчивается, а мы играем на + 1 кучке. Мы рано или поздно возьмем камень из самой правой ( + 1-ой) кучки, т.к. игра на левых заканчивается. Потом еще один. И еще...

б) Сделать своим ходом четное число камней во всех кучках 2.9. Чтобы помешать акционеру провести кандидатов конкуренты должны провести + 1 своего кандидата. Оптимально распределеть имеющиеся голоса поровну. В непрерывном случаенужно выбрать минимальное удовлетворяющее неравенству: > ( ). Получаем = +1 + 1.

В непрерывном случае неравенство заменяется на > ( ) Поэтому алгоритм выглядит так: Пробуем = +1 + Если оно подходит в неравенство, то объявляем его ответом.

Если оно не подходит в неравенство, то объявляем ответом = +1 + 2.

2.10.

2.11. Последний называет остаток от деления на суммы цветов шляп впереди стоящих, гарантировано спасены ( 1).

2.12. первый день прийти в особой рубашке, затем копировать действия Васи 2.13.

2.14.

2.15.

2.16. б) Выбират руку наугад. Если видимое число больше того, что сказала гадалка, говорить, что оно большее. Если гадалка попала между Машиных чисел - мы выиграли. Если нет, то у нас шансы выиграть равны 50% г) если Маша загадывает два соседних очень больших числа, то можно приблизить вероятность машиного проигрыша к 50% 2.17. а) нет, нужно считать условное ожидание, а для него нужны априорные вероятности б) для существования условного м.о. нужна конечность обычного м.о. Здесь обычное м.о. равно плюс бесконечности...

3.1. цикл:

-,+,+,+,+,и далее -+ 3.4. Решаем по индукции. Для удобства занумеруем пиратов начиная с самого младшего (номер 1 зеленый юнга,..., номер - капитан). Если в живых остался один пират, то он предлагает все себе и сам же одобряет этот дележ. Если в живых осталось два пирата ( = 2), то предлагающий дележ должен все отдать юнге. Иначе юнга не согласится, и по правилам игры дележ не будет одобрен, а неодобренный дележ означает для пирата номер 2 смерть. Если в живых осталось три пирата, то пират номер 3 предлагает все себе. Сам он одобряет этот дележ, юнга одобряет (ему все равно ничего не достанется), только пират номер 2 против. Дележ одобрен. Если осталось > 3 пиратов, то пират номер предлагает все себе. Все пираты кроме пирата номер ( 1) одобряют этот дележ 3.5. one of possible, the first 44 pirates are thrown overboard, and then P456 offers one gold piece to each of the odd-numbered pirates P1 through P 3.6.

3.7.

3.8.

3.9.

3.10.

3.11.

3.12.

3.13.

3.14.

3.15.

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

3.17.

3.18.

3.19.

3.20.

3.21.

3.22. A, C, D, E, H = +; B, F, G, I = Один тигр и одна антилопа -> тигр съедает антилопу. Два тигра и одна антилопа -> тигры не едят антилопу, т.к. иначе за вкус придется заплатить жизнью. По индукции - при четном числе тигров, тигры воздерживаются от трапезы; при нечетном числе тигров один из тигров ест антилопу, а далее тигры воздерживаются от трапезы.

3.26.

3.27.

3.28.

3.29.

3.30.

3.31. нет 3.32. 1 патрон, :

при четном - стрелять равновероятно в впередистоящих при нечетном - стрелять равновероятно в позадистоящих или в воздух (если позади - никого), = 1 - вероятность погибнуть для ковбоя номер. (при четном ) бесконечные патроны, :

при четном - стрелять равновероятно в остальных при нечетном - стрелять в воздух 3.33.

3.34.

3.35.

3.36.

3.37.

3.38.

3.39.

3.40.

3.41.

3.42.

3.43.

3.44.

3.45.

3.46.

3.47.

3.48.

3.49.

3.50.

3.51.

3.52.

3.53.

3.54.

3.55. Выигрышные позиции при малых : 1,2,3,5,7,9,10,12,14,16,18,19...

Можно заметить, что выигрышные позиции остоят друг от друга на расстояние 1 или на расстояние 2. На двумерной доске (вроде бы?) если аккуратно действовать то можно доказать, что начиная с 6-ой разницы есть цикл разниц вида: (1-2-2-2-2-1-2-) 3.56.

3.57.

3.58.

3.59. а) NE: RB, LA; SPNE: LA, б) RXX-BB, в) AX-R, г) LX-AA, RX-AA, LX-AB 3.60.

3.61.

3.62.

3.63.

3.64.

3.65.

3.66.

3.67.

4.1. е) - нет, могут быть «плохие» ходы ж) - да, по определению функции 4.2.

4.3.

4.4.

4.5.

4.6.

4.7.

4.8.

4.9.

5.1. Занумеруем рабочих. Делаем нумерацию общеизвестной. Публично обещаем уволить «тунеядца»

с наименьшим номером. Все. В результате: Номеру 1 не выгодно быть тунеядцем - его уволят не глядя на других. Номеру 2 не выгодно быть тунеядцем, т.к. номер 1 тунеядцем не будет. И т.д.

5.2. Чтобы максимум () + (1 ) (1 ) был в точке = необходимым условием будет: () = Если левую часть обозначить (), то получаем уравнение () = (1 ). Берем любую функцию, симметричную относительно 1/2 (останется потом только проверить, что = - это максимум, а не минимум). Например, подойдет () = 1, тогда получаем () = ln(), или () = 2(1 ), тогда получаем () = 2 + 5.3.

5.4. Guy number one makes a guesstimate of what the average salary is. Announces it out loud. Guy number 2 computes the difference between the guessed average and his own salary. He then whispers a number that is in the range of the computed number to guy 3. Guy 3 makes the same computation, and then adds that to the number the number that was whispered to him. 3 whispers to 1. 1 makes the same computation. Whispers to 2. 2 backs out his fake number. adds in his real number. Divides by 3. Adds to the original guess.

5.5.

5.6.

5.7.

5.8. Разбив время на интервалы по несколько моментов, можно передавать информацию не в виде «коснулся-не коснулся», а целые слова.

ности плюс задачка об уведомлении центрального.

6.1.

6.2.

6.3.

6.4.

6.5.

6.6.

6.7.

6.8.

6.9.

6.10.

6.11.

6.12.

6.13.

6.14.

6.15.

6.16.

6.17.

6.18.

6.19.

6.20.

6.21.

6.22.

6.23.

7.1.

7.2.

7.3. Два игрока. Множество стратегий первого 1 = [0; +), множество стратегий второго 2 = [0; +). Платежные функции: 1 = 1.5(2+2 ) 1, 2 = 1.5(2+2 ) 2. В матричной форме не представляется, т.к. стратегий у каждого игрока бесконечное количество. Равновесие по Нэшу 1 = 0, 2 = 0. Стратегия 1 = 0 строго доминирует любую стратегию первого игрока, аналогично со стратегией 2 = 0.

7.4. Эту ситуацию можно смоделировать так: игроков, у каждого две стратегии: стоять или сидеть.

Равновесий по Нэшу два: главарь сидит и все сидят, главарь стоит и все стоят.

7.5. б) 1 в) 2 г) + 7.6. 4 равновесия 7.7.

7.8.

7.9.

7.10.

7.11.

7.12.

7.13.

7.14.

7.15.

7.16.

7.17. b) geometric distribution в) Лотерея оказалась неустойчива к сговору игроков.

7.18. б) (0.5; 0.25; 0.25) 7.19. вроде, да 7.20.

7.21. Достаточно рассмотрететь отрезок вместо круга. (?)...

7.22.

7.23. нет 7.24. обе партии голосуют «за» и денег не получают 7.25. да, конечно 7.26.

7.27. да, конечно 7.28.

7.29.

7.30.

7.31.

7.32. да, классическая дилемма заключенного 7.33.

7.34.

7.35.

7.36.

7.39.

7.40.

7.41. а) (14/3, 16/3), (2/3, 16/3) б)..., (0, 2) в) а - нет, б - похоже тоже нет 7.42. а) равновесия в чистых нет.

б) Первый игрок должен быть безразличен между усилиями: 1 [; ]. Т.е. (1 ) = () = ().

Если первый игрок выбирает уровень усилий 1, то он выигрывает с вероятностью 0 1 (). Следовательно:

Поскольку есть стратегия 1 = 0, приносящая полезность 0, любая играемая стратегия должна приносить платеж не меньше 0. Отсюда = 0 и = 1/ 2. Взяв производную по 1 получаем:

() = 4 на отрезке [0; 1/ 2].

7.43.

7.44.

7.45.

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

Машеньке не выгодно отклоняться: (1 + )(1 + ) (1 + )(1 + ) Вовочке не выгодно отклоняться: (1 + )(1 + ) (1 + )(1 + ) Эти неравенства упрощаются до:

Из первого неравенства следует, что > 0. Это логично, т.к. единственный довод ходить в платную школу в данной модели - это наличие там умного окружения.

Но > значит система неравенств не имеет решения. Подобная ситуация невозможна.

б) Из пункта а) можно сделать вывод: если в равновесии кто-то выбирает платную школу, то все школьники с более высоким уровнем интеллекта также выбирают платную школу.

Отсюда: любое равновесие по Нэшу должно иметь вид: школьники с интеллектом до * выбирают бесплатную школу, более умные - платную. Найдем этот *.

Средний контингент бесплатной школы:, в платной - 2.

Условие при котором школьнику лучше идти в бесплатную:

Упрощаем: 2 1. Т.е. * = 2 1.

Вывод:

Если < 0.5, то в равновесии все выбирают бесплатную школу.

Если > 0.5, то в равновесии школьники с интеллектом < 2 1 выбирают бесплатную школу, а остальные - платную.

7.47.

7.48. а) да; б) бесконечное количество; в) да; г) может не быть 7.49.

7.50.

7.51.

7.52.

7.53.

7.54.

7.55. 7.56.

7.57. Если (, ) = +, > 0, > 0, то = (+)2, = (+)3 Может вторая производная больше нуля? Какова вероятность выигрыша команды с подготовкой, если известно, что ей придется встретиться с командами с подготовками 1, 2... ?

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

Производная этой вероятности в свою очередь распадается на несколько слагаемых...

Может от произведения лучше взять логарифм?

7.58. a) = 1, = 7.59.

7.60.

7.61.

7.62.

7.63.

7.64.

7.65.

7.66.

7.67.

7.68.

7.69.

7.70.

7.71.

7.72.

7.73. Кстати, решается для 3-х в смешанных стратегиях, см. Limbo.

7.74.

7.75. Нет.

7.76.

7.77.

7.78.

7.79.

7.80.

7.81. а) оптимальной стратегии нет б) Равновмерно на [0; 2], гарантирует выигрыш с вероятностью не менее 0.5.

7.82. Пусть Саша использует функцию плотности, а Алеша - чистую стратегию. Находим условие безразличия для Алеши. Решаем дифф. уравнение на. Ответ: () =...3/2 при [0.25; 1].

8.1.

8.2.

8.3.

8.4.

8.5.

8.6.

8.7.

8.8.

8.9.

8.10.

8.11.

8.12.

8.13.

8.14.

8.15.

8.16.

8.17.

8.18.

8.19.

8.20.

8.21.

8.22. Предположим, что решение задачи, функция () - возрастающая.

() = ( )( (())1, максимизируем по Получаем линейное дифференциальное уравнение на ():

+ (1) () = (1) () Решение соответствующего однородного: () = ( ()) Начальное условие (0) = Решение неоднородного: Легко проверить, что () получилась возрастающая 8.23. I am searching for the Nash-Equilibrium bid function b(v).

Let’s guess. Maybe it’s linear?

I verify whether it is of the form () = ·.

How a bidder think?

If my value is v and i bid b then my expected profit is:

= (I win)( ( 2 +3 +...+ |I win)) It may be simplyfied to:

I maximize it, choosing b and get equation:

It seems plausible. Because in the case of = 2 it gives = (truthful bidding) but in that case this auction is just the second price auction.

8.24. Let’s guess.

Maybe is linear?

In that case = ·. (I prefer for bid and for value) If is uniform then (for linear f) is also uniform.

While searching for Nash Equilibria one fix the strategies of all other players and find the best response for one selected player. So i fix strategies of all ( 1) players as = · for {2,..., } Let’s denote - the event "I Win the auction".

Expected profit or utility for risk neutral player equals to: ( ) = ( )·(( +2 | ) Here (i am(the +...

Plugging this into ( ) and maximizing by b: ( ) = · ( 2 ) ( 1) 2 1+1 = 0 Or And it’s indeed linear!

For large you bid about one half of the value - just like in the case of "average of the others bid"auction.

Because the influence of your bid disappears.

8.25.

8.26. б) да в) (1,..., ), (1, 0, 0,..., 0), (2, 1, 0, 0,..., 0) 8.27.

8.28.

8.29.

8.30.

9.1.

9.2.

9.3.

9.4.

9.5.

9.6.

9.7. {,,, = 0} solution (full):

Слабое секвенциальное равновесие должно удовлетворять нескольким критериям:

1. Если вероятность попасть в информационное множество больше нуля, то веры в нем должны определяться по формуле условной вероятности.

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

У первого 16 стратегий, у второго - 2 стратегии. Проще искать перебором. (Хотя можно выписать матрицу 16 на 2, найти равновесия по Нэшу и попытаться дополнить их верами).

Пусть второй играет b.

Оптимальность действий в верхнем правом узле требует, чтобы там первый выбирал c.

Оптимальность действий в нижнем правом узле требует, чтобы там первый выбирал h.

Оптимальность действий в нижнем левом узле требует, чтобы там первый выбирал k.

Оптимальность действий в верхнем левом узле требует, чтобы там первый выбирал i.

Зная стратегию первого, считаем веры для второго. Веры равны по 0.5.

Проверяем, оптимальность действий второго в его информационном множестве.

При таких верах ожидаемая полезность от хода b равна 2.

При таких верах ожидаемая полезность от хода j равна -1.

Ходить b оптимально.

Итого: chki, b, mu=0.5 - WSE Пусть второй играет j.

Оптимальность действий в верхнем правом узле требует, чтобы там первый выбирал c.

Оптимальность действий в нижнем правом узле требует, чтобы там первый выбирал h.

Оптимальность действий в нижнем левом узле требует, чтобы там первый выбирал k.

Оптимальность действий в верхнем левом узле требует, чтобы там первый выбирал a.

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

Веры равны: 0 (вверху) и 1 (внизу).

Проверяем, оптимальность действий второго в его информационном множестве.

При таких верах ожидаемая полезность от хода b равна 2.

При таких верах ожидаемая полезность от хода j равна -5.

Ходить j неоптимально.

Итого: нет WSE таких, что второй играет j.

Ответ: WSE: (chki, b, mu=0.5) 9.8.

9.9.

9.10.

9.11.

9.12.

9.13.

9.14.

9.15.

9.16. нет, нет 9.17.

9.18.

9.19.

9.20.

9.21.

9.22.

9.23.

9.24.

9.25.

9.26.

9.27.

9.28.

9.29.

9.30.

9.31.

9.32.

9.33.

9.34.

9.35.

9.36.

9.37.

Главное не война - главное - маневры!

Задачи, где самое важное понять как передается информация между игроками...

9.38.

9.39.

10.1.

10.2.

10.3.

10.4.

10.5.

10.6.

10.7.

10.8.

10.9.

10.10.

10.11.

10.12. ( 10.13. 36, 13, 16, ядро пусто 10.14.

10.15.

10.16.

11.1.

13.1. здесь ссылку - где поискать в инете 13.2. мне казалось есть какая-то статья в Journal of gt and ec. beh 13.3.

13.4.

13.5.

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

Решение в (слабо-) доминирующих стратегиях (WDE) - исход игры в случае наличия у каждого "абсолютно-оптимальной"стратегии, то есть стратегии, (слабо) доминирующей над всеми другими его стратегиями независимо от ходов партнеров, их целей и текущих решений. [Аналогично и определение сильно-доминирующего равновесия SDE.] Решение в итерационно- (слабо-)недоминируемых стратегиях (IND ) - исход игры в случае одновременного итерационного отбрасывания (слабо-) доминируемых стратегий каждым игроком и соответствующего редуцирования игры: исключения отброшенных стратегий из рассмотрения ВСЕМИ игроками. Требует знания или целей партнеров или факта отбрасывания стратегий. [Аналогично определяется Решение в итерационно- сильно-недоминируемых стратегиях (IND ).] Равновесие Нэша (NE) стимула отступить от своей текущей стратегии, при знании текущих стратегий партнеров и гипотезе, что партнеры не отступят. [Эквивалентный вариант: Равновесие Нэша - исход, когда все сходили одновременно вслепую, имея лишь некоторые ожидания о запланированном ходе партнеров, а когда карты открылись, то все ожидания оправдались.] нутой форме игры, являющееся также равновесием Нэша во всех ее подыграх.

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

лицией в переговорах. Коалиция блокирует в переговорах (отвергает) вариант, если имеет другой, строго более желательный для всех своих членов, среди СВОИХ возможностей (среди вариантов, достижимых независимо от действий вне-коалиционных игроков). Т.е. Ядро - множество вариантов, вне которого соглашений быть не может.

– MaxiMin, – Dominant Equilibrium, – Strong Dominant Equilibrium, Сокращения:

– Iterative (Weakly) Non-Dominant Equilibrium, – Sophisticated Equilibrium, Nash Equilibrium, – Nash Equilibrium in Mixed stratagies, ( ) – Subgame Perfect (Nash) Equilibrium, – Stackelberg Equilibrium, - Pareto, – Core.

16 Названия некоторых стратегий в повторяющейся дилемме Обозначения:

- исход базовой игры с номером ;

- ход сделанный -ым игроком в базовой игре с номером.

- стратегия -го игрока;

- предыстория игры к моменту времени : = {1, 2,...1 } ;

( ) - ход, предписываемый стратегией после истории (в момент );

Стратегия «Всегда кооперироваться» (always cooperate) Предписывает всегда играть ход : ( ) =, Наивная стратегия переключения (naive grim trigger) Предписывает играть ход в первой партии и далее до тех пор, пока противник играет ход :

Стратегия переключения (grim trigger) Предписывает играть ход в первой партии и далее до тех пор, пока оба игрока играют ход :

Стратегия «Зуб за зуб» (Tit for Tat) Предписывает играть ход в первой партии и далее повторять ход противника в предыдущей партии:

Стратегия Кнута и Пряника (Win-Stay, Lose-Shift; Pavlov strategy) Предписывает играть ход в первой партии и далее играть ход, если в предыдущей партии действия игроков совпали: ( ) =, = 1, > 1, 1 {(; ), (; )}, Тигр:

Эта хитрая стратегия была внедрена известными специалистами по теории игр Кнутом Б.Б. и Пряником В.Л.

Стратегия ограниченного возмездия Предписывает играть ход, пока все игроки кооперируются. Если произошло нарушение, то в течение ходов играть, затем вернуться в исходное состояние. Состоит из трех фаз: Фаза 1:

сыграть ход и переключиться в фазу 2; Фаза 2: играть ход до тех пор, пока все игроки играют ход, в противном случае переключиться в фазу 3, положив := 0 ; Фаза 3: пока, положить := + 1 и играть ход, иначе переключиться в фазу 1.

Список литературы [1] Курс Массачусетского Технологического института.

http://web.mit.edu/14.12/www/index.html Лекции, задачи, образцы экзамена.

[2] Кинофильм «Игры разума» («beautiful mind»).

Абсолютно бесполезен при подготовке к экзамену по теории игр.

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

Книга с огромным количеством примеров дележа! Кэмп-Дэвидские соглашения и процедура дележа «подстраивающийся победитель». Ничего кроме умения решать уравнения вроде 6+7 = 8 не требуется.

[5] Gametheory.net. www.gametheory.net, Если захотелось поискать какие-то ресурсы по теории игр, то есть вероятность, что они там упомянуты. Хотя гугл и так рулит.

Парадоксы в теории вероятностей и математической статистике.

Куча парадоксов, занимательных задач и фактов! Элементарная теория вероятностей!

http://www.nes.ru/RUssIan/research/abstracts/2002/Danilov-r.htm Хороший курс для математиков на русском.

http://www.mccme.ru/mmmf-lectures/books/books/books.php Задача про разборчивую невесту, изложенная на школьном уровне.

Оригинальная книжка по теории игр для начинающих! Серьезно и с юмором! Есть доказательство теоремы о существовании равновесия по Нэшу в смешанных стратегиях, построенное на игре «Шестиугольники».

[10] Taylor Brams. An envy-free cake division protocol. 1995.

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

[11] Cramton. Курс лекций. Автор cramton.

Прекрасный курс с лекционными материалами и задачами для магистров.

[12] Francis Edward Su Elisha Peterson. Exact procedures for envy-free chore division. 1998.

http://citeseer.ist.psu.edu/22271.html Как поделить грязную работу, чтобы никто не завидовал другому?

[13] Chrusutuan Ewerhart. Chess-like games are dominance solvable in at most two steps. Games and Economic Behavior, 33:41–47.

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

[14] Thomas Ferguson and Christian Genest. Toetjes na. 2003.

Братья по очереди пытаются угадать, сколько стоил пирог. От пирога остался только один кусочек - он достанется тому, кто оказался ближе всех к истинной цене. http://www.math.

ucla.edu/~tom/papers/toetjes.pdf.

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

[16] Jowas. Politically incorrect math problems.

www.mai.liu.se/~jowas/Incorrect Здесь были политически некорректные задачи по теории игр, но они куда-то делись.

[17] Kockesen. Курс лекций, автор kockesen.

http://www.columbia.edu/~lk290/gameug.htm Еще один хороший курс. Лекции и задачи..

Можно рассматривать как более серьезное продолжение книги Osborne, Introduction to game Толстая книжка по микроэкономике (Тигр: говорят, можно использовать как талисман против злых духов), где есть несколько глав про теорию игр. Изложено занудно и аккуратно.

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

Introduction to game theory.

Лучший учебник по теории игр для начинающих. Много задач, широкий охват материала.

[22] Polisci. Курс лекций. Автор polisci.

Прекрасный курс с лекционными материалами и задачами для бакалавров. Наиболее соответствует курсу ГУ-ВШЭ в настоящее время. Единственный минус - он там темнит по-поводу perfect bayesian nash equilibrium.

[23] F. Squintani. Notes for non-cooperative game theory.

Заметки к лекциям магистерского уровня. На стадии разработки (похоже вечной), т.е. есть пропуски и небольшие ошибки. Стоит прочитать тем, кто хочет заниматься теорией игр. Автор убрал их из открытого доступа в сети. Может готовятся к публикации... Но кто ищет ;).

[24] F. Vega-Redondo. Economics and the Theory of Games.

Книжка с нестандартными обозначениями.

[25] Winkler. Games people don’t play.

Несколько красивейших задач по теории игр с решениями! Например, как получить пользу от посторонней информации?

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