---
lang: ja
tags: OptMech-2021, lecture
---
# 2021年度 知的システム<br>第11回：割当問題とオークション(3) VCGメカニズム
[ポータルへ戻る](https://hackmd.io/@nagae/OptMech_2021)
<div style="text-align: center">

このページへは以下のQRコードまたはURLからアクセスできます：
<code style="font-size:20pt">https://hackmd.io/@nagae/OptMech_2021-Ch10</code>
</div>

# VCG (*Vickrey-Clarke-Groves*) メカニズム
## Vickrey-Clarke-Groves 価格
オークションに参加する各買手にとって，自らの**真の評価値**を申告することが **(弱)支配戦略(weakly dominant strategy)** となるような価格として知られる．

:::info
**弱支配戦略**: 他の買手の申告によらず，**虚偽の申告**によって**自らの利得を改善できない**.
:::
なお，「虚偽の申告をすると常に**利得が減少する**場合」は，正直申告が(弱のつかない)**支配戦略**であると言う．

提案者である William **V**ickrey, Edward H. **C**larke および Theodore **G**roves の頭文字をとって，**VCG価格**と呼ばれている．
- William Vickrey は交通渋滞を表現するボトルネック・モデルの始祖としても有名．1996年にNobel経済学賞を受賞．
- Clarke-Groves 税は公共政策で使われる．研究室に$M$ 万円のコーヒーマシンを導入したい．支払い意思額を低く入札する **ただ乗り(free-ride)** をさせないための支払いルール．「各学生は支払い意思額$b_{j}$を入札する．入札額の合計$\sum_{j} b_{j}$が$M$以上となったらコーヒーマシンを購入する．その場合，学生$l$が実際に支払う金額は，導入費用と彼以外の入札額の合計の差(負になった場合は0)とする: $\max\left\{M-\sum_{j \ne l}b_{j}, 0\right\}$．

## VCG価格の計算方法
### 買手サブ集合に対する割当問題
- $v_{j}(\mathbf{x}) = \sum_{i \in \mathcal{G}} v_{ij}x_{ij}$: ある割当 $\mathbf{x} = \{x_{ij}\}$ の下で買手$j$が得る評価値．
- $\mathbf{x}^{\ast}(\hat{\mathcal{N}})$: ある買手サブ集合$\hat{\mathcal{N}} \subseteq \mathcal{N}$に対する割当問題の最適解(最適割当):
$$
\begin{align}
V^{\ast}(\hat{\mathcal{N}}) = \max_{\mathbf{x}} &\sum_{j \in \color{red}{\hat{\mathcal{N}}}} v_{j}(\mathbf{x})\\
\text{s.t.} &
\sum_{i \in \mathcal{G}} x_{ij} \leq 1 \qquad \forall j \in \color{red}{\hat{\mathcal{N}}}\\&
\sum_{j \in \color{red}{\hat{\mathcal{N}}}} x_{ij} \leq d_{i}\qquad \forall i \in \mathcal{G}\\&
x_{ij} \in \{0, 1\}\qquad \forall (i,j) \in \mathcal{G} \times \color{red}{\hat{\mathcal{N}}}
\end{align}
$$
## ある買手$l$ のVCG価格
- $\hat{\mathcal{N}} = \mathcal{N}$なら元の割当問題に一致する．この時の最適割当および最適値を，それぞれ，以下のように表す：
$$\begin{align}
\mathbf{x}^{\ast} &= \mathbf{x}^{\ast}(\mathcal{N})\\
V^{\ast} &= V^{\ast}(\mathcal{N})\\
&= \sum_{j \in \mathcal{N}} v_{j}(\mathbf{x}^{\ast})\end{align}$$
- ある買手 $l\in \mathcal{N}$ について，**それ以外の買手**からなるサブ集合$\mathcal{N}\setminus\{l\}$に対する最適割当および最適値を，それぞれ，以下のように定義する：
$$\begin{align}
\mathbf{x}_{-l}^{\ast} &= \mathbf{x}^{\ast}\left(\mathcal{N}\setminus\{l\}\right), \\
V_{-l}^{\ast} &= V^{\ast}\left(\mathcal{N}\setminus\{l\}\right) \\
%&=
%\sum_{j \in \mathcal{N}\setminus\{l\}} %v_{j}^{\ast}\left(\mathcal{N}\setminus\{l\}\right)\\
&= \sum_{j \ne l} v_{j}^{\ast}(\mathbf{x}_{-l}^{\ast})
\end{align}$$
- このとき，買手$l$ のVCG価格 $p_{l}$ は，以下の2つの項の差で与えられる：
1. **買手 $l$ が不在の集合** $\mathcal{N}\setminus\{l\}$ における割当問題の最適値:
$$\begin{equation}V_{-l}^{\ast} = \sum_{j \ne l} v_{j}(\mathbf{x}_{-l}^{\ast})\end{equation}$$
2. 全買手集合に対する最適割当における**買手$l$以外**の総評価値:
$$\begin{equation}V^{\ast} - v_{l}(\mathbf{x}^{\ast}) = \sum_{j \ne l} v_{j}(\mathbf{x}^{\ast})\end{equation}$$

具体的には，買手$l$が支払うべき**VCG価格**は，以下の式で表される：
$$\begin{align}
p_{l} &= V_{-l}^{\ast} -\left\{V^{\ast} - v_{l}^{\ast}\left(\mathbf{x}^{\ast}\right)\right\}\\
&= \underbrace{\sum_{j \ne l} v_{j}(\mathbf{x}_{-l}^{\ast})}_{\text{買手$l$がいない時の総評価値}}
-\underbrace{\sum_{j \ne l} v_{j}(\mathbf{x}^{\ast})}_{\text{買手$l$以外の総評価値}}
\end{align}$$

# VCG価格の特徴
## 買手の市場参入による"迷惑料"としての解釈
買手$l$ のVCG価格
$$\begin{align}
p_{l} &= \sum_{j \ne l}
\left\{
v_{j}(\mathbf{x}_{-l}^{\ast}) - v_{j}(\mathbf{x}^{\ast})
\right\}
\end{align}$$
- $v_{j}(\mathbf{x}_{-l}^{\ast}) - v_{j}(\mathbf{x}^{\ast})$ は，買手集合が $\mathcal{N}\setminus\{l\}$から$\mathcal{N}$に変化した(i.e. 買手$l$が**市場に参入**した)時の**買手$j$の評価値の減少分**
- 買手$l$の**VCG価格**は，買手$l$が**市場に参入**することで**他の買手が失った評価値の総和**(===**迷惑料**==)に等しい．

## VCG価格の下で買手が得る利得の"限界生産"としての解釈
VCG価格の下での買手$l$の利得(i.e. 買手$l$が得る評価値$v_{l}(\mathbf{x}^{\ast})$からVCG価格$p_{l}$引いたもの)：
$$\begin{align}
\pi_{l} &= v_{l}(\mathbf{x}^{\ast}) - p_{l}\\
&= v_{l}(\mathbf{x}^{\ast}) - \sum_{j\ne l}
\left\{
v_{j}(\mathbf{x}_{-l}^{\ast}) - v_{j}(\mathbf{x}^{\ast})
\right\}\\
&= v_{l}(\mathbf{x}^{\ast}) + \sum_{j\ne l} v_{j}(\mathbf{x}^{\ast}) - \sum_{j \ne l} v_{j}(\mathbf{x}_{-l}^{\ast})\\
&= V^{\ast} - V_{-l}^{\ast}
\end{align}$$
買手$l$の利得は，買手$l$が**市場に参入**することによる**総評価値の増分**(===**限界生産**==)に等しい．

# 2財3人の例
下記のケースでVCG価格を計算してみよう．

| |買手1|買手2|買手3|供給量|
|---|---|---|---|--|
|財$A$| 70 | 30 | 40|1|
|財$B$|60 | 20 | 10 |1|

1. **全買手集合**に対する最適配分と総評価値:
$\mathbf{x}^{\ast}=(x_{A3}=1,x_{B1}=1)$
$V^{\ast} = 100$.
| |買手1|買手2|買手3|
|---|---|---|---|
|財$A$| 70 | 30 | <div style="background-color:orange">40</div>|
|財$B$|<div style="background-color:orange">60</div> | 20 | 10 |

あとで使うことになるので，いまのうちに下記を計算しておこう：
- **買手1以外**の総評価値: $V^{\ast} -v_{1}(\mathbf{x}^{\ast}) = 100-60=40$
- **買手3以外**の総評価値: $V^{\ast} -v_{3}(\mathbf{x}^{\ast}) = 100-40=60$

2. **買手1が不在の場合**の最適配分と総評価値
$\mathbf{x}_{-1}^{\ast}=(x_{A3}=1,x_{B2}=1)$
$V^{\ast}_{-1} = 60$.
| |~~買手1~~|買手2|買手3|
|---|---|---|---|
|財$A$| ~~70~~ | 30 | <div style="background-color:orange">40</div>|
|財$B$|~~60~~ | <div style="background-color:orange">20</div> | 10 |

4. 買手1のVCG価格
- **買手1が不在時**の総評価値： $V_{-1}^{\ast} = 60$
- **買手1以外**の総評価値: $V^{\ast}-v_{1}(\mathbf{x}^{\ast}) = 40$

だから， $p_{1} = 60-40=20$.

この金額は，**買手1が市場に参入**することで**買手2が失う評価値**(20)に等しい．

買手1の利得$\pi_{1} = 60-20=40$ は，**買手1が市場に参入**することによる総評価値の増分$V^{\ast}-V_{-1}^{\ast}= 100-60=40$に等しい．

3. 買手3が不在の場合の最適配分と評価値
$\mathbf{x}_{-3}^{\ast}=(x_{A1}=1,x_{B2}=1)$または$(x_{A2}=1,x_{B1}=1)$
$V^{\ast}_{-3} =90$.
| |買手1|買手2|~~買手3~~|
|---|---|---|---|
|財$A$| <div style="background-color:orange">70</div> | 30 | ~~40~~|
|財$B$|60 | <div style="background-color:orange">20</div> | ~~10~~ |

| |買手1|買手2|~~買手3~~|
|---|---|---|---|
|財$A$| 70 |<div style="background-color:orange"> 30</div> | ~~40~~|
|財$B$|<div style="background-color:orange">60</div> | 20 | ~~10~~ |

5. 買手3のVCG価格
- **買手3が不在時**の評価値： $V_{-3}^{\ast} = 90$
- **買手3以外**の評価値: $V^{\ast}-v_{3}(\mathbf{x}^{\ast}) = 60$

だから，$p_{3} = 90-60=30$.

この金額は,**買手3が市場に参入**することで**買手1と買手2が失う評価値の和**(30)に等しい

買手3の利得$\pi_{3} = 40-30=10$ は，**買手3が市場に参入**することによる総評価値の増分$V^{\ast}-V_{-3}^{\ast}= 100-90=10$に等しい．

# VCG価格の誘引整合性
上記 VCG価格の最大のメリットを端的に表現すると，「合理的な買手なら誰でも，**自分の評価値を正直に申告する**こと」ことにある．より正確に言うと，VCG価格には「虚偽の申告によってより高い利得を得ることはできない」という仕組み(メカニズム)が備わっている．このような性質を **誘引整合性(incentive compatibility)** という．
## 直感的な説明

買手1が支払うVCG価格は，下記の2つの評価値：
- **買手1不在時**の評価値: 60(下図中の青い棒)
- (最適配分における)**買手1以外**の評価値: 40 (下図中の赤い棒)

の差 20 (下図中の緑の棒)．
<div style="text-align:center">

</div>

従って，買手1が支払い(緑の棒)を減らすためには，
1. **買手1が不在時**の評価値(青い棒)を**短くする**
2. **買手1以外**の評価値(赤い棒)を**長くする**

かしかない． このうち，前者は「自分が不在時の配分」によって決まるため，**買手1はコントロールできない**． 一方，後者は，「自分以外の評価値を増やす」ことは「**自分が得る評価値を減らす**」ことを意味している(最適配分における総評価値は一定であるため)．言い換えれば，買手1以外の評価値が増えた分，買手1の支払いは減るが，得られる評価値も同じだけ減り，その差である利得は変わらない．

同じことは，どの買手にも当てはまる．このため，**虚偽を申告をすることでは，より高い利得は得られない**．

## 数理的証明
:::info
VCG価格の下では， 各買手は，自らの評価値を**正直に表明する** ことが **(弱)支配戦略**となる. すなわち，各買手 $l \in \mathcal{N}$は ==他の買手がどんな評価値を申告しているかに関わらず==自らの評価値 $\mathbf{v}_{l} := \{v_{il} : \forall i \in \mathcal{G}\}$ を正直に入札したときより高い利得を得ることはできない．
:::

これを証明するために，以下の記号を導入しよう：
- $\mathbf{b}_{l} := \{b_{il} : i \in \mathcal{G}\}$: 買手 $l$ の各財への申告額
- $\mathbf{b}_{−l} :=\{b_{ij} :(i,j) \in \mathcal{G}×(\mathcal{N}\setminus\{l\})\}$: 買手 $l$ 以外の各財への申告額(買手$l$ の行動とは無関係に決まる)
- $\mathbf{x}^{\ast}$: 買手 $l$ が自らの(真の評価値を)**正直に申告** した時の**最適配分**(i.e. 申告された評価値 $(\mathbf{v}_{l}, \mathbf{b}_{−l})$ の総和を最大化する配分)
- $\mathbf{y}^{\ast}$: 買手 $l$ が**虚偽の申告**をした時の**最適配分**(i.e. 申告された評価値 $(\mathbf{b}_{l}, \mathbf{b}_{−l})$ を最大化する配分)
- $\mathbf{x}^{∗}_{−l}$: 買手$l$ が不在の市場 $\mathcal{J} \setminus \{l\}$ における**最適配分**(i.e. $l$ 以外が申告した評価値$\mathbf{b}_{-l}$の総和を最大化する配分)

ここで, **正直な申告**の下での配分$\mathbf{x}^{∗}$ は，目的関数
$$\begin{equation}
\sum_{i} v_{i{\color{red}l}}x_{i{\color{red}l}} + \sum_{i}\sum_{j \ne {\color{red}l}} b_{ij} x_{ij}
\end{equation}$$
を最大化するから，任意の配分$\mathbf{y}$について，以下が成り立つ：
$$\begin{equation}
\sum_{i} v_{i{\color{red}l}}x_{i{\color{red}l}}^{\ast} + \sum_{i}\sum_{j \ne {\color{red}l}} b_{ij} x_{ij}^{\ast}
\geq
\sum_{i} v_{i{\color{red}l}}y_{i{\color{red}l}} + \sum_{i}\sum_{j \ne {\color{red}l}} b_{ij} y_{ij}
\end{equation}$$

買手 $l$ が**正直に申告した場合**の配分$\mathbf{x}^{\ast}$と，**虚偽を申告した場合**の配分 $\mathbf{y}^{\ast}$のそれぞれについて，この買手が得る利得は，
$$\begin{align}
\pi_{{\color{red}l}}(\mathbf{x}^{\ast}) &= \sum_{i} v_{i{\color{red}l}} x_{i{\color{red}l}}^{\ast} - \underbrace{\left(
-\sum_{j \ne l} b_{j}(\mathbf{x}^{\ast}) + \sum_{j \ne {\color{red}l}} b_{j}(\mathbf{x}_{-{\color{red}l}}^{\ast})\right)}_{\text{$\mathbf{x}^{\ast}$の下での買手$l$のVCG価格}}\\
\pi_{{\color{red}l}}(\mathbf{y}^{\ast}) &= \sum_{i} v_{i{\color{red}l}}
y_{i{\color{red}l}}^{\ast} - \underbrace{\left(-
\sum_{j \ne {\color{red}l}} b_{j}(\mathbf{y}^{\ast}) + \sum_{j \ne {\color{red}l}} b_{j}(\mathbf{x}_{-{\color{red}l}}^{\ast})\right)}_{\text{$\mathbf{y}^{\ast}$の下での買手$l$のVCG価格}}
\end{align}$$
と表される． ただし，$b_{j}(\mathbf{x}) = \sum_{i} b_{ij} x_{ij}$は，配分 $\mathbf{x}$ の下で買手 $j$ が得る(申告額ベースの)評価値である． ==買手 $l$ にとっては，他の買手が獲得するのが真の評価値であろうが，虚偽の評価値であろうが関係ない==．

どちらの式も右辺第3項が同じであるため，**正直な申告**と**虚偽の申告**の利得の差は，
$$\begin{align}
\pi_{{\color{red}l}}(\mathbf{x}^{\ast}) - \pi_{{\color{red}l}}(\mathbf{y}^{\ast})
&=\left\{\sum_{i} v_{i{\color{red}l}} x_{i{\color{red}l}}^{\ast} +
\sum_{i}\sum_{j \ne {\color{red}l}} b_{ij}x_{ij}^{\ast}\right\} -
\left\{\sum_{i} v_{i{\color{red}l}}
y_{i{\color{red}l}}^{\ast} +
\sum_{i} \sum_{j \ne {\color{red}l}} b_{ij}y_{ij}^{\ast}\right\}
\\
&\geq 0
\end{align}$$
となる．ただし，最後の不等式は，上述した$\mathbf{x}^{\ast}$の最適性より導かれる．

従って， 買手$l$ は，いかなる評価値$\mathbf{b}_{l}$ を申告しようと，正直な申告(i.e. $\mathbf{b}_{l} = \mathbf{v}_{l}$)をした時以上の利得を獲得することはできない．

$\square$

# VCG価格の長所と短所
VCG価格に対しては，下記の**長所**と**短所**が指摘されている(Ausbel and Milgrom, 2005)．
## 長所
1. **正直な申告**が **支配戦略** となる．
2. マイルドな仮定の下で以下の3つの重要な要素を実現できる ==**唯一**== の**直接表明メカニズム**である:
a. **正直申告**が**支配戦略**となる.
b. **効率的配分**が実現できる(i.e. 真の評価値の総和を最大化する).
c. **敗者の支払いが不要**である．
3. **組み合わせオークション**を含む，**より一般的な枠組**へも適用可能

## 短所
1. ルールが判り難く, 大規模に なると VCG **価格の計算** が 大変(i.e. (勝者の数+1)個の割当問題を解く必要がある)
2. **売手の収益**が **極めて低い**, もしくは**ゼロ**になる
3. **売手の収益**が**買手集合**や**買手の入札額**に対して**単調ではない**
4. **敗者同士の提携** や**匿名入札**(1人の買手が別人になりすます)に対して頑健でない

ただし，2〜4は買手が代替的(buyers are substitute)であれば(e.g. 単一需要)生じない．

さらに，残った1つ目の短所についても，**線形計画問題**に帰着する**割当問題**ならば，解決可能．

# VCG価格と双対問題の最適解
:::info
**割当問題**において，各買手が各財に対して支払う**VCG 価格**は**双対問題の最適解** $(\mathbf{p}^{\ast},\mathbf{π}^{\ast})$の中で**最小の価格**に一致する. (Demange et al., 1986)
:::

**VCG 価格**を **定義通り** に求めるには,
- **最適割当**を求める問題
- 財を割当てられた買手(勝者)ごとのVCG価格を求める問題

を解かなければならない. 勝者 (=財の供給量) が $N′$ なら $N′ + 1$ 個の 割当問題 を解く必要がある.

一方，**割当問題** が **線形計画問題** に帰着する場合, 双対問題を **一度** 解くだ けで以下が全て計算できる:
- 各買手の**VCG価格**(最適解として求められる)
- **最適割当** (**相補性定理** から計算できる)

前々回の講義で紹介した**競り上げオークション**は，**最適配分**と**VCG価格**(=等価な線形双対問題の解)を**同時**に求められる**間接顕示**(各買手の評価値を直接申告させることのない)メカニズムとして位置付けられる(Demange et al., 1986; Bikhchandani and Ostroy, 2002,2006; de Vries et al., 2007).

# 練習問題
第9回の講義で扱った下記の問題について，
1. 学生1, 学生4, 学生5が支払うべき**VCG価格**を求めよ．なお，学生4にソーダが配分される場合と，コーラが配分される場合ではVCG価格は異なる．それぞれの場合についてVCG価格を求めよ．
2. 割当問題を線形計画問題に帰着させた場合の**双対問題の解** $(\mathbf{p}, \mathbf{\pi})$を求め，上記1.の解と比較せよ．

||学生1|学生2|学生3|学生4|学生5|学生6|供給量|
|---|---|---|---|---|---|---|---|
|ソーダ($S$)|100|60|90|120|150|110|3|
|コーラ($C$) |30|60|40|70|100|50|2|

# 参考文献
- Ausubel, L. M. and Milgrom, P. “Lovely but Lonely Vickrey Auction,” In Cramton, P., Shoham, Y., and Steinberg, R. eds. *Combinatorial Auctions*. The MIT Press 2005.
- Bikhchandani, S. and Ostroy, J. “Ascending price Vickrey auctions,” *Games and Economic Behavior*, 55 (2), pp. 215–241 2006.
- Bikhchandani, S. and Ostroy, J. M. “The Package Assignment Model,” *Journal of Economic Theory*, 107 (2), pp. 377–406 2002.
- 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.