Graphs in Game Theory
Graphs in Game Theory
Introduction
Game theory is a field of mathematics that studies decision-making in situations where multiple players interact with each other. It has been widely used in economics, political science, psychology, and other fields to model human behaviour in strategic situations. One of the key concepts in game theory is the use of graphs to represent the relationships among players and the outcomes of their actions. In this blog post, we will explore the power of graphs in game theory and provide examples of games that can be represented using graphs.
Graphs are mathematical structures that represent the relationships between objects. In game theory, graphs are used to represent the relationships between players and the outcomes of their actions. A graph consists of a set of nodes or vertices, and a set of edges that connect the nodes. Each node represents a player or an outcome of their actions, while each edge represents the relationship between the players or the outcome of their actions.
The use of graphs in game theory allows us to model complex interactions between players in a simple and intuitive way. By using graphs, we can easily visualise the relationships between players and the outcomes of their actions, and we can analyse the behaviour of players in different scenarios.
Types of Graphs in Game Theory
There are several types of graphs that are used in game theory, including directed graphs, undirected graphs, weighted graphs, and bipartite graphs. Each type of graph has its own set of properties that make it suitable for different types of games.
1. Directed Graphs
Directed graphs are graphs in which the edges have a direction. In other words, each edge goes from one node to another in a specific direction. Directed graphs are often used to represent games in which players make sequential moves, such as chess or poker.
2. Undirected Graphs
Undirected graphs are graphs in which the edges do not have a direction. In other words, each edge connects two nodes without indicating a specific direction. Undirected graphs are often used to represent games in which players make simultaneous moves, such as rock-paper-scissors or the prisoner’s dilemma.
3. Weighted Graph
Weighted graphs are graphs in which the edges have a weight or a value associated with them. The weight or value of an edge represents the cost or benefit of a particular action or outcome. Weighted graphs are often used to represent games in which players have different preferences or utilities, such as the ultimatum game or the bargaining game.
4. Bipartite Graphs
Bipartite graphs are graphs in which the nodes can be divided into two disjoint sets, and the edges only connect nodes from different sets. Bipartite graphs are often used to represent games in which players have different roles or functions, such as the principal-agent game or the market game.
Examples of Games Represented Using Graphs
Now that we have introduced the concept of graphs in game theory, let’s look at some examples of games that can be represented using graphs.” Rock-Paper-Scissors:
This is a simple game where two players simultaneously choose one of three options: rock, paper, or scissors. The winner is determined by a set of rules that dictate which option beats which, and the goal is to win as many rounds as possible.
Graphs can be used to analyse the outcomes of rock-paper-scissors games. One common way to represent the game is by creating a circular graph, with the three options (rock, paper, scissors) placed at equal distances around the circle. Each option is then connected to the two other options by an edge, representing the outcomes of a game.
For example, if rock beats scissors, a directed edge is drawn from rock to scissors. Similarly, paper beats rock, so an edge is drawn from paper to rock, and scissors beats paper, so an edge is drawn from scissors to paper. The resulting graph will have a total of nine edges, with each option having two edges connected to it.
This graph can then be used to analyse the properties of the rock-paper-scissors game. For example, we can see that the graph is symmetric, meaning that each option has the same number of incoming and outgoing edges. This symmetry indicates that each option has an equal chance of winning, as long as the players choose randomly.
We can also use the graph to analyse strategies for playing the game. For example, if we know that our opponent tends to choose rock more often than the other options, we might choose paper more often to take advantage of this bias. By looking at the graph, we can see that paper beats rock and loses to scissors, so this strategy could be effective.
Overall, graphs can be a useful tool for analysing the properties and strategies of games like rock-paper-scissors.
Chess:
Chess is a complex strategy game that involves multiple pieces with different movements and objectives. The game can be represented using a “chessboard graph” that shows the positions of all the pieces and their possible moves. This graph can be used to calculate possible outcomes and to develop strategies for winning the game.
Graphs can be used to represent chess positions and analyse the game. In particular, graphs can be used to represent legal moves from a given position. Each vertex in the graph represents a unique position on the chess board, and each edge represents a legal move between positions.
By representing the game as a graph, it becomes possible to use graph algorithms to analyze the game. For example, finding the shortest path between two positions on the board can help a player plan their moves more effectively. Additionally, algorithms like depth-first search and breadth-first search can be used to explore different possible game paths and determine the best course of action.
In computer science, there are also algorithms specifically designed for graph games like chess, such as alpha-beta pruning and Monte Carlo tree search. These algorithms use the graph representation of the game to search through possible moves and evaluate their outcomes, helping computers to play the game at a high level.
Tic-Tac-Toe:
This is a simple game played on a 3x3 grid where two players take turns placing X’s and O’s. The first player to get three in a row wins. The game can be represented using a “tic-tac-toe graph” that shows all possible moves and their corresponding payoffs. This graph can be used to develop strategies for winning or forcing a tie.
In the game of tic-tac-toe, a graph can be used to represent the game board and the possible moves that players can make. One common representation of the tic-tac-toe board is a 3x3 grid, with each cell in the grid representing a possible move. To use a graph to represent this board, we can create a graph with nine nodes, each representing one of the cells in the grid. We can connect nodes that represent adjacent cells with edges to represent the possible moves.
Once the graph is constructed, we can use it to model the game state by assigning a player’s mark to a node whenever they make a move. For example, if player X places a mark in the centre cell of the grid, we would update the graph by marking the corresponding node as X.
To determine if a player has won the game, we can use graph traversal algorithms such as depth-first search or breadth-first search to check for a path of three connected nodes that all belong to the same player. If such a path exists, that player has won the game.
Using a graph to represent the game board in tic-tac-toe can provide a flexible and powerful framework for analysing the game and developing strategies. It can also be useful for more complex variations of the game, such as larger board sizes or games with multiple players.
Conclusion:
Graph theory has wide variety of application in different fields. One of those field is Game Theory. Graphs are very useful in logical representation of many graphs. It is useful in making strategies to win popular games such as Chess, Tic-Tac-Toe, Rock-Paper-Scissors, etc.
Now lets test your understanding,
1. Which is the following is an invalid type of a Graph?
a. Directed Graph
b. Null Graph
c. Undirected Graph
d. Proper Graph
Ans : d. Proper Graph
2. Which of the following is an invalid graph representation method?
a. Adjacency List
b. Adjacency Matrix
c. Priority List
d. Incidence Matrix
Ans: c. Priority List
3. Which one of the following is a part of every game theory model?
a. Players
b. Payoffs
c. Probabilities
d. Strategies
Ans: c. Probabilities
4. In game theory, a choice that is optimal for a firm no matter what its competitors do is referred to as
a. The dominant strategy
b. The game-winning choice
c. Super optimal.
d. Sub optimal
Ans : a. The dominant strategy
5. Which of the following is a zero-sum game?
a. Stone-Paper-Scissors
b. Chess
c. Tic-Tac-Toe
d. All of the above.
Ans: b. Chess
References:
[1] https://en.wikipedia.org/wiki/Graphical_game_theory
[3] http://www.coalitiontheory.net/research-areas/game-theory-graphs
[4] https://www.nature.com/articles/s41598-023-28627-8
Acknowledgement
I gratefully acknowledge the support, guidance, and encouragement provided by Dr. Rekha Sharma (Associate Professor, TCET).