Convergence properties of the El Farol bar problem with social learning

The El Farol Bar problem proposed by Arthur in [1] is a study of economic system. Though Arthur's main objective was to highlight how humans are more apt in making inductive reasoning for complex decision making process rather than deductive reasoning; the model has been widely used in analysis of economic systems, particularly when congestion issues arise. The original model is described as follows. A population of agents have to decide every week whether to go to the El Farol bar or not. If many agents attend the bar, for example more that 60%, it will be overcrowded and that results unpleasant experience for the attendees. The decision made by each agent is purely individual and based on a random subset of predictors. Arthur's simulation results showed that the system kept fluctuating near the 60% threshold and the agents divided themselves into a 60/40 ratio of bar attendance. In this research, we are interested in interaction-based decision making processes, which are lacking in Arthur's model. Several attempts have been made in the literature to introduce such interaction processes or communication mechanisms to the original model. Those extended models often involve a xed network/neighborhood structure over the agents and the system dynamics were mainly studied with computer simulations [4, 6, 7]. Our contribution is a novel mechanism of information exchange and decision making among the agents, resulting an extended model for the El Farol 1 bar problem. The idea is similar to social communication. Each agent randomly communicates with two other agents within the population to obtain information about the last bar attendance. Based on this information the agent makes a stochastic decision to go to the bar. The aim of the study is to experimentally and rigorously analyse how such a system behaves, in particular how the bar attendance varies. The first part of this thesis is dedicated to simulation results. We first investigate the system settings for which an equilibrium corresponding to the threshold of the bar can be reached. The behaviours of the system related to the initial state of below and above the threshold are discussed. From the perspective of individual attendance, we also address the formation of structures within the population. With the proposed model, the population of agents eventually divides into two groups of attendees: regulars and casuals. In the second part, we show that the dynamics of the proposed system can be analyzed by mean of rigorous mathematics, and the expected time for the system to reach the equilibrium can be proved. For this purpose, we use Drift Analysis as the main tool. Note that Drift Analysis is widely used in Evolutionary Computation to compute expected runtime of Randomised Search Heuristics (see Lehre [8]). Due to the nature of the system that the bar attendance can wamble around the threshold, the importance of analyzing the reduction in the variance is further detailed. The proof of the runtime is shown in Chapter 4 followed by further discussion in Chapter 5. In summary, this study investigate a novel model of the El Farol Bar problem from a social coordination perspective. We show that with the right settings, the system eventually converges to the equilibrium associated with the threshold of the bar. A rigorous analysis of the system dynamics is initiated using advanced probability tools