第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

1

複数財オークションについて
松井知己 渡辺隆裕

まく機能しない場合がある. 補完性や代替性がある場

1 はじめに合に異種複数財オークションをどのように行うかは大オークションは , Vickley 8] を契機としてゲーム理きな課題である.

重要な研究課題として複数財のオークションがある.

異種複数財のオークションの応用範囲は広い. deVries and Vohra 4] によると, 「いくつかのロジスティ
クスコンサルタント , 例えば SAITECH-INC のシス
テム SBID などは, 組合せオークションのソフトウエアを実装し , Logistics.com のシ ステム OptiBidTM
は 50 億ドル以上の運送契約が Bid されたと主張している（ 2000 年１月）」などと伝え , 物流のプライシン
グでこの分野が注目されていることを主張している.

複数財のオークションは売り手が複数の財を売り

また公共部門では規制緩和と市場経済重視の流れかに出すオークションである. 花市場や国債の市場なら , 電波（周波数帯）をオークションで売り出すこと論や経済学などで盛んに研究されてきた分野であるが , オークションが電子商取引の代表的な取引モデルとして大きく発展した事から , これらの理論の応用可能性は広がった. Yahoo や e-Bay に代表されるような消費者間取引（ C2C ）における電子オークションに対し , 近年は企業間取引（ B2B) の取引モデルとしてのオークションが注目されている. この分野におけるど複数財のオークションは昔から存在したが , これらが検討され , 既にアメリカやヨーロッパなどで実施さる. これに対し , 最近注目されつつあるのは異種複数わせて購入すると, 価値が大きく増大するため, 複数は同種複数財 (multi-items) が売り出されるものであ財 (multi-objects) のオークションである. 異種複数れている. 周波数帯などは隣り合う周波数帯を組み合の財をどのように組み合せてオークションするかが大財のオークションでは, 販売される財が「組み合せるきな課題となっている. 今後は公的資産や公有地の売生む」という補完性（シナジー効果）を持っている場されるであろう.

ことによって, 個々の価値の総和よりも大きな価値を合や, その逆の代替性を持っている場合がある. このような場合には , 個々の財を独立して売る事が必ずしも効率的な資源配分につながらず, オークションがう

Notes on multi-object auctions
Tomomi MATSUI, 東京大学大学院 情報理工学系研究科,
Graduate School of Information Science and Technology, University of Tokyo.
Takahiro WATANABE, 岩 手 県立 大 学 総 合 政策 学 部
総合政策学科, Department of Policy Studies, Iwate
Prefectural University.

166

却などに対しても, 異種複数財のオークションが注目

複数財オークションの 1 つである組合せオークション (combinatorial auctions) は , このような異種複数財のオークションの代表的なモデルであり, 多くの研究が行われている (de Vries and Vohra 4] など ). 組合せオークションは, 参加者が財のすべての部分集合に対する価値を売り手に提出し , 売り手がその情報をもとに利益が最大となるような財の配分方法を決定するというオークションである.

組合せオークションでは, 参加者は財の部分集合

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17
すべてについて金額を申告しなければならないため,その申告数は指数的に増大し , 財の数が大きくなった場合には現実的ではない. これに対し , 筆者たちはMatsui and Watanabe 6]7] において「その集合の中のど れか 1 つが欠けても価値がなく, またその集合以外の財にも価値がないような財の集合」である「必要十分財 (necessary bundle) 」が各参加者に 1 つある場合を分析した. そして，参加者が必要十分財を欲しているような状況で , 参加者が「彼の必要十分財 1 つとその価値」を入札するようなオークションについて分析を行った. その結果として, 必要十分財のオークションは , 戦略的な行動によっても効率的な資源配分を達成できるオークションであることを示した. 更に周波数オークションなどに応用できるようなconsecutive one property と呼ばれる性質を満たすな

らば , 売り手の利益を最大にするような財の最適な割り当てを求める多項式時間アルゴ リズムが存在し , 売り手の利益を最大にするような最適解が複数ある場合（ 同点となる参加者群が複数ある場合）に , 等確率で 1 つの解を選び出す多項式時間アルゴ リズムが存在することなどを示している. 本論文は , 筆者たちの研究 Matsui and Watanabe 6]7] の研究成果を要約し , 紹介することを目的としている.

オークションは学際的な研究分野であり, マルチエージェント理論, 経済学・ゲーム理論, 組合せ理論,経営学・経営情報, 暗号理論などに離散して研究者が存在している. 各分野の研究者が連携を取り合い研究を進めるうえで , 本稿がきっかけになれば幸いである.

