Game Theory

Game theory is a framework for analysing interactions between a set of agents. It is an abstract specification of interactions, describing each agent’s preferences in terms of their utility. We assume agents want to maximise utility.

Link to original

Playoff Matrix

Playoff Matrix

A playoff matrix is a table where the strategies of one player are listed in rows (agent $i$) and the other player in columns (agent $j$).

			$j$
		left		right
	left		1		0
$i$		1		0
	right		0		1
		0		1

Each player picks a pure strategy.

Link to original

Outcome (Game Theory)

An outcome is what we get when we combine the actions of all the players. It corresponds to an element of the payoff matrix. We identify outcomes by the moves the players make: $(\text{what i plays},\text{what j plays})$

Link to original

Rational Agent Behaviour

We look at different strategies rational agents can pick.

Dominant Strategy

Dominant strategy

Given any particular strategy $s$ (either C or D) agent $i$, there will be a number of possible outcomes. We say $s_1$ dominates $s_2$ if every outcome possible by $i$ playing $s_1$ is preferred over every outcome possible by $i$ playing $s_2$.

Link to original

Example

In this example, $C$ dominates $D$ for both players.

There are two interpretations of ‘preferred’:

• Strong domination (strategy)

  Strong domination: $s_1$ dominates $s_2$ if utility of every outcome possible by $i$ playing $s_1$ is strictly greater than every outcome possible by $i$ playing $s_2$. $u(s_1)>u(s_2)$ for all outcomes

  Link to original

• Weak domination (strategy)

  Weak domination: $s_1$ weakly dominates $s_2$ if utility of every outcome possible by $i$ playing $s_1$ is no less than every outcome possible by $i$ playing $s_2$. $u(s_1)\ge u(s_2)$ for all outcomes

  Link to original

A rational agent will never play a dominated strategy, so in deciding what to do, we can delete dominated strategies. (however there isn’t always a unique un-dominated strategy)

Nash Equilibrium

Nash Equilibrium

If two strategies are best responses to each other, then they are in Nash equilibrium.

In general, we say that two strategies $s_1$ and $s_2$ are in Nash equilibrium (NE) if:

1. under the assumption that agent $i$ plays $s_1$, agent $j$ can do no better than play $s_2$; and
2. under the assumption that agent $j$ plays $s_2$, agent $i$ can do no better than play $s_1$

Neither agent has any incentive to deviate from a NE.

Link to original

Nash Equilibrium solution

A pair of strategies $(i^{\ast },j^{\ast })$ is a Nash equilibrium solution to the game $(A,B)$ if:

$$\begin{array}{rl}\forall i,a_{i\ast ,j\ast }& \ge a_{i,j\ast }\\ \forall j,b_{i\ast ,j\ast }& \ge a_{i\ast ,j}\end{array}$$

That is, $(i^{\ast },j^{\ast })$ is a Nash equilibrium if:

• if $j$ plays $j^{\ast }$ then $i^{\ast }$ gives the best outcome for $i$
• if $i$ plays $i^{\ast }$ then $j^{\ast }$ gives the best outcome for $i$

Unfortunately:

1. not every interaction scenario has a pure strategy NE
2. some interaction scenarios have more than one NE

Link to original

Example

Consider the payoff matrix:

Here the NE is $(Y,Y)$. If $i$ assumes that $j$ is playing $Y$, then $i$‘s best response is to play $Y$. Similarly for $j$.

You can find the NE by cycling through all outcomes and asking if either agent can improve its payoff by changing strategy:

• $(Y,Y)$ is NE
• $(X,Y)$ is not NE as $i$ can switch payoff from $1$ to $2$ by switching to $Y$
• $(Y,X)$ is not NE as $j$ can switch payoff from $1$ to $2$ by switching to $X$
• $(X,X)$ is not NE as both $i,j$ can switch payoff from $3$ to $4$

Example

Consider this scenario:

There is an NE for the play $(A,D)$.

Pareto Optimality

Pareto Optimal

An outcome is said to be Pareto optimal (or Pareto efficient) if there is no other outcome that makes one agent better off without making another agent worse off.

