Проблема с баром Эль-Фарол

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

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

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

Парадоксально, но если каждый использует детерминированную чистую стратегию , которая является симметричной (одна и та же стратегия для всех игроков), она гарантированно потерпит неудачу, какой бы она ни была. Если стратегия предполагает, что там не будет многолюдно, все пойдут, и, следовательно, там будет многолюдно; но если стратегия предполагает, что там будет многолюдно, никто не пойдет, и, следовательно, там не будет многолюдно, но опять-таки никому не будет весело. Больший успех возможен при использовании вероятностной смешанной стратегии . Для одноэтапной задачи «Бар Эль-Фарол» существует уникальная симметричная смешанная стратегия равновесия Нэша , в которой все игроки решают пойти в бар с определенной вероятностью, определяемой в зависимости от количества игроков, порога переполненности и относительной полезности. похода в переполненный или пустой бар по сравнению с пребыванием дома. Существуют также множественные равновесия Нэша, в которых один или несколько игроков используют чистую стратегию, но эти равновесия не симметричны. ^[1] Несколько вариантов рассматриваются в «Развитие теории игр» книге Герберта Гинтиса . ^[2]

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

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

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

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

Многоэтапная совместная игра меньшинства была представлена в манге « Игра лжецов» , в которой большинство неоднократно уничтожалось, пока не оставался только один игрок. ^{[ нужна ссылка ]}

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

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

Аналогичная проблема: больничные койки есть в каждом населенном пункте, но у пациентов возникает соблазн обратиться в престижные больницы за пределами своего района. Однако, если слишком много пациентов попадают в престижную больницу, некоторые вообще не получают больничных коек, а в местных больницах к тому же тратятся неиспользованные койки. ^[11] Стратегии оцениваются на основе их совокупной отдачи и/или доли посещаемых ресторанов (коэффициент использования). Ведущая стохастическая стратегия с коэффициентом использования ~0,79 дает каждому клиенту вероятность p выбора того же ресторана, что и вчера ( p меняется обратно пропорционально количеству игроков, выбравших этот ресторан вчера), при этом выбор среди других ресторанов осуществляется с одинаковой вероятностью. Это лучший результат, чем детерминированные алгоритмы или простой случайный выбор ( шумовой трейдер ), с коэффициентом использования 1 — ¹/ _е ≈ 0,63. ^[12] повышение эффективности использования для клиентов, имеющих возможность локального поиска по оптимизации с использованием алгоритмов типа «Коммивояжер» . Также было изучено ^[13] Расширения KPR для решения проблем с арендой автомобилей по вызову были изучены в . ^[14]^[15] Также изучалась стабильность КНР, вызванная введением клубов-ресторанов. ^[16]

Были изучены расширения квантовых игр для трех игроков KPR; ^[17]^[18] видеть ^[19] для недавнего обзора.

Ссылки