またそれ以外の財にも価値がないとする. 現実にはこのような仮定がいつも成り立つとは限らない. 例えば１つや２つの財が欠けても残りの財の価値は減ずる
ことはあれ 0 になることはない場合も多いであろう.
この仮定は「 必要十分財中のどれか 1 つが欠けると価値が大幅に減じられ , それ以外の財にはほとんど価値がない」ような状況を近似的に表していると解釈できる. 参加者 i の必要十分財を Ti とし , 彼の Ti に対する価値を vi > 0 とする. したがって,Vi (S ) は以下のように表せる.

Vi (S ) =(vi (Ti  S )0 (その他):

以下では  を財の価値の最小単位とする. すなわち,すべての i2 N に対し vi 2 f 2 3 : : :g とする.

3 必要十分財のオークション
必要十分財のオークションルールは以下のような 3ステップからなっている.
ステップ 1

各参加者 i は , 自分の必要十分財 Bi とその入札額（ 落札時の購入額）bi を同時に提出する(各参加者は正直に入札するとは限らないので, (Bi  bi )と (Ti  vi ) を区別する). ここで入札最小単位を " とし , ある正整数 I に対して " = I を仮定する. またZ" = f" 2" 3" : : :g と定義する. なお以下では入札を並べたベクトル ((B1  b1 ) (B2  b2 ) : : :  (Bn  bn )) を(B  b) と成分の順番を変えて表示する.
ステップ 2

競売人は 全参加者から の 入札を もとにし て, 売却額が 最大にな るよ うな 財の 割り当てを（ 計 算 機で ）計 算 す る.

2 必要十分財のモデルとその応用
本稿で 扱 うモデルでは , 一人の競売人（ 売り手 ）が m 個の 財をオークションに 出し ており, n 人のオークション参加者（買い手）がいる状況を扱う. 参f1 2 : : :  ng とし , 財の集合を
M = f1 2 : : :  mg とする. 財の部分集合 S  M に対する各参加者 i の価値を Vi (S ) で表す. Vi (S )  0とし , 便宜的に Vi ()  0 とする.
加者の集合を N =各参加者は必要十分財と呼ばれる財の部分集合 1 つを欲していると仮定する. 各参加者にとっては , その部分集合中の財のどれか 1 つが欠けると価値がなく,

1672

これ は 以 下の よ うな

BAP (B,b)(Bundle Assignment Problem) と呼ばれる整数計画問題で表される.
XBAP(B  b): maximize
bi xi = bx
subject toXi2N

i:Bi 3jixi  1 (8j 2 M )x 2 f0 1g (8i 2 N )なおここで x = (x1  x2  : : :  xn )> である.
ステップ 3最大利益となる割当が唯一の時は , この割当にしたがって財が配分される. 最大利益となる割当が 2 つ以上あるときは , これらのうちの 1 つの割当

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17
をランダムに選び 、その割当にしたがって財が配分される. 結果として財が配分された参加者を落札者と呼ぶ. 落札者は入札額を競売人に渡す.

上記の問題 BAP は , winner determination prob-lem, set packing problem, weighted stable set problem, weighted clique problem, weighted independent set problem 等, 様々な名前で呼ばれる. この問
題は NP-困難と呼ばれるクラスに属し , 理論的には ,解くことが困難と予想されている. しかしながら, 組合せ最適化の分野では古くから研究されており, 現在
では商業用整数計画法ソフトウェアで数千変数の問題も実用的な時間で解くことができる 1].

B  b)

参加者 i の期待効用を議論するために , BAP(B  b) とし , 参加者を以下の 3 種の最適解の集合を (類に分ける.

P (B  b) = fi 2 N j xi = 1 8x 2 (B  b)gR(B  b) = fi 2 N j xi = 0 8x 2 (B  b)gQ(B  b) = N n (P (B  b)  R(B  b))3ある.

この場合における効率的な資源配分とは, 競売人と参加者の総余剰が最大になることを示す. ここでは単純化のために売り手の財に対する価値は 0 であり, 買い手は財を購入するために十分なお金を持っており、売り手の効用は財から得た効用とお金との合計で決まるとする. 財の配分 (S1  : : :  Sn ) が効率的 (ecient)な財の配分であるとは , 任意の財の配分 (S1  : : :  Sn )に対して

XXVi (Si )  Vi (Si )i2Ni2Nが成立することである. なおここで (S1  : : :  Sn ) が財の配分であるとは, (S1  : : :  Sn ) が財の集合 M の分割となっていること, すなわち i2N Si = M , かつ任意の fi j g  N に対し i 6= j ! Si \ Sj = ] が成立することを言う.
必要十分財オークションにおいて , もし参加者が正直に自分の真の必要十分財とその価値を申告した場
合, 競売人の利益を最大にする財の割当は効率的な資源配分となる. しかし参加者は自分の真の必要十分財

