Game Theory
Swift — Problems Catalogue — S02 #1 Decision Making
Welcome to the second series of the Swift Problems catalogue. I really hope you liked the first series focused on common software design patterns.
This second series is focused on much broader problems, problems that spawned entire fields, especially in mathematics. We are gonna look at them through the looking glass of a software engineer and use Swift code to describe the mathematical formulas.
Of course, this article only serves as a gentle introduction to the topic at hand. The topics treated in this series are too vast to be covered in just one article. Use this paper as a starting point for exploration.
In this article, we’re gonna explore one of the most fundamental parts of being…well…being human. When faced with situations of competition and conflict, how do we make decisions?
What is Game Theory?
Game theory studies precisely that: the science of decision-making.
This branch of mathematics aims to model the strategic interactions between different actors that have conflicting interests in order to identify the optimal decision-making strategies.
It gives you a framework for analyzing complex decision-making scenarios, predicting outcomes, and understanding how individuals or groups can improve their outcomes by cooperating or competing strategically.
The Basics:
Let’s start with the basics and that’s:
The Utility function
Basically, it measures the wins and losses of each player at the end of a game. The main hypothesis here is to consider the concept of utility as an amount that can be measured numerically.
But how can you measure utility? It is a concept that is very subjective. One thing has more utility for a person than for another one.
Well, the objective is not to measure the absolute utility but two compare two situations in a way in which you can determine what has more utility in comparison with another. And here the concept of order relation from math comes into play.
The math expression for utility is the following.
U(x) = f(x)Now, let’s switch that math expression to code:
func calculateUtility(outcome: String) -> Double {
switch outcome {
case "Win":
return 1.0
case "Tie":
return 0.5
case "Loss":
return 0.0
default:
return 0.0
}
}Perfect, now it’s much clearer. Based on the string outcome the utility function returns a value.
If we want to compare utilities between them we say that:
u > v => V(u) > V(v)In the first case before the “=>” symbol we mean that u is preferred to v. It means that a player prefers the scenario with the u utility instead of the scenario with the v utility.
In the second case after the “=>” symbol we mean that the value of the utility function V based on scenario u is higher than the utility function V based on scenario v.
Allocation, dominance and solution
Now, here are some other basic concepts that we need.
In game theory, allocation refers to the division of resources or payoffs among players in a game. This allocation can be based on multiple criteria, such as fairness, efficiency or strategic considerations. For example, in an auction game, the allocation of the item being auctioned would be the assignment of the item to the highest bidder.
We say that a win allocation with X utility > a win allocation with Y utility if the utility function V(X) > than the utility function V(Y).
The number of people that will see their win increase by switching from X to Y is called the effective group for X’s dominance over Y.
A strategy is said to be dominant if it is always a player’s best choice, regardless of the choices made by other players. Dominance can be either strict (i.e., the strategy is always better) or weak (i.e., the strategy is at least as good as any other). A player may have multiple dominant strategies or no dominant strategies at all.
We define a Solution as:
A group S of allocations that accomplish the following:
- Not a single element y from S is not dominated by another element X from S.
- All allocations y that are not in S are dominated by an element X from S.
This is pretty much the math definition of a solution but in other words, a solution is a concept that describes a set of outcomes that are considered desirable or optimal in some sense.
The general definition
Now, in game theory, a game is defined as a mathematical model that describes the interactions between multiple decision-makers (players) who have conflicting objectives.
The elements of this model (game) are the following:
- First and foremost, the players.
- Strategies, which represent the total possible choices that a player has.
- Payoffs are the rewards or penalties that each player receives for choosing a particular strategy.
- The Rules that govern the game, including how the payoffs are calculated and how players make their decision.
- Information or the amount of knowledge each player has about the game, including the strategies chosen by the other players.
- Last but not least, Timing or the sequence of events that occurs during the game, including when each player makes their decision.
Let’s define a simple game where two players (Player 1 and Player 2) can choose to cooperate or defect. The payoff matrix for this game is as follows:
| Cooperate | Defect
----------------------------------
Cooperate | 3, 3 | 0, 5
----------------------------------
Defect | 5, 0 | 1, 1In this matrix, the first number in each cell represents the payoff to Player 1, while the second number represents the payoff to Player 2.
For example, if both players cooperate, they both receive a payoff of 3.
if Player 1 cooperates and Player 2 defects, Player 1 receives a payoff of 0 and Player 2 receives a payoff of 5.
Let’s put the game into code:
// Player definition
enum Player: Int {
case player1 = 1
case player2 = 2
}
// Strategies
enum Strategy {
case cooperate
case defect
}
// Payoff matrix
let payoffMatrix: [[(Int, Int)]] = [
[(3, 3), (0, 5)],
[(5, 0), (1, 1)]
]
// Payoff calculation of a player based on the strategies chosen by both players
func calculatePayoff(player: Player, player1Strategy: Strategy, player2Strategy: Strategy) -> (Int, Int) {
let row = player1Strategy == .cooperate ? 0 : 1
let col = player2Strategy == .cooperate ? 0 : 1
let payoff = payoffMatrix[row][col]
if player == .player1 {
return payoff
} else {
return (payoff.1, payoff.0)
}
}We define the Player and Strategy enums to represent the players and strategies in the game. Then, we define the payoffMatrix as a matrix of tuples, where each tuple represents the payoffs to each player for a particular combination of strategies.
Finally, we define the calculatePayoff() method that takes the strategies chosen by both players and returns the payoffs to the specified player as a tuple.
Now, this implementation demonstrates just the basic elements of a game: players, strategies and payoffs. We could extend this implementation to include the other elements of a game like information, timing and rules depending on the specifics of the game that we want to create.
Alright, alright, then the obvious question appears: how many types of games CAN we create?
The answer is…quite a few and each has its own set of characteristics and strategic considerations. Here are some of the most common types of games:
Cooperative games
Non-cooperative games
Zero-sum games
Non-zero sum games
Simultaneous games
Sequential games
Perfect information games
Imperfect information games
Stochastic games
Symmetric games
Asymmetric games
Bayesian games
Evolutionary games
Combinatorial games
…
These are just a few examples of types of games that exist in game theory. There are many more variations and combinations of these types (ex: Sequential-move, zero-sum games), and each type presents its own challenges and strategic considerations for the players involved.
There are quite a lot of them and truth be told, a number of articles can be written just about one of them.
So, in this article, we will focus only on one type and that is the sum-zero type in its simplest form.
Sum-zero games between two players
In a sum zero game, the total payoff to the players is zero. This means that any gains made by one player come at the expense of the other player.
The classic example of a sum zero game is poker: if one player wins, the other player loses an equivalent amount. The sum of the winnings and losses is zero.
In game theory, sum zero games are studied using mathematical models that define the players’ strategies and the payoffs associated with different outcomes. These models can be used to predict how players will behave in real-world situations and to help players make optimal decisions.
Another important concept in sum zero games is “dominant strategies”. A dominant strategy is a strategy that is the best option for a player, regardless of the other player’s actions. For example, in a game of rock-paper-scissors, there is a dominant strategy for each player: always choose rock, paper, or scissors, respectively. This ensures that the game is fair and neither player has an advantage.
In order to model a sum zero game, we need to define the following:
- Players: in this case, we have two players, player1 and player2
- Strategies: in this game, each player can choose one of three possible strategies: rock, paper, or scissors.
- Payoff: the payoff is the gain or loss of a player based on the outcome of the game. If a player wins the other one loses.
Let’s put the game into code:
// Strategy Definition
enum Strategy {
case rock
case paper
case scissors
}
// Player Definition
enum Player: Int {
case player1 = 1
case player2 = 2
}
// Define the payoff matrix
let payoffMatrix: [[Int]] = [[0, -1, 1], [1, 0, -1], [-1, 1, 0]]
// In this matrix, the row player is player 1 and the column player is player 2
// The first index of the matrix corresponds to the strategy of player 1, and the second index corresponds to the strategy of player 2
// Payoff value of a player based on the strategies chosen by both players
func calculatePayoff(player: Player, player1Strategy: Strategy, player2Strategy: Strategy) -> Int {
let row = player1Strategy.hashValue
let col = player2Strategy.hashValue
let payoff = payoffMatrix[row][col]
if player == .player1 {
return payoff
} else {
return -payoff
}
}
// Example usage
let player1Strategy = Strategy.rock
let player2Strategy = Strategy.paper
let player1Payoff = calculatePayoff(player: .player1, player1Strategy: player1Strategy, player2Strategy: player2Strategy) // returns -1
let player2Payoff = calculatePayoff(player: .player2, player1Strategy: player1Strategy, player2Strategy: player2Strategy) // returns 1In this implementation, we define the strategies, players, and payoff matrix as enums. We then define a function to calculate the payoff of a player based on the strategies chosen by both players. Finally, we put them all together and we calculate the payoffs of player1 and player2 given their strategies.
Alright, but what do we do if we want to improve our odds? Well, we can try to change our strategy. But till what end?
One key concept in sum zero games is the “Nash equilibrium”. This is a situation in which neither player can improve their outcome by changing their strategy, given the other player’s strategy. In other words, both players are playing optimally, given the other player’s actions.
Nash’s equilibrium
The Nash equilibrium is a solution concept for non-cooperative games, where players are assumed to be rational and strategic. In such games, each player’s payoff depends not only on their own actions but also on the actions of their opponents. The Nash equilibrium is a set of strategies, one for each player, such that no player can improve their payoff by unilaterally changing their strategy, given the other players’ strategies.
In other words, it is a situation where both players are making the best decision given the decision of the other player.
To find the Nash equilibrium of the above rock-paper-scissors game, we need to identify the strategies that each player will choose given the strategies of the other player. In a sum zero game, the Nash equilibrium occurs when both players choose their strategies randomly with equal probabilities, since this ensures that the expected payoff for each player is zero, and neither player can unilaterally improve their payoff.
Let’s update our code from above:
// Strategy definition
enum Strategy {
case rock
case paper
case scissors
static func random() -> Strategy {
let allValues = [rock, paper, scissors]
let randomIndex = Int.random(in: 0..<allValues.count)
return allValues[randomIndex]
}
}
// Player definition
enum Player: Int {
case player1 = 1
case player2 = 2
}
// Payoff matrix definition
let payoffMatrix: [[Int]] = [[0, -1, 1], [1, 0, -1], [-1, 1, 0]]
// Provides Payoff value of a player based on the strategies chosen by both players
func calculatePayoff(player: Player, player1Strategy: Strategy, player2Strategy: Strategy) -> Int {
let row = player1Strategy.hashValue
let col = player2Strategy.hashValue
let payoff = payoffMatrix[row][col]
if player == .player1 {
return payoff
} else {
return -payoff
}
}
// Find the Nash equilibrium
let strategy1 = Strategy.random()
let strategy2 = Strategy.random()
let player1Payoff = calculatePayoff(player: .player1, player1Strategy: strategy1, player2Strategy: strategy2)
let player2Payoff = calculatePayoff(player: .player2, player1Strategy: strategy1, player2Strategy: strategy2)
if player1Payoff == 0 && player2Payoff == 0 {
print("Nash equilibrium: player 1 chooses \(strategy1), player 2 chooses \(strategy2)")
} else {
print("No Nash equilibrium found")
}In this implementation, we define a random() function for the Strategy enum that chooses a random strategy with equal probabilities. We then use this function to find the Nash equilibrium of the game by choosing a random strategy for each player and checking if the resulting payoffs are both zero.
If they are, we print out the strategies as the Nash equilibrium; otherwise, we print out that no Nash equilibrium was found. Note that since the game of Rock-Paper-Scissors is also a symmetric game, there are multiple Nash equilibria where both players choose their strategies randomly with equal probabilities.
The Nash equilibrium is a powerful tool for predicting behaviour in many different types of games, including auctions, bargaining, and voting. It has also been used to study social phenomena such as cooperation, trust, and the evolution of social norms.
However, the Nash equilibrium has some limitations.
First, it assumes that players are rational and have complete information about the game. In reality, players may have limited information, may not be perfectly rational, or may be motivated by factors that go beyond simple self-interest.
Second, the Nash equilibrium may not always exist or may be multiple, which can make it difficult to apply in practice.
Despite these limitations, the Nash equilibrium remains an important concept in game theory and social science. Its insights have been used to develop better strategies for negotiation, conflict resolution, and economic policy, and its influence can be seen in many areas of modern life.
Nash’s disequilibrium
While the Nash equilibrium represents a stable solution where no player has the incentive to change their strategy, the Nash disequilibrium represents a situation where players have the incentive to deviate from their current strategies.
In a Nash disequilibrium, one or more players have an incentive to change their strategies, which creates a situation of instability and uncertainty. This can lead to a range of outcomes, including a new equilibrium, a cycle of oscillation between strategies, or even a complete breakdown of the game.
In our case, if one player always plays Rock, the other player can exploit this by always playing Paper, resulting in a higher payoff for the second player. This leads to a state of disequilibrium, where one or both players may be motivated to change their strategy in order to achieve a higher payoff.
The Nash disequilibrium can arise in many different types of games, including those involving strategic alliances, asymmetric information, and incomplete contracts. It is an important concept because it highlights the limits of the Nash equilibrium as a predictive tool for real-world situations.
While the Nash equilibrium remains a useful and influential concept in game theory and social science, the Nash disequilibrium reminds us that not all situations can be easily modeled using a simple equilibrium framework.
In some cases, the best strategy may be to intentionally create disequilibrium, for example by using strategic shocks or other tactics to disrupt the stability of the game. Understanding both equilibrium and disequilibrium is essential for making optimal decisions in complex strategic situations.
Real-World Usage:
Ok, ok…so, this intro into game theory looks nice…but what can I do with it you may ask. Well…you can enhance your knowledge of this mathematical framework and take game theory into game practice.
There are a plethora of fields in which you can apply this mathematical framework. To name a few, fields like:
- Economics where you can model and analyze markets, auctions and the dynamics of price competition.
- Law where you can model and analyze legal disputes and decision-making. See the behaviour of litigants in legal disputes, the effects of legal rules and regulations on social behaviour and the dynamics of legal negotiations.
- Biology where you can study the evolutionary dynamics and the behaviour of animals and plants in different ecological contexts. You can study the evolution of cooperation, how predators and prey behave and the dynamics of social interactions within groups.
- Political science where you can model and analyze political decision-making, voting behaviour, international relations and the behaviour of political parties.
- Computer science where you can model and analyze algorithms, network usage, the behaviour of users in online social media, and the performance of distributed computing systems.
From this point on, the sky is the limit 🚀 well…almost.
Of course, this article is only a gentle introduction to Game Theory. If you want to go further and in more detail, I recommend starting with the book that started it all. You can find it here.
This is the first article in the second series of the Swift Problems Catalogue. In this series I’ll tackle different problems and provide an overview on them with a software development looking glass. The aim is to have a quick reference guide that can be easily accessed when having a design/algorithm dillemma.
Let me know what you think and don’t be shy to share where and when this pattern simplified your coding experience 🎶
