オークションの設計理論と数理計画_{01605000 東京大学松井知己 01900730 東京都立大学渡辺隆裕}

\underline{1 . はじめに} ; 近年，複数の財を割り当てるオークションが経 ; 営面からも，政策面からも注目を集めている。１ ; つの大きな契機は，アメリカが携帯電話や放送な ; どの電気通信事業者への周波数免許を，それまで ; の認可制からオークションによる販売に切り替え ; た事である。このような周波数免許割当へのオー ; クション導入は，現在ヨーロッパ各国にも広がっ ; ている。周波数免許は，事業者によっては複数の ; 免許を組合せて取得することで，個々の免許の価 ; 値の総和よりも価値が増加したり (補完性)，減少 ; したり (代替性) するため，免許を１つずつ販売 ; することで不都合が生じる。 ; 簡単な例でこれを考えてみる。 A と B という ; ２つの地域の周波数免許を， 1 と 2 という 2 人の ; 事業者にオークションで売るとしよう。事業者 1 ; は A と B の両方の地域で大規模に事業を行いた ; いと考えており，片方の地域の免許しか取得でき ; なければ，免許の価値は 1 地域につき 10 である ; が，両方の地域の免許を取得できれば価値は総和 ; より大きい 35 となる。一方，事業者 2 はどちら ; か一方の地域で小規模に事業を行いたいと考えて ; おり， 1 つの地域の免許が取得できれば免許の価 ; 値は 20 であるが，両方の地域の免許を取得でき ; ても価値は総和より小さい 30 しかない (表 1)。 ; 表 1: 各事業者の免許に対する価値 ; \begin{aligned}& 免許 A & 免許 B & 免許 A と B \\ 事業者 1 & 10 & 10 & 35 \\ 事業者 2 & 20 & 20 & 30 \end{aligned} ; 表 1 で，価値の総和を最大にする免許の割当は ; 事業者 1 に免許 A と B の両方を割り当てること ; である。しかし，免許 A と免許 B を別々のオー ; クションにかけると，事業者 1 の少なくとも一方 ; の免許の入札額は 35/2 = 18.5 以下になってしま ; うであろう。したがって，事業者 2 が 19 を入札 ; すればその免許を得ることができる。両方の免許 ; を別々にオークションすれば，事業者 1 に免許 A ; と B の両方が割り当てられない可能性は大きい。 ; このような互いに補完性や代替性を持つ複数 ; の財を販売するために，各財を個別に入札するの ; ではなく，財の組合せに入札をする「組合せオー ; クション」と呼ばれるオークションが提案されて ; いる。組合せオークションは周波数オークション ; だけではなく，ロジスティクスなどを中心とする ; 電子商取引でも注目されおり，数多くの研究がな ; されている。 ; 本稿では，組合せオークションとその周辺につ ; いて簡単に紹介し，数理計画をオークションに適 ; 用する時の問題やゲーム理論との関係などについ ; て議論していきたい。 ; \underline{2 . モデルとオークションの目的} ; まずオークションの問題を数学的に記述し， ; オークションの目的について述べる。オークショ ; ンの参加者を N = \{1, ⋯, n\} で表し，オークショ ; ンによって販売される財を M = \{1, ⋯, m\} とす ; る。財の部分集合 S ⊆ M に対する参加者 i の持 ; つ価値を V_{i}(S) で表す。簡単のためオークション ; の主催者が財に対して持つ価値は 0 であり，任意 ; の参加者 i に対し V_{i}(∅) = 0 とする。オークショ ; ンとは, このような状況で参加者に何らか (多く ; は財に対する入札額) の申告をさせて，財の割当 ; と支払額を決めるルールである。オークションと ; 言うと「競り」のように相手の入札額が分かる公 ; 開オークションが多いが，本稿では各参加者が他 ; の参加者に分からないように入札額を申告し，主 ; 催者がそれを見て割り当てを決める封印オーク ; ションについて議論する。 ; 仮に, あるオークションによって財の割当 ; (S_{1}, …, S_{n}) と支払額 (p_{1}, …, p_{n}) が決まったと

