LP Duality

Prime problem:

max⁡xcTxs.t.Ax≤bx≥0\begin{aligned} \max_{\mathbf{x}} \mathbf{c}^{\mathrm{T}}\mathbf{x}\\ s.t. \quad \mathbf{A}\mathbf{x}\le \mathbf{b}\\ \mathbf{x}\ge 0 \end{aligned}

Interpretation:

  • xix_i: amount of product ii produced
  • bib_i: amount of raw material of type ii available
  • aija_{ij}: amount of raw material ii used to produced 11 unit of product jj
  • cjc_j: profit from 11 unit of product jj

Dual problem:

min⁡ybTys.t.ATy≥cy≥0\begin{aligned} \min_{y} \mathbf{b}^{\mathrm{T}}\mathbf{y} \\ s.t. \quad \mathbf{A}^{\mathrm{T}}\mathbf{y}\ge \mathbf{c}\\ \mathbf{y}\ge 0 \end{aligned}

  • yiy_i 可以理解为单位原材料 ii 的售价
  • ATy≥c\mathbf{A}^{\mathrm{T}}\mathbf{y}\ge \mathbf{c} 是因为只有当直接售卖原材料的收益大于产品利润是，才会出售
  • min⁡ybTy\min_{y} \mathbf{b}^{\mathrm{T}}\mathbf{y} 是买家希望最小化支出

有结论：
bTy∗=cTx∗\mathbf{b}^{\mathrm{T}}\mathbf{y}^{*}=\mathbf{c}^{\mathrm{T}}\mathbf{x}^{*}

Strong Duality of LP:
If the primal and dual are feasible, then both have the same optimal objective value. (feasible 表示有解)

Farka’s lemma

Exactly one of the following statements is true:

  • ∃x≥0,s.t. Ax=b\exists \mathbf{x}\ge 0,\quad s.t. ~\mathbf{A}\mathbf{x}=\mathbf{b}
  • ∃y,s.t. yTA≥0 and yTb<0\exists \mathbf{y}, \quad s.t. ~\mathbf{y}^{\mathrm{T}}\mathbf{A}\ge 0 \text{ and } \mathbf{y}^{\mathrm{T}}\mathbf{b}<0

Geometric Interpretation of Fraka’s

考虑二维的情形，记组成 A\mathbf{A} 的向量为 a1,a2\mathbf{a}_1,\mathbf{a}_2

如果想要满足第一个条件，那么向量 b\mathbf{b} 应当在图像中高亮区域内；但是如果要满足第二个条件，则需要找到 y\mathbf{y}，使得向量 a1,a2\mathbf{a}_1,\mathbf{a}_2 和 b\mathbf{b} 应当正好在直线 yTx=0\mathbf{y}^{\mathrm{T}}\mathbf{x}=0 的两侧。因此此两个条件只能有一个满足。

Proof of Duality

要证明 bTy∗=cTx∗\mathbf{b}^{\mathrm{T}}\mathbf{y}^{*}=\mathbf{c}^{\mathrm{T}}\mathbf{x}^{*}，可以先证明左边小于等于右边，再证明右边小于等于左边。

cTx=xTc≤xTATy≤bTy\mathbf{c}^{\mathrm{T}}\mathbf{x}=\mathbf{x}^{\mathrm{T}}\mathbf{c}\le \mathbf{x}^{\mathrm{T}}\mathbf{A}^{\mathrm{T}}\mathbf{y} \le \mathbf{b}^{\mathrm{T}}\mathbf{y}

现在希望证明 cTx∗≥bTy∗\mathbf{c}^{\mathrm{T}}\mathbf{x}^{*}\ge \mathbf{b}^{\mathrm{T}}\mathbf{y}^{*}

记 cTx∗=Δ\mathbf{c}^{\mathrm{T}}\mathbf{x}^{*}=\Delta，由于 x∗\mathbf{x}^{*} 为最优解，因此