^ Уайтхед, Дункан (17 сентября 2008 г.). «Возвращение к проблеме с баром Эль Фарола: обучение с подкреплением в потенциальной игре» (PDF) . Школа экономики Эдинбургского университета . Проверено 13 декабря 2014 г.
^ Гинтис, Герберт (2009). Развитие теории игр . Том. 6. Издательство Принстонского университета . п. 134. ИСБН 978-0-691-14051-3 .
^ «Экология вычислений», Исследования в области компьютерных наук и искусственного интеллекта, издательство North Holland, стр. 99. 1988.
^ Д. Шалле, М. Марсили, Ю.-К. Чжан, Игры меньшинств: взаимодействующие агенты на финансовых рынках, Oxford University Press, Оксфорд (2005)
^ А.С. Чакрабарти; Б.К. Чакрабарти; А. Чаттерджи; М. Митра (2009). «Проблема ресторана Paise в Калькутте и использование ресурсов». Физика А. 388 (12): 2420–2426. arXiv : 0711.1639 . Бибкод : 2009PhyA..388.2420C . дои : 10.1016/j.physa.2009.02.039 . S2CID 53310941 .
^ Асим Гош, Бикас К. Чакрабарти. «Проблема ресторана Калькутта Пайсе (КПР)» . Вольфрам Альфа .
^ А. Гош; Д.Д. Мартино; А. Чаттерджи; М. Марсили; Б.К. Чакрабарти (2012). «Фазовый переход в динамике распределения ресурсов толпы». Физический обзор E . 85 (2): 021116.arXiv : 1109.2541 . Бибкод : 2012PhRvE..85b1116G . дои : 10.1103/physreve.85.021116 . ПМИД 22463162 . S2CID 26159915 .
^ Фредерик Абергель; Бикас К. Чакрабарти ; Анирбан Чакраборти; Асим Гош (2013). Эконофизика системного риска и сетевой динамики (PDF) . Новые экономические окна. Бибкод : 2013esrn.book.....A . дои : 10.1007/978-88-470-2553-0 . ISBN 978-88-470-2552-3 .
^ А. Чакраборти; Д. Шалле; А. Чаттерджи; М. Марсили; Ю.-К. Чжан; Б.К. Чакрабарти (2015). «Статистическая механика конкурентного распределения ресурсов с использованием агентных моделей». Отчеты по физике . 552 : 1–25. arXiv : 1305.2121 . Бибкод : 2015ФР...552....1С . дои : 10.1016/j.physrep.2014.09.006 . S2CID 42076636 .
^ Бикас К. Чакрабарти ; Арнаб Чаттерджи; Асим Гош; Судип Мукерджи; Боаз Тамир (27 июля 2017 г.). Эконофизика задачи ресторана в Калькутте и связанные с ней игры: классические и квантовые стратегии для многоагентных повторяющихся игр с множественным выбором . Спрингер. ISBN 978-3-319-61351-2 .
^ А. Гош; А. Чаттерджи; М. Митра; Б.К. Чакрабарти (2010). «Статистика проблемы ресторана Paise в Калькутте» . Новый журнал физики . 12 (7): 075033. arXiv : 1003.2103 . дои : 10.1088/1367-2630/12/7/075033 .
^ А. Синха; БК Чакрабарти (2020). «Фазовый переход в проблеме ресторана Paise в Калькутте». Хаос . 30 (8): 083116. arXiv : 1905.13206 . дои : 10.1063/5.0004816 .
^ К. Кастамполиду; К. Папалицас; Т. Андроникос (2022). «Распределенная ресторанная игра в Калькутте-Пайсе» . Игры . 13 (3): 33. дои : 10.3390/g13030033 .
^ Л. Мартин (2017). «Распространение проблемы ресторана Kolkata Paise на динамическое сопоставление на рынках мобильности». Младший менеджер. Наука . 4 : 1–34. дои : 10.5282/jums/v4i1pp1-34 .
^ Л. Мартин; П. Караенке (2017). Задача о найме автомобиля: обобщенная задача ресторана Kolkata Paise; Учеб. Семинар по информационным технологиям и системам (PDF) .
^ А. Харлалка; А. Бельмонте; К. Гриффин (2023). «Стабильность ресторанных клубов в ресторане Paise в Калькутте. Проблема с мошенничеством и без». Физика А. 620 : 128767. arXiv : 2302.14142 . дои : 10.1016/j.physa.2023.128767 .
^ П. Шариф; Х. Хейдари (2012). «Стратегии решения симметричной квантовой проблемы ресторана в Калькутте». Материалы конференции AIP . 1508 : 492–496. arXiv : 1212.6727 . дои : 10.1063/1.4773171 .
^ М. Рамзан (2013). «Задача квантового ресторана Калькутты для трех игроков в условиях декогеренции». Квантум Информ. Процесс . 12 : 577. arXiv : 1111.3913 . дои : 10.1007/s11128-012-0405-8 .
^ Б.К. Чакрабарти; А. Раджак; А. Синха (2022 г.). «Стохастическое обучение в задаче ресторана Paise в Калькутте: классические и квантовые стратегии» . Передний. Артиф. Интелл . 5 : 874061. doi : 10.3389/frai.2022.874061 . ПМК 9181993 .

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

Артур, В. Брайан (1994). «Индуктивное рассуждение и ограниченная рациональность» (PDF) . Американский экономический обзор: статьи и труды . 84 : 406–411. Архивировано из оригинала (PDF) 20 февраля 2015 г. Проверено 13 декабря 2014 г.

Внешние ссылки

Вводное руководство по игре меньшинства
Minority Games (аккаунт для популяризации)
Игра меньшинства на arxiv.org
Бар El Farol в Санта-Фе, Нью-Мексико
Проблема El Farol Bar в Java с использованием набора средств моделирования на основе агентов Java (JABM)
Ресторан Kolkata Paise (КНР) Проблема: демонстрации Wolfram

[1] Уайтхед, Дункан (17 сентября 2008 г.). «Возвращение к проблеме с баром Эль Фарола: обучение с подкреплением в потенциальной игре» (PDF) . Школа экономики Эдинбургского университета . Проверено 13 декабря 2014 г.

