Ryuji Sano

(1)

組み合わせ時計オークション

（ The Combinatorial Clock Auction ）

佐野隆司

∗

京都大学経済研究所平成 28 年 5月 30 日

「コア選択オークション」は，近年，世界各国の周波数オークションで採用が広がりつつある．また，米国においては混雑空港の発着枠割り当てにコア選択オークションの採用が提案された．採用，あるいは提案されたオークションのルールは，単純な封印入札方式ではなく，価格せり上げ方式と封印入札方式を組み合わせた「組み合わせ時計オークション（Combinatorial clock auction^）」と呼ばれる極めて複雑なオークションルールである．この小論は，「コア選択オークション」を踏まえ，近年現実に採用されつつある組み合わせ時計オークションがどのようなルールであるかについて解説する．

近年英国やオランダ，デンマーク，オーストラリアなどの国の周波数割当オークションにコア選択オークションが実際に採用されている．これらの国で実際に用いられたオークションは「組み合わせ時計オークション（あるいはパッケージ時計オークション）」と呼ばれるもので，価格せり上げ方式と封印入札方式が混在した極めて複雑なオークションである．この補論では，組み合わせ時計オークションの具体的なルールを紹介する

1

．

VCGメカニズムやコア選択オークションなどの複数財オークションを現実に実施する際にしばしば問題となるのは，入札者が申告すべき情報量が膨大であるという点がある．例えば財の数が_K個あり，それぞれ異質な財であるとする．入札者が落札できる財の個数に上限がない場合，可能な財のパッケージの数は₂

K− 1^{個存在する．封印}

∗E-mail: [email protected]

1

本補論で紹介するオークションの背後にある理論的性質や背景については，カバーしない．興味のある読者は，Ausubel et al. (2006)^とCramton (2013)^{を参照せよ．}

(2)

入札型のコア選択オークションを仮に実施しようとするならば，各入札者は₂

K− 1^個の入札額を申告する必要があり，_Kが非常に小さな値でない限り現実的ではない．また，入札者自身が，全ての財のパッケージに対して，その評価価値を正確に把握しているとは考えにくい．

組み合わせ時計オークションは，「価格せり上げ方式」を取り入れることによって，この問題を緩和しようと試みている．価格せり上げ方式では，現在の価格のもとで，どの財のパッケージを需要するかを考えるだけで良く，全ての財のパッケージの価値を完全に認識できていなくてもビッドを出すことができる．また，部分的に観察される他の入札者の行動や，価格の推移を通じて，各財の「相場」のようなものを知ることができるだろう．これらの情報を通じて，各入札者は自身の価値評価を把握することができると思われる

2

．