∄cTx≥Δ+ε(∀ε>0),Ax≤b,x≥0\not \exists \mathbf{c}^{\mathrm{T}}\mathbf{x}\ge \Delta+\varepsilon (\forall \varepsilon>0), \mathbf{A}\mathbf{x}\le \mathbf{b}, \mathbf{x}\ge 0

我们使用 α0,α\alpha_0, \mathbf{\alpha} 将不等式写为等式

−cTx+α0=−Δ+ε,Ax+α=b,α0,α,x≥0-\mathbf{c}^{\mathrm{T}}\mathbf{x}+\alpha_0 = -\Delta + \varepsilon, \mathbf{A}\mathbf{x}+\mathbf{\alpha} = \mathbf{b}, \alpha_0, \mathbf{\alpha}, \mathbf{x}\ge 0

将其写为矩阵形式

(−cT10A0I)(xα0α)=(−Δ−εb)\begin{pmatrix} -\mathbf{c}^{\mathrm{T}} & 1 & \mathbf{0} \\ \mathbf{A} & \mathbf{0} & \mathbf{I} \end{pmatrix} \begin{pmatrix} \mathbf{x} \\ \alpha_0 \\ \mathbf{\alpha} \end{pmatrix} = \begin{pmatrix} -\Delta - \varepsilon \\ \mathbf{b} \end{pmatrix}

由 Farkas’ lemma，因为上述方程不存在解，因此

∃λ0≥0,λ1≥0\exists \lambda_0\ge 0, \mathbf{\lambda}_1 \ge 0

使得

−cTλ0+λ1TA≥0 and −(Δ+ε)λ0+λ1Tb<0⇒1λ0λ1TA≥cT and 1λ0λ1Tb<Δ+ε\begin{gather*} -\mathbf{c}^{\mathrm{T}}\lambda_0 + \mathbf{\lambda}_1^{\mathrm{T}}\mathbf{A}\ge 0 \text{ and } -(\Delta+\varepsilon)\lambda_0 + \mathbf{\lambda}_1^{\mathrm{T}}\mathbf{b} < 0 \\ \Rightarrow \frac{1}{\lambda_0} \mathbf{\lambda}_1^{\mathrm{T}}\mathbf{A} \ge \mathbf{c}^{\mathrm{T}} \text{ and } \frac{1}{\lambda_0}\mathbf{\lambda}_1^{\mathrm{T}}\mathbf{b}<\Delta + \varepsilon \end{gather*}

令 y=λ1/λ0y = \mathbf{\lambda}_1 / \lambda_0，那么对于 ∀ε>0\forall \varepsilon>0，都有 y∗Tb≤yTb<Δ+ε\mathbf{y^{*}}^{\mathrm{T}}\mathbf{b} \le \mathbf{y}^{\mathrm{T}}\mathbf{b}<\Delta+\varepsilon，因此

y∗Tb≤Δ=cTx∗\mathbf{y^{*}}^{\mathrm{T}}\mathbf{b}\le \Delta=\mathbf{c}^{\mathrm{T}}\mathbf{x}^{*}

Another explanation of Duality

将原问题写为：

max⁡xcTxs.t.a1Tx≤b1a2Tx≤b2⋯anTx≤bnx≥0\begin{aligned} \max_{\mathbf{x}} \mathbf{c}^{\mathrm{T}}\mathbf{x}\\ s.t. \quad \mathbf{a}_1^{\mathrm{T}} \mathbf{x}\le b_1\\ \mathbf{a}_2^{\mathrm{T}} \mathbf{x}\le b_2 \\ \cdots \\ \mathbf{a}_n^{\mathrm{T}} \mathbf{x}\le b_n \\ \mathbf{x}\ge 0 \end{aligned}

引入一系列系数 y1,y2,…,yn>0y_1,y_2, \ldots ,y_n>0，则有

