03 Games: classes

2 player games

Aka bimatrix game. Row and column players: $p_r,p_c$; their Prob distr over $S_r$ and $S_c$ as vectors :$D_r,D_c$. Utility matrix wrt $p_r$ and $p_c$: R, C.

2 - Player 0 sum games

Utility matrix $A_{i,j}=u_r(..)$. (Nash) Eg: Matching pennies.

Value paid by $p_c$ to $p_r$: $v_r=D_r^{\ast }A{D}_c$.

Knowing $D_r$, $p_c$ always selects \(min(D_{r}^{}A)\) or finds \(v_{c} = \min_{k_{1}} \max_{D_{r}} E_{k_{r} \distr D_{r}}[u_{1}(k_{1}, k_{2})] = \min_{k_{1}} \max_{D_{r}} u_{1}(k_{1},D_{r})\). So, best strategy for $p_r$ is to maximize (Maxmin) \(min(D_{r}^{}A)\).

Solution by linear program

$v_r=maxv;D_r>0;\sum _i{D}_{r,i}=1;(D_r^{\ast }A{)}_j\ge v\mathrm{\forall }j$.

Dual of this LP finds $v_c=-v_r$ and $D_c$: aka Minmax / minimax theorem (Neumann).

Reduction from constant (k) sum 2 player games

Use a equivalent utility matrix $A_{i,j}=u_r(..)$. So, any constant sum game has well defined value: $(v_r,k-v_r)$.

Symmetric two player games

R, C are same. $D_c$ is the best response to itself. $D_c=D_r=D$.

Finding Nash Equilibrium

(Lemke - Howson). Consider inequalities $Ax\le 1$, $x\ge 0$; visualize 2d case like an LP: intersecting halfspaces in a plane with axes $\left\{x_i\right\}$. $(\genfrac{}{}{0ex}{}{2n}{n})$ verteces in n-d polytope.

Solution pt must lie in some vertex where payoff is maximum; at solution pt, $\mathrm{\forall }i$: $A_{i}x=1$ and $i\in D$ by prop of Nash equilib, or $x_i=0$ and $i\notin D$. To get the final strategy, take x, and scale it so that $\sum x_i=1$. Move from vertex to vertex by relaxing constraints and moving along edges.

Almost always runs in poly time. (Smoothed complexity.)

Reduction from general 2 player games

R and C are $m\times n$. Make symmetric game $\left[\begin{array}{ccc}0& R{\text{C}}^T& 0\end{array}\right]$; Find solution distribution $\left[\begin{array}{c}x\text{y}\end{array}\right]$: now, x and y best responses to each other, so solution to original game.

Games with n turns

Casting as a simultaneous move game

Each $p_i$ picks full strategy from $S_i^n$. But, $|S_i^n|=|S_i{|}^n$; so games with turns are a compact representation. Extensive form: Game tree with payoffs at leaves.

Subgame Perfect Nash Equilibria

Nash Equilib with notion of order of moves: Strategy should be Nash even if any prefix of the game is already played.

Ultimatum game

$p_1$, $p_2$ split money m; 1 turn each: $p_1$ offers n; $p_2$ accepts or reject. $p_2$’s interest to accept whatever offered. Cast to a simultaneous move game. Many Nash equilibria: If $p_2$ rejects if $n<o$, $p_1$ must offer o. 1 subgame perfect nash equilib.

Games with partial info about utilities

Work with beliefs about others’ properties and preferences.

Bayesian Games

Eg: Card game: \ Only distribution of others’ cards known.

Bayesian first price auction

$\left\{p_i\right\}$ have values $\left\{v_i\right\}$ for item. If all info available; best strategy for $p_i$: choose $s_i$ = $v_j$ next lower to $v_i$. If only distribution of $v_k$ for other players known, $p_i$ bids second E[$v_j$ next lowest to $v_i|v_i$ is max]. \why

Cooperative games

Groups (G ..) can change strategies jointly.

Strong Nash Equilibrium

In s, $G\subset P$ has \textbf{joint deviation} if \(\exists s’{G}| u{i}(s) \leq u_{i}(s’{G}, s{-A})\forall p_{i} \in G\), and for some \(p_{j} \in G, u_{i}(s) < u_{i}(s’{G}, s{-A})\).

s is strong Nash if no $G\subset P$ has joint deviation. Similarly, mixed strategy Nash equilibria. Few games have this. Eg: Stable marriage problem.

