FIT2005(第4回情報科学技術フォーラム)LF-004組み合わせオークションにおける効用比較に基づいた架空名義入札者発見法の提案
A Method of Discovering Shill Bidders based on a Comparison of Bidders’ Utilities

in Combinatorial Auctions
松尾徳朗 †伊藤孝行 †‡新谷 虎松 †
Tokuro Matsuo, Takayuki Ito, Toramatsu Shintani
かし，そこでのメカニズムでは架空名義入札に対する頑1 はじめに健性の性質を満たすオークションプロトコルは Pareto

人工知能やマルチエージェントの分野においてリソー効率性および誘因両立性を満たしていない．

スの効果的な分配などの問題解決のためにオークショ

一方，本稿では GVA において架空名義入札を防止ンメカニズムの研究などが注目を集めている．オークするために架空名義入札者を発見する手法を提案する．

ション理論は，近年多くの研究者により注目を浴びて本論文で提案するアルゴリズムは GVA を行った結果いる研究分野である．本論文では，組み合わせオークから架空名義入札者が存在しているかどうかを判定す

ションにおける架空名義入札を防止するために，架空る．架空名義入札の可能性があれば，オークショニア名義を企てるエージェントの発見に関して議論する．

は財の割当に関してオークションの取りやめなどの意

組み合わせオークションは，広く研究されている重思決定をすることができる．これは横尾らのアプロー要なオークションの一形態である．組み合わせオーク

チと本質的に異なる．

ションの参加者は，財を出品するオークショニアと入

架空名義入札は，ある１人の入札者が自分を含めて札を行う入札者（エージェント）であり，入札者は複２人以上の入札者をたてて入札を行うことで，不当な数の財をバンドルとして入札する．オークションの勝利益を得ることである．従って，架空名義入札者を発見者決定において，一般的には，オークションの参加者する直接的な方法は，架空名義入札者の入札値をマー全員の効用が最大化される財の割当が効率的であるとジしたときに，しないときと比べて効用が減少する入される．しかし，そのような割当を求める場合，財の札者を発見することである．しかし，マージに関する数および入札者の数が増加すれば，組み合わせ問題の基準を設けるためには妥当性のあるマージ関数の定義解を探索する必要があり，それは計算困難な問題であが必要であり，それは困難であると考えられる．そこる．多くの研究では，様々な探索アルゴリズムによりで，本稿では入札者の評価値をマージする方法を用い問題解決が試みられている．
一般化 Vickrey オークション（GVA）プロトコルは，入札者が財に対して真の申告をすることが支配戦略とずに，入札者が存在しない場合の他の入札者の効用を分析することで架空名義入札者の発見を行う．架空名
義を企てた入札者は，架空名義入札に失敗した場合になる性質である誘因両立性および割当に関して Pareto

は，効用を増加させることができないことを示す．以

効率性の特徴を持った組み合わせオークションプロト

上に基づけば，本稿で示す手法は妥当性があると考えコルである [2]．オークション理論において，多くの研られる．

究では誘因両立性の性質を持っているため GVA に焦本稿の構成は以下の通りである．２章で，定義およ点が当てられている．

びオークションに関して説明する．３章で，架空名義

横尾らは，インターネットオークションにおいて異入札者に関する効用の変化について説明し，評価値をなる e-mail アカウントを持つことで，架空名義入札がマージする方法の問題点を示す．４章では本稿におい可能となることを指摘している．架空名義入札を行うて提案する勝者を除外した効用の比較に基づいた方法

入札者は，オークションプロトコルが架空名義入札にについて説明する．５章で，オークショニアと架空名頑健でない場合に利益を得ることができる．架空名義義入札者の結託に関して考察する．６章で，本稿をま入札を防止する方法はオークション理論研究が必要ととめる．

する重要な事項である．

2 準備

横尾らのアプローチでは，オークションプロトコルや2.1 モデルメカニズムを開発することに焦点が当てられている．し本論文で提案するメカニズムに関する定義および仮† 名古屋工業大学 大学院工学研究科，‡DEAS Harvard University

定を示す．オークションへの参加者はオークショニア

95

FIT2005(第4回情報科学技術フォーラム)および入札者とする．オークショニアは複数の財を準値を付けた入札者に割り当てられる．GVA において，備し，入札者は購入したい財に対し正の評価値を入札

まず入札者はオークショニアに対して，財に対する評する．

価値 vi (Gi , θi ) を申告する．本論文では簡単のため”タイプ”による記述を省略し，vi (Gi , θi ) = vi (Gi ) で表す．

• オークションにおいて，参加する入札者の集合をN = {1, 2, . . . , i, . . . , n} とし，財の集合を G =効率的な割当は，評価値の総和が最大化される割当として計算される．

{a1 , a2 , . . . , ak , . . . , am } とする．
•G∗ = arg

