---
lang: ja
tags: MTNS-2022, lecture, linear programming
---
# 2022年度 交通社会システム論<br>第9回：割当問題とオークション(1) 割当問題 | Assignment Problem and Auction Theory (1): Assignment Problem
[ポータルへ戻る | 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-Ch08</code>
</div>

# 背景 - 交通問題とオークション | Transportation Management and Auction
## 私的情報と社会的意思決定 | Private Information and Social Decision Making
- 線形計画問題をはじめとする**最適化**は**資源の効率的配分**に他ならない．都市計画，交通計画，大規模感染症対策などの**社会的意思決定問題**に適用する際には注意が必要．
Linear programming and other **optimization** is nothing more than **efficient allocation of resources**. It should be applied with caution to **social decision-making problems** such as urban/transportation planning and countermeasures against large-scale infectious diseases.
- しばしば，社会を構成する個々の主体の**私的情報**をモデルの入力として与える必要がある(e.g. 目的関数, 制約条件)．
It is often necessary to provide **private information** of the individual agents of society as input to the model (e.g. objective function, constraints, and so on).
- 社会的調査によって私的情報を推計する方法はいろいろある([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))が，どんなに頑張って最適な戦略を求めたとしても，**入力としての私的情報が間違っていたら**社会にとって**望ましくない結果**をもたらし得る (例えば，バス路線を設計する際，乗降バス停ごとの時刻別需要を正確に把握できるか?)．
Although there are many ways to estimate private information through social surveys (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)), if **incorrect private information** is provided to a model, it might lead to **undesirable results** for society, no matter how hard we try to find the optimal strategy. (For example, when designing a bus route network and timetable, is it possible to accurately estimate demand for each time of day at each origin-destination bus stop?)
- **私的情報の観測・推計誤差**に ==**頑健な**== 意思決定(c.f. ロバスト最適化)や， **私的情報の観測・推計** そのものを ==**必要としない**== 意思決定(c.f. **メカニズム設計**)へのパラダイム・シフトが必要．
**A paradigm shift** is needed toward social decision making that is ==**robust**== (c.f. robust optimization) and/or that needs *no observation and estimation* of **private information** itself (c.f. **mechanism design**) .

## メカニズム設計とは | What is Mechanism Design?
ミクロ経済学/ゲーム理論をベースとした，私的情報下での **工学的** な **問題解決手法**．
An **engineering solution approach** based on microeconomics/game theory under private information.
- 経済学の本質は **資源の効率的配分**:
The essence of economics is **efficient allocation of resources**:
:::info
**厚生経済学の第1基本定理**:
**完全競争市場** において実現する資源配分は **Pareto最適** である．

**First Fundamental Theorem of Welfare Economics**:
The allocation of resources realized in a **perfectly competitive market** is **Pareto optimal**.
:::

**Pareto最適**: 集団に対する資源配分が Pareto 最適であるとは，その集団内の誰かの効用を犠牲にしなければ，別の誰かの効用を高められない(=資源が最大限に活用されている)とき．
**Pareto optimum**: A resource allocation to a set of agent is Pareto optimal when the utility of an agent must be sacrificed to increase the utility of another. In other words, the resource is fully utilized.
- **完全競争市場** ではない局面(e.g. 外部性や私的情報が存在)で，市場に代わるメカニズム/制度を設計する．
Design an alternative mechanism to **imperct market** with externalities and private information, for example.

