A Guide to Mathematical Studies (Archive)

Rudimentary Game Theory – An Introduction

—

by

Isaac Teng
in ,

When John Forbes Nash first pioneered his idea of Nash Equilibrium, he revolutionized the field of game theory and laid the foundation for understanding strategic decision-making in competitive situations. His groundbreaking concept, introduced in his doctoral thesis in 1950 and later expounded upon in his seminal paper “Non-Cooperative Games” published in 1951, fundamentally changed the way economists and mathematicians analyze interactions between rational actors. Today I would like to talk about Game Theory, what it is, and how we can use it to model real-life interactions and potentially solve conflicts. Let’s begin!

John Forbes Nash.

So what is Game Theory? According to the Cambridge Dictionary, it is “a mathematical theory about how decisions are made in situations where one person’s decision affects another, that is used in many fields such as economics, psychology, and biology”. In essence, it is the mathematics of choice and its influence cannot be underestimated.

Going into the history of Game Theory, it stems from the early works of John von Neumann, who published the paper On the Theory of Games of Strategy in 1928. The paper went into foundational concepts such as zero-sum games and the minimax theorem which we will discuss later, laying the groundwork for subsequent developments in the field. This was the groundwork for the mathematical formalization of strategic decision-making and paved the way for the emergence of game theory as a distinct branch of mathematics and economics.

Following von Neumann’s pioneering contributions, other influential figures further expanded and refined the field of game theory. Notably, mathematician John Nash introduced the concept of Nash equilibrium in the 1950s, providing a powerful framework for analyzing non-cooperative games where players act independently to maximize their own utility.

Nash’s work, alongside contributions from scholars like John Harsanyi and Reinhard Selten, propelled game theory into a central area of study within economics, political science, and other social sciences. It has since become a valuable tool for analyzing a wide range of strategic interactions, from negotiations and auctions to voting behavior and international relations. In particular, the idea of Nash equilibrium and the minimax theorem has propelled the development of further investigation into the field, which we will be discussing today.

Let’s start by discussing Nash equilibrium. Nash’s notion of equilibrium describes a set of strategies where no player has an incentive to deviate from, which earned him the Nobel Prize in Economic Sciences in 1994. To gain a better understanding of Nash equilibrium, we can look at a famous example – the prisoner’s dilemma.

The problem is as follows : Two suspects are arrested and placed in separate cells, with no means of communication. The authorities offer each suspect a deal: if one confesses and implicates the other, they will not be charged, while the other suspect will receive a sentence of 10 years. However, if both suspects remain silent, they will both receive a sentence of 1 year, and if both are implicated, they recieve a sentence of 5 years.

A graphical representation of the problem.

In such a scenario, what should the suspects do? The reasonable choice would obviously be for both suspects to coorporate to get a shorter sentence. However, since the suspects are unable to communicate and do not know each other’s actions, they are incentivized to minimize their potential sentence individually. As a result, they may choose to implicate each other in order to protect themselves from the worst possible outcome, even though cooperating would lead to a better collective outcome.

In this case, this option is known as the Nash equilibrium of the problem, as even if the suspects know what the other suspect was choosing, the option would not change. If the prisoner knew the other prisoner was choosing to remain silent, he would confess to go free, while if the other prisoner chose to confess he would also confess to reduce his possible sentence. As shown by John Nash himself in 1950, Nash equilibriums exist for all finite games1. One may thus be tempted to ask whether this is the case for infinite games or games of unknown length – this is not the case as we shall demonstrate below.

Instead of prisoners now we consider a game where the setup is in essence the same but instead of penalties, we now operate a firm and are competing directly with another firm for sales. We can choose to hold down or increase our output, and the respective payouts are as below.

If say this was a one-off choice, we see that this is exactly the same as the prisoner’s dilemma, thus we deviate to our Nash equilibrium, i.e. to increase output. This is the same for a known finite number of games : in the last round to maximise profit the natural choice would be to increase output, however the same argument could be made for the game before and so on and so forth – thus for the entire game both players do not coorporate and retain Nash equilibrium.

For unknown lengths however or infinite games, the situation diverges. As the end-point of the game is unknown, to maximize profit the two players will inadvertently have to coorporate. In 1980, Professor Robert Axelrod at the University of Michigan held a tournament for the exact situation described above and had programs play against each other and themselves repeatedly2. The results showed that Tit-for-Tat suprisingly was the best option among all algorithms (which is not of Nash equilibrium). Four factors were identified from this experiment :

  1. Nice – The algorithm begins with cooperation and only defects in response to competition.
  2. Forgiving – The algorithm immediately produces cooperation should the competitor make a cooperative move.
  3. Provocable – It provides immediate retaliation for those who compete.
  4. Clear – Players facing against it quickly recognize its contingencies and adjust their behavior accordingly.

