Optimization in game theory

Authors: Jego Fonseca(jfs244), Caroline Grala(cg677), Max Johnson(gh436), Lauren Ribordy(lkr34), Dean Schifilliti(dts87) (SysEn 5800 Fall 2021)

Introduction

Game Theory (GT) is a branch of mathematics that analyzes and predicts trends in a number of different game scenarios with a varying number of players. The application of GT can be found in a multitude of disciplines, including economics, biology, political science, computer systems, and philosophy [1].

Emile Borel has been credited with being the first mathematician to suggest a formal theory of games in 1921, but the popularity of GT became more apparent in 1944 when John von Neumann and Oskar Morgenstern published “Theory of Games and Economic Behavior”. In the 1950s and 1960s, GT application was expanded to war, politics, philosophy, and political and social sciences [1].

In general, games are broken down into two main categories: noncooperative and cooperative. Within these two categories, many different game types exist. Noncooperative games are defined as games where “each participant acts independently, without collaborating with the others, and chooses their strategy for improving their own benefit,” whereas cooperative games are defined as games where “a set of players seek to form cooperative groups to improve their performance in a competitive game, and to enable players to succeed in reaching objectives that they may not accomplish independently” [1].

Optimal choices and their relative influence on the game can be analyzed through the mathematical methods in GT. However, the number of possible combinations increases exponentially with the number of players, so the optimal solution may not always be a computationally realistic possibility. This article aims to discuss the theory and methodology, provide numerical examples, and discuss the applications of GT [1].

Theory, methodology, and/or algorithmic discussions

Theory

Nash Equilibrium

The Nash Equilibrium is a fundamental concept in game theory. It is most widely used in predicting the outcome of a strategic interaction in the social sciences. A game consists of: a set of players, a set of actions available to each player, and a payoff function for each player. The payoff function is a player’s preference of the action profiles. A “pure-strategy Nash equilibrium” is an action profile with the property that no single player can obtain a higher payoff by deviating from this profile. [2]

The classic game Prisoners’ Dilemma is widely used to demonstrate the Nash equilibrium. In this decision game, if one player stays silent while the other talks, that player will get 10 years in prison. If they both talk, they both get 8 years. If neither talk, they both will get 2 years. The Nash equilibrium for this game is each player talking and getting 8 years. While both players staying silent is the optimal solution, neither of the players have incentive from deviating to this profile because the player who remains silent is worse off. [3]

Payoffs for two players in Prisoner's Dilemma game. [3]

Methodology

Nash Equilibrium is commonly used as an example to describe a non-cooperative game involving two or more people. Mixed Integer Linear Programming is an optimization method that aims to either maximize or minimize a linear objective function given at least one constraint. In addition, some of the variables in a MILP problem are discrete while others are continuous. Nash equilibrium can be found through mixed-integer linear programming optimization. It can also be found using other optimization methodologies, such as the one created by Tsaknakis and Spirakis. Their method takes the maximum deviation of a player’s payoff from the best payoff that could be achieved by the other players based on their strategy of choice [7].

Linear programming (LP) is another method used in optimization to describe a problem that has an objective function, constraints, and variables that are both linear and continuous. It can be used to determine an optimal strategy for simple games like rock-paper-scissors or more complex ones like poker [5]. The goal is similar to an MILP problem in that it quantifies decision consequences in order to achieve a specific outcome [6]. For the rock-paper-scissors game where there are two players involved, one player’s set of options are defined as a, where a = {1, 2, and 3} and the other as b, where b = {1, 2, and 3}. Each player can decide from one of three options, i.e. rock, represented by the number 1 and so forth. Their choice results in either a win, loss, or draw with the payoff represented by 1, -1, or 0, respectively. Depending on the established amount of times that the game is played, a matrix can be generated to model the outcome and size from the set of decisions made by both players.

Algorithm

The common algorithm associated with computing a Nash Equilibrium is the Lemke-Howson algorithm. This algorithm utilizes iterated pivoting much like the simplex algorithm used in the simplex algorithm used in linear programming. A notable difference between the two algorithms is that unlike the simplex algorithm, the Lemke-Howson algorithm cannot be run in polynomial time. The Lemke-Howson algorithm can be considered a brute force algorithm in which we utilize a possible solution as a guess and continue to adjust it through each iteration until we have arrived at the Nash equilibrium. [7]

The tableau method is a pivoting process that can be used to find the Nash equilibrium using the Lemke-Howson algorithm. The first step is preprocessing, the goal here is to limit the options of the game by iterating to maintain the dominating strategies. This reduces the problem complexity and thus the work required to solve it. The initialization of the tableau is the next step. One tableau is needed for each player in the game. Now with a constructed tableau we can begin pivoting. The primary aspect here are the entry and exit variables. The exit variable is the entry variable to the next pivot until the complementarity conditions are met. [7]

Numerical Example

A town has two competitors for taxi services—Beru and Fylt. Consumers will choose between the two companies based on their prices and availability, i.e. the cost of a ride based on distance and the wait time for a ride.

Beru has more availability, but has historically higher prices. Fylt is a newcomer looking to challenge Beru. Fylt is trying to decide how to develop its brand and where it stands to make most profit: capturing the market for people who take long and expensive but inconvenient rides, such as going to the airport, or for people who take short and inexpensive but convenient rides, such as going to a grocery store.

