            

架空名義入札に頑健な組合せオークションプロトコルの評価                  松谷 俊宏

    横尾 真岩崎 敦      

九州大学大学院 システム情報科学研究院

                                            
                                                !                    "   #  $  % #$%
                 &          '     '                   



はじめに

インターネットオークションは電子商取引 () の重要な一分野であり，人工知能やエージェント技術の有効な適用領域であると考えられる．インターネットオークションに関連する研究の一つに組合せオークションがある *+,．従来のオークショ
ンでは一度に一つの財が販売されるが，組合せオークションでは価値に依存性 補完性や代替性 のある複数種類の財が同時に販売され，入札者は財の組合せ バンドル に対して入札を行う．入札者の補完的・代替的な選好を考慮することで，入札者の効用および主催者の利益を増加することができる．
インターネットは組合せオークションを行う上で非常に優れた環境を提供しているが，その匿名性により架空名義入札と呼ばれる新しい不正行為の可能性が指摘されている *- . /,．架空名義入札とは，ある入札者が別の名義を使ってオークションに参加し，自分の利益を大きくしようとする不正行為であり，インターネット環境において参加者を識別するのは ほとんど不可能なため，防ぐことは困難である．
従来研究によって，架空名義入札が可能な場合には，個人合理性・パレート効率性・戦略的操作不可能性の三つを同時に満足する組合せオークションプロトコルは存在しないことが証明されている．そこで，パレート効率性は必ずしも保証されないが，個人合理性と戦略的操作不可能性を満足するプロトコルに関する研究が行われており，そのようなプロトコルは架空名義入札に頑健なオークションプロトコルと呼ばれる．
プロトコルが戦略的操作不可能であるとは，入札者にとって自己の評価値を正直に申告することが支配戦略になることである 正直が最良の策．
架空名義入札に頑健なオークションプロトコルでは，パレート効率性は必ずしも保証されないが，得られる社会的余剰がより大きい割当てを実現するプロトコルが求められている．社
会的余剰とは入札者と主催者の効用の総和である．
本論文では新しい架空名義入札に頑健な組合せオークション
プロトコルとしてバンドルサイズ優先     プロトコルを提案し，シミュレーション実験によって，
 プロトコルと従来のプロトコルを社会的余剰の点から比較する．
本論文では個人価値のオークション *0, に限定して議論を行
連絡先1 松谷俊宏，2+-232+ 福岡県福岡市東区箱崎 0+4+，45-0/-.22-， 6  "7

う．個人価値のオークションでは，それぞれの入札者は自身の評価値を曖昧性なく知っており，かつこの評価値は他者の評価値とは独立である．
8 +，財の集合を詳細には，入札者の集合を8 + として，各入札者 はバンドル に対する選好を持っている．入札者は集合 9 から選ばれるタイプ を持っており，このタイプを用いて，入札者 のバンドの評価値を  と表現する．また，入札者 がル を得て支払額  を支払った場合の効用は   であると仮定する このような効用は準線形 *0, と呼ばれる．
本論文では以下，戦略的操作不可能なプロトコルの一般的な記述法である価格ベース・調整不要 #  $ % #$% プロトコル *3, について説明する 第 - 章 次に，既存の架空名義入札に頑健なプロトコルである最小バンドル      ' プロトコル *3, について述べる 第. 章 さらに， プロトコルの定義を示し， プロトコルの架空名義入札に対する頑健性の証明を示す 第 / 章 ．最後にシミュレーション実験の結果を示し 第 3 章 考察を行い
第 0 章 結論と今後の課題を述べる 第 : 章 ．

           価格ベース・調整不要プロトコル
価格ベース・調整不要 #$% プロトコルは，戦略的操作不可能なプロトコルの一般的な記述法である．従来のプロトコル記述法では，まず勝者の決定方法を記述し，次に支払額の計算方法を記述する．これに対して #$% プロトコルでは，各入札者のバンドルに対する価格の計算方法のみがプロトコル毎に指定され，具体的な財の割当て方法はすべての #$% プロ
トコルに共通なルールに従う．#$% プロトコルは従来のプロトコルの記述法と大きく異なっているが，任意の戦略的;架空名義操作不可能プロトコルは，#$% プロトコルとして記述可能である *3,．
#$% プロトコルは以下のように定義される．
は自分のタイプ < を申告する 真のタイを申告するとは限らない．

 各入札者 プ 入札者 に対して，任意のバンドル 

