---
lang: ja
tags: MTNS-2021, lecture, linear programming
---
# 2021年度 交通社会システム論<br>第12回：割当問題とオークション(4) 主双対アルゴリズムと競り上げオークション
[ポータルへ戻る](https://hackmd.io/@nagae/MTNS_2021)
<div style="text-align: center">

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

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

# 今回で学ぶこと
**双対定理**と**相補性定理**を駆使した線形計画問題の解法である **主双対アルゴリズム** を学び，その手続きが **(主双対)競り上げオークション** として構成できることを学ぶ．

本稿は以下の内容を整理したものです：
- Bikhchandani, S. and Ostroy, J. “Ascending price Vickrey auctions,” *Games and Economic Behavior*, 55 (2), pp. 215–241 2006.
- Demange, G., Gale, D., and Sotomayor, M. “Multi-Item Auctions,” *Journal of Political Economy*, 94 (4), pp. 863–872 1986.
- de Vries, S., Schummer, J., and Vohra, R. V. “On ascending Vickrey auctions for heterogeneous objects,” *Journal of Economic Theory*, 132 (1), pp. 95–118 2007.

# 主双対アルゴリズム
## 相補性定理と主双対アルゴリズム
$\mathbf{A}\in\mathcal{R}^{M\times{}N}$, $\mathbf{b}\in \mathcal{R}^{M}$, $\mathbf{c} \in \mathcal{R}^{N}$を与件とした**線形計画問題**:
$$\begin{equation}
\min\left\{\left.\mathbf{c}^{\top}{x} \right| \mathbf{A} \mathbf{x} = \mathbf{b}, \mathbf{x} \geq \mathbf{0} \right\}
\end{equation}$$
とその**双対問題**:
$$\begin{equation}
\max\left\{\left.\mathbf{b}^{\top}\mathbf{y} \right| \mathbf{A}^{\top} \mathbf{y} \leq \mathbf{c} \right\}
\end{equation}$$
を考える． **相補性定理** より, $\mathbf{x} \in \mathcal{R}^{N}$, $\mathbf{y} \in \mathcal{R}^{M}$ が以下の3つの条件を全て満たすなら最適解．
1. $\mathbf{x}$ が**主実行可能**(i.e. $\mathbf{A}\mathbf{x} = \mathbf{b}, \mathbf{x} \geq \mathbf{0}$)
2. $\mathbf{y}$ が**双対実行可能**(i.e. $\mathbf{A}^{\top}\mathbf{y} \leq \mathbf{c}$)
3. $\mathbf{x}, \mathbf{y}$ が**相補性条件**を満足する：
$$\begin{align}
\mathbf{x}^{\top}\left(\mathbf{A}^{\top}\mathbf{y} - \mathbf{c}\right) &\Leftrightarrow
\sum_{n \in \mathcal{N}} x_{n} \left(\sum_{m\in\mathcal{M}} a_{m,n}y_{m} - c_{n}\right) = 0\\
&\Leftrightarrow
\begin{cases}
x_{n} > 0 &\rightarrow \sum_{m} a_{m,n}y_{m} = c_{n} \\
x_{n} = 0 &\leftarrow \sum_{m} a_{m,n} y_{m} < c_{n}
\end{cases}
\end{align}$$
ここで，$\mathcal{N} = \{1, \cdots, N\}$および$\mathcal{M} = \{1, \cdots, M\}$は**添字の集合**．

:::success
**主双対アルゴリズムの基本的考え方**
双対実行可能な(2を満足する)$\mathbf{y}$を生成し，相補性条件(3)を満足するように$\mathbf{x}$を構築する．そうして得られた$\mathbf{x}$が主実行可能(1を満足する)なら最適解．そうでなければ，より最適解に近づくように$\mathbf{y}$を改訂．
:::

## 相補性条件を満足する主変数の構築
ある**双対実行可能解** $\mathbf{y}^{(k)}$ に対して，**相補性条件**($\sum_{m} a_{m,n}y_{m} < c_{n} \rightarrow x_{n} = 0$)を満足するような主変数$\mathbf{x}^{(k)}$を構築するために，まず，**双対問題の不等式制約が厳密に満足される(主変数が0となる)添字の集合**を，以下のように定義する：
$$\begin{equation}
\mathcal{N}^{(k)}:=\left\{n \in \mathcal{N} \left|
\sum_{m \in \mathcal{M}} a_{m,n}y_{k}^{(k)} < c_{n}
\right.\right\}
\end{equation}$$

主変数$\mathbf{x}^{(k)}$が**相補性条件**を満足するためには，以下の制約を満たす必要がある:
$$\begin{equation}
x_{n}^{(k)} = 0, \forall n \in \mathcal{N}^{(k)}
\end{equation}$$

上述の制約の下で，**主実行可能解**$\mathbf{x}^{(k)}$を構築できるならば，$\mathbf{x}^{(k)}$および$\mathbf{y}^{(k)}$は**最適解**である．

では，==どうすれば実行可能な$\mathbf{x}^{(k)}$を構築できる(もしくは不能であると判定できる)のだろうか?== → **二段階単体法**の**第1段階**(初期実行可能解の生成)に似た方法を使う．

## 主実行可能な解の構築方法
$x_{n}=0$となる添字集合$\mathcal{N}^{(k)}$を与えられた下で，**相補性条件**を満足する実行可能な主変数を構築したい．→**二段階単体法**の第1段階と同様の**補助問題**を考える．

まず，主問題の**等式制約の右辺**がいずれも$b_{m}\geq0$となるように，$b_{m} < 0$となっている制約条件$m$の両辺に$-1$を乗じておく．
$$\begin{align}
\text{[P]} \qquad \min_{\mathbf{x}} &\sum_{n \in \mathcal{N}} c_{n} x_{n} \\
\text{s.t.}\quad &
\sum_{n \in \mathcal{N}} a_{m,n} x_{n} = b_{m} (\geq 0), \qquad \forall m \in \mathcal{M},\\
& x_{n} \geq 0, \quad \forall n \in \mathcal{N}.
\end{align}$$

次に，相補性条件と等価な制約$x_{n}^{(k)} = 0, \forall n \in \mathcal{N}^{(k)}$を設けた以下の**制約付き問題**(restricted problem)を考える:
$$\begin{align}
\text{[RP]} \qquad \min_{\mathbf{x}^{(k)}, \mathbf{z}^{(k)}} &\sum_{m \in \mathcal{M}} z_{m}^{(k)} \\
\text{s.t.}\quad &
\sum_{n \in \mathcal{N}} a_{m,n} x_{n} + z_{m}^{(k)} = b_{m} (\geq 0), \qquad \forall m \in \mathcal{M},\\
& x_{n}^{(k)} = 0, \quad \forall n \in \mathcal{N}^{(k)}\\
& x_{n}^{(k)} \geq 0, \quad \forall n \not \in \mathcal{N},\\
& z_{m}^{(k)} \geq 0, \quad \forall m \in \mathcal{M}
\end{align}$$
ここで，$z_{m}^{(k)}$は$m$番目等式制約に対応する人工的な**補助変数**．

この制約付き問題$\text{[RP]}$は，以下の便利な性質を持つ:
1. **自明な実行可能解**$(\mathbf{x}^{(k)}, \mathbf{z}^{(k)})=(\mathbf{0}, \mathbf{b})$を持つ．
2. 任意の実行可能解に対して**目的関数が非負**である．
3. $\text{[RP]}$の**最適値が0**，すなわち最適解において$\mathbf{z}^{(k)} = \mathbf{0}$であるとき，かつその時に限り，$\mathbf{x}^{(k)}$は**主実行可能**．

:::warning
[二段階単体法の第1段階](https://hackmd.io/@nagae/MTNS_2021-Ch06#%E4%BA%8C%E6%AE%B5%E9%9A%8E%E5%8D%98%E4%BD%93%E6%B3%95%E3%81%A7%E7%94%A8%E3%81%84%E3%82%8B%E8%A3%9C%E5%8A%A9%E5%95%8F%E9%A1%8C)では1次元の人工変数だけを用い，等式制約の右辺定数を非負にしておく必要も無かった．

上記$\text{[RP]}$で$M$次元の補助変数を導入したり，$b_{m}$の非負性を要求したりするのは，続く制約付き双対問題を使って双対変数$\mathbf{y}$を改訂するためである．
:::

## 双対変数の改訂
**制約付き問題**$\text{[RP]}$の最適値が0より大きいとき，与えられた双対実行可能解$\mathbf{y}^{(k)}$の下で，**相補性条件を満足する主実行可能解は存在しない**． このとき，$\text{[RP]}$の**双対実行可能解**を用いることで，$\mathbf{y}^{(k)}$よりも**最適解に近い双対実行可能解**を求められる．

$\text{[RP]}$の双対問題は，以下のように定式化される：
$$\begin{align}
\text{[RD]} \quad \max_{\mathbf{\psi}^{(k)}} &\sum_{m \in \mathcal{M}} b_{m} \psi_{m}^{(k)}\\
\text{s.t.} \quad & \sum_{m \in \mathcal{M}} a_{m, n} \psi_{m}^{(k)} \leq 0, \quad \forall n \not \in \mathcal{N}^{(k)}\\
& \psi_{m}^{(k)} \leq 1, \quad \forall m \in \mathcal{M}
\end{align}$$

いま，**制約付き問題**$\text{[RP]}$の最適解が0より大きいとき，**弱双対定理**より，
\begin{equation}
0 < \underbrace{\sum_{m \in \mathcal{M}} b_{m} \psi_{m}^{(k)}}_{\text{[RD]の目的関数}} \leq \underbrace{\sum_{m \in \mathcal{M}} z_{m}^{(k)}}_{\text{[RD]の最適値}}
\end{equation}
を満足し，かつ
\begin{equation}
\mathbf{y}^{(k+1)} =\mathbf{y}^{(k)} + \alpha^{(k)} \boldsymbol{\psi}^{(k)}
\end{equation}
が双対実行可能となるような$\text{[RD]}$の**実行可能解**(最適解である必要はない) $\boldsymbol{\psi}^{(k)}$ および**ステップ・サイズ**(正のスカラ) $\alpha^{(k)} > 0$が**必ず**存在する．

$\mathbf{A}^{\top} \mathbf{y}^{(k)} \leq \mathbf{c}$ かつ$\mathbf{A}^{\top} \boldsymbol{\psi}^{(k)} \leq \mathbf{0}$だから，
$$
\mathbf{A}^{\top} \mathbf{y}^{(k+1)} = \mathbf{A}^{\top} \mathbf{y}^{(k)}
+\alpha^{(k)} \mathbf{A}^{\top}\boldsymbol{\psi}^{(k+1)} \leq \mathbf{c}
$$

こうして得られる新しい**双対実行可能解** $\mathbf{y}^{(k+1)} = (y_{m}^{(k+1)})_{m \in \mathcal{M}}$ に対する**双対目的関数**は，
\begin{align}
\sum_{m \in \mathcal{M}} b_{m} y_{m}^{(k+1)}
&= \sum_{m \in \mathcal{M}} b_{m}
\left(y_{m}^{(k)} + \alpha \psi_{m}^{(k)}\right)
\\
&= \sum_{m \in \mathcal{M}} y_{m}^{(k)} +
\alpha^{(k)} \underbrace{\sum_{m \in \mathcal{M}} \psi_{m}^{(k)}}_{> 0}\\
&> \sum_{m \in \mathcal{M}} y_{m}^{(k)}
\end{align}
となり， $\mathbf{y}^{(k)}$における目的関数よりも大きい，すなわち**最適解に「近い」** ことが保証される．

## 主双対アルゴリズム
- **Step 0** (初期化): **初期双対実行可能解** $\mathbf{y}^{(1)}$ を選ぶ． $k:=1$．
- **Step 1** (制約付き問題の構築): 双対問題の不等式制約が厳密に満足される($x_{n}=0$となる)添字集合$\mathcal{N}^{(k)}$を求める．
- **Step 2** (最適性の確認): **制約付き問題**$\text{[RP]}$を解く．最適値が0ならば，$\mathbf{x}^{(k)}$および$\mathbf{y}^{(k)}$が**最適解**．最適値が正ならば，$\mathbf{y}^{(k)}$に対応する相補性条件を満足する主実行可能解は存在しない． **Step 3** へ．
- **Step 3** (解の改訂方向の探索): $\mathbf{b}^{\top}\boldsymbol{\psi}^{(k)} > 0$かつ$\mathbf{y}^{(k)} + \alpha^{(k)} \boldsymbol{\psi}^{(k)}$が双対実行可能となるような**制約付き双対問題**$\text{[RD]}$の実行可能解$\boldsymbol{\psi}^{(k)}$およびステップ・サイズ$\alpha^{(k)}$を求める．
- **Step 4** (解の改訂): **双対実行可能解**を $\mathbf{y}^{(k+1)} := \mathbf{y}^{(k)} + \alpha ^{(k)} \boldsymbol{\psi}^{(k)}$と改訂する．$k:=k+1$として **Step 1**へ．

以下では，この手続きが，**競り上げオークション**として解釈できることを見ていこう．

# 主双対オークション
## 双対解の価格による特徴付け
価格$\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 && 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 j \in \mathcal{G}_{j}^{\ast}(\mathbf{p}^{(k)}), \forall j \in \mathcal{N} \\
&x_{ij} = 0 && \forall j \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$