viak は i 番目の入札者が k 番目の財に対する評価値である (但し，1 ≤ i ≤ n, 1 ≤ k ≤ m)．

•vi (Gi ).

i∈Ni の支払額 pi は次式で定義される．

ンドルとして入札したときの入札者 i の評価値でpi =ある (但し，1 ≤ i ≤ n, 1 ≤ k, l ≤ m)．

vj (G∗∼i ) −i=j• pai k は，入札者 i が財 ak を落札したときの支払額である．入札者 i がバンドルで入札した商品を落札
a ,al

G=(G1 ,...,Gn )オークショニアは入札者に支払額を告げる．入札者

vi (Biak ,al ) は，入札者 i が財 ak および al の財にバしたとき，支払額は pi (Bi kmax

vj (G∗ ).

i=j

G∗∼i は入札者 i 以外のすべての入札者の評価値の総) のように表される．

• 割当の集合は，G = {(G1 , . . . , Gn ) : Gi ∩ Gj =φ, Gi ⊆ G} とする．Gi は，入札者 i に対する商品和が最大化される組み合わせである．入札者 i を除いた場合の，他の入札者の評価値の総和が最大化される割当は次式で定義される．

G∗∼i = arg maxの割当である．

G\GiAssumption 1 (準線形の効用) 入札者 i の効用 ui は，入札者 i に割り当てられる財に対する支払い額 pi と入札者 i の評価値 vi の差 ui = vi − pi で表される．この

vj (Gj ).

N −i

2.3 スキーマーの効用について
本稿では，オークションにおいて，架空名義を企てるエージェントをスキーマーと呼ぶ．スキーマーは架ような効用を準線形の効用と呼び，本論文では準線形

空名義入札者が勝者とならない場合は，効用を増加さの効用を仮定する．

せることはできない．つまり，スキーマーは，架空名

Assumption 2 (評価値の単調性) 入札者が入札する

義入札者をおとりにするだけでは効用を増加させるこ真の評価値に関して，バンドル B および B （但し，B =とはできず，複数の架空名義入札者およびそれらをたB  ）に対して，B ⊂ B  であれば，vi (B, θi ) ≤ vi (B  , θi )が成り立つ．てたスキーマーが勝者にならない場合は，効用を増加させることはできない．以下の定理によりこの特徴を示す．

それぞれの入札者 i は財およびバンドルで表される財の部分集合 Gi ⊆ G に対する選好を持つ．形式的に，Theorem 1 (スキーマーの効用増加) スキーマーは，それぞれの入札者 i はタイプの集合 Θ において，自ら架空名義入札者がオークションに勝たない場合，効用のタイプ θi を持つ．そのタイプに基づいて，入札者がを増加させることはできない．

i
割当の集合 Gi を pGi で購入するとき，入札者の効用スキーマーを入札者 i とする．オークションにおいivi (Gi , θi ) − pGi が表される（但し，入札者 i のバンドて，架空名義入札者が勝者にならないときに入札者 i のル Gi ⊆ G に対する評価値は vi (Gi , θi )）．

2.2

効用 ui は減少しないことを示せば良い．入札者 i が架

GVA: Generalized Vickrey Auction

空名義入札者をたてないときの入札者 i のペイメントpi は pi = i=j vj (G∗∼i ) − i=j vj (G∗ ) となる．

GVA は，Vickrey-Clarke-Groves メカニズムから発両立性および Pareto 効率性の特長を持っている．オー

入札者 i が架空名義入札者をたてるとき，入札者 i の∗
ペイメント p i は p i = i=j vj (G ∼i ) − i=j vj (G∗ )クションプロトコルが Pareto 効率であるとは，オークとなる．

展され，架空名義入札が存在しない状況において，誘因

こ こ で 次 の 証 明 で は pi

ションに参加するすべてのエージェントの効用の総和≥

pi を 示 す．オ ー ク

すなわち社会的総余剰が最大となる性質を持つことでション に お い て ，入 札 者 i の た て た 架 空 名 義 入 札ある．もし，財の数が一つであるとき，財は最大の評価者がオークションの勝者にならないと仮定する．こ96

FIT2005(第4回情報科学技術フォーラム)２を比較し，それぞれが同一の勝者の場合に効用の差の場合，オークションにおいて割当の集合は変化し

な い ．つ ま り，G= G /s が 成 立 す る ．p i およ び pi の 差 は 次 の よ う に 示 さ れ る ．p i − pi =vj (G∼i ) −vj (G ) − ( i=j vj (G∼i ) − i=j 
i=ji=j vj (G)) =i=j vj (G∼i ) −i=j vj (G∼i ). よって， i=j vj (G∼i ) ≥ i=j vj (G∼i ).

がある場合が架空名義入札の可能性がある場合である．