y1a1Tx≤b1y1y2a2Tx≤b2y2⋯ynanTx≤bnyn\begin{gather*} y_1 \mathbf{a}_1^{\mathrm{T}}\mathbf{x} \le b_1 y_1\\ y_2 \mathbf{a}_2^{\mathrm{T}}\mathbf{x} \le b_2 y_2\\ \cdots \\ y_n \mathbf{a}_n^{\mathrm{T}}\mathbf{x} \le b_n y_n \end{gather*}

假如满足条件 y1a1T+y2a2T+⋯+ynanT≥cTy_1 \mathbf{a}_1^{\mathrm{T}} + y_2 \mathbf{a}_2^{\mathrm{T}} + \cdots + y_n \mathbf{a}_n^{\mathrm{T}}\ge \mathbf{c}^{\mathrm{T}}，即 ATy≥c\mathbf{A}^{\mathrm{T}}\mathbf{y}\ge \mathbf{c}，则有

cTx≤(y1a1T+y2a2T+⋯+ynanT)x≤bTy\mathbf{c}^{\mathrm{T}}\mathbf{x} \le (y_1 \mathbf{a}_1^{\mathrm{T}} + y_2 \mathbf{a}_2^{\mathrm{T}} + \cdots + y_n \mathbf{a}_n^{\mathrm{T}})\mathbf{x} \le \mathbf{b}^{\mathrm{T}}\mathbf{y}

从而得到了对偶问题。

从直观上来说，就是希望 c\mathbf{c} 能够被 a1,a2,…an\mathbf{a}_1,\mathbf{a}_2, \ldots \mathbf{a}_n 的线性组合得到，从而就可以确定 cTx\mathbf{c}^{\mathrm{T}}\mathbf{x} 的上界；同理，这个上界也是 bTy\mathbf{b}^{\mathrm{T}}\mathbf{y} 的下界。

Two-player zero sum Game

  • Two player p1,p2
  • Payoff to p1 = - Payoff to p2

Let:

  • A(i,j)A(i,j) is the payoff to p1 when ii is p1’s action, jj is p2’s action.
  • xx: prob distribution over p1’s actions
  • yy: prob distribution over p2’s actions

⇒u1(x,y)=∑ijA(i,j)xiyj=xTAyu2(x,y)=−u1(x,y)\begin{gather*} \Rightarrow u_1(x,y)=\sum_{ij}A(i,j)x_i y_j = \mathbf{x}^{\mathrm{T}}\mathbf{A}\mathbf{y}\\ u_2(x,y) = -u_1(x,y) \end{gather*}

Thus a NE (x∗,y∗)(x^{*},y^{*}) satisfies

(x∗)TAy∗≥xTAy∗and (x∗)TAy∗≤(x∗)TAy\begin{aligned} &(x^{*})^{\mathrm{T}}A y^{*} \ge x ^{\mathrm{T}} A y^{*}\\ \text{and~} &(x^{*})^{\mathrm{T}} A y^{*}\le (x^{*})^{\mathrm{T}}A y \end{aligned}

我们称 (x∗,y∗)(x^{*},y^{*}) 是 saddle point

Minmax Theorem

  1. min⁡ymax⁡xxTAy=max⁡xmin⁡yxTAy(1)\min_{y} \max_{x} x^{\mathrm{T}}Ay = \max_{x} \min_{y} x^{\mathrm{T}}Ay \tag{1}

    上述结果得到的值我们称其为 game 的 value。

  2. max⁡x(min⁡yxTAy)(2.1)\max_{x}(\min_{y}x^{\mathrm{T}}Ay) \tag{2.1}

    min⁡y(max⁡xxTAy)(2.2)\min_{y}(\max_{x}x^{\mathrm{T}}Ay) \tag{2.2}

    x∗x^{*} solves (2.1), y∗y^{*} solves (2.2). Then

    • (x∗,y∗)(x^{*},y^{*}) is NE
    • (x∗)TAy∗(x^{*})^{\mathrm{T}}Ay^{*} is the value of the game

  3. If (x∗,y∗)(x^{*},y^{*}) is a NE

    • (x∗)TAy∗(x^{*})^{\mathrm{T}}Ay^{*} is the value of the game
    • x∗x^{*} solves (2.1), y∗y^{*} solves (2.2)