Tit-for-Tat, having these qualities, is superior to other algorithms most of the time. Thus in this case to maximize profits, the firms would play Tit-for-Tat instead of defecting all the time as in Nash equilibrium. However, do note that this is not the best way to approach all algorithms. For example, by playing Tit-for-Tat against itself, if one algorithm defects the game will be locked in a state of retaliation cycles or mutual defection, which is obviously suboptimal.

Pareto optimal strategies are also important in such scenarios. These are strategies where it is impossible to make any one individual better off without making at least one individual worse off. Nash strategies may also be Pareto efficient however this is not a guarantee. An example of Pareto optimal strategy is the cooporation of the 2 firms as mentioned above. By choosing to increase output one must necessarily make the other firm worse off – thus firms will choose to maximize overall welfare or utility without wasting or misallocating resources by using a strategy which is Pareto efficient.

Here, to get a better sense of how game theory can arise in more familiar scenarios, I would like to talk about Nash equilibrium in different games in the traditional sense, namely Tic-Tac-Toe and Connect 4. Tic-Tac-Toe, due to its small size, can easily be analyzed by considering all possible moves. By doing so, we can show that players will always tie given they play perfectly. This occurs because both players are using strategies that prevent their opponent from winning, leading to a situation where neither player can achieve a victory. This is called a solved game, i.e. given that all players play optimally, the outcome of the game is predetermined.

Nash equilibrium also arises in Connect 4, which is another solved game, where the first player to start will always win (again assuming that everyone plays perfectly). In Connect 4, as a zero sum game, i.e. where the interests of the players are directly opposed, meaning that one player’s gain is the other player’s loss, the game can be analysed by the minimax algorithm3.

Expressing the minimax theorem in mathematical notation :

Let X \in \mathbb{R}^n and Y \in\mathbb{R}^m be compact convex sets. If f : X\times{Y}\rightarrow\mathbb{R} is a continuous function that is concave-convex, i.e. f(\cdot, y) : X\rightarrow\mathbb{R}is concave for fixed y, and f(x, \cdot) : Y\rightarrow\mathbb{R} is convex for fixed x, then we have the following :

{\displaystyle \max _{x\in X}\min _{y\in Y}f(x,y)=\min _{y\in Y}\max _{x\in X}f(x,y).}

This is described in more detail here4. However, the important thing to note about this is that it allows for an algorithm to parse the game and select definitively what steps to take. The first player can always force a win by starting in the middle column with perfect play, as shown by James Dow Allen and by Victor Allis independently in October 1988. Here we also link the original method developed to analyse Connect 4 using game theory by Allen. By employing the minimax algorithm, artificial intelligence achieves a high level of proficiency in game-solving, making it exceedingly challenging for human players to defeat AI opponents.

To recap today’s introduction to game theory, we talked about Nash equilibrium, Pareto optimal strategies and the minimax theorem. If you would like to learn more about game theory which we have only scraped the surface of today, please do look at the links attached below for reference – in particular I would recommend Dr. Bazett’s series for a more entry-level point of view and Dr. Polak’s for those who would like to persue Game Theory as a field of study. As always, thank you for reading and I will see you next month!

References :

  1. https://www.youtube.com/watch?v=dgxPlUgIqSA
    ‘MatPat’s FINAL Theory!’ – The Game Theorists
  2. https://www.youtube.com/watch?v=mScpHTIi-kM
    ‘What Game Theory Reveals About Life, The Universe, and Everything’ – Veritasium
  3. https://www.youtube.com/playlist?list=PLHXZ9OQGMqxdzD8KpTHz6_gsw9pPxRFlX
    ‘Game Theory – A Youtube Series’ – Dr. Trefor Bazett
  4. https://oyc.yale.edu/economics/econ-159 ‘Game Theory’ – Dr. Ben Polak

Footnotes:

  1. https://www.ncbi.nlm.nih.gov/pmc/articles/PMC1063129/ ↩︎
  2. https://cs.stanford.edu/people/eroberts/courses/soco/projects/1998-99/game-theory/axelrod.html ↩︎
  3. https://medium.com/analytics-vidhya/artificial-intelligence-at-play-connect-four-minimax-algorithm-explained-3b5fc32e4a4f ↩︎
  4. https://www.inf.ed.ac.uk/teaching/courses/agta/lec4_landscape.pdf ↩︎

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *