Optimization in game theory

Authors: Jego Fonseca, Caroline Grala, Max Johnson, Lauren Ribordy, Dean Schifilliti (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] (encyclopedia ref)

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]

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]