以上三个条件得到的 (x∗,y∗)(x^{*},y^{*}) 都是相同的。

Proof

  1. Suppose p1 wants to maximize its worst case payoff

    max⁡xmin⁡yxTAy=max⁡xmin⁡j(xTA)j\begin{gather*} \max_{x} \min_{y} x^{\mathrm{T}}Ay\\ = \max_{x} \min_{j} (x^{\mathrm{T}}A)_{j} \end{gather*}

    问题转化为 LP 问题，可以用 LP Duality 来解

    max⁡x,v1v1s.t.v1≤(xTA)j,∀jx≥0\begin{gather*} \max_{x,v_1} v_1 \\ \tag{LP1} s.t. \quad v_1\le (x^{\mathrm{T}}A)_{j} ,\forall j\\ x\ge 0 \end{gather*}

    Similarly, p2’s problem is

    min⁡y,v2v2s.t.v2≥(Ay)i,∀iy≥0\begin{gather*} \min_{y,v_2} v_2 \\ \tag{LP2} s.t. \quad v_2\ge (Ay)_{i}, \forall i \\ y\ge 0 \end{gather*}

    Thus by strong duality, we have v1∗=v2∗v_1^{*}=v_2^{*}, or

    max⁡xmin⁡yxTAy=min⁡ymax⁡xxTAy\max_{x}\min_{y}x^{\mathrm{T}}Ay=\min_{y}\max_{x}x^{\mathrm{T}}Ay

  2. Let x⋆x^{\star } be a solution of LP1. From the constraint

    v1⋆≤(x⋆TA)j∀j\begin{aligned}v_1^\star\leq(x^{\star\mathrm{T}}A)_j\forall j\end{aligned}

    Multiply yj⋆y_j^\star and sum over jj, we get

    ∑jv1⋆yj⋆≤∑j(x⋆TA)jyj⋆\begin{aligned}\sum_jv_1^\star y_j^\star\leq\sum_j(x^{\star\mathrm{T}}A)_jy_j^\star\end{aligned}

    ⇒v1⋆≤x⋆TAy⋆\Rightarrow v_{1}^{\star}\leq x^{\star\mathrm{T}}Ay^{\star}

    where y⋆y^{\star } is the solution of LP2. Similarly, we can show that

    v2⋆≥x⋆TAy⋆v_{2}^{\star}\geq x^{\star\mathrm{T}}Ay^{\star}

    Since v1⋆=v2⋆v_{1}^{\star }= v_{2}^{\star }, we have

    x⋆TAy⋆=max⁡xmin⁡yxTAy=min⁡ymax⁡xxTAyx^{\star\mathrm{T}}Ay^{\star}=\max_{x}\min_{y}x^{\mathrm{T}}Ay=\min_{y}\max_{x}x^{\mathrm{T}}Ay

    Then we can show that (x⋆,y⋆)( x^\star , y^\star ) is a NE.

    min⁡yx⋆TAy=max⁡xmin⁡yxTAy=min⁡ymax⁡xxTAy=max⁡xxTAy⋆≥x⋆TAy⋆\operatorname*{min}_{y}x^\mathrm{\star T}Ay=\operatorname*{max}_{x}\operatorname*{min}_{y}x^\mathrm{T}Ay=\operatorname*{min}_{y}\operatorname*{max}_{x}x^\mathrm{T}Ay=\operatorname*{max}_{x}x^\mathrm{T}Ay^{\star} \ge x^{\star \mathrm{T}}Ay^{\star}

    ⇒y⋆\Rightarrow y^\star solves min⁡ymax⁡xxTAy\min_{y} \max_{x} x^\mathrm{T} Ay

    Similarly, x∗x^{*} solves max⁡xmin⁡yxTAy\max_{x}\min_{y}x^{\mathrm{T}}Ay. So (x∗,y∗)(x^{*},y^{*}) is a NE.

  3. Suppose (x∗,y∗)(x^{*},y^{*}) is a NE, then

    x∗TAy∗=min⁡yx∗TAy≤max⁡xmin⁡yxTAyx^{* {\mathrm{T}}} A y^{*} = \min_{y} x^{* {\mathrm{T}}} A y \le \max_{x} \min_{y} x^{\mathrm{T}}Ay

    Similarly,

    x∗TAy∗=max⁡xxTAy≥min⁡ymax⁡xxTAyx^{* {\mathrm{T}}}A y^{*} = \max_{x} x^{\mathrm{T}}Ay\ge \min_{y} \max_{x} x^{\mathrm{T}}Ay

    ⇒min⁡ymax⁡xxTAy≤x⋆TAy⋆≤max⁡xmin⁡yxTAy\Rightarrow\min_y\max_xx^{\mathrm{T}}Ay\leq x^{\star\mathrm{T}}Ay^{\star}\leq\max_x\min_yx^{\mathrm{T}}Ay

    Considering

    min⁡ymax⁡xf(x,y)≥max⁡xmin⁡yf(x,y)\begin{aligned}\min_y\max_xf(x,y)\geq\max_x\min_yf(x,y)\end{aligned}

    So

    min⁡yx⋆TAy=x⋆TAy⋆=max⁡xmin⁡yxTAy≥min⁡yxTAy∀x\min_{y}x^{\star\mathsf{T}}Ay=x^{\star\mathsf{T}}Ay^{\star}=\max_{x}\min_{y}x^{\mathsf{T}}Ay\geq\min_{y}x^{\mathsf{T}}Ay\forall x

    ⇒x∗\Rightarrow x^{*} maximizes min⁡yxTAy\min_{y}x^{\mathrm{T}}Ay. Similarly, y∗y^{*} minimizes max⁡xxTAy\max_{x}x^{\mathrm{T}}Ay

