Введение
Проблема бара Эль-Фароль — это задача теории игр. Каждый четверг вечером определённое число людей хотят пойти развлечься в бар «Эль-Фароль», если только там не будет слишком многолюдно. Если в бар пойдёт менее 60% населения, они получат больше удовольствия, чем если бы остались дома. Если в бар пойдёт более 60% населения, они получат меньше удовольствия, чем если бы остались дома. Каждый должен одновременно решить, идти или нет, не зная о выборе других. Парадоксально, но если каждый использует детерминированную чистую стратегию, которая симметрична (одинакова для всех игроков), она гарантированно провалится, независимо от того, какая это стратегия. Если стратегия предполагает, что в баре будет немноголюдно, все пойдут, и, следовательно, там станет многолюдно; но если стратегия предполагает, что в баре будет многолюдно, никто не пойдёт, и, следовательно, там будет немноголюдно, но опять же никто не получит удовольствия. Лучшие результаты возможны при использовании вероятностной смешанной стратегии. Для одноэтапной задачи El Farol Bar существует единственная симметричная стратегия равновесия Нэша, в которой все игроки выбирают идти в бар с определённой вероятностью, определяемой в зависимости от числа игроков, порога переполненности и относительной полезности посещения переполненного или не переполненного бара по сравнению с пребыванием дома. Существуют также множественные равновесия Нэша, в которых один или несколько игроков используют чистую стратегию, но эти равновесия не симметричны. Несколько вариантов рассматриваются в книге Герберта Гинтиса «Теория игр: эволюция». В некоторых вариантах задачи игрокам разрешается общаться перед тем, как решить, идти в бар или нет. Однако они не обязаны говорить правду. Задача названа в честь бара в Санта-Фе, штат Нью-Мексико, и была создана в 1994 году У. Брайаном Артуром. Однако под другим названием эта задача была сформулирована и решена динамически за шесть лет до этого Б. А. Хуберманом и Т. Хоггом.
Малочисленная игра
Вариантом является игра меньшинств, предложенная И Чен Чжаном и Дэмиеном Шале из Университета Фрибурга. Нечётное число игроков на каждом ходу независимо друг от друга должно сделать один из двух возможных выборов, а победителями становятся игроки, оказавшиеся в меньшинстве. Как и в задаче об El Farol Bar, ни одна (симметричная) детерминированная стратегия не может привести к равновесию, однако для смешанных стратегий существует единственное симметричное равновесие Нэша (каждый игрок выбирает с вероятностью 50%), а также множество асимметричных равновесий. Многоэтапная, кооперативная игра меньшинств была изображена в манге Liar Game, где игроки, составляющие большинство, последовательно исключались, пока не оставался только один участник.
Проблема ресторана в Калькутте
Другой вариант проблемы El Farol Bar — это проблема ресторана в Калькутте (KPR), названная в честь многочисленных дешевых ресторанов, где рабочие могут быстро пообедать, но рискуют вернуться на работу голодными, если выбранный ресторан окажется слишком переполненным. Формально, большое число игроков N выбирает один из большого числа ресторанов n, обычно N = n (в то время как в проблеме бара Эль-Фароль n = 2, включая возможность остаться дома). В каждом ресторане случайным образом один посетитель получает обед (выигрыш = 1), а все остальные остаются без обеда (выигрыш = 0). Игроки не знают о выборе друг друга в конкретный день, но игра повторяется ежедневно, и история выбора всех игроков доступна каждому. Оптимально, чтобы каждый игрок выбирал разный ресторан, но это практически невозможно без координации, что приводит к голодным посетителям и пустующим ресторанам, теряющим свою пропускную способность. В аналогичной проблеме в каждом районе есть больничные койки, но пациенты стремятся попасть в престижные больницы за пределами своего района. Однако, если слишком много пациентов обращаются в престижную больницу, некоторые из них не получают койку вообще, при этом остаются незадействованными койки в местных больницах. Стратегии оцениваются на основе их совокупного выигрыша и/или доли посещенных ресторанов (коэффициент использования). Ведущая стохастическая стратегия, обеспечивающая коэффициент использования около 0,79, предоставляет каждому посетителю вероятность p выбрать тот же ресторан, что и вчера (p обратно пропорциональна числу игроков, выбравших этот ресторан вчера), при этом выбор среди других ресторанов осуществляется с равной вероятностью. Это лучший результат, чем детерминированные алгоритмы или случайный выбор (шумовой трейдер), с коэффициентом использования 1 - 1/e ≈ 0,63. Также изучалось повышение коэффициента использования за счет предоставления клиентам возможности локального поиска с использованием алгоритмов типа задачи коммивояжера. Расширения KPR для задач аренды автомобилей по запросу были исследованы в [укажите источник]. Стабильность KPR, обусловленная введением обеденных клубов, также изучалась. Исследовались расширения для квантовых игр для KPR с тремя игроками; см. [укажите источник] для недавнего обзора.