Introducing Game Theory

József Konczer, Wolfram Research

(RowDefault[, (Spacer1), , (Spacer1), ])  #WolframTechConf

ABSTRACT

Game theory was originally proposed to model the economic behavior of rational agents.
Besides the introduction of influential concepts in economics and finance, it provided useful tools in other human-related fields such as sociology, politics and military strategy.
The framework appeared to be applicable in evolutionary biology, information theory and control theory as well.
In my presentation, I want to introduce the basic concepts of the framework and their implementation into the Wolfram Language.
In more detail, I will talk about non-cooperative game theory modeled by matrix games (a.k.a. normal-form games) and tree games (a.k.a. extensive-form games). I will present the proposed construction, visualization and solution methods for these objects.

Table of Content

Motivation and Assumptions

Basic Concepts and Notation

Matrix Games (aka Normal Form Games)

Tree Games (aka Extensive Form Games)

Visualizations

Finding Equilibria

Using other BackEnds

A Real World problem

Future Plans

Motivation and Assumptions

What is Game Theory?

A simple Definition:
The study of strategically interdependent behaviour.

strategically interdependence: 
what I do, affects your outcomes, and what you do, affects my outcomes.

Examples :

Games with simultaneous actions:

Rock-Paper-Scissors

Soccer penalty kicks

Interrogation of prisoners

Sequential Games:

Classic board games

Tic-Tac-Toe

Chess

Poker

Repeated Games

The canonical example: Prisoners Dilemma

A well known game: Rock Paper Scissors

Assumptions for Matrix Games

There are finite number of Players

Every Player can choose from (a possibly different) finite set of Actions (aka Moves)

Outcomes of the Game can depend on all Players chosen Action

Players can NOT communicate with each other

Players can “Randomize” their strategies, if desirable

Players are “Rational”, meaning they are aiming to maximize their Expected Utility

Associating Utilities to Outcomes for each Player can be a nontrivial modelling problem

For small monetary gains and losses it can be approximated by the monetary Payoffs

In general we assume, that these are known.

All above property (including every Players Action dependent Payoff) is Common Knowledge

meaning every Player knows, and every Player knows that every (other) Player knows, etc.

Tree Game Examples

Tic-Tac-Toe

Poker

,... Iterated Games

Assumptions for Tree Games

The Game Play can go trough stages (or rounds)

In each round one of the following can happen:

One Player can chose from finite many Actions

A Random choice is made (by “Nature”) from finite alternatives

The Game terminates, and all Players receives given Payoffs

The Game must end after a Finite number of rounds

There can be stages, which are not distinguishable by some Players

The subset of  indistinguishable stages form a so called Information Set

In Information Sets all Stages must lead to the same number of Actions, and there must be a one to one map between them

Basic Concepts and Structure

Matrix Games

Players:

Action set for Player : ,

Action profile ,

, represents the “Payoff matrix” (or Utility Tensor/Array).

gives the utility vector for Action Profile .

Wolfram Language representation:

uPD=(({{{-5,-5}, {0,-20}}, {{-20,0}, {-1,-1}}}))

Gpd=MatrixGame[uPD,"ActionLabels"->{{"Confess","Remain Silent"},{"Confess","Remain Silent"}},"PlayerLabels"->{"A","B"}]

Basic Concepts and Structure

Tree Games

Extensive Form Games can be represented by a Rooted Tree

Nodes are decorated:

A Node can be a Player Node, decorated by Player Index (or Label)

Leaf Node, which must contain a Payoff vector

Or a Chance Node, which contains no Player Index, but must contain Action Probabilities

Nodes with the same Player Index, and same number of children can belong to the same Information Set:

Information Sets give an extra Hypergraph structure to the Tree.

Wolfram Language representation:

Rmp=
\[LeftAssociation]"Player"->1\[RightAssociation]->
{
\[LeftAssociation]"Player"->2,"InformationSet"->1\[RightAssociation]->
{
\[LeftAssociation]"Payoffs"->\[LeftAssociation]1->1,2->0\[RightAssociation]\[RightAssociation],
\[LeftAssociation]"Payoffs"->\[LeftAssociation]1->0,2->1\[RightAssociation]\[RightAssociation]
},
\[LeftAssociation]"Player"->2,"InformationSet"->1\[RightAssociation]->
{
\[LeftAssociation]"Payoffs"->\[LeftAssociation]1->0,2->1\[RightAssociation]\[RightAssociation],
\[LeftAssociation]"Payoffs"->\[LeftAssociation]1->1,2->0\[RightAssociation]\[RightAssociation]
}
};

Tmp=RulesTree[Rmp]

TreeGame[Tmp]

Basic Concepts and Structure

Optimal Strategy Concepts for MatrixGames

A Strategy of the (k^th) Player,  is a Probability Distribution on the Action Set

A Strategy Profile  is a collection of individual Strategies

The Expected Utility for Player  is:

We call  a Nash Equilibrium, if there is no Player who could increase its Expected Utility by changing on his/her own strategy.

Wolfram Language representation:

First@FindMatrixGameStrategies[GameData["RockPaperScissors"]]

Basic Concepts and Structure

Optimal Strategy Concepts for TreeGames

A Behavioral Strategy for Player  is represented by a collection of Probability Distributions on the Actions, which can be chosen by the Player on their Nodes.

The Distributions have to be the same on Nodes belonging to the same Information Set

In this way a Behavioral Strategy Profile decorates all Nodes with Action Probabilities.

Behavioral Strategy Profile determines an Expected Utility vector:

A Nash Equilibrium can be defined in a similar way

A useful new Equilibrium concept is Subgame Perfect Equilibrium

Which can be calculated effectively if the Information Set structure is simple.

WL Functionalities

MatrixGame Visualization

GameData["RockPaperScissors"]
%//MatrixGamePlot

GameData["PrisonersDilemma"]
MatrixGamePlot[%,{{1},{2}},"PlayerNodes"->False,"PlotLegend"->True]

GameData[{"DinersDilemma",3,{1,2,1,3}}]
MatrixGamePlot[%,{{1},{2,3}},"PlotLegend"->True]

GameData[{"DinersDilemma",4,{1,2,1,3}}]
MatrixGamePlot[%,{{1,2},{3,4}},"PlotLegend"->True]
MatrixGamePlot[%%,{{1},{2,3,4}},"PlotLegend"->True]

GameData["BattleOfTheSexes"]
MatrixGamePlot[%,{{1},{2}},"PlayerNodes"->False,"PlotLegend"->True]

GameData[{"ElFarolBar",3,0.7}]
MatrixGamePlot[%,{{1},{2,3}},"PlotLegend"->True]

GameData[{"ElFarolBar",3,0.6}]
MatrixGamePlot[%,{{1},{2,3}},"PlotLegend"->True]

WL Functionalities

TreeGame Visualization

GameData["TreeMatchingPennies"]
TreeGamePlot[%]

MatrixPlot[-{{1,-1,0},{1,-1,1},{0,0,-1}}]
GameData[{"TicTacToe",{{1,-1,0},{1,-1,1},{0,0,-1}}}];
%//TreeGamePlot

TreeGamePlot[GameData[{"Truel",{1,1,1},{1/2,1/3,1/4}}]]

Calculating Nash Equilibria

Two Player Games

FindMatrixGameStrategies[GameData["RockPaperScissors"]]

FindMatrixGameStrategies[GameData["PrisonersDilemma"]]

FindMatrixGameStrategies[GameData["BattleOfTheSexes"]]
MatrixGamePlot[GameData["BattleOfTheSexes"],{{1},{2}},"PlayerNodes"->False,"PlotLegend"->True]

Multiplayer Games

FindMatrixGameStrategies[GameData[{"ElFarolBar",3,0.7}]]
Length[%]

