FIT2010（第 9 回情報科学技術フォーラム）RF-002

架空名義操作不可能な組合せオークションメカニズム:

VCG メカニズムの改良
A False-name-proof Combinatorial Auction Mechanism:
A variation of VCG Mechanism
毛利 貴之∗

東藤 大樹 ∗†

岩崎 敦 ∗

横尾 真 ∗

Takayuki Mouri

Taiki Todo

Atsushi Iwasaki

Makoto Yokoo

告することが最適な戦略 (支配戦略) となることを保証

1 序論

する組合せオークションメカニズムである．

1.1 研究の背景

インターネットは組合せオークションのような複雑なインターネットオークションは, 急成長している電子取引を実行するインフラを安価に提供しており，組合せ

商取引の重要な一分野であり，人工知能／エージェン

オークションの利用は拡大していくと予想される．このト技術の有望な適用領域である [1, 14]．インターネッ

ようにインターネットは組合せオークションを行う上でトの利用により, 低コストで大規模なオークションが実

非常に優れた環境を提供している一方で，ネットワーク

行可能となった反面, 不特定多数の人々が参加可能であでの匿名性を利用した新しい不正行為である架空名義入ることから, オークション方式 (オークションメカニズ

札 (操作) の可能性が指摘されている [11, 13]．架空名義

ム) の設計にあたっては, 様々な不正行為に対する頑健入札とは，ある入札者が複数の名義を使ってオークショ

性, オークションの結果に関するなんらかの理論的な裏ンに参加し，自分の利益を大きくしようとする不正行為

付け等が重要となるものと考えられる. 複数の戦略的行である．架空名義入札は個人で行うことが可能なため，動をするエージェントが集団で意思決定を行う場合に，実行が容易である．更に，インターネット環境において社会的に望ましい結果が得られるように社会的ルールを

参加者を識別することはほとんど不可能なため，防ぐ

設計することは，メカニズムデザインと呼ばれ，ミクロことは困難である．したがって，インターネットオーク

経済学，ゲーム理論の一分野として活発に研究が行われションにおいて架空名義入札は深刻な問題となり得る．

ている．

これまで架空名義入札に関する研究は多数行われていインターネットオークションに関連する研究の 1 つる．まず，架空名義入札が可能である場合，VCG メカに組合せオークション [2] がある．通常のオークション

ニズムが架空名義入札に脆弱であることが指摘されては，一度に 1 つの商品 (財) を販売するが，組合せオークいる [6, 12]．更に，個人合理性，パレート効率性，架空ションでは，価値に依存性のある (代替性や補完性) 複

名義入札への頑健性を同時に満たす組合せオークショ

数種類の異なる財が販売され，入札者は財の組合せ (バンメカニズムは存在しないという不可能性定理が示さ

ンドル) に対して入札を行う．入札者の複雑な選好を考れている [6, 11, 12]．架空名義入札に頑健なメカニズ

慮することで，入札者の効用および主催者の利益を増加

ムはいくつか提案されている．例えば，最小バンドル

させることが可能になる．理論的に優れた性質を持つ(minimal bundle, MB) [9] メカニズム，レベル付き分割
セット (leveled division set, LDS) [13] メカニズム等が組合せオークションメカニズムとして，Vickrey-ClarkeGroves (VCG) メカニズム [7] が知られている．VCG メ

提案されているが，メカニズムの分かりやすさ，割当結

カニズムは，公共財を対象とした Clarke-Groves (CG)果の効率性，理論的性質，計算量等のいくつかの評価基

メカニズムの一種である．CG メカニズムは，社会的選準において，決定版と呼べるような優れたメカニズムは択理論の研究において，公共財に対して便益を共有する

未だ存在しない．本論文では，VCG メカニズムをベー

人々に真の評価値を申告させるメカニズムとして提案さスとした，新しい架空名義入札に頑健な組合せオークれたものである．VCG メカニズムは，真の評価値を申ションメカニズムを提案する．

∗ 九州大学大学院システム情報科学府† 日本学術振興会特別研究員 DC1

51（第2分冊）

FIT2010（第 9 回情報科学技術フォーラム）1.2 関連研究を必要とする入札者を意味する．すなわち，もし，ある組合せオークションの研究は多岐に渡って行われており，その一つとして勝者決定問題が挙げられる．
組合せオークションでは，オークションの勝者は複数存在することになり，勝者を決めることが複雑な制約最適化問題となる．売手は入札額の和が最大化されるように商品の割当方法を決定する必要があり，これを勝者決定問題と呼ぶ．勝者決定問題の難しさは，入札者数を nとすると，勝者の可能な組合せの数が 2n と指数的に増加する点にある．これは Weighted Set Packing 問題の一入札者 i が single-minded ならば，あるバンドル Bi が存在し，Bi′ ⊇ Bi となる任意の Bi′ に対して v(Bi′ , θi ) =v(Bi , θi ) > 0 が成立する，かつ全ての Bi′ + Bi において v(Bi′ , θi ) = 0 が成立する．
次に single-minded bidder の一般化として，k 個のバ
ンドルのいずれかを必要とする k-minded bidder を定義する．ここで，k = 2m − 1 とすれば，任意の入札者を

k-minded bidder として表現できる．

