Упражнения с решениями

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

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

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

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

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

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

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

S5. Проанализируйте следующую таблицу игры:

a) Есть ли доминирующая стратегия у Ровены либо у Колина? Объясните, почему есть или нет.

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

c) Разрешима ли эта игра по доминированию? Объясните, почему да или нет.

d) Найдите в ней равновесие (или равновесия) Нэша.

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

S7. Пожилой даме нужна помощь, чтобы перейти улицу. Для этого достаточно одного человека; не имеет смысла привлекать больше людей. Мы с вами находимся поблизости и можем помочь, причем одновременно должны решить, стоит ли это делать. Каждый из нас получит удовольствие с выигрышем 3 единицы, если все разрешится благополучно (независимо от того, кто ее переведет). Однако именно тому, кто непосредственно поможет даме, это обойдется в 1 единицу — такова ценность нашего времени, потраченного на оказание помощи. Если никто из игроков не оказывает помощь, выигрыш каждого будет равен нулю. Сформулируйте эту ситуацию в виде игры. Составьте таблицу выигрышей и найдите равновесия Нэша в чистых стратегиях.

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

a) Каковы равновесия Нэша в чистых стратегиях в этой игре?

b) Какая из игр, представленных в данной главе, больше всего напоминает эту игру? Объясните логику своих рассуждений.

S9. Предположим, два участника игрового шоу, Алекс и Боб, каждый по отдельности выбирают двери с номерами 1, 2, 3. Оба игрока получают призы, если их выбор совпадает, как показано в следующей таблице:

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

b) Рассмотрите несколько измененную игру, в которой варианты выбора — снова просто числа, но две ячейки таблицы с выигрышами 15, 15 теперь содержат выигрыши 25, 25. Какой ожидаемый (средний) выигрыш каждого игрока, если каждый из них подбросит монету, чтобы решить, выбрать вариант 2 или 3? Лучше ли это фокусировки на том, чтобы оба выбрали 1 в качестве фокального равновесия? Как вам следует учитывать риск того, что Алекс может сделать одно, а Боб — другое?

S10. У Марты три сына: Артуро, Бернардо и Карлос. Она находит разбитую лампу посреди гостиной и понимает, что это сделал кто-то из сыновей. На самом деле виновник произошедшего Карлос, но Марта об этом не знает. Она заинтересована скорее в том, чтобы выяснить истину, а не наказать ребенка, поэтому предлагает сыновьям сыграть в следующую игру.

Каждый из них напишет на листе бумаги свое имя, а также слова: «Да, это я разбил лампу» либо «Нет, я не разбивал лампу». Если хотя бы один ребенок признается, что разбил лампу, Марта даст по 2 доллара (обычную сумму карманных денег) каждому, кто скажет, что разбил лампу, и 5 долларов тому, кто будет утверждать, что не делал этого. Если все три сына откажутся сознаваться, ни один из них не получит карманных денег (то есть каждый получит 0 долларов).

a) Составьте таблицу игры. Пусть Артуро соответствует строка таблицы, Бернардо — столбец, а Карлосу — страница.

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

c) В этой игре множество равновесий Нэша. Какое из них вы назвали бы фокальной точкой?

S11. Рассмотрите игру, в которой на кону стоит приз в размере 30 долларов. В ней три участника — Ларри, Керли и Мо. Каждый из них может купить (или нет) билет стоимостью 15 или 30 долларов. Игроки делают выбор одновременно и независимо друг от друга. Затем, собрав информацию о решениях игроков по поводу покупки билетов, организатор игры присуждает приз. Если никто не купит билет, приз не присуждается. В противном случае приз вручается тому, кто купил самый дорогой билет, если такой человек всего один, и делится поровну между двумя или тремя игроками, если они купили самые дорогие билеты по одной цене. Представьте эту игру в стратегической форме, включив в нее Ларри в качестве игрока, которому соответствуют строки, Керли — столбцы, а Мо — страницы. Найдите все равновесия Нэша в чистых стратегиях.

S12. Анна и Брюс намерены взять напрокат фильм, но не могут решить, какой именно. Анна хочет комедию, в Брюс — драму. Они решают сделать выбор случайным образом, сыграв в игру «чет или нечет». На счет три каждый из них выбрасывает один или два пальца. Если сумма пальцев представляет собой четное число, побеждает Энн и они берут напрокат комедию, если нечетное, то выигрывает Брюс и они смотрят драму. Каждый игрок получает выигрыш 1 за победу и 0 за проигрыш в игре «чет или нечет».

a) Нарисуйте таблицу игры «чет или нечет».

b) Покажите, что в этой игре нет равновесия Нэша в чистых стратегиях.

S13. В фильме «Игры разума» Джон Нэш и трое его коллег по магистратуре, придя в бар, сталкиваются с дилеммой. В баре находятся четыре брюнетки и одна блондинка. Каждый молодой человек хочет подойти и привлечь внимание одной из девушек. Выигрыш каждого за блондинку составляет 10, за брюнетку — 5, а если кто-то вообще останется без девушки, то 0. Проблема в том, что, если сразу несколько парней подойдут к блондинке, она отвергнет их всех, после чего брюнетки тоже их отвергнут, поскольку не хотят быть вторыми в очереди. Таким образом, каждый игрок получит выигрыш 10 только в случае, если окажется единственным претендентом на внимание блондинки.

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

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

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

d) (дополнительное упражнение). Используйте результаты, полученные в пунктах а, b и c, чтобы обобщить анализ на ситуацию, когда в игре участвуют n молодых людей. Не пытайтесь строить n-мерную таблицу выигрышей, просто вычислите выигрыш одного игрока в случае, если k других игроков выберут блондинку и (n — k — 1) выберут брюнетку, при k = 0, 1… (n — 1). Может ли исход, указанный в фильме в качестве равновесия Нэша (когда все молодые люди подойдут к брюнеткам), быть действительно равновесием Нэша в данной игре?