Repeated game

Imagine you play a game with a friend. You might play it once or many times.

If you play many times, you might act differently. You may want to keep a good name. This helps you work together. Some games have a set end. Other games go on for a long time. Playing many times can change how you play. It helps people choose to be kind.

Imagine you play a game with a friend. If you only play once, you might act selfishly. You might try to win quickly without caring about your friend. But what if you play the same game many times? This is called a repeated game. In these games, your actions today affect your future. Your past choices build your reputation.

For example, two gas stations near each other might compete on price. If they only compete once, they might both lower prices too much. This hurts their profits. But if they compete every day, they might learn to work together.

Some games are finite. This means you know exactly when the game ends. In these games, players often stop cooperating near the end. This is because there is no future to worry about. Other games are infinite. This means the game goes on for a long time or never ends. In infinite games, people can use a trigger strategy. This is a way to punish someone who breaks the rules. If a player is selfish, the other player can make them lose later. This helps people choose to cooperate instead of being selfish.

Imagine you are playing a game with a friend. If you only play once, you might act selfishly to win. You might not care how your choice affects your friend. But what happens if you play the same game many times? This is called a repeated game. In these games, your actions today change what happens tomorrow. Your past choices help build your reputation with others. This reputation tells people if they can trust you or not.

Let's look at how this works with two gas stations.

Imagine they are next to each other. They both want to make a high profit. If they both keep prices high, they both do well. However, one station might try to steal customers by lowering its price. This is a single-shot game where everyone acts in their own interest. In a repeated game, they compete over a long time. This long view changes how they choose their prices.

There are two main types of repeated games. The first type is a finite game. In a finite game, players know exactly how many rounds will be played. They know when the very last round will happen. This can cause a problem called unravelling. Since the last round has no future, players act selfishly. This logic moves backward to the second-to-last round and so on. The second type is an infinite game. These games go on for many rounds without a known end.

In infinite games, players often find better ways to work together. They might use something called a trigger strategy. This is a plan to punish anyone who breaks the rules. If a player is selfish, the other player can punish them later. This punishment makes both players lose money or points. Because of this, it is often smarter to cooperate. This helps everyone reach a socially optimum result. This idea is part of what scientists call Folk Theorems.

Math helps us understand these tricky choices. Scientists use tools like linear algebra to solve complex games. They also study how people value rewards over time. Some people care more about winning right now. Others are patient and care about winning over many years. By studying these patterns, we learn how people interact. We can see how rules and punishments keep things fair. It shows us why working together can be a winning plan.

In game theory, a repeated game is a type of interaction where players engage in a base game multiple times. This base game is often called a stage game. While a single-shot game involves only one interaction, a repeated game allows players to consider the future. Players must account for how their current choices influence the future behavior of others. This influence is often described as a player's reputation.

To understand the mechanics, consider two adjacent gas stations competing on price.

Both stations have the same constant marginal cost, which is the wholesale price of gasoline. If both stations set a high price, they maximize their joint profit. However, a station might be tempted to deviate by lowering its price to steal customers. In a single-shot game, this selfish move is common. This leads to a Nash equilibrium where prices drop to the marginal cost, which is inefficient for both businesses. In a repeated game, the interaction continues over an indefinite time range, changing the incentives.

Repeated games are divided into two main classes: finite and infinite. Finite games occur when players know the exact number of rounds that will be played. These games can often be solved using a method called backward induction. In this process, players look at the final round and work their way back to the start. Infinite games are played an infinite number of times, or for an unknown number of rounds. Because there is no final round, backward induction cannot be used to solve these games. The difference between these two types is significant, as they lead to very different optimal strategies and equilibria.

In infinitely repeated games, players often find ways to cooperate rather than following the selfish Nash strategy of a single stage game. This cooperation can lead to a socially optimum strategy. To maintain this, players use strategies to punish those who deviate from the cooperative plan. One example is a trigger strategy. If a player acts selfishly, the other player responds with a punishment that reduces the payoffs for both parties for the rest of the game. This threat makes cooperation more valuable than the immediate gain of acting selfishly.

Mathematical models help describe how players value these future payoffs. One method is the limit of means, which looks at the average utility over an infinite path of outcomes. Another method is discounting. In discounting, a player's valuation of a reward diminishes over time based on a discount factor, represented by the symbol delta. If a player is sufficiently patient and has a high enough discount factor, many different strategies can become a Nash equilibrium. These various results regarding how to maintain cooperation are collectively known as Folk Theorems.

Finite games behave differently depending on the number of Nash equilibria in the stage game. If the stage game has only one unique Nash equilibrium, the repeated game often results in players playing that same equilibrium every round. This happens because the known end date causes the game to "unravel" through backward induction. However, if a stage game has multiple Nash equilibria, players can use them to reward or punish others. For example, in a two-stage game, Player 1 might offer a reward in the second round if Player 2 cooperates in the first. If Player 2 deviates, Player 1 can threaten a punishment in the final round.

Researchers use advanced mathematical tools to study these complex interactions. Many techniques for solving repeated games rely heavily on linear algebra. Some studies also involve fictitious play to understand how players react to others. Furthermore, scientists study games with incomplete information. This involves situations where one player has information that the other does not. Researchers like Aumann and Maschler pioneered the study of these games. By understanding these patterns, we can see how long-term relationships and reputations shape the way people and businesses interact.