財 の 数 を m と し ，財 の 集 合 を M{a1 , a2 , . . . , am } と す る ．入 札 の 集 合 は B==た方法を用いて架空名義入札者を発見する．本稿では，{B1 , . . . , Bi−1 , Bi+1 , . . . , Bn } ∈ G∼i と す る ．入札の集合は B  = B ∪ {B1 , . . . , Bn  } ∈ G∼i とする．集の入札者が仮にオークションに参加していないとした

しかし，入札者の評価値に対する基準はそれぞれ異なっているため，妥当であると評価される評価値のマージ関数を定義することは困難である．そこで，本稿では入札者をマージするのではなく，Theorem 1 を利用し勝者を除外した効用比較による方法と呼ぶ．それぞれ場合のオークションの勝者および効用を計算し，勝者

合 {B1 , . . . , Bn  } は架空名義入札の部分集合であるとの効用の変化に基づき架空名義入札者と特定する．次する．

節に，本稿で提案する架空名義入札者の発見手法の詳G∼i

こ こ で ，割 当 G∼i お よ び
は G∼i
=
n
n+n

max x=1 px yx で表され，G∼i = max x=1 px yx
s.t. x|z∈Sx yx ≥ 1, ∀z ∈ {1, . . . , m}, yx ∈ {0, 1} となnn+nる．よって，max x=1 px yx ≤ max x=1 px yx とな細を示す．

り，すなわち，次式が成立する．

ンの勝者にならない場合は，スキーマーは効用を増加vj (G∼i ) ≥i=j

3.2 勝者を除外した効用比較による方法
上で示した定理に基づけば，架空名義入札は，それに関わっているできるだけ多くの入札者がオークショさせることができない．そこで，組み合わせオークショ

vj (G∼i )ンにおける参加者を擬似的に参加させない場合と実際

i=jの結果を比較することで架空名義入札に関わる入札者.
よって，pi ≥ pi ．ui = vi − pi とすれば ui ≥ ui が成を発見することができる．
本稿で提案する手法ではまず，実際に GVA による立する．

財の割当を計算する．勝者の効用を計算する．その後

3 入札者同士の結託の発見
3.1に，それぞれの勝者に関して仮に参加していない場合

評価値マージ法のオークションを実施し，財の割当および効用を計算

架空名義入札は入札者の効用の変化により発見できする．実際のオークションと勝者を一人ずつ除外した

る．具体的な発見手法としては，入札者の評価値を，す場合のオークションにおける効用の差を計算し，そのべての組み合わせにおいて，入札者の評価値をマージ場合，共通に効用が減少する入札者を探索し，架空名することにより統合する．それぞれにおいてオークショ義入札者を発見する．オークショニアは架空名義入札ンの勝者および効用を計算し，勝者の効用の変化に基者全員を除外したオークションを実施し，財を割り当づき架空名義入札者を特定するという方法が有効であてる．以下に，具体的にアルゴリズムを示す．

[Algorithm] (Step 1) n 人の入札者が参加したると考えられる．
架空名義入札は，あるバンドルを複数に分けて，複オークションにおいて，まず，GVA の方法に基づい数の架空名義入札者によりそれぞれ分割して入札されて，勝者を決定する．勝者は，評価値の総和が最大化

される割当 G∗ = arg maxG=(G1 ,...,Gn ) i∈N vi (Gi )た場合に有効となる [1]．分割せずに（つまり架空名義として計算される．入札者 i の支払額 pi は pi =∗∗∗i=j vj (G∼i ) −i=j vj (G ) で定義される．G∼i は入札者をたてずに）入札した場合と，分割して（すなわち架空名義入札をして）入札し，財を得た場合に，それぞれの効用を計算し，後者の効用が前者より大きい

入札者 i 以外のすべての入札者の評価値の総和が最場合に架空名義入札の可能性がある．したがって，以大化される組み合わせである．入札者 i を除いた場合

下の手続きで架空名義入札者の発見が可能になる．まの，他の入札者の評価値の総和が最大化される割当はG∗∼i = arg maxG\Gi N −i vj (Gj ) で定義される．

ず，オークションにおいて入札された評価値に基づき，単純に勝者とペイメントを計算する．計算結果を結果(Step 2) ここで，勝者の効用が計算される．勝者の１とする．次に，すべての入札者の組み合わせに関し集合を簡単のため W = {1, 2, . . . , ι, . . . , θ} とする．そて，定義されたマージ関数により評価値をマージし，それぞれの勝者の効用 uι が格納される．の場合のオークションの勝者および評価値を計算する．

(Step 3) 入 札 者 θ が 参 加 し な かった 場 合の オ ー ク ション を 試 み る ．割 当 は ，G∗∼θ=

計算結果を結果２とする．ここで，結果１および結果

97

FIT2005(第4回情報科学技術フォーラム)arg maxG=(G1 ,...,Gn )N −θ vi (Gi ) となる．