種であり，NP 困難と呼ばれる問題のクラスに属する．

定義 2 (k-minded bidder). k-minded bidder とは，k 個

つまり，解を求めるための効率的な (多項式時間で解けのバンドル（もしくはそのスーパセット）のみを必要

る) アルゴリズムが存在せず，最悪の場合は指数的な時とする入札者を意味する．すなわち，もし，入札者 i間が必要となるということである．この問題に関してが k-minded ならば，ある k 個のバンドル B1 , . . . , Bk

は，人工知能分野での探索の技術を導入した種々の最適が存在し，任意のバンドル B に関して，v(B, θi ) =化手法が提案されている [1]．

maxBj ⊆B v(Bj , θi ) が成立する．

また，キーワード連動広告オークションが近年では，
広く用いられるようになっている．具体的には，広告主
は検索エンジン (Google や Yahoo!) のキーワードに対して入札額を設定する．キーワードがユーザによって検索されると，基本的には入札額の高い順に，検索結果とは別に，例えば画面の右端に広告が提示される．これらの広告料の決定において，Generalized Second Price

組合せオークションメカニズム M(X, p) は，一般に割当規則と支払規則という 2 つの関数によって構成される．A を可能な財の割当の集合とすると，割当規則

X : Θn → A は，各入札者の申告したタイプの組を入力とし，各入札者への財の割当を出力する．支払規則

p : Θn → Rn は，各入札者の申告したタイプの組を入力とし，各入札者が支払う金額を決定する．さらに i が申Auction (GSP) と呼ばれる，ビックレー入札に準じたメカニズムが用いられている [3, 8]．

告したタイプの組を θi とし， i 以外の入札者が申告し2 準備たときの i への割当及び支払額をそれぞれ Xi (θi , θ−i )，本章では，本論文で扱う組合せオークションメカニズ
ムについて説明する．まず，問題の定式化を行い，オー
クションメカニズムが社会的に望ましくなるための満たすべき性質について説明する．次にメカニズムの記述方
法について述べ，代表的なメカニズムである VCG メカ
ニズムを紹介する．

たタイプの組を θ−i とする． このとき i が θi を申告しpi (Xi (θi , θ−i ), θ−i ) と表すこととする．また，可能な財の割当を a = (a1 , a2 , . . . , an ) ∈ A とするとき，入札者

i に割り当てられるバンドルを ai とする．入札者 i がバ
ンドル B を獲得し，支払額 pi (B, θ−i ) を支払った場合の効用を v(B, θi ) − pi (B, θ−i ) と定義する．入札者 i が何も獲得できないときの支払額 pi (∅, θ−i ) は 0 とする．
メカニズム設計者は社会的に望ましい性質を満たすよ

2.1 問題の定式化存在しうる入札者の集合を N = {1, 2, . . . , n}，財の集合を M = {g1 , g2 , . . . , gm } として，各入札者 i はうにメカニズムを設計する．本論文では以下の 4 つの性質を定義する．

財の組合せ (バンドル) B ⊆ M に対する評価値を持

定義 3 (パレート効率性). ∀i ∈ N, ∀θi , ∀a ∈ A におつ．入札者 i のバンドル B ⊆ M に対する評価値は，いて，タイプと呼ばれる θi ∈ Θ を用いて v(B, θi ) で表現す′る．バンドルに関する評価値は常に，B ⊇ B に対してv(B ′ , θi ) ≥ v(B, θi ) が成立する．また，申告するタイプの組を θ = (θ1 , . . . , θn ) ∈ Θn とする．ここで入札者のタイプに関する仮定として single-minded bidder および k-minded bidder を定義する．

X(θ) ∈ arg maxa∈A∑v(ai , θi )i∈Nを満たすとき，割当はパレート効率的である．ただし，

X(θ) = (X1 (θ), . . . , Xn (θ)) と表す．
ここで，割当がパレート効率的であるとは全ての参加

定義 1 (single-minded bidder). Single-minded bidder とは，唯一のバンドル（もしくはそのスーパセット）のみ

者の効用の和，すなわち社会的余剰が最大化されることを意味する．したがって，パレート効率的な割当が実現している場合，いずれかの入札者の効用を犠牲にしない

52（第2分冊）

FIT2010（第 9 回情報科学技術フォーラム）限り，他の入札者の効用を増加させるような割当を作ることはできない．

