Авинаш Диксит - Стратегические игры

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). Может ли исход, указанный в фильме в качестве равновесия Нэша (когда все молодые люди подойдут к брюнеткам), быть действительно равновесием Нэша в данной игре?

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

a)

b)

c)

b)

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

U3.Как и в упражнении S3, используйте метод минимакса для поиска равновесий Нэша в играх с нулевой суммой, найденных в упражнении U2.

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

a)

b)

c)

b)

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

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

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

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

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

U8. Битва в море Бисмарка (по названию моря в юго-западной части Тихого океана, отделяющего архипелаг Бисмарка от Папуа — Новой Гвинеи) представляла собой морское сражение между Соединенными Штатами и Японией во время Второй мировой войны. В 1943 году японский адмирал получил приказ провести конвой кораблей в Новую Гвинею. Ему предстояло сделать выбор между дождливым северным маршрутом и более солнечным южным, каждый из которых требовал трех дней плавания. Американцы знали об отплытии конвоя и хотели послать вслед за ним бомбардировщики, но им не было известно, по какому пути отправится конвой. Американцам пришлось послать самолеты-разведчики на поиски конвоя, но их хватало только на изучение одного маршрута за один раз. И американцам, и японцам приходилось принимать решения, не имея никакой информации о планах другой стороны.

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