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

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

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

# 主双対オークション | Primal-Dual Auction
## 双対解の価格による特徴付け | Characterize of Dual Solution by Price
価格$\boldsymbol{p}^{(k)} = \left(p_{i}^{(k)}\right)_{i \in \mathcal{G}}$が与えられたとき，買手$j$の利得$\pi_{j}$は双対問題の制約条件:
Given price $\boldsymbol{p}^{(k)} = \left(p_{i}^{(k)}\right)_{i \in \mathcal{G}}$, buyer $j$ 's maximum payoff $\pi_{j}$ should satisfy the dual constraint:
$$\begin{equation}
\pi_{j} \geq v_{ij} - p_{i}^{(k)} \quad \forall i \in \mathcal{G}
\end{equation}$$
より
and thus
$$\begin{equation}
\pi_{j} \geq \max_{i \in \mathcal{G}} \left\{v_{ij} - p_{i}^{(k)}
\right\}
\end{equation}$$
となる．さらに，非負制約$\pi_{j} \geq 0$より，
From the non-negativity constraint $\pi_{j} \geq 0$, it should be met
$$\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\}$は非負空間への射影演算子．
where $[z]_{+} = \max\{z, 0\}$ is a projection operator onto the non-negative orthant.

双対問題の目的関数$\sum_{j} \pi_{j} + \sum_{i} p_{i} d_{i}$は$\pi_{j}$について単調増加だから，$\boldsymbol{p}^{(k)}$に対する最適な$\pi_{j}$は
Since the dual objective $\sum_{j} \pi_{j} + \sum_{i} p_{i} d_{i}$ monotonically increases with respect to $\pi_{j}$, the optimal $\pi_{j}$ for given $\boldsymbol{p}^{(n)}$ is uniquely determined as
$$\begin{equation}
\pi_{j}(\boldsymbol{p}^{(k)}) = \left[\max_{i \in \mathcal{G}} \left\{v_{ij} - p_{i}^{(k)}\right\}\right]_{+}
\end{equation}$$
と一意に決まる． 従って，双対問題の解は**財の価格**$\boldsymbol{p}$のみで特徴づけることができる．
Therefore a dual solution can be characterized only by the price $\boldsymbol{p}$.

## 参入者集合と需要集合 | Active Buyers Set and Demand Correspondence
双対実行可能解$\boldsymbol{p}^{(k)}$に対して，
**相補性条件を満足するような主実行可能解**を求めるために
**制約付き問題**$\text{[RP]}$を構成したい．
そのために，次の2つの集合を定義しておく．
Given a dual feasible solution (i.e. price) $\boldsymbol{p}^{(k)}$, the corresponding **restricted problem** $\mathrm{[RP]}$ should be constructed to obtain a **primal feasible solution** (if possible) that satisfies the complementarity condition. To do so, the following two sets are introduced.
:::success
**参入者集合** (set of active buyers)
価格$\boldsymbol{p}^{(k)}$の下で**正の利得**を獲得できる買手(**参入者**)の集合:
The set of active buyers, who achieve positive payoff under price $\boldsymbol{p}^{(k)}$:
$$\begin{equation}
\mathcal{N}^{\ast}(\boldsymbol{p}^{(k)}) := \left\{
j : \pi_{j}(\boldsymbol{p}^{(k)}) > 0
\right\}
\end{equation}$$
:::

:::success
**買手$j$の需要集合** (the demand correspondence of buyer $j$)
買手$j$ にとって**最大の利得**をもたらす(**買手$j$が需要する**)財の集合:
The set of items that achieves maximum payoff to buyer $j$ (i.e. the set of items that buyer $j$ demands):
$$\begin{equation}
\mathcal{G}_{j}^{\ast}(\boldsymbol{p}^{(k)}) := \left\{
i: \pi_{j}(\boldsymbol{p}^{(k)}) = v_{ij} - p_{i}^{(k)}
\right\}
\end{equation}$$
:::
ただし，買手$j$が**参入者**でない(i.e. $\pi_{j}(\boldsymbol{p^{(k)}})=0$ )場合は，$\mathcal{G}_{j}^{\ast}(\boldsymbol{p}^{(k)}) = \emptyset$とする．
For any non-active buyer $j$ (i.e $\pi_{j}(\boldsymbol{p}^{(k)})) = 0$), let $\mathcal{G}_{j}^{\ast}(\boldsymbol{p}^{(k)}) = \emptyset$.