v(Xi ((θi , ∅, . . . , ∅), θ−ϕ(i) ), θi )−pi (Xi ((θi , ∅, . . . , ∅), θ−ϕ(i) )), θ−i )∪Xl (θϕ(i) , θ−ϕ(i) ), θi )≥ v(

定義 4 (個人合理性). ∀i ∈ N, ∀θi において，v(Xi (θ), θi ) − pi (Xi (θ), θ−i ) ≥ 0∑−l∈ϕ(i)pi (Xl (θϕ(i) , θ−ϕ(i) ), θ−l )l∈ϕ(i)

を満たすとき，組合せオークションメカニズム M(X, p)を満たすことをいう．すなわち，入札者は名義を複数用

は個人合理性を満たす．

いて入札するよりも，単一の名義を用いて入札すること

個人合理性とは，他の入札者の申告に関わらず，各入札者は自分のタイプを正直に申告することによって損をすることはないという性質である．
定義 5 (戦略的操作不可能性). θi を入札者 i の真のタイプとし，θi′ を入札者 i の偽のタイプとする．∀i ∈N, ∀θ−i , ∀θi , θi′ において，が最良の策となる．

2.2 価格ベース・調整不要メカニズム
価格ベース・調整不要 (Price-Oriented, Rationing-Free,
PORF) メカニズム [9] は戦略的操作不可能なメカニズ
ムの一般的な記述方法である．従来のメカニズム記述
法では，まず勝者の決定方法を記述し，次に支払額の計算方法を記述する．これに対して，PORF メカニズムでは，入札者の各バンドルに対する価格の計算方法のみを

v(Xi (θ), θi ) − pi (Xi (θ), θ−i )≥ v(Xi (θi′ , θ−i ), θi ) − pi (Xi (θi′ , θ−i ), θ−i )記述する．PORF メカニズムは従来のメカニズムの記述法と大きく異なっているが，任意の戦略的／架空名義操作不可能メカニズムは，PORF メカニズムとして記述可を満たすとき，組合せオークションメカニズム M(X, p)
が戦略的操作不可能性を満たす．

能である．

PORF メカニズムは以下のように定義される．

任意の入札者において，自分の真のタイプを申告した
とき自分の効用が最大となる．すなわち，任意の入札者にとって各財に対して真の評価値を入札することが• 入札者 i ∈ N は自分のタイプ θ̂i を申告する (真のタイプ θi を申告するとは限らない) ．
• 入札者 i に対して，任意のバンドル B ⊆ M の価格（弱）支配戦略であるとき，そのメカニズムは戦略的操

pi (B, θ−i ) を定義する．この価格は i が申告したタ

作不可能であるという．

イプと独立に決定しなければならないが，他の入札

最後に，組合せオークションメカニズム M(X, p) が者が申告したタイプに依存してもよい．

数の名義を使って複数の入札を行い，効用を増加させ• B ⊆ B ′ なら pi (B, θ−i ) ≤ pi (B ′ , θ−i ) とし，更に
pi (∅, θ−i ) = 0 を仮定する．
ˆi − pi (B, θ−i ) を• 入札者 i に対して，効用 v(B, θ)

ようとする行為である．まず，架空名義操作に関する記最大化するバンドル B を割り当て，その支払額を法を導入する．ある入札者 i が s 個の名義 id1 , . . . , ids
を用いるとする．次に，入札者 i が用いる (架空) 名

pi (B, θ−i ) とする．効用を最大化するバンドルが複数存在する場合は，いずれか 1 つを割り当てる．

義の集合を表すために，関数 ϕ(i) = {id1 , . . . , ids } を• 割当結果は割当可能性を満たす．すなわち，入札導入する．このとき，申告されたタイプの組を θ =者 i, j に割り当てられるバンドル Bi , Bj に関して，(θid1 , . . . , θids , θs+1 , . . . , θn ) とする．ここで，θ−ϕ(i) を定義する．θ−ϕ(i) とは，入札者 i が用いる s 個の名義
id1 , . . . , ids を除くタイプの集合である．また，入札者

Bi ∩ Bj = ∅ が成立する．

架空名義操作不可能性を満たすことを定義する．オークションにおける架空名義操作とは，一人の入札者が複i がただ 1 つの名義を用いて入札する場合の申告の組を(θi , ∅, . . . , ∅, θs+1 , . . . , θn ) と表す．
定義 6 (架空名義操作不可能性). 組合せオークション
メカニズム M(X, p) が架空名義操作不可能性を満たすとは，∀i ∈ N, ∀ϕ(i), ∀θi , ∀θϕ(i) において，以上の定義より，価格は自分の申告したタイプとは独立に決定される．また，入札者は他者の割当結果とは独立に，自分の効用を最大化するバンドルを獲得することができる．したがって，以下の定理が成立することを証明している．
定理 1. あるメカニズムが戦略的操作不可能ならば，PORF メカニズムとして記述可能である．

53（第2分冊）

FIT2010（第 9 回情報科学技術フォーラム）PORF メカニズ ムの架 空名義操作不可能性に関 して，本論文では，弱匿名価格ルール (weakly-anonymous

表1

pricing rule, WAP) [9] を満たすメカニズムに議論を限定する．

架空名義入札の存在しない場合

{g1 }

{g2 }

{g1 , g2 }

入札者 1

9

1

10

入札者 2

6

0

8

定義 7 (弱匿名価格ルール). 入札者 i に着目し，i 以外の入札者の集合を N ′ とする．N ′ に含まれる入札者によって申告されたタイプの組を θN ′ とする．このとき，i に対して提示されるバンドル B の価格は i の申告したタイプ θi に依存しない．すなわち，p(B, θN ′ ) で表わされる．

を以下で決定する．

pi (B, θ−i ) = V ∗ (M, θN \{i} )−V ∗ (M \B, θN \{i} ) (1)

この仮定により，他の入札者のタイプの集合が同じであれば，全ての入札者に関して，同じバンドルへの支払額は同じとなる．WAP はきわめて自然な仮定であり，ほとんど全てのメカニズムはこの性質を満足する．
次に弱匿名価格ルールを用いた PORF メカニズムに関して，非優加法的価格増加条件 (no super-additive priceincrease condition, NSA) [9] を定義する．
定義 8 (非優加法的価格増加条件). 任意の入札者の集合

S ⊆ N, N ′ = N \ S ，および i ∈ S に関して，Bi が ip(Bi ,i∈S∪{θj } ∪ θN ′ ) ≥ p(j∈S\{i}∪

このメカニズムはパレート効率的な割当において，i がB を獲得するとき，pi (B, θ−i ) は VCG メカニズムにおける支払額と等しくなり，B は i の効用を最大化する．
しかし，VCG メカニズムは戦略的操作不可能性，パレート効率性，個人合理性を満たす一方で，架空名義操作不可能性を満たさないことが示されている．
定理 2. VCG メカニズムは架空名義操作不可能性を満たさない [6, 12]．
定理 2 が成立することは，次の例を考えることによっの効用を最大化するバンドルであるとき，∑B, Bi ∩ Bi′ = ∅} を可能な財の割当として，V ∗ (B, θS )∑を maxg i∈S v(Bi , θi ) で定義する．そして，V ∗ を用いて入札者 i ∈ N に対するバンドル B ∈ M の支払額て確認できる．

Bi , θ N ′ )
例 1. VCG メカニズムを用いて 2 人の入札者に 2 つのi∈S