の価格 が定義される．この価格は， の申告したタイプとは無関係に決定される 他者の申告したタイプには依存してもよい．

   なら，





¼ 

 および

8 4 を仮定する．

             

 <    を最大化するバンドル が割り当てられ，支払額は  となる．効用を最大化するバンドルが複数存在する場合には，それらのいずれか一つが割り当てられる．



 

 入札者 に対して，効用表 +1 評価値
      
 :4 4 /4 :4 ++4 /4++4
 4 4 4 544454
 4 04 04 04 04 0404

 割当て結果は割当て可能性を満たす．すなわち，入札者に割り当てられるバンドル  8
 に関して，  が成立する．
価格は自分の申告したタイプとは無関係に決定され，また，入札者は他者の割当て結果とは独立に，自分の効用を最大化するバンドルを得ることができることから，任意の #$% プロト
コルは戦略的操作不可能であることが導かれる．
本論文では，価格は以下の弱匿名価格ルール  "       =#*3, と呼ばれる性質を満たすことを仮定する．




 適用例

 

弱匿名価格ルール  入札者 ， 以外の参加者
定義の集合を ，これらのタイプの集合を 9 として，バンドルの価格は  9  で与えられる．

' プロトコルがどのように機能するかを例を用いて示す．

- 人 . 財の組合せオークションにおいて，各入札者には
例それぞれ + - .，各財にはそれぞれ    という番号が付いている．各入札者の評価値が表 + で与えられている場合を考える．' プロトコルは戦略的操作不可能なため，入札者は自己の評価値を正直に申告するものとし，以降の例も同様とする．入札者 + は  と  のどちらか，もしくは両方が必要で，入札者 - は  と  が同時に必要であり，入札者 . は  と  のどちらか一方だけが必要である．この場合，入札者 + の最小バンドルは  と  と  であり，入札者 - の最小バンドルは  であり，入札者 . の最小バンドルは  と  である．入札者 + の ， の支払額には，入札者 - の  に対する申告額である 54 が提示され， の支払額には，入札者 . の  に対する申告額である 04 が提示される．入札者 の  の支払額には，入札者 + の  に対する申告額である ++4 が提示される．この結果，各入札者に提示される価格は表 - の通りとなり，入札者 + が  を 54 で獲得し， は売れ残る．

この仮定により，他の入札者のタイプの集合が同じであれば，全ての入札者に関して，同じバンドルの価格は同じとなる．=#はきわめて自然な仮定であり，ほとんど全ての良く知られたプ
ロトコルはこの性質を満足する．
弱匿名価格ルールを用いた #$% プロトコルに関して，非優加法的価格増加       >*3,なる条件を定義する．
定義  非優加法的価格増加 
任意の入札者の集合 8，および  に関して， を の効用を最大化するバンドルであるとすると，
9    9  が成立     









する．

=# を満たす #$% プロトコルが > を満足すれば，そのプロトコルが架空名義操作不可能であることが証明されている *3,．

  プロトコル  プロトコル 定義

既存の架空名義入札に頑健なプロトコルとして最小バンド
ル      ' プロトコル *3, を紹介する．まず，記述を簡単にするために最小バンドルと呼ばれる概念を定義する．

      の入札者  に対す

8 &

 ¼   8        8              
ある財は，その財を含む最小バンドルの中で，最も高い申告額を提示した入札者に割り当てられる．



この最小バンドルを用いて，バンドルる価格  は以下のように決定される．





最小バンドル    バンドル が入札定義かつ8者 の最小バンドルであるとは，全てのに対して    が成立することである．

  プロトコルでは，主催者は販売される個々の財 に対して留保価格  を設定する．留保価格とは，財 またはバンドル に対する価格が留保価格より小さい場合，主催者に対するは財を販売しないという価格である．バンドル
留保価格は に含まれる全ての財の留保価格の総和，つまりとなる．また， に含まれる財の個数を の 8 
バンドルサイズとして   とする．
入札者 のバンドル に対する価格  は以下のように決定される．

 定義



表 -1 ' プロトコルの価格
      54

