El Farol Bar problem

The El Farol bar problem is a problem in game theory. Every Thursday night, a fixed population want to go have fun at the El Farol Bar, unless it's too crowded.

• If less than 60% of the population go to the bar, they'll all have more fun than if they stayed home.
• If more than 60% of the population go to the bar, they'll all have less fun than if they stayed home.

Everyone must decide at the same time whether to go or not, with no knowledge of others' choices.

Paradoxically, if everyone uses a deterministic pure strategy which is symmetric (same strategy for all players), it is guaranteed to fail no matter what it is. If the strategy suggests it will not be crowded, everyone will go, and thus it will be crowded; but if the strategy suggests it will be crowded, nobody will go, and thus it will not be crowded, but again no one will have fun. Better success is possible with a probabilistic mixed strategy. For the single-stage El Farol Bar problem, there exists a unique symmetric Nash equilibrium mixed strategy where all players choose to go to the bar with a certain probability, determined according to the number of players, the threshold for crowdedness, and the relative utility of going to a crowded or uncrowded bar compared to staying home. There are also multiple Nash equilibria in which one or more players use a pure strategy, but these equilibria are not symmetric.^[1] Several variants are considered in Game Theory Evolving by Herbert Gintis.^[2]

In some variants of the problem, the players are allowed to communicate before deciding to go to the bar. However, they are not required to tell the truth.

Named after a bar in Santa Fe, New Mexico, the problem was created in 1994 by W. Brian Arthur. However, under another name, the problem was formulated and solved dynamically six years earlier by B. A. Huberman and T. Hogg.^[3]

마이너리티 게임

변종은 프리부르 대학의 이청 장과 데미안 찰렛이 제안한 마이너리티 게임이다.^[4] 홀수 선수 각자가 턴마다 독자적으로 바이너리 선택을 해야 하는데, 승자는 결국 소수 편에 서게 되는 선수들이다. 엘 파롤 바 문제에서처럼 단일(대칭) 결정론적 전략은 평형을 줄 수 없지만, 혼합 전략의 경우, 고유한 대칭 나시 평형(각 플레이어가 50% 확률로 선택)이 있을 뿐 아니라, 다중 비대칭 평형도 있다.

다단계 협동 마이너리티 게임이 망가라이어 게임에서 등장했는데, 이 게임에서는 한 명의 선수만 남게 될 때까지 다수가 반복적으로 탈락되었다.^{[citation needed]}

콜카타 페이즈 레스토랑 문제

엘 파롤 바 문제의 또 다른 변종으로는,^{[5][6][7][8][9][10]} 노동자들이 점심을 간단히 먹을 수 있는 값싼 식당들의 이름을 딴 '콜카타 페이즈 레스토랑 문제'가 있다. 그러나 만약 그들이 선택한 식당이 너무 붐비면, 배고픔에 허덕이며 직장으로 돌아가야 할지도 모른다. 형식적으로, 많은 수의 N명의 플레이어가 N개의 많은 레스토랑 중 하나를 선택한다. 일반적으로 N = n(El Farol Bar 문제에서 n = 2(Stay-home 옵션 포함) 각 식당에서는 손님 1명이 임의로 점심식사(지급 = 1)를 제공하는 반면 다른 손님들은 모두 손해를 본다(지급 = 0). 선수들은 주어진 날 서로의 선택을 알지 못하지만 경기는 매일 반복되고, 모든 선수의 선택 이력은 누구나 이용할 수 있다. 최적으로 각 플레이어가 다른 식당을 선택하지만 이는 조정 없이는 사실상 불가능해 배고픈 고객들과 무인 식당들 모두 용량을 낭비하게 된다.^{[citation needed]}

전략은 총 급여 및/또는 식당에 참석한 비율(활용률)을 기준으로 평가한다. 활용률이 0.79에 이르는 선도적인 확률적 전략은 고객 개개인에게 어제와 같은 레스토랑을 선택할 확률 p(어제 그 레스토랑을 선택한 선수 수와 반대로 변화함)을 제공하는 동시에 동일한 확률을 가진 다른 레스토랑을 선택할 확률 p를 제공한다. 이는 결정론적 알고리즘이나 단순 무작위 선택(소음 거래자)보다 더 나은 결과로서 활용률 분율은 _e1 - / 0 0.63이다.^{[citation needed]}

비슷한 문제로 지역마다 병원 침대가 있지만 환자들은 자기 지역 밖 명문병원에 가고 싶어 한다. 하지만, 너무 많은 환자들이 명문 병원에 간다면, 어떤 사람들은 병원 침대를 전혀 얻지 못하는 반면, 사용되지 않는 침대는 지역 병원에서 추가로 낭비한다.^{[citation needed]}

참조

추가 읽기

• Arthur, W. Brian (1994). "Inductive Reasoning and Bounded Rationality" (PDF). American Economic Review: Papers and Proceedings. 84: 406–411. Retrieved 2014-12-13.

외부 링크

• 마이너리티 게임 입문 안내서
• 마이너리티 게임(대중화 계정)
• 마이너리티 게임 arxiv.org
• 뉴멕시코 주 산타페의 엘 파롤 바
• JABM(Java Agent-Based Modeling Toolkit)을 사용한 Java의 El Farol Bar 문제
• Kolkata Paise 레스토랑(KPR) 문제: 울프램 데모