Stable Marriage problem

\tbc

Transferable utility

\tbc

Market equilibria

Pricing and Allocation game with linear utility

Aka Fisher’s linear case. Bipartite graph G = (I, B) of goods and buyers: edges indicate interest of $b\in B$ in $i\in I$. Quantity of i scaled to 1; price vector for I: p; money vector for B: m. Utility of i for b: $u_{b,i}$.

Want to find optimal p (pricing) and partition items among B: allocation x. Equilibrium properties: all money, goods exhausted.

Best bang per buck for b: $a_b=ma{x}_i\frac{u_{b,i}}{p_i}$: a linear function: so ’linear case'.

Primal dual approach: Start with arbit p = 1; find x; find $\left\{b\right\}$ with excess money; adjust price; repeat.

Finding x by reduction to network flow problem: add source s and sink t; connect s to all I and t to all B; set capacities of edges in original graph to be $\mathrm{\infty }$ and on new edges to match a(i) and m(b); thence find c.

Find best allocation

(Arrow Debreu) Agents come in with goods portfolio, utilities for various goods, leave with goods: money only inbetween. Generalizes Fisher’s linear case: .

Auction based approx algorithm solves it: Market clears approximately.

Repeated games with partial info about utilities

$p_1$ in uncertain environment ($p_{-1}$); utilities of $p_{-1}$ not known. Eg: Choosing a route to go to school.

Model

Same game repeated T times; At time t: $p_1$ uses online algorithm H to pick distr $D_H^{(t)}$ over $S_1$. $p_1$ picks action $k_1^{(t)}$ from $D_H^{(t)}$. Loss/ cost function for $p_1$: $c_1:{\times }_i{S}_i\to [0,1]$. $c_1^{(t)}(k_1^{(t)}):=c_1(k_1^{(t)},D_{-1}^{(t)})$, $c_1(D):=E_{x\sim D}[c_1(x)]$.

Model with full info about costs

H gets cost vector $c_1^{(t)}\in [0,1{]}^{|S_1|}$, pays cost \ $c_1(D_H^{(t)},D_{-1}^{(t)})=E_{k_1^{(t)}\sim D_H^{(t)}}[c_1(k_1^{(t)},D_{-1}^{(t)})]=E_{k_1^{(t)}\sim D_H^{(t)}}[c_1^{(t)}(k_1^{(t)})]$.

Total loss for H: $L_H^{(T)}=\sum c_1(D_H^{(t)},D_{-1}^{(t)})$.

Model with partial info about costs

Aka Multi Armed Bandit (MAB) model.\ $p_1$ (or H) pays cost for $k_1^{(t)}$: $c_1(k_1^{(t)},D_{-1}^{(t)})=c_1^{(t)}(k_1^{(t)})$.

Total loss for H: $L_H^{(T)}=\sum c_1(k_1^{(t)},D_{-1}^{(t)})$.

Goal

Minimize $\frac{L_{?}^{(T)}}{T}$. Maybe other $p_i$ do the same. $D_{-1}^{(t)}$ and $c_1^{(t)}$ can vary arbitrarily over time; so, model is adversarial.

Best response algorithm For every i: Start with s; suppose $s_{-i}$ fixed, do hill climbing by varying $s_i$.

Regret analysis

H incurs loss $L_H^{(T)}$; $p_1$ sees simple policy $\pi$ would have had much lower loss. Comparison class of orithms G. $\pi$ best algorithm in G: $L_{\pi }^{(T)}=mi{n}_{g\in G}{L}_g^{(T)}$. Regret $R_G=L_H^{(T)}-L_{\pi }^{(T)}=ma{x}_{g\in G}(L_H^{(T)}-L_g^{(T)})$.

Goal

Minimize $R_G$.

Regret wrt all policies: Lower bound

$G_{all}=\{g:T\to S_1\}$: $\mathrm{\exists }$ sequence of loss vectors $c_1^{(t)}$: $R_{G_{all}}\ge T(1-|S_1{|}^{-1})$:

For $k^{\prime }=argmi{n}_{k_1^{(t)}}P{r}_{D_H^{(t)}}(k_1^{(t)})$, $c_1^{(t)}(k^{\prime })=0$, for others, \ $c_1^{(t)}(k_1^{(t)})=1$; $\underset{k_1^{(t)}}{min}P{r}_{D_H^{(t)}}(k_1^{(t)})\le |S_1{|}^{-1}$.

