2022年度交通社会システム論<br>第11回：割当問題とオークション(3) VCGメカニズム

--- lang: ja tags: MTNS-2022, lecture, linear programming --- # 2022年度交通社会システム論<br>第11回：割当問題とオークション(3) VCGメカニズム | VCG Mechanism [ポータルへ戻る](https://hackmd.io/@nagae/MTNS_2022) <div style="text-align: center"> このページへは以下のQRコードまたはURLからアクセスできます： ![](https://i.imgur.com/s7nGRQE.png =200x) <code style="font-size:20pt">https://hackmd.io/@nagae/MTNS_2022-Ch10</code> </div> # VCG (*Vickrey-Clarke-Groves*) メカニズム | VCG Mechanism ## Vickrey-Clarke-Groves 価格 | VCG Price オークションに参加する各買手にとって，自らの**真の評価値**を申告することが **(弱)支配戦略(weakly dominant strategy)** となるような価格として知られる． VCG price is known as a price such that it is a **weekly dominant strategy** for each buyer in the auction to declare his/her **true value**. :::info **弱支配戦略**: 他の買手の申告によらず，**虚偽の申告**によって**自らの利得を改善できない**. **Weekly dominant strategy**: No one can achieve a higher payoff by false telling independent of the other buyers' declarations. ::: なお，「虚偽の申告をすると常に**利得が減少する**場合」は，正直申告が(弱のつかない)**支配戦略**であると言う． It is (strong) dominant strategy if every buyer always looses his/her payoff by false-telling. 提案者である William **V**ickrey, Edward H. **C**larke および Theodore **G**roves の頭文字をとって，**VCG価格**と呼ばれている． The price is referred to as VCG price named after, William **V**ickrey, Edward H. **C**larke and Theodore **G**roves, who proposed it. - William Vickrey は交通渋滞を表現するボトルネック・モデルの始祖としても有名．1996年にNobel経済学賞を受賞． William Vickrey is also famous as the pioneer of the bottleneck model that represents the road congestion. He received the Nobel Prize in Economics in 1996. - 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\}$． Clarke-Groves Taxes is well known in the public economics. Suppose that lab members want to buy a coffee machine in the lab, which costs $M$ JPY. Payment rules to prevent **free-riding** by bidding a lower willingness-to-pay amount is: Each student bids his/her willingness-to-pay, $b_{j}$ and its sum $\sum_{j} b_{j}$ is greater than $M$, the coffee machine is purchased. In that case, the amount that student $l$ actually pays is the difference between the installation cost and the sum of his other bids (0 if negative): $\max\left\{M-\sum_{j \ne l}b_{j}, 0\right\}$. ## VCG価格の計算方法 | Calculation of VCG Price ### 買手サブ集合に対する割当問題 | Assignment Problem for A Buyers' Subset - $v_{j}(\boldsymbol{x}) = \sum_{i \in \mathcal{G}} v_{ij}x_{ij}$: ある割当 $\boldsymbol{x} = \{x_{ij}\}$ の下で買手$j$が得る評価値 | The value that buyer $j$ yields under assignment $\boldsymbol{x} = \{x_{ij}\}$. - $\boldsymbol{x}^{\ast}(\hat{\mathcal{N}})$: ある買手サブ集合$\hat{\mathcal{N}} \subseteq \mathcal{N}$に対する割当問題の最適解(最適割当) | The optimal assignment for buyers' subset $\hat{\mathcal{N}} \subseteq \mathcal{N}$: $$ \begin{align} V^{\ast}(\hat{\mathcal{N}}) = \max_{\boldsymbol{x}} &\sum_{j \in \color{red}{\hat{\mathcal{N}}}} v_{j}(\boldsymbol{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価格 | VCG Price of Buyer $j$ - $\hat{\mathcal{N}} = \mathcal{N}$なら元の割当問題に一致する．この時の最適割当および最適値を，それぞれ，以下のように表す： The optimal assignment for $\hat{\mathcal{N}} = \mathcal{N}$ is identical to the optimal solution of the original assignment problem. Let denote its optimal assignment and optimal value by: $$\begin{align} \boldsymbol{x}^{\ast} &= \boldsymbol{x}^{\ast}(\mathcal{N})\\ V^{\ast} &= V^{\ast}(\mathcal{N})\\ &= \sum_{j \in \mathcal{N}} v_{j}(\boldsymbol{x}^{\ast})\end{align}$$ - ある買手 $l\in \mathcal{N}$ について，**それ以外の買手**からなるサブ集合$\mathcal{N}\setminus\{l\}$に対する最適割当および最適値を，それぞれ，以下のように定義する： For buyer $l \in \mathcal{N}$, let us define the optimal assignment and the optimal value for buyers' subset $\mathcal{N} \setminus \{l\}$, which is the set of buyers **except for** buyer $l$. $$\begin{align} \boldsymbol{x}_{-l}^{\ast} &= \boldsymbol{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}(\boldsymbol{x}_{-l}^{\ast}) \end{align}$$ - このとき，買手$l$ のVCG価格 $p_{l}$ は，以下の2つの項の差で与えられる： The VCG price of buyer $l$ is given by the difference of the following two terms: 1. **買手 $l$ が不在の集合** $\mathcal{N}\setminus\{l\}$ における割当問題の最適値: The total value for the **market without** $l$, $\mathcal{N} \setminus \{l\}$: $$\begin{equation}V_{-l}^{\ast} = \sum_{j \ne l} v_{j}(\boldsymbol{x}_{-l}^{\ast})\end{equation}$$ 2. 全買手集合に対する最適割当における**買手$l$以外**の総評価値: The total value **other than** $l$ for the full market, $\mathcal{N}$: $$\begin{equation}V^{\ast} - v_{l}(\boldsymbol{x}^{\ast}) = \sum_{j \ne l} v_{j}(\boldsymbol{x}^{\ast})\end{equation}$$ 具体的には，買手$l$が支払うべき**VCG価格**は，以下の式で表される： That is, VCG price of buyer $l$ is obtained as $$\begin{align} p_{l} &= V_{-l}^{\ast} -\left\{V^{\ast} - v_{l}^{\ast}\left(\boldsymbol{x}^{\ast}\right)\right\}\\ &= \underbrace{\sum_{j \ne l} v_{j}(\boldsymbol{x}_{-l}^{\ast})}_{\begin{array}{c}\text{買手$l$がいない時の総評価値}\\\text{Total value for the market without $l$}\end{array}} -\underbrace{\sum_{j \ne l} v_{j}(\boldsymbol{x}^{\ast})}_{\begin{array}{c}\text{買手$l$以外の総評価値}\\\text{Total value for the full market other than $l$}\end{array}} \end{align}$$ # VCG価格の経済学的解釈 | Economic Implications of VCG Price ## 買手の市場参入による"迷惑料"としての解釈 | "Compensation Price" for the Buyer's Entry 買手$l$ のVCG価格 VCG price of buyer $l$ is: $$\begin{align} p_{l} &= \sum_{j \ne l} \left\{ v_{j}(\boldsymbol{x}_{-l}^{\ast}) - v_{j}(\boldsymbol{x}^{\ast}) \right\} \end{align}$$ - $v_{j}(\boldsymbol{x}_{-l}^{\ast}) - v_{j}(\boldsymbol{x}^{\ast})$ は，買手集合が $\mathcal{N}\setminus\{l\}$から$\mathcal{N}$に変化した(i.e. 買手$l$が**市場に参入**した)時の**買手$j$の評価値の減少分** $v_{j}(\boldsymbol{x}_{-l}^{\ast}) - v_{j}(\boldsymbol{x}^{\ast})$ is the decrease in the value of buyer $j$ with respect to the change in the buyers' set from $\mathcal{N}\setminus \{l\}$ to $\mathcal{N}$ (i.e. buyer $l$ enters the market). - 買手$l$の**VCG価格**は，買手$l$が**市場に参入**することで**他の買手が失った評価値の総和**(===**迷惑料**==)に等しい． VCG price of buyer $j$ is equivalent to the sum of decreases of other buyers' value with respect to the buyer $j$ 's entry to the market. ## VCG価格の下で買手が得る利得の"限界生産"としての解釈 | "Marginal Product" of Buyer VCG価格の下での買手$l$の利得(i.e. 買手$l$が得る評価値$v_{l}(\boldsymbol{x}^{\ast})$からVCG価格$p_{l}$引いたもの)： The payoff of buyer $l$ (i.e. the difference between the value $v_{l}(\boldsymbol{x}^{\ast}))$ and VCG price $p_{l}$): $$\begin{align} \pi_{l} &= v_{l}(\boldsymbol{x}^{\ast}) - p_{l}\\ &= v_{l}(\boldsymbol{x}^{\ast}) - \sum_{j\ne l} \left\{ v_{j}(\boldsymbol{x}_{-l}^{\ast}) - v_{j}(\boldsymbol{x}^{\ast}) \right\}\\ &= v_{l}(\boldsymbol{x}^{\ast}) + \sum_{j\ne l} v_{j}(\boldsymbol{x}^{\ast}) - \sum_{j \ne l} v_{j}(\boldsymbol{x}_{-l}^{\ast})\\ &= V^{\ast} - V_{-l}^{\ast} \end{align}$$ 買手$l$の利得は，買手$l$が**市場に参入**することによる**総評価値の増分**(===**限界生産**==)に等しい． This implies that buyer $l$ 's payoff $\pi_{l}$ is equivalent to the marginal product, the increase in the total value by buyer $l$ 's entry to the market. # 2財3人の例 | An Example of Two Items and Three Buyers 下記のケースでVCG価格を計算してみよう: Compute VCG prices for the following case: | |買手1<br>Buyer 1|買手2<br>Buyer 2|買手3<br>Buyer 3|供給量<br>supply| |---|---|---|---|--| |財(item) $A$| 70 | 30 | 40|1| |財(item) $B$|60 | 20 | 10 |1| 1. **全買手集合**に対する最適配分と総評価値: Optimal assignment and the optimal value for the full market: $\boldsymbol{x}^{\ast}=(x_{A3}=1,x_{B1}=1)$ $V^{\ast} = 100$. | |買手1<br>Buyer 1|買手2<br>Buyer 2|買手3<br>Buyer 3| |---|---|---|---| |財(item) $A$| 70 | 30 | <div style="background-color:orange">40</div>| |財(item) $B$|<div style="background-color:orange">60</div> | 20 | 10 | あとで使うことになるので，いまのうちに下記を計算しておこう： For the later convenience, let us calculate the followings: - **買手1以外**の総評価値 (total value other than Buyer 1): $V^{\ast} -v_{1}(\boldsymbol{x}^{\ast}) = 100-60=40$ - **買手3以外**の総評価値 (total value other than Buyer 3): $V^{\ast} -v_{3}(\boldsymbol{x}^{\ast}) = 100-40=60$ 2. **買手1が不在の場合**の最適配分と総評価値 The optimal assignment and the optimal value for the market **without Buyer 1**: $\boldsymbol{x}_{-1}^{\ast}=(x_{A3}=1,x_{B2}=1)$ $V^{\ast}_{-1} = 60$. | |~~買手1~~<br><strike>Buyer 1</strike>|買手2<br>Buyer 2|買手3<br>Buyer 3| |---|---|---|---| |財 (item) $A$| ~~70~~ | 30 | <div style="background-color:orange">40</div>| |財 (item) $B$|~~60~~ | <div style="background-color:orange">20</div> | 10 | 4. 買手1のVCG価格 VCG price of Buyer 1 - **買手1が不在時**の総評価値 (total value for the **market without Buyer 1**)： $V_{-1}^{\ast} = 60$ - **買手1以外**の総評価値 (total value for the full market **other than Buyer 1**): $V^{\ast}-v_{1}(\boldsymbol{x}^{\ast}) = 40$ 従って，VCG価格は That is, VCG price is $p_{1} = 60-40=20$. この金額は，**買手1が市場に参入**することで**買手2が失う評価値**(20)に等しい． This amount is equal to the value that **Buyer 2 loses** by **Buyer 1's entry** to the market, 20. 買手1の利得$\pi_{1} = 60-20=40$ は，**買手1が市場に参入**することによる総評価値の増分$V^{\ast}-V_{-1}^{\ast}= 100-60=40$に等しい． The payoff of Buyer 1 $\pi_{1} = 60-20=40$ is equal to the increment in the total value due to **Buyer 1's entry** to the market, $V^{\ast}-V_{-1}^{\ast}= 100-60=40$. 3. **買手3が不在の場合**の最適配分と評価値 The optimal assignment and the optimal value for the market **without Buyer 3**: $\boldsymbol{x}_{-3}^{\ast}=(x_{A1}=1,x_{B2}=1)$ or $(x_{A2}=1,x_{B1}=1)$ $V^{\ast}_{-3} =90$. | |買手1<br>Buyer 1|買手2<br>Buyer 2|~~買手3~~<br><strike>Buyer 3</strike>| |---|---|---|---| |財 (item) $A$| <div style="background-color:orange">70</div> | 30 | ~~40~~| |財 (item) $B$|60 | <div style="background-color:orange">20</div> | ~~10~~ | | |買手1<br>Buyer 1|買手2<br>Buyer 2|~~買手3~~<strike>Buyer 3</strike>| |---|---|---|---| |財 (item) $A$| 70 |<div style="background-color:orange"> 30</div> | ~~40~~| |財 (item) $B$|<div style="background-color:orange">60</div> | 20 | ~~10~~ | 5. 買手3のVCG価格 VCG price of Buyer 3 - **買手3が不在時**の評価値 (total value for the **market without Buyer 3**)： $V_{-3}^{\ast} = 90$ - **買手3以外**の評価値(total value for the full market **other than Buyer 3**): $V^{\ast}-v_{3}(\boldsymbol{x}^{\ast}) = 60$ 従って，VCG価格は That is, VCG price is $p_{3} = 90-60=30$. この金額は,**買手3が市場に参入**することで**買手1と買手2が失う評価値の和**(30)に等しい This amount is equal to the sum of values that **Buyer 1 and Buyer 2 lose** by **Buyer 3's entry** to the market, 30. 買手3の利得$\pi_{3} = 40-30=10$ は，**買手3が市場に参入**することによる総評価値の増分$V^{\ast}-V_{-3}^{\ast}= 100-90=10$に等しい． The payoff of Buyer 3$\pi_{3} = 40-30=10$ is equal to the increment in the total value due to **Buyer 1's entry** to the market, $V^{\ast}-V_{-3}^{\ast}= 100-90=10$. # VCG価格の誘引整合性 | Incentive Compatibility of VCG Price 上記 VCG価格の最大のメリットを端的に表現すると，「合理的な買手なら誰でも，**自分の評価値を正直に申告する**こと」ことにある．より正確に言うと，VCG価格には「虚偽の申告によってより高い利得を得ることはできない」という仕組み(メカニズム)が備わっている．このような性質を **誘引整合性(incentive compatibility)** という． The most relevant advantage of the VCG price can be simply expressed as "any reasonable buyer would **truthfully declare** his/her own value." More precisely, the VCG price has a mechanism that "no higher payoff can be obtained by false declarations." Such property is referred to as **incentive compatibility**. ## 直感的な説明 | An Intuitive Explanation 買手1が支払うVCG価格は，下記の2つの評価値： The VCG price that Buyer 1 has to pay is the difference of the following two values, 20: - **買手1不在時**の評価値: 60(下図中の青い棒) The total value for **the market except for Buyer 1**, 60 (the blue bar in the figure below) - (最適配分における)**買手1以外**の評価値: 40 (下図中の赤い棒) The total value the full market **other than Buyer 1**, 40 (the red bar in the figure below) の差 20 (下図中の緑の棒)． <div style="text-align:center"> ![](https://i.imgur.com/HIOoWF9.png =x150) </div> 従って，買手1が支払い(緑の棒)を減らすためには， This implies that either of the following is needed to decrease Buyer 1's payment (the green bar in the figure above): 1. **買手1が不在時**の評価値(青い棒)を**短くする** Shorten the blue bar (decrease the total value for **the market without Buyer 1**) 2. **買手1以外**の評価値(赤い棒)を**長くする** Lengthen the red bar (increase the total value for the full market **other than Buyer 1**) かしかない．このうち，前者は「自分が不在時の配分」によって決まるため，**買手1はコントロールできない**．一方，後者は，「自分以外の評価値を増やす」ことは「**自分が得る評価値を減らす**」ことを意味している(最適配分における総評価値は一定であるため)．言い換えれば，買手1以外の評価値が増えた分，買手1の支払いは減るが，得られる評価値も同じだけ減り，その差である利得は変わらない． The former can not be done by Buyer 1 as he/she can not affect the decision in the market "without him." The later is also not reasonable to Buyer 1, because "increase in the total value other than Buyer 1" implies that "decrease in Buyer 1's value" as the total value at the optimal assignment for the full market is constant. In other words, when the total value other than Buyer 1 increases by $M$, Buyer 1 can reduce payment by $M$ and he/she lose the value by $M$ with payoff remaining unchanged. 同じことは，どの買手にも当てはまる．このため，**虚偽を申告をすることでは，より高い利得は得られない**． Similar argument is applicable to every buyer. Therefore, no one can achieve a higher payoff by false-declarations. ## 数理的証明 | Rigorous Proof :::info VCG価格の下では，各買手は，自らの評価値を**正直に表明する** ことが **(弱)支配戦略**となる. すなわち，各買手 $l \in \mathcal{N}$は ==他の買手がどんな評価値を申告しているかに関わらず==自らの評価値 $\boldsymbol{v}_{l} := \{v_{il} : \forall i \in \mathcal{G}\}$ を正直に入札したときより高い利得を得ることはできない． Under the VCG price, it is a **(weak) dominant strategy** for every buyer to declare his/her **true value**. That is no one can yield a higher payoff than when he/she declare truth, $\boldsymbol{v}_{l} := \left\{v_{il} : \forall i \in \mathcal{G}\right\}$ ==regardless of what other buyers have declared==. ::: これを証明するために，以下の記号を導入しよう： In order to prove it rigorously, let us define the followings: - $\boldsymbol{b}_{l} := \{b_{il} : i \in \mathcal{G}\}$: 買手 $l$ の各財への申告額 | the declaration of buyer $l$ - $\boldsymbol{b}_{−l} :=\{b_{ij} :(i,j) \in \mathcal{G}×(\mathcal{N}\setminus\{l\})\}$: 買手 $l$ 以外の各財への申告額(買手$l$ の行動とは無関係に決まる) | the declaration of buyers other than $l$ (determined independently of buyer $l$'s declaration). - $\boldsymbol{x}^{\ast}$: 買手 $l$ が自らの(真の評価値を)**正直に申告** した時の**最適配分**(i.e. 申告された評価値 $(\boldsymbol{v}_{l}, \boldsymbol{b}_{−l})$ の総和を最大化する配分) | The optimal assignment when buyer $l$ declared his/her truth value (i.e. the assignment that maximize the total declared value $(\boldsymbol{v}_{l}, \boldsymbol{b}_{−l})$ ). - $\boldsymbol{y}^{\ast}$: 買手 $l$ が**虚偽の申告**をした時の**最適配分**(i.e. 申告された評価値 $(\boldsymbol{b}_{l}, \boldsymbol{b}_{−l})$ を最大化する配分) | Then optimal assignment when buyer $l$ declared false value, $\boldsymbol{b}_{l} \ne \boldsymbol{v}_{l}$. (i.e. the assignment that maximizes the total declared value $(\boldsymbol{b}_{l}, \boldsymbol{b}_{−l})$). - $\boldsymbol{x}^{∗}_{−l}$: 買手$l$ が不在の市場 $\mathcal{N} \setminus \{l\}$ における**最適配分**(i.e. $l$ 以外が申告した評価値$\boldsymbol{b}_{-l}$の総和を最大化する配分) | The optimal assignment for the market other than buyer $l$, $\mathcal{N} \setminus \{l\}$ (i.e. the assignment that maximizes the total value of buyers other than $l$, $\boldsymbol{b}_{-}$). ここで, **正直な申告**の下での配分$\boldsymbol{x}^{∗}$ は，目的関数 Since the optimal assignment for the truth declaration, $\boldsymbol{x}^{\ast}$, maximizes $$\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}$$ を最大化するから，任意の配分$\boldsymbol{y}$について，以下が成り立つ： the following should be satisfied for any assignment $\boldsymbol{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$ が**正直に申告した場合**の配分$\boldsymbol{x}^{\ast}$と，**虚偽を申告した場合**の配分 $\boldsymbol{y}^{\ast}$のそれぞれについて，この買手が得る利得は， The payoffs of buyer $l$ at the assignment for the truth declaration, $\boldsymbol{x}^{\ast},$ and that for the false declaration $\boldsymbol{y}^{\ast}$ respectively are $$\begin{align} \pi_{{\color{red}l}}(\boldsymbol{x}^{\ast}) &= \sum_{i} v_{i{\color{red}l}} x_{i{\color{red}l}}^{\ast} - \underbrace{\left( -\sum_{j \ne l} b_{j}(\boldsymbol{x}^{\ast}) + \sum_{j \ne {\color{red}l}} b_{j}(\boldsymbol{x}_{-{\color{red}l}}^{\ast})\right)}_{\text{$\boldsymbol{x}^{\ast}$の下での買手$l$のVCG価格}}\\ \pi_{{\color{red}l}}(\boldsymbol{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}(\boldsymbol{y}^{\ast}) + \sum_{j \ne {\color{red}l}} b_{j}(\boldsymbol{x}_{-{\color{red}l}}^{\ast})\right)}_{\text{$\boldsymbol{y}^{\ast}$の下での買手$l$のVCG価格}} \end{align}$$ と表される．ただし，$b_{j}(\boldsymbol{x}) = \sum_{i} b_{ij} x_{ij}$は，配分 $\boldsymbol{x}$ の下で買手 $j \ne l$ が得る(申告額ベースの)評価値である． ==買手 $l$ にとっては，他の買手が獲得するのが真の評価値であろうが，虚偽の評価値であろうが関係ない==． where $b_{j}(\boldsymbol{x}) = \sum_{i} b_{ij} x_{ij}$ is the (declared) value of buyer $j \ne l$ at an assignment $\boldsymbol{x}$. Note that for buyer $l$, it does not matter whether the other buyers obtain true or false values. どちらの式も右辺第3項が同じであるため，**正直な申告**と**虚偽の申告**の利得の差は， Since the 3rd term of the right-hand side of both equation are identical, the difference of payoffs of the **truth-telling** and the **false-telling** is $$\begin{align} \pi_{{\color{red}l}}(\boldsymbol{x}^{\ast}) - \pi_{{\color{red}l}}(\boldsymbol{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}$$ となる．ただし，最後の不等式は，上述した$\boldsymbol{x}^{\ast}$の最適性より導かれる． where the last inequality stems from the optimality of $\boldsymbol{x}^{\ast}$ above. 従って，買手$l$ は，いかなる評価値$\boldsymbol{b}_{l}$ を申告しようと，正直な申告(i.e. $\boldsymbol{b}_{l} = \boldsymbol{v}_{l}$)をした時以上の利得を獲得することはできない． Accordingly, buyer $l$ can not yield a higher payoff than the truth declaration (i.e. $\boldsymbol{b}_{l} = \boldsymbol{v}_{l}$), no matter what value $\boldsymbol{b}_{l}$ is declared. $\square$ # VCG価格の長所と短所 | Lovely but Lonely VCG Prices VCG価格に対しては，下記の**長所**と**短所**が指摘されている(Ausbel and Milgrom, 2005)． For the VCG price, the following advantages and disadvantages are known: ## 長所 | Advantages 1. **正直な申告**が **支配戦略** となる． **Truth-telling** is **(weekly) dominant** 2. マイルドな仮定の下で以下の3つの重要な要素を実現できる ==**唯一**== の**直接表明メカニズム**である: It is the **unique** direct revelation mechanism that can achieve the following important factors: a. **正直申告**が**支配戦略**となる. | The truth-telling is dominant. b. **効率的配分**が実現できる(i.e. 真の評価値の総和を最大化する). | Efficient (i.e. it maximizes the total truth value) c. **敗者の支払いが不要**である．| No payment is required for losers. 3. **組み合わせオークション**を含む，**より一般的な枠組**へも適用可能 It can be extended to more general framework including **combinatorial auctions**. ## 短所 | Disadvantages 1. ルールが判り難く, 大規模になると VCG **価格の計算** が大変(i.e. (勝者の数+1)個の割当問題を解く必要がある) The rule is complicated and the calculation of VCG price is demanding for a large scale (i.e. $N+1$ assignment problems should be solved). 2. **売手の収益**が **極めて低い**, もしくは**ゼロ**になる The seller's revenue will be very low or zero, sometimes. 3. **売手の収益**が**買手集合**や**買手の入札額**に対して**単調ではない** The seller's revenue is not monotone with respect to the number of buyers as well as their values. 4. **敗者同士の提携** や**匿名入札**(1人の買手が別人になりすます)に対して頑健でない It is not robust against **the losers coalitions** as well as **the false-named bid** (the case with a buyer pretending to be several different buyers). ただし，2〜4は買手が代替的(buyers are substitute)であれば(e.g. 単一需要)生じない． Note that from 2 to 4 above are not realized for the case when buyers are substitute (e.g. unit demand). さらに，残った1つ目の短所についても，**線形計画問題**に帰着する**割当問題**ならば，解決可能． The remaining disadvantage 1 also can be resolved when the assignment problem reduces to a LP. # VCG価格と双対問題の最適解 | VCG Price and Dual Optimal Solution :::info **割当問題**において，各買手が各財に対して支払う**VCG 価格**は**双対問題の最適解** $(\boldsymbol{p}^{\ast},\boldsymbol{π}^{\ast})$の中で**最小の価格**に一致する. (Demange et al., 1986) When the assignment problem is equivalent to a LP, the VCG prices are identical to the equivalent LP's dual optimal solution $(\boldsymbol{p}^{\ast},\boldsymbol{π}^{\ast})$ with minimal prices. ::: **VCG 価格**を **定義通り** に求めるには, Recall that the following problems should be solved to compute the VCG price as defined: - **最適割当**を求める問題 The assignment problem for the full market - 財を割当てられた買手(勝者)ごとのVCG価格を求める問題 The problem of finding the VCE price for each winner を解かなければならない. 勝者 (=財の供給量) が $N′$ なら $N′ + 1$ 個の割当問題を解く必要がある. It implies that we need to solve $N^{\prime}+1$ assignment problems, where $N^{\prime}$ is the number of winners. 一方，**割当問題** が **線形計画問題** に帰着する場合, 双対問題を **一度** 解くだけで以下が全て計算できる: When the assignment problem can be reduced to a LP, on the other hand, all of the following can be computed by solving the dual **only once**: - 各買手の**VCG価格**(最適解として求められる) The VCG price for every winner (as the optimal dual solution with minimum price) - **最適割当** (**相補性定理** から計算できる) The optimal assignment (from the complementarity theorem) 前々回の講義で紹介した**競り上げオークション**は，**最適配分**と**VCG価格**(=等価な線形双対問題の解)を**同時**に求められる**間接顕示**(各買手の評価値を直接申告させることのない)メカニズムとして位置付けられる(Demange et al., 1986; Bikhchandani and Ostroy, 2002,2006; de Vries et al., 2007). The ascending auction can be regarded as the indirect revelation mechanism (i.e. it does not require declarations of buyers' value directly) that obtains the optimal assignment as well as the VCG price, simulataneously. # 練習問題 | Exercise 第9回の講義で扱った下記の問題について， For the problem in Lecture #9, answer the following questions: 1. 学生1, 学生4, 学生5が支払うべき**VCG価格**を求めよ．なお，学生4にソーダが配分される場合と，コーラが配分される場合ではVCG価格は異なる．それぞれの場合についてVCG価格を求めよ． Obtain VCG prices of Students 1, 4 and 5. Note that VCG prices are different when soda is assigned to Student 4 and cola is assigned to Student 4. Find the VCG prices for each case. 2. 割当問題を線形計画問題に帰着させた場合の**双対問題の解** $(\boldsymbol{p}, \boldsymbol{\pi})$を求め，上記1.の解と比較せよ． Obtain the dual optimal solution $(\boldsymbol{p}, \boldsymbol{\pi})$ of the equivalent LP and compare those with the solution to 1. ||学生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>supply| |---|---|---|---|---|---|---|---| |ソーダ (soda) ($S$)|100|60|90|120|150|110|3| |コーラ (cola) ($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.