しよう。ここで S_{i} ⊆ M と p_{i} は，参加者 i に対する財の割当と支払額を表す。簡単に分かるように, 財の割当は [∀i, ∀j ∈ N, i ≠ j ⇒ S_{i} ∩ S_{j} = ∅] かつ [∪_{i∈N}S_{i} ⊆ M] を満たさなければならない。値 ∑_{k∈N} p_{k} を主催者の利潤と呼び， V_{i}(S_{i}) − p_{i} を参加者 i の余剰と呼ぶ。

\underline{経営的な意味}でのオークションの目的は，主催者の利潤を最大にすることと考えられる。これに対して，周波数オークションなどの公共体が行うオークションや, \underline{経済学的な意味}でのオークションの目的は，主催者の利潤と参加者の余剰の総和，すなわち ∑_{k∈N} p_{k} + ∑_{k∈N}(V_{k}(S_{k}) − p_{k}) = ∑_{k∈N} V_{k}(S_{k}) を最大化することである。上記の値は社会的総余剰と呼ばれる。上記の式から分かるように, 社会的総余剰は支払い額には依存せず, 財の割当のみで定まる。社会的総余剰を最大にするような財の割当を効率的資源配分^{1} と呼ぶ。オークションの経済学的な目的は， (社会全体の余剰を最大にする) 効率的資源配分を達成することにある。

\underline{3 . 組合せオークション}

本節では組合せオークションとその問題点について解説する。組合せオークションは次のような手続きで実行される。 (1) 参加者は財の部分集合すべてに対する入札額を申告する, (2) 申告をもとに，主催者は各参加者の入札額の総和が最大になるように財の割当を定める, (3) 参加者は割り当てられた財に対する自分の申告した入札額を主催者に支払う。オークションの問題を記述する際, 参加者の財に対する真の価値と入札額は同じとは限らない点に注意されたい。以下では財の部分集合 S ⊆ M に対する参加者 i の入札額を b_{i}(S) とする。上記 (2) の手続きにおいて, 主催者は下記の問題を解く必要がある。決定変数として y(S, i) を導入しよう。 y(S, i) = 1 は，参加者 i に財の部分集合 S を割り当てることを意味する。最適な財の割当を求める問題 CAP は

maximize ∑_{i∈N} ∑_{S⊆M} b_{i}(S)y(S, i)

subject to

∑_{S:S∋j} ∑_{i∈N} y(S, i) ≤ 1 (∀j ∈ M),
∑_{S⊆M} y(S, i) ≤ 1  (∀i ∈ N),

y(S, i) ∈ {0, 1} (∀S ⊆ M, ∀i ∈ N),

と定義される。オークション主催者は参加者の入札に基づいて CAP を解き，最適解に従って財の割当を決める。財 (の集合) を割り当てられた参加者 (落札者とも呼ばれる) は，対応する入札額を支払う。以上が組合せオークションである。組合せオークションにおいて，もし全員が真の価値を正直に申告する (b_{i}(S) = V_{i}(S), ∀S ⊆ M) ならば，上記の手続きは効率的資源配分を達成し，かつ主催者の利益を最大にする。しかしこれを実際に達成するには，下記のような問題がある。

問題 1 CAP は集合パッキング問題と呼ばれる NP 困難問題であり，最適解の計算が難しい。

問題 2 全員が価値を正直に申告するとは限らない。参加者の行動が分からなければ，効率的な資源配分が達成されるか，主催者の利益がいくらになるか，は不明である。

問題 3 参加者は，財の部分集合すべての入札額を申告するが，財の数 m が増えると 2^{m} は膨大な数となり現実的ではない。

問題 4 最適解が複数あるときは, 財の割当を唯一に定め，それを求める方法が必要である。

