Game Theory Made Simple

Author(s): Igor Novikov

Originally published on Towards AI.

Many of you, I bet, heard about game theory at some point in your life. If you want to sound smart and impress your girlfriend — just mention “zero-sum game” and your chances to bring her home tonight have just increased by 50%. Or you can use it to make decisions like investing (which will probably ruin you) or deciding whether to marry (which is very likely to ruin you as well). An all-around useful theory as you can see.

But not only to appear smart but actually know something — let’s look at what game theory is.

The earliest mention that can be linked to game theory is found in some writings by Charles Waldegrave, an 18th-century mathematician, who developed a strategy solution for a two-person card game called “le Her”. Judging by the name he too, was trying to impress a girl. The rules of the game were lost in history but the the foundation was laid.

The modern mathematical formulation of game theory began with the 1928 paper “Theory of Parlor Games” by John von Neumann. This paper contained a systematic theory of two-person zero-sum games. The field was significantly expanded and formalized with the publication of “Theory of Games and Economic Behavior” in 1944, co-authored by John von Neumann and Oskar Morgenstern (not that Morgenstern, an actually useful one). This book applied game theory to economics and social sciences, revolutionizing these fields.

Most of the terminology is taken directly from games. Participants are called players and every action is called a move.

The real world is very complex so game theory deals with models. Before you’ve started imagining hot babes in bikinis — I mean simplified structures representing processes of the real world.

Rationality

Before we dive in, I have to note one important quality of the players — rationality. It is a quality of experienced players that know the rules and act logically, in a way to maximize their benefit. There is a funny concept in game theory called common knowledge of rationality, that assumes that you know that the other player is rational, and the other player knows that you know that he is rational, and so on, ad infinitum. Anyone who had a spouse knows that this is a huge exaggeration. That is why it is only a mere theory.

Keynesian Beauty Contest

A more practical example is the Keynesian Beauty Contest, proposed by very famous economic John Maynard Keynes, who is famous for creating the IMF and the World Bank and having a Russian wife. So, obviously, he was a smart man. He likened the stock market to a beauty contest, but not the kind where you simply pick the prettiest face. No, that would be too straightforward for our sophisticated financial world.

In this economic beauty pageant, it’s not about finding the stock with the inherent best value. Instead, it’s about guessing which stock everyone else thinks is the prettiest. It’s a second-level thinking game: you’re trying to outsmart the crowd who is trying to outsmart the crowd. It’s like playing chess with mirrors — every move reflects several layers of strategy.

So, investors scrutinize each other with a sly grin, thinking, “I know that you know that I know…” It turns the market into a hall of mirrors where seeing the truth becomes as tricky as spotting a whisper in a windstorm. This isn’t just an investment; it’s a mental acrobatics routine.

Keynes’ point highlights the irony of markets: Often, success in investing isn’t about assessing fundamental values. Instead, it’s about predicting collective psychology, akin to trying to forecast the weather based on the flapping of a butterfly’s wings. Investors become so focused on predicting others’ predictions that they might forget what they were predicting in the first place.

In a way, the Keynesian Beauty Contest serves as an ironic reminder of the world’s complexity. It’s not merely a dance of numbers and logic, but a psychological thriller where the protagonist — the rational investor — must navigate a labyrinth of reflections, perceptions, and misperceptions. It’s a serious game, indeed, but one can’t help but chuckle at its rules and the often-circular logic it inspires.

There is a simpler version of the same thought experiment proposed by Richard Taller: “Guess 2/3 of the Average” game. Participants in the game are asked to pick a number between 0 and 100. The goal is to guess what 2/3 of the average of all participants’ guesses will be. If everyone in the game is perfectly rational and knows that everyone else is perfectly rational, the logic goes like this:

The highest possible average would be 100
so 2/3 of that is 66.67

But if everyone else also calculates this — the new average to consider would be 66.67,
and 2/3 of that is about 44.44.

This iterative process continues, theoretically spiraling down to zero, as the only equilibrium in a game of fully rational players.

