---
lang: ja
tags: OptMech-2021, lecture
---
# 2021年度 知的システム<br>第13回：割当問題とオークション(5) 主双対競り上げオークション
[ポータルへ戻る](https://hackmd.io/@nagae/OptMech_2021)
<div style="text-align: center">

このページへは以下のQRコードまたはURLからアクセスできます：

<code style="font-size:20pt">https://hackmd.io/@nagae/OptMech_2021-Ch12</code>
</div>

# 主双対オークション
## 双対解の価格による特徴付け
価格$\mathbf{p}^{(k)} = \left(p_{i}^{(k)}\right)_{i \in \mathcal{G}}$が与えられたとき，買手$j$の利得$\pi_{j}$は双対問題の制約条件:
\begin{equation}
\pi_{j} \geq v_{ij} - p_{i}^{(k)} \quad \forall i \in \mathcal{G}
\end{equation}
より
\begin{equation}
\pi_{j} \geq \max_{i \in \mathcal{G}} \left\{v_{ij} - p_{i}^{(k)}
\right\}
\end{equation}
となる．さらに，非負制約$\pi_{j} \geq 0$より，
\begin{equation}
\pi_{j} \geq \left[\max_{i \in \mathcal{G}} \left\{v_{ij} - p_{i}^{(k)}
\right\}\right]_{+}
\end{equation}
ただし，$[z]_{+} = \max\{z, 0\}$は非負空間への射影演算子．双対問題の目的関数$\sum_{j} \pi_{j} + \sum_{i} p_{i} d_{i}$は$\pi_{j}$について単調増加だから，$\mathbf{p}^{(k)}$に対する最適な$\pi_{j}$は
\begin{equation}
\pi_{j}(\mathbf{p}^{(k)}) = \left[\max_{i \in \mathcal{G}} \left\{v_{ij} - p_{i}^{(k)}\right\}\right]_{+}
\end{equation}
と一意に決まる． 従って，双対問題の解は**財の価格**$\mathbf{p}$のみで特徴づけることができる．

## 参入者集合と需要集合
双対実行可能解$\mathbf{p}^{(k)}$に対して，
**相補性条件を満足するような主実行可能解**を求めるために
**制約付き問題**$\text{[RP]}$を構成したい．
そのために，次の2つの集合を定義しておく．
:::success
**参入者集合**
価格$\mathbf{p}^{(k)}$の下で**正の利得**を獲得できる買手(**参入者**)の集合
\begin{equation}
\mathcal{N}^{\ast}(\mathbf{p}^{(k)}) := \left\{
j : \pi_{j}(\mathbf{p}^{(k)}) > 0
\right\}
\end{equation}
:::

:::success
**買手$j$の需要集合**
買手$j$ にとって**最大の利得**をもたらす(**買手$j$が需要する**)財の集合:
\begin{equation}
\mathcal{G}_{j}^{\ast}(\mathbf{p}^{(k)}) := \left\{
i: \pi_{j}(\mathbf{p}^{(k)}) = v_{ij} - p_{i}^{(k)}
\right\}
\end{equation}
:::
ただし，買手$j$が**参入者**でない(i.e. $\pi_{j}(\mathbf{p^{k}})=0$ )場合は，$\mathcal{G}_{j}^{\ast}(\mathbf{p}^{(k)}) = \emptyset$とする．

## 価格$\mathbf{p}^{(k)}$ に対する相補性条件
価格$\mathbf{p}^{(k)}$に対応する**相補性条件**:
\begin{align}
\sum_{i \in \mathcal{G}} \sum_{j \in \mathcal{N}}
x_{ij} \left(\pi_{j}(\mathbf{p}^{(k)}) - v_{ij} + p_{i}^{(k)}\right) = 0 &\Leftrightarrow
\begin{cases}
x_{ij} > 0 &\rightarrow \pi_{j}(\mathbf{p}^{(k)}) = v_{ij} - p_{i}^{(k)}\\
\color{red}{x_{ij} = 0} &\color{red}{\leftarrow \pi_{j}(\mathbf{p}^{(k)}) > v_{ij} - p_{i}^{(k)}}\\
\end{cases}\\
\sum_{j \in \mathcal{N}} \pi_{j}(\mathbf{p}^{(k)})\left(\sum_{i \in \mathcal{G}} x_{ij} - 1\right) = 0 &\Leftrightarrow
\begin{cases}
\color{red}{\pi_{j}(\mathbf{p}^{(k)}) > 0} &\color{red}{\rightarrow
\sum_{i \in \mathcal{G}} x_{ij} = 1}\\
\pi_{j}(\mathbf{p}^{(k)}) = 0 &\leftarrow
\sum_{i \in \mathcal{G}} x_{ij} < 1
\end{cases}
\end{align}
2つの相補性条件と整合的な(i.e. 相補性条件と実行可能性を満たす) **主変数** を構築できるか判別したい．

まずはこれらの条件が何を意味しているのかをおさらいしておこう．
:::success
1. $\pi_{j}(\mathbf{p}^{(k)}) > v_{ij} - p_{i}^{(k)} \rightarrow x_{ij} = 0$
財$i$が買手$j$の**利得を最大化しない**(i.e. 財$i$が買手$j$に**需要されない**, $i \not \in \mathcal{G}_{j}^{\ast}(\mathbf{p}^{(k)})$)なら，その財は買手には割り当てられない．

2. $\pi_{j}(\mathbf{p}^{(k)}) > 0 \rightarrow \sum_{i \in \mathcal{G}} x_{ij} = 1$
買手$j$ が**正の利得**を得る(i.e. $j$が**参入者**, $j \in \mathcal{N}^{\ast}(\mathbf{p}^{(k)}))$なら，その買手には何らかの財が割り当てられる．
:::

## 相補性条件と整合するために主変数が満たすべき条件
- $\pi_{j}(\mathbf{p}^{(k)}) > v_{ij} - p_{i}^{(k)} \rightarrow x_{ij} = 0$ と整合するための条件
\begin{equation}
x_{ij} = 0 \quad \forall i \not \in \mathcal{G}_{j}^{\ast}(\mathbf{p}^{(k)}), \quad \forall j \in \mathcal{N}
\end{equation}
- $\pi_{j}(\mathbf{p}^{(k)}) > 0 \rightarrow \sum_{i \in \mathcal{G}} x_{ij} = 1$ と整合するための条件
\begin{equation}
\sum_{i \in \mathcal{G}} x_{ij} =1 \quad \forall j \in \mathcal{N}^{\ast}(\mathbf{p}^{(k)})
\end{equation}

以上の2つを加えた制約を満足する**主実行可能解**(実行可能な配分)を求める(あるいはそのような配分が存在しないことを判別する)ための**制約つき問題**は， 補助変数$\mathbf{z} = \{z_{ij}\}$を用いて，
\begin{align}
\text{[RP]} \quad \max_{\mathbf{x}, \mathbf{z}} &-\sum_{j \in \mathcal{N}^{\ast}(\mathbf{p}^{(k)})} z_{j}\\
\text{s.t.} \quad
&\sum_{i \in \mathcal{G}} x_{ij} + z_{j} = 1 && \forall j \in \mathcal{N}^{\ast}(\mathbf{p}^{(k)}) && (\psi_{j})\\
&\sum_{j \in \mathcal{N}} x_{ij} \leq d_{i} && \forall i \in \mathcal{G} &&(q_{i})\\
&x_{ij} \geq 0 && \forall i \in \mathcal{G}_{j}^{\ast}(\mathbf{p}^{(k)}), \forall j \in \mathcal{N} \\
&x_{ij} = 0 && \forall i \not \in \mathcal{G}_{j}^{\ast}(\mathbf{p}^{(k)}), \forall j \in \mathcal{N}\\
&z_{j} \geq 0 && \forall j \in \mathcal{N}^{\ast}(\mathbf{p}^{(k)})
\end{align}と定式化できる．括弧内はあとで使う双対変数．

この**制約つき問題**の最適値が0なら，価格$\mathbf{p}^{(k)}$の下で最適な配分$\mathbf{x}^{\ast}$が実現できる．
最適値が負の場合(つまり，$z_{j} > 0$となるようなものが1つでもある場合)，価格$\mathbf{p}^{(k)}$を改訂する必要がある→$\text{[RP]}$の双対問題を使うことで改訂方向が求められる．

## 制約つき双対問題
$\text{[RP]}$の双対問題は以下のように導かれる：
\begin{align}
\text{[RD]} \quad \min_{\boldsymbol{\psi}, \mathbf{q}} & \sum_{j \in \mathcal{N}^{\ast}(\mathbf{p}^{(k)})} \psi_{j} + \sum_{i \in \mathcal{G}} d_{i} q_{i} \\
\text{s.t.} \quad
& \psi_{j} + q_{i} \geq 0 && \forall i \in \mathcal{G}_{j}^{\ast}(\mathbf{p}^{(k)}), \forall j \in \mathcal{N} && (x_{ij})\\
& \psi_{j} \geq -1 && \forall j \in \mathcal{N}^{\ast}(\mathbf{p}^{(k)}) && (z_{j})\\
& q_{i} \geq 0 && \forall i \in \mathcal{G}
\end{align}

この制約付き双対問題$\text{[RD]}$の**実行可能解**$(\boldsymbol{\psi}^{(k)}, \mathbf{q}^{(k)})$を，
以下の2つの条件：
1. 目的関数$\sum_{j \in \mathcal{N}^{\ast}(\mathbf{p}^{(k)})} \psi_{j} + \sum_{i \in \mathcal{G}} d_{i} q_{i}$が**負**
2. $(\mathbf{p}^{(k+1)}, \boldsymbol{\pi}^{(k+1)}) = (\mathbf{p}^{(k)} + \mathbf{q}^{(k)}, \boldsymbol{\pi}^{(k)} + \boldsymbol{\psi}^{(k)})$ が**双対実行可能**

を満足するように選べれば，現在の解$(\mathbf{p}^{(k)}, \boldsymbol{\pi}^{(k)})$より**最適解に「近い」双対実行可能解**$(\mathbf{p}^{(k+1)}, \boldsymbol{\pi}^{(k+1)})$が得られる．

→ **「どの財の価格を上げ(その結果どの買手の利得が下が)ればいいか」**

## 財サブ集合(束)の需要と供給
財集合$\mathcal{G}$のサブ集合$\mathcal{G}^{\prime}$を考える．財集合が$\mathcal{G} = \{A, B, C\}$なら，考えられる「財サブ集合」は以下の通り：
$$
\{A, B, C\}, \{A, B\}, \{A, C\}, \{B, C\}, \{A\}, \{B\}, \{C\}, \emptyset
$$

:::success
**財サブ集合$\mathcal{G}^{\prime}$の需要量**
価格$\mathbf{p}^{(k)}$が与えられたとき，$\mathcal{G}^{\prime}$に**需要集合が含まれる買手の数**:
$$\begin{equation}
D_{\mathcal{G}^{\prime}}(\mathbf{p}^{(k)}):=
\#\left\{j: \mathcal{G}_{j}^{\ast}(\mathbf{p}^{(k)}) \subseteq \mathcal{G}^{\prime}\right\}
\end{equation}$$を，$\mathcal{G}^{\prime}$の(価格$\mathbf{p}^{(k)}$の下での)**需要量**と呼ぶ．
:::

:::success
**財サブ集合$\mathcal{G}^{\prime}$の供給量**
$\mathcal{G}^{\prime}$に含まれる財の供給量の総和
\begin{equation}
S_{\mathcal{G}^{\prime}}:= \sum_{i \in \mathcal{G}^{\prime}} d_{i}
\end{equation}を，$\mathcal{G}^{\prime}$の**供給量**と呼ぶ．
:::

## 超過需要集合と価格競り上げ定理
各財サブ集合に対して**需要量**と**供給量**が与えられれば，以下の**超過需要集合**(正確には「超過需要・財サブ・集合」)が定義できる．
:::success
**超過需要集合**
価格$\mathbf{p}^{(k)}$の下で，ある財サブ集合$\mathcal{G}^{\prime}$について，その**需要量が供給量を上回る**:
\begin{equation}
D_{\mathcal{G}^{\prime}}(\mathbf{p}^{(k)}) > S_{\mathcal{G}^{\prime}}
\end{equation}とき，$\mathcal{G}^{\prime}$は **需要超過(over demanded)** であるという．
:::
このとき，以下の**価格競上げ定理**が成り立つ(証明は後述)．
:::success
ある価格$\mathbf{p}^{(k)}$の下で， ある超過需要集合$\mathcal{G}^{\prime} \subseteq \mathcal{G}$に含まれる財の価格を**1単位**だけ上げる．すなわち，財$i$の価格の増分$\mathbf{q}^{(k)} = (q_{i}^{(k)})_{i \in \mathcal{G}}$を
$$\begin{equation}
{q}_{i}^{(k)} := \begin{cases}1 & \text{if } i \in \mathcal{G}^{\prime}\\
0 & \text{otherwise}
\end{cases}\end{equation}$$
とするとき，新しい価格
$$
\mathbf{p}^{(k+1)} := \mathbf{p}^{(k)} + \mathbf{q}^{(k)}
$$
の下での解$(\mathbf{p}^{(k+1)}, \boldsymbol{\pi}^{(k+1)})$は**双対実行可能**で，$(\mathbf{p}^{(k)}, \boldsymbol{\pi}^{(k)})$よりも**最適解に「近い」**(i.e. より小さい目的関数値を実現する)．
:::

:::warning
上述の価格の改訂幅($q_{i}^{(k)}$の大きさ)は，各買手の**評価値の単位**に合わせる．評価値が10円単位の場合は，価格の改訂は10円ずつ行う．
:::

## (主双対)競り上げオークションの手続き
以上より，主双対アルゴリズムを活用した競り上げオークションの手続きは，下記のように整理できる：
- **Step 0** (初期化): **初期価格**を$\mathbf{p}^{(1)} = \mathbf{0}$とする. $k:=1$.
- **Step 1** (制約付き問題の構築): 現在の価格$\mathbf{p}^{(k)}$の下で，各買手は**需要集合**$\mathcal{G}_{j}^{\ast}(\mathbf{p}^{(k)})$を表明する．
- **Step 2** (最適性の判別・解の改訂方向の探索): 全ての財サブ集合$\mathcal{G}^{\prime}$について**需要量** $D_{\mathcal{G}^{\prime}}(\mathbf{p}^{(k)})$を求め，供給量$S_{\mathcal{G}^{\prime}}$と比較して**超過需要**か否かを判別． **超過需要集合** $\mathcal{G}^{\prime}$が見つかれば，それを**値上げ対象**として**Step 3**へ． どの財サブ集合も超過需要でなければ，**全ての買手の需要を満たす割当** が存在するので，これを**最適割当**として終了．
- **Step 3** (解の改訂): 値上げ対象$\mathcal{G}^{\prime}$に含まれる財の価格を**1単位増加**させたものを$\mathbf{p}^{(k+1)}$とする．$k:=k+1$として**Step 1**へ．

## 主双対競上げオークションの解と VCG価格
主双対競上げオークションの **Step 2**で超過需要集合が複数存在する場合，その中で要素数が最小のもの(**最小超過需要集合**, minimum overdemanded set)を選ぶ場合，主双対競り上げオークションで得られる価格は**双対問題の解の中で価格が最小となるもの**(i.e. VCG価格)に一致する．

## 私的情報の下での主双対オークションの利点
- **Step1** の制約付き問題の構築において,管理者が知る必要があるのは 各買手の**需要集合**だけで， **私的情報** である 評価値の **観測・推計** が不要.
- 各買手$j \in \mathcal{N}$は, 自らの**評価値**$\mathbf{v}_{j} = (v_{ij})_{i \in \mathcal{G}}$と，公開されている価格$\mathbf{p}^{(k)}$のみに基づいて**需要集合** $\mathcal{G}_{j}^{\ast}(\mathbf{p}^{(k)})$を構築できる.
- 各買手が **虚偽の需要集合** を申告する**誘引**を持たなければ，最適割当の実現が保証される. → 各買手にとって需要集合を正直に申告することが **Nash 均衡戦略** となることが保証されている.

:::warning
正直な申告が**Nash均衡戦略**とは「**全員が正直に申告**している場合，その中で誰か一人だけが虚偽を申告しても利得を改善できない」ことを差す． これに対して，VCG価格は **(弱)支配戦略**であった．つまり「ある買手 $l$ に注目したとき， **$l$以外の他の買手がどんな申告をしていようが**， 買手$l$ にとっては正直に申告する以上の利得を獲得できない」のである．
:::

## 価格競上げ定理の証明
### 証明のアウトライン
値上げ対象となる財のサブ集合が$\mathcal{G}^{\prime}$であるときの**価格の変化分** を $\mathbf{q} = \{q_{i}: q_{i}=1 \forall i \in \mathcal{G}^{\prime} \text{ and } q_{i}=0 \forall i \not \in \mathcal{G}^{\prime}\}$ とし，
\begin{equation}
\psi_{j}(\mathbf{q}) = \max_{i \in \mathcal{G}_{j}^{\ast}(\mathbf{p}^{(k)})}\left\{ - q_{i}\right\} \quad
\Leftrightarrow \quad
\psi_{j}(\mathbf{q}) = \begin{cases}
-1 & \text{if } \mathcal{G}_{j}^{\ast}(\mathbf{p}^{(k)}) \subseteq \mathcal{G}^{\prime}\\
0 & \text{otherwise}
\end{cases}
\end{equation}と定義する．この式は，価格変化に伴う **参入者** $j \in \mathcal{N}^{\ast}(\mathbf{p}^{(k)})$の **最大利得の変化分** と解釈できる． すなわち，価格$\mathbf{p}^{(k)}$の下で，**需要する「全ての財」の価格が上がった時に限り，1単位減少する**．

「価格を$\mathbf{q}$だけ増加させることで，より最適解に「近い」新しい価格が得られること」を証明するため，以下を順に示していこう．
1. $(\mathbf{q}, \boldsymbol{\psi}(\mathbf{q}))$が **$\text{[RD]}$実行可能**である．
2. $(\mathbf{q}, \boldsymbol{\psi}(\mathbf{q}))$に対する **$\text{[RD]}$の目的関数が負**である:
$$\sum_{j \in \mathcal{N}^{\ast}(\mathbf{p}^{(k)})} \psi_{j}(\mathbf{q}) + \sum_{i \in \mathcal{G}} d_{i}q_{i} < 0.$$
3. 新しい価格$\mathbf{p}^{(k+1)} = \mathbf{p}^{(k)} + \mathbf{q}$およびその下での最大利得$\boldsymbol{\pi}(\mathbf{p}^{(k+1)}) = \boldsymbol{\pi}(\mathbf{p}^{(k)}) + \boldsymbol{\psi}(\mathbf{q})$ が**双対実行可能**である．

### $(\mathbf{q}, \boldsymbol{\psi}(\mathbf{q}))$が **$\text{[RD]}$実行可能**
$\mathbf{p}^{(k)}$に対応する**制約付き双対問題**$\text{[RD]}$の許容領域は
$$
\left\{
(\mathbf{q}, \boldsymbol{\psi}) \left|
\begin{split}
\psi_{j} + q_{i} \geq 0 \quad& \forall i \in \mathcal{G}_{j}^{\ast}(\mathbf{p}^{(k)}) , \forall j \in \mathcal{N}^{\ast}(\mathbf{p}^{(k)})\\
q_{i} \geq 0 \quad& \forall i \in \mathcal{G}\\
\psi_{j} \geq -1 \quad&\forall j \in \mathcal{N}^{\ast}(\mathbf{p}^{(k)})
\end{split}
\right.
\right\}
$$
である．ここで，
- 任意の参入者$j \in \mathcal{N}^{\ast}(\mathbf{p}^{(k)})$について $\psi_{j} = \max_{i \in \mathcal{G}_{j}^{\ast}(\mathbf{p}^{(k)})}\{-q_{i}\}$ であるから，$\psi_{j} \geq q_{i}\, \forall i \in \mathcal{G}_{j}^{\ast}(\mathbf{p}^{(k)})$
- $q_{i}$は $0$ または $1$ のいずれかだから，$q_{i} \geq 0$
- 定義より$\psi_{j}$は $0$ または $-1$ のいずれかだから，$\psi_{j} \geq -1$.

従って，$(\mathbf{q}, \boldsymbol{\psi}(\mathbf{q}))$は **$\text{[RD]}$実行可能**. $\square$

### $(\mathbf{q}, \boldsymbol{\psi}(\mathbf{q}))$に対する **$\text{[RD]}$の目的関数が負**
$\text{[RD]}$の目的関数：
$$\sum_{j \in \mathcal{N}^{\ast}(\mathbf{p}^{(k)})} \psi_{j}(\mathbf{q}) + \sum_{i \in \mathcal{G}} d_{i}q_{i} < 0$$
となることを示そう．

まず，目的関数の第1項は，
$$\psi_{j}(\mathbf{q}) = \begin{cases}
-1 & \text{if } \mathcal{G}_{j}^{\ast}(\mathbf{p}^{(k)}) \subseteq \mathcal{G}^{\prime}\\
0 & \text{otherwise}
\end{cases}
$$より，
$$\begin{align}
\sum_{j \in \mathcal{N}^{\ast}(\mathbf{p}^{(k)})} \psi_{j}(\mathbf{q}) &= - \#\left\{j: \mathcal{G}_{j}^{\ast}(\mathbf{p}^{(k)}) \subseteq \mathcal{G}^{\prime}\right\}\\
&= - D_{\mathcal{G}^{\prime}}(\mathbf{p}^{(k)})
\end{align}
$$すなわち， **値上げ対象となる財サブ集合** $\mathcal{G}^{\prime}$の **需要量**(の符号を反転させたもの)に等しい．

次に，目的関数の第2項は，
$$\begin{equation}
\mathbf{q}_{i} := \begin{cases}1 & \text{if } i \in \mathcal{G}^{\prime}\\
0 & \text{otherwise}
\end{cases}
\end{equation}$$
より，
$$
\sum_{i \in \mathcal{G}} d_{i} q_{i} = \sum_{i \in \mathcal{G}^{\prime}} d_{i} = S_{\mathcal{G}^{\prime}}
$$
すなわち，**値上げ対象となる財サブ集合** $\mathcal{G}^{\prime}$ の**供給量** に等しい．

以上のことから，値上げ対象となる財サブ集合 $\mathcal{G}^{\prime}$ が**超過需要**であれば，すなわち，$D_{\mathcal{G}^{\prime}}(\mathbf{p}^{(k)}) > S_{\mathcal{G}^{\prime}}$ であれば，**$\text{[RD]}$の目的関数は負**である． $\square$

### $(\mathbf{p}^{(k+1)}， \boldsymbol{\pi}(\mathbf{p}^{(k+1)})) = (\mathbf{p}^{(k)} + \mathbf{q}， \boldsymbol{\pi}(\mathbf{p}^{(k)}) + \boldsymbol{\psi}(\mathbf{q}))$ が**双対実行可能**

ここでは，簡単のために，
$$
\boldsymbol{\pi}(\mathbf{p}^{(k)}) = \boldsymbol{\pi}^{(k)}, \qquad
\boldsymbol{\psi}(\mathbf{q}) = \boldsymbol{\psi}
$$
と記述することにしよう．

まず，$\mathbf{p}^{(k)}, \mathbf{q} \geq \mathbf{0}$ より，$\mathbf{p}^{(k+1)} = \mathbf{p}^{(k)} + \mathbf{q} \geq \mathbf{0}$ は明らか．
残る双対問題の制約は
- $\pi_{j} \geq v_{ij} - p_{i}$
- $\pi_{j} \geq 0$

の2つ．

いま，$v_{ij}, p_{i}$がいずれも同じ単位の **離散値** を取るならば，上記制約を満たす$\pi_{j}$もまた同じ単位の **離散値** であり， 以下の不等式を満足する：
\begin{align}
\pi_{j} &> v_{ij} - p_{i} &&\rightarrow \pi_{j} - 1 \geq v_{ij} - p_{i} \\
\pi_{j} &>0 &&\rightarrow \pi_{j} - 1 \geq 0
\end{align}

以下, 全ての買手$j \in \mathcal{N}$ について，(i)利得が変化しない($\psi_{j}=0$)場合と，
(ii)利得が1単位減少する($\psi_{j}=-1$)場合のそれぞれについて，新しい解$(\mathbf{p}^{(k+1)}, \pi_{j}^{(k+1)})=(\mathbf{p}^{(k)}+\mathbf{q}, \pi_{j}^{(k)} + \psi_{j})$ が双対問題の制約条件を満足することを示そう．
**■ $\psi_{j}=0$ となる場合**
- $\pi_{j}^{(k)} \geq 0$ であるから，$\pi_{j}^{(k+1)}=\pi_{j} ^{(k)}+ \psi_{j}=\pi_{j}^{(k)} \geq 0$.
- $q_{i} \in \{0, 1\}$より，
$$
\pi_{j}^{(k)} \geq v_{ij} - p_{i}^{(k)} \rightarrow
\pi_{j}^{(k+1)} \geq v_{ij} - (p_{i}^{(k)} + q_{i}) =: v_{ij} - p_{i}^{(k+1)}
$$

従って，$(p_{i}^{(k+1)}, \pi_{j}^{(k+1)})$は双対実行可能である．

**■ $\psi_{j} = -1$となる場合**
- この時，買手$j$ は**参入者**である(i.e. $j \in \mathcal{N}^{\ast}(\mathbf{p})$)から，$\pi_{j}^{(k)} > 0$. $\pi_{j}^{(k)}$は離散値だから，$\pi_{j}^{(k+1)} = \pi_{j}^{(k)} + \psi_{j} \geq 0$.
- $\psi_{j}=-1$となるのは，買手$j$の需要集合の財が全て値上げされる(i.e. $\mathcal{G}_{j}^{\ast}(\mathbf{p}^{(k)}) \in \mathcal{G}^{\prime}$)ので，
- 値上りする財$i \in \mathcal{G}^{\prime}$については，
$$
\pi_{j}^{(k)} \geq v_{ij} - p_{i}^{(k)} \quad \rightarrow \quad \pi_{j}^{(k)} + \psi_{j} \geq v_{ij}-(p_{i}^{(k)} + q_{i})
$$が成立する．
(**不等式の両辺が1単位ずつ減少する**ので大小関係は変化しない)
- 値上りしない財$i \not\in \mathcal{G}^{\prime}$については， **改訂前の価格では需要されていない**ので
$$
\pi_{j}^{(k)} > v_{ij}-p_{i}^{(k)}
$$が成り立つ． $\pi_{j}^{(k)}$は離散値であるから，
$$
\pi_{j}^{(k)} > v_{ij} - p_{i}^{(k)} \quad
\rightarrow \pi_{j}^{(k)} + \psi_{j} \geq v_{ij} - (p_{i}^{(k)}+q_{i})
$$

よって，いずれの場合でも $\pi_{j}^{(k+1)} \geq v_{ij} - p_{i}^{(k+1)}$ が成り立つ．

従って，$(\mathbf{p}^{(k+1)}, \pi_{j}^{(k+1)})$ は双対実行可能である．

以上のことから， $(\mathbf{p}^{(k+1)}， \boldsymbol{\pi}(\mathbf{p}^{(k+1)})) = (\mathbf{p}^{(k)} + \mathbf{q}， \boldsymbol{\pi}(\mathbf{p}^{(k)}) + \boldsymbol{\psi}(\mathbf{q}))$ は**双対実行可能**である. $\square$