From Nash equilibria to collective behavior

https://twitter.com/ulaulaman/status/517303481565458432 by @ulaulaman about #Nash equilibria and their role in collective behavior

The Nash equilibrium is an important tool in game theory:

[It] is a solution concept 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 their own strategy. If each player has chosen a strategy and no player can benefit by changing strategies while the other players keep theirs unchanged, then the current set of strategy choices and the corresponding payoffs constitute a Nash equilibrium.
Stated simply, Amy and Will are in Nash equilibrium if Amy is making the best decision she can, taking into account Will's decision, and Will is making the best decision he can, taking into account Amy's decision. Likewise, a group of players are in Nash equilibrium if each one is making the best decision that he or she can, taking into account the decisions of the others in the game.

Nash equilibria may, for example, be found in the game of coordination, in the prisoner's dilemma, in the paradox of Braess⁽⁶⁾, or more generally in any strategy game. In particular, given a game, we can ask whether it has or not a Nash equilibrium: apparently deciding the existence of Nash equilibria is an intractable problem, if there is no restriction on the relationships among players. In addition for a strong Nash equilibrium, the problem is on the second level of the polynomial hierarchy, which is a scale for the classification problem based on the complexity of resolution⁽¹⁾.
In addition to this study about Nash equilibria, Gianluigi Greco (one of my high school classmates), together with Francesco Scarcello, also studied the Nash equilibria (in this case the forced equilibria) in graphical games, where graphical game is a game represented in a graphical manner, through a graph⁽²⁾.
But Gianluigi has also won the Gödel Research Prize for the logical foundation of artificial intelligence with the project Collective Behavior in Social Environments: Models and Complexity. So, simply by reading the title of the project, you could think of something away from a study related to artificial intelligence, however the study and modeling of collective behavior has an important role in this specific field of research.
Understanding the behavior of individual definitely has a certain scientific interest, not only to understand the functioning of our brain, but also to understand the cognitive mechanisms, which are essential in the construction of effective teaching strategies. On the other hand groups of people interacting between them are able to emerge organizations of higher level than the individual:

Interacting ants create colony architectures that no single ant intends. Populations of neurons create structured thought, permanent memories and adaptive responses that no neuron can comprehend by itself.⁽³⁾

So it is clear the interest in models of collective behavior: it seems that the most used models are based on intelligent agents, such the swarm intelligence, introduced in 1989 by Gerardo Beni and Jing Wang⁽⁴⁾: in this case some agents, programmed with simple rules, are made to interact with one another and with the surrounding environment. The background idea it could be considered as an evolution of the Conway's game of life.
Such a system can definitely be useful in biology and in the study of swarms (or human behavior), and on the other hand, the study of social interactions within swarms may suggest strategies for optimization of algorithms⁽⁵⁾ used to model collective behavior (e.g. in the study of the problem of the traveler).
The interest in using this approach is, therefore, in the emergency within a system of interacting individuals of a sort of collective intelligence⁽⁷⁾ (or a consciousness!), and then in trying to understand if a system of artificial neurons interacting with one another on the basis of more or less simple rules is able to bring out some form of artificial intelligence, then maybe that can itself evolve according to interactions with the external environment. In this picture also the study of Nash equilibria has an important role: the interaction between agents is a kind of game, and then discover these balances within the rules set could allow, in the case of transport patterns in human societies rather than in the development of artificial intelligence, to discover the mechanisms of optimization choices.

---

Some papers by Nash:
Nash, J. (1950). Equilibrium points in n-person games Proceedings of the National Academy of Sciences, 36 (1), 48-49 DOI: 10.1073/pnas.36.1.48
Nash J. (1951). Non-Cooperative Games, The Annals of Mathematics, 54 (2) 286-295. DOI: http://dx.doi.org/10.2307/1969529 (pdf)

---

(1) Gottlob G., Greco G. & Scarcello F. (2003). Pure Nash equilibria, Proceedings of the 9th conference on Theoretical aspects of rationality and knowledge - TARK '03, 215-230. DOI: http://dx.doi.org/10.1145/846241.846269 (arXiv)
(2) Greco, G., & Scarcello, F. (2009). On the complexity of constrained Nash equilibria in graphical games Theoretical Computer Science, 410 (38-40), 3901-3924 DOI: 10.1016/j.tcs.2009.05.030
(3) Goldstone, R., & Janssen, M. (2005). Computational models of collective behavior Trends in Cognitive Sciences, 9 (9), 424-430 DOI: 10.1016/j.tics.2005.07.009 (pdf)
(4) Beni G. (1993). Swarm Intelligence in Cellular Robotic Systems, Robots and Biological Systems: Towards a New Bionics?, NATO ASI Series Volume 102 703-712. DOI: http://dx.doi.org/10.1007/978-3-642-58069-7_38
(5) Bonabeau E., Dorigo M. & Theraulaz G. (2000). Inspiration for optimization from social insect behaviour, Nature, 406 (6791) 39-42. DOI: http://dx.doi.org/10.1038/35017500 (researchgate)
(6) The prisoner's dilemma is, between the three that I mentioned, certainly the best known. Proposed by Flood and Dresher in 1950, was formalized and became "prisoner's dilemma" thanks to Albert Tucker in 1992:

Two members of a criminal gang are arrested and imprisoned. Each prisoner is in solitary confinement with no means of speaking to or exchanging messages with the other. The police admit they don't have enough evidence to convict the pair on the principal charge. They plan to sentence both to a year in prison on a lesser charge. Simultaneously, the police offer each prisoner a Faustian bargain. Each prisoner is given the opportunity either to betray the other, by testifying that the other committed the crime, or to cooperate with the other by remaining silent. Here's how it goes:
If A and B both betray the other, each of them serves 2 years in prison
If A betrays B but B remains silent, A will be set free and B will serve 3 years in prison (and vice versa)
If A and B both remain silent, both of them will only serve 1 year in prison (on the lesser charge)

Nash has shown that the best strategy is to remain both silent.
(7) The existence of a possible collective intelligence is the basis of psychohistory introduced by Asimov in the Foundation's saga developed between 1942 and 1944. This soon became a research subject (for example, the Journal of psychohistory is published since 1973). An example of a study that may fall within this discipline is the research performed by Kalev Leetaru: using the automated sentiment mining, in practice a detection of mood, he seemed to be able to build a model able to describe the Arab Spring. What is missing is the confirmation of any predictive ability of the model (and all models of this kind, of course), something that we will understand only with the future.