## 実問題への適用例 | Application to Real World Problems
### 周波数オークション | Frequency Auction
- 1994年以来，米国 FCC (*Federal Communications Commission*; 米国連邦通信委員会)は周波数帯域の免許の割当を **オークション** で決定
Since 1994, [*Federal Communications Commission*; U.S. FCC)](https://www.fcc.gov/auctions/about-auctions) has conducted **auctions** of licenses for electromagnetic spectrum.
- **関連記事 | Related Articles**
- [安田先生の解説記事 | An introductory article by Prof. YYasuda](https://note.com/yagena/n/nbd7f4c70394c)
- [Auctions | FCC](https://www.fcc.gov/auctions)
- https://www.cnbc.com/2021/02/24/verizon-commits-more-than-45-billion-to-5g-spectrum-bid.html

### 英国バス路線オークション | London Bus Tenders
- ロンドン交通局(TfL:*Transport for London*)では，バス路線の運営を民間企業に委託することで，サービスの安定化・効率化を測っている．
TfL (*Transport for London*) has been outsourcing the operation of bus routes to private companies to provide stable and efficient bus services.
- '85年から，毎年，一部の路線について，それぞれの運営会社を入札によって選んでいる．
Since 1985, operating companies have been chosen for each of several bus routes each year through tenders.
- 1つの契約は5〜7年で， 契約期間中の運行距離,信頼性,運転手・車両の品質, 顧客満足度, 法令遵守, 安全性などが厳しく評価される.
Each contract is for five to seven years, and during the contract period, the operating distance, reliability, quality of drivers and vehicles, customer satisfaction, compliance with laws and regulations, and safety are strictly evaluated.
- **関連記事 | Related Articles**
- [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)

# 割当問題とオークション | Assignment Problem and Auction
## 問題設定 | Framework
- 夏の暑い日を想像しよう． 研究室の冷凍庫にガリガリ君(R)のソーダ味($S$)が3本，コーラ味($C$)が2本あるとする．
Imagine a hot summer day. Suppose there are three sticks of soda-flavored ($S$) and two sticks of cola-flavored ($C$) of Garigari-kun (R) (a famous popsicle in Japan) in the laboratory freezer.
- 研究室には，好みの違う6人の学生がいる． 誰にどの味を割り当てるのが最適か?
There are six students in the laboratory who have different tastes. Which flavor is the best to assign to whom?
- 学生の集合 (set of students): $\mathcal{N} = \{1, 2, 3, 4, 5, 6\}$
- 財(ガリガリ君)の集合 (set of goods): $\mathcal{G} = \{S, C\}$
- 財の供給量 (supply of each goods): $(d_{S}, d_{C}) = (3, 2)$.

学生$j \in \mathcal{N}$の財$i \in \mathcal{G}$に対する好み(を金銭換算したもの)を **評価値** $v_{ij}$ で表すことにする． ここでの評価値は， 以下のいずれとしても解釈できる．
The preference of student $j \in \mathcal{N}$ for good $i \in \mathcal{G}$ is denoted by ** value** $v_{ij}$. The values can be interpreted as any of the following.
- **支払い意思額** (willingness to pay): その財を取得するために支払ってもよいと思う最大の金額
**Willingness to pay**: the maximum price at or below which the agent will buy the goods.
- **留保価格**: その財の価格がそれを超えたら取得を諦める(留保する)金額
**Reservation price**: the lowest price to prevent the agent from "walking-away".

例えば，各学生の評価値が以下のように与えられるとしよう．
Suppose that the value of each agent is given by the following table:
||学生1<br>Student 1|学生2<br>Student 2|学生3<br>Student 3|学生4<br>Student 4|学生5<br>Student 5|学生6<br>Student 6|
|---|---|---|---|---|---|---|
|ソーダ (Soda flavor) ($S$)|100|60|90|120|150|110|
|コーラ (Cola flavor) ($C$) |30|60|40|70|100|50|

以下を仮定する：
It is assumed that
- 学生$j \in \mathcal{N}$の評価値$\boldsymbol{v}_{j}=\{v_{ij}: i \in \mathcal{G}\}$は，その学生しか知らない(**私的情報**である)とする．
The value of student $j \in \mathcal{N}$, $\boldsymbol{v}_{j} = \left\{v_{ij}: i \in \mathcal{C}\right\}$ is known only to the student (i.e. it is **private information**).
- 各学生には高々1つのアイスしか割り当てられないものとする．
Each student is assigned at most one popsicle.

アイスを割り当てられた学生の**評価値の合計が最大となる**ようにするには，誰にどのアイスを割り当てればよいだろう?
What assignment of the popsicles to the students maximizes the total value?

## 解法(1): 中央集権的なアプローチ | Solution Method (1): A Centralized Approach
アイス割当問題を解く一つの方法は，研究室で絶大な権力を誇る誰か（教授ではなく秘書さんだったりする）が，全ての学生の評価値を聞き出し，それに基づいて**中央集権的に**配分を決める方法である．
One way to solve the popsicle assignment problem is **centralized** approach: let someone with tremendous power in the lab (sometimes a secretary, not a professor) to find out the values of all the students and decide the assignment based on them.

財$i \in \mathcal{G}$の学生$j \in \mathcal{N}$への配分を変数$x_{ij}$で表すことにしよう． 財$i$が学生$j$に配分されるなら$x_{ij}=1$, そうでないときは$x_{ij}=0$とする．
Let denote an assignment of goods $i \in \mathcal{G}$ to student $j \in \mathcal{N}$ by $x_{ij}$. $x_{ij}=1$ if goods $i$ is assigned to student $j$ and $x_{ij}=0$ otherwise.

この時， 割り当て問題は下記の**二値線形計画問題**(*BLP: binary linear programming*)として定式化できる．
Then the assignment problem can be formulated as the following BLP (*binary linear programming*):
$$
\begin{alignat}{3}
\max_{\boldsymbol{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つの財しか割り当てられない | each student is assigned at most one goods)}\\
& \sum_{j \in \mathcal{N}} x_{ij} \leq d_{i} && \forall i \in \mathcal{G} && \text{(各財は供給量まではしか割り当てられない | each goods is assigned up to its supply)}\\
& x_{ij} \in \{0, 1\} && \forall i \in \mathcal{G} , \forall j \in \mathcal{N}
\end{alignat}
$$

この問題は，**二値制約** (binary constraint) $x_{ij} \in \{0, 1\}$があるため，本来ならば解くのが大変な問題である． ところが，割当問題の場合， この二値制約を緩和した下記の**線形計画問題**の解が，もとの二値線形計画問題の解に ==**必ず一致する**ことが保証されている==．
This problem is generally difficult to solve because of the **binary constraint** $x_{ij} \in \{0, 1\}$. However, for this assignment problem, it is guaranteed that the solution of the following **linear programming problem**, in which the binary constraint is relaxed, ==will always match== that of the original BLP.
$$
\begin{alignat}{3}
\max_{\boldsymbol{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}
$$

この線形計画問題の最適解は
The optimal solution of the above LP is
$$
x_{S, 1} = x_{S, 4} = x_{S, 6} = x_{C, 2} = x_{C, 5} = 1
$$
であり，その時の最適値は490となる． 評価値の表に配分を重ねてみる：
and its optimal value is $490$. Let denote the optimal assignment over the value table.

||学生1<br>Student 1|学生2<br>Student 2|学生3<br>Student 3|学生4<br>Student 4|学生5<br>Student 5|学生6<br>Student 6|
|---|---|---|---|---|---|---|
|ソーダ Soda ($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>|
|コーラ Cola ($C$) |30|<div style="background-color:orange">60</div>|40|70|<div style="background-color:orange">100</div>|50

なお，学生4と学生5への配分を入れ替えても，全く同じ最適値490が実現する．これもまた最適解である：
Note that the assignment to Student 4 and 5 can be swapped while the optimal value remains $490$. This assignment is also optimal.
||学生1<br>Student 1|学生2<br>Student 2|学生3<br>Student 3|学生4<br>Student 4|学生5<br>Student 5|学生6<br>Student 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): 競上げオークションによるアプローチ | Solution Method (2): Ascending Auction Approach
上述の中央集権的アプローチは， 各学生の全ての評価値を正確に聞き出せなければ適用できない（秘書さんが極めて有能なら可能かもしれないが）．そこで，**私的情報**を ==直接聞き出すことなく== 全く同じ配分を実現する方法として，**競り上げオークション**を導入してみよう．
The centralized approach described above cannot be applied unless all the values of each student are accurately elicited (although this might be possible to an extremely talented secretary). We therefore introduce an **ascending auction** that enables us to obtain the equivalent optimal assignment without obtaining the private information directly.

オークションは，下記の手続きで進められる：
This auction will proceed according to the following procedure:
- 競売人が財価格 $\boldsymbol{p}=(p_{S}, p_{C})$ を提示する． 初期価格は $\boldsymbol{p} = (0,0)$ とする．
The auctioneer offers a price $\boldsymbol{p}=(p_{S}, p_{C})$. The initial price is $\boldsymbol{p} = (0,0)$.
- 各学生 $j \in \mathcal{N}$ は， 提示された価格をもとに，各財について**利得**(=自分の評価値と価格の差) $v_{ij} - p_{i}$ を計算する．
Each student $j \in \mathcal{N}$ calculates the **payoff** (=difference between his/her value and the price) $v_{ij} - p_{i}$ for each goods based on the offered price.
- 各学生 $j \in \mathcal{N}$ は，利得が最大となる(希望する)財を**表明**する． 希望する(利得が最大となる)財が複数あるなら，その**全て**を表明する． 表明する財の集合を $\mathcal{R}_{j}(\boldsymbol{p})$ で表す． **利得が0以下となる場合**には表明を行わず($\mathcal{R}_{j}(\boldsymbol{p}) = \emptyset$)， ==オークションから離脱する==．
Each student $j \in \mathcal{N}$ **declares** the (desired) goods with the maximum payoff. If there is more than one desired (payoff-maximizing) goods, then **all** of them are declared. The set of goods to be declared is denoted by $\mathcal{R}_{j}(\mathbf{p})$. If the **payoff is less than or equal to zero**, no declaration is made ($\mathcal{R}_{j}(\mathbf{p}) = \emptyset$) and ==leaves the auction==.
- 価格が $(p_{S}, p_{C}) = (0, 0)$ であるとき， 学生1が希望する(利得が最大となる)のはソーダ味だけなので，$\mathcal{R}_{1}((0,0)) = \{S\}$.
When the price is $(p_{S}, p_{C}) = (0, 0)$, Student 1 wants only soda flavor (maximum gain), so $\mathcal{R}_{1}((0,0)) = \{S\}$.
- 価格が $(70, 0)$ の場合，ソーダ味もコーラ味も利得が30で**無差別(indifferent)** なので，希望する財全て$\mathcal{R}_{1}((70,30)) = \{S, C\}$を表明する.
When the price is $(70, 0)$, then both the soda and cola flavors have a payoff of 30 and are **indifferent**, so $\mathcal{R}_{1}((70,30)) = \{S, C\}$ for all desired goods.
- 価格が$(80, 0)$ の場合， コーラ味だけを希望するので $\mathcal{R}_{1}((80, 0)) = \{C\}$.
When the price is $(80, 0)$, then $\mathcal{R}_{1}((80, 0)) = \{C\}$ since only cola flavor is desired.
- 価格が$(130, 50)$ の場合，どちらの財も利得が負になるので $\mathcal{R}_{1}((130,50)) = \emptyset$ としてオークションから離脱．
If the price is $(130, 50)$, the student leaves the auction with $\mathcal{R}_{1}((130,50)) = \emptyset$ because the payoff for both goods is negative.
- 競売人は， 財の**束**(bundle) $\{S\}, \{C\}, \{S, C\}$のそれぞれに対して**需要**(その財の束の中に表明した財が含まれる人数)を計算し， それを**供給**（組み合わせに含まれる財の供給数の総和）と比較する．
The auctioneer computes the **demand** for each of the bundles (the number of people whose declared set of goods is included in the bundle), $\{S\}, \{C\}, \{S, C\}$), and compares it to the **supply** (the total number of supplies of the goods in the combination).
- 例1) 初期価格$\boldsymbol{p} = (0,0)$ の下では， 学生2は「ソーダまたはコーラ(ソーダとコーラが無差別)」を希望し，それ以外が「ソーダのみ」を希望するので，各財の束の需要と供給は以下のように整理できる：
Example 1) Under the initial price $\boldsymbol{p} = (0,0)$, Student 2 wants "soda or cola (soda and cola indiscriminately)" and the rest want "soda only". So the demand and supply for each good bundle can be summarized as follows:
|財の束(bundle)|需要(demand)|供給(supply)|
|---|---|---|
|ソーダのみ (soda only) $\{S\}$|5|3||
|コーラのみ (cola only)$\{C\}$| 0 | 2|
|ソーダまたはコーラ (soda or cola) $\{S,C\}$| 6| 5 |

注意 | Remarks：
- コーラのみを表明している学生はいないため，$\{C\}$への需要が0となっている
Demand for $\{C\}$ is zero as there is no student who wants "cola only".
- 「ソーダもしくはコーラ」に対する需要は「ソーダのみ」を表明した5名と「ソーダとコーラ」を表明した1名の合計で6名となる．
Demand for $\{S, C\}$ (soda or cola) is 6, which is a sum of the number of students who declare "soda only" and the number of students with demand "soda or cola".
- 例2) 価格が$\boldsymbol{p} = (90,40)$の場合， 各学生の各財に対する利得と表明する財は以下の表の通りになる:
Example 2) Under price $\boldsymbol{p} = (90,40)$, the payoff of each student from each goods and declared goods are the following:
||学生1<br>Student 1|学生2<br>Student 2|学生3<br>Student 3|学生4<br>Student 4|学生5<br>Student 5|学生6<br>Student 6|
|---|---|---|---|---|---|---|
|ソーダ(soda) ($S$)|10|-30|0|30|60|20|
|コーラ(cola) ($C$) |-10|20|0|30|60|10|
|希望する財(declared goods)|$\{S\}$|$\{C\}$|$\emptyset$|$\{S,C\}$|$\{S,C\}$|$\{S\}$|