Remark

(x∗,y∗)(x^{*},y^{*}), (x~,y~)(\tilde{x},\tilde{y}) are NE, then (x∗,y~)(x^{*},\tilde{y}), (x~,y∗)(\tilde{x},y^{*}) are also NE.

None Zero Sum Game

ui(ai,a−i)u_i(a_i,a_{-i}) payoff to p1, ai∈Aia_i\in A_i (discrete, finite)
pi(ai)=Pr⁡(player i plays ai)p_{i}(a_i)=\operatorname{Pr}(\text{player } i \text{ plays } a_i)
ui(pi,p−i)=E(payoff to pi)u_i(p_{i},p_{-i})=E(\text{payoff to } p_{i})

Theorem: A NE exists.

Let C⊆RnC \subseteq{\mathbb{R}^{n}} be a convex, closed, bounded set. Let f:C→Cf: C \rightarrow C be a continuous function. The ff has a fixed point, i.e. ∃x∈C,x=f(x)\exists x \in C, x=f(x)。从直观上来说，就是符合条件的 y=f(x)y=f(x) 与 y=xy=x 必定有交点。

Let p=(p1,p2,…,pn)p=(p_1,p_2, \ldots ,p_n) be a set of strategies.
Define ri(ai)=(ui(ai,p−i)−ui(pi,p−i))+r_i(a_i)=(u_i(a_i,p_{-i})-u_i(p_{i},p_{-i}))^{+}，这个变量表示的是从策略 pip_{i} 变化到 aia_i 之后收益的增加量。我们希望能找到 pi∗p_{i}^{*}，使得 ∀ai\forall a_i，有 ri(ai)=0r_i(a_i)=0，此时就能够得到一个纳什均衡。

