El Farol Bar problem

Last updated
El Farol located on Canyon Road, Santa Fe, New Mexico El Farol Restaurant and Cantina, Santa Fe NM.jpg
El Farol located on Canyon Road, Santa Fe, New Mexico

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.

Contents

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 probablistic 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.

Based on 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]

Minority game

A variant is the Minority Game proposed by Yi-Cheng Zhang and Damien Challet from the University of Fribourg. [4] An odd number of players each must make a binary choice independently at each turn, and the winners are those players who end up on the minority side. As in the El Farol Bar problem, no single (symmetric) deterministic strategy can give an equilibrium, but for mixed strategies there is a unique symmetric Nash equilibrium (each player chooses with 50% probability), as well as multiple non-symmetric equilibria.

A multi-stage, cooperative Minority Game was featured in the manga Liar Game , in which the majority was repeatedly eliminated until only one player was left.

Kolkata Paise Restaurant Problem

Another variant of the El Farol Bar problem is the Kolkata Paise Restaurant Problem, [5] [6] [7] [8] [9] [10] named for the many cheap restaurants where laborers can grab a quick lunch, but may have to return to work hungry if their chosen restaurant is too crowded. Formally, a large number N of players each choose one of a large number n of restaurants, typically N = n (while in the El Farol Bar Problem, n = 2, including the stay-home option). At each restaurant, one customer at random is served lunch (payoff = 1) while all others lose (payoff = 0). The players do not know each others' choices on a given day, but the game is repeated daily, and the history of all players' choices is available to everyone. Optimally, each player chooses a different restaurant, but this is practically impossible without coordination, resulting in both hungry customers and unattended restaurants wasting capacity.

Strategies are evaluated based on their aggregate payoff and/or the proportion of attended restaurants (utilization ratio). A leading stochastic strategy, with utilization ~0.79, gives each customer a probability p of choosing the same restaurant as yesterday (p varying inversely with the number of players who chose that restaurant yesterday), while choosing among other restaurants with uniform probability. This is a better result than deterministic algorithms or simple random choice (noise trader), with utilization fraction 1 - 1/e ≈ 0.63.

In a similar problem, there are hospital beds in every locality, but patients are tempted to go to prestigious hospitals out of their district. However, if too many patients go to a prestige hospital, some get no hospital bed at all, while additionally wasting the unused beds at their local hospitals.

Related Research Articles

Game theory The study of mathematical models of strategic interaction between rational decision-makers

Game theory is the study of mathematical models of strategic interaction among rational decision-makers. It has applications in all fields of social science, as well as in logic, systems science and computer science. Originally, it addressed zero-sum games, in which each participant's gains or losses are exactly balanced by those of the other participants. Today, game theory applies to a wide range of behavioral relations, and is now an umbrella term for the science of logical decision making in humans, animals, and computers.

In game theory and economic theory, a zero-sum game is a mathematical representation of a situation in which each participant's gain or loss of utility is exactly balanced by the losses or gains of the utility of the other participants. If the total gains of the participants are added up and the total losses are subtracted, they will sum to zero. Thus, cutting a cake, where taking a larger piece reduces the amount of cake available for others as much as it increases the amount available for that taker, is a zero-sum game if all participants value each unit of cake equally.

In game theory, the Nash equilibrium, named after the mathematician John Forbes Nash Jr., is a proposed solution of a non-cooperative game involving two or more players in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only his own strategy.

Econophysics is a heterodox interdisciplinary research field, applying theories and methods originally developed by physicists in order to solve problems in economics, usually those including uncertainty or stochastic processes and nonlinear dynamics. Some of its application to the study of financial markets has also been termed statistical finance referring to its roots in statistical physics. Econophysics is closely related to social physics.

In game theory, the best response is the strategy which produces the most favorable outcome for a player, taking other players' strategies as given. The concept of a best response is central to John Nash's best-known contribution, the Nash equilibrium, the point at which each player in a game has selected the best response to the other players' strategies.

