The Education Of A Machine — Part 3/7 (The Nash Equilibrium)

15 min readSep 24, 2017

If one is teaching the machines to understand the human behavior, what would one embed in the silicon ? (Remember, for an autonomous car to navigate effortlessly in a complex turnaround, it has to perform orchestrated negotiated inferred behavior and understand when/how to break the rules …Just the rules of the road or the navigation mechanics are not enough …)

The best, of course, is to wire a robot brain very similar to ours — unfortunately which we are way far away from understanding the brain’s mechanisms. The next best thing could be to wire the logic that explains “why do we do what we do” … which is where Game Theory and Nash equilibrium come in the picture …

Traditionally the Nash Equilibrium and associated theories have found applications in managing auctions, choosing stock portfolios, multi-firm bids in corporate mergers and acquisitions … even improving principles under democratic voting !

Of late, the theories developed by John Forbes Nash have found relevance in AI — from multi-way-multi-lane merge for autonomous cars, to predicting mob psychology, to developing an orchestrated mobility service, to orchestrating charging of electric vehicles, to building reinforcement learning systems, …

Let us dig deeper by reviewing the book “A Beautiful Math” by Tom Siegfried as our guide.

From Asimov, to Pascal, to Adam Smith, to modern scientists — “A Beautiful Math” by Tom Siegfried offers a breadth of rich, colorful and vivid journey through a spectrum of related topics — makes you think, research, read interesting papers and ultimately appreciate the influence of game theory on a wide variety of domains.

At 262 pages, the book is not that big and packed with tons of interesting observations. In the process we will touch upon our favorite author Asimov, Hari Seldon’s Psychohistory, Star Trek and Adam Smith …

Siegfried succeeds in giving us “a flavor of what scientists are doing at the frontiers of knowledge … no grantees of ultimate success but probing intriguing possibilities” — That exactly is why you should definitely read … probably brood over this book.

In short, SiegFried’s “A Beautiful Math” is a must read, with a very rich treatment of the Game Theory, full of interesting anecdotes, history and luminaries, behind the sciences we take for granted, and a breadth of topics that one can dive into. I did go deeper into multiple detours & then (reluctantly) back to the main thread.

P.S: I have linked the papers and blogs at the appropriate places as and when you want to digress !

Psychohistory dealt with masses …. It was the science of mobs; mobs in their billions. It could forecast reactions to stimuli with something of the accuracy that a lesser science could bring to the forecast of a rebound of a billiard ball.
The reaction of one could be forecast by no known mathematics; the reaction of a billion is something else again …
— Isaac Asimov. Foundation and Empire

Background a.k.a The Same Page Thing

Before we dive into the book, it would be good to get a perspective on what exactly Nash Equilibrium is …

Game Theory, in it’s essence deals with payoffs and strategies; the science of strategy, in short. The Nash Equilibrium, named after John Forbes Nash, the Nobel Prize winner, provides a mathematical means of computing the payoffs and policies. Since then, the principles of Nash Equilibrium are used by economists, biologists, anthropologists and neuroscientists. An interesting offshoot is the new domain of Neuroeconomics — a science combining game theory and brain scanning for studying human judgements and behavior.

My interest in Nash Equilibrium stems from the Deep Reinforcement Learning angle, for building Autonomous Negotiated Orchestrated Services Platform using Artificial Intelligence and agents, say, for mobility services (like Uber) in a world of autonomous cars or for flying drones autonomously or to create a Jarvis who/that can learn !

Probably John Forbes Nash’s PNAS (Proceedings of the National Association of Sciences) paper “The Bargaining Problem” was his first published work. It describes the n-person collaborative game for mutual benefit. The precursor was John von Neumann’s “Theory of Games and Economic Behavior” that explored two person zero-sum game with a Minmax ie minimize the maximum loss, in a competitive setting.

The Nash Equilibrium was formally introduced in his paper “Equilibrium points in n-person games”. The succinct impact of Nash Equilibrium is eloquently described in “The Mathematics of Strategy” as:

“The Nash equilibrium concept has become a benchmark by which economists and other scientists measure both rational behavior and the extent to which humans depart from pure rationality. Over the years, this concept has illuminated questions in economics, psychology, and even biology.”

John Nash’s PhD dissertation is unique in it’s succinctness (27 pages) and the very short bibliography (just 2 references and one of them his own paper !)

**From Udacity Reinforcement Learning Class by Prof. Isbell & Prof. Littman**

Nash then published the work in the Annals of Mathematics, which is more readable !

