The 19th Annual Conference of the Japanese Society for Artificial Intelligence, 2005

3E2-01

組み合わせオークションにおける不正入札者の発見手法の提案
A Discovering Method of Shill bidders in Combinatorial Auctions
松尾徳朗∗1 ，伊藤孝行∗1∗2 ，新谷虎松∗1Tokuro Matsuo, Takayuki Ito, Toramatsu Shintani∗1

名古屋工業大学大学院工学研究科情報工学専攻

Dept. of Computer Science and Engineering, Graduate School of Engineering, Nagoya Institute of Technology∗2DEAS, Harvard University

This paper presents a method for discovering and detecting shill bids in combinatorial auctions. Combinatorial
auctions have been studied very widely. The Generalized Vickrey Auction (GVA) is one of the most importantcombinatorial auctions because it can satisfy the strategy-proof property and Pareto eﬃciency. As Yokoo et al.
pointed out, false-name bids and shill bids pose an emerging problem for auctions, since on the Internet it is easy
to establish diﬀerent e-mail addresses and accounts for auction sites. Yokoo et al. proved that GVA cannot satisfy
the false-name-proof property. Moreover, they proved that there is no auction protocol that can satisfy all threeof the above major properties. Their approach concentrates on designing new mechanisms. As a new approachagainst shill-bids, in this paper, we propose a method for ﬁnding shill bids with the GVA in order to avoid them.
Our algorithm can judge whether there might be a shill bid from the results of the GVA’s procedure. However, astraightforward way to detect shill bids requires an exponential amount of computing power because we need tocheck all possible combinations of bidders. Therefore, we propose an improved method for ﬁnding a shill bidder.
The method is based on winning bidders, which can dramatically reduce the computational cost. The preliminary
results demonstrate that the proposed method successfully reduces the computational cost needed to ﬁnd shill bids.
The contribution of our work is in the integration of the theory and detecting fraud in combinatorial auctions.

1.

はじめにに満たされるオークションプロトコルが存在しないことを証明している．そこでは架空名義入札に対する頑健性の性質を満たすオークションプロトコルを提案している．横尾らのアプロー
チでは，オークションプロトコルやメカニズムを開発することに焦点が当てられている．しかし，そこでのメカニズムでは架空名義入札に対する頑健性の性質を満たすオークションプロト
コルは Pareto 効率性および誘因両立性を満たしていない．
一方，本稿では GVA において架空名義入札を防止するために架空名義入札者を発見する手法を提案する．本論文で提案するアルゴリズムは GVA を行った結果から架空名義入札者が存在しているかどうかを判定する．架空名義入札の可能性があれば，オークショニアは財の割当に関してオークションの取りやめなどの意思決定をすることができる．つまり，本稿で示すア
プローチでは，架空名義入札を防止するためのアルゴリズムを開発する．これは横尾らのアプローチと本質的に異なる．
架空名義入札は，ある１人の入札者が２人またはそれ以上の入札者をたてて入札を行うことで，不当な利益を得ることである．従って，架空名義入札者を発見する直接的な方法は，架空名義入札者の入札値をマージしたときに，しないときと比べて効用が減少する入札者を発見することである．マージの方法は３章において示す．しかし，この直接的な手法では，入札者のすべての組み合わせを調べる必要があり，指数関数的に増加した計算コストが必要となる．
本稿では，架空名義入札者を発見するための改良した手法を提案する．本手法は，brute force アルゴリズムに基づいており，大幅に計算コストを減少させることができる．
本稿の構成は以下の通りである．２章で，定義およびオークションに関して説明する．３章で，shill-biddable な割当を定義し，４章では本論文において用いられる brute force アルゴリ
ズムを示す．５章で，入札者の数が増加した場合のヒューリスティックスを説明する．６章で予備実験および考察を示し，７
章で本稿をまとめる．

