Проблема с баром Эль Фарол - El Farol Bar problem

Эль Фарол расположен на Каньон-роуд, Санта-Фе, Нью-Мексико

В Проблема с баром Эль Фарол проблема в теория игры. Каждый четверг вечером определенное население хочет развлечься в баре El Farol, если только он не слишком переполнен.

  • Если менее 60% населения пойдет в бар, им всем будет веселее, чем если бы они остались дома.
  • Если более 60% населения пойдет в бар, им всем будет меньше веселья, чем если бы они остались дома.

Каждый должен решить в то же время идти или нет, не зная о выборе других.

Парадоксально, но если каждый использует детерминированный чистая стратегия который является симметричным (одна и та же стратегия для всех игроков), он гарантированно потерпит неудачу, какой бы он ни был. Если стратегия предполагает, что он не будет переполнен, все пойдут, и, следовательно, он буду быть переполненным; но если стратегия предполагает, что он будет переполнен, никто не пойдет, и поэтому он будет нет будет многолюдно, но опять же никто не повеселится. Лучший успех возможен с вероятностным смешанная стратегия. Для одноэтапной задачи El Farol Bar существует единственная симметричная равновесие по Нэшу смешанная стратегия, при которой все игроки решают пойти к барной стойке с определенной вероятностью, определяемой в зависимости от количества игроков, порога переполненности и относительной полезности посещения переполненного или немноголюдного бара по сравнению с пребыванием дома. Также существует несколько равновесий по Нэшу, в которых один или несколько игроков используют чистую стратегию, но эти равновесия не являются симметричными.[1] Рассмотрены несколько вариантов. Развитие теории игр пользователя Герберт Гинтис.[2]

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

На основе бара в Санта-Фе, Нью-Мексико, проблема была создана в 1994 г. В. Брайан Артур. Однако под другим названием проблема была сформулирована и динамически решена шестью годами ранее Б. А. Хуберманом и Т. Хоггом.[3]

Игра меньшинств

Вариант - это Игра меньшинств предложенный И-Ченг Чжаном и Дэмиеном Чалле из Фрибургский университет.[4] Нечетное количество игроков каждый должен делать бинарный выбор независимо на каждом ходу, и победителями становятся те игроки, которые оказываются в меньшинстве. Как и в задаче бара Эль Фарола, ни одна (симметричная) детерминированная стратегия не может дать равновесие, но для смешанных стратегий существует уникальное симметричное равновесие по Нэшу (каждый игрок выбирает с вероятностью 50%), а также несколько несимметричных равновесий.

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

Проблема с рестораном в Калькутте Пайсе

Другой вариант проблемы с баром El Farol - это Проблема с рестораном в Калькутте Пайсе,[5][6][7][8][9][10] назван в честь множества дешевых ресторанов, где рабочие могут быстро перекусить, но, возможно, придется вернуться на работу голодными, если выбранный ими ресторан слишком переполнен. Формально большое количество N игроков каждый выбирает одного из большого числа п ресторанов, обычно N = п (находясь в задаче о баре Эль Фарол, п = 2, включая вариант проживания дома). В каждом ресторане обед подают одному случайному клиенту (заплатить = 1), а все остальные проигрывают (заплатить = 0). Игроки не знают выбора друг друга в данный день, но игра повторяется ежедневно, и история выбора всех игроков доступна каждому. Оптимально, каждый игрок выбирает другой ресторан, но это практически невозможно без координации, в результате чего как голодные клиенты, так и оставленные без присмотра рестораны теряют вместимость.

Стратегии оцениваются на основе их совокупной отдачи и / или доли посещаемых ресторанов (коэффициент использования). Ведущая стохастическая стратегия с коэффициентом использования ~ 0,79 дает каждому покупателю вероятность п выбрать тот же ресторан, что и вчера (п изменяется обратно пропорционально количеству игроков, выбравших этот ресторан вчера), при выборе среди других ресторанов с одинаковой вероятностью. Это лучший результат, чем детерминированные алгоритмы или простой случайный выбор (шумовой трейдер ), с долей использования 1 - 1/е ≈ 0.63.

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

Рекомендации

  1. ^ Уайтхед, Дункан (17 сентября 2008 г.). «Повторение проблемы бара Эль-Фарола: обучение с подкреплением в потенциальной игре» (PDF). Школа экономики Эдинбургского университета. Получено 2014-12-13.
  2. ^ Гинтис, Герберт (2009). «Развитие теории игр». 6 (24). Princeton University Press: 134. Цитировать журнал требует | журнал = (Помогите)
  3. ^ «Экология вычислений», Исследования в области компьютерных наук и искусственного интеллекта, издательство Северной Голландии, стр. 99. 1988.
  4. ^ Д. Шале, М. Марсили, Ю.-К. Чжан, Игры меньшинств: взаимодействующие агенты на финансовых рынках, Oxford University Press, Оксфорд (2005)
  5. ^ А. С. Чакрабарти, Б. К. Чакрабарти, А. Чаттерджи, М. Митра (2009). «Проблема ресторана Калькутта Пайсе и использование ресурсов». Physica A. 388 (12): 2420–2426. arXiv:0711.1639. Bibcode:2009PhyA..388.2420C. Дои:10.1016 / j.physa.2009.02.039.CS1 maint: использует параметр авторов (ссылка на сайт)
  6. ^ Асим Гош, Бикас К. Чакрабарти. «Проблема с рестораном Kolkata Paise (KPR)». вольфрам Альфа.
  7. ^ А. Гош, Д. Д. Мартино, А. Чаттерджи, М. Марсили, Б. К. Чакрабарти (2012). «Фазовый переход в динамике распределения ресурсов». Физический обзор E. 85 (2): 021116. arXiv:1109.2541. Bibcode:2012PhRvE..85b1116G. Дои:10.1103 / Physreve.85.021116.CS1 maint: использует параметр авторов (ссылка на сайт)
  8. ^ Фредерик Абергель, Бикас К. Чакрабарти, Анирбан Чакраборти, Асим Гош (2013) (2013). Эконофизика системного риска и сетевой динамики (PDF). Новые экономические окна. Bibcode:2013esrn.book ..... A. Дои:10.1007/978-88-470-2553-0. ISBN  978-88-470-2552-3.CS1 maint: использует параметр авторов (ссылка на сайт)
  9. ^ А. Чакраборти, Д. Чалле, А. Чаттерджи, М. Марсили, Я.-К. Чжан, Б. К. Чакрабарти (2015). «Статистическая механика конкурентного распределения ресурсов с использованием агентных моделей». Отчеты по физике. 552: 1–25. arXiv:1305.2121. Bibcode:2015ФР ... 552 .... 1С. Дои:10.1016 / j.physrep.2014.09.006.CS1 maint: использует параметр авторов (ссылка на сайт)
  10. ^ Бикас К. Чакрабарти, Арнаб Чаттерджи, Асим Гош, Судип Мукерджи, Боаз Тамир (2017). Эконофизика проблемы ресторана Калькутты и связанных игр: классические и квантовые стратегии для многоагентных повторяющихся игр с множественным выбором. ISBN  978-3-319-61351-2.CS1 maint: использует параметр авторов (ссылка на сайт)

дальнейшее чтение

внешняя ссылка