学生3は，ソーダとコーラが無差別だが，その利得が正ではないため，希望を表明せずオークションから離脱していることに注意．
In this case, Students 3 has no positive payoff and leaves the auction without declaration.

このときの各財の束への需要と供給は以下の通り:
The demand and supply for each goods bundle can be summarized as follows:
|財の束(bundle)|需要(demand)|供給(supply)|
|---|---|---|
|ソーダのみ (soda only)$\{S\}$|2|3||
|コーラのみ (cola only) $\{C\}$| 1 | 2|
|ソーダまたはコーラ (soda or cola) $\{S,C\}$| 5 | 5 |

注意：
- 「ソーダまたはコーラ」の需要は「ソーダのみ」を表明した2名，「コーラのみ」を表明した1名，「ソーダまたはコーラ」を表明した2名の合計で5名．
Demand for $\{S, C\}$ (soda or cola) is 5, which is a sum of the number of students who declare "soda only" and the number of students with demand "soda or cola".
- 競売人は，需要が供給を上回っている(需要過多・供給不足)財の束のうち，最も要素数の小さいものの価格を1単位(ここでは10円)上げる． そのような財の束が無い場合， オークションに残っている全員に，表明した財（複数の場合はそのいずれか）を割当てることができる．
The auctioneer raises the price of the *overdemanded* bundle with the smallest number of elements by one unit (in this case, 10 yen). If there is no such bundle, every students remaining in the auction can be assigned the declared goods (or one of them if he/she declares multiple goods).
- 上述の例1)では，「ソーダのみ$\{S\}$」については，需要5に対して供給が3であるため，需要が供給を上回っている．同様に，「ソーダまたはコーラ$\{S,C\}$」についても需要6に対して供給が5であるため，需要過多(供給不足)である．この場合，要素数が小さい「ソーダのみ」の価格を10円上げる．
In Example 1) describe above, "soda only $\{S\}$" is overdemanded as its demand 5 is higher than its supply , 3. Similarly, "soda or cola $\{S, C\}$" is also overdemanded as its demand 6 is higher than its supply 5. In this case, the price of "soda only $\{S\}$" with minimum number of element is raised.
- 例2)では，どの財の束についても需要が供給を上回っていない． この場合「ソーダのみ」を希望する学生1と学生6にソーダを，「コーラのみ」を希望する学生2にコーラを割り当て，1本づつ残ったソーダとコーラを，学生4と学生5に割り当てればよい．
In Example 2), no bundle is overdemanded. In this case, Students 1 and 6, who declare "soda only" are assigned soda popsicle, while Student 2 who declares "cola only" is assigned a cola popsicle. The remaining soda and cola popsicles are assigned to Students 4 and 5, who declare "soda or cola."