[2] Гинтис, Герберт (2009). Развитие теории игр . Том. 6. Издательство Принстонского университета . п. 134. ИСБН 978-0-691-14051-3 .

[3] «Экология вычислений», Исследования в области компьютерных наук и искусственного интеллекта, издательство North Holland, стр. 99. 1988.

[4] Д. Шалле, М. Марсили, Ю.-К. Чжан, Игры меньшинств: взаимодействующие агенты на финансовых рынках, Oxford University Press, Оксфорд (2005)

[5] А.С. Чакрабарти; Б.К. Чакрабарти; А. Чаттерджи; М. Митра (2009). «Проблема ресторана Paise в Калькутте и использование ресурсов». Физика А. 388 (12): 2420–2426. arXiv : 0711.1639 . Бибкод : 2009PhyA..388.2420C . дои : 10.1016/j.physa.2009.02.039 . S2CID 53310941 .

[6] Асим Гош, Бикас К. Чакрабарти. «Проблема ресторана Калькутта Пайсе (КПР)» . Вольфрам Альфа .

[7] А. Гош; Д.Д. Мартино; А. Чаттерджи; М. Марсили; Б.К. Чакрабарти (2012). «Фазовый переход в динамике распределения ресурсов толпы». Физический обзор E . 85 (2): 021116.arXiv : 1109.2541 . Бибкод : 2012PhRvE..85b1116G . дои : 10.1103/physreve.85.021116 . ПМИД 22463162 . S2CID 26159915 .

[8] Фредерик Абергель; Бикас К. Чакрабарти ; Анирбан Чакраборти; Асим Гош (2013). Эконофизика системного риска и сетевой динамики (PDF) . Новые экономические окна. Бибкод : 2013esrn.book.....A . дои : 10.1007/978-88-470-2553-0 . ISBN 978-88-470-2552-3 .

[9] А. Чакраборти; Д. Шалле; А. Чаттерджи; М. Марсили; Ю.-К. Чжан; Б.К. Чакрабарти (2015). «Статистическая механика конкурентного распределения ресурсов с использованием агентных моделей». Отчеты по физике . 552 : 1–25. arXiv : 1305.2121 . Бибкод : 2015ФР...552....1С . дои : 10.1016/j.physrep.2014.09.006 . S2CID 42076636 .

[10] Бикас К. Чакрабарти ; Арнаб Чаттерджи; Асим Гош; Судип Мукерджи; Боаз Тамир (27 июля 2017 г.). Эконофизика задачи ресторана в Калькутте и связанные с ней игры: классические и квантовые стратегии для многоагентных повторяющихся игр с множественным выбором . Спрингер. ISBN 978-3-319-61351-2 .

[11] А. Гош; А. Чаттерджи; М. Митра; Б.К. Чакрабарти (2010). «Статистика проблемы ресторана Paise в Калькутте» . Новый журнал физики . 12 (7): 075033. arXiv : 1003.2103 . дои : 10.1088/1367-2630/12/7/075033 .

[12] А. Синха; БК Чакрабарти (2020). «Фазовый переход в проблеме ресторана Paise в Калькутте». Хаос . 30 (8): 083116. arXiv : 1905.13206 . дои : 10.1063/5.0004816 .

[13] К. Кастамполиду; К. Папалицас; Т. Андроникос (2022). «Распределенная ресторанная игра в Калькутте-Пайсе» . Игры . 13 (3): 33. дои : 10.3390/g13030033 .

[14] Л. Мартин (2017). «Распространение проблемы ресторана Kolkata Paise на динамическое сопоставление на рынках мобильности». Младший менеджер. Наука . 4 : 1–34. дои : 10.5282/jums/v4i1pp1-34 .

[15] Л. Мартин; П. Караенке (2017). Задача о найме автомобиля: обобщенная задача ресторана Kolkata Paise; Учеб. Семинар по информационным технологиям и системам (PDF) .

[16] А. Харлалка; А. Бельмонте; К. Гриффин (2023). «Стабильность ресторанных клубов в ресторане Paise в Калькутте. Проблема с мошенничеством и без». Физика А. 620 : 128767. arXiv : 2302.14142 . дои : 10.1016/j.physa.2023.128767 .

[17] П. Шариф; Х. Хейдари (2012). «Стратегии решения симметричной квантовой проблемы ресторана в Калькутте». Материалы конференции AIP . 1508 : 492–496. arXiv : 1212.6727 . дои : 10.1063/1.4773171 .

[18] М. Рамзан (2013). «Задача квантового ресторана Калькутты для трех игроков в условиях декогеренции». Квантум Информ. Процесс . 12 : 577. arXiv : 1111.3913 . дои : 10.1007/s11128-012-0405-8 .

