特集●エージェント
VCG-equivalent in Expectation
メカニズム
藤田 悦誌 岩崎 敦 東藤 大樹 横尾 真
本論文では，新しい公開型オークションメカニズムのクラスとして，VCG-equivalent in expectation メカニズム を提案する．正直な戦略の組が事後ナッシュ均衡となる公開型オークションメカニズムはクエリの回答が回答者の財 の割当と支払額に影響を与えない無関係なクエリを送信する必要がある．露呈される情報に関して参加者が弱い誘因 を持つ場合，無関係なクエリを送信するメカニズムは望ましくない．本論文で新しく提案する VCG-equivalent in expectation メカニズムは，割当は Vickrey-Clarke-Groves (VCG) メカニズムと等しく，支払額は VCG の支払 額の期待値とするメカニズムである．本論文では，VCG-equivalent in expectation メカニズムにおいて，正直な 戦略の組が逐次的均衡となること，及び，無関係なクエリを送信しない VCG-equivalent in expectation メカニズ ムを構築する手法を示した．さらに，提案メカニズムの現実的な応用事例への適用可能性を示すため，日本の第四世 代の周波数オークションに適用可能なメカニズムを示した．In this paper, we develop a new class of iterative mechanisms called a VCG-equivalent in expectation mech-anism. To guarantee that sincere strategies are an ex post equilibrium, it inevitably asks an irrelevant query, in which a participant has no incentive to answer the query sincerely. Such an irrelevant query causes unnecessary leakage of private information and a different incentive issue. In a VCG-equivalent in expec-tation mechanism, the mechanism achieves the same allocation as VCG, but the transfers are the same as VCG only in expectation. We show that in a VCG-equivalent in expectation mechanism, sincere strategies constitute a sequential equilibrium. Also, we develop a general procedure for constructing a VCG-equivalent in expectation mechanism that does not ask any irrelevant query. To demonstrate the applicability of this idea in a practical application, we develop a VCG-equivalent in expectation mechanism that can be applied to the Japanese 4G spectrum auction.
1 序論
一般にVickreyオークションのような封印型のオー クションよりも，英国型などの公開型オークションの 方が好まれることが多い [13]．公開型の利点として， 公開型では参加者は逐次的に意思決定を行うことが でき，自身の評価値(タイプ)に関する完全な情報をVCG-equivalent in Expectation Mechanism. Etsushi Fujita, Taiki Todo, Makoto Yokoo, 九州大学
大学院システム情報科学府, Graduate School of ISEE, Kyushu University.
Atsushi Iwasaki, 電 気 通 信 大 学 大 学 院 情 報 シ ス テ ム 学 研 究 科 社 会 知 能 情 報 学 専 攻, Graduate School of Information Systems, University of Electro-Communications. コンピュータソフトウェア, Vol.31, No.3 (2014),pp.156–167. [研究論文] 2013 年 7 月 5 日受付. 他者に露呈する必要がない点が挙げられる．また，周 波数帯域の使用権のような公共物を対象とする場合 に，参加者の意思決定の過程が明らかとなる，透明性 のある公開型メカニズムが望まれている．実際，現実 に行われているオークションの多くは公開型である． 組合せオークションとは，複数種類の財が同時に販 売され，参加者は財の組合せ(バンドル)に対して入 札するオークションであり，参加者の補完的・代替的 な選好を考慮することで，社会的余剰(オークショニ アを含む参加者全員の効用の総和)を増加させること ができる [17]．よく知られたVickrey-Clarke-Groves メカニズム(VCG)[6] [10] [15]は，正直入札が支配戦 略となり，パレート効率的な割当(社会的余剰が最大 となる割当)を実現する等の理論的に望ましい性質を 持つ封印型の組合せオークションメカニズムである．
他の入札者の行動が観測可能な公開型の組合せオー クションでは，観測結果に基づいて非合理的な行動を 取るような他の入札者が存在する可能性がある．こ のような状況において，正直入札が支配戦略となる ことを保証するのは一般には不可能である．したがっ て，次善の策として正直戦略の組が事後ナッシュ均衡 となること，すなわち，他の参加者が正直戦略を用い るならば自身も正直戦略を用いることが最良となる ことが望まれる．参加者のタイプに特別な仮定を置か ない一般的な設定において，正直戦略の組が事後ナッ シュ均衡となり，かつパレート効率的な割当を実現す る公開型オークションメカニズムはVCGと等価な結 果を得るメカニズムに限定されることが示されてい る [16] [12]． 本論文で扱う抽象化されたモデルでは，公開型の オークションは，各参加者にメカニズムが逐次的に “yes/no”で答えられる質問またはクエリを行うメカ ニズムとして表現される．このモデルにおいてVCG と等価な結果を得るためには，クエリの回答が回答者 の財の割当と支払額に影響を与えないという意味で の回答者にとって無関係なクエリを送信することが 避けられないことが示される．したがって，VCGと 等価な結果を得るためには，パレート効率的な割当 に必要な情報を得た，すなわち，勝者が決定した後で あっても，勝者の支払額を計算するためにクエリを送 信する必要がある．このようなクエリは，クエリの対 象者自身の割当及び支払額には影響を与えない． メカニズム設計においては，簡単のため，正直に行 動しても嘘をついても効用が変化しない場合は，参 加者は正直に行動するという前提が置かれることが 通例である．この前提の下では，参加者は無関係なク エリに対して正直に答えると考えることができるが， 露呈される情報に関して参加者が，弱い誘因を持つ場 合は，この前提が成立しない可能性がある．例えば， 参加者が自身のタイプを正確に認識するためにコス トまたは労力が生じる場合，参加者はこのコストまた は労力を省くために，無関係なクエリに対してランダ ムに返答する可能性がある．さらに，参加者は，自身 の効用が変わらないなら，他者に露呈される自身の評 価値またはタイプに関して，なるべく小さく見せたい という誘因を持つ可能性がある．例えば，自身の効用 が非常に大きいにも関わらず，安価で落札できた参加 者は社会的に非難される可能性がある．財が1つだ けのオークションでは，英国型オークションを用いる ことにより，勝者の評価値を公開することは避けられ るが，一般の組合せオークションでは勝者の評価値の 露呈を完全に避けることは一般には不可能である． このような弱い誘因の問題を避ける方法として，参 加者の入札の情報，もしくはオークションの手順を非 公開にするという方法が考えられる．他の参加者のク エリの回答やクエリの送信の順序が分からなければ， 現在のクエリが無関係かどうかの判断が困難となる． しかしながら，周波数帯域の使用権のような公共物を 対象としたオークションのメカニズム設計を考える 場合，メカニズムの透明性が強く求められ，クエリの 情報やオークションの手順を非公開にすることは望 ましくない．原理的には，参加者に一切情報を与えな ければ，無関係なクエリを送信することなく，メカニ ズムは全ての参加者のタイプを知ることができるが， そのようなメカニズムは封印型オークションメカニズ ムと等価であり，評価値またはタイプに関する完全な 情報の露呈を必要としないという公開型の利点を失っ ている． これまでの議論を要約すると，公開型の組合せオー クションメカニズムの設計にあたって，以下のような ジレンマに対応する必要がある．参加者に(事後ナッ シュ均衡として)正直申告の誘因を与えるためには， メカニズムは無関係なクエリを送信することが避け られない．一方，無関係なクエリは，タイプに関する 情報を露呈し，新たな誘因に関する問題が生じる． 1. 1 本研究による成果 本論文では，前節で述べたジレンマを解決するため に，新しいメカニズムのクラス(VCG-equivalent in expectationメカニズム, VCG-EE)を提案する．こ のクラスのメカニズムは，VCGと完全に等価な結果 ではなく，正直申告が事後ナッシュ均衡とならない が，期待値としてVCGと等価である．より厳密には VCG-EEでは，割当はVCGと同じくパレート効率 的な割当を実現するが，勝者の支払額はVCGにおけ
158 る支払額の期待値と等しくする．すなわち，VCG-EE では，パレート効率的な割当が判明した時点で，それ 以上のクエリの送信を行わなくてよい．VCGの支払 額を計算するための情報を得ていない場合，具体的 には，一部の参加者の評価値が正確には分かっておら ず，勝者の支払額が厳密に計算できない場合に，これ らの参加者の評価値の分布を用いて，VCGの支払額 の期待値を求める． VCG-EEは期待値や評価値の分布を用いているた め，正直戦略の組が事後ナッシュ均衡となることは 保証されない．このような，評価値またはタイプの 分布に関する事前の知識が存在し，メカニズムの実 行中に他者のタイプが逐次的または部分的に判明す る状況は不完備情報展開型ゲームとして表現できる． 不完備情報展開型ゲームにおいて最も洗練された均 衡概念として逐次均衡 [11]が存在する．本論文では， VCG-EEにおいて，正直戦略の組が逐次均衡となる こと，すなわち，他者が正直戦略を用いる限り，他者 のタイプに関する事前の知識と，メカニズムの実行途 中で得られた情報を加味して得られる，他者のタイプ の分布に関する信念の下で，自身も正直戦略を用いる ことが期待効用を最大化することを示す． 本論文では厳密な分析を行うため，二分決定木 (BDT)に基づいた公開型メカニズム(BDT-basedメ カニズム)を定義する．BDT-basedメカニズムは， 二分決定木のノードにおいて，参加者を1人選び，そ の参加者のタイプに関する“yes/no”型のクエリ，例 えば，この財に対する評価値は100ドルより大きい か否か，という形式のクエリを送信する．メカニズ ムが参加者のタイプについて十分な情報を得たとき， 財の割当と支払額を決定する．本モデルでは，クエリ の情報が参加者に対して完全に公開されていると仮 定する．すなわち，公開型メカニズムにおいて，全て の参加者は全ての参加者の入札情報の履歴を参照で きるものとする． 1. 2 例: チャリティのためのオークション チャリティのためのオークションを用いて，露呈さ れる情報に関して参加者が，弱い誘因を持つ場合に， 参加者が正直に行動しない例を示す． チャリティのためのオークションにおいては，参加 者は自身の評価値が小さいことが露呈することを望 まない可能性がある．この状況では，敗者の評価値を 公開し，勝者の評価値を秘匿する英国型を利用するこ とは望ましくない．評価値の露呈に関する弱い誘因を 考慮しなければ，以下に示すダッチ(競り下げ)オー クションの変形版により，正直申告が事後ナッシュ均 衡となることを保証できる．例えば，参加者は2人 (A, Bとする)，販売する財は1個として，価格を競 り下げていく過程で，価格が9ドルのときにAがス トップを宣言したとする．通常のダッチオークション では，この時点でオークションは終了し，Aが9ド ルで落札するが，この変形版ではオークションはまだ 終了せず，Bがストップと言うまで価格は下がり続け る．価格が5ドルのときにBがストップを宣言した とすれば，Aは5ドルで財を購入する． このメカニズムは良く知られたVickreyオークショ ンに対応しており，理論的には正直申告が事後ナッ シュ均衡となる．しかしながら，この状況では，Bに は財が割り当てられないことが明らかであり，Bは 正直に行動する強い誘因を持たない．Bが財を落札 しない範囲で，自身の評価値をなるべく大きく見せ たいという，弱い誘因を持つ場合，A が9ドルでス トップを宣言した後に，直ちにストップを宣言するこ とにより，自分の評価値を実際よりも高く見せること が可能になる．変形版ダッチオークションのような， メカニズムの単純な変形を行うと，このような問題が 生じるのは当然だと思われるかもしれないが，VCG と等価な結果を得る組合せオークションは，この変形 版ダッチオークションと同様に無関係なクエリを送信 することが避けられない． しかし，この変形版ダッチオークションにVCG-EE のアイデアを適用した場合，Aがストップを宣言し た時点でオークションは終了し，Bの評価値の期待値 がAの支払額となる(Bの評価値が一様分布に従う ならば，支払額は4.5ドルとなる)．したがって，露 呈される情報に関する弱い誘因の問題を解決するこ とができる．
2 関連研究
競り上げ式組合せオークションメカニズムに関し ては数多くの研究事例があり [1] [2] [3] [16] [12]，競り 上げ式組合せオークションにおけるメカニズムと参 加者の間の通信量，効率的な参加者の選好獲得方法 等も議論されている[4] [5] [7] [14]. 選好獲得に関する研 究 [7] [14]で用いられている精巧なモデルと比較する と，BDT-basedモデルは抽象的であり，選好獲得で 議論されている課題を表現するには不十分であるこ とが予想される．一方，BDT-basedモデルは単純で 均衡の確認が容易であり，競り上げ式オークションを 含む多くのメカニズムをモデル化するのに十分な一 般性を持つ． メカニズムデザインにおいて，期待値を用いるア プローチは古くから存在する．例えば，良く知られ た-externalityメカニズム [8] は，参加者の他者に 与える外部性の期待値を用いて，ベイジアンナッシュ 誘因両立性，パレート効率性，予算均衡を満たすメ カニズムを実現している．VCG-EEのアイデアは， expected-externalityメカニズムに触発されて生まれ たものである．3 モデル
本論文では以下の組合せオークションのモデルを用 いる．非分割財の集合をM ={1, · · · , m}とし，参 加者の集合をN ={1, · · · , n}とする．参加者 iの タイプは独立に集合Θi から選ばれる．簡単のため， Θiは可算有限集合と仮定する．各参加者iの真のタ イプθiは，参加者iのみが知っており，他者及びメ カニズムは知らない個人情報である．タイプがθi の 参加者iが財の集合またはバンドルB⊆ M を得たと きの効用をv(θi, B)と表す．更に，vはv(θi,∅) = 0 で正規化され，自由可処分性，すなわち任意のバンド ルの組B⊆ B′ に関して，v(θi, B)≤ v(θi, B′)が成 立することを仮定する． 参加者の効用については準線形効用を仮定する．す なわち，タイプがθi の参加者がバンドルB および 金銭による補償tiを得た場合の効用はv(θi, B) + ti で与えられるものとする(オークションでは勝者は支 払いを行うためti は負の値となる．すなわち，−ti はBに対する支払額を表す). 参加者iのタイプがθiである確率をp(θi) > 0と し，∑θ i∈Θip(θi) = 1が成り立つとする．各参加者 及びメカニズムにとって， pは共通知識とする．ま た，Θ′i⊆ Θiについて，p(Θ′i)を ∑ θi∈Θ′ip(θi) と定 義する．Θを∏i∈NΘi，Θ−iを∏j̸=iΘj とする． 更に，θ = (θ1,· · · , θn) ∈ Θを参加者全員のタイ プのプロファイルとする．また，θ−i∈ Θ−iをiを 除いた参加者のタイプのプロファイルとする．さら に，i のタイプが θi で，i 以外の参加者のタイプ のプロファイルがθ−iであるタイプのプロファイル を，(θi, θ−i)と記述する．p(θ)を∏i∈Np(θi)とし， p(θ−i)を∏j̸=ip(θj)と定義する． 実 現 可 能 な 割 当 の 集 合 を X と し ，X = (X1,· · · , Xn) ∈ X と表す．ただし，Xi⊆ M は参 加者iに対する割当である．実現可能な割当X∈ X に つ い て ，Xi∩ Xj = ∅(i ̸= j) が 成 り 立 つ ．割 当 X ∈ X，タイプのプロファイル θ ∈ Θ につい て，∑i∈Nv(θi, Xi′) > ∑ i∈Nv(θi, Xi)を満たす割当 X′∈ X が存在しないとき，Xは(θ, M )についてパ レート効率的な割当であるという． 参加者に対して，そのタイプを直接尋ねるメカニズ ムを直接顕示メカニズムと呼ぶ．直接顕示メカニズ ムは割当関数a : Θ→ X と補償関数t : Θ→ Rn に より定義される．aは，申告されたタイプから割当を 決定する関数で，a(θ) = (a1(θ),· · · , an(θ))と表す． tは，申告されたタイプから金銭による補償を決定す る関数で，t(θ) = (t1(θ),· · · , tn(θ))と表す． VCGメカニズムは，次の割当関数a∗と補償関数 t∗により定義される直接顕示メカニズムである． 定義1 (VCGメカニズム). • a∗(θ) = X. ここでX∈ X はθに対するM の パレート効率的な割当． • t∗ i(θ) = ∑ j̸=iv(θj, Xj)− ∑ j̸=iv(θj, Xj′). こ こでX′ ∈ X は ∑j̸=iv(θj, Xj′)を最大化する 割当． VCGについて，簡単な例を用いて説明する． 例 1. 財 の 集 合 が M = {1, 2}， 参 加 者 の 集 合 が N = {1, 2, 3} と す る ．参 加 者 1 は 財 1 に ，160 参加者 2 は財 2 に，参加者 3 は財 1 と財 2 の セットに対して評価値を持つ．評価値は一次元で 表 せ る た め ，各 参 加 者 の タ イ プ を 評 価 値 で 表 す． Θ1 = Θ2 = {2, 4, 6, 8}, Θ3 = {9}とし，各タイプ は独立であり，一様分布に従うとする．θ = (2, 2, 9) ならば，a∗(θ) = (∅, ∅, {1, 2}), t∗(θ) = (0, 0,−4)と なる．θ = (8, 8, 9) ならば，a∗(θ) = ({1}, {2}, ∅), t∗(θ) = (−1, −1, 0)となる．
4 二分決定木
本章では公開型オークションメカニズムを形式的に 表現するための枠組みである(全)二分決定木に基づ いたメカニズム(BDT-based メカニズム)を導入す る．BDT-basedメカニズムでは，メカニズムがある 参加者に“yes/no”クエリを送信するタイミングが二 分決定木の(葉ノードを除く)各ノードに対応してお り，オークションの結果が葉ノードに対応している． 定 義 2 (BDT-based メ カ ニ ズ ム). N, M, Θ が 与 え ら れ た と き ，BDT-based メ カ ニ ズ ム は ⟨dr, Din, Dl, int, q, ¯a, ¯t⟩ により定義される．Din は 内部ノードの集合，Dl は葉ノードの集合である． dr∈ Dinはルートノードである．ノードd∈ Din∪Dl の親ノードを p(d) ∈ Din とする．また，ノード d ∈ Din の左の子を lc(d), 右の子を rc(d)とする (lc(d), rc(d)∈ Din∪ Dl)． d∈ Dinにおいて，int(d)∈ N はクエリの対象で ある参加者，q(d)⊂ Θint(d)はクエリである．¯aは割 当関数，¯tは補償関数である． 各ノードdでは，参加者int(d)∈ N に対して，自 身のタイプがq(d)⊂ Θint(d) に含まれるか否かとい うクエリが送信される．ノードdの入力はn次の超 立方体(低次に縮退したものも含む) Θd=∏i∈NΘdi である．ただし，Θd i ⊆ Θi である．以降， ∏ j̸=iΘdj をΘd −iとする． 定義 3 (ノードの入力). ノードdの入力は，以下で 定義される． • d = dr について，その入力はΘである． • d ̸= drについて，p(d) = d′, int(d′) = i, q(d′) = Θ′iとするとき，dの入力Θdは, d = lc(d′)なら ばΘ′i×Θd ′ −i，d = rc(d′)ならば(Θd ′ i \Θ′i)×Θd ′ −i {2}x{2} lose (0,0) {2}x{4} lose (0,0) {2}x{6} lose (0,0) {2}x{8} win (-1,-7) {6}x{2} lose (0,0) {8}x{2} win (-7,-1) {4}x{4} lose (0,0) {4}x{6,8} win (-2,-5) {4}x{2} lose (0,0) {6,8}x{4,6,8} win (-3,-2) θ1≦2? θ2≦2? θ2≦2? θ1≦4? θ1≦4? θ2≦4? θ2≦4? θ1≦6? θ2≦6? yes yes yes yes yes no no no no yes no yes no no yes no yes no 図 1 二分決定木の例 である． メカニズムは ルートノードdrから開始される．現 在のノードがdのとき，クエリq(d)の回答が“yes” ならば，lc(d)に，回答が“no” ならば，rc(d)に移 動する．入力Θdはクエリにより2つの超立方体に 分割される． ここで，クエリは空集合を入力とするノードが存在 しないように定義されている．すなわち，各ノードd について，int(d) = iとしたとき，q(d)⊂ Θdi が成り 立っている(真部分集合であることに注意されたい). 葉ノード d∈ Dl に移動したとき，メカニズムは オークションの結果¯a(Θd), ¯t(Θd)を出力する．定義2 に示している通り，¯aは割当関数，¯tは補償関数であ り，Θ′⊂ Θを入力とする． 図1に例1の組合せオークションに適用した BDT-basedメカニズムの例を示す．参加者3のとりうる タイプは唯一であるため，参加者1, 2のタイプにつ いてのみ考える．葉ノードの“win” は財 1 が参加 者1 に，財2 が参加者2 に割り当てられることを 表す．“lose”は両方の財が参加者3に割り当てられ ることを表す．このBDT-basedメカニズム は財1 と財2の価格が交互に上がる競り上げ式オークショ ンと等価である．この場合，ルートノードの入力は {2, 4, 6, 8}×{2, 4, 6, 8}となる．最初のクエリ(θ1≤ 2 ?)により，ルートノードの入力は{2} × {2, 4, 6, 8} と{4, 6, 8} × {2, 4, 6, 8} に分割される．前者はルートノードの左の子の入力，後者はルートノードの右の 子の入力となる．ルートノードの左の子について，ク エリ(θ2≤ 2 ?)により，{2} × {2}と{2} × {4, 6, 8} に分割される．他のノードについても同様である． このメカニズムは，参加者のタイプのプロファイ ルが一意に定まらなくとも，割当と補償を決定でき る．例えば，一番右の葉ノードでは，参加者1のと りうるタイプは{6, 8}，参加者2のとりうるタイプ は{4, 6, 8}である． 以下，BDT-basedメカニズムに関する性質を定義 する．まず最初にVCG-equivalenceを定義する． 定義 4 (VCG-equivalence). 任意の葉ノードd に ついて，∀θ, θ′ ∈ Θd, a∗(θ) = a∗(θ′) = ¯a(Θd) かつ t∗(θ) = t∗(θ′) = ¯t(Θd)を満たすBDT-basedメカニ ズムはVCG-equivalentであるという． 図1で表現されるメカニズムは濃い影つきの葉ノー ド(一番右から2つの葉ノード)を除いた葉ノードに ついて，VCG-equivalentの条件を満たしている． 次 に ，提 案 す る フ レ ー ム ワ ー ク で あ る
VCG-equivalent in expectationメカニズム(VCG-EE)を 定義する．
定義5 (VCG-equivalence in expectation (VCG-EE)).
任意の葉ノードdについて，次の条件を満たす BDT-basedメカニズムはVCG-EEであるという． • ∀θ, θ′ ∈ Θd , a∗(θ) = a∗(θ′) = ¯a(Θd) が成り立 つ．すなわち，任意の葉ノード，その葉ノードに 入力される任意のタイプのプロファイルについ て，パレート効率的な割当が存在する． • 補償関数¯t(Θd)が次式で与えられる． ¯ ti(Θd) = ∑ θ−i∈Θd −i t∗i((θ d i, θ−i))× p(θ−i) p(Θd −i) ここで，θd i はΘdi に含まれる任意のタイプで ある． VCG-EEにおいて，任意の葉ノード dについて， ∀i ∈ N, ∀θi, θi′ ∈ Θ d i,∀θ−i ∈ Θ d −i, t∗i((θi, θ−i)) = t∗i((θ′i, θ−i))が成り立つことに注意されたい．¯ti(Θd) は，iを除く参加者のタイプのプロファイルの集合 Θd−iに関するVCGの補償の期待値に等しい． 図1で表現されるメカニズムは，VCG-EEの例と なっている．一番右の葉ノードでは，{6, 8}×{4, 6, 8} の任意のタイプのプロファイルについて，パレート 効率的な割当は一意に定まる．ここで，参加者2の 評価値を4 としたとき，参加者1 のVCG の補償 は，参加者 1 のタイプに関わらず −5 となる．同 様に，参加者 2の評価値が 6, 8 のとき，参加者 1 の VCG の補償は −3, −1 となる．参加者 2 のタ イプは一様分布に従うので，p(4) = p(6) = p(8) = 1/4, p({4, 6, 8}) = 3/4となる．したがって，参加者 1の補償は，(4− 9)/3 + (6 − 9)/3 + (8 − 9)/3 = −3 となる．参加者2の補償も同様に−2となる． BDT-basedメカニズムを実行する際，BDTに関 する情報は事前に参加者にアナウンスされていること を仮定する．また，ある参加者のクエリに対する回答 は，他の参加者にとって観測可能であること，すなわ ち，入札情報が完全に公開されているモデルを仮定す る．これらの仮定を満たすことは，メカニズムの透明 性の観点から重要であると考えられる．また，これら の情報が参加者に与えられない場合，各参加者にとっ て，自身の効用を増加させるような戦略的行動を選ぶ ことは，より困難となる．本論文では，メカニズムの 実行過程で明らかとなる情報は，すべて公開されると いう，戦略的行動の影響を受けないメカニズムを設計 するためには，最も扱い難い状況を対象としている． BDT-basedメカニズムでは1つのノードに1つの クエリが対応する．また，1つのクエリは1人の参加 者に対してのみ送信される．これは，メカニズムの表 現を簡単にするためであり，同時に複数のクエリを送 信可能とするようにメカニズムを拡張するのは容易 である．
5 VCG-EE の特徴付け
本章では，VCG-equivalentメカニズムとVCG-EE の特徴の解析を行う．最初に，用語と概念を定義する． ノードd,参加者iについて，int(d) = iのとき， dはiのターゲットであるという．iとタイプ θi に ついて，dがiのターゲットかつθi∈ Θdi ならば，d は(i, θi)と適合するノードという．iの戦略とは，i のターゲットである各ノードから“yes/no”への写像 であり，siと表す．(i, θi)と適合するノードd′ につ162 いて，θi∈ q(d′)ならばsi(d′)が“yes”，そうでなけ ればsi(d′)が“no”となるとき，si はd′ において， (i, θi)に対して整合的な申告をしているという．siが (i, θi)と適合する各ノードにおいて，(i, θi)に対して 整合的な申告をしているならば，siは(i, θi)に対し て整合的な戦略という．とくに，iの真のタイプがθ′i のとき，(i, θ′i)に対して整合的な戦略は正直戦略と いう． 参加者j のタイプがθj であるという初期信念を p(θj)とする．初期信念は次のように更新される． 定義 6 (更新された信念). 各参加者j(j ̸= i) が正 直戦略 sj を用いるとする．参加者 i と i のター ゲットであるノードdについて，参加者j(j̸= i)の タイプがθj であるというdでの更新された信念を p(θj|d) = p(θj)/p(Θdj)とする． 定義7 (拡張された正直戦略). タイプがθiである参 加者iの正直戦略si は次の条件を満たすとき，拡張 された正直戦略であるという：(i, θi)と適合しない各 ノードdについて，各参加者j(j̸= i)が正直戦略sj を用いると仮定したとき，siはdにおける更新され た信念の下で期待効用を最大化する行動を選択する． 他の参加者が正直戦略を用いると仮定すると，バッ クワードインダクション(先読みに基づいた展開形 ゲームの解法)より，(i, θi)と適合しない各ノードd について，期待効用を最大化する最適な行動si(d)を 決定できる． 以下に逐次均衡 [11]の定義を示す. 定義 8 (逐次均衡). 以下の条件を満たす戦略の組と 各意思決定点での参加者の信念は逐次均衡であると いう：(a)各戦略は逐次合理的である．すなわち，各 意思決定点において，信念とその後の戦略の組合せが 与えられたとき，参加者の戦略は，その参加者の期待 効用を最大化する．(b)信念が整合的アセスメントで ある．すなわち，信念はベイズルールが適用可能なら ば，ベイズルールにより与えられ，ベイズルールが適 用不可能な非均衡経路については，わずかに摂動を加 え，全てのノードは正の確率で到達可能とした場合の 戦略の組合せに対して，ベイズルールを適用したもの により与えられる． 逐次均衡は完全ベイズ均衡 [9]の精緻化となってい る．具体的には，到達する可能性がゼロでありベイズ ルールが適用不可能な非均衡経路上の信念に関して も，以下の定義に示すように整合的であることを要求 する．より詳細な議論に関しては文献 [11]等を参照 されたい． 定理1. VCG-equivalentメカニズムにおいて，正直 戦略の組は事後ナッシュ均衡となる．すなわち，他の 参加者が正直戦略を用いるならば，自分も正直戦略 を用いるのが最良である．また，事後ナッシュ均衡に おいてパレート効率的な割当を実現することができ， 正直戦略を用いる限り，効用が負になる参加者はい ない． 紙面の都合上，証明は割愛する． ノードdにおいて，タイプがθi で戦略si を用い る参加者iの期待効用をE(si, θi|d)と表す．ただし， iを除く参加者は拡張された正直戦略を用いるものと する．次の補題は定理2の証明で用いられる． 補題 1. VCG-EEにおいて，全ての参加者が自分の 真のタイプを申告し，(i, θi)と適合するノードdで の更新された信念が与えられたとき，E(si, θi|d) は VCGの期待効用に等しくなる．より厳密には，次式 により与えられる． ∑ θ−i∈Θd −i u∗i(θi, (θi, θ−i))× p(θ−i) p(Θd −i) . ここで，真のタイプがθiの参加者iがθ′iを申告し， 他の参加者の宣言したタイプのプロファイルが θ−i であるときのiのVCGの効用をu∗i(θi, (θ′i, θ−i))と 表す． 証明は割愛するが，VCGとVCG-EEの期待効用 が等しくなることは直感的には明らかである． 定理 2. VCG-EEにおいて，拡張された正直戦略の 組と各ノードにおける更新された信念は逐次均衡と なる．また，逐次均衡においてパレート効率的な割当 が実現される． 証明. 戦略の組と信念が逐次均衡となることを示すた めには，(a)各戦略は逐次合理的であり，(b)信念は 整合的アセスメントであることを示せばよい． (b)について，ターゲットが参加者iである各ノー
ドdにおいて，定義6で与えられる信念は整合的ア セスメントである．dが(i, θi)と適合するならば，ベ イズルールにより信念は得られる．d が(i, θi) と適 合しないならば，各参加者が非常に小さい確率で誤っ た回答をすると仮定したときのベイズルールにより 得られる信念となる． 次に，拡張された正直戦略が逐次合理的であること を示す．si を拡張された正直戦略とし，s′iを任意の 戦略とする．ターゲットがiである各ノードdにつ いて，E(si, θi|d) ≥ E(s′i, θi|d)が成り立つことを示 せばよい． dがθi と適合しない場合，拡張された正直戦略の 定義より，この条件は直ちに満たされる．したがって， dがθiと適合することを仮定する． 補題1より，E(si, θi|d)は次式により与えられる： ∑ θ−i∈Θd −i u∗i(θi, (θi, θ−i))× p(θ−i) p(Θd −i) . (1) 次に，E(s′i, θi|d) について考える．lv(d) を d を ルートノードとする部分木の葉の集合とする．s′i を 用いたとき，dから到達可能な lv(d) の部分集合を D′⊂ lv(d) とすると，E(s′i, θi|d)は以下により計算 することができる． E(s′i, θi| d) = ∑ d′∈D′ (v(θi, ¯ai(Θd ′ )) + ¯ti(Θd ′ )) × p(Θd ′ −i) ∑ d′∈D′p(Θd−i′) v(θi, ¯ai(Θd ′ )) + ¯ti(Θd ′ )を書き直すと， ∑ θ−i∈Θd′ −i u∗i(θi, (θd ′ i , θ−i))× p(θ−i) p(Θd′ −i) . 各θ−i∈ Θd
−iについて，θ−i∈ Θd−i′ なるd′∈ D′が
唯一存在する．よって，∪ d′∈D′Θ d′ −i= Θd−iが成り立 つため，E(s′i, θi|d)は次式となる． ∑ d′∈D′ ∑ θ−i∈Θd′ −i u∗i(θi, (θd ′ i , θ−i))× p(θ−i) p(Θd −i) . (2) E(s′i, θi | d) > E(si, θi | d) を 仮 定 す る ．各 θ−i ∈ Θd −i に関する和をとる式 1， 2 より，次 式を満たすθ−iが少なくとも1つは存在する． u∗i(θi, (θd ′ i , θ−i)) > u∗i(θi, (θi, θ−i)). しかし，VCG は戦略的操作不可能性を満たすた め ，そ の よ う な θ−i は 存 在 し な い ．し た がって ， E(si, θi| d) ≥ E(s′i, θi| d)を満たす． また，参加者全員が拡張された正直戦略を用いる場 合，パレート効率的な割当が実現されるのは明らかで ある． VCGの効用は非負であることから次の定理が成り 立つ． 定理 3. VCG-EEにおいて，正直戦略を用いる参加 者の効用は負になることはない． 次に，無関係なノードという概念を導入し， BDT-basedメカニズムが無関係なクエリを送信するかを解 析する． 定 義 9 (無 関 係 な ノ ー ド). 参 加 者 i，int(d) = i な る ノ ー ド d に つ い て ，∃θi ∈ q(d), ∃θi′ ∈ Θ d i \
q(d),∀θ−i∈ Θd−i, ¯a(Θdl) = ¯a(Θd′l)かつ ¯ti(Θdl) =
¯ ti(Θd ′ l)が成り立つならば，このときに限り，dはi にとって無関係なノードであるという．ただし，dl, d′l は葉ノードであり，Θdl i ∋ (θi, θ−i), Θd ′ l i ∋ (θ′i, θ−i) を満たす． ノードdがiにとって無関係なノードでない場合， dをiにとって関係のあるノードという． ノードdが参加者iにとって無関係なノードなら ば，iの回答は割当とiの補償に影響を与えない(他 の参加者のタイプにのみ依存する)ため，iは送信さ れたクエリに対して正直に答える誘因を持たない．し たがって，二分決定木は無関係なノードを含まないこ とが望ましい． 例1において，Θ1 ={8}とすれば，VCGの補 償を計算するために，参加者2に無関係なクエリを 送信する必要がある．したがって，次の定理が成り 立つ． 定理4. 無関係なノードを含まないVCG-equivalent メカニズムが存在しないN, M, Θが存在する． 無関係なノードを含まないVCG-EE を構築する 手続きを示すために，無差別集合という概念を導入 する．
164 定 義 10 (無 差 別 集 合). Θ′i ⊆ Θi で あ る 低 次 に 縮 退 し た も の も 含 む) n 次 元 の 超 立 方 体 Θ′ = ∏ i∈NΘ′iについて，∀θi, θ′i∈ Θ ind i ,∀θ−i∈ ∏ j̸=iΘ′j, a∗((θi, θ−i)) = a∗((θ′i, θ−i))が成り立つならば，そ のときに限り，Θindi ⊆ Θ′i はiの Θ′ に対する無差 別集合であるという． また，Θind i が全ての無差別集合の真部分集合でな いとき，Θind i は極大であるという． Θ′ について，iの無差別集合が存在しない場合や 複数の極大無差別集合が存在する場合があることに 注意されたい．また，複数の極大無差別集合が存在す る場合，それらは互いに素である． 次の定理は，iにとって関係のあるノードであるた めの十分条件を示すものである． 定理 5. VCG-EEにおいて，i = int(d)であるノー ド dについて，次の条件を満たすノードd は iに とって関係のあるノードである：iのΘdに対する任 意の無差別集合Θindi ⊆ Θdi について，Θindi ⊆ q(d) またはΘindi ⊆ Θdi\ q(d)が成り立つ． 証明. 背理法により示す．i = int(d)であるノード d，iの Θd に対する任意の無差別集合Θind i ⊆ Θdi について，Θind i ⊆ q(d) またはΘindi ⊆ Θdi \ q(d) が成り立つが，d は i にとって無関係であると仮 定する．θi ∈ q(d), θ′i ∈ Θ d i \ q(d) とする．仮定よ り，θiとθ′iは同一の無差別集合に含まれない．よっ
て，a∗((θi, θ−i))̸= a∗((θi′, θ−i))となるθ−i∈ Θd−i
が存在する．他の参加者のタイプのプロファイル を θ−i とし，正直戦略を用いると仮定する．dl を iが (i, θi) に対して整合的な戦略 si を用いたとき に到達する葉ノードとし，d′l をi が(i, θ′i) に対し て整合的な戦略 s′i を用いたときに到達する葉ノー ドとする．VCG-EE であるから，(θi, θ−i) ∈ Θdl 及び¯a(Θdl) = a∗((θ i, θ−i)) が成り立つ．同様に， (θ′i, θ−i) ∈ Θd ′ l 及び¯a(Θd′l) = a∗((θ′ i, θ−i)) が成り
立つ．a∗((θi, θ−i))̸= a∗((θi′, θ−i))より，¯a(Θdl) ̸= ¯ a(Θd′l)が成り立つ．これはdがiにとって無関係で あるという仮定に反する．したがって，dはiにとっ て関係のあるノードである． 定理 6. 任意のN, M, Θについて, 無関係なノード を含まないVCG-EEが存在する． 証明. そのようなメカニズムを構築する手続きを示す ことで定理が成り立つことを示す．この手続きはルー トノードから開始し再帰的に新しいノードを生成す る．ルートノードの入力はΘである． 入力がΘdであるノードdについて，任意のi∈ N について，|Θd i| = 1またはΘdi がiの無差別集合な らば，d を葉ノードとする．無差別集合の定義より， 任意のθ∈ Θdについて，パレート効率的な割当は等 しい． 葉ノードとなる条件を満たさない場合，|Θd i| > 1を 満たす参加者iが選択される．iの無差別集合が存在す る場合，極大無差別集合Θind i を選択し，int(d) = i, q(d) = Θind i とする．ただし，極大無差別集合が複数 存在する場合，任意の1つを選択する．iの無差別集 合が存在しない場合，Θdi の真部分集合Θ′iを任意に 選択し，int(d) = i, q(d) = Θ′iとする．ノードの入 力のサイズは単調減少なので，この手続きは必ず停 止する．また，極大無差別集合が複数存在しても，そ れらは互いに素であるため，任意のノードについて， 定理5の条件を満たす．以上より，このメカニズムは 無関係なノードを含まない． この手続きは柔軟であり，Θdi の真部分集合の選び 方を変えることで多くのメカニズムを構築できる．
6 日本の第四世代の周波数オークションへの
応用
本章では，VCG-EEの現実的な応用事例への適用 可能性を示すために，日本の第四世代の周波数オー クション [18]に適用可能なVCG-EEメカニズムを 構築する．日本政府はキャリアに3.4∼ 3.6 GHzの 周波数帯域の利用権(周波数帯域幅は200 MHz)を割 り当てる予定である．周波数オークションは日本では 初の試みとなる．現在，対象の200 MHzを10ロッ トに分ける予定である(各ロットは 20 MHzの周波 数帯域幅となる)．同時送受信方式として，時分割複信(Time Division Duplex, TDD)と周波数分割複信
(Frequency Division Duplex, FDD)という2つの方
るため，2ロットをまとめて割り当てる必要がある． すなわち，FDDを用いるキャリアにとって，1ロッ トのみの割当は意味をなさない(2ロットに補完性が ある)． このオークションを単純な競り上げ式にする場合， 2つの財の間に補完性があるため，よく知られている Ausubelオークションメカニズム [2]を用いることは できない．そこで，本論文では，VCG-EEに基づい た単純な競り上げ式オークションメカニズムを提案 する． このオークションを次の簡単なモデルとして扱う． 割り当てるロット数をmとする．各参加者のTDD のライセンスとFDDのライセンスの評価値は独立と し，それぞれ限界効用逓減を満たすと仮定する．ま た，各参加者の評価値は異なり，同点またはタイは生 じないことを仮定する．この前提は，タイブレークの 取り決めによるメカニズムの煩雑化を防ぐためのも のであり，同点またはタイを扱うようにメカニズムを 拡張することは容易である． 紙面の都合上，メカニズムの概要のみ示す．メカ ニズムは価格p, q を持つ．各ラウンドにおいて，メ カニズムは，TDDのライセンスの価格は1つにつき p，FDDのライセンスの価格は1つにつきp + q と アナウンスし，参加者は各ライセンスの需要を申告す る．メカニズムはp = q = 0として開始し，マーケッ トがクリアするまで，以下のようにp, q を増加させ る．TDDのライセンスの需要の合計がm以上のと き，p, qを増加させる．TDDのライセンスの需要の 合計がmより小さいとき，pのみ増加させる．TDD のライセンスの需要が減少したとき，q = pとなるま でqのみ増加させる．その後，再びpのみ増加させ る．オークションの結果は，VCG-EEに基づいて決 定される．各ラウンドにおいて，需要を下げた分の財 は得られないが，下げなかった分の財を得る可能性は 常に存在するため，このメカニズムは無関係なクエリ を送信しない． 本メカニズムでは，割当の決定は単純かつ明瞭であ るが，補償の計算は期待値を用いるため複雑であり， 参加者に理解されることは困難であることが予想さ れる．しかし，周波数オークションのように，参加者 数が限られている状況においては，補償の計算は現実 的な時間で可能な程度の難しさであり，日本の第四世 代の周波数オークションへの適用は可能であると考え られる．
7 結論
公開型オークションが封印型オークションより好 まれている理由の1つに，参加者のタイプに関する 完全な情報を他者に露呈する必要がないことがある． しかし，公開型組合せオークションにおいて，参加者 に正直な申告をする誘因を与えるためには，メカニズ ムは無関係なクエリを送信する必要がある．これによ り，タイプに関する不要な情報が露呈され，正直な申 告を行わない新たな誘因が生じるというジレンマが 存在する．VCG-EE は，VCGと，期待値において 等価な結果を与えるというアイデアで，このジレン マを解決している．本論文では，BDT-basedメカニ ズムという簡単なモデルを用いて，VCG-equivalent メカニズムは無関係なクエリを送信する必要がある ことを示した．更に，VCG-EEでは，正直戦略の組 が逐次均衡となることを示した．また，無関係なクエ リを送信することなく，VCG-EEメカニズムを構築 する一般的な手法を示した．最後に，VCG-EEの現 実問題への適用可能性を示すために，日本の第四世代 の周波数オークションに適用可能なVCG-EEに基づ くメカニズムを構築した． 今後の課題として，開発した日本の第四世代の周 波数オークション向けのメカニズムのさらなる改良， 特に，支払額に関して，VCG-EEでの支払額に十分 近く，簡単かつ理解が得やすい計算方法を与えること が挙げられる． 謝辞 本研究の遂行にあたり，日本学術振興会科学 研究費補助金基盤研究(S) (課題番号24220003)の助 成を受けました．ここに深く感謝致します．また，非 常に有益なコメントを下さった日本ソフトウェア科学 会 の3名の査読者に深く感謝致します．166
参 考 文 献
[ 1 ] Ausubel, L. M. and Milgrom, P. R.: Ascending Auctions with Package Bidding, Frontiers of Theo-retical Economics, Vol. 1, No. 1 (2002), pp. 1–42. [ 2 ] Ausubel, L. M.: An Efficient Ascending-Bid
Auction for Multiple Objects, American Economic Review, Vol. 94, No. 5 (2004), pp. 1452–1475. [ 3 ] Ausubel, L. M.: An efficient dynamic auction for
heterogeneous commodities, American Economics Review, Vol. 96, No. 3 (2006), pp. 602–629.
[ 4 ] Blumrosen, L. and Nisan, N.: On the Computa-tional Power of Demand Queries, Siam Journal on Computing, Vol. 39, No. 4 (2009), pp. 1372–1391. [ 5 ] Blumrosen, L. and Nisan, N.: Informational
Limitations of Ascending Combinatorial Auctions, Journal of Economic Theory, Vol. 145, No. 3 (2010), pp. 1203–1223.
[ 6 ] Clarke, E. H.: Multipart Pricing of Public Goods, Public Choice, Vol. 2 (1971), pp. 19–33. [ 7 ] Conen, W. and Sandholm, T.: Preference
Elic-itation in Combinatorial Auctions (Extended Ab-stract), in Proceedings of the ACM conference on electronic commerce, MIT Press, 2001, pp. 256–259. [ 8 ] d’Aspremont, C. and Gerard-Varet, L.-A.: In-centives and incomplete information, Journal of Public Economics, Vol. 11, No. 1 (1979), pp. 25–45. [ 9 ] Fudenberg, D. and Tirole, J.: Perfect Bayesian
equilibrium and sequential equilibrium, Journal of Economic Theory, Vol. 53, No. 2 (1991),pp. 236–260. [10] Groves, T.: Incentives in teams, Econometrica,
Vol. 41 (1973), pp. 617–631.
[11] Kreps, D. M. and Wilson, R. B.: Sequential Equi-libria, Econometrica, Vol. 50, No. 4 (1982), pp. 863– 94.
[12] Mishra, D. and Parkes, D. C.: Ascending price Vickrey auctions for general valuations, Journal of Economic Theory, Vol. 132, No. 1 (2007), pp. 335– 366.
[13] Parkes, D. C.: Iterative Combinatorial Auctions, Combinatorial auctions, MIT Press, 2006, pp. 41– 78.
[14] Sandholm, T. and Boutilier, C.: Preference Elic-itation in Combinatorial Auctions, Combinatorial auctions, MIT Press, 2006, pp. 233–264.
[15] Vickrey, W.: Counter Speculation, Auctions, and Competitive Sealed Tenders, Journal of Fi-nance, Vol. 16 (1961), pp. 8–37.
[16] Vries, de S., Schummer, J. and Vohra, R. V.: On ascending Vickrey auctions for heterogeneous ob-jects, Journal of Economic Theory, Vol. 132, No. 1 (2007), pp. 95–118. [17] 横尾 真：オークション理論の基礎 –ゲーム理論と情 報科学の先端領域–, 東京電機大学出版局, 2006. [18] 松島斉：4G 周波数オークション・ジャパン: Japanese Package Auction(JPA) 設 計 案 の 骨 子, http://hdl. handle.net/2261/51497 (2012) 藤 田 悦 誌 2013年九州大学工学部電気情報工学 科卒業．現在，九州大学大学院システ ム情報科学府修士課程に在籍中．メ カニズムデザイン，アルゴリズム，計 算論的社会選択理論に関する研究に興味を持つ． 岩 崎 敦 2002年神戸大学大学院自然科学研究 科博士課程修了．同年より2004年 までNTT コミュニケーション科学 基礎研究所に勤務．九州大学大学院 システム情報科学研究院助教を経て，2013年より電 気通信大学大学院情報システム学研究科准教授． 博 士(学術). ゲーム理論と最適化に関する研究に従事． オークションやマッチングなどのメカニズム設計やノ イズ付き繰り返しゲームや協力ゲームなどに興味を もつ．2012年情報処理学会論文賞，2011年第10回 情報科学技術フォーラム船井ベストペーパー賞受賞． IEEE，人工知能学会，情報処理学会各会員． 東 藤 大 樹 2012年3月九州大学大学院システム 情報科学府博士後期課程修了．2012 年∼2013年，デューク大学博士研究 員．2013年12月より，九州大学大 学院システム情報科学研究院助教．ゲーム理論やメ カニズムデザインに関する研究に従事．博士(情報科 学)．2011年度情報処理学会論文賞受賞．人工知能学 会，情報処理学会各会員． 横 尾 真 1984年東京大学工学部電子工学科 卒業．1986年同大学院修士課程修了． 同年NTT に入社．1990年∼ 1991 年ミシガン大学客員研究員．2004年 より九州大学大学院システム情報科学研究院教授． マルチエージェントシステム，制約充足問題に関す る研究に従事．博士(工学)．1992年, 2002 年人工
知能学会論文賞，1995年情報処理学会坂井記念特 別賞，2004年ACM SIGART Autonomous Agent Research Award，2005年ソフトウェア科学会論文
賞，2006年学士院学術奨励賞，2009年人工知能学会
業績賞，2011年ソフトウェア科学会基礎研究賞，情
報処理学会論文賞受賞．情報処理学会，AAAIフェ
