1. 2-1 Mixed Strategies and Nash Equilibrium (I)
  2. 2-2 Mixed Strategies and Nash Equilibrium (II)
  3. 2-3 Computing Mixed Nash Equilibrium
  4. 2-4 Hardness Beyond 2x2 Games - Basic
  5. 2-4 Hardness Beyond 2x2 Games - Advanced
  6. 2-5 Example: Mixed Strategy Nash
  7. 2-6 Data: Professional Sports and Mixed Strategies

Game Theory

Week 2: Mixed-Strategy Nash Equilibrium

https://www.coursera.org/learn/game-theory-1/home/week/2

2-1 Mixed Strategies and Nash Equilibrium (I)

举例：设置检查站，攻击与防守

2-2 Mixed Strategies and Nash Equilibrium (II)

Define a strategy \(s_i\) for agent \(i\) as any probability distribution over the actions \(A_i\).

  • pure strategy: only one action is played with positive probability

  • mixed strategy: more than one action is played with positive probability

    these actions are called the support of the mixed strategy

\(S_i\): all strategies for \(i\)

\(S = S_1 \times \cdots \times S_n\): all strategy profiles

  • expected utility

\[u_i(s) = \sum_{a \in A} u_i(a) Pr(a \mid s)\]

\[Pr(a \mid s) = \prod_{j \in N} s_j(a_j)\]

  • Theorem (Nash, 1950) 定理（纳什，1950）

    Every finite game has a Nash equilibrium.

    每一个有限博弈都有纳什均衡。

2-3 Computing Mixed Nash Equilibrium

概率计算

2-4 Hardness Beyond 2x2 Games - Basic

2 example algorithms to finding Nash Equilibrium:

2 个寻找纳什均衡的算法：

  • LCP (Linear Complementarity) formulation

  • Support Enumeration Method

PPAD (Polynomial Parity Arguments on Directed graphs)

  • Theorem

    Computing a Nash equilibrium is PPAD-complete

2-4 Hardness Beyond 2x2 Games - Advanced

  • LCP (Linear Complementarity) formulation

    1. Finding a NE with a specific support

    2. Smart heuristic search through all sets of support

the following are NP-complete:

  1. (Uniqueness) Given a game \(G\), does there exist a unique equilibrium in \(G\)?

  2. (Pareto optimality) Given a game \(G\), does there exist a strictly Pareto efficient equilibrium in \(G\)?

  3. (Guaranteed payoff) Given a game \(G\) and a value \(v\), does there exist an equilibrium in \(G\) in which some player \(i\) obtains an expected payoff of at least \(v\)?

  4. (Guaranteed social welfare) Given a game \(G\), does there exist an equilibrium in which the sum of agents' utilities is at least \(k\)?

  5. (Action inclusion) Given a game \(G\) and an action \(a_i \in A_i\) for some player \(i \in N\), does there exist an equilibrium of \(G\) in which player \(i\) plays action \(a_i\) with strictly positive probability?

  6. (Action exclusion) Given a game \(G\) and an action \(a_i \in A_i\) for some player \(i \in N\), does there exist an equilibrium of \(G\) in which player \(i\) plays action \(a_i\) with zero probability?

2-5 Example: Mixed Strategy Nash

Example: Soccer Penalty Kicks

举例：足球罚球

2-6 Data: Professional Sports and Mixed Strategies

上节例子的数据分析