Top

Journal of Economic Interaction and Coordination

Published in:

01-03-2015 | Regular Article

Coordination in the El Farol Bar problem: The role of social preferences and social networks

Authors: Shu-Heng Chen, Umberto Gostoli

Published in: Journal of Economic Interaction and Coordination | Issue 1/2017

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this paper, we continue the pursuit of the self-coordination mechanism as studied in the El Farol Bar problem. However, in addition to efficiency (the optimal use of the public facility), we are also interested in the distribution of the public resources among all agents. Hence, we consider variants of the El Farol Bar problem, to be distinguished from many early studies in which efficiency is the only concern. We ask whether self-coordinating solutions can exist in some variants of the El Farol Bar problem so that public resources can be optimally used with neither idle capacity nor congestion being incurred and, in the meantime, the resources can be well distributed among all agents. We consider this ideal situation an El Farol version of a “good society”. This paper shows the existence of a positive answer to this inquiry, but the variants involve two elements, which were largely left out in the conventional literature on the El Farol Bar problem. They are social networks and social preferences. We first show, through cellular automata, that social networks can contribute to the emergence of a “good society”. We then show that the addition of some inequity-averse agents can even guarantee the emergence of the “good society”.

previous article Heterogeneous wage setting and endogenous macro volatility

next article Is the service sector different in size heterogeneity?

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

This distinction is suggested by Franke (2003), who distinguished best-response learning from stimulus-response learning (reinforcement learning). The essential feature of the former is to keep track of numerous belief models and to respond to the best of them. Later on, various evolutionary algorithms have been applied to keeping track of these models (see Sect. 2 for the literature review). Therefore, another way to distinguish these two strands of the literature by using the standard taxonomy, as suggested by Duffy (2006), is evolutionary algorithms vs reinforcement learning. The former is applied to a large set of forecasting models (beliefs), whereas the latter is applied to a rather small set of actions only.

In the literature on minority games, a similar problem to the inequity issue is known as the trapping state, as first well addressed by Dhar et al. (2011) and Sasidevan and Dhar (2014). In the trapping state, both the majority and the minority have no incentive to change their choices (moving to the other restaurant), which are all locked into a Nash equilibrium. Under an expected utility maximization framework, Sasidevan and Dhar (2014) develop a co-action equilibrium as an alternative solution concept and show that there are ways out of the trap toward the co-action equilibrium.

Probably under the impact of the recent financial crisis and the social turbulence, economists are challenged by a very general and fundamental issue on whether our economics can actually help build a good society at large. These reflections can be best exemplified by some recent events, including plenary speeches and organized sessions, in the Allied Social Science Association (ASSA) and American Economic Association (AEA) annual meetings (Marangos 2011; Shiller 2012).

Surprising in the sense that the generic procedure or algorithm for programming individuals which can lead to the desirable emergent patterns is generally unknown. This challenge is well-known in the study of complex systems. Since the El Farol Bar problem has been constantly modeled as a kind of complex adaptive system, and in this paper it will be modeled via cellular automata (Wolfram 2002), this challenge, therefore, remains.

There are two bodies of literature related to this development. One is network-based agent models, and the other is the agent-based modeling of (social) networks. The former refers to the agent-based models which explicitly involve networks, mainly for the purpose of interactions and decision-making; hence it can also be termed as the network-based decision model. A number of earliest agent-based economic models are of this type (Albin 1992; Albin and Foley 1992). More recent surveys can be found in Wilhite (2006). The latter, the agent-based models of networks, considers agent-based models as formation algorithms of networks, to be separated from sociological models, sociophysical models, and game-theoretic models (Eguiluz et al. 2005; Hamill and Gilbert 2009). In this paper, we are mainly concerned with the first type.

As we will see in Sect. 2.2, agents can still gain access to global information (the bar’s aggregate attendance), but it is only used to enable agents to determine when to start searching (to learn from neighbors) and when to stop.

A survey of various similar attempts can be found in Fehr and Schmidt (2006). The model has been under intensive examination in experimental economics for more than a decade; see, for example, Fehr et al. (2006), Blanco et al. (2011), and Dreber et al. (2014).

The interested reader is referred to Gintis (2008) and Hetzer and Sornette (2013).

Quite surprisingly, examples of the adoption of local interaction in the former and of different learning mechanisms in the latter are much rarer.

These two versions of the payoff inequality will be discussed in Sect. 2.2.