So, must restrict G.

External regret

Aka Combining Expert Advice. $G=\{i^T:i\in S_1\}$, policies where all $k_1^{(t)}$ are the same; $\pi$ is best single action. $L_{\pi }^{(T)}=\sum c_1(\pi ,D_{-1}^{(t)})$.

If H has low external regret bound: H matches performance of offline algorithm. \why H comparable to optimal prediction rule from some large hyp class H. \why

Deterministic Greedy (DG) algorithm

$S_1^{(t-1)}=\{i:argmi{n}_{i\in S_1}{L}_i^{(t-1)}\}$,\ $k_1^{(t)}=\underset{i\in S_1^{(t-1)}}{min}i$. $L_{DG}^{(T)}\le |S_1|mi{n}_i(L_i^{(T)})+(|S_1|-1)$: Suppose $c_1^{(t)}\in {\{0,1\}}^{|S_1|}$. For every increase in $\underset{i}{min}{L}_i^{(t)}$, max loss $|S_1|$: For $L_{DG}^{(t)}=L_{DG}^{(t-1)}+1$ but $\underset{i}{min}{L}_i^{(t)}=\underset{i}{min}{L}_i^{(t-1)}$: $S_1^{(t)}\subseteq S_1^{(t-1)}$; so count num of times $S_1^{(t)}$ can shrink by 1.

Deterministic algorithm Lower bound For any deterministic online algorithm H’, $\mathrm{\exists }$ loss seq where $L_{H^{\prime }}^{(T)}=T,mi{n}_{i\in S_1}(L_i^{(t)})\le \lfloor T/|S_1|\rfloor$: $c_1^{(t)}(k_1^{(t)})=1$, for other i, $c_1^{(t)}(i)=0$; so $L_{H^{\prime }}^{(T)}=T$; some action used by H’ $\le \lfloor T/|S_1|\rfloor$ times; so $mi{n}_{i\in S_1}(L_i^{(t)})\le \lfloor T/|S_1|\rfloor$.

So find rand algorithm.

Rand Weighted majority algorithm (RWM)

Suppose $c_1^{(t)}\in {\{0,1\}}^{|S_1|}$. Treat $S_1$ as a bunch of experts: Want to put as much wt as possible on best expert. Let $|S_1|=N$. Init weights $w_i^{(1)}=1$, total wt $W^{(1)}=N$, $P{r}_{D_H^{(1)}}(i)=N^{-1}$.

If $c_1^{(t-1)}(i)=1$, $w_i^{(t)}=w_i^{(t)}(1-\eta )$, $P{r}_{D_1^{(t)}}(i)=\frac{w_i^{(t)}}{W^{(t)}}$. \why Like analysis of mistake bound of panel of k experts in colt ref.

For $\eta <2^{-1}$, $L_H^{(T)}\le (1+\eta )\underset{i\in S_1}{min}{L}_i^{(t)}+\frac{\ln N}{\eta }$. Any time H sees significant expected loss, big drop in W. $W^{(T+1)}\ge ma{x}_i{w}_i^{(T+1)}=(1-\eta {)}^{\underset{i}{min}{L}_i^{(T)}}$. \tbc

For $\eta =min\{\sqrt{\ln N/T},2^{-1}\}$: $L_H^{(T)}\le \underset{i}{min}{L}_i^{(T)}+2\sqrt{T\ln N}$. If T unknown, use ‘guess and double’ with const loss in regret. \why

Polynomial weights algorithm

Extension of RWM to $c_1^{(t)}\in [0,1{]}^{|S_1|}$. Wt update is $w_i^{(t)}=w_i^{(t)}(1-\eta c^{(t-1)}(i))$. $L_H^{(T)}\le \underset{i}{min}{L}_i^{(T)}+2\sqrt{T\ln N}$. \why

Rand algorithm Lower bounds

If $T<{\log }_{2}N$: For any online algorithm H, $\mathrm{\exists }$ stochastic generation of losses: $E[L_H^{(T)}]=T/2$, but $\underset{i}{min}{L}_i^{(t)}=0$: at t=1 let N/2 actions get loss 1; at time t: half the actions which had a loss 0 at time t-1 get loss 1; so, probability mass on actions with 0 = $2^{-1}$.

If N=2, $\mathrm{\exists }$ stochastic generation of losses: $E[L_H^{(T)}-\underset{i}{min}{L}_i^{(T)}]=\mathrm{\Omega }(\sqrt{T})$. \why