Financial Times actually ran this experiment and average was the number 19. How rational is that? So in reality players have “limited rationality”. Let’s not risk being burnt at the stake for speculations limited by what, but let me point out the existence of bubbles — the pinnacle of rational irrationality.

Games with simultaneous moves

The next important basic concept is games with simultaneous moves. In these games, players make their decisions at the same time, without knowledge of the other players’ choices, which is much more common in the real world. This contrasts with sequential games, where players take turns and have some information about previous moves.

A classic example of simultaneous move games is Rock-Paper-Scissors, where each player must choose one option at the same time. A classic business example is the strategic decision-making process in a duopoly market, where two companies compete on pricing. Let’s consider two companies, A and B, which produce a similar product. Each company must decide on the price of its product without knowing the pricing decision of the other.

Here’s the setup:

• Decision: each company must decide whether to set a high price or a low price for its product.
• Outcomes: the profit for each company depends not only on its own pricing decision but also on the pricing decision of the competitor.

The possible scenarios are as follows:

1. Both choose high prices: if both A and B set high prices, they maintain a higher profit margin, but the overall demand might be lower.
2. Both choose low prices: if both set low prices, the demand for their products might increase, but the profit margin decrease.
3. One high, one low: if A sets a high price and B sets a low price, customers might flock to B for the cheaper option, increasing B’s market share but decreasing A’s profit. The reverse happens if A sets a low price and B sets a high price.

In this game, each company must consider the potential pricing strategies of its competitor. If they believe the other will set a high price, they might be tempted to set a low price to capture more market share. However, if they expect the other to set a low price, they might also set a low price to remain competitive, even at the cost of reduced profit margins.

This situation can be analyzed using game theory to predict potential outcomes and to find a Nash Equilibrium, where neither company has an incentive to deviate from its chosen strategy, given the strategy of the other.

Nash Equilibrium

Nash Equilibrium: a central concept in these games was named after John Nash. In a Nash Equilibrium, no player can benefit by changing their strategy while the other players keep theirs unchanged. Since players make decisions simultaneously, they often aim to achieve the best outcome given the expected strategies of others.

Consider another example: Imagine Alice and Bob have a weekend ritual of watching movies together. Alice loves comedies, while Bob is a big fan of action movies. However, both of them are ok to watch documentaries together:

Here’s how their movie-picking adventure unfolds:

1. The Movie Choice: every Saturday night, they have to choose what genre of movie to watch. They write down their choice on a piece of paper without telling the other. The choices are Comedy, Action, or Documentary.
2. The Different Tastes: if Alice chooses Comedy and Bob chooses Action, they can’t agree, so they end up not watching anything, and both lose. If both choose the same genre — they watch that genre.
3. If they are both rational — the only choice they have is Documentary, and that is what they choose, based on the understanding that the other party will choose the same. It is not an optimal outcome for each of them but it definitely explains why I watched so much anime.

The Prisoner’s Dilemma

The Prisoner’s Dilemma is another classic example in the field of game theory that illustrates why two rational individuals might not cooperate, even if it appears that it’s in their best interest to do so. This dilemma is presented as a story involving two criminals, named Alice and Bob, who have been arrested and are being interrogated in separate rooms.

Here’s the setup:

1. The Crime: Alice and Bob are partners in crime and are arrested for a crime they committed together. The police don’t have enough evidence to convict them on the primary charge, but they have enough to convict both on a lesser charge.
2. The Interrogation: the police separate Alice and Bob, offering each the same deal: If one testifies against the other (defects) and the other remains silent (cooperates), the defector will be freed, and the cooperator will get a heavy sentence (say, 10 years). If both remain silent, they will both be convicted of the lesser charge and receive a moderate sentence (say, 2 years each). If both betray each other, they will both receive a significant sentence (say, 5 years each).
3. The Dilemma: the dilemma arises because each prisoner has two options, neither of which they can make confidently without knowing the other’s decision. The optimal outcome for both would be to cooperate and remain silent, resulting in a total of 4 years in prison between them. However, the fear that the other might defect and leave them bearing the heavy sentence often leads each to defect, resulting in a total of 10 years in prison between them. In game theory, they say that the “betray” strategy dominates others.