[19] Б.К. Чакрабарти; А. Раджак; А. Синха (2022 г.). «Стохастическое обучение в задаче ресторана Paise в Калькутте: классические и квантовые стратегии» . Передний. Артиф. Интелл . 5 : 874061. doi : 10.3389/frai.2022.874061 . ПМК 9181993 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

v т и Темы теории игр
Определения	Игра с пробками Кооперативная игра Определенность Эскалация обязательств Игра развернутой формы Победа первого и второго игрока Сложность игры Графическая игра Иерархия убеждений Информационный набор Игра в нормальной форме Предпочтение Последовательная игра Одновременная игра Выбор одновременного действия Решенная игра Краткая игра Конструкция механизма
Равновесие концепции	Байесовское коррелированное равновесие Байесовское равновесие Нэша Равновесие Бержа Основной Коррелированное равновесие Коалиционно-устойчивое равновесие Нэша Эпсилон-равновесие Эволюционно стабильная стратегия Равновесие Гиббса Устойчивое равновесие Мертенса Марковское совершенное равновесие Равновесие Нэша Парето-эффективность Идеальное байесовское равновесие Правильное равновесие Равновесие квантового ответа Практически идеальный баланс Доминирование риска Равновесие удовлетворенности Самоподтверждающееся равновесие Последовательное равновесие Значение Шепли Сильное равновесие Нэша Совершенство подигры Дрожащая рука, равновесие
Стратегии	Умиротворение Обратная индукция Затенение ставок Сговор Дешевый разговор Деэскалация Сдерживание Эскалация Прямая индукция Мрачный триггер Марковская стратегия Доминирующие стратегии Чистая стратегия Смешанная стратегия Аргумент о краже стратегии Око за око
Классы игр	Аукцион Проблема с переговорами Глобальная игра Непереходная игра Среднее поле игры n игроков игра для Идеальная информация Большая игра Пуассона Потенциальная игра Повторная игра Скрининговая игра Сигнальная игра Строго определенная игра Стохастическая игра Симметричная игра Игра с нулевой суммой
Игры	Идти шахматы Бесконечные шахматы Шашки Аукцион с полной оплатой Дилемма заключенного Игра-обмен подарками Необязательная дилемма заключенного Дилемма путешественника Координационная игра Курица игра многоножка Сигнальная игра Льюиса Дилемма волонтера Долларовый аукцион Битва полов Охота на оленя Соответствующие пенни Ультиматум игра Электронная почтовая игра Камень-ножницы-бумага Пиратская игра Диктатор игра Игра «Общественные блага» Блото игра Война на истощение Проблема с баром Эль-Фарол Ярмарочный отдел Ярмарка разрезания торта Бертран конкурс Конкурс Курно конкурс Штакельберга Тупик Дилемма закусочной Угадайте 2/3 от среднего Кун покер Торговая игра Нэша Индукционные головоломки Доверительная игра Игра Принцесса и монстр Проблема встречи
Теоремы	Теорема согласия Ауманна Народная теория Теорема о минимаксе Nash's theorem Теорема Негамакса Теорема очистки Принцип откровения Теорема Спрэга – Гранди Теорема Цермело
Ключ цифры	Альберт В. Такер Амос Тверски Антуан Огюстен Курно Ариэль Рубинштейн Клод Шеннон Дэниел Канеман Дэвид К. Левин Дэвид М. Крепс Дональд Б. Гиллис Дрю Фуденберг Эрик Маскин Гарольд В. Кун Герберт Саймон Эрве Мулен Джон Конвей Жан Тироль Жан-Франсуа Мертенс Дженнифер Тур Чейес Джон Харсаньи Джон Мейнард Смит Джон Нэш Джон фон Нейман Кеннет Эрроу Кеннет Бинмор Леонид Гурвич Ллойд Шепли Мелвин Дрешер Меррилл М. Флуд Ольга Бондарева Оскар Моргенштерн Пол Милгром Пейтон Янг Райнхард Зельтен Роберт Аксельрод Роберт Ауманн Роберт Б. Уилсон Роджер Майерсон Сэмюэл Боулз Сюзанна Скотчмер Томас Шеллинг Уильям Викри
Разнообразный	Альфа-бета-обрезка Ограниченная рациональность Комбинаторная теория игр Анализ конфронтации сотрудничество Эволюционная теория игр Глоссарий теории игр Список теоретиков игр Список игр по теории игр Безвыходная ситуация Топологическая игра Трагедия общего пользования