財を販売する組合せオークションを考える．まず，入札が成立する．

者 1 及び 2 のタイプが表 1 で与えられている場合を考

この条件は，バンドルの和集合を単一の名義を用いてえる．このとき，パレート効率的な割当により入札者 1

獲得した場合の支払額 (右辺) が，個別の名義を用いて獲がバンドル {g1 , g2 } を獲得し，入札者 2 は何も獲得でき得した場合の支払額の和 (左辺) よりも小さいことを意ない．このときの入札者 1 の支払い額 p1 ({g1 , g2 }, θ−1 )味している．WAP および NSA を同時に満たす PORF

を以下のように決定する：

メカニズムは架空名義操作不可能となることが証明されている [9]．

p1 ({g1 , g2 }, θ−1 ) = 8 − 0 = 8.
次に，入札者 1 が 1’ という架空名義を用いて，２つ

2.3 VCG メカニズム
本 節 で は ，Vickrey-Clarke-Groves (VCG) メ カ ニ ズの名義から入札する場合を考える．表 2 がそれぞれのム [7] の PORF 記述を示す．VCG は代表的な組合せ

名義によって申告されたタイプを表しているとする．

オークションメカニズムの 1 つであり，架空名義入札がこのとき，パレート効率的な割当により，名義 1 及び許されない状況ならば，戦略的操作不可能性，パレート

1’ がそれぞれ財 g1 , g2 を獲得する．ここで，式 (1) に効率性，個人合理性の 3 つを満足するメカニズムであ

よって支払額を計算すると，名義 1 及び 1’ の支払額

