Introduction to Game Theory

Game Theory

Game theory is the study of mathematical models of strategic interactions among multiple rational agents. It involves modelling cooperation and competition between intelligent and rational decision-makers.

Mechanism Design

Mechanism design involves the study of mechanisms by which a particular desirable outcome or result can be achieved.

Preferences & Utilities

Outcomes & Lotteries

Let $O=\{o_1,...,o_K\}$$\large O =\{o_1, ..., o_K\}$ be a set of $K$$\large K$ mutually exclusive outcomes. A lottery $A$$\large A$ describes a probability distribution over outcomes $O$$\large O$. We write $A=\sum _k{p}_k{o}_k$$\large A = \sum\limits_k p_k o_k$ to indicate that $o_k\in O$$\large o_k \in O$ happens with probability $p_k$$\large p_k$.

For e.g. $A=0.75o_1+0.25o_2$$\large A = 0.75 o_1 + 0.25 o_2$ means $P(o_1)=0.75$$\large P(o_1) = 0.75$ and $P(o_1)=0.25$$\large P(o_1) = 0.25$.

A compound lottery is a lottery defined based on other lotters.

For e.g., suppose $O=\{o_1,o_2,o_3\}$$\large O = \{o_1, o_2, o_3\}$, and lotteries $A$$\large A$ and $B$$\large B$ are defined as follows:

• $A=0.2o_1+0.8o_2$$\large A = 0.2 o_1 + 0.8 o_2$
• $B=0.4o_1+0.6o_2$$\large B = 0.4 o_1 + 0.6 o_2$

Then, lottery $C$$\large C$, defined by $C=0.5A+0.5B$$\large C = 0.5 A + 0.5 B$, is a compound lottery.

Ordinal Preferences

A preference relation over lotteries can be defined as follows:

• $A\succ B$$\large A \succ B$ means an agent strictly prefers $A$$\large A$ to $B$$\large B$
• $A⪰B$$\large A \succeq B$ means an agent weakly prefers $A$$\large A$ to $B$$\large B$
• $A\sim B$$\large A \sim B$ means an agent is indifferent between $A$$\large A$ and $B$$\large B$ (i.e. $A⪰B$$\large A \succeq B$ and $B⪰A$$\large B \succeq A$)

Completeness

$\mathrm{\forall }$$\large \forall$ lotteries $A,B$$\large A, B$, either $A\succ B$$\large A \succ B$ or $B\succ A$$\large B \succ A$ or $A\sim B$$\large A \sim B$

Transitivity

$\mathrm{\forall }$$\large \forall$ lotteries $A,B,C$$\large A, B, C$, $A⪰B$$\large A \succeq B$ and $B⪰C⟹A⪰C$$\large B \succeq C \implies \large A \succeq C$

Independence of Irrelevant Alternative

$\mathrm{\forall }$$\large \forall$ lotteries $A,B,C$$\large A, B, C$, $\mathrm{\forall }p\in [0,1]$$\large \forall p \in [0, 1]$, $A⪰B⟺pA+(1-p)C⪰pB+(1-p)C$$\large A \succeq B \iff pA + (1 - p) C \succeq pB + (1 - p) C$

Continuity

$\mathrm{\forall }$$\large \forall$ lotteries $A,B,C$$\large A, B, C$, $A⪰B⪰C⟹\mathrm{\exists }p\in [0,1]$$\large A \succeq B \succeq C \implies \exist p \in [0, 1]$ such that $B\sim pA+(1-p)C$$\large B \sim pA + (1 - p)C$

Utilities

For any von Neumann-Morgenstern-rational agent, there exists a function $u$$\large u$ (known as the von Neumann-Morgenstern utility) that maps each lottery $A$$\large A$ to a real number $u(A)$$\large u(A)$, such that:

• $u(A)=u(\sum _k{p}_k{o}_k)=\sum _k{p}_{k}u(o_k)$$\large u(A) = u(\sum\limits_k p_k o_k) = \sum\limits_k p_k u(o_k)$
• $u(A)\ge u(B)⟺A\succ B$$\large u(A) \ge u(B) \iff A \succ B$