アメリカの周波数オークションでは，組合せオークションの導入が検討されたものの，このような問題点から導入は先送りされている (鬼木 [9])。数理計画に携わる者にとって，まず目が行くのは問題 1 であろう。問題 1 に対しては，周波数オークションの実施に伴い, 人工知能などの分野でいち早く注目され多くの論文が書かれたのに対し, 数理計画の分野では初動研究が少ないのは非常に残念である。特に, 集合パッキング問題に関する研究結果が十分認知されていない事から生じた問題については， Andersson, Tenhunen and Ygge [1] を参照されたい。以下本稿では，問題 2,3,4 について順番に議論する。

1 「効率的」という単語は，経済学においては社会的な厚生を最大にするという意味を持ち，日常的に使う「効率」の概念とはやや異なることに注意されたい。

\underline{4 . VCG メカニズム}

問題 2 は，組合せオークションの問題が単なる最適化ではなく，オークション (＝１つのアルゴリズム) を提示した時に，参加者がどのような行動をとるかを読み込んで，制度やルールを決定しなければならないことを示している。「参加者がどのような行動をとるかを読み込んで，制度やルール (メカニズム) の設計を行う」という問題は，ゲーム理論のメカニズムデザインと呼ばれる分野で研究されている。この分野において有名な結果に, Vickrey-Clarke-Groves メカニズム (以下 VCG メカニズム) と呼ばれるものがある。これは，各参加者が他の参加者の行動に依存せず真の価値を申告することが良く，かつ効率的な資源配分を達成するようなメカニズムである。 VCG メカニズムを複数財のオークションに適用すると次のようになる。参加者はすべての部分集合に関する入札額を申告し，主催者は CAP を解いて財の割当を決める (ここまでは前節と同じ)。異なるのは，参加者の支払額だけである。財の割当に対応する CAP の最適解を y^{∗}(S, i)(∀S ⊆ M, ∀i ∈ N) とし，最適値を z^{∗} としよう。主催者は，各参加者 k について k を除いた CAP，すなわち

maximize ∑_{i∈N\{k}} ∑_{S⊆M} b_{i}(S)y(S, i) subject to

∑_{S:S∋j} ∑_{i∈N\{k}} y(S, i) ≤ 1 (∀j ∈ M),
∑_{S⊆M} y(S, i) ≤ 1  (∀i ∈ N \ {k}),

y(S, i) ∈ {0, 1} (∀S ⊆ M, ∀i ∈ N \ {k}),

を解き, 最適値 z_{−k}^{∗} を求める。 VCG メカニズムでは, 参加者 k の支払額は

z_{−k}^{∗} − (z^{∗} − ∑_{S⊆M} b_{k}(S)y^{∗}(S, k)) で決定される。

VCG メカニズムでは, 各参加者は，他の参加者の申告に関わらず, 自分の真の価値を入札することに比べ，他のどんな入札額も自分の余剰を大きく出来ない事が保障される (例えば Krishna[4])。したがって， VCG メカニズムでは効率的資源配分を達成できる。この魅力的な性質から， VCG メカニズムは多くの研究がなされており，組合せオークションの文脈においても VCG メカニズムの研究は盛んであり (例えば Yokoo[8]), 数理計画の研究者も参入している (Archer, Papadimitriou, Talwar and Tardos [2] 等)。

このように魅力的な VCG メカニズムであるが，問題点も多くある。まず, 問題 1 の計算量の問題は依然として残っている。 VCG メカニズムの研究において， CAP の近似解法の研究が盛んになりつつあるが，単純には評価できない。なぜならば，近似解法による落札者決定アルゴリズムのもとでは，参加者が正直に価値を入札してくる保証は得られず， VCG メカニズムの意味がなくなるからである。また, 問題 3 も解決されてはいない。さらに VCG メカニズムは，経営的な視点からは大きな問題を抱えている。以下では, 3 人の参加者が 2 つの財 A, B に対し表 2 のような価値を持つとし， VCG メカニズムを適用してみよう。

表 2: VCG メカニズムと主催者利益

V_{i}({A}) V_{i}({B}) V_{i}({A, B})
参加者 1 w − 1 0  w − 1
参加者 2 0  w − 1 w − 1
参加者 3 0 0 w

(ただしここで w > 2 とする。 )