Fylt’s data analysis department has analyzed sales data and created the following strategic form price matrices for both far and short distance rides:

Fylt and Beru 1

Fylt and Beru 2

The Fylt finance department receives the cost matrices and performs calculations to inform the company’s future strategy.

Fylt draws up the following diagrams to determine the dominant strategies for both Beru and Fylt. Circled in green is the best choice given the two terminal options.

• Is there a dominant strategy for Beru and/or Fylt? If so, what is it?

When the distance is far, the dominant strategies for both Beru and Fylt are to do low prices.

When the distance is short, Beru does not have a dominant strategy because its optimal price depends on whether Fylt chooses to price low or high. If Fylt prices low, Beru should go low; but if Fylt prices high, Beru should go high. Fylt has a dominant strategy for short distances: low prices.

• What is the Nash equilibrium, if it exists?

Based on the data, the Nash equilibrium for short distances and long distances is for Beru and Fylt to do low prices. So for far trips, Beru will make 150, and Fylt 100. For short trips, Beru will make 30 and Fylt will make 50.

• How should Fylt invest to outcompete Beru—in doing more short or long distance trips?

Fylt should invest in scaling up its short distance trips.

Applications

The application of GT can be found across a multitude of disciplines, but the general framework of GT allows players to compare the outcomes of different decisions. A list of popular applications for GT will be discussed, and these game examples can be altered and applied to a wide range of scenarios.

Game Examples

Stag Hunt

This game balances safety and social cooperation. Two hunters go for a hunt, and each must choose to hunt a stag or a hare, without knowing which the other chooses. In order for the hunters to take down a stag, both must hunt the stag. Each may hunt a hare individually, but the payoff from the hare is less than that of the stag. The goal is to maximize payoff [1].

The Battle of Sexes

This game falls into the category of coordination games and is based around the decisions for what two individuals will do on a given night. For instance, a girlfriend and boyfriend prefer to go to the opera and a football game, respectively. They do not decide on where they are going before leaving for the day and do not communicate with each other throughout the day. They prefer the place that they chose, but they would prefer to go to the same place. The goal is to maximize happiness [1].

The Prisoner’s Dilemma

Two criminals are arrested, imprisoned, and isolated from each other. Without enough evidence to accuse either criminal of a crime, there are three possible outcomes: both reveal evidence and both stay in prison for 4 years, one reveals evidence and one stays silent so the one that reveals is set free while the one that stays silent serves 5 years, and if both prisoners stay silent then both will only remain in prison for 2 years. The goal is to minimize prison time [1].

Extensions of GT

Evolutionary Game Theory

GT was developed on human interaction, but the theory was applied in biology to model how animals behave when competing for a resource. Rather than using logic, the players, or animals, instead are motivated by reproductive success. In Evolutionary Game Theory, the success is based on the frequency of success against competing strategies. In the end, successful strategies will be used more frequently and be the final victor [1].

Behavioral Game Theory

While computers may try to optimize utility and use perfect logic, humans have been found to not always use logic or maximize utility. Instead, Behavioral Game Theory attempts to model and predict human choices in games, rather than advise the optimal solution. Experimental data is leveraged to show trends and account for external factors, such as emotions, bounded rationality, cultural influences, and reputation among others on the decisions that humans make in games [1].

Mechanism Design

Mechanism design introduces a reverse approach to GT in that the objective is known while the rules and mechanisms are unknown. The game must be designed such that players are incentivized to behave as the designer intended. As an example, a Vickrey auction style is an example of auctioning where the good goes to the highest bidder at the price of the second-highest bid. This form of game incentivizes players to be honest in their evaluation of the good [1].

Conclusion

This article summarized GT, a branch of mathematics that analyzes and predicts trends in a number of different game scenarios with a varying number of players. The theory and methodology, numerical implementation, and the wide variety of applications of GT were discussed. GT has existed since 1921, is still applied today, and will continue to be useful to individuals across all disciplines, such as the future development of Artificial Intelligence [1].

References

1. Burguillo, Juan C. “Game Theory.” Self-Organizing Coalitions for Managing Complexity, 2017, pp. 101–135., https://doi.org/10.1007/978-3-319-69898-4_7.
2. Cournot, A. A. et al, "Nash Equilibrium," International Encyclopedia of the Social Sciences, 2nd Edition, ed. William A. Darity, Jr. (Michigan: Gale, 2008).
3. Stephen Woodcock Lecturer in Mathematics. “The Legacy of John Nash and His Equilibrium Theory.” The Conversation, 21 Oct. 2019, https://theconversation.com/the-legacy-of-john-nash-and-his-equilibrium-theory-42343.
4. “Nash Equilibrium.” Wikipedia, Wikimedia Foundation, 25 Nov. 2021, https://en.wikipedia.org/wiki/Nash_equilibrium.
5. Dotzenrod, Nick, and Matt Kweon. “Matrix Game (LP for Game Theory).” Optimization, 2014, https://optimization.mccormick.northwestern.edu/index.php/Matrix_game_(LP_for_game_theory).
6. You, Fengqi. “6800-LP F21.” Optimization Modeling.
7. http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=AE0EBA82161430FD61B8915771E19649?doi=10.1.1.110.770&rep=rep1&type=pdf