BTW, probably the dissertation was published using a Cyclostyling copier. An old technique … I have to confess that I published my Masters Thesis using a cyclostyling copier — much modern than shown in Wikipedia ! Yep, I also have used punch cards … that too to program in COBOL, while dodging Dinosaurs on my way to work !! (We didn’t have Java and c# then …)

Needless to say, John Nash won the Nobel prize in 1994.

The Nobel Seminar that summarizes Nash’s work is an excellent read, so is the book “The Essential John Nash”. The Proceedings of the National Association of Sciences (PNAS) paper “The Nash equilibrium: A perspective” summarizes Nash’s work like so:

In the last 20 years, the notion of a Nash equilibrium has become a required part of the tool kit for economists and other social and behavioral scientists …. There have been modifications, generalizations, and refinements, but the basic equilibrium analysis is the place to begin (and sometimes end) the analysis of strategic interactions, not only in economics but also in law, politics, etc.

A beautiful Math — Walk-thru

Let us run down the chapters and look at some of the interesting waypoints. My hope is that you will take the time to read the book after reading this blog. The book is a lot more interesting and elaborate …

1: Smith’s Hand

Siegfried begins the book drawing parallels between Adam Smith’s work and Game Theory — Adam Smith’s view of self-interest that drives prosperity and game theory’s profit maximizing agents. One of the points raised by Adam Smith in the “An Inquiry into the Nature and Causes of the Wealth of Nations” is the pursuit of self interest “It is not from the benevolence of the butcher, the brewer, or the baker, that we expect our dinner, but from their regard to their own interest …” [P.16 of the book] ] This is analogous to rationality in Nash’s world.

Adam Smith also wrote “The Theory of Moral Sentiments” as a prelude to his later works, which has insightful explanations of human behavior that are useful in deriving Nash Equilibrium in many situations.

2: Von Neumann’s Games

Of course, “The Theory of Games & Economic Behavior” by John von Neumann and Oskar Morgenstern is the pre cursor to John Nash’s Game theory, in fact that was the only reference in John Nash’s 27 page PhD dissertation !

“Theory of games of strategy is the proper instrument with which to develop a theory of economic behavior” he wrote.

Neumann’s work explored utility and value from a two-person-zero-sum game and the focus was mostly economics. In that work, the value was measured in terms of monetary and the strategy was minimax. As we will see in later chapters, further work by Nash & others expanded this notion.

3: Nash’s Equilibrium

John von Neumann published the book in 1944; 4 years later Nash joined Princeton as a graduate student. An interesting coincidence - John Nash won the Nobel Prize in 1994, the 50th anniversary of the publication of “The Theory of Games & Economic Behavior” !

John Nash extended Neumann’s work to multiplayer games and generalized the concept to cooperative situations. Eventually Nash’s dissertation proposed the Nash Equilibrium as opposed to the minimax as a strategy.

Siegfried, in this chapter, traces the history of the Prisoner’s Dilemma from Edgar Allen Poe’s “The Mystery of Marie Roget” to the lecture at Stanford by Nash’s Professor Albert Tucker. A good read.

The Game theory has evolved since then, into multiple areas of science, but the essential characteristic still remains ie the ability to predict different strategies in different situations. The extension of Nash’s theories to Reinforcement Learning — with multiple players, dynamic value propositions and policy iterations in a continuous multiplayer games, holds interesting possibilities in the world of AI, and that is where my focus is.

4: Smith’s Strategies

Siegfried starts the chapter quoting Harper’s paper on Mallard ducks. It seems animals do have an instinct understanding of Nash Equilibrium ! For example, Harper observed that when food is distributed in two places with varying frequencies, ducks figured out Nash Equilibrium and distributed themselves to maximize the food-getting ! Interesting paper …

Pioneering work on applying game theory to evolution was done by John Meynard Smith — his paper with George Price and book “Evolution and the Theory of Games”

Interesting contribution to classical game theory from Smith is the substitution of “fitness” for utility and “natural selection” for rationality. I really like the evolution of utility from a single monotonically increasing linear scale to a multi variable function — very relevant for formulating a combined weighted reward function in Reinforcement Learning !

This chapter is very interesting to read — good discussions on evolutionary strategies like fight or flight, tit for tat and reciprocity mechanisms. As we read the chapter, we realize that these are more deep and involved than appear at first sight and are fundamental to evolution among humans and animals !

5: Freud’s dream

Interesting chapter on the synergy between study of brain and Game theory. With the advent of Neuroeconomics, game theory has been instrumental in understanding the inner working of our brain and understanding human behavior.

Couple of interesting Neuroeconomics papers that explore “neurobiological and computational basis of value-based decision making”

Montague and Berns, “Neural economics and the biological substrates of valuation”
Rangel, Camerer and Montague, “A framework for studying the neurobiology of value-based decision making”

It is interesting to see how Neuroeconomics views the chemical dopamine (the pleasure molecule in our brain) as the ultimate payoff and hence value evaluator - an interesting concept that broadens the basic tenets of Game Theory. As all our brains are not alike, the expected payoff will differ between people and incorporating that view, by itself, makes Nash’s theories more flexible and adaptable to explain and predict human behaviors.

