Game Theory - HackMD

Game Theory === https://math.meta.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference # Week 1: Introduction and Overview :::success **Best Responce** Definition: $a_{-i} = \{a_{1},a_{2},a_{3},...a_{-i}, a_{i}, ...a_{n-1}, a_{n}\}$ $a = (a_{-i}, a_i)$ $a_i^* \in BR(a_{-i}),\iff \forall a_{i} \in A_{i}, u_{i}(a_i^* , a_{-i}) \geq u_{i}(a_i , a_{-i})$ > A is the set of all actions, a is entire action vactor, we call it the action profile. > $a_i$ is your original action, $BR()$ is the set of Best Responce. > ui is utility. ::: :::success **Nash Equilibrium** Definition: a = ⟨a1,...,an⟩ is a (“pure strategy”) $Nash \ equilibrium \iff \forall i, ai ∈ BR(a_{−i}).$ ::: :::success **Strictly Donimate** Definition: $s_i$ strictly donimates $s_i^{'}$ , if $\forall s_{-i} \in S_{-i}, u_i(s_i, s_{-i}) \gt u_i(s_i^{'},s_{-i})$ ::: :::success **Very Weakly Donimate** Definition: $s_i$ very weakly donimates $s_i^{'}$ , if $\forall s_{-i} \in S_{-i}, u_i(s_i, s_{-i}) \ge u_i(s_i^{'},s_{-i})$ ::: :::success **Pareto Optimality** Definition: An outcome $o^*$ is Pareto Optimal if there is no other outcome that Pareto Donimates it. ::: # Week 2: Mixed Strategies and Nash Equilibrium :::success **Best Responce** Definition: $s_i^* \in BR(s_{-i}),\iff \forall s_{i} \in S_{i}, u_{i}(s_i^* , s_{-i}) \geq u_{i}(s_i , s_{-i})$ ::: :::success **Nash Equilibrium** Definition(for mix stratigies): s = ⟨s1,...,sn⟩ is a (“mix strategy”) $Nash \ equilibrium \iff \forall i, s_i ∈ BR(s_{−i}).$ ::: :::success support is the set of pure strategies that receive positive probability under the mix strategy of the players. ::: 如何最佳？讓對方不管選什麼，得分期望都一樣。 # Week 3: Alternate Solution Concepts :::success **Strictly Dominated Strategies** Definition: A strategy $a_i \in A_i$ is strictly donimated by $a_i^{'} \in A_i$ , if $\forall a_{-i} \in A_{-i}, u_i(a_i, a_{-i}) \lt u_i(a_i^{'},a_{-i})$ ::: :::success **Weakly Donimated** Definition: $a_i$ weakly donimated $a_i^{'}$ , if $u_i(a_i, a_{-i}) \le u_i(a_i^{'},a_{-i}) \forall a_{-i} \in A_{-i}, and \\ \exists \ \ u_i(a_i, a_{-i}) \lt u_i(a_i^{'},a_{-i}) a_{-i} \in A_{-i}$ ::: Weakly donimated can remove them iteratively too, but: 1. They can be best replies. 2. Order of removal can matter. 3. At least one equilibrium preserved. :::success **Maxmin** Definition: The $maxmin \ strategy$ for player i is $arg\max_{s_i} \min_{s_{-i}} u_i(s_1,s_2)$, and the $maxmin \ value$ for player i is $\max_{s_i}\min_{s_{−i}} u_i(s_1,s_2)$. ::: Why would i want to play a maxmin strategy? • a conservative agent maximizing worst-case payoff :::success **Minmax** Definition: In a two-player game, the $minmax \ strategy$ for player i against player −i is $arg\min_{s_i}\max_{s_{−i}} u_{−i}(s_i,s_{-i})$, and player −i’s $minmax \ value$ is $\min_{s_i} \max_{s_{-i}} u_{-i}(s_i,s_{-i})$. ::: :::info Theorem (**Minimax theorem** (von Neumann, 1928)) In any finite, two-player, zero-sum game, in any $Nash \ equilibrium$ each player receives a payoff that is equal to both his maxmin value and his minmax value. ::: 1. Each player’s maxmin value is equal to his minmax value. The maxmin value for player 1 is called **the value of the game**. 2. For both players, the set of maxmin strategies coincides with the set of minmax strategies. 3. Any maxmin strategy profile (or, equivalently, minmax strategy profile) is a Nash equilibrium. Furthermore, these are all the Nash equilibria. Consequently, all Nash equilibria have the same payoff vector (namely, those in which player 1 gets the value of the game). -- # Week 4: Extensive-Form Games A (finite) perfect-information game (in extensive form) is defined by the tuple $(N,A,H,Z,χ,ρ,σ,u)$, where: * Players: $N$ is a set of n players * Actions: $A$ is a (single) set of actions * Choice nodes and labels for these nodes: * Choice nodes: $H$ is a set of non-terminal choice nodes. * Action function: $χ : H → 2^{\lvert A\rvert}$ assigns to each choice node a set of possible actions * $ρ : H \to N$ assigns to each non-terminal node $h$ a player $i ∈ N$ who chooses an action at $h$ * Terminal nodes: $Z$ is a set of terminal nodes, disjoint from $H$ * Successor function: $σ : H \times A \to H \bigcup Z$ maps a choice node and an action to a new choice node or terminal node such that $\forall$ $h_1,h_2 \in H$ and $a_1,a_2 \in A$, if $σ(h_1,a_1) = σ(h_2,a_2)$ then $h_1 = h_2$ and $a_1 = a_2$ * Utility function: $u = (u_1,...,u_n)$; $u_i : \Bbb Z \to \Bbb R$ is a utility function for player $i$ on the terminal nodes $\Bbb Z$ :::success **pure strategies** quentities Definition: Let $G = (N,A,H,Z,χ,ρ,σ,u)$ be a perfect-information extensive-form game. Then the pure strategies of player $i$ consist of the cross product $$\prod_{h \in H, \ ρ(h)=i}χ(h)$$ ::: :::success **subgame** of $G$ rooted at $h$ Definition: The subgame of $G$ rooted at $h$ is the restriction of $G$ to the descendents of $H$. ::: :::success **subgames** of $G$ Definition: The set of subgames of $G$ is defined by the subgames of $G$ rooted at each of the nodes in $G$. ::: $s$ is a **subgame perfect equilibrium** of $G \iff \forall$ **subgame** $G^′$ of $G$, the restriction of s to $G^′$ is a Nash equilibrium of $G^′$ * NOTE: * since $G$ is its own subgame, every **SPE** is a **NE**. * this definition rules out “non-credible threats” :::success **Imperfect-information Game (in extensive form)** Definition: An imperfect-information game (in extensive form) is a tuple (N,A,H,Z,χ,ρ,σ,u,I), where (N,A,H,Z,χ,ρ,σ,u) is a perfect-information extensive-form game, and $I = (I_1,...,I_n)$, where $I_i = (I_{i,1},...,I_{i,ki})$ is an $equivalence \ relation$ on (that is, a partition of) ${h \in H : ρ(h) = i}$ with the property that $χ(h) = χ(h^′)$ (該節點有相同決策選項) and $ρ(h) = ρ(h^′)$ (該節點是同一決策人) whenever there exists a $j$ for which $h \in I_{i,j}$ and $h^′ \in I_{i,j}$. ::: # Week 5: Repeated Games :::success **Average reward** Definition: Given an infinite sequence of payoffs $r_1,r_2,...$ for player $i$, the average reward of $i$ is: $$\lim_{k \to \infty} \sum^k_{j=1} {r_j\over k}$$ ::: :::success **Future discounted reward** Definition: Given an infinite sequence of payoffs $r_1,r_2,...$ for player $i$ and discount factor ${\beta}$ with $0 \lt \beta \lt 1$, i^’s future discounted reward is $$\sum^{\infty}_{j=1} {\beta}^j r_j$$ ::: Two equivalent interpretations of the discount factor: 1. the agent cares more about his well-being in the near term than in the long term 2. the agent cares about the future just as much as the present, but with probability 1−${\beta}$ the game will end in any given round :::success **Stochastic game** Definition A stochastic game is a tuple $(Q,N,A,P,R)$, where $Q$ is a finite set of states $N$ is a finite set of n players $A = A_1 \times ···\times A_n$, where $A_i$ is a finite set of actions available to player $i$ $P : Q \times A \times Q \to [0,1]$ is the transition probability function; $P(q,a, \hat q)$ is the probability of transitioning from state $q$ to state $\hat q$ after joint action a $R = \{r_1,...,r_n\}$, where $r_i : Q \times A \to R$ is a real-valued payoff function for player $i$. ::: :::success For every $a \in A$ let $w(a)$ be the number of times the opponent has player action $a$. Can be initialized to non-zero starting values. Assess opponent’s strategy using these counts: $σ(a)$ = ${w(a)} \over {\sum}_{a^{'} \in A} w(a′)$ ::: :::info Theorem About Fictitious Play: **If** the empirical distribution of each player’s strategies **converges** in fictitious play, **then** it converges to a $Nash \ equilibrium$. -- Each of the following are a **sufficient conditions** for the empirical frequencies of play to converge in fictitious play: 1. The game is zero sum; 2. The game is solvable by iterated elimination of strictly dominated strategies; 3. The game is a potential game; 4. The game is $2 \times n$ and has generic payoffs. ::: :::success **Regret** Definition: The regret an agent experiences at time $t$ for not having played $s$ is $R^t(s) = max(α^t(s)−α^t,0)$. ::: :::success **No-regret learning rule** Definition: A learning rule exhibits no regret if for any pure strategy of the agent $s$ it holds that $$Pr([{\lim}_{\infty} R^t(s)] \le 0) = 1$$. ::: At each time step each action is chosen with probability proportional to its regret. That is: $${\sigma}^{t+1}_i (s) = {R^t(s) \over {\sum}_{s^{'} \in S_i} R^t(s^{'})}$$ where ${\sigma}^{t+1}_i (s)$ is the probability that agent $i$ plays pure strategy $s$ at time $t + 1$. Converges to a correlated equilibrium for finite games. ### Equilibria of Infinitely Repeated Games Consider any n-player game $G = (N,A,u)$ and any payoff vector $r = (r_1,r_2,...,r_n)$. Let $$v_i = \min_{s_{−i} \in S{−i}} \max_{s_i \in S_i} u_i(s_{-i},s_i)$$ :::success **Enforceable** definition: A payoff profile r is **enforceable** if $r_i \ge v_i$. ::: :::success **feasible** definition: A payoff profile $r$ is feasible if there exist rational, non-negative values ${\alpha}_a \ such \ that \ \forall i$, we can express $r_i$ as ${\sum}_{a \in A} \ {\alpha}_a \ u_i(a)$, with ${\sum}_{a \in A} \ {\alpha}_a = 1$. ::: :::info Folk theorem: Consider any n-player game G and any payoff vector$r = (r_1,r_2,...,r_n)$. 1. If $r$ is the payoff in any Nash equilibrium of the infinitely repeated G with average rewards, then for each player $i$, $r_i$ is enforceable. 2. If $r$ is both feasible and enforceable, then $r$ is the payoff in some Nash equilibrium of the infinitely repeated $G$ with average rewards. ::: Discounted Repeated Games Stage game: $(N,A,u)$ Discount factors: $β_1,...,β_n \ ,and \ β_i \in [0,1]$ Assume a common discount factor for now: ${\beta}_i = {\beta} \ \forall i$ Payoff from a play of actions $a_1,...,a_t,...$: $${\sum}_t {\beta}^t_i \times u_i(a_t)$$ 當 Cooperate Payoff = Defect payoff 時有臨界$\beta$值當 Cooperate Payoff < Defect payoff 時則永遠 Defect # Week6: Bayesian Games We’ll still assume: 1. All possible games have the same number of agents and the same strategy space for each agent; **differing only in payoffs**. 2. Agents’ beliefs are posteriors, obtained by conditioning a common prior on individual private signals. :::success **Bayesian Game** Definition: A Bayesian game is a tuple $(N,G,P,I)$ where $N$ is a set of agents, $G$ is a set of games with $N$ agents each such that if $g, \ g^{'} \in G$ then for each agent $i \in N$ the strategy space in $g$ is identical to the strategy space in $g^{'}$, (for these $G = (N,A,u)$) $P \in {\Pi}(G)$ is a common prior over games, where ${\Pi}(G)$ is the set of all probability distributions over $G$(是g賽局的可能性), and $I = (I_1,...,I_n)$ is a set of partitions of $G$, one for each agent. (所以I將會是一個等價關係類) ::: :::success **Bayesian Game** Definition(in Epistemic type): A Bayesian game is a tuple $(N,A,{\Theta},p,u)$ where $N$ is a set of agents, $A = (A_1,...,A_n)$, where $A_i$ is the set of actions available to player $i$, ${\Theta} = ({\theta}_1,...,{\theta}_n)$, where ${\theta}_i$ is the type space of player $i$, $p : {\theta} \to [0,1]$ is the common prior over types, $u = (u_1,...,u_n)$, where $u_i : A \times {\theta} \ \to R$ is the utility function for player $i$. ::: ### Stratigies Given a Bayesian game $(N,A,{\Theta},p,u)$ with finite sets of players, actions, and types, strategies are defined as follows: * Pure strategy: $s_i : {\Theta}_i \to A_i$ * a choice of a pure action for player $i$ as a function of his or her type. * Mixed strategy: $s_i : {\Theta}_i \to {\pi}(A_i)$ * a choice of a mixed action for player $i$ as a function of his or her type. * $s_i(a_i|{\Theta}_i)$ * the probability under mixed strategy $s_i$ that agent $i$ plays action $a_i$, given that $i$’s type is ${\Theta}_i$. ### Expected Utility Three standard notions of expected utility: 1. ex-ante * the agent knows nothing about anyone’s actual type; 2. interim * an agent knows her own type but not the types of the other agents; 3. ex-post * the agent knows all agents’ types. Given a Bayesian game $(N,A,{\Theta},p,u)$ with finite sets of players, actions, and types, $i$’s **interim expected utility** with respect to type ${\theta}_i$ and a mixed strategy profile $s$ is $${EU}_i(s|{\theta}_i) = \sum_{ {\theta}_{-1} \in {\Theta}_{-i} } p({\theta}_{-i}|{\theta}_i) \cdot \{\sum_{a \in A}(\prod_{j \in N} s_j(a_j, {\theta}_j)) \cdot u_i(a,{\theta}_i,{\theta}_{-i})\}$$ $i$’s **ex-ante** expected utility with respect to a mixed strategy profile $s$ is: $$EU(s|{\theta}) = \sum_{{\theta}_i \in {\Theta}_i } p({\theta}_i) \cdot {EU}_i(s|{\theta}_i)$$ A Bayesian equilibrium is a mixed strategy profile s that satisfies: $\forall i$ and ${\theta}_i \in {\Theta}_i$ $$s_i \in arg\max_{s^′_i} EU_i(s^′_i,s_{-i}|{\theta}_i)$$ The above is defined based on interim maximization. It is equivalent to an ex-ante formulation: If $p({\theta}_i) \gt 0, \ \forall \ {\theta}_i \in {\Theta}_i$, then this is equivalent to requiring that $\forall i$ $$s_i \in arg\max_{s^′_i} EU_i(s^′_i,s_{-i}) = arg\max_{s^{'}_i} \sum_{{\theta}_i} (p({\theta}_i)EU_i(s^′_i,s_{-i}|{\theta}_i))$$ # Week 7: Coalitional Games We are not concerned with: * how the agents make individual choices within a coalition * how they coordinate :::warning **Transferable utility** assumption: * payoffs may be redistributed among a coalition’s members. * satisfied whenever payoffs are dispensed in a universal currency. * each coalition can be assigned a single value as its payoff. ::: :::success **Coalitional game with transferable utility** Definition: A coalitional game with transferable utility is a pair $(N,v)$, where $N$ is a finite set of players, indexed by $i$, and $v : 2^{\vert N \vert} \to \Bbb R$ associates with each coalition $S \subseteq N$ a real-valued payoff $v(S)$ that the coalition’s members can distribute among themselves, and We assume that $v(\emptyset) = 0$. ::: :::success **Superadditive game** Definition: A game $G = (N,v)$ is superadditive if $\forall S,T \subset N$, if $S \cap T = \emptyset$, then $v(S \cup T) \ge v(S) + v(T)$. ::: Superadditivity is justified when coalitions can always work without interfering with one another. ## Shapley’s axioms $\forall S$ that contains neither $i$ nor $j$, $v(S \cup \{i\}) = v(S \cup \{j\})$. :::warning **Symmetry** $\forall v$, if $i$ and $j$ are interchangeable then $\psi_i(N,v) = \psi_j(N,v)$. ::: $i$ is a dummy player if the amount that $i$ contributes to any coalition is 0. :::warning **Dummy player** $\forall v$, if $i$ is a dummy player then $\psi_i(N,v) = 0$. ::: :::warning **Additivity** For all two $v_1$ and $v_2$, $\psi_i(N,v_1 + v_2) = \psi_i(N,v_1) + \psi_i(N,v_2)$ for each $i$, where the game $(N,v_1 + v_2)$ is defined by $(v_1 + v_2)(S) = v_1(S) + v_2(S)$ for every coalition $S$. ::: ## Shapley Value :::info **Shapley Value** Theorem: Given a coalitional game $(N,v)$, there is a unique payoff division $x(v) = \psi(N,v)$ that divides the full payoff of the grand coalition and that satisfies the **Symmetry**, **Dummy player** and **Additivity** axioms: the Shapley Value ::: for each $i$, $$\psi_i(N,v) = {1 \over {N!}} \sum_{S \subseteq N \setminus \{i\}} \vert S\vert! \cdot (\vert N\vert − \vert S\vert −1)! \cdot [v(S \cup {i})−v(S)]$$ ## Core it is a set :::success **Core** definition: A payoff vector $x$ is in the core of a coalitional game $(N,v)$ $\iff \forall S \subseteq N$, $\sum_{i \in S}x_i \ge v(S)$ ::: Is the core always nonempty? > **NO.** > Consider again the voting game. > The set of minimal coalitions that meet the required 51 votes is $\{A,B\},\{A,C\},\{A,D\}, and\{B,C,D\}$. > If the sum of the payoffs to parties $B, C, and D$ is less than $100 million, then this set of agents has incentive to deviate. > If $B, C, and D$ get the entire payoff of $100 million, then $A$ will receive $0 and will have incentive to form a coalition with whichever of $B, C, and D$ obtained the smallest payoff. > Thus, the core is empty for this game. Is the core always unique? > **NO.** > Consider changing the example so that an 80% majority is required. > The minimal winning coalitions are now$\{A,B,C\}and\{A,B,D\}$. > Any complete distribution of the $100 million among $A$ and $B$ now belongs to the core. > All winning coalitions need the support of these two parties. > Thus, the core is not unique for this game. :::success **Simple game** Definition: A game $G = (N,v)$ is simple if $\forall S \subset N$, $v(S) ∈\in \{0,1\}$. ::: :::success **Veto** Definition: A player $i$ is a veto player if $v(N \setminus \{i\}) = 0$. ::: :::info In a **simple game** the **core** is **empty** $\iff$ there is **no veto player**. If there are veto players, the core consists of all payoff vectors in which the nonveto players get 0. ::: :::success **Convex game** Definition: A game $G = (N,v)$ is convex if $\forall S,T \subset N$, $v(S \cup T) \ge v(S) + v(T)−v(S \cap T)$. ::: > Convexity is a stronger condition than superadditivity. > :::info Every convex game has a nonempty core. ::: :::info In every convex game, the Shapley value is in the core. ::: 2/16/2019 done.