FindMatrixGameStrategies[GameData[{"DinersDilemma",4,{1,2,1,3}}]]

FindMatrixGameStrategies[GameData[{"DinersDilemma",4,{1,2,1,10}}]]

GameData[{"DinersDilemma",4,{1,2,1,10}}]
MatrixGamePlot[%,{{1,2},{3,4}},"PlotLegend"->True]

Compatibility with Open Source Packages

Supporting Multiplayer Games

Various Methods

CommandLine connectivity

Many Builtin Games

Issues with 64-bit machines

Not too active project (github activity from 1996 to 2020)

Two Player Games

FindMatrixGameStrategies[GameData["BattleOfTheSexes"],"BackEnd"->"Gambit","Method"->"Polynomial"]

FindMatrixGameStrategies[GameData["BattleOfTheSexes"],"BackEnd"->"Gambit","Method"->"PolynomialMixed"]
FindMatrixGameStrategies[GameData["BattleOfTheSexes"],"BackEnd"->"Gambit","Method"->"GlobalNewton"]
FindMatrixGameStrategies[GameData["BattleOfTheSexes"],"BackEnd"->"Gambit","Method"->"IteratedPolymatrix"]

Multiplayer Games

FindMatrixGameStrategies[GameData[{"ElFarolBar",3,0.7}],"BackEnd"->"Gambit","Method"->"Polynomial"]
FindMatrixGameStrategies[GameData[{"ElFarolBar",3,0.7}],"BackEnd"->"Gambit","Method"->"PolynomialMixed"]
FindMatrixGameStrategies[GameData[{"ElFarolBar",3,0.7}],"BackEnd"->"Gambit","Method"->"GlobalNewton"]
FindMatrixGameStrategies[GameData[{"ElFarolBar",3,0.7}],"BackEnd"->"Gambit","Method"->"IteratedPolymatrix"]

NashPy

Two Player Games Only

Few but effective Methods

Python compatibility

Recently Active project (github activity from 2017 to 2021)

FindMatrixGameStrategies[GameData["BattleOfTheSexes"], "BackEnd" -> "NashPy", "Method" -> "SupportEnumeration"]
FindMatrixGameStrategies[GameData["BattleOfTheSexes"], "BackEnd" -> "NashPy", "Method" -> "VertexEnumeration"]
FindMatrixGameStrategies[GameData["BattleOfTheSexes"], "BackEnd" -> "NashPy", "Method" -> "LemkeHowsonOne"]
FindMatrixGameStrategies[GameData["BattleOfTheSexes"], "BackEnd" -> "NashPy", "Method" -> "LemkeHowsonAll"]

Solving a Real World Problem

How to model Penalty kicks in Soccer

IGNACIO PALACIOS-HUERTA: Professionals Play Minimax

From Galileo to penalty shootouts: data, economics and human behaviour

GameData["MatchingPennies"];
MatrixGamePlot[%]
FindMatrixGameStrategies[%%]

uPK=(({{{58.30,100-58.30}, {94.97,100-94.97}}, {{92.91,100-92.91}, {69.92,100-69.92}}}))

MatrixGame[uPK];
MatrixGamePlot[%]
FindMatrixGameStrategies[%%]

Future Plans

Coming Next:

Compatibility with Gambit File Format(s) .efg  and .nfg

Finding Subgame Perfect Equilibrium for TreeGames

Converting TreeGames to MatrixGames

In the foreseeable future:

Approximative Methods

Interactivity, AutoPlay

Refined Equilibria

Evolutionary Stable Strategies

Correlated Equilibria

etc.

Possible further directions:

Evolutionary Game Theory

Bayesian Games

Coalitional (aka Cooperative) Game Theory

Iterated Game Theory

Connections with other fields:

Reinforcement Learning

Control Theory

Mechanism Design

For more insight see the LiveStreams when the project has been initiated:

Part1

Part2