本論文では，組み合わせオークションにおける架空名義入札を防止するために，架空名義を企てるエージェントの発見に関して議論する．オークション理論は，近年多くの研究者により注目を浴びている研究分野である．人工知能やマルチエージェン
トの分野においてリソースの分配などの問題解決のためにオークションメカニズムの研究などが注目を集めている．
組み合わせオークションは，広く研究されている重要なオークションの一形態である．組み合わせオークションにおいて，入札者は複数の財をバンドルとして入札する．組み合わせオークションの主な研究対象は勝者決定問題の解決である．そこでは，財の数に対してオークショニアの revenue を最大化する組み合わせを求めるため，計算困難な問題である．多くの研究では，様々な探索アルゴリズムにより問題解決が試みられている．
一般化 Vickrey オークション（GVA）プロトコルは，入札者が財に対して真の申告をすることが支配戦略となる性質である
誘因両立性および割当に関して Pareto 効率性の特徴を持った組み合わせオークションプロトコルである [2]．オークション理論において，多くの研究では誘因両立性の性質を持っているため GVA に焦点が当てられている．
横尾らは，インターネットオークションにおいて異なる e-mailアカウントを持つことで，架空名義入札が可能となることを指摘している．架空名義入札を行う入札者は，オークションプロ
トコルが架空名義入札に頑健でない場合に利益を得ることができる．架空名義入札を防止する方法はオークション理論研究が必要とする重要な事項である．
横尾らは，GVA が架空名義入札に対する頑健性を満足しないことを証明している．さらに，架空名義入札に対する頑健性，Pareto 効率性，誘因両立性および個人合理性などの性質が同時
連絡先: 松尾徳朗，名古屋工業大学大学院工学研究科情報工学専攻，tmatsuo@ics.nitech.ac.jp1

The 19th Annual Conference of the Japanese Society for Artificial Intelligence, 2005

2.

準備2.1

モデル

pi =

2.3

• pai k は，入札者 i が財 ak を落札したときの支払額である．
入札者 i がバンドルで入札した商品を落札したとき，支払a ,a額は pi (Bi k l ) のように表される．
• 割当の集合は，G = {(G1 , . . . , Gn ) : Gi ∩ Gj = φ, Gi ⊆G} とする．Gi は，入札者 i に対する商品の割当である．

架空名義入札に対する不頑健性

3.

Shill-biddable Allocation

3.1

定義

