Week 1-Part 2: Games

Definition (Key Ingredients of Games)

• Players — The decision makers. Examples include people, governments (trade agreements), companies (company strategy), employees of a company.
• Actions — What can the players do? Examples include bidding in an auction, deciding to end a strike, deciding to sell a stock, deciding how to vote, etc.
• Payoffs — The motivations of players. Do they care about profit? Do they care about another player being better off?

Definition (Representation of Games)

Games can be represented in two standard ways:

• Normal Form

  Also called Matrix Form or Strategic Form. In this form, you list what payoffs players get as a form of their actions. It is interpreted as if players moved simultaneously

• Extensive Form

  This form includes timing of moves (i.e. players move sequentially and this is represented as a tree). For example, in chess, the white player moves, then the black player can see the move and react accordingly.

  Another example is poker, where players can bet sequentially. What can a given player see when it is their turn to bet?

Definition (Normal Form Game)

In a finite, $n$-person normal form game $\langle N, A, u\rangle$, we have:

• Players: $N = \{1,\dots, n\}$ is a finite set of $n$, indexed by $i$

• The action set for player $i$ (Denoted $A_i$): $\underbrace{a=(a_1, \dots, a_n)}_{\text{Action Set}} \in \underbrace{A = A_1 \times A_2 \times \dots \times A_n}_{\text{Action Profile}}$

  For example, are players deciding to co-operate (or not)?

• The utility function (or payoff function) for player $i$ is defined as: $u_i: A \mapsto \mathbb{R}$, where $u = (u_1, \dots, u_n)$ is a profile of utility functions

  This tells a player how to evaluate the outcomes of a game (it is important to make sure you have the correct representation of the utility function)

If we want to represent a two-player game in the Standard Matrix representation, we first understand that the “row” player is player 1, and the “column” player is player 2. Each row corresponds to actions $a_i \in A_1$, columns correspond to actions $a_2 \in A_2$. Each cell represents the payoffs of each player in the form:

$(\text{Player 1's Payoff}, ~~\text{Player 2's Payoff})$

Example (TCP Backoff)

The following is the TCP backoff game in the previous note written as a matrix:

$\begin{array}{c|c|c|} & C & D \\ \hline C & -1,-1 & -4,0 \\ \hline D & 0,-4 & -3,-3 \\ \hline\end{array}$

Example (Large Collective Action)

Consider a population (players $N= \{1,\dots, 10~000~000\}$) that wants to revolt against its government. Each individual can choose to either revolt or not revolt. i.e. the Action Set for player $i$ is:

$A_i = \{\text{Revolt}, \text{Not Revolt}\}$

The Utility Function for player $i$ is:

$u_i (a) = \begin{cases} 1, \text { if } \#\left\{j: a_{j}=\text { Revolt }\right\} \geq 2,000,000\\ \\ 0, \text { if } \#\left\{j: a_{j}=R \text {evolt}\right\}<2,000,000 \text { and } a_{i}=\text{Not}\\ \\ -1, \text { if } \#\left\{j: a_{j}=R \text {evolt}\right\}<2,000,000 \text { and } a_i = \text{Not} \end{cases}$

e.g. if you end up with at least 2 million people revolting, player $i$ gets 1. Note that this is true even without player $i$ being in the 2 million. So some players can benefit even if they do not participate.

If player $i$ participates in the revolt and it fails, they get a payoff of $-1$ (government punishes them etc.)

If player $i$ does not participate and if the revolt is not successful, their payoff is $0$.

Built with GatsbyJS