る．これまで示してきたように PORF は戦略的操作不p′1 ({g1 }, θ−1 ), p′1′ ({g2 }, θ−1′ ) は可能なメカニズムであるため，以降では入札者 i は常に真のタイプ θi を申告すると仮定する．
まず，メカニズムの記述を簡単にするため，V ∗ を導入する．任意の入札者の集合 S と財の集合 B および Sに属する入札者のタイプ集合 θS に関して，財の集合 B
を S 中の入札者に最適に割り当てた場合の効用の総和を V ∗ (B, θS ) とする．より正確には，θi を入札者 i のタイプ i ̸= i′ について g = {(B1 , B2 , . . .)|∪i∈S Bi ⊆p′1 ({g1 }, θ−1 ) = (6 + 5) − 5 = 6
p′1′ ({g2 }, θ−1′ ) = 10 − 9 = 1と な る ．よ っ て ，入 札 者 1 は 支 払 額 7 で バ ン ド ル{g1 , g2 } を獲得でき，架空名義操作を行わない場合に比べて効用が増加している．
架空名義操作が不可能な環境では VCG メカニズムがパレート効率性を満たすただ 1 つの戦略的操作不可能な54（第2分冊）

FIT2010（第 9 回情報科学技術フォーラム）表 2 入札者 1 が架空名義 1’ を用いて 2 名義で入札した場合

{g1 }

{g2 }

{g1 , g2 }

入札者 1

9

1

10

入札者 2

6
1

0
5

8
5

入札者 1’

表3

入札者 i

表4

入札者 i が持つタイプ

{g1 }

{g2 }

{g1 , g2 }

6

0

8

入札者 i を分割したときの各入札者の持つタイプ

{g1 }

{g2 }

{g1 , g2 }組合せオークションメカニズムであることが知られてい入札者 ia6

0

6

る [4]．それゆえ，定理 2 より架空名義操作不可能性と入札者 ib008

パレート効率性を同時に満たす組合せオークションメカ
ニズムは存在しないことが示される．このため，架空名
義操作不可能性を満たし，かつ可能な限り社会的余剰を名義選択メカニズムは [N \ {i}]s に含まれる任意の名大きくする割当を実現可能な組合せオークションメカニ

義の集合を選び，支払額を決定することで，架空名義不ズムの設計が重要な課題となっており，従来研究では，可能性を実現している．実際，ここで新規に名義を加え複数の架空名義操作不可能な組合せオークションメカニ

て，入札を増やしたとしても，その増やした入札が支払ズムが設計されている（例えば，[5, 9, 10, 13] など）．

額を減らすようであれば，その入札の影響を除外する．
一方で，VCG メカニズムでは新規に入札が加わることで3 名義選択メカニズム

支払額が減少するので，VCG メカニズムにおける価格を本章では，架空名義操作不可能な新たなメカニズムを提案する．まず，提案メカニズムを述べ，実際の動作例を挙げる．次に，提案メカニズムが架空名義操作不可能

pVi CG (B, θ−i ) としたとき，pi (B, θ−i ) ≥ pVi CG (B, θ−i )が常に成立する．
続いて，例 1 に名義選択メカニズムを適用し，このメカニズムが架空名義操作不可能であることを述べる．

性を満たすことを理論的に証明する．

3.1 提案メカニズム

例 2. 2 人の入札者に 2 つの財を販売する組合せオーク

本節では，新しい架空名義操作不可能な組合せオークションメカニズムとして，架空名義の可能性のある名義を除外して支払額を決定する名義選択メカニズムを提案する．このメカニズムは PORF メカニズムで記述されるが，顕示原理により割当可能性を満たす PORF で記述したメカニズムに限定しても一般性は失うことはない．
以下に提案メカニズムの概要を述べる．まず，入札者の集合を N ，財の集合を M とする．入札者 i の価格を計算する際に，N \ {i} に含まれる入札者 j が k-minded
である場合，j を k 人の single-minded な入札者に置き換える．この操作を入札者の分割と呼ぶ．入札者の分割によって得られた新しい入札者集合を [N \ {i}]s と記述する．入札者 i がバンドル B を獲得するときの支払額を以下に示す．

ションを考える．入札者 1 および 2 のタイプが表 1 で与えられている．このとき，VCG メカニズムを適用させると，例 1 で示したパレート効率的な割当により入札
者 1 がバンドル {g1 , g2 } を支払額 8 で獲得し，入札者 2は何も獲得できない．ここで，入札者 1 が 1’ という架空名義を用いて，合計 2 名義で入札した場合を考える．
表 2 がそれぞれの名義によって申告されたタイプを表している．このとき，VCG メカニズムを適用させると，
例 1 より入札者 1 がバンドル {g1 } を支払額 6 で，入札者 1’ がバンドル {g2 } を支払額 1 で獲得する．よって入札者 1 は架空名義入札を行うとき，財 g1 , g2 を合計支
払額 7 で獲得することができ，架空名義入札を行う前に比べて効用が増加している．
では次に名義選択メカニズムを適用する場合を考える．先ほどの 2 人 2 財の組合せオークションにおいて，pi (B, θ−i ) =max

N ′′ ⊆[N \{i}]s[V ∗ (M, θN ′′ )−V ∗ (M \B, θN ′′ )].

それぞれのタイプは表 1 で与えられている．まず入札者 1 の支払額を計算するために 入札者 2 を 2a，2b と分入札者を k 人の single-minded bidders に分割すると割する．分割したタイプが表 5 で与えられている．

存在するとき，表 4 で与えられるタイプを持つ入札者

入札者 1 のバンドル {g1 } に対する支払額を求めると，{g1 } にコンフリクトしているバンドルに入札を行ってia, ib に分割することをいう．支払額は，B とコンフリいるのは入札者 2a，2b である．この中で評価値の和のクトしている，互いに素なバンドルの集合の評価値の和最大値が支払額となり，入札者 1 のバンドル {g1 } に対の最大値をとる．B とコンフリクトしているとは，あるする支払額は 8 となる．入札者 1 のバンドル {g2 } に対バンドル B ′ が B ′ ∩ B ̸= ∅ であることをいう．

する支払額を求めると，{g2 } にコンフリクトしているは，例えば，表 3 で与えられるタイプを持つ入札者 i が55（第2分冊）

FIT2010（第 9 回情報科学技術フォーラム）表5

証明. 名義選択メカニズムは割当可能性を満たさないと

入札者 2 を 2a，2b に分割した場合仮定する．すなわち，ある入札者 i, j がバンドル Bi , Bj

{g1 }

{g2 }

{g1 , g2 }

入札者 1

9

1

10

を獲得するとき，Bi ∩ Bj ̸= ∅ が成立するこのとき，入札者 2a

6
0

0
0

6
8

v(Bi , θi ) > pi (Bi , θ−i ), v(Bj , θj ) > pj (Bj , θ−j ) が成立
する． 入札者 i がバンドル Bi を獲得するための支払額

入札者 2bは，支払額の定義より，Bi とコンフリクトしている，互いに素なバンドルの集合の評価値の和の最大値をとる．

表 6 名義選択メカニズムを適用させた支払額

入札者 1
入札者 2

{g1 }

{g2 }

{g1 , g2 }

8
10

8
10

8
10

先述した通り，本論文で扱う入札者は k-minded bidders
であり，その入札者を各バンドルについて single-mindedbidders である入札者に分割することが可能である．入
札者 j を分割するとバンドル Bj のみを欲しがる入札者

j c が入札者の集合 [N \ {i}]s の中に存在する．
表7

架空名義を用いた場合に名義選択メカニズムを

pi (Bi , θ−i ) =適用させた支払額

{g1 }

{g2 }

{g1 , g2 }

入札者 2

8
10

8
10

11
11

入札者 1’

10

10

10

入札者 1

max

N ′′ ⊆[N \{i}]s[V ∗ (M, θN ′′ ) − V ∗ (M \ Bi , θN ′′ )]≥ v(M, θj c ) − v(M \ Bj , θj c ).

入札者 j c は Bj のみを欲しがるので，v(M \ Bj , θj c ) =0，v(M, θj c ) = v(Bj , θj ) が成立する． したがって，以下の式が成立する．
バンドルに入札を行っているのは入札者 2b である．したがって入札者 1 のバンドル {g2 } に対する支払額は 8v(Bi , θi )となる．
入札者 1 のバンドル {g1 , g2 } に対する支払額を求めると，{g1 , g2 } にコンフリクトしているバンドルに入札> pi (Bi , θ−i )≥ v(M, θj c ) − v(M \ Bj , θj c )= v(Bj , θj ).

を行っているのは入札者 2a，2b である．この中で評価

同様の議論を Bj を獲得する j について適用すると，
v(Bj , θj ) > v(Bi , θi ) が成立するため，仮定は矛盾する．

値の和の最大値が支払額となり，入札者 1 のバンドル

したがってコンフリクトしているバンドルを同時に獲得{g1 , g2 } に対する支払額は 8 となる．

する入札者は存在しないので，名義選択メカニズムは，同様の議論を入札者 2 に適用させたとき，それぞれの支払額は表 6 で与えられる．したがって入札者 1 がバ
ンドル {g1 , g2 } を支払額 8 で獲得する．
では，入札者 1 が架空名義 1’ を用いて合計 2 名義で入札した場合を考える．それぞれのタイプは表 2 で与えられている．これを名義選択メカニズムに適用させると，それぞれの支払額は表 7 で与えられる．表 7 から，入札者を各バンドルについて single-minded bidders である入札者に分割することで，割当可能性を満たす．

3.3 架空名義操作不可能性
本節では名義選択メカニズムは架空名義操作不可能性を満たすことを示す．その議論に入る前に以下の補題が成立することを示す．

入札者 1 がバンドル {g1 } を支払額 8 で獲得することに補題 1. 名義選択メカニズムでは，入札者数の増加に対なり，架空名義入札を行う前に比べて，獲得できたはず

して，任意の入札者の支払額は非減少である．

の財が獲得できなくなっている．すなわち，架空名義入札を行う必要性がなくなり，名義選択メカニズムは架空名義入札に頑健であることがわかる．

証明. 本証明は背理法を用いる．入札者の集合を N とし，各入札者を分割した入札者の集合を N s とおく．
更に N から i を除く入札者の集合を N ′ とおく．入3.2 割当可能性

札者 i がバンドル B を獲得するとき，その支払額を本節では，名義選択メカニズムが割当可能性を満たすことを示す．その議論の前に割当可能性を定義する．
定義 9 (割当可能性). 任意の入札者 i, j ̸= i がバンドル

Bi∗ , Bj∗ を獲得するとき，Bi∗ ∩ Bj∗ = ∅ が成立する．
定理 3. 名義選択メカニズムは割当可能性を満たす．

pi (B, θN ′s ) とする．また，入札者 j ∈/ N を含めた入札者の集合 N ∪ {j} において，入札者 i がバンドル B を獲得するとき，その支払額を p′i (B, θ[N ′ ∪{j}]s ) とする．
このとき，p′i (B, θ[N ′ ∪{j}]s ) < pi (B, θN ′s ) が成立すると仮定する．N ′s において，B とコンフリクトしている，互いに素なバンドルの集合における勝者の集合を

56（第2分冊）

FIT2010（第 9 回情報科学技術フォーラム）s
NWとする．支払額 pi (B, θN ′s ) は以下の通りである．

pi (B, θN ′s )∗s ) − V (M \ B, θN s )= V ∗ (M, θNWW∗s ).
= V (M, θNW

Case 1. 名義を分割して効用を増加させる場合
Case 2. 勝者とならない名義を追加して効用を増加させる場合

また，入札者の集合 [N ′ ∪ {j}]s において，B とコンフリ

まず Case 1 より，名義を分割して効用を増加させクトしている，互いに素なバンドルの集合における i をる場合を考える．入札者 i が名義を分割してバンド′s
除く勝者の集合を NWとする．支払額 p′i (B, θ[N ′ ∪{j}]s )ル Bi を 獲 得 す る と 仮 定 す る ．そ れ ぞ れ の 支 払 額 はは以下の通りである．

pi′ (Bi′ , θ[N ′ ∪{i′′ }]s ), pi′′ (Bi′′ , θ[N ′ ∪{i′ }]s ) とする．すな

わち，i′ がバンドル Bi′ を，i′′ がバンドル Bi′′ を獲得す∗′s ) − V (M \ B, θN ′s )p′i (B, θ[N ′ ∪{j}]s ) = V ∗ (M, θNW
Wる．このとき，Bi′ ∩ Bi′′ = ∅, Bi′ ∪ Bi′′ = Bi である．
′s ).
= V ∗ (M, θNWs
入札者の集合 NWの条件下で，Bi′ とコンフリク
V ∗ は財の集合における評価値の和の最大値をとる．
トしている，互いに素なバンドルの集合において評価ある入札者 j を分割したときの single-minded bidders
値の和が最大となる集合を W ′ ⊆ W とし，Bi′′ とコ′である入札者を j c とする．もし，j c ∈
/ NW
ならば，
ンフリクトしている，互いに素なバンドルの集合にお
′s
s
NW
= NW
が成立する．すなわち j c の評価値を考慮
いて評価値の和が最大となる集合を W ′′ ⊆ W とす∗′s ) = V (M, θN s )しないことになるので，V ∗ (M, θNW
Wる．このとき，W ′ ∪ W ′′ = W が成立する．i′ , i′′ の支′sが成立する．また，j c ∈ NW
ならば，B とコンフリ
払額 pi′ (Bi′ , θ[N ′ ∪{i′′ }]s ), pi′′ (Bi′′ , θ[N ′ ∪{i′ }]s ) を以下でクトしている，互いに素なバンドルの集合の評価値の和が j c の評価値を考慮したときに最大値となるので，∗′s ) ≥ V (B, θN s ) が成立する．
V ∗ (B, θNW
W

表す．
s )
pi′ (Bi′ , θNW

以上より，p′i (B, θ[N ′ ∪{j}]s ) ≥ pi (B, θN ′s ) が成立し，仮定に矛盾する．したがって名義選択メカニズムは，入札者の増加に関して価格は非減少である．

==
s )pi′′ (Bi′′ , θNW==∗′s ) − V (M \ W , θN s )V ∗ (M, θNWW∗′s
V (W , θNW ),∗′′s ) − V (M \ W , θN s )V ∗ (M, θNW
Ws ).
V ∗ (W ′′ , θNWss ) +入札者の集合 NWの条件下では，V ∗ (W ′ , θNW

補題 1 より，以下の定理が成立する．

∗s ) ≥ V (W, θN s ) が成立する． 名義選択
V (W ′′ , θNW
W∗

定理 4. 名義選択メカニズムは架空名義操作不可能性をメカニズムが非優加法的価格増加条件を満たすことを以

満たす．

下で示す．

証明. 名義選択メカニズムが架空名義操作不可能性を満たすには，弱匿名価格ルールと非優加法的価格増加条件
を満たすことを示せばよい．まず，支払額の定義より名義選択メカニズムが弱匿名価格ルールを満たすことは明らかである．次に，名義選択メカニズムが非優加法的価
格増加条件を満たすことを示す．
入札者 i が 2 つの名義 i′ , i′′ を用いて入札する状況を考える．ここで，N ′ = N \ {i, i′ , i′′ } とする．また，各入札者を分割した入札者の集合を N s とする．入札者 iがバンドル Bi を獲得するときの支払額を pi (Bi , θN ′s )とする．Bi とコンフリクトしている，互いに素なバンドルの集合において評価値の和が最大となる集合を Wとし，W において入札者の集合 N から入札者 i, i′ , i′′を除いた残りの入札者を分割した中で，勝者となる入札s
者の集合を NW
とおく．このときの pi (Bi , θN ′s ) は以

下の通りである．

s ) + pi′′ (Bi′′ , θN s ) − pi (Bi , θN ′s )pi′ (Bi′ , θNWW∗′′∗s ) + V (W , θN s ) − V (W, θN s )≥ V ∗ (W ′ , θNW
W
W
≥ 0.

s
更に NW ⊆ N であることから，NW⊆ [N ′ ∪ {i′ }]ss
お よ び NW
⊆ [N ′ ∪ {i′′ }]s が 成 立 し て い る ．こ こs )で 補 題 1 よ り pi′ (Bi′ , θ[N ′ ∪{i′′ }]s ) ≥ pi′ (Bi′ , θNWs ) が成 立 すかつ pi′′ (Bi′′ , θ[N ′ ∪{i′ }]s ) ≥ pi′′ (Bi′′ , θNWる．よって pi′ (Bi′ , θ[N ′ ∪{i′′ }]s )+pi′′ (Bi′′ , θ[N ′ ∪{i′ }]s )−pi (Bi , θN ′s ) ≥ 0 が成立する．
以上より，ある入札者が名義を分割することで，効用は増加しない．したがって Case 1 では，名義選択メカ
ニズムは非優加法的価格増加条件を満たしている．
次に Case 2 より，勝者とならない名義を追加して効用を増加させる場合を考える．補題 1 より，入札者の増加によって支払額は減少しないため，Case 2 では，名義
選択メカニズムは非優加法的価格増加条件を満たす．

∗
s ) − V (M \ W, θN s )pi (Bi , θN ′s ) = V ∗ (M, θNWWs ).
= V ∗ (W, θNW

ムは弱匿名価格ルールと非優加法的価格増加条件を同時入札者 i が架空名義入札を行う状況として，以下の状に満たしている．したがって，名義選択メカニズムは架況に場合分けされる．

以上における全ての状況において，名義選択メカニズ

空名義操作不可能性を満たすといえる．

57（第2分冊）

FIT2010（第 9 回情報科学技術フォーラム）

Review, Vol. 97, No. 1, pp. 242–259, 2007.
[4] Bengt R. Holmstrom. Groves’ scheme on restricted

4 結論
本論文では，VCG メカニズムをベースとした名義選
択メカニズムを提案した．名義選択メカニズムは，任意の評価値を持つ入札者に対して適用可能であることを示し，さらに架空名義入札に頑健であることを示した．
名義選択メカニズムは VCG メカニズムをベースとしており，入札者 i における支払額は i 以外の入札者の評価値によって計算される．本論文では，各入札者は k 人のただ 1 つのバンドルを欲しがる single-minded biddersである入札者に分割可能であるとした．名義選択メカニ
ズムは，分割された入札者の集合の中で評価値の和が最大となる名義を選択して支払額の計算を行う．常に評価値の和の最大値を支払額とするので，入札者の増加に対して支払額が非減少であるという性質を名義選択メカ
ニズムは持っている．そのため，任意の入札者が財を割り当てられない架空名義を追加しても支払額は非減少である．また，名義を分割して財を獲得するとき，名義
選択メカニズムでは支払額は非減少であることが示された．したがって，名義選択メカニズムは架空名義入札に頑健であることが示された．しかし，名義選択メカニ
ズムは，入札者の増加に対して支払額は非減少であるという性質を持っているため，VCG メカニズムに比べると財を割り当てる条件が厳しく，効率が悪い点が難点である．
今後の課題として，名義選択メカニズムを基に，より効率の良い架空名義入札に頑健なメカニズムを設計することが挙げられる．既存のメカニズムと名義選択メカニズムを比較することで，より良いメカニズムが設計できると著者らは考えている．また既存の架空名義操
作不可能なメカニズムは複数提案されているが，中にはsingle-minded bidders である入札者に限定された条件付
きのメカニズムが存在する．これらの条件付きのメカニ
ズムを一般の場合に適用可能となるように拡張するためのルールが存在すると著者らは考えている．

domains. Econometrica, Vol. 47, No. 5, pp. 1137–
1144, 1979.
[5] Atsushi Iwasaki, Vincent Conitzer, Mingyu Guo,
Taiki Todo, Yoshifusa Omori, Yuko Sakurai, and
Makoto Yokoo. Worst-case efficiency ratio in falsename-proof combinatorial auction mechanisms. In
the Proceeding of the Ninth International Conference on Autonomous Agents and Multiagent Systems(AAMAS), pp. 633–640.
[6] Yuko Sakurai, Makoto Yokoo, and Shigeo Matsubara. A limitation of the generalized Vickrey auction
in electronic commerce: Robustness against falsename bids. In the Proceedings of the Sixteenth National Conference on Artificial Intelligence (AAAI) ,pp. 86–92, 1999.
[7] Hal R. Varian. Economic mechanism design forcomputerized agents. In the Proceedings of the
1st Usenix Workshop on Electronic Commerce, New
York, 1995.
[8] Hal R. Varian. Position Auctions. International
Journal of Industrial Organization, Vol. 25, No. 6,
pp. 1163–1178, 2007.
[9] Makoto Yokoo. Characterization of strategy/falsename proof combinatorial auction protocols: Priceoriented, rationing-free protocol. In the Proceedingsof the Eighteenth International Joint Conference on
Artificial Intelligence (IJCAI), pp. 733–742, 2003.
[10] Makoto Yokoo, Yuko Sakurai, and Shigeo Matsubara. Robust combinatorial auction protocol against
false-name bids. Artificial Intelligence, Vol. 130,
No. 2, pp. 167–181, 2001.
[11] Makoto Yokoo, Yuko Sakurai, and Shigeo Matsubara. The effect of false-name bids in combinatorial
auctions: New fraud in internet auctions. Games andEconomic Behavior, Vol. 46, No. 1, pp. 174–188,

参考文献[1] Peter Cramton, Yoav Shoham, and Richard Steinberg, editors. Combinatorial Auctions. MIT Press,
2005.
[2] Sven de Vries and Rakesh V. Vohra. Combinatorial
auctions: A survey. INFORMS Journal on Computing, Vol. 15, No. 3, pp. 284–309, 2003.

2004.
[12] 横尾真, 櫻井祐子, 松原繁夫. 架空名義表明のメカ
ニズムデザインに対する影響 : インターネットでの集団意思決定に向けて. コンピュータソフトウェ
ア, Vol. 17, No. 5, pp. 445–454, 2000.
[13] 横尾真, 櫻井祐子, 松原繁夫. 架空名義入札に頑健な[3] Benjamin Edelman, Michael Ostrovsky, andMichael Schwarz. Internet advertising and the

組合せオークションプロトコル. 情報処理学会論文

generalized second-price auction: Selling billionsof dollars worth of keywords. American Economic[14] 横尾真. オークション理論の基礎 –ゲーム理論と情報科学の先端領域–. 東京電機大学出版局, 2006.

誌, Vol. 43, No. 6, pp. 1814–1824, 2002.

58（第2分冊）