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

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

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 asymmetric 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.[ citation needed ]

Kolkata Paise Restaurant Problem

Another variant of the El Farol Bar problem is the Kolkata Paise Restaurant Problem (KPR), [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.[ citation needed ]

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. [11] 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. [12] Increased utilization for customers having allowance for local optimization search using Traveling Salesman Problem type algorithms have also been studied. [13] Extensions of KPR for on-call car hire problems have been explored in. [14] [15] Stability of the KPR, induced by the introduction of dining clubs have also studied. [16]

Extensions to quantum games for three player KPR have been studied; [17] [18] see [19] for a recent review.

Related Research Articles

<span class="mw-page-title-main">Quantum computing</span> Technology that uses quantum mechanics

A quantum computer is a computer that takes advantage of quantum mechanical phenomena.

In quantum computing, a quantum algorithm is an algorithm that runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a problem, where each step or instruction can be performed on a classical computer. Similarly, a quantum algorithm is a step-by-step procedure, where each of the steps can be performed on a quantum computer. Although all classical algorithms can also be performed on a quantum computer, the term quantum algorithm is generally reserved for algorithms that seem inherently quantum, or use some essential feature of quantum computation such as quantum superposition or quantum entanglement.

Econophysics is a non-orthodox 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 combinatorial game theory, the strategy-stealing argument is a general argument that shows, for many two-player games, that the second player cannot have a guaranteed winning strategy. The strategy-stealing argument applies to any symmetric game in which an extra move can never be a disadvantage. A key property of a strategy-stealing argument is that it proves that the first player can win the game without actually constructing such a strategy. So, although it might prove the existence of a winning strategy, the proof gives no information about what that strategy is.

In lattice field theory, fermion doubling occurs when naively putting fermionic fields on a lattice, resulting in more fermionic states than expected. For the naively discretized Dirac fermions in Euclidean dimensions, each fermionic field results in identical fermion species, referred to as different tastes of the fermion. The fermion doubling problem is intractably linked to chiral invariance by the Nielsen–Ninomiya theorem. Most strategies used to solve the problem require using modified fermions which reduce to the Dirac fermion only in the continuum limit.

Quantum annealing (QA) is an optimization process for finding the global minimum of a given objective function over a given set of candidate solutions, by a process using quantum fluctuations. Quantum annealing is used mainly for problems where the search space is discrete with many local minima; such as finding the ground state of a spin glass or the traveling salesman problem. The term "quantum annealing" was first proposed in 1988 by B. Apolloni, N. Cesa Bianchi and D. De Falco as a quantum-inspired classical algorithm. It was formulated in its present form by T. Kadowaki and H. Nishimori in 1998 though an imaginary-time variant without quantum coherence had been discussed by A. B. Finnila, M. A. Gomez, C. Sebenik and J. D. Doll in 1994.

Quantum game theory is an extension of classical game theory to the quantum domain. It differs from classical game theory in three primary ways:

  1. Superposed initial states,
  2. Quantum entanglement of initial states,
  3. Superposition of strategies to be used on the initial states.

In theoretical physics, quantum nonlocality refers to the phenomenon by which the measurement statistics of a multipartite quantum system do not allow an interpretation with local realism. Quantum nonlocality has been experimentally verified under a variety of physical assumptions. Any physical theory that aims at superseding or replacing quantum theory should account for such experiments and therefore cannot fulfill local realism; quantum nonlocality is a property of the universe that is independent of our description of nature.

<span class="mw-page-title-main">D-Wave Systems</span> Canadian quantum computing company

D-Wave Quantum Systems Inc. is a Canadian quantum computing company, based in Burnaby, British Columbia. D-Wave claims to be the world's first company to sell computers that exploit quantum effects in their operation. D-Wave's early customers include Lockheed Martin, University of Southern California, Google/NASA and Los Alamos National Lab.

Adiabatic quantum computation (AQC) is a form of quantum computing which relies on the adiabatic theorem to perform calculations and is closely related to quantum annealing.

There is a diversity of views that propose interpretations of quantum mechanics. They vary in how many physicists accept or reject them. An interpretation of quantum mechanics is a conceptual scheme that proposes to relate the mathematical formalism to the physical phenomena of interest. The present article is about those interpretations which, independently of their intrinsic value, remain today less known, or are simply less debated by the scientific community, for different reasons.

Quantum pseudo-telepathy is the fact that in certain Bayesian games with asymmetric information, players who have access to a shared physical system in an entangled quantum state, and who are able to execute strategies that are contingent upon measurements performed on the entangled physical system, are able to achieve higher expected payoffs in equilibrium than can be achieved in any mixed-strategy Nash equilibrium of the same game by players without access to the entangled quantum system.

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.

<span class="mw-page-title-main">Bikas Chakrabarti</span>

Bikas Kanta Chakrabarti (born 14 December 1952 in Kolkata is an Indian physicist. At present he is INSA Senior Scientist at the Saha Institute of Nuclear Physics & Visiting Professor at the Indian Statistical Institute, Kolkata, India.

Kinetic exchange models are multi-agent dynamic models inspired by the statistical physics of energy distribution, which try to explain the robust and universal features of income/wealth distributions.

Quantum cryptography is the science of exploiting quantum mechanical properties to perform cryptographic tasks. The best known example of quantum cryptography is quantum key distribution, which offers an information-theoretically secure solution to the key exchange problem. The advantage of quantum cryptography lies in the fact that it allows the completion of various cryptographic tasks that are proven or conjectured to be impossible using only classical communication. For example, it is impossible to copy data encoded in a quantum state. If one attempts to read the encoded data, the quantum state will be changed due to wave function collapse. This could be used to detect eavesdropping in quantum key distribution (QKD).

Quantum Moves is an online citizen science simulation video game where players move quantum atoms. The game is part of the ScienceAtHome umbrella project, developed by AU Ideas Center for Community Driven Research (CODER). CODER aims to merge theoretical and experimental quantum research with online community efforts to explore the potential for online citizen science in this otherwise highly specialized field.

Quantum refereed game in quantum information processing is a class of games in the general theory of quantum games. It is played between two players, Alice and Bob, and arbitrated by a referee. The referee outputs the pay-off for the players after interacting with them for a fixed number of rounds, while exchanging quantum information.

<span class="mw-page-title-main">Quantum machine learning</span> Interdisciplinary research area at the intersection of quantum physics and machine learning

Quantum machine learning is the integration of quantum algorithms within machine learning programs.

Quantum optimization algorithms are quantum algorithms that are used to solve optimization problems. Mathematical optimization deals with finding the best solution to a problem from a set of possible solutions. Mostly, the optimization problem is formulated as a minimization problem, where one tries to minimize an error which depends on the solution: the optimal solution has the minimal error. Different optimization techniques are applied in various fields such as mechanics, economics and engineering, and as the complexity and amount of data involved rise, more efficient ways of solving optimization problems are needed. Quantum computing may allow problems which are not practically feasible on classical computers to be solved, or suggest a considerable speed up with respect to the best known classical algorithm.

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. Vol. 6. Princeton University Press. p. 134. ISBN   978-0-691-14051-3.
  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. S2CID   53310941.
  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. PMID   22463162. S2CID   26159915.
  8. ↑ Frédéric Abergel; Bikas K. Chakrabarti; Anirban Chakraborti; Asim Ghosh (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.
  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. S2CID   42076636.
  10. ↑ Bikas K Chakrabarti; Arnab Chatterjee; Asim Ghosh; Sudip Mukherjee; Boaz Tamir (27 July 2017). Econophysics of the Kolkata Restaurant Problem and Related Games: Classical and Quantum Strategies for Multi-agent, Multi-choice Repetitive Games. Springer. ISBN   978-3-319-61351-2.
  11. ↑ A. Ghosh; A. Chatterjee; M. Mitra; B. K. Chakrabarti (2010). "Statistics of the Kolkata Paise Restaurant problem". New Journal of Physics. 12 (7): 075033. arXiv: 1003.2103 . doi: 10.1088/1367-2630/12/7/075033 .
  12. ↑ A. Sinha; B. K. Chakrabarti (2020). "Phase transition in the Kolkata Paise Restaurant problem". Chaos. 30 (8): 083116. arXiv: 1905.13206 . doi:10.1063/5.0004816.
  13. ↑ K. Kastampolidou; C. Papalitsas; T. Andronikos (2022). "The Distributed Kolkata Paise Restaurant Game". Games. 13 (3): 33. doi: 10.3390/g13030033 .
  14. ↑ L. Martin (2017). "Extending Kolkata Paise Restaurant problem to dynamic matching in mobility markets". Junior Manag. Sci. 4: 1–34. doi:10.5282/jums/v4i1pp1-34.
  15. ↑ L. Martin; P. Karaenke (2017). The vehicle for hire problem: a generalized Kolkata Paise Restaurant problem; Proc. Workshop on Information Technology and Systems (PDF).
  16. ↑ A. Harlalka; A. Belmonte; C. Griffin (2023). "Stability of dining clubs in the Kolkata Paise Restaurant Problem with and without cheating". Physica A. 620: 128767. arXiv: 2302.14142 . doi:10.1016/j.physa.2023.128767.
  17. ↑ P. Sharif; H. Heydari (2012). "Strategies in a symmetric quantum Kolkata restaurant problem". AIP Conference Proceedings. 1508: 492–496. arXiv: 1212.6727 . doi:10.1063/1.4773171.
  18. ↑ M. Ramzan (2013). "Three-player quantum Kolkata restaurant problem under decoherence". Quantum Inform. Process. 12: 577. arXiv: 1111.3913 . doi:10.1007/s11128-012-0405-8.
  19. ↑ B. K. Chakrabarti; A. Rajak; A. Sinha (2022). "Stochastic Learning in Kolkata Paise Restaurant Problem: Classical and Quantum Strategies". Front. Artif. Intell. 5: 874061. doi: 10.3389/frai.2022.874061 . PMC   9181993 .

Further reading

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.