The El Farol Bar Problem

The  El Farol Bar Problem, and it's close generalization, the Minority Game, are recent, but well-studied coordination games in game theory (there's even a book).  I was going to write a descriptive post about it, but Ken, a math professor (Update: holder of two patents) and trader with a new blog has already covered the Minority Game in detail, and better yet, it's analogies to his trading experiences.  This leaves me free to cover it with respect to one of my recurring pet topics, randomness and the Efficient Market Hypothesis (EMH).

As Ken points out, if you study the Minority Game, you'll see it's striking similarity to the way the markets operate, and Ken provides links to the extensive research on this.  The real El Farol Bar (pictured above)is in Santa Fe and is/was a hangout for some of my favorite researchers at the Santa Fe Institute who extensively study Complex Adaptive Systems.

Randomness and the Optimal Strategy.  Some of the more interesting aspects of the game are that a set of agents playing the game can maximize their collective outcome with no coordination by applying stochastic strategies, i.e. - strategies that employ randomness (pdf).  What is interesting is that strategies like these essentially reduce to a random walk (pdf) whereby the game history "signal" contains no useful information.  The solution is only optimal to the degree all agents act stochastically (randomly) using the same strategy.  Thus, for these agents, to act rationally is to act randomly collectively.  This, of course, is analogous to the Efficient Market Hypothesis (EMH) nirvana where you can't beat or predict the market.  These strategies are actually a little more complicated than that in that the agents act orderly if they win and randomly if they lose.  This key subtlety allows them to collectively adapt to the optimal solution using the right amount of randomness.  It's kind of a collective tit-for-tat strategy, and since it's optimal, no collective strategy can be better. 

The Problem with the Random Optimal Strategy.  It's quite interesting to note from quantum game theory (pdf), however, that if agents can communicate and coordinate their actions, they can game the system (outdo the players playing randomly at their expense).  Indeed, if conditions are right, they can make it so the random players can never win.  I would add that two players who independently chose to act non-randomly could stumble on the same coordinated strategy without resorting to communicating (cheating).  Thus, the random, optimal strategies are not a Nash Equilibrium.  It would thus appear that there is no basis for the agents to act rationally (randomly), because they can be exploited if they do.  In the ultimate irony, they can be exploited if they are predictably random.  The analogy with the markets here is that when everyone is herded into an index fund by the EMH (because they believe the market is a random walk), they can be cheated of their hypothetical optimal EMH payoff as well.  You're damned if you do and damned if you don't!

Self Interested Agents. Even more interesting is the more studied problem when the agents as a whole do not employ randomness, but rather try to predict the "market."  Brian Arthur was the researcher who formulated the game in 1994 and had this to say about it then:

"The inductive-reasoning system I have described above consists of a multitude of "elements" in the form of belief-models or hypotheses that adapt to the aggregate environment they jointly create. Thus it qualifies as an adaptive complex system. After some initial learning time, the hypotheses or mental models in use are mutually co-adapted. Thus we can think of a consistent set of mental models as a set of hypotheses that work well with each other under some criterion--that have a high degree of mutual adaptedness. Sometimes there is a unique such set, it corresponds to a standard rational expectations equilibrium, and beliefs gravitate into it. More often there is a high, possibly very high, multiplicity of such sets. In this case we might expect inductive reasoning systems in the economy--whether in stock-market speculating, in negotiating, in poker games, in oligopoly pricing, in positioning products in the market--to cycle through or temporarily lock into psychological patterns that may be non-recurrent, path-dependent, and increasingly complicated. The possibilities are rich.

Economists have long been uneasy with the assumption of perfect, deductive rationality in decision contexts that are complicated and potentially ill-defined. The level at which humans can apply perfect rationality is surprisingly modest. Yet it has not been clear how to deal with imperfect or bounded rationality. From the reasoning given above, I believe that as humans in these contexts we use inductive reasoning: we induce a variety of working hypotheses, act upon the most credible, and replace hypotheses with new ones if they cease to work. Such reasoning can be modeled in a variety of ways. Usually this leads to a rich psychological world in which agents' ideas or mental models compete for survival against other agents' ideas or mental models--a world that is both evolutionary and complex."

His more recent words reflect the research of the ensuing 10 years into the flurry of activity he started:

"In the minority game, agents align their strategies to the condition of the market: they want to choose the strategy that on average minimizes their chance of being in the majority. As a result, strategies co-organize themselves so as to minimize collective dissatisfaction. But this collective result has two phases. With few players, the recent history of the game contains some useful information that strategies can exploit. But once the number of players passes a critical value, all useful information has been used up. The properties of the outcome differ in these two regimes. Information, in fact, is central to the situation. And its role can be explicitly observed: players act as if to minimize a Hamiltonian that is itself a measure of available information. So the process by how information gets eaten up by players is made explicit, and this is another useful pathway into exploring financial markets.

Because some information is left unexploited if few players are in the market, and all information is used up as players increase past a critical number, Challet, Marsili and Zhang point out that players may enter the market until this critical number is reached. The market will therefore display self-ordered criticality. This is an important conjecture, and not just a theoretical one. It tells us that speculative investors — technical traders, at least — will seek out thin markets where possible and avoid deep ones. Markets may therefore hover on the edge of efficiency — a significant insight that can be made explicit with the techniques used here and one that is worth further investigation."

The lesson here, I think, is a reiteration Patton's advice: it's good to think differently than the crowd, especially in the markets. 

Comments

[Ken]

Alan, your analysis is insightful as usual. However, I want to point out a potential flaw in one of your comments:
"These strategies are actually a little more complicated than that in that the agents act orderly if they win and randomly if they lose. This key subtlety allows them to collectively adapt to the optimal solution using the right amount of randomness."
This is not actually true. According to the rules of the GCMG, agents will deterministically choose their next trading strategy either if they win or lose. Agents have backup strategies that get scored on every period, and agents will choose the highest ranked backup strategy if their primary one loses effectiveness.

[Alan J]

Hi Professor! (just kidding)

Good catch! I believe I didn't stress the connection between that quote and this paper:

http://www.citebase.org/abstract?id=oai%3AarXiv.org%3Acond-mat%2F0007351

The authors therein used a uniform strategy for each agent (choose the same if winning and randomly if they lose) as I described, and arrived at an optimal solution. Other authors have look at other strategies.