5454
 54 54 04++4 ++4++4
 ++4 04 ++4 ++4++4 ++4++4
 ++4 54 ++4 ++48



 

      8      &         

 ¼  8

 ¼   &  ¼



¼   

ただし， が存在しなければ ¼ を満たす
 8 4 とする．また， は十分に大きな値であり，これを             

表 .1  プロトコルの価格 +      
+44+34
 34 04 04 +44++4 ++4+34
  04  ++4++4 ++4+34    ++4
















   のとき
8      
8   のとき       となり， 以外の入札者は財  を含むバンドルを獲得すること提示された入札者はそのバンドルを購入することができないものとする．と財が重複し， 以外の入札者が留保価格以上の
 は，申告をしているバンドルの中で，最も多くの財を含むバンドルのバンドルサイズである．  はサイズが  であるバンドルに対する他者の最大の申告額である．
この結果，ある財は，その財を含み，かつ最も多くの財を含むバンドルに対して，留保価格以上かつ最大の申告額を提示した入札者に割り当てられる．







例  例 + と同じ . 人 . 財のオークションを仮定する．留保価
格は全て 34 である場合を考える．入札者 + の  の支払額には   8 +   8 + より入札者 . の  に対する申告額であ 8 -    8 +る 04 が提示され， の支払額には より留保価格の +44 34  - が提示される．また，入札者 .の  の支払額には   8 +   8 - より  が提示される．この結果，各入札者に提示される価格は表 . のようになり，入札者 + が  を +44 で獲得し，入札者 . が  を 34 で獲得する．

         9  を満たす．

 問題設定

入札者が 人，財の個数が 個の組合せオークションにおと評価値 はいて，入札者 の選好するバンドル以下のようにして決定する．



 





を指数分布 * , 8*:, に従って決定する．この設定によって，バンドルサイズがの入札者の出現確率は，バンドルサイズが ? + の入倍となる．
札者の出現確率の まず，バンドルサイズ

架空名義操作不可能性 次に，バンドルをサイズが のバンドルからランダ を *4 , の一様分布からラムで決定し，評価値 ンダムに決定する．

             

本章では，まず，留保価格を変化させた場合の  プロト
コルの社会的余剰の変化を調べ，その後，入札数を変化させた
場合の ' プロトコルと  プロトコルの社会的余剰を比較する．

まず， プロトコルが割当て可能性を満たすことを証明する．任意の財  に関して，その財を含むバンドル を獲得して効用が正になるような入札者が複数存在しないことを証明する．
  を満た入札者 の  に対する評価値が しているとする．  8  8 とすると，  8  よ  の場合は ¼ り     は明らかである．   が成立し，  8   の場合は    より     が成立する．このとき， に対して提示の価格はされる

 ¼ 

 実験次に， プロトコルを用いて財が売れ残る場合の例
例を示す．財の番号や留保価格は例 - と同じとする．入札者 +，入札者 -，入札者 . の評価値が表 / で表される場合を考える．
 8 -    8 - より入入札者 + の  の支払額には 
札者 - の  に対する申告額である +43 が提示される．また，入札者 . の  の支払額には   8 +   8 - より が提示される．この結果，各入札者に提示される価格は表 3 になり，入札者 + が  を +43 で獲得し，財  は売れ残る．

 ¼ 




 

 ¼  

 プロトコルがどのように機能するかを例を用いて示す．

 ¼ で正の効用を得ることができない．よって，任意の財を含むバンドルを獲得して効用が正になる入札者は複数存在しないので， プロトコルは割当て可能性を満たす．
次に， プロトコルが > の条件を満たすことを証明  8  に対してする．二つのバンドル ?  8 
 より  ? ¼ 
  ¼  が成立する．よ9    9  が成立し， って，  に対して  9 ¼ 
 9  が満たされるので， プ9 
ロトコルは > の条件    適用例

表 31  プロトコルの価格 -      
+44+34   04 +44++4 ++4+34
  04  ++4++4 ++4+34    ++4

 +44 個のインスタンスに対してそれぞれのプロトコルを適用し，得られた社会的余剰の平均値を比較する．また，簡単のために，各財に対する留保価格は全て同じとする．

 留保価格の変動に対する性能の変化