6: Seldon’s solution

Asimov attempts to model a Code of Nature that enables a quantitative description and accurate predictions of collective human behavior[2].

An interesting chapter, starts with Sam Spade from The Maltese Falcon.

Game theory provides a more sophisticated and quantitate tool for describing human nature than the intuition of criminals ;o)

Game theory is a valuable tool to predict human behavior in ”broad sweeps, with calculable probabilities”. But, the actual manifestation of game theory in a human society need to consider the social context, to explain things that can appear to be inconsistent with self-interest-maximizing agents, We will see more of this social context from cultural point-of-view in a later chapter. Cultural norms & diversity, evolutionary instincts, how certain offerings are traditionally perceived, and even biases do play important roles in achieving Nash equilibrium. Hence the difficulty of applying pure game theory to understand and predict events in the society.

What Seldon saw, in the Foundation series, is equally applicable to designing Uber-like mobility service in modern era, using principles like Reinforcement Learning. For example, the reward functions for students are not the same as the value functions of an executive who is late for an appointment (and hence the surge pricing from Uber!) But societal values and norms also play a part — Uber and Amazon did catch a lot of flack for applying surge pricing in situations like the recent hurricane in Texas.

7: Quetelet’s Statistics & Maxwell’s Molecules

Trivia: Quetelet invented the index for obesity called BMI.

Interestingly, Quetelet got his PhD in Mathematics in 1819 and has worked on a variety of sciences incl Physics and Astronomy — “described as amiable and considerate, tactful and modest, but still a rigorous thinker who expressed his views strongly” !

In 1823, Quetelet travelled to Paris to study Astronomy and establish an observatory in Brussels. during the stay, he learned Statistics and Probability from Laplace and met his colleagues Fourier and Poisson ! Result was Quetelet’s work on social physics — the statistical description of the society !

James Clark Maxwell, using statistics, derived mathematical descriptions of average behavior of large groups of molecules. “Measuring temperature tells you about the average speed of molecules and the energy; moreover you can calculate the effect of altering the temperature on the gas’s pressure. Knowing the average energy, one can predict the chemical reaction without knowing the inner workings and complexities of molecular motion — Too numerous to count and too small to be seen.”

In fact, temperature is not even a property of a molecule, but a distribution of the velocities of a set of molecules !

Maxwell, in “On the Dynamical Theory of Gases”, observed that, when velocities reach the bell shaped distribution, no further net change was likely. Any single molecule might speed up or slow down, but other molecules will compensate . A good insight we can transfer to the world of Game Theory and Nash Equilibrium, relevant in reinforcement learning — say to orchestrate cars for mobility as a service !

Asimov describes masses of people in the same way Maxwell describes masses of molecules.

Nash-strategies reach a stable set of payoffs such that then, there is no incentive for any player to change the strategy. Of course, it will be different for continuous games, probably a continuous Nash Equilibrium as a set of dynamic snapshots.

Siegfried aptly concludes “the success of statistical mechanics in physics … has driven belief that it could be applied with similar success to society and social interactions..”

8: Bacon’s Links — Networks, Society and games

The combination of game theory and graph mathematics (especially the social graph, as opposed to knowledge graph or an interest graph) for predicting collective human behavior. For more notes on Twitter see OSCON-2012 tutorial.

The history of social network theory started with Swiss mathematician Leonard Euler and his analysis of the bridges in Koeinsburg; more mathematical theories developed by Paul Erdos and Alfred Renyi.

While there are network theories and metrics, describing and inferring behavior from real world complexities is a lot more harder. The topic became a lot interesting after the model of small world networks, pioneered by Watts and Strogatz in their paper in nature “Collective dynamics of ‘small-world’ networks”.

Siegfried succinctly describes network metrics like path length, clustering coefficient, cliques and k-cliques, the node degree, scale free networks, the power law [“a few big things and lots of little things”] and the power of strongly connected components. Overlaying Game Theory to the network math — ie co-operation, common good, networks and game theory, to name a few, are very relevant to modern social and commerce and economics domains and trade.

Interesting papers on networks and game theory :

Albert-Laszlo Barabasi, Reka Albert (Univ. of Notre Dame) “Emergence of scaling in random networks”.
Santos and Pacheco “Scale-Free Networks Provide a Unifying Framework for the Emergence of Cooperation”
Ebel and Bornholdt “Evolutionary games and the emergence of complex networks”

Interesting observation — “all small world networks are not scale-free e.g. power grids or nervous systems, but social networks are”