Because of this, there comes an additional difference. To ensure that there is always a minority side, in the minority game it is explicitly assumed that $N$ is an odd number, an assumption which is not made in the El Farol Bar problem. As a result, the two games are characterized by different dynamics of the average long-term payoff per agent, as $N$ increases. While in the MG the average long-term payoff per agent improves, as $N$ grows larger, and asymptotically goes to zero from below, in the case of the El Farol problem it stays around zero, as the positive effect of the decreased fluctuation around the threshold is offset by the negative effect of the decreased probability of hitting the threshold, a possibility which in the MG is precluded by construction.

Here, we would like to add a remark to draw a distinction between the minority game with local information (Kalinowski et al. 2000) and the local minority game (Moelbert and De Los Rios 2002). In the former case, the minority game is played globally, i.e., the minority is defined globally, but information used for decision making is mainly obtained from local neighbors. In the latter case, the minority game is simply played locally, i.e., the minority is defined locally. Our paper belongs to the former.

It should be noted that since we assume that agents are bounded rational agents following search heuristics rather than expected-utility maximizing agents, only ordinal utility is relevant here.

Specifically, there are four types of dynamics being established under various rules studied by Wolfram (2002). As we shall see, in our El Farol setting, the pursuits for the types of dynamics that we may have and what are the rules supporting the emergent dynamics are very much motivated by the cellular-automata underpinning. Compared to the case of Wolfram (2002), we have two additional settings, namely, heterogeneity and learning: we start with agents using different rules and then learning in order to coordinate themselves in the sense that they collectively find the rule that generates the type of dynamics that is consistent with the pattern characterizing the ‘good society’.

In this second set of simulations, we will not consider the circular neighborhood as in this part our aim is to assess the effect of the inequity-averse preference on the equilibrium distribution.

One may wonder about the noticeable discontinuity appearing in this figure. Why does it make the fluctuation suddenly stop? We shall come back to this point in Sect. 5.

Here, we use equilibria because, except for the 1C equilibrium, we can have multiple equilibria for each $C\,(C \ge 2)$. For example, for the 2C equilibria, in addition to $\varXi _{Bi}$ as shown in (7), the other observed $2C$ equilibrium is:

$$\begin{aligned} \varXi _{2} \equiv \left\{ (1, 0.2), (0.5, 0.8) \right\} \end{aligned}$$

(9)

Similarly, for $C=3$, we can have

$$\begin{aligned} \varXi _{3-1} \equiv \left\{ (0.7, 0.1), (0.6, 0.8), (0.5, 0.1) \right\} \end{aligned}$$

(10)

$$\begin{aligned} \varXi _{3-2} \equiv \left\{ (1, 0.4), (0.5, 0.4), (0, 0.2) \right\} . \end{aligned}$$

(11)

Furthermore, even for two equilibria having the same $\{ b_{j}^{*} \}$, their $\{ \pi _{j}^{*} \}$ can still be different. For example, one alternative for $\varXi _{3-1}$ is

$$\begin{aligned} \varXi _{3-3} \equiv \left\{ (0.7, 0.3), (0.6, 0.4), (0.5, 0.3) \right\} . \end{aligned}$$

(12)

The equilibrium with more than eight clusters of agents has not been found in any of our simulations.

For this reason, Fig. 6 only shows the results up to $N_{\alpha , 0.6}=23$.

Notice that in equilibrium $N1$ and $N3$ are well aligned with the same action.

As shall be made clear below, each agent experiences the dynamics of his environment in equilibrium as a 10-period cycle: 16-16-7-7-10-10-7-7-10-10.

This is because in the equilibrium each agent only looks at his neighbor to the west $(N2)$ or to the north $(N3)$, and imitates his behavior.

It should be pointed out that there are another two periodic cycles also found in our simulation, a 5-period cycle (1-1-1-0-0), and a 10-period cycle (1-1-0-0-1-1-0-1-1-0). All these three cycles can be generated by any of the four strategies shown in Fig. 8. Obviously, they all lead to an attendance frequency of 60 %. One qualification which we would like to add here is that all these emergent cyclical patterns do depend on some subtle combinations of the number of agents and the threshold parameter. For example, under this specific setting, one would not expect the appearance of this cyclical pattern when $\alpha _{i}=0.59$ rather than 0.6.

Of course, since the system is not deterministic, small or large stochastic perturbations may still cause the path to cross the border and also cause travel along the path in another domain of attraction.

While the model has not been that analytical, a formal expression of this result is that the attraction domain of the $1C$ equilibrium has a measure of one, whereas the attraction domains of other many-cluster equilibria have a measure of zero.