Convergence to equilibrium: 2 player constant sum repeated game

All $p_i$ use algorithm H with external regret R; Value of game: $(v_i)$. Avg loss: $\frac{L_H^{(T)}}{T}\le v_i$. \why If $R_G=O(\sqrt{T})$, convergence to $v_i$.

Low external regret algorithm in partial cost info model

Exploration vs exploitation tradeoff in algorithms.

algorithm MAB: Divide time T into K blocks; in each time block $\tau +1$: explore and get cost vector: execute action i at random time to get vector of RV’s: ${\hat{c}}^{(\tau )}$, also exploit: use distr $D^{(\tau )}$ as strategy; pass ${\hat{c}}^{(\tau )}$ to full info external regret algorithm F with ext regret $R^{(K)}$ over K time steps; get distr $D^{(\tau +1)}$ from F.

Max Loss during exploration steps: NK. RV for total loss of F over K time blocks: \(\hat{L}{F}^{(T)} = \frac{T}{K}\sum{\tau}p^{\tau}c^{\tau} \leq \frac{T}{K}(min_{i} \hat{L}{i}^{(K)} + R^{(K)}\). Taking expectation, \(L{MAB}^{(T)} = E[\hat{L}{MAB}^{(T)}]= E[\hat{L}{F}^{(T)} + NK] \leq \frac{T}{K}(E[min_{i} \hat{L}{i}^{(K)}] + R^{(K)}) + NK \leq \frac{T}{K}(min{i} E[\hat{L}{i}^{(K)}] + R^{(K)}) + NK \leq min{i}L_{i}^{(T)} + \frac{T}{K}R^{(K)} + NK\).

Using the $O(\sqrt{K\log N})$ algorithm, with $K=(\frac{T}{K}{R}_K)$, we get $L_{MAB}^{(T)}\le mi{n}_i{L}_i^{(T)}+O(T^{2/3}{N}^{1/3}\log N)$.

Swap regret

Comparison algorithm (H,g) is H with some swap fn $g:S_1\to S_1$.

Internal regret

A special case: Swap every occurance of action $b_1$ with action $b_2$. Modification fn: $switc{h}_i(k_i,b_1,b_2)=k_i$ except $switc{h}_i(b_1,b_1,b_2)=b_1$.

Low Internal regret algorithm using external regret minimization algorithms

Let $N=|S_i|$; $(A_1,..,A_N)$ copies of algorithm with external regret bound R. Master algorithm H gets from $A_i$ distr $q_i^{(t)}$ over $S_i$; makes matrix $Q^{(t)}$ with $q_i^{(t)}$ as rows; finds stationary distr vector $p^{(t)}=p^{(t)}{Q}^{(t)}$: Picking $k_i\in S_i$ same as picking $A_j$ first, then picking $k_i\in S_i$; gets loss vector $c^{(t)}$; gives $A_i$ loss vector $p_i^{(t)}{c}^{(t)}$.

$\mathrm{\forall }j:L_{A_i}=\sum _t{p}_i^{(t)}⟨c^{(t)},q_i^{(t)}⟩\le \sum _t{p}_i^{(t)}{c}_j^{(t)}+R$. Also, Sum of percieved losses = actual loss. So, for any swap fn g, $L_H^T\le \sum _i\sum _t{p}_i^{(t)}{c}_{g(i)}^{(t)}+NR=L_{F,g}^{(T)}+NR$.

Thence, using polynomial weights algorithm, swap regret bound\ $O(\sqrt{|S_1|T\log |S_1|})$.

Convergence to Correlated equilibrium

Every $p_i$ uses strategy with swap regret $\le R$: then empirical distr Q over ${\times }_i{S}_i$ is an $\frac{R}{T}$ correlated equilibrium. $R=L_H^{(T)}-L_{H,g}^{(T)}=\sum _t{E}_{s^{(t)}\sim D^{(t)}}[r_i(s,g)]=T{E}_{s\sim Q}[r_i(s,g)]$.

Convergence if all players have sublinear swap regret.

Frequency of dominated strategies

$p_1$ uses algorithm with swap regret R over time T; w: avg over T of prob weight on $ϵ$ dominated strategies; so $ϵwT\le R$; so $w\le \frac{R}{Tϵ}$.

If algorithm minimizes external regret using polynomial weights algorithm, freq of doing dominated actions tends to 0.