## 解法(2)の具体的な手続きの例 | An Example of Ascending Auction
### 初期価格 (Initial Price): $\boldsymbol{p}^{(0)} = (0,0)$
例1)と同様，「ソーダのみ」と「ソーダとコーラ」が需要超過だが，そのうち要素数の少ない「ソーダのみ」の価格を1単位増加させる: $(p_{S}^{(1)}, p_{C}^{(1)}) = (p_{S}^{(0)}, p_{C}^{(0)}) + (10, 0) = (10, 0)$．
As shown in Example 1), the bundles "soda only ($\{S\}$)" and "soda or cola ($\{S, C\}$)" are overdemanded. Raise the price of the "soda only ($\{S\}$)" bundle as it has the smallest number of elements: $(p_{S}^{(1)}, p_{C}^{(1)}) = (p_{S}^{(0)}, p_{C}^{(0)}) + (10, 0) = (10, 0)$.
### 1ラウンド目 (1st Round): $\boldsymbol{p}^{(1)} = (10,0)$
各学生の利得:
The payoff of each pair of student and goods:
||学生1<br>Student 1|学生2<br>Student 2|学生3<br>Student 3|学生4<br>Student 4|学生5<br>Student 5|学生6<br>Student 6|
|--|---|---|---|---|---|---|
|ソーダ(soda) ($S$)|90|50|80|110|140|100|
|コーラ(soda) ($C$) |30|60|40|70|100|50|
|希望する財(declared goods) $\mathcal{R}$|$\{S\}$|$\{C\}$|$\{S\}$|$\{S\}$|$\{S\}$|$\{S\}$|

