in which I cover the Game Theory content in [[00_Plan]] We can introduce randomness so that we choose an action over some distribution A player's expected payoff is the sum of 'probability of event x ' {TIMES} 'payoff of event x'

Zero Sum Games¶

If one player's payoff is x, the other's is -x We denote the payoff matrix as $U$, where $U_{a,b}$ is player 1's payoff if player 1 chooses action $a$, and player $2$ chooses action $b$

Pure NE¶

A Nash equilibrium means that no individual player can benefit from changing their strategy if the other players' strategies are fixed.

To solve NE, assume all moves by others are fixed and choose the best action a. This tells us that if our opponents choose this combination of moves, then we will make action a. Repeat for all opponents, and if we end up with a combination where everyone chooses that same action, then we have NE since we're in a gridlock.

Mixed NE and LP¶

Players choose a strategy according to a distribution. Note that the players can choose any distribution they want! they're not selecting from any subset. Note that every player is aware of the other players' distributions! Note that the payoff matrix $U$ remains the same in mixed and pure problems.

for player 1 who chooses a distribution $x$, where $x = (x_1, x_2, ...)$ Their payoff is $y^TUx$

Since they know player 2 will choose a distribution to make the payoff the lower bound, player 1 will choose the distribution $x$ which maximizes the lower bound. Thus, player 1's chosen distribution $x$ = $\text{arg } \text{max}_{\bar{x}} \text{min}_{\bar{y}} \bar{y}^T U \bar{x}$

This is a tricky formulation because we have two variables. Instead we can represent the payoff matrix according to the rows of ${u_1, u_2, ... u_n} = U$, where each row represents a different action taken by player 2. Then $U\bar{x} = [u_1\bar{x}, u_2\bar{x}, ...]^T$ Then $argmin_{\bar{y}} \bar{y} [u_1\bar{x}, u_2\bar{x}, ...]^T$ would be the $\bar{y}$ which deterministically selects the minimum $u_i \bar{x}$. Thus, we ultimately have that $\text{min} \bar{y}^T U \bar{x} = \text{min}_i u_i \bar{x}$ \ Consequently, player 1 will choose the action $x$ which maximizes this expression $$ x = \text{arg max}{\bar{x}} \text{min}{i} u_i \bar{x} $$ And so we've removed the $y$ variable! Now we can express this as a linear program in either player's perspective. No player actually moves first, so we could denote player 1 or 2's payoff, depending on what's more convenient for our problem. We can solve this LP to find the nash equilibrium (how?)

Let $v_1$ be the payoff for player one. Then we can add a constraint for every strategy that every payoff must be $\leq$ the payoff of that strategy - this is a cool way to infuse the min $u_i x$ requirement as a constraint! - still don't understand the minimax theorem that well though. not sure how it relates to the dual ![[Pasted image 20221111232314.png]]

![[Pasted image 20221111232824.png]] Minimax theorem

Properties of NE¶

a pure NE has actions selected deterministically, while a mixed NE has actions chosen over a distribution.

Every finite normal game has a NE There exist normal games that are infinite without NE there exist finite normal games without pure NE (everything we study with a payoff matrix is a normal game)

Optima of linear programs are NE $\text{max}_x \text{min}_y f(x,y) \leq \text{min}_y \text{max}_x$ in contrast to our minimax theorem, which states that both directions hold.

think about constant sum games (could be a quiz q). Is there any difference?

Normal Form Games¶

N players
each player has a set of actions $A_i$
A = A_1 X ... A_n is the set of all action profiles
$s_i$ is the strategy for player i
strategies are chosen independently
players act at once
all players have perfect information about other player's payoff matrix

Tips¶

Recitation problem 4 quiz to show a problem is at nash equilibrium, we must show that if B's decision is fixed at 1/3, then A's decision is also fixed at 1/3 because there isn't any action which can improve their outcome. Since the problem is symmetric, we only need to show it for A. Otherwise, we would need to show it for B as well. To show that no deviation can improve outcome, we can define the change with reference to a delta. This was the challenge I had since I had only ever thought about discrete games where each action is discrete.

I can also solve it by taking the derivative and showing that 1/3 is the optimal value. ![[Pasted image 20221114175801.png|500]] ![[Pasted image 20221114212922.png]] It was obvious that any combination that leads to a sum of 1 is a nash equilibrium. BUT there's also a nash equilibrium if their sum exceeds 1! in the case that both pairs use greater than 1, then no person can reduce their bandwidth to get any payoff