エージェントが架空名義入札者を作ることで効用を増加させることができる割当を shill-biddable allocation と定義する．本
稿では，架空名義入札（shill-biddable allocation）の可能性を発見する手法を提案する．
Definition 1 (Shill-biddable allocation) Shill-biddable
な割当とは，架空名義入札者をたてたエージェントの効用が架空名義入札者を用いないオークションにおける効用以上になる割当である．
例えば，あるオークションにおいて勝者となった入札者 i のa ,...,ak ,...,am) であるとする．ui (Bia1 ,...,am ) は，入効用が ui (Bi 1
札者 i がこのオークションにおいて架空名義入札者をたてない場合の，入札者 i のバンドルのセット (a1 , . . . , am ) を含んだ効用の総和である．
架空名義入札者が存在する状況を考える．架空名義入札者をたてた入札者 i はバンドル (a1 , . . . , ak ) に入札し，架空名義入札者は残りの財のバンドル (ak+1 , . . . , am ) に入札する．それぞれの入札者は入札した商品を落札できたとする．架空名義入札者a ,...,ak)の効用を u i とする．この場合，入札者 i の効用は ui (Bi 1
ak+1 ,...,amとなり，架空名義入札者の効用は u i (Bi) となる．
Shill-biddable な割当は，次式が成立するときに定義される．

Assumption 1 (準線形の効用) 入札者 i の効用 ui は，入札者 i に割り当てられる財に対する支払い額 pi と入札者 i の評価値 vi の差 ui = vi − pi で表される．このような効用を準線形の効用と呼び，本論文では準線形の効用を仮定する．
Assumption 2 (評価値の単調性) 入札者が入札する真の評価値に関して，バンドル B および B （但し，B = B  ）に対して，B ⊂ B  であれば，vi (B, θi ) ≤ vi (B  , θi ) が成り立つ．
Assumption 3 (一人のスキーマー) 本論文では，架空名義入札を企てるのは一人以下の入札者であると仮定する．複数の入札者が存在するとき，分析はより困難になるため，ここでは架空名義を企てるエージェントは単一であるとする．
それぞれの入札者 i は財およびバンドルで表される財の部分集合 Gi ⊆ G に対する選好を持つ．形式的に，それぞれの入札者 i はタイプの集合 Θ において，自らのタイプ θi を持つ．そGのタイプに基づいて，入札者が割当の集合 Gi を pi i で購入すGiるとき，入札者の効用 vi (Gi , θi ) − pi が表される（但し，入札者 i のバンドル Gi ⊆ G に対する評価値は vi (Gi , θi )）．

a ,...,a ,...,aa ,...,aa,...,ammkkui (Bi 1) ≤ F (ui (Bi 1), u i (Bi k+1)).
上式において，F (·) は効用をマージするために用いられる．

GVA: Generalized Vickrey Auction

GVA は，Vickrey-Clarke-Groves メカニズムから発展され，架空名義入札が存在しない状況において，誘因両立性およびPareto 効率性の特長を持っている．オークションプロトコルがPareto 効率であるとは，オークションに参加するすべてのエージェントの効用の総和すなわち社会的総余剰が最大となる性質を持つことである．もし，財の数が一つであるとき，財は最大の評価値を付けた入札者に割り当てられる．GVA において，まず入札者はオークショニアに対して，財に対する評価値 vi (Gi , θi )を申告する．本論文では簡単のため”タイプ”による記述を省略し，vi (Gi , θi ) = vi (Gi ) で表す．効率的な割当は，評価値の総和が最大化される割当として計算される．
G=(G1 ,...,Gn )N−i

横尾らは，組み合わせオークションにおける架空名義入札の影響を分析している [3] 架空名義入札は，ある一人の入札者が複数の e-mail アカウントのような複数のインターネットオークションの ID を用いてオークションに参加することをいう．上記の研究で得られた結果は以下のように要約される．
（１）誘因両立的および Pareto 効率的である Vickrey-Clarke-Groves (VCG) メ
カニズムは，架空名義入札に対して頑健ではない．
（２）Pareto
効率性を満たす架空名義入札に頑健な組み合わせオークション
プロトコルは存在しない．

• vi (Biak ,al ) は，入札者 i が財 ak および al の財にバンドルとして入札したときの入札者 i の評価値である (但し，1 ≤ i ≤ n, 1 ≤ k, l ≤ m)．

vj (G∗ ).

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

maxG∗∼i は入札者 i 以外のすべての入札者の評価値の総和が最大化される組み合わせである．入札者 i を除いた場合の，他の入札者の評価値の総和が最大化される割当は次式で定義される．
G∗∼i = arg maxvj (Gj ).

• オ ー ク ション に お い て ，参 加 す る 入 札 者 の 集 合={1, 2, . . . , i, . . . , n} と し ，財 の 集 合 をを N
G = {a1 , a2 , . . . , ak , . . . , am } とする．

G∗ = arg

vj (G∗∼i ) −i=j

本論文で提案するメカニズムに関する定義および仮定を示す．
オークションへの参加者はオークショニアおよび入札者とする．
オークショニアは複数の財を準備し，入札者は購入したい財に対し正の評価値を入札する．

2.2

3.2

計算困難性

架空名義入札の特徴は，架空名義入札者をたてたエージェン
トがバンドルとしての評価値を分割し，架空名義入札者にそれぞれ入札させることで効用を増加させることができる点である．
エージェントが付けた評価値をマージし，その場合のエージェントの効用およびマージせずそのままの手続き求めた効用とを比較することで，架空名義入札者の可能性を発見することができる．評価値をマージする組み合わせは 2n − n − 1 であり，計算コストは O(2n ) となる．その上，GVA おいて勝者のペイメントを決定するとき，それぞれの勝者に関して O(2n ) だけの計算コストが必要となる．したがって，割当が shill-biddable であるかどうか判断するには莫大な計算コストが必要となる．そこ
で，本稿では shill-biddable な割当を発見する際の計算コストの削減手法およびエージェントの数が多くなった場合のヒューリスティックな手法を提案する．

vi (Gi ).

i∈N

オークショニアは入札者に支払額を告げる．入札者 i の支払額 pi は次式で定義される．

2The 19th Annual Conference of the Japanese Society for Artificial Intelligence, 2005

4.

Brute Force Algorithm

4.1

架空名義入札と効用

Function Detecting a Shill bid
begin
Determining winners and calculating
payments based on GVA.
Creating a power set S for a set of players.
for each s ∈ S
Merging players’ evaluation values in s
by merge function f (s).
Determining winners and calculating payments
based on merged evaluation values by GVA.
uf (s) := the utility of s after merged.
usums := sum of the utilities in s before merged.
if uf (s) < usums
return True
return False
end.

オークションにおいて，架空名義入札者をたてたエージェン
トは架空名義入札者が勝者とならない場合は，効用を増加させることはできない．つまり，架空名義入札者をたてたエージェ
ントは，架空名義入札者をおとりにするだけでは効用を増加させることはできず，複数の架空名義入札者およびそれらをたてた元の入札者が勝者にならない場合は，効用を増加させることはできない．以下の定理によりこの特徴を示す．

Theorem 1 (架空名義入札者は勝者とならなければならない)
架空名義入札者をたてた入札者は，架空名義入札者がオークションに勝たない場合効用を増加させることはできない．
架空名義入札者をたてたエージェントを入札者 i とする．オークションにおいて，架空名義入札者が勝者にならないときに入札者 i の効用 ui は減少しないことを示せば良い．入札者 i が架空名義入札者をたてないときの入札者 i のペイメント pi は
pi = i=j vj (G∗∼i ) − i=j vj (G∗ ) となる．

ここで，マージ関数 f を定義し，マージされた入札者の評価値および入札者の集合からのペイメントを示す．マージされたエージェントの集合を {i, i + 1, . . . , j} ∈ N とする．

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

Definition 2 (マージ関数) f は入札者の集合 {i, i + 1, . . . , j}がマージされるとき f (i, i + 1, . . . , j) として定義されるマージ関数である．

ここで次の証明では pi ≥ pi を示す．オークションにおいて，入札者 i のたてた架空名義入札者がオークションの勝者にならないと仮定する．この場合，オークションに/s がおいて割当の集合は変化しない．つまり，G = G 成立する．p i および pi の差は次のように示される．p i −pi =v (G∼i ) −v (G ) − ( i=j vj (G∼i ) −i=j ji=j jv (G)) =v (G∼i ) −v (G∼i ).
i=j ji=j ji=j j
i=jvj (G∼i ) ≥i=jそのまま GVA を行った場合とマージした場合で入札者の効用を比較するためにマージされるエージェントの評価値 v ，ペイメント p および効用 u は次のように定義される．
vf (i,i+1,...,j) はエージェント {i, i + 1, . . . , j} の評価値に基づき，マージされた評価値である．pf (i,i+1,...,j) はマージが行われる場合のエージェント {i, i + 1, . . . , j} のペイメントである．uf (i,i+1,...,j) はマージが行われる場合のエージェント {i, i +1, . . . , j} の効用である．
本章では，vf (i,i+1,...,j) はそれぞれの財に対するエージェン
トの評価値間の最大値の関数とする．

よって，vj (G∼i ).

財の数を m とし，財の集合を M = {a1 , a2 , . . . , am } とする．
入札の集合は B = {B1 , . . . , Bi−1 , Bi+1 , . . . , Bn } ∈ G∼i とする．入札の集合は B  = B ∪ {B1 , . . . , Bn  } ∈ G∼i とする．集合 {B1 , . . . , Bn  } は架空名義入札の部分集合であるとする．
n
ここで，割当 G∼i および G∼i は G∼i = max x=1 px yx で表され，G∼i = max

n+n
x=1

px yx s.t.

max

n+n
x=1x=1p x yx ≤もし，架空名義入札者の可能性がある場合，次式が成り立つ．

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

i=j.

yx ≥ 1, ∀z ∈

nx|z∈Sx{1, . . . , m}, yx ∈ {0, 1} となる．よって，maxMaximum selection method 入 札 者 i の 評 価 値(via1 , via2 , . . . , vi (Bia1 ,...,am )) に 関 し て ，vf (i,i+1,...,j)が(maxi,i+1,...,j {via1 },
maxi,i+1,...,j {via2 },. . . ,a1 ,...,am}) として表される．
maxi,i+1,...,j {vi (Bivj (G∼i ) ≥

vj (G∼i )i=j

よって，pi ≥ pi ．ui = vi − pi とすれば ui ≥ ui が成立する．

4.2

ui,i+1,...,j > uf (i,i+1,...,j)i,i+1,...,ji,i+1,...,jui,i+1,...,j は同一の財の割当において，分割入札の場合の入札者 {i, i + 1, . . . , j} の効用の和である．
マージされた評価値の例を示す．４人の入札者および３つの財M = (a1 , a2 , a3 ) のオークションを考える．入札者はバンドル{(a1 ), (a2 ),(a3 ),(a1 , a2 ),(a1 , a3 ),(a2 , a3 ),(a1 , a2 , a3 )} に対して入札する．

勝者ベースアルゴリズム

定理１に基づいて，組み合わせオークションにおける勝者の評価値を用いた架空名義入札の可能性を決定する手法を提案する．架空名義入札者はある単一のエージェント（入札者）を分割したものになる．つまり，架空名義入札者を生成したエージェ
ントは評価値を分割することにより効用を増加させることができる．架空名義入札者を作成した入札者および架空名義入札者がオークションの勝者となるとき，分割された評価値をマージし，マージしない場合と比較することでエージェントの効用の差を計算できる．そのまま GVA を行った場合の効用およびマージした場合の効用の差に基づいた勝者ベースアルゴリズムを提案する．下にアルゴリズムの詳細を示す．

入札者１の評価値 v1 (B1a1 ,a2 ,a3 ) : {7, 0, 0, 7, 7, 0, 7}
入札者２の評価値 v2 (B2a1 ,a2 ,a3 ) : {0, 0, 0, 0, 0, 0, 16}a ,a ,a
入札者３の評価値 v3 (B3 1 2 3 ) : {0, 6, 0, 6, 0, 6, 6}
入札者４の評価値 v4 (B4a1 ,a2 ,a3 ) : {0, 0, 8, 0, 8, 8, 8}
勝者は入札者１，３および４となり，社会的総余剰は $21 となる．入札者１は，財 a1 を $2 で購入し，入札者３は財 a3 を$1 で購入し，入札者４は財 a4 を $3 で購入する．それぞれの入札者の効用は $5 となる．
ここで，架空名義入札者を発見するために，入札者の評価値をマージする．入札者１および３の評価値がマージされた場合，マージされた評価値 vf (1,3) は {7, 6, 0, 7, 7, 6, 7} となる．入札

Input: evaluation values of bundles for each player.
Output: True if there is a shill bid.
False if there is no shill bid.

3

The 19th Annual Conference of the Japanese Society for Artificial Intelligence, 2005
者１および３のマージされたペイメント pf (1,3) は 16 − 8 = 8と計算され $8 となる．この場合入札者４のペイメント p4 は $3となる．効用 uf (1,3) は 13 − 8 = 5 となる．入札者１および３が同一の入札者であれば，評価値を分割することにより効用を増加させることができることを示している．
マージに関してすべての可能性を計算することで，架空名義入札者の存在の可能性を発見できるが，エージェントの数が増加すれば計算コストは指数関数的に増加する．この問題を解決するために次章において greedy なアルゴリズムを提案する．

5.

多数の入札者が存在するときの対処法

入札者が多い場合において計算コストに関する問題を解決するために，架空名義入札者を発見するアルゴリズムを提案する．
以下を仮定する．

Assumption 4 (架空名義入札の可能性) エージェントにより入札された評価値の一つでも，バンドル（財をまとめて購入する）として入札された評価値がそれぞれの財の評価値の総和以上
k,k+1,...,l)≤であるとき，架空名義入札は成功する．つまり vi (Bil kvである．
ik
下にアルゴリズムを示す．アルゴリズムの特徴は架空名義入札の可能性のある入札者を探索する点である．探索空間を減少させるために，探索候補の枝借りに基づいて架空名義の可能性のあるエージェントを探索する．
[Algorithm ] (Step 1) 勝者は入札者の評価値に基づき決定される．勝者の効用 ui は格納される．(Step 2) システムは勝者の評価値および勝者のペイメントを決定する入札者の評価値を格納する．(Step 3) 上記の仮定のような評価値が探索される．探索に基づき，評価値の集合が以下の２つうちから場合分けされる．
（１）上記の仮定において示されている評価値のタイプが存在しない．
（２）上記の仮定において示されている評価値のタイプが存在する．(Step 4) 前者（１）の場合，勝者のペイメントが計算される．後者（２）の場合，(step5) に移る．
(Step 5) システムは，上記の仮定において示されてるエージェントの評価値に基づきペイメントが決定される入札者を発見する．(Step 6) 勝者の評価値が４章において示されている方法に基づきマージされる．それぞれのマージに関して，勝者の効用 uf (·) は格納される．入札者の効用 ui はメージされた入札者の効用 uf (·) と比較される．(Step 7) (step 5) における比較に基づいて，ui および uf (·) の差が等しくない場合，架空名義入札に関わった可能性のある入札者のリストがオークショニアに示される．

6.

議論

6.1

予備実験

図 1: Experimental Resultsいることがある．オークショニアと入札者が結託することがある．形式的にオークションは行っているが，カルテルを結んでいる状況である．本状況を分析するには，売り手の total revenueを計算することで発見が可能になる．本稿で示したように，買い手の入札値をマージし，架空名義入札者を発見する．その後，架空名義入札者を除外した場合のオークションの結果を計算する．この際に，大幅に total revenue が減少している場合，オークショニアと入札者が結託している可能性を指摘できる．

7.

本稿では，組み合わせオークションにおいて架空名義入札を防止するために，架空名義入札者の発見手法を提案した．提案
したアルゴリズムは GVA に基づいたオークションの結果から架空名義入札者の存在を判定することができる．しかし，直接的な方法では考えられるすべての組み合わせに関して計算するため，財の数や入札者の数に対して計算コストが指数関数的に増加する．そこで，本稿では架空名義入札者を発見するための改良した手法を提案した．本手法は勝者に基づいている．予備実験では，本稿で示したアルゴリズムを用いることで計算時間が大幅に減少することを確認できた．

参考文献

勝者ベースアルゴリズムを用いて予備実験を行った．実験では架空名義入札者が存在するかどうかを判定する平均時間として求めた．図 1 は財の数が３つのときの実験結果である．入札者の数を３人から１７人に変化させて 1000 回異なる問題を生成して実験を行った．縦軸は平均時間を示し，横軸は入札者の人数を表している．５章で示したアルゴリズムに関して，計算コストが勝者ベースアルゴリズムより少ないことが確認された．
なお，ここでは両者ともに文献 [1] で提案されている CASS と呼ばれるアルゴリズムを用いている．

6.2

おわりに

[1] Y. Fujishima, K. Leyton-Brown, and Y. Shoham. Taming the computational complexity of combinatorial auctions: Optimal and approximate approaches. In Proc.
of the 16th International Joint Conference on Artificial
Intelligence (IJCAI99), pages 548–553, 1999.
[2] P. Milgrom. Putting Auction Theory to Work. Cambridge University Press, 2004.
[3] M. Yokoo, Y. Sakurai, and S. Matsubara. The eﬀectof false-name bids in combinatorial auctions: New fraud
in Internet auctions. Games and Economic Behavior,
46(1):174–188, 2004.

オークショニアと入札者の結託オークションにおいて，入札者どうしが結託したり架空名義入札者をたてたりするだけではなく，オークショニアが関与して4