This scenario demonstrates the difficulty in achieving the best outcome when individuals cannot trust each other to cooperate. The Prisoner’s Dilemma has been applied to a variety of fields and situations beyond criminal investigations, including economics, politics, and biology, to explain behaviors in competitive environments where the outcome for each participant depends on the actions of others.

This word exists in the real world in many forms. For example Nuclear Arms race or AI race. It could be beneficial for all participants to come to an agreement and stop the race but since each party does not trust the others — it is only rational to continue increasing the arsenals.

Sometimes there is more than one equilibrium point in the situation. This is called Multiplicity of equilibria and means that depending on initial conditions or the behavior of the participants, the system can settle into different stable states. These points might represent very different outcomes in terms of the payoffs for the players.

Often, which equilibrium is reached depends on the expectations and coordination of the agents involved. For instance, if all economic agents expect a market to thrive, their investments can lead to a prosperous equilibrium. Conversely, if they expect it to fail, their lack of investment can lead to a poor equilibrium.

Example — bank runs: a classic example is a bank run. There are two equilibria: one where everyone trusts the bank and keeps their money there (no bank run), and one where everyone doubts the bank and tries to withdraw their money, creating the state called self-fulfilling prophesy, leading to the collapse of the bank (bank run). No run condition is stable until there is trust in the bank- but if people see a long line in front of the bank to withdraw money- they will try to withdraw too. This is a way of coordination, which usually comes in the form of observing what other participants do or social norms.

Same for equities or currency markets. A speculative attack by hedge funds when they first take a stake in the company or short its stock and then release some kind of investigation — in an attempt to shift Nash equilibrium to the new point. There are funds that specialize in that kind of behavior. The most famous case of this is George Soros shorting the British pound in 1992.

Mixed strategy games

So far we were talking about equilibrium in pure strategies, where players make decisions with confidence because there is only one rational choice. But this is not always possible. Let’s take the paper-scissors-rock game. It’s a zero-sum game, meaning that if one participant wins — the other loses. So players act unpredictably — because if a player’s actions could be predicted — the other player will use that to his advantage. These types of situations have no equilibrium and are random. The same happens in real life in the case of tax evasion. Since auditing everyone for the tax authorities is not possible, some taxpayers might choose to evade taxes hoping they will not be audited. They may do that based on their own considerations but from the outside, this decision looks random. And for tax authorities, the only rational decision is to randomly pick whom to audit, because they don’t know who is trying to evade.

Repeated Games vs One-Shot Games

We’ve only talked about One-Shot Games so far, where participants interact only once. Decision-making in such games is based solely on the situation at hand, without considering future interactions or past history. An example is the classic Prisoner’s Dilemma, where two criminals decide without knowing and without expecting future interactions with the other.

There are also Repeated Games: In repeated games, the same game (or very similar games) is played multiple times, often with an indefinite number of repetitions. So it is a bit more like a marriage vs one nightstand in a bar. In such situations, players take into account previous interactions when making decisions and can develop strategies based on observations of other players’ behavior. This allows for the development of concepts such as trust, punishment for undesirable behavior, and cooperation.

In one-shot games, players often lean towards more aggressive or selfish strategies, as there are no consequences for future interactions. In repeated games, conversely, players might aim for cooperation and sustainable strategies, as actions in one round can influence the behavior of others in subsequent rounds.

Example with the Repeated Prisoner’s Dilemma: If the Prisoner’s Dilemma is repeated many times, players might choose a cooperative strategy to maximize overall benefit in the long term, even if it seems less advantageous in the short term. Reinhard Zelten actually ran this experiment where people played Prisoner’s Dilemma for money, but they didn’t know when the game would end. Cooperative strategies were the most common.

Evolutionary Game Theory

As you remember from the beginning, classical game theory views all participants as rational. But there were people that saw this is clearly not the case. John Maynard Smith and George Price, on account of meeting too many British scientists, had another opinion. They said that many behaviors of people and animals are socially and genetically programmed. Their game of Hawks vs Doves is still a basic principle of evolutionary biology. This game points out the importance of evolutionary stability.