組み合わせ時計オークションは，大きく₂つのステージによって構成される．第₁ ステージを「価格せり上げ（時計）ステージ」，そして第₂ステージを「封印入札ステージ」と呼ぶことにする．_K種類の財がそれぞれ複数単位配分され，その供給ベクトルを_L_{= (L}₁_,…_{, L}_K₎で表す．価格せり上げステージでは各財について価格がつけられており，価格ベクトルを_q_{= (q}₁_,…_{, q}_K₎で表す．以下では財のパッケージ_x_iはベクトルで表現することとし，可能なパッケージの集合_X_iを

Xi = {xi _{∈ Z}^K₊|0 ≤ xi≤ L}

とする³．任意の価格ベクトル_qに対する入札者_iの需要対応を Di(q) ≡ arg max

x_i∈Xi

vi(xi) − q · xi (1)

で表す．価格せり上げステージは複数ラウンドによって構成され，各ラウンドにおいて各入札者は，現在の価格ベクトルの下でどのような財のパッケージを需要するかを申告する．そして，各ラウンドで申告された需要をもとにして，次のラウンドの価格ベクトルが売り手によって決定される：

価格せり上げステージ

1. ^ラウンドt= 1とする．初期価格ベクトルを_q¹= (0, . . . , 0)^とする⁴^．

2

このようなせり上げの過程で得られる情報を用いた価値評価の把握はしばしば“price discovery”^と呼ばれており，価格せり上げ方式を採用する根拠の一つとしてしばしば言及される．

3

各入札者について，獲得できる財の上限等に何らかの制約が課されていても差支えない．

4

各財について任意に設定された最低入札価格を初期価格ベクトルとして構わない．

(3)

2. ^{各ラウンド}t= 1, 2, . . . において，各入札者は現在の価格ベクトルの下で需要する財のパッケージ_d_i_(q

t) ∈ Di(q^t)^{を申告する．}

3. ^{各人の申告}d(q^t) = (di(q^t))i∈N₋₀ をもとに，売り手は総需要を計算する．財_k について，もし

∑

i^d^ik^(q

t) > Lk^{であるならば，財}kの次のラウンドの価格を q^t+1_k = q^t_k+ ε^{とする．もし}^∑_idik(q^t) ≤ Lk^{であるならば，財}k^{の次のラウンド} の価格を_q

t+1

k ^{= q}

t

kと据え置き，次のラウンド_t_{+ 1}に移行し，₂に戻る． 4. ^ラウンドTにおいて，すべての財について

∑

i^d^ik(q^T) ≤ Lk^{となったとき，価}

格せり上げステージを終了する．

価格せり上げステージでは，入札者自身がビッドを出すのではなく，売り手が総需要に応じて価格を上げていく（それゆえ「時計」オークションと呼ばれる）のが特徴である．直感的には価格せり上げステージの終了時点の価格と需要によって財配分と支払い額を定めてしまえばよいように思われるが，組み合わせ時計オークションでは価格せり上げステージはオークションの「準備」に過ぎない．価格せり上げステージに続いて，第₂ステージの封印入札ステージに移行する．なぜ価格せり上げステージのみから構成されるオークションにしないのか，その問題点については後述することにする．

封印入札ステージは，原則的には単純な封印入札を行う．すなわち，各入札者は自分の価値評価関数_v_ˆ_iを売り手に申告する．そして，この申告された価値評価関数の組を用いてコアの配分を計算する：

封印入札ステージ

1. 各入札者は，自分の価値評価関数_v_ˆ_iを売り手に申告する．申告された価値評価関数の組をもとに，コアに属するように財配分と支払い額を決定する．

最終的な財配分と支払額は封印入札ステージで申告される価値評価情報のみによって行われる．価格せり上げステージでは，様々な価格ベクトルに直面し，そのとき需要する財のパッケージを申告する過程を通して，入札者は様々な財のパッケージの評価価値を把握することができる

5

．また，他の入札者の需要や価格の推移を観察することで，自身がどのような財を獲得できそうかが把握できるかもしれない．価格せり上

5Price discoveryは，標準的なオークション理論が想定するような私的価値・独立価値の仮定が成り

立っていないことを示唆している．しかしながら，これらの仮定をはずした相互依存価値モデルで複数財オークション、特に組み合わせオークションを扱った研究はほとんどない．

(4)

げステージは，このような「価値（価格）発見」の効果を通じて，封印入札ステージにおける価値評価関数の申告を補助する役割を担っている．

しかし，価格せり上げステージと封印入札ステージの間に何の関連性もなければ，価値発見の効果が期待できないだけでなく，戦略的な入札行動を助長したり，あるいは入札者間の談合の温床になりかねない．そこで，価格せり上げステージの進行を円滑にし，価値発見および封印入札ステージでの入札補助の効果を適切に生み出すための様々な制約が課されている．この制約を「行動ルール（activity rule^）^{」と呼び，組み} 合わせ時計オークションにおける極めて重要な設計要素になっている．

行動ルールは一意に決まったものではない．代表的なものとして，「ポイント行動ルール（eligibility point rule^）」と「顕示選好行動ルール（revealed preferences rule^）^」がある．

ポイント行動ルール

ポイント行動ルールは主として価格せり上げステージで課される制約である．大雑把にいうと，「価格せり上げステージにおいて，需要する財の総個数を途中で増やしてはならない」というものである．価格せり上げステージの各ラウンドにおいて，入札者は直前のラウンドで申告した財の総個数を超える財のパッケージは申告できない．同様のルールは₁₉₉₄年に米国の周波数オークションで採用された「同時せり上げオークション」でも採用されている．財の品質に大きな差がある場合は，財の種類ごとに財の品質を反映した「入札ポイント」をあらかじめ設定し，財の総個数の代わりに，財のパッケージの総ポイント数について同様の単調性を制約として課す方法がある．

顕示選好行動ルール

顕示選好行動ルールは，価格せり上げステージおよび封印入札ステージで課されるもので，「顕示選好に矛盾が生じるような申告をしてはならない」という制約である．言いかえると，価格せり上げステージの各ラウンドの価格と申告された需要について，それらの情報と矛盾しない価値評価関数が必ず存在することを要求するものである．更に，封印入札ステージでは，そのような矛盾しない価値評価関数のみを申告することができる．

具体的には価格せり上げステージのラウンド_tでは以下のように制約が課せられる．入札者_iが価格せり上げステージにおいて正直に入札しているのであれば，ラウンド

(5)

s < tにおいて申告された需要_d_i_(q

s)^{と，現在のラウンド}tにおいて申告される需要_x_i は以下の不等式を満たしているはずである：

vi(di(q^s)) − q^s· di(q^s) ≥ vi(xi) − q^s· xi, vi(xi) − q^t· xi ≥ vi(di(q^s)) − q^t· di(q^s).

この₂式を足すことで，

(q^t− q^s) · (xi− di(q^s)) ≤ 0 (2) が得られる．入札者_iがラウンド_tで申告できる需要は

{xi ∈ Xi|(q^t− q^s) · (xi− di(q^s)) ≤ 0(∀s < t)}

の範囲内に制限される．

更に，封印入札ステージにおいて申告する価値評価関数_ˆ_v_i_(x_i₎は，任意の_x_i _{∈ X}_i と任意の価格せり上げステージのラウンド_tにおける価格と需要について，

ˆ

vi(xi) ≤ ˆvi(di(q^t)) + q^t· (xi− di(q^t)) (3)

によって評価額の上限が設定される．更に価格せり上げステージ内において申告された需要については，

ˆ

vi(di(q^t)) ≥ q^t· di(q^t) (4)

を満たさなければならない．

現実には，これらの制約の一部のみを課すような「緩和された顕示選好行動ルール」を考えることも可能である．例えば，価格せり上げステージにおいては，過去のラウンド全てについて₍₂₎を課すのではなく，直前のラウンドとの間にだけ顕示選好制約を課す，すなわち

(q^t− q^t−1) · (xi− di(q^t−1)) ≤ 0 (5) のみを制約として課す方法も考えられる．

混合型行動ルール

実際に各国の周波数オークションで採用されているのは，ポイント行動ルールと顕示選好行動ルールの混合型である．入札者の立場からすると，顕示選好行動ルールに比べてポイント行動ルールの方が分かり易い．よって，価格せり上げステージでは原

(6)

則的にポイント行動ルールを採用する．その一方で，封印入札ステージで申告できる価値評価関数について，部分的な顕示選好行動ルールを課している．以下のように混合型行動ルールは定義される：財ベクトル_x_iの財の個数（あるいは_x_iの総入札ポイント数）を_|x_i_|で表す．

1. 価格せり上げステージの各ラウンド_tでは

|di(q^t)| ≤ |di(q^t−1)| (6)

を満たす（ポイント行動ルール），

2. 価格せり上げステージの最終ラウンド_T における申告需要がゼロベクトルでない場合，

ˆ

vi(di(q^T)) ≥ q^T · di(q^T) (7) を満たす，

3. 価格せり上げステージの最終ラウンド_T における申告需要がゼロベクトルである場合，ゼロベクトルでない需要を申告した最後のラウンドを_Sとして，

ˆ

vi(di(q^S)) ≤ q^S+1· di(q^S) (8)

を満たす，

4. ^{任意の財ベクトル}xiについて，価格せり上げステージで_|x_i_{| > |d}_i_(q

S)|^を満たす最小のラウンド_Sについて，

ˆ

vi(xi) ≤ ˆvi(di(q^S)) + q^S· (xi− di(q^S)) (9)

を満たす．

価格せり上げステージの最終ラウンドで空でない財を申告している場合，最終ラウンドで申告した財のパッケージ及び，それより小さい財のパッケージについては評価価値に上限を設けない．しかし，より大きい財のパッケージについては，そのパッケージが申告できなくなったラウンドの価格と需要に対して顕示選好の制約を課している．制約式₍₉₎はしばしば“relative cap”^{と呼ばれる}⁶．価格せり上げステージの最終ラウンドで空でない財パッケージを申告していた場合，封印入札ステージで申告できる評

6(8)^は(9)の特殊ケースであることに注意せよ．

(7)

価額には上限がない．しかし，異なるパッケージ間の評価額の差（相対的な価値評価）について，価格せり上げステージでの申告に応じて制約が課されている．混合型行動ルールを実行する際には，サイズの小さいパッケージから順番に評価額を入力する必要がある．

単純なせり上げオークションの問題点

以上が組み合わせ時計オークションの概要である．素朴な疑問として，なぜ価格せり上げステージの結果を最終的な配分としないのだろうか．価格せり上げステージの結果によって配分と支払い額を定める「単純なせり上げオークション」は，効率性・インセンティブの双方の面で不十分であることが知られている．

第₁の問題点は補完性の問題である．仮に各入札者が各期の価格に対して常に正直に需要を申告し，価格せり上げステージで需給が完全に一致して終了したとするならば，その時の配分と価格はワルラス均衡に他ならず，配分は効率的である．しかしながら，財の補完性がある場合，価格せり上げステージでは需給が完全に一致して終了することが保証されず，一般に超過供給が発生する

7

．従って，入札者のインセンティブを考慮しなかったとしても，単純なせり上げオークションでは効率的な配分を達成することは保証されない．

財が全ての入札者にとって代替財になっている場合は，価格せり上げステージの価格は概ねワルラス均衡に収束し，効率的な配分を発見することが可能である（_{Gul and}

Stacchetti, 2000^）. ^しかし第2の問題点として，入札者のインセンティブの問題が

残っている．単純なせり上げオークションでは，入札者は自分のビッドが一定の価格支配力を持っているため，過少入札をするインセンティブがあることが知られている

（Ausubel and Cramton, 2002^）^．Ausubel (2006)で提案されている手法を使って，各入札者の支払い額を最終的なワルラス均衡価格とは別に計算することで，正直に入札するインセンティブを与えることは実は可能であるが，単純なせり上げオークションの結果は一般に_VCGメカニズムのそれとは異なり，個人合理性を満たさない

8

．

7

非分割補完財の場合，ワルラス均衡の存在自体が保証されない．

8Ausubel (2006)^{は，入札者の人数}ⁿに対して価格せり上げステージをn_{+ 1}回実行することで，_VCG メカニズムの支払い額を計算する手法を提示している．

(8)

その他の論点

その他オークションルールの設計において実践的に重要になりうる論点をいくつか列挙しておく．

• オークションにかけられる個々の財が異質であるほど，可能なパッケージの数は指数的に増えてしまう．完全に同質ではないが，ほとんど同質財だと考えられる財については，便宜的に同質財として取り扱うことで，この問題を多少緩和することができる．周波数オークションの文脈で言えば，他の用途で使用されている帯域と接している周波数帯免許は，電波干渉のおそれなどから，他の免許に比べて質が劣ると予想される．しかし，このような異質性を無視して，一定の周波数帯域の免許を全て同質財として扱うこともできる

9

．一旦同質財として扱い，オークションで各入札者が「何単位の免許を獲得するか」を決定したのち，各入札者が具体的にどの免許を獲得するかを決定する．この最終的な配分を決定する段階は「割り当てステージ（Assignment Stage^）^{」と呼ばれる．}

• 現実のほとんどの事例では各財に対して最低入札価格が設定される．最低入札価格をいくらに設定するかによって，各人の支払額が大きく変わる可能性がある¹⁰．

価格せり上げステージと封印入札ステージからなる極めて複雑なルールであるが，基本的なコンセプトは，価格せり上げステージによって，各入札者自身が自分の価値評価をより正確に認識した上で，最終的には封印入札ステージで配分を決めようというものである．したがって，前半の価格せり上げステージは，オークションそのものというよりもいわば入札者の「価値発見」の為の補助ステージである．しかし一方で，価格せり上げステージでの申告が，封印入札ステージで申告できる評価額を強く制限することになるため，価格せり上げステージでいい加減な申告をすることが難しくなっている．また，オークションのインターフェイスを工夫すれば，価格せり上げステージで申告された情報を用いて，封印入札ステージにおける入札額の入力にかかるコストを大幅に削減することが可能となるだろう．現実の周波数オークションでは封印入

9

このように異質性の小さい異質財を「同質化」した財をgeneric goods^と呼ぶ．

10Sano (2012)によれば，組み合わせ時計オークションの均衡での効率性，収入双方について最低入札

価格の影響が大きいことがあることが示唆される．

(9)

札ステージでコア選択オークションが用いられたが，_VCGメカニズムに代替することも可能である．

参考文献

[1] Ausubel, L.M. (2006) “An Efficient Dynamic Auction for Heterogeneous Com- modities,” American Economic Review, Vol. 96, pp. 602-629.

[2] Ausubel, L.M. and P. Cramton (2002) “Demand Reduction and Inefficiency in Multi-Unit Auctions,” mimeo, University of Maryland.

[3] Ausubel, L.M., P. Cramton and P. Milgrom (2006) “The Clock-Proxy Auction,” in P. Cramton, Y. Shoham and R. Steinberg (Eds.), Combinatorial Auctions, MIT Press.

[4] Cramton, P. (2013) “Spectrum Auction Design,” Review of Industrial Organiza- tion, Vol. 42, pp. 161-190.

[5] Gul, F., and E. Stacchetti (2000) “The English Auction with Differentiated Com- modities,” Journal of Economic Theory, Vol. 92, pp. 66-95.

[6] Sano, R. (2012) “Non-Bidding Equilibrium in an Ascending Core-Selecting Auc- tion,” Games and Economic Behavior, Vol. 74, pp. 637-650.