この例の効率的資源配分は, 参加者 1, 2 に財 A, B をそれぞれ割り当てる事であり， VCG メカニズムではこの配分が実現する事が保障されている。では支払額はどうなるだろうか。全員が真の価値を入札したとして (これが達成されることも保障されている) 支払い額を計算すると， z^{∗} = 2w − 2, z_{−1}^{∗} = w, z_{−2}^{∗} = w, z_{−3}^{∗} = 2w − 2,

であるから，参加者 1 と 2 の支払額はそれぞれ w − {(2w − 2) − (w − 1)} = 1

であり，参加者 3 の支払額は 0 である。ゆえに, 主催者の利潤は w の大きさにかかわらず 2 となる。例えば w = 1000 ならば, 主催者は z^{∗} = 2000 − 2 = 1998 に近い利潤を望むだろうが, これに対し非常に小さい利潤 2 しか得られていない。

このように VCG メカニズムは，真の価値を正直に申告する誘因を参加者に与え, 効率的な資源配分を達成するが, その代償として主催者に与える利益を小さくする傾向がある。この傾向は明示的には証明されていないが，よく知られている。 VCG メカニズムは，主催者の利益を全く問わない公共的な財配分等には大きな可能性を秘めているが，経営的な意味では必ずしも好ましくない。

5 . Single Bundle Bidding と均衡分析

問題 3 に対する単純な解決策としては, すべての財の組合せの入札額を申告させないで，一部の組合せに対してだけ申告させるという方法がある。では，どのようなルールで組合せを申告させれば良いのだろうか。すぐ思いつく方法として，各参加者に財の組合せを自由に申告させ，申告されていない組合せは各財の入札額の加法和で計算する，又は申告されてない組合せは 0 とするといった方法がある。これは一見現実的であるが，参加者は全ての組合せを入札したほうが有利となるケースがあるため, 最悪のケースを考えると解決法となっていない。

適当なルールを用いて財の組合せを制限したときに，参加者はどのような行動を取るのだろうか。ゲーム理論を使った均衡分析が，このような状況を説明すると期待されるが，単純なルールであっても均衡を求めることは容易ではない。筆者らは [5][6] において，非常に単純なルールである，「財の部分集合１つと, その入札額を申告させるオークション」 Auctions with Single Bundle Bidding(以下 ASBB) を提案し分析した。以下本節では，これを解説する。

ASBB では，各参加者 i に財の部分集合 1 つ, B_{i} ⊆ M と書く，とその入札額 b_{i} を申告させる。ここで入札額の最小単位を ε とし, b_{i} は ε の非負整数倍のみを許すとする。また各参加者が申告した n 個の財集合と入札額の組 ((B_{1}, b_{1}), (B_{2}, b_{2}), …, (B_{n}, b_{n})) は順序を変えて (B, b) と表記する。

オークションの主催者は，申告 (B, b) をもとに，以下の財の割当問題 BAP(B, b)

maximize ∑_{i∈N} b_{i}x_{i} subject to

∑_{i:B_{i}∋j} x_{i} ≤ 1 (∀j ∈ M),
x_{i} ∈ {0, 1}  (∀i ∈ N),

を解く。この BAP(B, b) の最適解を用いて落札者を決定し，参加者は財を割り当てられる。最適解が複数ある際は最適解の１つをランダムに選ぶとする。ちなみに BAP(B, b) も集合パッキング問題であり, NP 困難に属するため, 問題 1 が本質的に解決される訳ではない。

参加者の行動の分析を容易にするために，各参加者は各自の essential bundle という財の集合１つだけを選好していると仮定しよう。 essential bundle とは，その集合の中のどの財が 1 つ欠けても価値がない完全補完性のある財の集合であり，かつ，その集合以外の財には価値がないというものである。参加者 i の essential bundle を T_{i} ⊆ M とし，その価値を v_{i} とすると，