ここで P (B b) Q(B b) R(B  b) に含まれる参加者とその価値を正直に申告するとは限らない. そこで ,る, と呼ばれる. passed な参加者は必ず落札者としてナッシュ均衡がどのようなものであり, ナッシュ均衡はそれぞれ passed, questionable, rejected であナッシュ均衡を参加者の戦略的な行動の結果と考え ,財が割り当てられ , rejected な参加者には財は割り当における財の割当が効率的な資源配分となっているかるため, くじびきの結果として財が割り当てられる時

入札 (    ) がナッシュ均衡であるとは , 任意の参てられない. questionable な参加者は最適解が複数あを議論する.と割り当てられない時がある.

2 N の任意の入札 (Bi  bi ) 2 2M Z" に対して, Ui (B   b )  Ui ((Bi  B ;i ) (bi  b;i )) が 成立す

参加者 i の期待効用は以下のように定義される:

8>< Vi(Bi ) ; bi (i 2 P (B b))Ui (B  b) = > (Vi (Bi ) ; bi ) (i 2 Q(B b)):0(i 2 R(B b))
ここで  = jfx 2 (B  b) j xi = 1gj=j(B  b)j は参
加者 i が落札者として選ばれる確率を表す.

4 ゲーム理論からの分析結果
4.1 効率的な資源配分とナッシュ均衡

経済学等におけるオークション研究の目的の 1 つ

加者 iB bることである. ここで以下のような入札額ベクトルのF" (B v8) を考える.

9>< N  bi = vi (8i 2 R  Q) >=F" (B  v) = >b 2 Z"  bi  vi ; k" (8i 2 P ) >:
 (B b) = (B  v)
ここで k は k  j(B  v)j を満たす正の整数である.
また, P = P (B  v ) Q = Q(B  v) R = R(B  v ) である. F" (B  v) は BAP(B  v) と BAP(B  b) の最適集合

解の集合が一致するような入札額ベクトルの集合では, 参加者の戦略的な行動によってそのオークションある.

特に重要なのは , 戦略的な行動の結果としてもオーb 2 X が極小入札額ベクトルであるとは, 任意の b0 2 Z"N に対し て, b0  b かつ b0 6= b] ならばの結果がどのようなものになるかを調べる事である.
クションが効率的な資源配分を達成するかど うかで168与えられた入札額ベクトルの集合 Xて,

 Z"N に対し

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

b0 62 X が成立することを言う.
定理 1 F" (T  v) が非空ならば , F" (T  v ) の任意の極小入札額ベクトル b に対して, (T  b ) はナッシュ均衡となる.

4ある場合のオークションを考察し , (非分割財の) ワルラス均衡が存在する場合は独立したオークションで効率的な資源配分が達成されることを示した. 本研究での必要十分財が存在する状況は , ワルラス均衡が存在しない場合を含んでおり各財の独立したオークショ

F" (T  v) においては, passed な参加者は, 自分のンでは効率的な資源配分は達成できない.

低い入札額を申告しなければならないか（ すなわち5 組合せ最適化理論からの結果真の価値より低い入札額を申告するが , ど のくらいk の値）は, 参加者の真の価値に対する最適解の個数j(B v)j, すなわち「 同点となる落札結果の数 」によって異なる.
しかし最適解の個数は常に 2n 以下であるから , 参加者の真の価値に対する最適解の個数に関わらず以下のような結果が成立する.
系 1 以下の集合の任意の極小ベクトル b に対して,(T  b ) はナッシュ均衡となる:

8
9(8i 2 R  Q) >>< N  bi = vi=nb2Z(8i2P)"  bi  vi ; 2 ">>:(B  b) = (B  v)

もし 参 加 者の 真 の 価 値に 対 す る 最 適 解が 唯 一(j(B v)j = 1) ならば , Z系 2.

N" は以下のように表せるもし 参加者の真の価値と必要十分財に対する最適解が唯一ならば , 以下の集合の任意の極小ベクト8b T  b) はナッシュ均衡となる: 9(8i 2 R  Q) >>< N  bi = vi=b2Z(8i2P)"  bi  vi ; ">>:(B  b) = (B  v)
F" (T  v) が非空ならば , Nash 均衡は存在するが ,ル  に対して, (空であれば存在しない。しかしながら , 以下の定理により入札単位が十分に小さいならば , 必ずその Nash均衡が存在する.
定理 2

も し " が 十 分 に 小 さ い 正 の 数 な ら ば,F" (T  v) は非空である.

5.1 consecutive one property

財が何らかの順序で直線上に配置され , すべての必要十分財が直線上の 1 つの区間で表される時に, これらの必要十分財の組は consecutive one property を持つという. すなわち必要十分財の組 (T1  : : :  Tn ) がconsecutive one property を持つとは, 任意の i 2 Nに対して, Ti = fj 2 M j li  j  hi g となるような(li  hi ) が存在することを言う (実際には財の番号を置換した, ある財の並び替えに対して成立すればよい).
このような consecutive one property は , 物流や周波数帯のオークションにおける選好の特徴を良く表している. 例えば周波数帯のオークションでは, 隣り合うような周波数帯を取得すると, その組合せ効果により 2 つの周波数帯の価値を足し 合せたものよりも高い価値になると言われている. しかも各参加者が価値を持つ周波数帯は , その参加者の事業地域の特性に依存して, それぞれに異なる. Kirishna and Rosenthal

