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]