The discussion on ATP networks (the genomic network inside us responsible for metabolism), protein interactions and how game theory based co-operative behavior of multi cellular organisms are very interesting. As he mentions “on a higher evolutionary level, a combination of network math and game theory may be able to explain more advanced form of human co-operative behavior.”

9: Asimov’s Vision — Psychohistory or Sociophysics ?

Of course, my favorite chapter in the book ! This chapter encouraged me to reread the Foundation series — more interesting this time ! Link to reading Asimov updated with some more notes.

Trivia : The year was 1951 when Nash published his paper and The Foundations came out — interesting coincidence. Actually Asimov started The foundation in 1940s, still an interesting coincidence. Of course, at that time Asimov’s work was science fiction, but “Asimov’s idea for a predictive science of human history no longer seems unthinkable, it may be inevitable” !

In fact, Asimov did predict autonomous cars and even Uber !

“The field of Sociophysics, based on statistical mechanics (very similar to Asimov’s psychohistory) abstract behavior of complex systems — measuring the temperature of the society” — while molecules collide, people connect !

Serge Gallam’s work and papers by Bednar/Page titled “Can Game(s) Theory Explain Culture? The Emergence of Cultural Behavior Within Multiple Games” are interesting in terms of adding the human touch to the world of Game Theory.

Bednar’s paper is interesting because it takes the clinical “self-interest seeking rational agents operating in a context-free strategic environments” to culturally diverse, norm and patten based collective behavior. We can seek complex social behaviors, for example how students use Uber from works like these !

Interesting work on Behavioral Economics by Caltech’s Camerer has elevated Game Theory as a mathematical language for describing social interactions and global collective behavior ! Camerer’s ted talk “When you’re making a deal what’s going on in your brain” is very interesting.

The El farol Bar problem and the minority game that explores the mathematics by D. Challet and Y.-C. Zhang “Emergence of Cooperation and Organization in an Evolutionary Game” is very interesting.

10: Meyer’s Penny

This is a chapter about how Game Theory fits in the Quantum world — in fact many of the mechanics can be elegantly modeled by Quantum theory ! An interesting reference StartTrek, Captain Picard and Q (my favorite character!)

The Quantum Game Theory and Decoherence fits in very well with probability based mixed strategy.

Lots of interesting work in this area by UCSD’s David Meyer, for example “Quantum Strategies” is a must read. So is Lee and Johnson’s “Non-Cooperative Quantum Game Theory” and “Let The Quantum Games Begin”. I am sure one or more books will be written on Quantum Game Theory.

The concept of a Quantum Penny, the Quantum Entanglement, shared information and Quantum communications can greatly improve the effectiveness and make game theory more feasible and effective. For example “Proposal for optically realizing a quantum game” by and the “A Practical Quantum Mechanism for the Public Goods Game” by Chen, Hogg and Beausoleil.

11: Pascal’s Wager Games — Probability, Information & Ignorance

I really like Bertrand Russel’s quote in P.197 “All exact science is dominated by the idea of approximation !”

Trivia : Blaise Pascal at the age of 16 invented a rudimentary computer to hep calculations for his father who is a tax collector in 17th century. And Pascal invented the probability theory to help an aristocrat with a gambling habit ! Pascal’s probability discussions on thinking about the existence of God is also interesting from a historical perspective.

Current work in this area encourages the evolution of game theory from “perfectly rational ie payoff maximers with all the required information” to “limited rationality or bounded rationality”. In fact Wolpert’s “Information Theory — The Bridge Connecting Bounded Rational Game Theory and Statistical Physics” was an inspiration for writing this book !

Another interesting and widely adopted theory is the concept of MaxEntropy by Janes in his paper “Information Theory and Statistical Mechanics”, connecting Shannon’s ideas around entropy; it is finding lots of applications, especially in Machine Learning and Data Science.

The author ends the book with the observation :

Game theory is about putting it all together … offers a mathematical recipe for making sense of what seems to be a hopelessly messy world …

Well said, Tom !!

Epilogue:

In short, SiegFried’s A Beautiful Math is a must read, with a very rich treatment of the Game Theory, full of interesting anecdotes, history and luminaries, behind the sciences we take for granted, and a breadth of topics that one can dive into. I did go deeper into multiple detours & then (reluctantly) back to the main thread

I leave you with a passage Isaac Asimov’s “Foundation and the Empire”

“Attack now or never; with a single ship, or all the force in the Empire; by military force or economic pressure; by candid declaration of war or by treacherous ambush. Do whatever you wish in your fullest exercise of freewill. You will still lose.”
“Because of Hari Seldon’s dead hand?”
“Because of the dead hand of the mathematics of human behavior that can neither be stopped, swerved, nor delayed.

Probably we can say the same thing about the impending AI revolution, am sure Musk will agree !

Acknowledgements & References:

Thanks to the following blogs and links for some of the materials in this blog.