Difference between revisions of "Matrix game (LP for game theory)"

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search
(Intro)
Line 4: Line 4:
  
 
== Game Theory and Linear Programming ==
 
== Game Theory and Linear Programming ==
 +
[[File:JohnOskar.png|thumb|John von Neumann (1903–1957) and Oskar Morgenstern (1902–1977)]]
 
Game theory can be defined as a formal language for modeling and analyzing the interactive behaviors of intelligent, rational decision-makers (or players). Game theory provides the mathematical methods necessary to analyze the decisions of two or more players based on their preferences to determine a final outcome. The theory was first conceptualized by mathematician Ernst Zermelo in the early 20th century. However, John von Neumann pioneered modern game theory through his book Theory of Games and Economic Behavior, written with co-author Oskar Morgenstern. For this reason, John con Neumann is often credited by historians as the Father of Game Theory<sup>[1][2]</sup>. This theory has provided a framework for approaching complex, high-pressure situations and has a broad spectrum of applications. These applications of game theory have helped shape modern economics and social sciences as we know them today and are discussed in the Applications section below.  
 
Game theory can be defined as a formal language for modeling and analyzing the interactive behaviors of intelligent, rational decision-makers (or players). Game theory provides the mathematical methods necessary to analyze the decisions of two or more players based on their preferences to determine a final outcome. The theory was first conceptualized by mathematician Ernst Zermelo in the early 20th century. However, John von Neumann pioneered modern game theory through his book Theory of Games and Economic Behavior, written with co-author Oskar Morgenstern. For this reason, John con Neumann is often credited by historians as the Father of Game Theory<sup>[1][2]</sup>. This theory has provided a framework for approaching complex, high-pressure situations and has a broad spectrum of applications. These applications of game theory have helped shape modern economics and social sciences as we know them today and are discussed in the Applications section below.  
  
Analyzing game theoretic situations is a practical application of linear programming. These situations can get quite complex mathematically, but one of the simplest forms of game is called the Finite Two-Person Zero-Sum Game (or Matrix Game for short).  In a Matrix Game, two players are involved in a competitive situation in which one player’s loss is the other’s gain. Analyzing these games uses John von Neumann’s Minimax Theorem that was derived using the Brouwer Fixed-Point Theorem. However, over time it was proven that the Matrix Game could be solved using Linear Programming along with the Duality Theorem<sup>[3]</sup>. This solution to the Matrix game has been proven in the Theory and Algorithmic Discussion section below.
+
Analyzing game theoretic situations is a practical application of linear programming. These situations can get quite complex mathematically, but one of the simplest forms of game is called the Finite Two-Person Zero-Sum Game (or Matrix Game for short).  In a Matrix Game, two players are involved in a competitive situation in which one player’s loss is the other’s gain. Some common terms related to the Matrix Game that will be used throughout this chapter have been defined below:
 +
 
 +
'''Game''' – Any social situation involving two or more individuals <sup>[2]</sup>.
 +
 
 +
'''Players''' – The individuals involved in a game. In the case of two-person zero-sum games, these players are assumed to be rational and intelligent <sup>[2]</sup>.
 +
 
 +
'''Rationality''' – A decision maker is considered to be rational if he or she makes decisions consistently in pursuit of his or her own objectives. Assuming a player to be rational implies that said player’s objective is to maximize his or her own payoff <sup>[2]</sup>.
 +
 
 +
'''Utility''' – The scale upon which a decision’s payoff is measured <sup>[2]</sup>.
 +
 
 +
Analyzing these games uses John von Neumann’s Minimax Theorem that was derived using the Brouwer Fixed-Point Theorem. However, over time it was proven that the Matrix Game could be solved using Linear Programming along with the Duality Theorem<sup>[3]</sup>. This solution to the Matrix game has been proven in the Theory and Algorithmic Discussion section below.
  
 
== Theory and Algorithmic Discussion ==
 
== Theory and Algorithmic Discussion ==

Revision as of 12:05, 20 November 2020

Author: David Oswalt (SysEn 6800 Fall 2020)

Steward: Wei-Han Chen, Fengqi You

Game Theory and Linear Programming

John von Neumann (1903–1957) and Oskar Morgenstern (1902–1977)

Game theory can be defined as a formal language for modeling and analyzing the interactive behaviors of intelligent, rational decision-makers (or players). Game theory provides the mathematical methods necessary to analyze the decisions of two or more players based on their preferences to determine a final outcome. The theory was first conceptualized by mathematician Ernst Zermelo in the early 20th century. However, John von Neumann pioneered modern game theory through his book Theory of Games and Economic Behavior, written with co-author Oskar Morgenstern. For this reason, John con Neumann is often credited by historians as the Father of Game Theory[1][2]. This theory has provided a framework for approaching complex, high-pressure situations and has a broad spectrum of applications. These applications of game theory have helped shape modern economics and social sciences as we know them today and are discussed in the Applications section below.

Analyzing game theoretic situations is a practical application of linear programming. These situations can get quite complex mathematically, but one of the simplest forms of game is called the Finite Two-Person Zero-Sum Game (or Matrix Game for short).  In a Matrix Game, two players are involved in a competitive situation in which one player’s loss is the other’s gain. Some common terms related to the Matrix Game that will be used throughout this chapter have been defined below:

Game – Any social situation involving two or more individuals [2].

Players – The individuals involved in a game. In the case of two-person zero-sum games, these players are assumed to be rational and intelligent [2].

Rationality – A decision maker is considered to be rational if he or she makes decisions consistently in pursuit of his or her own objectives. Assuming a player to be rational implies that said player’s objective is to maximize his or her own payoff [2].

Utility – The scale upon which a decision’s payoff is measured [2].

Analyzing these games uses John von Neumann’s Minimax Theorem that was derived using the Brouwer Fixed-Point Theorem. However, over time it was proven that the Matrix Game could be solved using Linear Programming along with the Duality Theorem[3]. This solution to the Matrix game has been proven in the Theory and Algorithmic Discussion section below.

Theory and Algorithmic Discussion

  • Game Theory – Prisoner’s Dilemma
  • Stochastic Vector Introduction – Prisoner’s Dilemma with different probabilities
  • How this relates to Linear Programming
  • Minimax Theorem
    • Minimize the maximum payoff of opposing player
  • Duality Theorem

Numerical Example

  • Fourth and Goal Dilemma
  • Offensive and defensive decisions and payoffs
  • Results

Other Applications of the Matrix Game

  • Economics
  • War
  • Gambling
  • Intelligence and Foreign Policy

Conclusion

  • TBD

References

  • Add later