## 価格$\boldsymbol{p}^{(k)}$ に対する相補性条件 | Complementarity Condition for Given Price $\boldsymbol{p}^{(k)}$
価格$\boldsymbol{p}^{(k)}$に対応する**相補性条件**:
The complementarity condition corresponding to a given price $\boldsymbol{p}^{(k)}$:
$$\begin{align}
\sum_{i \in \mathcal{G}} \sum_{j \in \mathcal{N}}
x_{ij} \left(\pi_{j}(\boldsymbol{p}^{(k)}) - v_{ij} + p_{i}^{(k)}\right) = 0 &\Leftrightarrow
\begin{cases}
x_{ij} > 0 &\rightarrow \pi_{j}(\boldsymbol{p}^{(k)}) = v_{ij} - p_{i}^{(k)}\\
\color{red}{x_{ij} = 0} &\color{red}{\leftarrow \pi_{j}(\boldsymbol{p}^{(k)}) > v_{ij} - p_{i}^{(k)}}\\
\end{cases}\\
\sum_{j \in \mathcal{N}} \pi_{j}(\boldsymbol{p}^{(k)})\left(\sum_{i \in \mathcal{G}} x_{ij} - 1\right) = 0 &\Leftrightarrow
\begin{cases}
\color{red}{\pi_{j}(\boldsymbol{p}^{(k)}) > 0} &\color{red}{\rightarrow
\sum_{i \in \mathcal{G}} x_{ij} = 1}\\
\pi_{j}(\boldsymbol{p}^{(k)}) = 0 &\leftarrow
\sum_{i \in \mathcal{G}} x_{ij} < 1
\end{cases}
\end{align}$$
2つの相補性条件と整合的な **主実行可能解** を構築できるか判別したい．
We want to examine whether is we can construct a primal feasible solution consistent with these complementarity conditions.

まずはこれらの条件が何を意味しているのかをおさらいしておこう．
Let us summarize what there conditions imply:
:::success
1. $\pi_{j}(\boldsymbol{p}^{(k)}) > v_{ij} - p_{i}^{(k)} \rightarrow x_{ij} = 0$
財$i$が買手$j$の**利得を最大化しない**(i.e. 財$i$が買手$j$に**需要されない**, $i \not \in \mathcal{G}_{j}^{\ast}(\boldsymbol{p}^{(k)})$)なら，その財は買手には割り当てられない．
If item $i$ does not maximize buyer $j$ 's payoff (i.e. $i$ is not demanded by $j$; $i \not \in \mathcal{G}_{j}^{\ast}(\boldsymbol{p}^{(k)})$), $i$ is not assigned to $j$.

2. $\pi_{j}(\boldsymbol{p}^{(k)}) > 0 \rightarrow \sum_{i \in \mathcal{G}} x_{ij} = 1$
買手$j$ が**正の利得**を得る(i.e. $j$が**参入者**, $j \in \mathcal{N}^{\ast}(\boldsymbol{p}^{(k)}))$なら，その買手には何らかの財が割り当てられる．
If buyer $j$ achieves a positive payoff (i.e. $j$ is active; $j \in \mathcal{N}^{\ast}(\boldsymbol{p}^{(k)})$), an item is assigned to $j$.
:::

