このページの先頭です

メニューを飛ばして本文を読む

ここから本文です

サイト内の現在位置

研究者情報:研究・産学連携

研究室紹介OPAL-RING
高橋(里) 研究室

ネットオークションの新理論を社会に適用する

所属 大学院情報理工学研究科
情報・通信工学専攻
メンバー 高橋 里司 助教
所属学会 日本オペレーションズ・リサーチ(OR)学会、情報処理学会、米コンピュータ学会(ACM)、コンピュータと情報科学に関する国際会議(ACIS)
研究室HP http://optlab.org
印刷用PDF

掲載情報は2015年8月現在

高橋 里司
Satoshi TAKAHASHI
キーワード

オークション理論、数理最適化、オペレーションズ・リサーチ

実用的な新しいオークションの仕組みを提案し、社会問題の解決に役立てたい――。高橋里司助教はこうした目標を掲げ、情報科学や実験経済学の手法を駆使し、「数理最適化」の理論の応用に向けた研究に取り組んでいます。対象にしているのがインターネットオークションです。オークション理論の研究はあまた存在しますが、その多くは学術的な研究にとどまっており、社会にはほとんど適用されていないのだそうです。

さまざまなオークション理論

オークションとは、商品を効率的に取引するための手段の一つです。売り手がある商品を販売しようとする際に、購入条件を競わせることで、売り手が最も納得する形で買い手に売却する仕組みです。日本語で言えば「競売」で、築地市場の“マグロの競り”などは有名な例でしょう。
インターネットを利用した商取引が普及したことで、オークションも大量の商品を扱うようになり、さらに不特定多数の参加者を対象にするようになりました。商品を1点1点紹介する古典的なオークションに対して、ネットオークションは高速で商品をさばかないと大量の取引を成立させられません。加えて、そのシステムでは「買い手の割り当て」と「支払価格」の二つの要素を最適化する必要があり、仕組みは複雑です。
オークションのなかでは、日本最大の「Yahoo!オークション」や米国最大の「eBay」など、価格が徐々にせり上がっていく英国型が主流です。一方で、価格を緩やかに引き下げていき、最初に入札した人が落札者となる「ダッチ・オークション」と呼ばれるオランダ型の方式もあります。これはもともとチューリップの取引に使われた方法で、現在では、東京都大田区にある「大田花卉市場」が世界最大の市場として知られています。

オークション研究の概念図

第二価格方式とは

このように、オークションにはいくつかの種類がありますが、現在実用化されている手法はいずれも、競りにおける「最高値」を支払価格にしています(第一価格)。これに対して、最高値で入札した参加者が落札するという点は変わりませんが、支払価格は「2番目に高い入札値」にするという第二価格方式も存在します。これは、ノーベル経済学賞を受賞したW・Vickrey博士が分析した方式で、高橋助教は同方式を使ったオークションシステムの設計に挑んでいます。
第二価格は、理論的に分析しやすいという利点があり、第一価格と比べても、「期待できる売り手の利益にはほとんど差がない」ことが証明されています。この第二価格を一般化したのが「VCGメカニズム」と呼ばれる手法です。これは、落札者の支払価格は、【自分が入札しなかった場合の入札値の総和】と、【自分が落札した場合の、自分を除いた入札値の総和】との差額である、という難解なルールです。その複雑さゆえに、ほとんどが研究レベルでいまだ実用化に至っていません。
ただ、このルールの利点は、常に入札値の総和が最大になるように商品を割り当てて落札者を決定するだけではありません。全参加者がほかの参加者の行動に影響されずに、自分が考える「真の価値」で入札値を申告することが最も得をするという優れたメカニズムなのです。うそをついたり、ほかの参加者を出し抜いたりすることができないシステムになっており、商品を効率的かつ的確に配分することができます。

VCGメカニズムの実用化へ

そこで、高橋助教はVCGメカニズムの実用化に向けて、ルールを単純化するために、VCGメカニズムの近似アルゴリズム(貪欲法ベース)を提案しました。このアルゴリズムでは、これまであまり導入されてこなかった「単一種類の商品を複数人に割り当てる場合」を想定しています。例えば、1000本の鉛筆を40人に割り当てたい場合に、どのように配分すれば最も利益が大きくなるかというようなケースです。もちろん、各人で買い取り金額は異なるという設定です。「こうしたケースこそ実用的である」と高橋助教は考えているのです。
提案した近似アルゴリズムについて、計算機で実験したところ、近似解と厳密に解いた場合とで、ほぼ同様の結果になることが分かりました。さらに、300人を超える被験者でも実験した結果、近似アルゴリズムの導入によって、入札値の総和を最大にする割り当ての効率性は多少落ちるものの、オークション参加者の行動には違いが出ないこと、また売り手の利益にもほとんど差が出ないことを確かめました。

VCGメカニズムの説明図

最適化理論で広く応用

高橋助教は「実際に運用可能な、第二価格を利用した初めてのオークションシステムである」と考えており、「企業の資材調達の仕組みなどとして使えるほか、世界における電力や水の取引などに使えるかもしれない」と広い応用を見込んでいます。新しいアルゴリズムデザインに基づく、新時代のマーケットが将来、日本発祥で起こるかもしれないという期待も膨らみます。
オークションのほかにも、高橋助教は、データセンターの電力削減に向けた仮想マシンの最適な配置や、光通信の最適な通信経路を探る研究なども行っています。いずれも最適化の理論がベースになっています。「最適化の研究者は下請け業者である」と語る高橋助教。ある作業課題が与えられている場合に、意思決定をうまく行うことで、例えば、利益を最大化したり、移動時間を最小化したりするための「最適な解」を見つけ出すことができるのです。最適化理論は、“陰の立役者”と言えるかも知れません。
【取材・文=藤木信穂】

研究・産学連携
研究
産学官連携