If an outcome is Pareto optimal, then at least one agent will be reluctant to move away from it (because this agent will be worse off).

If an outcome $\omega$ is not Pareto optimal, then there is another outcome ${\omega }^{\prime }$ that makes everyone as happy, if not happier, than $\omega$.

“Reasonable” agents would agree to move to ${\omega }^{\prime }$ from $\omega$ if $\omega$ is not Pareto optimal and ${\omega }^{\prime }$ is.

Link to original

Example

This game has one Pareto efficient outcome $(D,D)$. There is no solution in which either agent does better.

Example

This game has two Pareto efficient outcomes, $(C,D)$ and $(D,C)$.

Example

This game has a Pareto optimal outcome, $(A,D)$:

Social Welfare

Social Welfare (rational behaviour)

The social welfare of an outcome $\omega$ is the sum of the utilities that each agent gets from $\omega$:

$$\sum _{i\in Ag}{u}_i(\omega )$$

As a concept, it may be appropriate when the whole system (all agents) have a single owner.

Link to original

Example

In both of these games, $(C,C)$ maximises social welfare.

Normal form games

Normal form games

An $n$-person, finite, normal form game is a tuple $(N,A,u)$ where:

• $N$ is a finite set of players
• $A=A_1\times \dots \times A_n$ where $A_i$ is a finite set of actions available to $i$ Each $a=(a_1,\dots ,a_n)\in A$ is an action profile.
• $u=(u_1,\dots ,u_n)$ where $u_i:A\mapsto \mathcal{R}$ is a real-valued utility function for $i$.

Represented by $n$-dimensional matrix.

We analyse games in terms of strategies, that is what agents decide to do. An agent’s strategy set is its set of available choices.

Link to original

Common payoff games

Common payoff game

Any game with $u_i(a)=u_j(a)$ for all $a\in A_i\times A_j$ is a common payoff game.

Link to original

Misanthropes’ (un)coordination game

Misanthropes' (un)coordination game

We try to avoid each other:

Link to original

Common sum games

Common sum game

Any game with $u_i(a)+u_j(a)=c$ for all $a\in A_i\times A_j$ is a constant sum game.

Link to original

Zero-sum games

Zero-sum game

A particular category of constant sum games are zero-sum games. Where utilities sum to zero:

$$u_i(a)+u_j(a)=0\text{ for all }a\in A_i\times A_j$$

They are strictly competitive scenarios.

Link to original

Mixed Strategies

Mixed strategy

A fixed / pure strategy is easy for an adaptive player to beat. A mixed strategy is just a probability distribution across a set of pure strategies.

For a game where agent $i$ has two choices $a_1$ and $a_2$, a mixed strategy for $i$ is the distribution: $M{S}_i=\{P(a_1),P(b_2)\}$ Given this strategy, when $i$ comes to play, they pick action $a_1$ with probability $P(a_1)$, and the same for $a_2$ with probability $P(a_2)$.

To determine the mixed strategy, $i$ can compute the best values of $P(a_1)$ and $P(a_2)$. These will be the values which give $i$ the highest expected payoff given the options that $j$ can choose and the joint payoffs that result.

Link to original

Example

Consider the payoff matrix:

$i$‘s analysis of the game would look like this:

This analysis will help $i$ and $j$ choose a mixed strategy in zero-sum games.

Nash equilibrium in mixed strategies

Nash Equilibrium in mixed strategies

We don’t always have a pure strategy NE, but every game has at least one mixed strategy Nash equilibrium.

For a game with payoff matrices $A$ (to $i$) and $B$ (to $j$), a mixed strategy $(x^{\ast },y^{\ast })$ is a Nash equilibrium solution if:

$$\begin{array}{r}\forall x,x^{\ast }A{y}^{\ast T}\ge xA{y}^{\ast T}\\ \forall y,x^{\ast }A{y}^{\ast T}\ge x^{\ast }B{y}^T\end{array}$$

In other words:

• $x^{\ast }$ gives higher expected value to $i$ than any other strategy when $j$ plays $y^{\ast }$.
• $y^{\ast }$ gives higher expected value to $j$ than any other strategy when $i$ plays $x^{\ast }$.

Link to original