5] や Rosenthal and Wang 9] は , 直線上に配置された周波数帯を考え , \local" bidder と呼ばれる参加者

は 1 つの周波数帯のみに , \global" bidder と呼ばれる参加者は 1 つの周波数帯とその右隣りの周波数帯のみに選好を持ち, 特に \global" bidder は , 該当する 2 つの周波数帯に強い補完性を持つような状況を議論している.

今ここで, 参加者が連続したいくつかの区間の周波数帯を必要十分財と考えているとしよう. このような周波数帯のオークションは consecutive one property

4.2 ワルラス均衡の非存在

このようなオークションを用いずとも, 個々の財を独立したオークションで売ることによって効率的な資源配分は達成されないのであろうか. Bikhchandani(1999) はこのような財の組合せに代替性・補完性が169を満たしている.

このような consecutive one property を満たす必要十分財オークションについて , 筆者達は以下のような結果を導いた .

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17
結果 1

必要十分財の組が consecutive one property を満5場合) に , 等確率で 1 つの解を選び出すことができる
ような多項式時間アルゴ リズムが存在することなどたす場合には , 必要十分財のオークションにおける最を示した.

題に変換することができる. この問題は古典的な動的る方は筆者たちの研究 Matsui and Watanabe 6]7] を適割当問題 BAP は , 重みづけ有向グラフの最長路問

本論文では結果における証明は省いている. 興味のあ計画法を用いて多項式時間で解く事が出来るので , 結参考にしていただければ幸いである. 筆者らの結果は ,在する.

らもダウンロード することができる.

果として BAP を多項式時間で解くアルゴ リズムが存

http://www.misojiro.t.u-tokyo.ac.jp/ tomomi/TRs/ か

入札に対して最適な財の割り当て方法が複数ある
ときは , 参加者の公平を保つため, すべての最適解の中から等確率で１つの割当方法を選ぶ. しかしながら, これには一般にはすべての最適解を列挙しなければならず , 多くの計算時間がかかる事が多い.
結果 2

必要十分財の組が consecutive one propertyを満たす場合には , 入札に対して最適な財の割り当て方法が複数あるときに等確率で１つの割当方法を選ぶ多項式時間で解くアルゴ リズムが存在する.
結果 3

必要十分財の組が consecutive one propertyを満たす場合には , 定理 1 で示したナッシュ均衡を,明示的な線形不等式系の解で ZN" に入っているものの極小解として表現することができる.

6 まとめ
以上本論文では , 必要十分財のオークションを定義

し , 戦略的な行動によっても効率的な資源配分を達成できること, 周波数オークションなどに応用できるよ

うな consecutive one property と呼ばれる性質を満たすならば , 競売人の利益を最大にするような財の最適な割り当てを求める, 多項式時間アルゴ リズムが存在し , 更に競売人の利益を最大にするような最適解が複数あるような場合 (同点となる参加者群が複数ある170

参考文献

 1 ] Andersson, A., Tenhunen, M., and Ygge, F.
(2000), \Integer programming for combinatorial
auction winner determination," Proc. of the FourthInternational Conference on Multiagent Systems(ICMAS-00).
 2 ] Bikhchandani, S. (1999), \Auctions of heterogeneous objects," Games and Economic Behavior,
vol. 26, 193{220.
 3 ] Bikhchandani, S. and Mamer, J. W. (1997),\Competitive equilibrium in an exchange economy
with indivisibilities," Journal of Economic Theory,
vol. 74, 385{413.
 4 ] de Vries, S. and Vohra, R. (2000), \Combinatorial auctions a survey," Kellog School of Management, technical report.
 5 ] Krishna, V. and Rosenthal, R. W. (1996), \Simultaneous auctions with synergies," Games andEconomic Behavior, vol. 17, 1{31.
 6 ] Matsui, T. and Watanabe, T. (2001), \Sealedbid multi-object auctions with necessary bundles
and its application to spectrums auctions ," in Intelligent Agents: Specication, Modeling, and Applications, LNAI, 78{92, Springer.
 7 ] Matsui, T. and Watanabe, T. (2001), \Multiobject auctions with necessary bundles," Discussion
Paper.
 8 ] Vickley, W. (1961), \Counter speculation, auctions and competitive sealed tenders", The Journalof Finance, vol. 16, 8{37.
 9 ] Rosenthal, R. W. and Wang R. (1996), \Simultaneous auctions with synergies and common values,"
Games and economic Behavior, vol. 17, 32{55.