Define

fi(pi(ai))=pi(ai)+ri(ai)∑α(pi(α)+ri(α))f_i(p_{i}(a_i)) = \frac{p_{i}(a_i)+r_i(a_i)}{\sum_{\alpha}(p_{i}(\alpha)+r_i(\alpha))}

pi(ai)p_{i}(a_i) 表示的是对于策略 pip_{i}，选中 aia_i 的概率。可以看出这个式子相当于求出 pi(ai)+ri(ai)p_{i}(a_i)+r_i(a_i) 在所有可能中的权重。

记

f(p)=(f1(p1)f2(p2)⋮fn(pn))f(p) = \begin{pmatrix} f_1(p_1) \\ f_2(p_2) \\ \vdots \\ f_n(p_n) \end{pmatrix}

  1. 注意到 p=(p1,p2,…pn)⊆[0,1]np=(p_1,p_2, \ldots p_n) \subseteq[0,1]^{n}，p∈p \in closed, bounded, convex set
  2. ff 是一个连续函数

所以存在一个 fixed point pp，p=f(p)p=f(p)，此时利用 ff 的表达式，应当有

pi(ai)=pi(ai)+ri(ai)∑α(pi(α)+ri(α))p_{i}(a_i) = \frac{p_{i}(a_i)+r_i(a_i)}{\sum_{\alpha}(p_{i}(\alpha)+r_i(\alpha))}

同样的，我们希望证明 ri(ai)=0r_i(a_i)=0。

First, we claim that for each ii, ∃ai,s.t. ri(ai)=0\exists a_i, s.t.~ r_i(a_i)=0.
Suppose for some ii, ri(ai)>0,∀air_i(a_i)>0, \forall a_i

⇒ui(ai,p−i)>ui(pi,p−i),∀ai\Rightarrow u_i(a_i,p_{-i})>u_i(p_{i},p_{-i}) ,\forall a_i

⇒∑ai∈Aipi(ai)ui(pi,p−i)>ui(pi,p−i)\Rightarrow \sum_{a_i\in A_i}p_{i}(a_i) u_i(p_{i},p_{-i}) > u_i(p_{i},p_{-i})

⇔ui(pi,p−i)>ui(pi,p−i)\Leftrightarrow u_i(p_{i},p_{-i})>u_i(p_{i},p_{-i})

which is contradictory.

Fix ii, let aia_i be ri(ai)=0r_i(a_i)=0

pi(ai)=pi(ai)∑α(pi(α)+ri(α))p_{i}(a_i) = \frac{p_{i}(a_i)}{\sum_{\alpha}(p_{i}(\alpha)+ r_i(\alpha))}

⇒∑α∈Aipi(α)+∑α∈Airi(ai)=1\Rightarrow \sum_{\alpha\in A_i} p_{i}(\alpha) + \sum_{\alpha \in A_i}r_i(a_i)=1

⇒∑α∈Airi(α)=0\Rightarrow \sum_{\alpha \in A_i}r_i(\alpha) = 0

Thus, ∀α∈Ai,ri(α)=0\forall \alpha\in A_i, r_i(\alpha)=0

Proof using the kakvtani fixed point theorem

Let CC be a closed, bounded, convex subset of Rn\mathbb{R}^{n}. Let ff be a corresponding mapping each point in CC to a subset of CC.

f:C→2Cf: C \rightarrow 2^{C}

需要证明这一点是因为之前遇到过 p∈BP(p)p \in BP(p)，这也是一个从 point 到 subset 的映射。

Suppose that:

  1. f(x)≠∅ ∀xf(x)\neq \emptyset~\forall x,
  2. f(x)f(x) is a convex set ∀x\forall x
  3. ff has a closed graph. (ff has a closed graph if all sequence {xn}∈C\left\{ x_n \right\} \in C and {yn}\left\{ y_n \right\}, (xn,yn)→(x,y)(x_n,y_n)\rightarrow(x,y) with yn∈f(xn)y_n\in f(x_n), ⇒y∈f(x)\Rightarrow y\in f(x)).