In this game, Hawks will always fight for available resources and Doves will demonstrate the willingness to fight but in reality, will cede. Let’s say the potential evolutionary value (for survival) of the resource is 100:

If a Dove encounters a hawk — it will always flee, so the result is always:

Hawk: 100, Dove: 0

If a Dove encounters another Dove — one of them will flee, with a 50% chance. On average they will each get 50% of the reward so the result is:

Dove 1: 50, Dove 2: 50

If a Hawk encounters a Hawk — they will fight, and one will win, the other will lose. Additionally, both of them can be harmed in a fight and get a penalty for survival (which is basically the cost of the conflict). On average they will win in 50% of cases, so the average result is:

Hawk 1: (100 - penalty)/2, Hawk 2: (100 - penalty)/2

What if the cost of the conflict is less than the reward? Then for a rational player, the only rational strategy is the Hawk strategy, and there are going to be a lot of fights. Let’s look at the example where the penalty is 40 and the reward is 100:

In this case, the hawk always wins something, and a lot against doves. In such cases, aggressive behavior has better results and chances for survival. This can affect the physical qualities of the species in their evolution. For example, animals tend to get bigger since bigger animals are stronger and survive in conflict better.

But if the cost of a conflict is higher than the reward — the situation changes. Let’s say the penalty is 120:

Ouch.. Now it all depends on how many Hawks are there in the population. If too many — there will be a lot of fights with lethal endings, so it’s no fun to be a Hawk, and being a Dove is a better strategy. Let’s call a chance to meet a Hawk p, then a chance to meet a Dove is (1- p). The evolutionary fitness of the Dove is:

dove_fittness = (p * 0) + # reward against Hawk
(1 - p)*(100/2) # reward against Dove

or
dove_fittness = 50–50p

And for Hawk:

hawk_fittness = p*((100–120)/2) + # reward against Hawk
(1 - p)*100 # reward against Dove

or
hawk_fittness = 100–110p

So it only makes sense to be a Hawk if: hawk_fittness > dove_fittness, or:

100–110p > 50–50p

or
p < 5/6

Therefore, if there are less than 5/6 of Hawks in the population — it is better to be a Hawk in this case. So optimal proportion of Hawks will be close to 5/6 and Doves to 1/6, resulting in evolutionary equilibrium. Animals are not rational in the common sense, but this equilibrium is equal to the Nash Equilibrium as if they were rational.

Nothing lasts forever, as we know from the ancient wisdom of Guns N’ Roses so changes in the environment would be constantly shifting shit the cost of the conflict, and the proportion of Hawks and Doves will change as well.

Games with sequential moves

Are games where players make their moves one after another, rather than simultaneously. This type of game involves a clear order of play, allowing players to observe and respond to the actions of others before making their own moves. Many sequential move games are games of perfect information, meaning each player, when making a decision, is fully aware of all the moves previously made.

A classic example of a sequential move game is chess. Each player observes the other’s move before deciding their next action. The strategy involves anticipating future moves of the opponent based on the current state of the game.

Sequential games are often represented using game trees, which visually depict the sequence of moves and the possible outcomes of each choice. Each node in the tree represents a point of decision for a player, and the branches represent the possible moves they can make.

Players in sequential games must plan their strategies by considering the potential responses of their opponents to each move. This often involves thinking several steps ahead, predicting opponents’ reactions, and adjusting strategies accordingly.

Beyond board games, sequential move games model real-world scenarios like business negotiations, bidding processes, and even certain aspects of political strategy, where the timing and sequence of actions are key to the outcome.

A common method of analysis in sequential games is backward induction, where players anticipate the end of the game and reason backward to determine the best course of action at earlier stages. This method is particularly useful in finite games where the sequence of moves is clearly defined.

Coming back to our previous example with Bob and Alice:

• Alice starts by choosing between ‘Watch Comedy’ (her top choice), ‘Watch Action Movie’ (her second choice), or ‘Do Nothing’ (least preferred).
• If Alice chooses a movie, Bob then decides whether to ‘Join’ or ‘Do Nothing’.

The rewards are assigned as follows:

• If they watch a movie together, they receive their preferred rewards (Alice gets 100 for comedy and 50 for action; Bob gets 100 for action and 50 for comedy).
• If one watches a movie alone, they get half of their reward for that choice.
• If both choose ‘Do Nothing’, the reward is 0 for each.

This game obviously has the advantage of the first move. Nash equilibrium here is for Bob to agree to watch Comedy. But not all games are like that and there are aspects that can shift the equilibrium. For example, if Bob is ballsy (or mad) enough can state that he will not watch comedy no matter what — then if Alice is rational — she will choose to watch Action.

Sometimes war is also a game with sequential moves, especially in the political plane: opponents analyze the actions of each other and respond. For example, as of now Nuclear strike only seems to be possible as retaliation for another nuclear strike (and hence nobody wants to strike first).

Games with asymmetric information

These are games where players do not have equal access to entire information about the game and some have more information. This imbalance of information affects the strategies and decisions of all players involved.

Players with more information can exploit their informational advantage, while players with less information have to strategize considering potential information asymmetries.

Types of asymmetric information:

• Hidden Actions: also known as a game of “moral hazard,” where one player’s action is not observable by others. For example, an employer cannot perfectly monitor an employee’s effort level.
• Hidden Information: also known as a game of “adverse selection,” where one player has private information that others do not have. For example, a seller of a used car knows more about the car’s condition than potential buyers.

Examples:

• Insurance Market: insurance companies often face asymmetric information as they might not know the true health condition or risk profile of their clients.
• Financial Markets: investors may have different information about the value or risk of an investment, leading to phenomena like insider trading.

Signaling and Screening: in response to asymmetric information, players may engage in signaling (sending credible signals to convey their private information) or screening (taking actions to reveal or deduce the hidden information of others). For example, job candidates might signal their ability through degrees or credentials, while employers might screen candidates through tests or interviews.

Asymmetric information games often use refined equilibrium concepts like Bayesian Nash Equilibrium, where players have beliefs about unknown factors and maximize their expected utility based on these beliefs.

Market for lemons

Asymmetric information can lead to market failure and following regulations, as seen in the classic example of the “market for lemons” by George Akerlof. Sellers of used cars know if their car is a peach (good) or a lemon (bad), but buyers, unfortunately, aren’t psychic. They judge all cars as half-lemon, half-peach hybrids, offering a price that’s somewhere in the middle. Sellers of peaches aren’t amused by these lowball offers and pull their cars out of the market, leaving it overrun with lemons. The result? A fruit salad nobody wants to buy.

This conundrum of peaches bowing out and lemons taking center stage extends far beyond used cars. It’s like trying to buy a mystery box — you hope for a treasure but often end up with a trinket. To avoid a market flooded with metaphorical lemons, we’ve devised solutions like warranties, certifications, and regulations that prohibit this kind of behavior.

Marketing, and specifically brand reputations can also work as a sort of guarantee because a company that spent tons of money on marketing is unlikely to willingly cheat and thus risk the bad publicity.

Group decisions

Sofar we have looked at games with individual players. But what if decisions are made by the group? This is a separate, difficult topic as it turned out (unsurprisingly) that the decisions of a group could be irrational even if every member is rational. The reason is that for a rational person, all his decisions are transient. Meaning that if I prefer hotdogs over burgers, and burgers over salad — I should prefer hotdogs over salad.

Unfortunately for a group, it is not the case, because the priorities of individual players in the group could be different and unaligned. Kenneth Arrow won a Nobel prize for his thesis that states that for a group with independent members, decisions can always become non-transient and appear irrational (need not go far for examples — anyone who participated in committees knows that already).

If you have questions or comments — write them in the comments section.

Links to resources used in this article:

1. https://en.wikipedia.org/wiki/Game_theory
2. https://en.wikipedia.org/wiki/Prisoner%27s_dilemma

Peace!

Join thousands of data leaders on the AI newsletter. Join over 80,000 subscribers and keep up to date with the latest developments in AI. From research to projects and ideas. If you are building an AI startup, an AI-related product, or a service, we invite you to consider becoming a sponsor.

Published via Towards AI