架空名義入札に頑健なダブルオークションプロトコル Robust Double Auction Protocol against False-name bids 横尾 真 Makoto Yokoo 櫻井 祐子 松原 繁夫 Yuko Sakurai Shigeo Matsubara ＮＴＴコミュニケーション科学基礎研究所 NTT Communication Science Laboratories 〒 619-0237 京都府相楽郡精華町光台 2-4 fyokoo; yuko; [email protected] Abstract 1 はじめに オークションは急成長している電子商取引の重要な一 電子商取引は新たな商業領域として急激に発展してき 分野であり, ソフトウェアエージェント技術の有望な適 ている. インターネットオークションは電子商取引の一 用領域であると考えられる. 形式であり, ソフトウェアエージェント技術の有望な適 インターネットを利用す 用領域であると考えられる. ることにより低コストで大規模なオークションが可能と オークションは, 買手／売手のどちらかのみが複数で なった一方で，ネットワークでの匿名性を利用した新し (one-sided) オークションと, 買手／売手の いタイプの不正行為が問題となる. 本論文では, このよう ある片方向 な不正行為の一つである架空名義入札に対して頑健性が 双方が複数存在し入札を行うダブルオークションに大別 保証される，新しいダブルオークションプロトコルを提 される. 片方向オークションに関してはこれまでに多く 案する．ダブルオークションは買手／売手の双方が複数 の研究事例があり 存在し入札を行うオークションであり, 外貨, 証券, 株等 ソフトウェアエージェントの利用等に関する研究も盛ん の取引に広く用いられている. 従来，架空名義入札が存 である [3, 16], インターネットオークション, [2, 10, 13]. 在しない場合には，支配戦略において誘因両立的である インターネットオークションは, 少ないコストで遠隔 ダブルオークションプロトコル (PMD プロトコル) が提 地から不特定多数の人々が参加可能であるという利点を 案されている. 一方, 売手が別の名義を用いて, 買手にな 持つ. その一方で, ネットワークでの匿名性を利用した新 りすまして入札を行うといった架空名義入札の可能性を しいタイプの不正行為が生じる可能性がある. そのよう 考えると, な行為の 1 つとして, ある参加者が複数の参加者になり PMD プロトコルでは, 入札者は架空名義入札 によって利益を増やすことが可能であり, 誘因両立性は 保証されない. 本論文では, 架空名義入札が可能な場合で も, 支配戦略において誘因両立的である, 閾値価格ダブル オークションプロトコル (Threshold Price Double auction protocol, TPD) を提案する. TPD プロトコルの特 徴は, 財の閾値価格を用いて可能な取引の数 および取引 価格を制御することである. シミュレーションを用いた 実験結果を用いて, 適切な閾値価格を設定することによ り, TPD プロトコルでパレート効率的な割当てに非常に 近い社会的余剰が得られることを示す. すまして, いくつもの名義で入札をすることが可能であ る. これを架空名義入札と呼ぶ. オークションにおける 不正行為の 1 つである参加者同士の結託は, これまで多 数研究されている. 結託とは, 参加者同士が事前に入札 額を調整し合うことで, 利益を増加させようとすること である [7, 10, 11]. 結託と比較して架空名義入札は個人 で実行可能であり, 結託に参加する参加者を探し, 結託に 参加するよう説得することが不要であるため, より容易 に実行可能である. さらに, ネットワーク環境では, 各参 加者の身元を正確に認証することは, 事実上不可能であ 1 る. よって, インターネットオークションでは架空名義入 本論文では, ダブルオークションに関して, 架空名義入 PMD プロトコルでは, 支配戦略における誘因両立性が 成立せず, PMD プロトコルは架空名義入札に対して頑健 ではない. 筆者らは文献 [15] で, 片方向の組合せオーク ションにおいて, 留保価格 (最低販売価格) を用いた, 架 空名義入札に対して頑健なプロトコルを示した. 本論文 では, 同様なアイデアを用いて架空名義入札に頑健なダ ブルオークションプロトコルを構築する方法を示す. こ 札の影響を解析する. ダブルオークションとは, 同じ種類 のプロトコルを閾値価格ダブルオークションプロトコル 札は深刻な問題となり得る. 筆者らはこれまで, 片方向オークションに関して, 架空 名義入札の影響を解析し [8, 9, 14, 17], 架空名義入札に対 して頑健な片方向オークションプロトコルの開発を行っ た [15]. (Threshold Price Double Auction protocol, TPD) と 引方法であり, 外貨, 証券, 株等の取引に広く用いられて 呼ぶ. 本論文の構成は以下の通りである. まず, 準備とし いる [1, 12]. ダブルオークションには様々なタイプが存 在する. 連続時間オークション (continuous-time auc- て基本的な用語の定義等を示す (２章). さらに, PMD tion) では, 取引期間中の任意の時刻に取引が可能であ プロトコルの説明 (３章) を行い, PMD プロトコルが架 り, オークションの結果は二者間の取引の集合となる. 一 空名義入札に対して頑健でない例を示す (４章). 次に, 方, 離散時間オークション (discrete-time auction, call- TPD プロトコルの説明を行い (５章). TPD プロトコル market もしくは clearing-house とも呼ばれる) では, す が支配戦略において誘因両立性を満足することを証明す べての取引はシングルステップで行われる. また, 取引さ る (６章). さらに, シミュレーションを用いた実験的評 れる財に関して, 買手／売手の需要／供給が 単一ユニッ 価により, TPD プロトコルで得られる結果の社会的余剰 トか複数ユニットか等の様々な場合が存在する. 文献 [5] の評価を示す (７章). 最後に, TPD プロトコルの性質に で指摘されているように, 片方向オークションと比較し ついて議論を行う (８章). て, ダブルオークションに関する理論的研究は少ない. こ の理由の一つとして, ダブルオークションは売手と買手 準備 の双方が複数存在するため, 理論的な解析が非常に複雑 2 となることがある. 以下, 本論文で対象とする問題と基本的な用語の説明 最も単純な場合である, 単一ユニットの財を, それぞれ を行う. 単独の買手／売手が取引する相対取引 (bilateral trade) に関して, 次章で説明する支配戦略における誘因両立性, 参加者: m 人の買手と n 人の売手が存在する. この m パレート効率性, 個人合理性を同時に満足する取引プロ と n は共通知識ではなく, 各買手／売手は, 全体 トコルは存在しないことが示されている [6] 1 . 相対取引 として何人の買手／売手がいるかは分からないとす はダブルオークションの一種であり, ダブルオークショ る. 買手 x は, 単一種類の財を, 一単位のみ必要と ン一般に関しても, これらの三つの性質を同時に満足す し, その評価値は b3x であるとする. この評価値は個 るものは存在しない. 文献 [5] では, パレート効率性を犠 人情報であり, x 以外の買手／売手はこの値は分か 牲にして, 各参加者の需要／供給が単一ユニットである らないとする. また, 売手 y は単一種類の財を一単 場合に関して, 支配戦略における誘因両立性および個人 位保有しており, その評価値は s3 であるとする. こ の財に関して, 買手と売手が共に複数存在する場合の取 合理性を満足する離散時間のダブルオークションプロト の評価値も個人情報である. コルを提案している. 以下, このプロトコルを PMD プ ロトコル (Preston McAfee's Double Auction Protocol) y 個人価値の財: 各参加者の評価値は互いに独立であるこ と呼ぶ. とを仮定する. このような財を個人価値の財と呼ぶ. 一方, 売手が別の名義を用いて, 買手になりすまして 一般には参加者たちの価値の間にはなんらかの相関 入札を行うといった架空名義入札の可能性を考えると, があると考えられるが, 分析を簡潔にするために, 個 1 この結果は, 次章で説明する支配戦略均衡よりも一般的な条件であ る, ベイジアンナッシュ均衡に関しても成立する. 人価値の財という仮定は多くの研究で用いられてい る [7, 2 4]. Youarereadingapreview.Wouldyouliketoaccessthefull-text? Accessfull-text [14] M. Yokoo, Y. Sakurai, and S. Matsubara. The effect of false-name declarations in mechanism design: Towards collective decision making on the Internet. In Proceedings of the Twentieth International Conference on Distributed Computing Systems (ICDCS-2000), pages 146{153, 2000. [15] M. Yokoo, Y. Sakurai, and S. Matsubara. Robust combinatorial auction protocol against falsename bids. In Proceedings of the Seventeenth National Conference on Articial Intelligence (AAAI-2000), pages 110{115, 2000. [16] 横尾 真. インターネットオークションの理論と応 用. 人工知能学会誌, 15(2):404{411, 2000. [17] 横尾 真, 櫻井 祐子, 松原 繁夫. 架空名義表明のメカ ニズムデザインに対する影響：インターネットでの 集団意思決定に向けて. コンピュータソフトウェア, 17(5), 2000. 10
© Copyright 2024 ExpyDoc