財の束ごとの需要と供給:
The demand and supply for each bundle of goods:

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

需要超過である「ソーダのみ」と「ソーダまたはコーラ」のうち，要素の小さいソーダの価格を上げる：$(p_{S}^{(2)}, p_{C}^{(2)}) = (p_{S}^{(1)}, p_{C}^{(1)}) + (10, 0) = (20, 0)$．
The overdemanded bundles are "soda only $\{S\}$" and "soda or cola $\{S, C\}$," while the former is smaller. Thus the price of soda only is raised: $(p_{S}^{(2)}, p_{C}^{(2)}) = (p_{S}^{(1)}, p_{C}^{(1)}) + (10, 0) = (20, 0)$.

詳細は省くが，このあと2ラウンド，3ラウンド，4ラウンドと各学生の希望する財のパターンが変わらないため，「ソーダのみ」の価格を上げる手続きが続く．
Although the details are omitted for the simplicity, the auction procedure raises the soda price for round 2, 3 and 4.

### 5ラウンド目 (5th Round): $\boldsymbol{p}^{(5)} = (50,0)$
この価格の下での各学生の利得と表明する財:
The payoff of each pair of student and goods, as well as the declared goods of each student under this price is:
||学生1<br>Student 1|学生2<br>Student 2|学生3<br>Student 3|学生4<br>Student 4|学生5<br>Student 5|学生6<br>Student 6|
|---|---|---|--|--|--|--|
|ソーダ (soda)($S$)|50|10|40|70|100|60|
|コーラ (cola)($C$) |30|60|40|70|100|50|
|希望する財(declared goods)|$\{S\}$|$\{C\}$|$\{S,C\}$|$\{S,C\}$|$\{S,C\}$|$\{S\}$|