We admit that this scale of sensitivity analysis is limited, but a thorough analysis of the effect of changing the parameters may be beyond the scope and the size of this paper.

Albin P (1992) Approximations of cooperative equilibria in multi-person prisoners’ dilemma played by cellular automata. Math Soc Sci 24(2–3):293–319CrossRef

Albin P, Foley D (1992) Decentralized, dispersed exchange without an auctioneer. J Econ Behav Organ 18:27–51CrossRef

Anghel M, Toroczkai Z, Bassler K, Korniss G (2004) Competition-driven network dynamics: emergence of a scale-free leadership structure and collective efficiency. Phys Rev Lett 92:058701CrossRef

Arthur B (1994) Complexity in economic theory: inductive reasoning and bounded rationality. Am Econ Rev 82(2):406–411

Atilgan C, Atilgan A, Demirel G (2008) Collective behavior of El Farol attendees. Adv Complex Syst 11(4):629–639CrossRef

Bell AM, Sethares WA (1999) The El Farol problem and the internet: congestion and coordination failure. Society for computational economics, working paper no. 1999 812

Blanco M, Engelmann D, Normann H (2011) A within-subject analysis of other-regarding preferences. Games Econ Behav 72(2):321–338CrossRef

Bolton GE (1991) A comparative model of bargaining: theory and evidence. Am Econ Rev 81(5):1096–1136

Bolton G, Qckenfels A (2000) ERC: a theory of equity, reciprocity, and competition. Am Econ Rev 90(1):166–193CrossRef

Caridi I, Ceva H (2004) The minority game with interactions. Phys A 339:574–582CrossRef

Challet D, Zhang Y-C (1997) Emergence of cooperation and organization in an evolutionary game. Phys A 246(3–4):407–418CrossRef

Challet D, Marsili M, Ottino G (2004) Shedding light on El Farol. Phys A 332(1):469–482CrossRef

Challet D, Marsili M, Zhang Y-C (2005) Minority game. Oxford University Press, Oxford

Chau H, Chow F, Ho K (2004) Minority game with peer pressure. Phys A 332:483–495CrossRef

Chen S-H (2008) Software-agent designs in economics: an interdisciplinary framework. IEEE Comput Intell Mag 3(4):18–22CrossRef

Chen S-H, Liao C-C, Chou P-J (2008) On the plausibility of sunspot equilibria: simulations based on agent-based artificial stock markets. J Econ Interact Coord 3(1):25–41CrossRef

Coolen A (2005) The mathematical theory of minority games: statistical mechanics of interacting agents. Oxford University Press, Oxford

Dhar D, Sasidevan V, Chakrabarti BK (2011) Emergent cooperation amongst competing agents in minority games. Phys A Stat Mech Appl 390(20):3477–3485CrossRef

Dreber A, Fudenberg D, Rand D (2014) Who cooperates in repeated games: the role of altruism, inequity aversion, and demographics. J Econ Behav Organ 98:41–55CrossRef

Duffy J (2006) Agent-based models and human subject experiments. In: Tesfatsion L, Judd K (eds) Handbook of computational economics: agent-based computational economics, vol 2. Elsevier, Oxford, UK, pp 949–1011

Edmonds B (1999) Gossip, sexual recombination and the El Farol bar: modelling the emergence of heterogeneity. J Artif Soc Soc Simul 2(3). http://jasss.soc.surrey.ac.uk/2/3/2.html

Eguiluz V, Zimmermann M, Cela-Conde C, Miguel M (2005) Cooperation and the emergence of role differentiation in the dynamics of social networks. Am J Sociol 110(4):977–1008CrossRef

Erev I, Roth A (1998) Predicting how people play games: reinforcement learning in experimental games with unique, mixed strategy equilibria. Am Econ Rev 88(4):848–881

Fehr E, Schmidt K (1999) A theory of fairness, competition, and cooperation. Q J Econ 114(3):817–868CrossRef

Fehr E, Schmidt K (2006) The economics of fairness, reciprocity and altruism-experimental evidence and new theories. In: Kolm S, Ythier J (eds) Handbook on the economics of giving, reciprocity and altruism, vol 1. Elsevier, Amsterdam, pp 615–669

Fehr E, Naef M, Schmidt K (2006) Inequality aversion, efficiency, and maximin preferences in simple distribution experiments: comment. Am Econ Rev 96(5):1912–1917CrossRef

Fogel D, Chellapilla K, Angeline P (1999) Inductive reasoning and bounded rationality reconsidered. IEEE Trans Evol Comput 3(2):142–146CrossRef