In game theory, coordination games are a class of games with multiple pure strategy Nash equilibria in which players choose the same or corresponding strategies.

In game theory, a player's strategy is any of the options which he or she chooses in a setting where the outcome depends not only on their own actions but on the actions of others. A player's strategy will determine the action which the player will take at any stage of the game.

In game theory, the stag hunt is a game that describes a conflict between safety and social cooperation. Other names for it or its variants include "assurance game", "coordination game", and "trust dilemma". Jean-Jacques Rousseau described a situation in which two individuals go out on a hunt. Each can individually choose to hunt a stag or hunt a hare. Each player must choose an action without knowing the choice of the other. If an individual hunts a stag, they must have the cooperation of their partner in order to succeed. An individual can get a hare by himself, but a hare is worth less than a stag. This has been taken to be a useful analogy for social cooperation, such as international agreements on climate change.

Backward induction is the process of reasoning backwards in time, from the end of a problem or situation, to determine a sequence of optimal actions. It proceeds by first considering the last time a decision might be made and choosing what to do in any situation at that time. Using this information, one can then determine what to do at the second-to-last time of decision. This process continues backwards until one has determined the best action for every possible situation at every point in time. It was first used by Zermelo in 1913, to prove that chess has pure optimal strategies.

<i>Aranyer Din Ratri</i> 1970 film by Satyajit Ray

Aranyer Din Ratri is an Indian Bengali adventure drama film released in 1970, written and directed by Satyajit Ray. It is based upon the Bengali novel of the same name by Sunil Gangopadhyay. It was one of the earliest films to employ the literary technique of the carnivalesque. The film was nominated for the Golden Bear for Best Film at the 20th Berlin International Film Festival. A sequel Abar Aranye directed by Goutam Ghose was released in 2003.

A Blotto game, Colonel Blotto game, or divide-a-dollar game is a type of two-person zero-sum game in which the players are tasked to simultaneously distribute limited resources over several objects. In the classic version of the game, the player devoting the most resources to a battlefield wins that battlefield, and the gain is then equal to the total number of battlefields won.

In game theory, a subgame perfect equilibrium is a refinement of a Nash equilibrium used in dynamic games. A strategy profile is a subgame perfect equilibrium if it represents a Nash equilibrium of every subgame of the original game. Informally, this means that if the players played any smaller game that consisted of only one part of the larger game, their behavior would represent a Nash equilibrium of that smaller game. Every finite extensive game with perfect recall has a subgame perfect equilibrium.

Quantal response equilibrium (QRE) is a solution concept in game theory. First introduced by Richard McKelvey and Thomas Palfrey, it provides an equilibrium notion with bounded rationality. QRE is not an equilibrium refinement, and it can give significantly different results from Nash equilibrium. QRE is only defined for games with discrete strategies, although there are continuous-strategy analogues.

Risk dominance and payoff dominance are two related refinements of the Nash equilibrium (NE) solution concept in game theory, defined by John Harsanyi and Reinhard Selten. A Nash equilibrium is considered payoff dominant if it is Pareto superior to all other Nash equilibria in the game. When faced with a choice among equilibria, all players would agree on the payoff dominant equilibrium since it offers to each player at least as much payoff as the other Nash equilibria. Conversely, a Nash equilibrium is considered risk dominant if it has the largest basin of attraction. This implies that the more uncertainty players have about the actions of the other player(s), the more likely they will choose the strategy corresponding to it.

In game theory, an epsilon-equilibrium, or near-Nash equilibrium, is a strategy profile that approximately satisfies the condition of Nash equilibrium. In a Nash equilibrium, no player has an incentive to change his behavior. In an approximate Nash equilibrium, this requirement is weakened to allow the possibility that a player may have a small incentive to do something different. This may still be considered an adequate solution concept, assuming for example status quo bias. This solution concept may be preferred to Nash equilibrium due to being easier to compute, or alternatively due to the possibility that in games of more than 2 players, the probabilities involved in an exact Nash equilibrium need not be rational numbers.