財の束ごとの需要と供給:
The demand and supply for each bundle:

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

このとき「ソーダのみ」「コーラのみ」の財はいずれも需要が供給未満であり，需要過多となるのは「ソーダまたはコーラ」である．そこで，両方の財の価格を増加させる: . $(p_{S}^{(6)}, p_{C}^{(6)}) := (p_{S}^{(5)}, p_{C}^{(5)}) + (10, 10) = (60, 10)$.
In this case, both of "soda only $\{S\}$" and "cola only $\{C\}$" are not overdemanded as their demands are smaller than supplies. The only overdemanded bundle is $\{S, C\}$ and thus its price is raised: $(p_{S}^{(6)}, p_{C}^{(6)}) := (p_{S}^{(5)}, p_{C}^{(5)}) + (10, 10) = (60, 10)$.

このあと，同様に，6ラウンド，7ラウンド，8ラウンドと両方の財の価格を上げる手続きが続く．
Similarly the prices of both soda and cola are raised in the subsequent rounds 6, 7 and 8.

### 9ラウンド目 (9th Round): $\boldsymbol{p}^{(9)} = (90,40)$
上述の例2)と同様，ここまで価格が上昇した時点で，学生3は正の利得を得ることができなくなり，オークションから離脱する．このとき，各学生の利得と表明する財は，
As shown in Example 2), Student 3 can not yield positive payoff under this price and leaves the market. The payoff of each pair of student and goods as well as the declared goods of each student under this price is:
||学生1<br>Student 1|学生2<br>Student 2|学生3<br>Student 3|学生4<br>Student 4|学生5<br>Student 5|学生6<br>Student 6|
|---|---|---|--|--|--|--|
|ソーダ($S$)|10|-30|0|30|60|20|
|コーラ($C$) |-10|20|0|30|60|10|
|希望する財|$\{S\}$|$\{C\}$|$\emptyset$|$\{S,C\}$|$\{S,C\}$|$\{S\}$|