4 オークショニアと入札者の結託(Step 4) (Step 3) の割当において，実際のオークションにおける勝者 W = {1, 2, . . . , ι, . . . , θ − 1} に関架空名義入札者をたてたりするだけではなく，オークして，効用を計算する．

ショニアが関与していることがある．オークショニア

オークションにおいて，入札者どうしが結託したり(Step 5) 実際のオークションにおけるそれぞれの勝と入札者が結託することがある．形式的にオークショ者の効用 uι から，自分自身が参加しないオークションンは行っているが，カルテルを結んでいる状況である．

以外（例えば，θ が参加しないオークション）でのそれ

本状況を分析するには，売り手の total revenue を計算∼θ
ぞれの勝者の効用 u∼θι の差 uι − uι を計算する．

することで発見が可能になる．本稿で示した手法によ(Step 6) (Step 5) において，効用の差 uι − u∼θι がり，架空名義入札者およびスキーマーを発見する．架存在する勝者の集合 {w∼ι } ∈ W を発見する．この結空名義入札者を除外した場合のオークションの結果を果は，格納される．

計算する．この際に，大幅に total revenue が減少して(Step 7) (Step 6) における結果に関して，{w∼ι \いる場合，オークショニアと入札者が結託している可θ} ∈ W = {w∼θ \ ι} ∈ W のような共通の場合に効用が減少する入札者をリストアップして，オークショニ能性を指摘できる．
具体的に，まず実際のオークションにおいて GVA にアに送信する．

よる勝者が計算される．ここで，オークションのペイメ
nントの合計 i pi が計算される．前章で示したように，
n入札者を除外した場合のペイメントの合計 N \ι pi を

(Step 8) オークショニアは，入札者 N \ w でオークションを再度実施する．

3.3

具体例

および２財が出品されているときの具体例を示す．そ計算する．架空名義入札者を発見する．入札者のペイnn
メント N \w pi を計算する．この際に， N \w pi に対n
して， i pi との差が大きい場合は，total revenue がのうち，１人のスキーマーおよび１人の架空名義入札大幅に減少しているといえる．

者が存在する場合を考える．入札者の評価値は以下で5 おわりに

本節では，上記アルゴリズムに関して，入札者が５人あるとする．

本稿では，組み合わせオークションにおいて架空名

a ,a
入札者１の評価値 v1 (B1 1 2 ) : {8, 9, 17}
a ,a
入札者２の評価値 v2 (B2 1 2 ) : {9, 8, 17}
a ,a
入札者３の評価値 v3 (B3 1 2 ) : {12, 0, 12}
a ,a
入札者４の評価値 v4 (B4 1 2 ) : {0, 12, 12}
a ,a
入札者５の評価値 v5 (B5 1 2 ) : {0, 0, 20}

義入札を防止するために，架空名義入札者の発見手法を提案した．提案した勝者を除外した効用計算による手法では，入札者の評価値をマージするより効果的にオークションの結果から架空名義入札者の存在を判定することができる．評価値のマージのためのマージ関数に関して妥当性を持ったマージ法を定義することはここで，勝者は入札者３および４となり，支払額はそれぞれ 8 となる．u3 および u4 はそれぞれ 4 となる．
上記アルゴリズムに基づき，勝者３を除外したオーが存在する場合においても，架空名義入札者の発見が可能であり，またオークショニアとスキーマーが結託クションを行う．この場合，勝者は入札者２および４する場合も total revenue を計算することで，結託を発となり，支払額 p2 は 8，p4 は 11 となる．u4 は 1 とな

見することが可能となる．

り，効用は減少する．

参考文献

同様に，勝者４を除外した場合にも同じことが言え[1] T. Matsuo, T. Ito, T, Shinitani. 組み合わせオークションにおける不正入札者の発見手法について.

る．つまり，勝者を除外した場合に，効用が減少する
他の勝者が架空名義入札者の可能性があるといえる．

3.4

困難である．本稿で示した方法では，複数のスキーマー

第１９回人工知能学会全国大会講演論文集, 2005.

複数のスキーマー[2] P. Milgrom. Putting Auction Theory to Work.

前章で示した，評価値マージ法においては複数のス

Cambridge University Press, 2004.

キーマーが存在する場合の架空名義入札者の同定は困難である．一方，本論文で提案した勝者を除外した効用[3] M. Yokoo, Y. Sakurai, and S. Matsubara. The ef-比較による方法では，複数のスキーマーが存在する場

fect of false-name bids in combinatorial auctions:

合においても架空名義入札者の発見は可能である．共通

New fraud in Internet auctions. Games and Economic Behavior, 46(1):174–188, 2004.に効用が減少する入札者グループが複数存在する場合は，スキーマーが複数存在していることを表している．

98