Algorithmic game theory is an area in the intersection of game theory and computer science, with the objective of understanding and design of algorithms in strategic environments.

In algorithmic game theory, a succinct game or a succinctly representable game is a game which may be represented in a size much smaller than its normal form representation. Without placing constraints on player utilities, describing a game of players, each facing strategies, requires listing utility values. Even trivial algorithms are capable of finding a Nash equilibrium in a time polynomial in the length of such a large input. A succinct game is of polynomial type if in a game represented by a string of length n the number of players, as well as the number of strategies of each player, is bounded by a polynomial in n.

Bikas Kanta Chakrabarti is an Indian physicist. Since January 2018, he is emeritus professor of physics at the Saha Institute of Nuclear Physics, Kolkata, India.

Mertens stability is a solution concept used to predict the outcome of a non-cooperative game. A tentative definition of stability was proposed by Elon Kohlberg and Jean-François Mertens for games with finite numbers of players and strategies. Later, Mertens proposed a stronger definition that was elaborated further by Srihari Govindan and Mertens. This solution concept is now called Mertens stability, or just stability.

References

  1. Whitehead, Duncan (2008-09-17). "The El Farol Bar Problem Revisited: Reinforcement Learning in a Potential Game" (PDF). University of Edinburgh School of Economics . Retrieved 2014-12-13.
  2. Gintis, Herbert (2009). "Game Theory Evolving". 6 (24). Princeton University Press: 134.Cite journal requires |journal= (help)
  3. "The Ecology of Computation", Studies in Computer Science and Artificial Intelligence, North Holland publisher, page 99. 1988.
  4. D. Challet, M. Marsili, Y.-C. Zhang, Minority Games: Interacting Agents in Financial Markets, Oxford University Press, Oxford (2005)
  5. A. S. Chakrabarti, B. K. Chakrabarti, A. Chatterjee, M. Mitra (2009). "The Kolkata Paise Restaurant problem and resource utilization". Physica A. 388 (12): 2420–2426. arXiv: 0711.1639 . Bibcode:2009PhyA..388.2420C. doi:10.1016/j.physa.2009.02.039.CS1 maint: uses authors parameter (link)
  6. Asim Ghosh, Bikas K. Chakrabarti. "Kolkata Paise Restaurant (KPR) Problem". Wolfram Alpha.
  7. A. Ghosh, D. D. Martino, A. Chatterjee, M. Marsili, B. K. Chakrabarti (2012). "Phase transition in crowd dynamics of resource allocation". Physical Review E. 85 (2): 021116. arXiv: 1109.2541 . Bibcode:2012PhRvE..85b1116G. doi:10.1103/physreve.85.021116.CS1 maint: uses authors parameter (link)
  8. Frédéric Abergel, Bikas K. Chakrabarti, Anirban Chakraborti, Asim Ghosh (2013) (2013). Econophysics of Systemic Risk and Network Dynamics (PDF). New Economic Windows. Bibcode:2013esrn.book.....A. doi:10.1007/978-88-470-2553-0. ISBN   978-88-470-2552-3.CS1 maint: uses authors parameter (link)
  9. A. Chakraborti, D. Challet, A. Chatterjee, M. Marsili, Y.-C. Zhang, B. K. Chakrabarti (2015). "Statistical Mechanics of Competitive Resource Allocation using Agent-Based Models". Physics Reports. 552: 1–25. arXiv: 1305.2121 . Bibcode:2015PhR...552....1C. doi:10.1016/j.physrep.2014.09.006.CS1 maint: uses authors parameter (link)
  10. Bikas K Chakrabarti, Arnab Chatterjee, Asim Ghosh, Sudip Mukherjee, Boaz Tamir (2017). Econophysics of the Kolkata Restaurant Problem and Related Games: Classical and Quantum Strategies for Multi-agent, Multi-choice Repetitive Games. ISBN   978-3-319-61351-2.CS1 maint: uses authors parameter (link)

Further reading