財の束ごとの需要と供給は:
The demand and supply for each bundle:

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

となり，いずれの財の束についても需要過多とはならない． したがって，最適な配分が求められた．
There is no overdemanded bundle and thus every student in the market would be assigned one of his/her declared goods.

### ラウンドごとの財価格と希望する財の変化 | Prices and Declared Goods in Each Round
以上の価格改訂と，各学生の希望する財の変化は以下のように整理できる．次の2つのラウンドが転換点となっていることが判るだろう：
The above price update and corresponding changes in students' declaration can be summarized as follows. You can see that the next two rounds are the turning points:
- 5ラウンド目: ソーダの価格が50円になったところで，学生3，学生4，学生5の希望する財が「ソーダまたはコーラ」に変化→これ以降両方の価格が上昇
Round 5: When the soda price becomes $p_{S}=50$ and the declared goods of Students 3, 4 and 5 changes to "soda or cola $\{S, C\}$". After this, the prices of both will be increased.
- 9ラウンド目： ソーダとコーラが価格差50円を維持したまま90円と40円になった時点で，学生3が正の利得をできなくなり離脱→これにより全ての財について需要過多が解消．
Round 9: When the soda and cola becomes 90 and 40 JPY while maintaining the price difference of 50 JPY, Student 3 can not yield positive payoff and leaves the market. This resolves overdemand for all bundles.

| ラウンド<br>Round | 財価格<br>Prices | 学生1<br>Student 1 | 学生2<br>Student 2 | 学生3<br>Student 3 | 学生4<br>Student 4 | 学生5<br>Student 5 | 学生6<br>Student 6 | |
| --- | ----------- | ------- | ------- | ----------- | --------- | --------- | ------- |--|
| | ソーダ評価値(value of soda) | 100 | 60 | 90 | 120 | 150 | 110 |
| | コーラ評価値(value of cola) | 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つの解法の等価性 | The Equivalence of Two Solution Methods
上記の解法(1)と解法(2)では，いずれも，全く同じ配分
The above two solution methods obtain the same assignment:
- 学生1と学生6にソーダ (soda to Student 1 and 6): $x_{1, S} = x_{6, S} = 1$
- 学生2にコーラ (cola to Student 2): $x_{2, C} = 1$
- 学生4と学生5にソーダかコーラのいずれか (either soda or cola to Student 4 and 5):
$x_{4, S} = x_{5, C}= 1$ もしくは $x_{4, C} = x_{5, S}= 1$

が得られ，割り当てられた財に対する各学生の評価値の和は，
and the total value can be summarized as
||学生1<br>Student 1|学生2<br>Student 2|学生3<br>Student 3|学生4<br>Student 4|学生5<br>Student 5|学生6<br>Student 6|合計<br>total|
|---| --- | --- | --- | --- | --- | --- |---|
|評価値(学生4にソーダ)<br>value: soda is assigned to Student 4|100|60|0|120|100|110|490|
|評価値(学生5にソーダ)<br>value: soda is assigned to Student 5|100|60|0|70|150|110|490|

となる．

解法(2)では，ソーダを割り当てられた学生は90円，コーラを割り当てられた学生は40円を支払うため，これらを評価値から引いた利得は
In Solution Method (2), the student who is assigned soda pays 90 JPY, while the student who is assigned cola pays 40 JPY. Thus the payoff that is difference of the value and the payment becomes as follows:
||学生1<br>Student 1|学生2<br>Student 2|学生3<br>Student 3|学生4<br>Student 4|学生5<br>Student 5|学生6<br>Student 6|合計<br>total|
|---| --- | --- | --- | --- | --- | --- |---|
|利得(学生4にソーダ)<br>payoff: soda is assigned to Student 4|10|20|0|30|60|20|140|
|利得(学生5にソーダ)<br>payoff: soda is assigned to Student 5|10|20|0|30|60|20|140|