Franke R (2003) Reinforcement learning in the El Farol model. J Econ Behav Organ 51(3):367–388CrossRef

Gali J (1994) Keeping up with the Joneses: consumption externalities, portfolio choice and asset prices. J Money Credit Bank 26(1):1–8CrossRef

Galstyan A, Lerman K (2002) Adaptive Boolean networks and minority games with time-dependent capacities. Phys Rev E 66:015103CrossRef

Gigerenzer G, Gaissmaier W (2011) Heuristic decision making. Ann Rev Psychol 62:451–482CrossRef

Gintis H (2008) The bounds of reason: game theory of the unification of behavioral sciences. Princeton University Press, Princeton

Hamill L, Gilbert N (2009) Social circles: a simple structure for agent-based social network models. J Artif Soc Soc Simul 12(2):3. http://jasss.soc.surrey.ac.uk/12/2/3.html

Hetzer M, Sornette D (2013) The co-evolution of fairness preferences and costly punishment. PloS One 8(3):e54308CrossRef

Kalinowski T, Schuklz H-J, Briese M (2000) Cooperation in the minority game with local information. Phys A 277(3–4):502–508CrossRef

Kauffman S (1993) The origins of order: self organization and selection in evolution. Oxford University Press, Oxford

Lavicka H, Slanina F (2007) Evolution of imitation network in minority game models. Eur Phys J B 56:53–63CrossRef

LeBaron B (2001) Evolution and time horizons in an agent-based stock market. Macroecon Dyn 5:225–254CrossRef

Ljungqvist L, Uhlig H (2000) Tax policy and aggregate demand management under catching up with the Joneses. Am Econ Rev 90(3):356–366CrossRef

Lo T, Chan H, Hui P, Johonson N (2004) Theory of networked minority games based on strategy pattern dynamics. Phys Rev E 70:056102CrossRef

Lux T, Schornstein S (2005) Genetic learning as an explanation of stylized facts of foreign exchange markets. J Math Econ 41(1–2):169–196CrossRef

Marangos J (ed) (2011) Alternative perspectives of a good society. Palgrave Macmillan, Basingstoke

Moelbert S, De Los Rios P (2002) The local minority game. Phys A Stat Mech Appl 303(1–2):217–225CrossRef

Paczuski M, Bassler K, Corral A (2000) Self-organized networks of competing Boolean agents. Phys Rev Lett 84(14):3185–3188CrossRef

Sasidevan V, Dhar D (2014) Strategy switches and co-action equilibria in a minority game. Phys A Stat Mech Appl 402:306–317CrossRef

Shang L, Wang X-F (2007) Evolutionary minority game on complex networks. Phys A 377:616–624CrossRef

Shiller R (2012) Finance good society. Princeton University Press, Princeton

Slanina F (2000) Social organization in the minority game model. Phys A 286(1–2):367–376CrossRef

Whitehead D (2008) The El Farol Bar problem revisited: reinforcement learning in a potential game. ESE discussion papers 186, University of Edinburgh

Wilhite A (2006) Economic activity on fixed networks. In: Tesfatsion L, Judd K (eds) Handbook of computational economics: agent-based computational economics, vol 2. Elsevier, Oxford, UK, pp 1013–1045

Wolfram S (2002) A new kind of science. Wolfram Media, Champaign

Xianyu B (2010) Social preference, incomplete information, and the evolution of ultimatum games in the small world networks: an agent-based approach. J Artif Soc Soc Simul. 13(2):7. http://jasss.soc.surrey.ac.uk/13/2/7.html

Zambrano E (2004) The interplay between analytics and computation in the study of congestion externalities: the case of the El farol problem. J Public Econ Theory 6(2):375–395CrossRef

Zenil H (ed) (2013) Irreducibility and computational equivalence: 10 years after wolfram’s a new kind of science. Springer, New York

Title: Coordination in the El Farol Bar problem: The role of social preferences and social networks
Authors: Shu-Heng Chen
Umberto Gostoli
Publication date: 01-03-2015
Publisher: Springer Berlin Heidelberg
Published in: Journal of Economic Interaction and Coordination / Issue 1/2017
Print ISSN: 1860-711X
Electronic ISSN: 1860-7128
DOI: https://doi.org/10.1007/s11403-015-0150-z

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 1/2017

A comparison of endogenous and exogenous timing in a social learning experiment

Scale-free distribution as an economic invariant: a theoretical approach

Dynamic patterns in similarity-based cooperation: an agent-based investigation

Is the service sector different in size heterogeneity?

Heterogeneous wage setting and endogenous macro volatility