V_{i}(S) = \{ \begin{matrix}v_{i} & (T_{i} ⊆ S), \\ 0 & (otherwise), \end{matrix}

となる。参加者全員が各自の essential bundle T_{i} とその価値 v_{i} を申告した際に対応する財の割当問題を, BAP(T , v) と書く。

筆者らは，このような選好のもとで ASBB での参加者の行動をゲーム理論を用いて分析した。その結果，入札額の最小単位 ε が十分小さいならば，効率的な資源配分を達成するナッシュ均衡が存在することを示した。詳細は [5][6] に譲るとして，ここでは表 3 に示す例で，ナッシュ均衡がどのようなものになるか説明しよう。

表 3 の例では， BAP(T , v) の最適解は，参加者 1 に {A, B} を割り当て，参加者 3 に {C} を割り当てるというものである。ここで入札単位 ϵ = 1 とし，入札額ベクトル b = (b_{1}, b_{2}, b_{3}) の中で次の性質を満たすものを全て集めた集合を F としよ

表 3: ASBB の例

essential bundle v_{i}
参加者 1 {A, B}  45
参加者 2 {B, C}  50
参加者 3 {C}  10

う。 (1)BAP(T , b) と BAP(T , v) は最適解集合が一致する, (2)BAP(T , v) の最適解で財が割り当てられない参加者 i(例では参加者 2) は b_{i} = v_{i} を満たす， (3)BAP(T , v) の最適解で財が割り当てられる参加者 i(例では参加者 1, 3) は b_{i} ≤ v_{i} − ε を満たす。

F は以下の集合となる。

\begin{aligned}F = & \{(44, 50, 9), (43, 50, 9), (42, 50, 9), \\ & (44, 50, 8), (43, 50, 8), (44, 50, 7)\}. \end{aligned}

このとき F の極小ベクトル (例では (42, 50, 9),(43, 50, 8),(44, 50, 7)) は以下を満たす。各参加者が essential bundle を申告し，その入札額を F の極小ベクトルとしたものはナッシュ均衡となる。またこのナッシュ均衡点は効率的資源配分を達成する。すなわち, ASBB を適用し essential bundle の存在を仮定したならば, 問題 2,3 は肯定的解決される。

このナッシュ均衡点では， VCG メカニズムに比べ主催者の利潤も大きいことも分かる。例えば，表 2 の例で VCG が主催者に与える利潤は 2 であったが， ASBB では提示されたナッシュ均衡における主催者の利潤は w となる。表 3 の例においても， ASBB では 51 であるのに対し， VCG では 45 である。

上記の分析は，選好の仮定も厳しく, 完備情報のナッシュ均衡が実際のオークションで達成されるかどうかなどの問題がある。しかしながら，このような簡単な分析であっても，複数財のオークションのメカニズムを設計する上で, 参加者の行動の示唆をいくつか得る事ができる。例えば, 財を手にすることができる落札者は，支払額ができるだけ安くなるように財を手に入れるため, 落札者以外の参加者が落札しない出来るだけ小さな価格まで入札額を下げようとする。 (上記の例で言えば，参加者 1 と 3 は入札額の合計を，参加者 2 が落札する可能性がない 51 まで下げる)。多くの場合 F の極小ベクトルは複数存在し, 参加者間の余剰をどのように取り合うかで，複数のナッシュ均衡が存在する。この事は, 次節で考慮する問題 4 の重要性を示唆している。

\underline{6 . 同点問題}

前節で述べたように，参加者は同点になる価格ギリギリまで落札額を下げたいが, 実際には他の参加者の価値に関する正確な情報を持たず, また複数のナッシュ均衡のどれが達成されるか不明のため, BAP(T , b) が多数の最適解を持つ入札額 b を申告することがしばしば起こると予想される。ゆえに，オークションの挙動を調べるために，参加者の入札額をランダムに発生させるようなシミュレーションは，問題 4(最適解が複数存在する可能性) を過小評価していると我々は考えている。

BAP(T , b) の最適解が複数ある際に, その中からランダムに 1 つ選ぶのは非常に難しい問題である。もしこれが意思決定者が一人の問題であれば，最適解の一つが得られれば問題無い。しかし参加者が利害関係にあるオークションでは, 「最初に見つかった最適解を用いる」あるいは「辞書的に目的関数を摂動する」といったルールは参加者全員の同意は得難い。最適解が複数ある際に，その一つをどうやって選ぶかは，公平性の問題とも絡んで，オークションの重要かつ困難な問題となっていくだろう。

\underline{7 . まとめ}

以上，複数の財のオークションと数理計画について, いくつかの話題や問題点，視点について議論した。複数財のオークションについては，ゲーム理論でも研究されているが，均衡点が複雑で通常は解析的な結果は得にくい。これに対しマルチエージェントなどの分野では，シミュレーションなどを用いて多くの研究がなされている。また経済学では，被験者に実験をさせることで経済学的な現象をつかむ実験経済学と呼ばれる分野が台頭してきている。解析的には得られにくい組合せオークションの挙動を，被験者の実験によって調べようという研究はまもなく盛んに行われるであろう (もう始まっているに違いない)。またインターネット上のオークションでは，本人確認や架空名義入札などの問題が大きな問題となっている。例えば Yokoo[8] などはこれに関する研究である。更にこの分野では暗号理論の研究者もオークション研究に乗り出している (例えば [7] 中の論文等)。

このようにオークションの研究は多くの分野が関係する学際的領域である。研究が盛んになっている背景には，周波数オークションや企業間電子商取引，いわゆる B2B におけるネットオークションがロジスティクス，旅行販売，不動産販売などの分野で大きな可能性を秘めており，高い収益の源泉となる可能性があるからである。実際 Vries and Vohra[3] では，「いくつかのロジスティクスコンサルタント，例えば SAITECH-INC のシステム SBID などは，組合せオークションのソフトウエアを実装し， Logistics.com のシステム OptiBid は 50 億ドル以上の運送契約が Bid されたと主張している」と述べており，その重要性を主張している。

数理計画の分野は，組合せオークションの研究に様々な道具と知識を提供できる力を持っていると筆者らは信じている。また FOCS, STOC といったレベルの高い国際会議では，オークションに関する論文が複数出現しつつある。実務面においては，既に日本でも周波数オークションに関する検討は始まっているし (鬼木 [9])，ビジネスへの組合せオークションの応用も始まっている。地方自治体の主催する電子入札も本格的に始まっている。筆者らは数年前より組合せオークションの研究の必要性を主張しているが, PR 不足のためか数理計画分野では日本が未だ出遅れている。しかし実務での必要性はもう待った無しの状況なのだ。今ここに, 未だ飼い慣らされていない現実問題が研究者を待っている。 \underline{参考文献}

[1] Andersson, A., Tenhunen, M., and Ygge, F. (2000), “Integer programming for combinatorial auction winner determination,” Proc. of ICMAS2000, 39–46.

[2] Archer, A., Papadimitriou, C., Talwar, K. and Tardos, E. (2003), “An approximate truthful for combinatorial auctions with single parameter agents,” Proc. of SODA2003, 205–214.

[3] de Vries, S. and Vohra, R. (2000), “Combinatorial auctions; a survey,” Kellog School of Management, technical report.

[4] Krishna, V. (2002), Auction Thoery, Academic Press.

[5] Matsui, T. and Watanabe, T. (2001), “Sealed bid multi-object auctions with necessary bundles and its application to spectrums auctions,” Proc. of PRIMA2001, LNAI 2132, 78–92, Springer-Verlag.

[6] Matsui, T. and Watanabe, T. (2003), “Multi- object auctions with single package bidding for perfect complements,” Univ. of Tokyo, technical report, METR2003-02.

[7] Syverson, P. F. (Ed.) (2001), Financial Cryptography, Proc. of FC2001, LNCS 2329, Springer-Verlag.

[8] Yokoo, M., Sakurai, Y. and Matsubara, S., “The effect of false-name bids in combinatorial auctions: new fraud in internet auctions,” to appear in Games and EconomicBehavior.

[9] 鬼木甫 (2002), 電波資源のエコノミクス, 現代図書.