となる．ここで，学生の支払い(90円×3+40円×2=350円)は競売人の収入となっていることことに注意されたい． つまり「6人の学生と競売人からなる社会」を考え，その社会的便益(social benefit)を
Note that the total payment (i.e. $90\times{}3+40\times{}2=350$ JPY) of students is the total income of the auctioneer. That is, when we define the social benefit of a society consists of 6 students and the auctioneer as
$$\begin{align}
\text{社会的便益} &= \text{学生の総利得}+ \text{競売人の収入}\\
\text{social benefit} &= \text{total payoff of students} + \text{total income of the auctioneer}\\
&= \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}\\
&= \sum_{i \in \mathcal{G}}\sum_{j \in \mathcal{N}} x_{ij} v_{ij}
\end{align}$$
と定義すれば， 解法(2)で得られる社会的便益は, 140円(学生の総利得)+350円(競売人の収入)=490円となり， 評価値の総和に一致する(学生の支出が競売人の収入に一致するので当然なのだが)．
the social benefit obtained by Solution Method (2) is 490, which is the sum of the total payment of student 140 and the total income of the auctioneer 350, equals to the total value.

# 解法(2)のメリット | Advantage of Solution Method (2)
上記の例で見たように，解法(1)と解法(2)はどちらも最適な配分を導くことが判った． では何故わざわざ回りくどい**オークション**などを使う解法(2)のメリットは何だろうか?
As shown in the above examples, both of Solution Methods (1) and (2) can derive the equivalent optimal assignment. Then, what is the advantage of using the auction procedure over the centralized optimization?

一つ目のメリットは，<span style="color:red">**解法(2)は，各学生の評価値を(明示的な)入力としては必要としない**</span>ことである．解法(2)では，各学生は，提示された価格の下で**自らが希望する財**のみを表明する．もちろん，各学生が希望する財は，その学生の利得(評価値と価格の差)を最大化するものなので，評価値そのものが不要，というわけではない．それでも「競売人が各学生の各財に対する==全ての評価値を知る必要はない==」「各学生の評価値は(競売人でも他の学生でもなく) ==その学生だけ==が知っていればよい」という事は，(何らかの方法によって全ての学生の評価値を調査するのに比べて) **情報効率的**と言えるだろう．
The first advantage is that Solution Method (2) does not need the value of students as an explicit input. In this method, each student declares **his/her own desired goods** given the price. Of course, the desired goods are those maximize the student's payoff (i.e. the difference between the value and the price) and thus it does not mean that the values are unnecessary. Still, this implies that Solution Method (2) based on auction is **information effective** from the viewpoints that "the auctioneer does not need to know the all value of each pair of students and goods" and "each student's value needs to be known only by him/herself."

もう一つのメリットは，解法(2)では，<span style="color:red">**各学生には嘘をつくメリットがない**</span>ことである．解法(1)では，入力としての評価値を調査する際に，高い評価値を申告すれば希望するアイスが割り当てられるわけだから，学生が虚偽の評価値を申告する可能性がある（次回で解説するように，それを回避する方法も存在する）． 一方，解法(2)では，学生が表明できるのは**希望する財**のみである．そのため，合理的な学生であれば，
- 自分の評価値よりも価格が高い財は表明しない(それで財が割り当てられたら損をするので)
- (財の価格上昇を止めるために)「利得を最大化する財をあえて表明しない」こともない(価格の上昇は止められるかもしれないが，その財が自分に割り当てられることもなくなるので)
ことが判るだろう．つまり，各学生は虚偽を表明できなくもないが，それによって何のメリットも得られない(獲得する利得を改善できない)．言い換えれば，解法(2)では，それぞれの学生にとって，自らの真の評価値にもとづいて表明することが合理的/最適な行動となることが保証されているのである．このことを**誘引整合的(incentive compatible)** と言う．
The second advantage is that, in Solution Method (2), each student has no incentive to lie. In Solution Method (1), each student would tell wrong value to increase the chance to obtain popsicles, as the popsicles tend to be assigned to students with higher value (this "false-bid" can be avoided as shown in the next lecture). In Solution Method (2), however, each student can declare only his/her desired goods. Thus a rational student **would not do any of the following**:
- declare goods whose prices are higher than his/her value, because the student will loss if such goods are assigned.
- not declare the payoff-maximizing goods (perhaps in order to stop the price rising), because the goods will no longer be assigned to him/her.

# 練習問題 | Exercise
上述の例で，ソーダ味が2本，コーラ味が3本の場合の最適配分を解法(1)と解法(2)のそれぞれで求めよ．
Obtain the optimal assignment by Solution Method (1) and Solution Method (2) when there are 2 soda popsicles and 3 cola popsicles.