図 + は  8 -4  8 +4 において， をそれぞれ -4 34
+44 としたときの留保価格の変動に対する  プロトコルの社会的余剰の変化を示す．社会的余剰は，パレート効率的な割当てを行ったときの社会的余剰を + とした場合の比率で表している．
図に示されるように，社会的余剰は留保価格が 4/ まではほとんど変化せず，留保価格が 42 付近で最も高くなる．

表 /1  プロトコルで売れ残る場合の評価値例

      4 /4 :4 ++4 /4++4
4 4 +43
44+4304 04 04040404

 :4
 4 4

入札数の変動に対する性能の変化



図-は8 -4 において， を +4 としたときの入札数の変動に対する ' プロトコルと  プロトコルの社会的余             
ドル同士が重複しても，申告額が留保価格よりも小さければ他の入札者の価格に影響せず，不要な価格の増加が起こらない．
そのため，入札者の増加によって社会的余剰は減少しない．逆に，入札数の増加は留保価格以上の評価値を持つ入札者を増やすため，入札数の増加により社会的余剰は増加する．

Ratio of Social Surplus

1
BSO(n=20)
BSO(n=50)
BSO(n=100)

0.80.6

 おわりに0.4

本論文では新しい架空名義入札に頑健な組合せオークションプロトコルとして  プロトコルを提案した．シミュレー
ション実験の結果，主催者が留保価格を適切に設定した場合，
 プロトコルを用いた場合に得られる社会的余剰は入札数の増加に従って増加し，既存のプロトコルである ' プロト
コルを用いた場合に得られる社会的余剰よりも大きくなることを示した．インターネットオークションで多数の入札が期待される場合においては，適切な留保価格が設定できるならば，
 プロトコルの方が ' プロトコルよりも適していると予想することができる．
一方，適切な留保価格を設定することが困難な状況では，
 プロトコルを用いても大きな社会的余剰を得ることができない．このようなパラメータの設定が不要で，より大きな社会的余剰を獲得できる架空名義入札に頑健な組合せオークションプロトコルを考案することが今後の課題である．

0.2

000.2

0.40.6
Reservation Price0.81

図 +1 留保価格の変動に対する社会的余剰の変化

Ratio of Social Surplus

10.80.6

参考文献

0.40.2*+,  @    @  $ @ -44. )     1    !"#$%     

MBBSO(0.8)
BSO(0.4)*-, 横尾 真．-444．インターネットオークション理論と応用．人工知能学会誌 @ 1+3-，/4//++

020

4060

80

100120*., A "  ' " A   '  -44+ $                   @ 1+.4-   +0:+2+

Number of Bidder

図 -1 入札数の変動に対する社会的余剰の変化*/, A "  ' " A   '  -44/ B            1>        &   '  ( )  /0+1+:/+22

剰の変化を示す． プロトコルは留保価格が 42 の場合と4/ の場合をそれぞれ示す．
適切な留保価格を設定した  プロトコルの社会的余剰は入札数が少なければ ' プロトコルの社会的余剰よりも小さいが，入札数の増加に従って大きくなり、' プロトコルよりも大きくなる．一方，適切な留保価格を設定していない 
プロトコルの社会的余剰は ' プロトコルよりも小さい．

*3, A "  ' -44. )   ;%  #  )     #   1 #  $   #    * +  ,           - ./ :..:.5

 考察
 プロトコルでは留保価格がある程度大きくなければ社*0, ')    =   ' C   D  E $ +555'     &  F   #

会的余剰が大きくならない．これは，留保価格が小さい場合，不要な財を含むバンドルに対しても留保価格以上の申告を行う入札者が現れ，他の入札者の価格を大きくし，多数の財が売れ残ってしまうためである．留保価格が適切な場合には，不要な財を含むバンドルに対して留保価格以上の申告を行う入札者が現れず，不要な価格の増加が起きないために社会的余剰が大きくなる．
' プロトコルでは複数の最小バンドルが重複したとき，申告額の小さいバンドルに含まれる財は，その財自身が重複していなくても販売されない．そのため，入札数の増加によりバンドル同士の重複が増えると，売れ残る財が増加し社会的余剰が低下する．これに対して  プロトコルでは，選好するバン*:, %7 A G   H     A +555      &       1     &   *    0           - / 3/233.
*2, @  I $ +553 (            *    "10 2 3   '   