02 Solution concepts: examples

Dominant strategy solution

$\mathrm{\forall }i$, $best(s_i)$ unique, independent of $s_{-i}$: \(u(s_{i}, s’{-i}) \geq u(s’{i}, s’{-i}) \forall s’\). Eg: Prisoner’s dilemma; not: Battle of sexes. So, players individually select strategies. May not lead to optimal payoff for any \(p{i}\).

Prisoner’s dilemma

Cost matrix $C=\left[\begin{array}{ccc}(4,4)& (1,5)\text{(}5,1)& (2,2)\end{array}\right]$. s = (2, 2) best for both, but unstable: If $p_1$ sets $s_1=2$, $p_2$ tempted to set $s_2=1$. $s=(1,1)$ stable. Optimal selfish strategy of $p_1$ independent of $p_2$’s actions. Can be extended to multi-player game.

Tragedy of commons

n players; 1 common bandwidth. Strategy about demanding a portion. So, $\mathrm{\infty }$ strategies for each: $s_i\in [0,1]$. If $\sum s_i>1$, payoff for all 0; As $\sum s_i$ increases, utility decreases for all; so utility $u_i(s_i)=s_i(1-\sum _{j\ne i}{s}_j)$. So, maximizing, best strategy: $s_i=(1-\sum _{j\ne i}{s}_j)/2$. Unique stable soln: $s_i=(1+n{)}^{-1}\mathrm{\forall }i$. $\sum u_i=\frac{n}{(1+n{)}^2}\approx n^{-1}$; so tragedy. A cartel would be better!

2nd price auction

Aka Vickery. 1 shot Auction of an item: $p_i$’s value for item is $v_i$; bids $s_i$; if $p_i$ looses, $u_i$ = 0; wins if $s_i=ma{x}_j{s}_j$. If $p_i$ wins, $u_i=v_i-s_j$, where j’s bid is next highest. Dominant strategy: $s_i=v_i$! Item auctioned to $p_i$ who values it most: ‘socially optimal outcome’.

Revelation principle

All $p_i$ can give Game Designer (GD) \ valuation function, let GD play game. Maybe need exponential communication for value function. Also, security needed.

Iterated elimination of str dominated strategies

Take\ game matrix. For each player: Amongst the strategies left, eliminate all dominated strategies.

Sometimes left with many incomparable strategies.

Elimination for weakly dominated strategies could lead to elimination of Nash equilibrium strategies.

Nash equilibrium

Defn: D or $\left\{D_i\right\}$ where even if all $p_i$ know all $D_i$, no treachery profitable. Maybe D not unique. So each $p_i$ can decide $D_i$ if he knows $D_{-i}$.

Pure strategy

s is Nash equilib if \(\forall i, s’: u_{i}(s_{i}, s_{-i}) \geq u_{i}(s’{i}, s{-i}) \). Eg: Battle of sexes. Includes dominant strategy solns.

(Anti) Coordination games

Battle of the sexes: $p_1,p_2$ gain when $s_1=s_2$. Players select strategies together. $C=\left[\begin{array}{ccc}(4,5)& (1,1)\text{(}2,2)& (5,4)\end{array}\right]$. Multiple equilibria; Eg: $Pr(s=(1,1))=1$.

Randomized (mixed) strategies

Not Pure strategy s, but distr D. Risk neutral $p_i$ maximize $u_i(D)=E_{s\sim D}[u_i(s)]$, with $P{r}_{s\sim D}(s)=\prod _{i}P{r}_{s_i\sim D_i}(s_i)$.

D or $\left\{D_i\right\}$ is mixed strategy Nash equilib if \(\forall i, D’: u_{i}(D) \geq u_{i}(D’{i}, D{-i})\). (Check) Eg: Matching pennies. Generalizes pure strategy equilib.

Matching pennies $C=\left[\begin{array}{ccc}(1,-1)& (-1,1)\text{(}-1,1)& (1,-1)\end{array}\right]$. A 0 sum game; so $p_i$ selects strategy independently. No stable s; so, $p_1$ randomizes $s_1$ to thwart 2.

Existance of Equilibria

(Nash) Any game with $|P|,|S_i|$ finite, $\mathrm{\exists }$ mixed strategy Nash equilib. \why

Some games don’t have Nash equilibrium.

Properties

If $D_i$ part of Nash equilibrium,\ every $t\in D_i$ is a best response to $D_{-i}$: $E_{D_{-i}}[t,D_i]$ is maximum: else there could’ve been 0 wt on t.

Time Complexity

Finding Nash equilibria is PPAD complete.

Games representable by digraphs with indegree, outdegree $\le 1$; problem is to find source or sink other than a ‘standard source’. Like Lemke - Howson polytope.

\tbc

eps Nash equilib

A special case: \(\forall i, D’: u_{i}(D) \geq u_{i}(D’{i}, D{-i}) - \eps\)

Correlated equilibrium D

(Aumann). Coordinator has distr D, samples s from D, tells each $p_i$ its $s_i$. $p_i$ not told $s_j$, but knows it is correlated to $s_i$; so knows all $Pr(s_{-i}|s_i)$. D known to every $p_i$. D is correlated equilib if it is not in any $p_i$’s interest to deviate from s, assuming other $p_i$ follow instructions: \ \(E_{s_{-i} \distr D|s_{i}} [u_{i}(s_{i}, s_{-i})] \geq E_{s_{-i}\distr D|s_{i}} [u_{i}(s’{i}, s{-i})] \).

Mixed strategy Nash equilibrium is the special case where $D_i$ are independently randomized (with diff coins).

Not well motivated in some games.

Coordinator picks correlated equilibrium by optimizing some fn (Eg: total payoff or avg payoff).

Regret defn

$f_i:S_i\to S_i$, regret $r_i(s,f)=u_i(f_i(s_i),s_{-i})-u_i(s)$:\ $E_{s\sim D}[r_i(s,f_i)]\ge 0$.

eps correlated equilibrium

$E_{s\sim D}[r_i(s,f_i)]\le ϵ$.

Traffic light/ Chicken $C=\left[\begin{array}{ccc}(-100,-100)& (1,0)\text{(}0,1)& (0,0)\end{array}\right]$. s = (1, 2) and (2, 1) stable; so coordinator picks one randomly. This correlation increases payoff as the low expected utility mixed strategy $D_i=({101}^{-1},1-{101}^{-1})$ is avoided.

Reduction to LP

Unknowns: concatenation of vectors $\left\{D_i\right\}$. If n players, m strategies each, mn unknowns. Make inequalities: $U_i(D_i,D_{-i})\ge U_i(D_i^{\prime },D_{-i})$; \(\norm{D_{i}}{1} = 1\); \(D{i} \geq 0\).

\tbc

Time Complexity

Correlated equilibria form a convex set; so if game specified explicitly, can find one in polynomial time if matrix U given. But finding optimal correlated equilibrium is hard. \tbc