Then ff has a fixed point in CC, x∈f(x)x\in f(x).

To estalish the existance of a solution to

p∈BP(p)p\in BP(p)

where

p=(p1p2⋮pn)BP(p)=(BP(p−1)BP(p−2)⋮BP(p−n))p=\begin{pmatrix} p_1\\ p_2\\ \vdots \\ p_{n} \end{pmatrix} \quad BP(p) = \begin{pmatrix} BP(p_{-1}) \\ BP(p_{-2}) \\ \vdots \\ BP(p_{-n}) \end{pmatrix}

We will verify BP has all the properties required in the kakvtani FP theorem.

  1. BP(p)BP(p) is a non-empty for each pp. 这是显然的，因为在别人给出了策略的情况下，我们总能找到最大化自身收益的策略。
  2. 根据 convex 的定义。If pi∗,pi~∈BP(p−i)p_{i}^{*}, \tilde{p_{i}} \in BP(p_{-i}), αpi∗+(1−α)pi~∈BP(p−i)\alpha p_{i}^{*}+(1-\alpha)\tilde{p_{i}} \in BP(p_{-i})。这也是显然的。由以下 uiu_i 的定义

    ui(pi,p−i)=∑aui(ai,a−i)p1(a1)p2(a2)⋯pn(an)u_i(p_{i},p_{-i}) = \sum_{a} u_i(a_i, a_{-i}) p_1(a_1) p_2(a_2) \cdots p_n(a_n)

    从线性的特征可以看出

    ui(pi,p−i)=ui(pi~,p−i)=αui(pi,p−i)+(1−α)ui(pi~,p−i)=ui(αpi∗+(1−α)pi~,p−i)u_i(p_{i},p_{-i}) = u_i(\tilde{p_{i}},p_{-i}) = \alpha u_i(p_{i},p_{-i}) + (1-\alpha) u_i(\tilde{p_{i}},p_{-i}) = u_i(\alpha p_{i}^{*}+(1-\alpha)\tilde{p_{i}},p_{-i})

  3. Let (pi(n),p−i(n))→(pi,p−i)(p_{i}^{(n)}, p_{-i}^{(n)}) \rightarrow (p_{i}, p_{-i}) and pi(n)∈BPi(p−i(n))p_{i}^{(n)} \in BP_{i}(p_{-i}^{(n)})
    Suppose that pi∉BPi(p−i)p_{i} \not \in BP_{i}(p_{-i}). Then ∃p^i\exists \hat{p}_i and ε>0\varepsilon>0

    ui(p^i,p−i)≥ui(pi,p−i)+εu_i(\hat{p}_i,p_{-i})\ge u_i(p_{i},p_{-i}) + \varepsilon

    p^i\hat{p}_i is a better response for p−i(n)p_{-i}^{(n)} (for some nn) then pi(n)p_{i}^{(n)} thus contradictory.
    For sufficiently large nn,

    ui(p^i,p−i(n))≥ui(p^i,p−i)−ε2≥ui(pi,p−i)+ε−ε2≥ui(pi(n),p−i(n))−ε4+ε2=ui(pi(n),p−i(n))+ε4\begin{aligned} u_i(\hat{p}_i,p_{-i}^{(n)}) &\ge u_i(\hat{p}_i,p_{-i}) - \frac{\varepsilon}{2} \\ &\ge u_i(p_{i},p_{-i}) + \varepsilon -\frac{\varepsilon}{2} \\ &\ge u_i(p_{i}^{(n)}, p_{-i}^{(n)}) - \frac{\varepsilon}{4} + \frac{\varepsilon}{2} \\ &=u_i(p_{i}^{(n)},p_{-i}^{(n)}) + \frac{\varepsilon}{4} \end{aligned}