## 相補性条件と整合するために主変数が満たすべき条件 | The Conditions for Primal Variable for the Complementarity
The following two conditions should be met for a primal solution $\boldsymbol{x}$ to satisfy the complementarity with respect to a given price, $\boldsymbol{p}^{(k)}$:
1. $\pi_{j}(\boldsymbol{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}(\boldsymbol{p}^{(k)}), \quad \forall j \in \mathcal{N}
\end{equation}$$
2. $\pi_{j}(\boldsymbol{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}(\boldsymbol{p}^{(k)})
\end{equation}$$
以上の2つを加えた制約を満足する**主実行可能解**(実行可能な配分)を求める(あるいはそのような配分が存在しないことを判別する)ための**制約つき問題**は， 補助変数$\boldsymbol{z} = \{z_{j} : j \in \mathcal{N}^{\ast}(\boldsymbol{p}^{(k)})\}$を用いて，
The restricted primal problem to find a prime feasible solution (i.e. feasible assignment) is formulated as the following linear programming problem with the above two conditions by using auxiliary variable $\boldsymbol{z} = \left\{z_{j} : j \in \mathcal{N}^{\ast}(\boldsymbol{p}^{(k)})\right\}$:
$$\begin{align}
\text{[RP]} \quad \max_{\boldsymbol{x}, \boldsymbol{z}} &-\sum_{j \in \mathcal{N}^{\ast}(\boldsymbol{p}^{(k)})} z_{j}\\
\text{s.t.} \quad
&\color{red}{\sum_{i \in \mathcal{G}} x_{ij} + z_{j} = 1} && \color{red}{\forall j \in \mathcal{N}^{\ast}(\boldsymbol{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}(\boldsymbol{p}^{(k)}), \forall j \in \mathcal{N} \\
&\color{red}{x_{ij} = 0} && \color{red}{\forall i \not \in \mathcal{G}_{j}^{\ast}(\boldsymbol{p}^{(k)}), \forall j \in \mathcal{N}}\\
&z_{j} \geq 0 && \forall j \in \mathcal{N}^{\ast}(\boldsymbol{p}^{(k)})
\end{align}$$と定式化できる．括弧内はあとで使う双対変数．
The variables in the parentheses are to be used later.

この**制約つき問題**の最適値が0なら，価格$\boldsymbol{p}^{(k)}$の下で最適な配分$\boldsymbol{x}^{\ast}$が実現できる．
最適値が負の場合(つまり，$z_{j} > 0$となるようなものが1つでもある場合)，価格$\boldsymbol{p}^{(k)}$を改訂する必要がある→$\text{[RP]}$の双対問題を使うことで改訂方向が求められる．
Note that the first condition ($\sum_{i \in \mathcal{G}} x_{ij} = 1 \forall j \in \mathcal{N}^{\ast}$) is relaxed by using the auxiliary variable $z_{j}$. When the optimal value of this restricted problem is 0, an feasible (and optimal) assignment $\boldsymbol{x}^{\ast}$ can be achieved under the price $\boldsymbol{p}^{(k)}$. If the optimal value is negative, that is, $z_{j}>0$ for some $j \in \mathcal{N}^{\ast}(\boldsymbol{p}^{(k)})$, we can update the price $\boldsymbol{p}^{(k)}$ by using the dual of the restricted problem $\mathrm{[RP]}$.

## 制約つき双対問題 | Restricted Dual
$\text{[RP]}$の双対問題は以下のように定式化される：
The dual of $\mathrm{[RP]}$ is formulated as follows:
$$\begin{align}
\text{[RD]} \quad \min_{\boldsymbol{\psi}, \boldsymbol{q}} & \sum_{j \in \mathcal{N}^{\ast}(\boldsymbol{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}(\boldsymbol{p}^{(k)}), \forall j \in \mathcal{N} && (x_{ij})\\
& \psi_{j} \geq -1 && \forall j \in \mathcal{N}^{\ast}(\boldsymbol{p}^{(k)}) && (z_{j})\\
& q_{i} \geq 0 && \forall i \in \mathcal{G}
\end{align}$$

この制約付き双対問題$\text{[RD]}$の**実行可能解**$(\boldsymbol{\psi}^{(k)}, \boldsymbol{q}^{(k)})$を，
以下の2つの条件：
By choosing a **feasible solution** to $\mathrm{[RD]}$ that satisfies the following two conditions:
1. 目的関数$\sum_{j \in \mathcal{N}^{\ast}(\boldsymbol{p}^{(k)})} \psi_{j} + \sum_{i \in \mathcal{G}} d_{i} q_{i}$が**負**
The objective $\sum_{j \in \mathcal{N}^{\ast}(\boldsymbol{p}^{(k)})} \psi_{j} + \sum_{i \in \mathcal{G}} d_{i} q_{i}$ is **negative**.
2. $(\boldsymbol{p}^{(k+1)}, \boldsymbol{\pi}^{(k+1)}) = (\boldsymbol{p}^{(k)} + \boldsymbol{q}^{(k)}, \boldsymbol{\pi}^{(k)} + \boldsymbol{\psi}^{(k)})$ が**双対実行可能**
$(\boldsymbol{p}^{(k+1)}, \boldsymbol{\pi}^{(k+1)}) = (\boldsymbol{p}^{(k)} + \boldsymbol{q}^{(k)}, \boldsymbol{\pi}^{(k)} + \boldsymbol{\psi}^{(k)})$ is **dual feasible**.

を満足するように選べれば，現在の解$(\boldsymbol{p}^{(k)}, \boldsymbol{\pi}^{(k)})$より**最適解に「近い」双対実行可能解**$(\boldsymbol{p}^{(k+1)}, \boldsymbol{\pi}^{(k+1)})$が得られる．
a new dual feasible solution $(\boldsymbol{p}^{(k+1)}, \boldsymbol{\pi}^{(k+1)})$ that is closer to the optimal solution than the current solution, $(\boldsymbol{p}^{(k)}, \boldsymbol{\pi}^{(k)})$.

→ **「どの財の価格を上げ(その結果どの買手の利得が下が)ればいいか」**
This is equivalent to find "**Which item should be priced higher (and which buyer should result in lower payoff)?**"

## 財サブ集合(束)の需要と供給 | The Demand and Supply of Item Subset
財集合$\mathcal{G}$のサブ集合$\mathcal{G}^{\prime}$を考える．財集合が$\mathcal{G} = \{A, B, C\}$なら，考えられる「財サブ集合」は以下の通り：
Suppose subsets of items $\mathcal{G}^{\prime} \subseteq \mathcal{G}$. If the item set is $\mathcal{G} = \{A, B, C\}$, the possible "item subsets" are
$$
\{A, B, C\}, \{A, B\}, \{A, C\}, \{B, C\}, \{A\}, \{B\}, \{C\}, \emptyset
$$

:::success
**財サブ集合$\mathcal{G}^{\prime}$の需要量** | Demand for item subset $\mathcal{G}^{\prime}$
価格$\boldsymbol{p}^{(k)}$が与えられたとき，$\mathcal{G}^{\prime}$に**需要集合が含まれる買手の数**:
For a given price $\boldsymbol{p}^{(n)}$, the number of buyers whose demand correspondence is included in $\mathcal{G}^{\prime}$:
$$\begin{equation}
D_{\mathcal{G}^{\prime}}(\boldsymbol{p}^{(k)}):=
\#\left\{j: \mathcal{G}_{j}^{\ast}(\boldsymbol{p}^{(k)}) \subseteq \mathcal{G}^{\prime}\right\}
\end{equation}$$を，$\mathcal{G}^{\prime}$の(価格$\boldsymbol{p}^{(k)}$の下での)**需要量**と呼ぶ．
is referred to as the **demand of subset** $\mathcal{G}^{\prime}$ (under price $\boldsymbol{p}^{(k)}$).
:::

:::success
**財サブ集合$\mathcal{G}^{\prime}$の供給量** | Supply of item subset $\mathcal{G}^{\prime}$
$\mathcal{G}^{\prime}$に含まれる財の供給量の総和
The sum of supplies of items in $\mathcal{G}^{\prime}$:
$$\begin{equation}
S_{\mathcal{G}^{\prime}}:= \sum_{i \in \mathcal{G}^{\prime}} d_{i}
\end{equation}$$を，$\mathcal{G}^{\prime}$の**供給量**と呼ぶ．
is referred to as the **supply of subset** $\mathcal{G}^{\prime}$.
:::

## 超過需要集合と価格競り上げ定理 | Over-demanded Set and Ascending Price Theorem
各財サブ集合に対して**需要量**と**供給量**が与えられれば，以下の**超過需要集合**(正確には「超過需要・財サブ・集合」)が定義できる．
Given the demand and supply of each item subset, we can define the **over-demanded set**:
:::success
**超過需要集合** (over-demanded set)
価格$\boldsymbol{p}^{(k)}$の下で，ある財サブ集合$\mathcal{G}^{\prime}$について，その**需要量が供給量を上回る**:
For a given price $\boldsymbol{p}^{(k)}$, if the demand for an item subset $\mathcal{G}^{\prime}$ exceeds its supply:$$\begin{equation}
D_{\mathcal{G}^{\prime}}(\boldsymbol{p}^{(k)}) > S_{\mathcal{G}^{\prime}}
\end{equation}$$とき，$\mathcal{G}^{\prime}$は **需要超過(over-demanded)** であるという．
$\mathcal{G}^{\prime}$ is referred to as **over-demanded**.
:::
このとき，以下の**価格競上げ定理**が成り立つ(証明は後述)．
In this case, the following **ascending price theorem** is satisfied:
:::success
ある価格$\boldsymbol{p}^{(k)}$の下で， ある超過需要集合$\mathcal{G}^{\prime} \subseteq \mathcal{G}$に含まれる財の価格を**1単位**だけ上げる．すなわち，財価格の増分$\boldsymbol{q}^{(k)} = (q_{i}^{(k)})_{i \in \mathcal{G}}$を
For a given price $\mathbf{p}^{(k)}$, let rise the price of items in an over-demanded set $\mathcal{G}^{\prime} \subseteq \mathcal{G}$ by 1 unit. That is, when the price increment $\boldsymbol{q}^{(k)} = (q_{i}^{(k)})_{i \in \mathcal{G}}$ is denoted by
$$\begin{equation}
{q}_{i}^{(k)} := \begin{cases}1 & \text{if } i \in \mathcal{G}^{\prime}\\
0 & \text{otherwise}
\end{cases}\end{equation}$$
とするとき，新しい価格
the dual solution under new price:
$$
\boldsymbol{p}^{(k+1)} := \boldsymbol{p}^{(k)} + \boldsymbol{q}^{(k)}
$$
の下での解$(\boldsymbol{p}^{(k+1)}, \boldsymbol{\pi}^{(k+1)})$は**双対実行可能**で，$(\boldsymbol{p}^{(k)}, \boldsymbol{\pi}^{(k)})$よりも**最適解に「近い」**(i.e. より小さい目的関数値を実現する)．
$(\boldsymbol{p}^{(k+1)}, \boldsymbol{\pi}^{(k+1)})$ is **dual feasible** as well as is closer to the optimal (i.e. it achieves the smaller objective).
:::

:::warning
上述の価格の改訂幅($q_{i}^{(k)}$の大きさ)は，各買手の**評価値の単位**に合わせる．評価値が10円単位の場合は，価格の改訂は10円ずつ行う．
The unit of price ascending, the magnitude of $q_{i}^{(k)}$, should be fit to the unit of buyers' value. When the unit of buyers' values is 10 JPY, the price updated are also made in 10 JPY increments.
:::

## (主双対)競り上げオークションの手続き | The Procedure of (Primal-Dual) Ascending Auction
以上より，主双対アルゴリズムを活用した競り上げオークションの手続きは，下記のように整理できる：
The procedure of primal-dual ascending auction can be summarized as follows:
- **Step 0** (初期化): **初期価格**を$\boldsymbol{p}^{(1)} = \boldsymbol{0}$とする. $k:=1$.
(initialize): Let the **initial price** be $\boldsymbol{p}^{(1)} = \boldsymbol{0}$. $k:=1$.
- **Step 1** (制約付き問題の構築): 現在の価格$\boldsymbol{p}^{(k)}$の下で，各買手は**需要集合**$\mathcal{G}_{j}^{\ast}(\boldsymbol{p}^{(k)})$を表明する．
(construct the restricted primal): given the current price $\boldsymbol{p}^{(k)}$, each buyer state his/her demand correspondence $\mathcal{G}_{j}^{\ast}(\boldsymbol{p}^{(k)})$.
- **Step 2** (最適性の判別・解の改訂方向の探索): 全ての財サブ集合$\mathcal{G}^{\prime}$について**需要量** $D_{\mathcal{G}^{\prime}}(\boldsymbol{p}^{(k)})$を求め，供給量$S_{\mathcal{G}^{\prime}}$と比較して**超過需要**か否かを判別． **超過需要集合** $\mathcal{G}^{\prime}$が見つかれば，それを**値上げ対象**として**Step 3**へ． どの財サブ集合も超過需要でなければ，**全ての買手の需要を満たす割当** が存在するので，これを**最適割当**として終了．
(optimality test and direction search): For each of all item subsets $\mathcal{G}^{\prime}$, check where if it is **over-demanded** by comparing its demand $D_{\mathcal{G}^{\prime}}(\boldsymbol{p}^{(k)})$ and supply $S_{\mathcal{G}^{\prime}}$.If an **over-demanded set** $\mathcal{G}^{\prime}$ is found, let it be the items set to be higher price and go to **Step 3**. If there is no over-demanded set, a **feasible assignment exists that satisfies all buyers' demand** and it is **optimal**. STOP.
- **Step 3** (解の改訂): 値上げ対象$\mathcal{G}^{\prime}$に含まれる財の価格を**1単位増加**させたものを$\boldsymbol{p}^{(k+1)}$とする．$k:=k+1$として**Step 1**へ．
(solution update): Let $\boldsymbol{p}^{(k+1)} = \begin{cases}p_{i}^{(k)} + 1 & i \in \mathcal{G}^{\prime}\\ p_{i}^{(k)} & \text{otherwise}\end{cases}$ be the next price. Let $k:=k+1$ and back to **Step 1**.

## 主双対競上げオークションの解と VCG価格 | The Solution of PD Auction and The VCG Price
主双対競上げオークションの **Step 2**で要素数が最小の超過需要集合(**最小超過需要集合**, minimum overdemanded set)を選ぶ場合，主双対競り上げオークションで得られる価格は**双対問題の最適解の中で価格が最小となるもの**(i.e. VCG価格)に一致する．
It is known that the prices obtained by the PD auction is equivalent to the **dual optimal solution with minimum price** (i.e. **VCG price**), when the **minimum over-demanded set** (the over-demanded set with minimum number of elements) is chosen in **Step 2**.

## 私的情報の下での主双対オークションの利点 | The Advantages of PD-Auction
- **Step1** の制約付き問題の構築において,管理者が知る必要があるのは 各買手の**需要集合** $\mathcal{G}_{j}^{\ast}(\boldsymbol{p}^{(k)})$だけ．つまり，**私的情報** である 評価値の **観測・推計** が不要.
In **Step 1**, the manager needs to know only the **demand correspondences** $\mathcal{G}_{j}^{\ast}(\boldsymbol{p}^{(k)})$ for each buyer. That is, it does note necessitate observation/estimation of the buyers' value, which is **private information**.
- 各買手$j \in \mathcal{N}$は, 自らの**評価値**$\boldsymbol{v}_{j} = (v_{ij})_{i \in \mathcal{G}}$と，公開されている価格$\boldsymbol{p}^{(k)}$のみに基づいて**需要集合** $\mathcal{G}_{j}^{\ast}(\boldsymbol{p}^{(k)})$を構築できる.
Each buyer $j$ can compute his/her **demand correspondence** $\mathcal{G}_{j}^{\ast}(\boldsymbol{p}^{(k)})$ only based on his own value $\boldsymbol{v}_{j} = (v_{ij})_{i \in \mathcal{G}}$ and the publicly opened price $\boldsymbol{p}^{(k)}$.
- 各買手が **虚偽の需要集合** を申告する**誘引**を持たなければ，最適割当の実現が保証される. → 各買手にとって需要集合を正直に申告することが **Nash 均衡戦略** となることが保証されている.
The efficient assignment, which maximizes the total true value, is guaranteed if each buyer has no incentive to false-telling. That is, for every buyer, the truth-telling is **Nash Equilibrium Strategy**.

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

When the truth-telling is **Nash Equilibrium Strategy** means that "**when every buyer states truth**, no one can achieve a higher payoff by false-telling unilaterally". In contrast, it is noted that the VCG price is **(weak) dominant strategy**: "no one can achieve a higher payoff by false-telling *regardless of* whether other buyers state true or false."
:::

## 価格競上げ定理の証明 | Proof of Ascending Price Theorem
### 証明のアウトライン | Outline of Proof
値上げ対象となる財のサブ集合が$\mathcal{G}^{\prime}$であるときの**価格の変化分** を $\boldsymbol{q} = \{q_{i}: q_{i}=1 \forall i \in \mathcal{G}^{\prime} \text{ and } q_{i}=0 \forall i \not \in \mathcal{G}^{\prime}\}$ とし，
Let $\boldsymbol{q} = \{q_{i}: q_{i}=1 \forall i \in \mathcal{G}^{\prime} \text{ and } q_{i}=0 \forall i \not \in \mathcal{G}^{\prime}\}$ be the increment in the price corresponding to the item subset $\mathcal{G}^{\prime}$ and define
$$\begin{equation}
\psi_{j}(\boldsymbol{q}) = \max_{i \in \mathcal{G}_{j}^{\ast}(\boldsymbol{p}^{(k)})}\left\{ - q_{i}\right\} \quad
\Leftrightarrow \quad
\psi_{j}(\boldsymbol{q}) = \begin{cases}
-1 & \text{if } \mathcal{G}_{j}^{\ast}(\boldsymbol{p}^{(k)}) \subseteq \mathcal{G}^{\prime}\\
0 & \text{otherwise}
\end{cases}
\end{equation}$$と定義する．この式は，価格変化に伴う **参入者** $j \in \mathcal{N}^{\ast}(\boldsymbol{p}^{(k)})$の **最大利得の変化分** と解釈できる． すなわち，価格$\boldsymbol{p}^{(k)}$の下で，**需要する「全ての財」の価格が上がった時に限り，1単位減少する**．
$\psi_{j}(\boldsymbol{q})$ can interpreted as the increment in the maximum payoff of active buyer $j \in \mathcal{N}^{\ast}(\boldsymbol{p}^{k})$. The second equation implies that the maximum payoff of active buyer $j$ decreases by 1 unit *only when* the prices of all items that he/she demands are raised.

The detailed proof is unnecessary long to understand the advantages of the PD auction, and thus would be translated according to the interest of foreign students.

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

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

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

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

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

次に，目的関数の第2項は，
$$\begin{equation}
\boldsymbol{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}}(\boldsymbol{p}^{(k)}) > S_{\mathcal{G}^{\prime}}$ であれば，**$\text{[RD]}$の目的関数は負**である． $\square$

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

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

まず，$\boldsymbol{p}^{(k)}, \boldsymbol{q} \geq \boldsymbol{0}$ より，$\boldsymbol{p}^{(k+1)} = \boldsymbol{p}^{(k)} + \boldsymbol{q} \geq \boldsymbol{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$)場合のそれぞれについて，新しい解$(\boldsymbol{p}^{(k+1)}, \pi_{j}^{(k+1)})=(\boldsymbol{p}^{(k)}+\boldsymbol{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}(\boldsymbol{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}(\boldsymbol{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)}$ が成り立つ．

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

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