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

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

# 背景 - 交通問題とオークション
## 私的情報と社会的意思決定
- 線形計画問題をはじめとする**最適化**は**資源の効率的配分**に他ならない
- 都市計画や大規模感染症対策などの**社会的意思決定問題**に適用する際には注意が必要
- しばしば，社会を構成する個々の主体の**私的情報**をモデルの入力として与える必要がある(e.g. 目的関数, 制約条件)
- 社会的調査によって私的情報を推計する方法はいろいろある([Ben-Akiba and Morikawa](https://www.sciencedirect.com/science/article/pii/0191260790900377); [Louviere et al, 2000](https://www.researchgate.net/publication/215666083_Stated_choice_methods_analysis_and_application); [Sanko,2021](https://www.b.kobe-u.ac.jp/~sanko/pub/Sanko2001_1.pdf); [Train and Wilson, 2008](https://eml.berkeley.edu/~train/spoffrp.pdf))
- どんなに頑張って最適な戦略を求めたとしても，**入力としての私的情報が間違っていたら**社会にとって**望ましくない結果**をもたらし得る．
(c.f. バス路線の設計→各バス停間の時刻別の需要を正確に把握できるか?)
- **私的情報の観測・推計誤差**に ==**頑健な**== 意思決定(c.f. ロバスト最適化)や， **私的情報の観測・推計** そのものを ==**必要としない**== 意思決定(c.f. **メカニズム設計**)へのパラダイム・シフトが必要

## メカニズム設計とは
- ミクロ経済学/ゲーム理論をベースとした，私的情報下での **工学的** な **問題解決手法**
- 経済学の本質は **資源の効率的配分**:
:::info
**厚生経済学の第1定理**: **完全競争市場** において実現する資源配分は **Pareto効率的** である．
:::
Pareto効率: 集団に対する資源配分が Pareto 効率的であるとは，その集団内の誰かの効用を犠牲にしなければ，別の誰かの効用を高められない(=資源が最大限に活用されている)とき．
- **完全競争市場** ではない局面(e.g. 外部性や私的情報が存在)で，市場に代わるメカニズムや制度を設計する．

## 実問題への適用例
### 周波数オークション
- 周波数帯域の各通信業者への割当を **オークション** で決定
- 米国('93〜'94) FCC (*Federal Communications Commision*; 米国連邦通信委員会) 主導で開催
- 2021年12月時点では，日本は未導入．
- 関連記事
- [安田先生の解説記事](https://note.com/yagena/n/nbd7f4c70394c)
- [Auction 107 | FCC](https://auctiondata.fcc.gov/public/projects/auction107)
- https://www.cnbc.com/2021/02/24/verizon-commits-more-than-45-billion-to-5g-spectrum-bid.html
- https://www.nikkei.com/article/DGXZQOUC307K60Q1A131C2000000/

### 英国バス路線オークション
- ロンドン交通局(TfL:*Transport for London*)では，バス路線の運営を民間企業に委託することで，サービスの安定化・効率化を図っている．
- '85年から，毎年，一部の路線について，それぞれの運営会社を入札によって選んでいる．
- 1つの契約は5〜7年で， 契約期間中の運行距離,信頼性,運転手・車両の品質, 顧客満足度, 法令遵守, 安全性などが厳しく評価される.
- 関連記事
- [Bus tender search | TfL](https://tfl.gov.uk/forms/13923.aspx)
- [London's Bus Contracting and Tendering Process | TfL ](http://content.tfl.gov.uk/uploads/forms/lbsl-tendering-and-contracting.pdf)
- Amaral, M., Saussier, S. and Yvrande-Billon, A.: Expected Number of Bidders and Winning Bids: Evidence from the London Bus Tendering Model, *Journal of Transport Economics and Policy*, 47(1), pp. 17-34, 2013.9 https://www.jstor.org/stable/24396350
- Kennedy, D. London bus tendering: an overview, *Transport Reviews*, 15(3), pp. 253-264, 1995.
[DOI: 10.1080/01441649508716915](https://www.tandfonline.com/doi/abs/10.1080/01441649508716915)
- [Privatisation of London bus services (WiKi)](https://en.wikipedia.org/wiki/Privatisation_of_London_bus_services)

# 割当問題とオークション
## 問題設定
- 夏の暑い日を想像しよう． 研究室の冷凍庫にガリガリ君(R)のソーダ味($S$)が3本，コーラ味($C$)が2本あるとする．
- 研究室には，好みの違う6人の学生がいる． 誰にどの味を割り当てるのが最適か?
- 学生の集合: $\mathcal{N} = \{1, 2, 3, 4, 5, 6\}$
- 財(ガリガリ君)の集合: $\mathcal{G} = \{S, C\}$
- 財の供給量: $(d_{S}, d_{C}) = (3, 2)$.

学生$j \in \mathcal{N}$の財$i \in \mathcal{G}$に対する好み(を金銭換算したもの)を ==**評価値**== $v_{ij}$ で表すことにする． ここでの評価値は， 以下のいずれとしても解釈できる．
- **支払い意思額** (willingness to pay): その財を取得するために支払ってもよいと思う最大の金額
- **留保価格** (reservation price): その財の価格がそれを超えたら取得を諦める(留保する)金額

例えば，各学生の評価値が以下のように与えられるとしよう．
||学生1|学生2|学生3|学生4|学生5|学生6|
|---|---|---|---|---|---|---|
|ソーダ($S$)|100|60|90|120|150|110|
|コーラ($C$) |30|60|40|70|100|50|

- 学生$j \in \mathcal{N}$の評価値$\mathbf{v}_{j}=\{v_{ij}: i \in \mathcal{G}\}$は，その学生しか知らない(**私的情報**である)とする．
- 各学生には高々1つのアイスしか割り当てられないものとする．

アイスを割り当てられた学生の**評価値の合計が最大となる**ようにするには，誰にどのアイスを割り当てればよいだろう?

## 解法(1): 中央集権的なアプローチ
アイス割当問題を解く一つの方法は，研究室で絶大な権力を誇る誰か（教授ではなく秘書さんだったりする）が，全ての学生の評価値を聞き出し，それに基づいて**中央集権的に**配分を決める方法である．

財$i \in \mathcal{G}$の学生$j \in \mathcal{N}$への配分を変数$x_{ij}$で表すことにしよう． 財$i$が学生$j$に配分されるなら$x_{ij}=1$, そうでないときは$x_{ij}=0$とする．

この時， 割り当て問題は下記の**二値線形計画問題**(*BLP: binary linear programming*)として定式化できる．
$$
\begin{alignat}{3}
\max_{\mathbf{x}} &\sum_{j \in \mathcal{N}} \sum_{i \in \mathcal{G}} v_{ij} x_{ij} \\
\text{s.t.} & \sum_{i \in \mathcal{G}} x_{ij} \leq 1 && \forall j \in \mathcal{N} && \text{(各学生には高々1つの財しか割り当てられない)}\\
& \sum_{j \in \mathcal{N}} x_{ij} \leq d_{i} && \forall i \in \mathcal{G} && \text{(各財は供給量まではしか割り当てられない)}\\
& x_{ij} \in \{0, 1\} && \forall i \in \mathcal{G} , \forall j \in \mathcal{N}
\end{alignat}
$$

この問題は，**二値制約** (binary constraint) $x_{ij} \in \{0, 1\}$があるため，本来ならば解くのが大変な問題である． ところが，割当問題の場合， この二値制約を緩和した下記の**線形計画問題**：
$$
\begin{alignat}{3}
\max_{\mathbf{x}} &\sum_{i \in \mathcal{N}} \sum_{j \in \mathcal{G}} v_{ij} x_{ij} \\
\text{s.t.} & \sum_{i \in \mathcal{G}} x_{ij} \leq 1 && \forall j \in \mathcal{N} && \text{(各学生には高々1つの財しか割り当てられない)}\\
& \sum_{j \in \mathcal{N}} x_{ij} \leq d_{i} && \forall i \in \mathcal{G} && \text{(各財は供給量まではしか割り当てられない)}\\
& \color{red}{x_{ij} \geq 0} && \forall i \in \mathcal{G} , \forall j \in \mathcal{N}
\end{alignat}
$$
の解が，もとの二値線形計画問題の解に ==**必ず一致する**ことが保証されている==．

この線形計画問題の最適解は
$$
x_{S, 1} = x_{S, 4} = x_{S, 6} = x_{C, 2} = x_{C, 5} = 1
$$
であり，その時の最適値は490となる． 評価値の表に配分を重ねてみる：

||学生1|学生2|学生3|学生4|学生5|学生6|
|---|---|---|---|---|---|---|
|ソーダ($S$)|<div style="background-color:orange">100</div>|60|90|<div style="background-color:orange">120</div>|150|<div style="background-color:orange">110</div>|
|コーラ($C$) |30|<div style="background-color:orange">60</div>|40|70|<div style="background-color:orange">100</div>|50

なお，学生4と学生5への配分を入れ替えても，全く同じ最適値490が実現する．これもまた最適解である：
||学生1|学生2|学生3|学生4|学生5|学生6|
|---|---|---|---|---|---|---|
|ソーダ($S$)|<div style="background-color:orange">100</div>|60|90|120|<div style="background-color:orange">150</div>|<div style="background-color:orange">110</div>|
|コーラ($C$) |30|<div style="background-color:orange">60</div>|40|<div style="background-color:orange">70</div>|100|50

## 解法(2): 競上げオークションによるアプローチ
上述の中央集権的アプローチは， 各学生の全ての評価値を正確に聞き出せなければ適用できない（秘書さんが極めて有能なら可能かもしれないが）．そこで，**私的情報**を ==直接聞き出すことなく== 全く同じ配分を実現する方法として，**競り上げオークション**を導入してみよう．

オークションは，下記の手続きで進められる：
- 競売人が各財に価格 $\mathbf{p}=(p_{S}, p_{C})$ を提示する． 初期価格は $\mathbf{p} = (0,0)$ とする．
- 各学生 $j \in \mathcal{N}$ は， 提示された価格をもとに，各財について**利得**(=自分の評価値と価格の差) $v_{ij} - p_{i}$ を計算する．
- 各学生 $j \in \mathcal{N}$ は，利得が最大となる(希望する)財を**表明**する． 希望する(利得が最大となる)財が複数あるなら，その**全て**を表明する． 表明する財の集合を $\mathcal{R}_{j}(\mathbf{p})$ で表す． **利得が0以下となる場合**には表明を行わず($\mathcal{R}_{j}(\mathbf{p}) = \emptyset$)， ==オークションから離脱する==．
- 価格が $(p_{S}, p_{C}) = (0, 0)$ であるとき， 学生1が希望する(利得が最大となる)のはソーダ味だけなので，$\mathcal{R}_{1}((0,0)) = \{S\}$.
- 価格が $(70, 0)$ の場合，ソーダ味もコーラ味も利得が30で**無差別(indifferent)** なので，希望する財全て$\mathcal{R}_{1}((70,30)) = \{S, C\}$を表明する.
- 価格が$(80, 0)$ の場合， コーラ味だけを希望するので $\mathcal{R}_{1}((80, 0)) = \{C\}$.
- 価格が$(130, 50)$ の場合，どちらの財も利得が負になるので $\mathcal{R}_{1}((130,50)) = \emptyset$ としてオークションから離脱．
- 競売人は， 財の**束**(bundle) $\{S\}, \{C\}, \{S, C\}$のそれぞれに対して**需要**(その財の束の中に表明した財が含まれる人数)を計算し， それを**供給**（組み合わせに含まれる財の供給数の総和）と比較する．
- 例1) 初期価格$\mathbf{p} = (0,0)$ の下では， 学生2は「ソーダまたはコーラ(ソーダとコーラが無差別)」を希望し，それ以外が「ソーダのみ」を希望するので，各財の束の需要と供給は以下のように整理できる：
|財の束|需要|供給|
|---|---|---|
|ソーダのみ$\{S\}$|5|3||
|コーラのみ$\{C\}$| 0 | 2|
|ソーダまたはコーラ$\{S,C\}$| 6| 5 |

注意：
- コーラのみを表明している学生はいないため，$\{C\}$への需要が0となっている
- 「ソーダもしくはコーラ」に対する需要は「ソーダのみ」を表明した5名と「ソーダとコーラ」を表明した1名の合計で6名となる．
- 例2) 価格が$\mathbf{p} = (90,40)$の場合， 各学生の各財に対する利得と表明する財は以下の表の通りになる:
||学生1|学生2|学生3|学生4|学生5|学生6|
|---|---|---|---|---|---|---|
|ソーダ($S$)|10|-30|0|30|60|20|
|コーラ($C$) |-10|20|0|30|60|10|
|希望する財|$\{S\}$|$\{C\}$|$\emptyset$|$\{S,C\}$|$\{S,C\}$|$\{S\}$|

学生3は，ソーダとコーラが無差別だが，その利得が正ではないため，希望を表明せずオークションから離脱していることに注意．

このときの各財の束への需要と供給は以下の通り:
|財の束|需要|供給|
|---|---|---|
|ソーダのみ$\{S\}$|2|3||
|コーラのみ$\{C\}$| 1 | 2|
|ソーダまたはコーラ$\{S,C\}$| 5 | 5 |

注意：
- 「ソーダまたはコーラ」の需要は「ソーダのみ」を表明した2名，「コーラのみ」を表明した1名，「ソーダまたはコーラ」を表明した2名の合計で5名．
- 競売人は，需要が供給を上回っている(需要過多・供給不足)財の束のうち，最も要素数の小さいものの価格を1単位(ここでは10円)上げる． そのような財の束が無い場合， オークションに残っている全員に，表明した財（複数の場合はそのいずれか）を割当てることができる．
- 上述の例1)では，「ソーダのみ$\{S\}$」については，需要5に対して供給が3であるため，需要が供給を上回っている．同様に，「ソーダまたはコーラ$\{S,C\}$」についても需要6に対して供給が5であるため，需要過多(供給不足)である．この場合，要素数が小さい「ソーダのみ」の価格を10円上げる．
- 例2)では，どの財の束についても需要が供給を上回っていない． この場合「ソーダのみ」を希望する学生1と学生6にソーダを，「コーラのみ」を希望する学生2にコーラを割り当て，1本づつ残ったソーダとコーラを，学生4と学生5に割り当てればよい．

## 解法(2)の具体的な手続きの例
### 初期価格: $\mathbf{p}^{(0)} = (0,0)$
例1)と同様，「ソーダのみ」と「ソーダとコーラ」が需要超過だが，そのうち要素数の少ない「ソーダのみ」の価格を1単位増加させる: $p_{S}: 0 \rightarrow 10$ とする．
### 1ラウンド目: $\mathbf{p}^{(1)} = (10,0)$
各学生の利得は
||学生1|学生2|学生3|学生4|学生5|学生6|
|--|---|---|---|---|---|---|
|ソーダ($S$)|90|50|80|110|140|100|
|コーラ($C$) |30|60|40|70|100|50|
|希望する財 $\mathcal{R}$|$\{S\}$|$\{C\}$|$\{S\}$|$\{S\}$|$\{S\}$|$\{S\}$|

財の束ごとの需要と供給は

|財の束|$\{S\}$|$\{C\}$|$\{S,C\}$|
|---|---|---|---|
|需要|==5==|1|==6==|
|供給|3|2|5|

であるから，需要超過である「ソーダのみ」と「ソーダまたはコーラ」のうち，要素の小さいソーダの価格を $p_{S}: 10\rightarrow 20$とする．

詳細は省くが，このあと2ラウンド，3ラウンド，4ラウンドと各学生の希望する財のパターンが変わらないため，「ソーダのみ」の価格を上げる手続きが続く．

### 5ラウンド目: $\mathbf{p}^{(5)} = (50,0)$
この価格の下での各学生の利得と表明する財は，
||学生1|学生2|学生3|学生4|学生5|学生6|
|---|---|---|---|---|---|---|
|ソーダ($S$)|50|10|40|70|100|60|
|コーラ($C$) |30|60|40|70|100|50|
|希望する財|$\{S\}$|$\{C\}$|$\{S,C\}$|$\{S,C\}$|$\{S,C\}$|$\{S\}$|

となり，財の束ごとの需要と供給は

|財の束|$\{S\}$|$\{C\}$|$\{S,C\}$|
|---|---|---|---|
|需要|2|1|==6==|
|供給|3|2|5|

である．このとき「ソーダのみ」「コーラのみ」の財はいずれも需要が供給未満であり，需要過多となるのは「ソーダまたはコーラ」である．そこで，両方の財の価格を増加させる: $(p_{S}, p_{C}): (50,0)\rightarrow(60,10)$.

このあと，同様に，6ラウンド，7ラウンド，8ラウンドと両方の財の価格を上げる手続きが続く．

### 9ラウンド目: $\mathbf{p}^{(9)} = (90,40)$
上述の例2)と同様，ここまで価格が上昇した時点で，学生3は正の利得を得ることができなくなり，オークションから離脱する．このとき，各学生の利得と表明する財は，
||学生1|学生2|学生3|学生4|学生5|学生6|
|---|---|---|---|---|---|---|
|ソーダ($S$)|10|-30|0|30|60|20|
|コーラ($C$) |-10|20|0|30|60|10|
|希望する財|$\{S\}$|$\{C\}$|$\emptyset$|$\{S,C\}$|$\{S,C\}$|$\{S\}$|

となり，財の束ごとの需要と供給は

|財の束|$\{S\}$|$\{C\}$|$\{S,C\}$|
|---|---|---|---|
|需要|2|1|5|
|供給|3|2|5|

となり，いずれの財の束についても需要過多とはならない． したがって，最適な配分が求められた．

### ラウンドごとの財価格と希望する財の変化
以上の価格改訂と，各学生の希望する財の変化は以下のように整理できる．次の2つのラウンドが転換点となっていることが判るだろう：
- 5ラウンド目: ソーダの価格が50円になったところで，学生3，学生4，学生5の希望する財が「ソーダまたはコーラ」に変化→これ以降両方の価格が上昇
- 9ラウンド目： ソーダとコーラが価格差50円を維持したまま90円と40円になった時点で，学生3が正の利得をできなくなり離脱→これにより全ての財について需要過多が解消．

| ラウンド | 財価格 | 学生1 | 学生2 | 学生3 | 学生4 | 学生5 | 学生6 | |
| --- | ----------- | ------- | ------- | ----------- | --------- | --------- | ------- |--|
| | ソーダ評価値 | 100 | 60 | 90 | 120 | 150 | 110 |
| | コーラ評価値 | 30 | 60 | 40 | 70 | 100 | 50 |
| 0 | $(0,0)$ | $\{S\}$ | $\{C\}$ | $\{S\}$ | $\{S\}$ | $\{S\}$ | $\{S\}$ |
| 1 | $(10,0)$ | $\{S\}$ | $\{C\}$ | $\{S\}$ | $\{S\}$ | $\{S\}$ | $\{S\}$ |
| 2 | $(20,0)$ | $\{S\}$ | $\{C\}$ | $\{S\}$ | $\{S\}$ | $\{S\}$ | $\{S\}$ |
| 3 | $(30,0)$ | $\{S\}$ | $\{C\}$ | $\{S\}$ | $\{S\}$ | $\{S\}$ | $\{S\}$ |
| 4 | $(40,0)$ | $\{S\}$ | $\{C\}$ | $\{S\}$ | $\{S\}$ | $\{S\}$ | $\{S\}$ |
| 5 | $(50,0)$ | $\{S\}$ | $\{C\}$ | $\{S,C\}$ | $\{S,C\}$ | $\{S,C\}$ | $\{S\}$ |
| 6 | $(60,10)$ | $\{S\}$ | $\{C\}$ | $\{S,C\}$ | $\{S,C\}$ | $\{S,C\}$ | $\{S\}$ |
| 7 | $(70,20)$ | $\{S\}$ | $\{C\}$ | $\{S,C\}$ | $\{S,C\}$ | $\{S,C\}$ | $\{S\}$ |
| 8 | $(80,30)$ | $\{S\}$ | $\{C\}$ | $\{S,C\}$ | $\{S,C\}$ | $\{S,C\}$ | $\{S\}$ |
| 9 | $(90,40)$ | $\{S\}$ | $\{C\}$ | $\emptyset$ | $\{S,C\}$ | $\{S,C\}$ | $\{S\}$ |

## 2つの解法の等価性
上記の解法(1)と解法(2)では，いずれも，全く同じ配分
- 学生1と学生6にソーダ: $x_{1, S} = x_{6, S} = 1$
- 学生2にコーラ: $x_{2, C} = 1$
- 学生4と学生5にソーダかコーラのいずれか:
$x_{4, S} = x_{5, C}= 1$ もしくは $x_{4, C} = x_{5, S}= 1$

が得られ，割り当てられた財に対する各学生の評価値の和は，
||学生1|学生2|学生3|学生4|学生5|学生6|合計|
|---| --- | --- | --- | --- | --- | --- |---|
|評価値(学生4にソーダ)|100|60|0|120|100|110|490|
|評価値(学生5にソーダ)|100|60|0|70|150|110|490|

となる．

もっとも，解法(2)では，ソーダを割り当てられた学生は90円，コーラを割り当てられた学生は40円を支払うため，これらを評価値から引いた利得としては
||学生1|学生2|学生3|学生4|学生5|学生6|合計|
|---| --- | --- | --- | --- | --- | --- |---|
|利得(学生4にソーダ)|10|20|0|30|60|20|140|
|利得(学生5にソーダ)|10|20|0|30|60|20|140|

となる．しかし，学生の支払い(90円×3+40円×2=350円)は競売人の収入となっていることことに注意されたい． つまり「6人の学生と競売人からなる社会」を考え，その社会的便益(social benefit)を
$$\begin{align}
\text{社会的便益} &= \text{(学生の総利得)}+ \text{競売人の収入}\\
&= \sum_{i \in \mathcal{G}} \sum_{j \in \mathcal{N}} x_{ji}\left(v_{ji} - p_{i}\right) +\sum_{i \in \mathcal{G}} p_{i} d_{i}
\end{align}$$
と定義すれば， 解法(2)で得られる社会的便益は, 140円(学生の総利得)+350円(競売人の収入)=490円となり， 評価値の総和に一致する(学生の支出が競売人の収入に一致するので当然なのだが)．

# 解法(2)のメリット
上記の例で見たように，解法(1)と解法(2)はどちらも最適な配分を導くことが判った． では何故わざわざ回りくどい**オークション**などを使う解法(2)のメリットは何だろうか? 一つ目のメリットは，<span style="color:red">**解法(2)は，各学生の評価値を(明示的な)入力としては必要としない**</span>ことである．

解法(2)では，各学生は，提示された価格の下で**自らが希望する財**のみを表明する．もちろん，各学生が希望する財は，その学生の利得(評価値と価格の差)を最大化するものなので，評価値そのものが不要，というわけではない．それでも「競売人が各学生の各財に対する==全ての評価値を知る必要はない==」「各学生の評価値は(競売人でも他の学生でもなく) ==その学生だけ==が知っていればよい」という事は，(何らかの方法によって全ての学生の評価値を調査するのに比べて) **情報効率的**と言えるだろう．

もう一つのメリットは，解法(2)では，<span style="color:red">**各学生には嘘をつくメリットがない**</span>ことである．解法(1)では，入力としての評価値を調査する際に，高い評価値を申告すれば希望するアイスが割り当てられるわけだから，学生が虚偽の評価値を申告する可能性がある（次回で解説するように，それを回避する方法も存在する）． 一方，解法(2)では，学生が表明できるのは**希望する財**のみである．そのため，合理的な学生であれば，
- 自分の評価値よりも価格が高い財は表明しない(それで財が割り当てられたら損をするので)
- (財の価格上昇を止めるために)「利得を最大化する財をあえて表明しない」こともない(価格の上昇は止められるかもしれないが，その財が自分に割り当てられることもなくなるので)

ことが判るだろう．つまり，各学生は虚偽を表明できなくもないが，それによって何のメリットも得られない(獲得する利得を改善できない)．言い換えれば，解法(2)では，それぞれの学生にとって，自らの真の評価値にもとづいて表明することが合理的/最適な行動となることが保証されているのである．このことを**誘引整合的(incentive compatible)** と言う．

# 練習問題
上述の例で，ソーダ味が2本，コーラ味が3本の場合の最適配分を解法(1)と解法(2)のそれぞれで求めよ．