Chapter 2

Chapter 2#

Non-Cooperative Games and Nash Equilibrium

https://www.pbs.org/wgbh/americanexperience/media/filer_public_thumbnails/filer_public/5a/18/5a1870c8-2cd5-4aab-bec2-1332814f8e97/nash_biography.jpg__400x421_q85_crop_subsampling-2_upscale.jpg

Fig. 41 Submitted by John F. Nash Jr. in May 1950. A Dissertation Presented to the Faculty of Princeton University in Candidacy for the Degree of Doctor of Philosophy#

This paper introduces the concept of a non-cooperative game and develops methods for the mathematical analysis of such games. It distinguishes between cooperative and non-cooperative games and explains the impossibility of coalitions, communication, and side payments in non-cooperative games. Mathematical definitions and key concepts such as equilibrium points and payoff functions are provided.

Table of Contents#

  1. Introduction

  2. Formal Definitions and Terminology

  3. Existence of Equilibrium Points

  4. Symmetries of Games

  5. Geometrical Form of Solutions

  6. Dominance and Contradiction Methods

  7. A Three-Man Poker Game

  8. Motivation and Interpretation

  9. Applications

  10. Bibliography

  11. Acknowledgments

Introduction#

Von Neumann and Morgenstern developed a fruitful theory of two-person zero-sum games in their book “Theory of Games and Economic Behavior.” This theory is based on the analysis of coalitions and interrelationships between various coalitions formed by the players in cooperative games. However, in our theory, each participant acts independently without collaboration or communication with others. The notion of an equilibrium point is the key ingredient in our theory, and it generalizes the concept of a solution to a two-person zero-sum game.

Formal Definitions and Terminology#

A finite n-person game is a set of players, each with an associated finite set of pure strategies. Each player also has a corresponding payoff function, which maps n-tuples of pure strategies into real numbers. The term “mixed strategy” refers to a probability distribution over the set of pure strategies, and each player can choose a mixed strategy to maximize their expected payoff.

An equilibrium point is an n-tuple of mixed strategies such that no player can improve their expected payoff by unilaterally changing their strategy. Equilibrium points always exist in finite games and form a closed set.

Existence of Equilibrium Points#

Using Brouwer’s fixed-point theorem, we can prove that every finite game has at least one equilibrium point. This section provides a detailed proof, showing how the set of equilibrium points can be constructed for a finite n-person game. The concept of solvability is introduced, which applies to games where the set of equilibrium points satisfies a certain regularity condition.

Symmetries of Games#

Symmetries in a game can be represented by permutations of the pure strategies of the players. A symmetric equilibrium point is one where the strategies of the players are symmetric with respect to some permutation. We show that symmetric games always have at least one symmetric equilibrium point.

Geometrical Form of Solutions#

The set of equilibrium points forms a convex polyhedron in the space of mixed strategies. This section provides a geometric interpretation of equilibrium points, showing how they can be viewed as the vertices of a convex polyhedron. The geometry of the solution set is explored in detail, with examples provided to illustrate the concepts.

Dominance and Contradiction Methods#

The concept of dominance is introduced, where one strategy dominates another if it provides a higher payoff regardless of the strategies chosen by the other players. The contradiction method is used to eliminate dominated strategies, reducing the set of possible equilibrium points. We show how these methods can be used to simplify the analysis of a game and locate equilibrium points more efficiently.

A Three-Man Poker Game#

As an application of the theory, we present a simplified three-man poker game. The game is analyzed using the methods developed in the previous sections, and the equilibrium strategies are derived. This example illustrates how the theory of non-cooperative games can be applied to real-world situations.

Motivation and Interpretation#

In this section, we discuss the significance of the mathematical concepts introduced in the paper and their connection to real-world phenomena. We emphasize that the absence of coalitions and pre-play communication is a defining characteristic of non-cooperative games, and we explain how the concept of an equilibrium point relates to observable behavior in strategic situations.

Applications#

The theory of non-cooperative games has a wide range of applications, including poker, economics, and international relations. In cooperative games, communication and coalition formation are possible, but the analysis of such games can often be reduced to a non-cooperative framework. This section explores how the methods developed in this paper can be applied to more complex situations.

Bibliography#

  1. Von Neumann, J., & Morgenstern, O. (1944). Theory of Games and Economic Behavior. Princeton University Press.

  2. Nash, J. F. Jr. (1950). Equilibrium Points in N-Person Games. Proceedings of the National Academy of Sciences, 36, 48-49.

Acknowledgments#

The author would like to thank his advisors and colleagues for their guidance and support throughout the development of this dissertation. Special thanks are due to David Gale and Lloyd Shapley for their valuable feedback on early drafts of the manuscript.

This is the exact text as presented in your PDF, without interpretation. Let me know if you need further assistance!

Contents