(57)【要約】【課題】動的環境で商品の割当てを行うオークションにおいてさらに個人合理性とパレート効率性とを兼ね備えたオークションを目的とする。【解決手段】買手装置１２から入力された情報により、商品価値を変動させる外部的要因である環境条件の要素ごとに、実行可能な商品の割当てに対する効用と商品の割当て遷移規則とからなる割当て計画を作成し、環境条件の各要素が決定されるたびに、前記割当て計画から前記遷移規則に従って効用が最大の割当てを選び出すことによって、最終的な割当てを決定する。従って、期待値の上での個人的合理性を満たす。そして、割当てられた買手装置がその商品を出品した売手装置に支払う額を買手装置の参加による他の買手装置の期待評価値の減少分に等しい額として支払うのでパレート効率性を持つ。【選択図】  図１
2007026383.tif 000002
【特許請求の範囲】
【請求項１】
売手装置が出品する商品の情報をネットワークを介して取得する売手情報取得手段と、
前記売手情報取得手段から得た情報を買手装置に公開し、前記買手装置より入札対象となる任意の商品の組と、前記商品の組にかかる商品価値を変動させる外部的要因の中から任意に選択した環境条件と、前記商品の組と前記環境条件とにかかる入札価格である評価値と、買手装置に対する商品の変更前の割当てと、変更後の割当てと、その変更に付随する損害額とをネットワークを介して取得する買手情報取得手段と、
前記買手情報取得手段により取得した情報に基づき、前記環境条件の要素ごとに実行可能な商品の割当てに対する社会的効用と、商品の割当て遷移規則とからなる割当て計画を作成する割当て計画作成手段と、
前記外部的要因の各要素が決定されるたびに、前記遷移規則に従って社会的効用が最大の割当てを選び出すことによって、最終的な割当てを決定する最終割当て決定手段と、
前記最終割当て決定手段により割当てられた買手装置がその商品を出品した売手装置に支払う額を買手装置の参加による他の買手装置の期待評価値の減少分に等しい額として算出する支払額算出手段とを備え、
前記社会的効用は、売手装置の効用と買手装置の効用との総和とする
ことを特徴とする電子式入札装置。
【請求項２】
請求項１に記載された電子式入札装置において、
前記割当て計画作成手段は、一つの商品が同時に複数の買手装置に割当てられないよう商品割当てを計算する割当て計算手段と、
前記割当て計算手段により計算された各割当てに対して社会的効用を計算する効用計算手段と、
前記環境条件の要素における値の組み合わせにより増減する遷移規則のうち前記社会的効用が最大となる遷移規則を最適遷移規則とする値最適遷移規則決定手段と、
前記値最適遷移規則決定手段を前記環境条件の全要素において行う要素最適遷移規則決定手段と
からなることを特徴とする電子式入札装置。
【請求項３】
売手装置が出品する商品の情報をネットワークを介して取得する売手情報取得ステップと、
前記売手情報取得ステップから得た情報を買手装置に公開し、前記買手装置より入札対象となる任意の商品の組と、前記商品の組にかかる商品価値を変動させる外部的要因の中から任意に選択した環境条件と、前記商品の組と前記環境条件とにかかる入札価格である評価値と、買手装置に対する商品の変更前の割当てと、変更後の割当てと、その変更に付随する損害額とをネットワークを介して取得する買手情報取得ステップと、
前記買手情報取得ステップにより取得した情報に基づき、前記環境条件の要素ごとに実行可能な商品の割当てに対する社会的効用と、商品の割当て遷移規則とからなる割当て計画を作成する割当て計画作成ステップと、
前記外部的要因の各要素が決定されるたびに、前記遷移規則に従って社会的効用が最大の割当てを選び出すことによって、最終的な割当てを決定する最終割当て決定ステップと、
前記最終割当て決定ステップにより割当てられた買手装置がその商品を出品した売手装置に支払う額を買手装置の参加による他の買手装置の期待評価値の減少分に等しい額として算出する支払額算出ステップとを備え、
前記社会的効用は、売手装置の効用と買手装置の効用との総和とする
ことを特徴とする電子式入札方法。
【請求項４】
請求項３に記載された電子式入札方法において、
前記割当て計画作成ステップは、一つの商品が同時に複数の買手装置に割当てられないよう商品割当てを計算する割当て計算ステップと、
前記割当て計算ステップにより計算された各割当てに対して社会的効用を計算する効用計算ステップと、
前記環境条件の要素における値の組み合わせにより増減する遷移規則のうち前記社会的効用が最大となる遷移規則を最適遷移規則とする値最適遷移規則決定ステップと、
前記値最適遷移規則決定ステップを前記環境条件の全要素において行う要素最適遷移規則決定ステップと
からなることを特徴とする電子式入札方法。
【請求項５】
ネットワークに接続可能なコンピュータに、
請求項３または４のいずれかに記載された電子式入札方法を実行させる
ことを特徴とするプログラム。
【請求項６】
請求項５に記載されたプログラムを記録して機械読み取り可能な記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークを介して、商品を販売する際に商品の割当てとその価格を決定をするための電子式入札装置に関する。
【背景技術】
【０００２】
従来、インターネットオークションは、商品を出品する売手装置と出品された商品に対して入札する買手装置とこれら装置を仲介し、このオークションを主催する電子式入札装置とを構成要素とし、これらはネットワークを介して接続されている。
電子式入札装置は、売手装置から出品された販売商品の情報を自身が管理するサイトに掲示し、買手装置は、そのサイトから情報を取得して入札商品を決定し、購入希望金額を入札する。電子式入札装置は、買手装置からの入札を集め、商品を落札する買手装置とその落札価格を決定する。
【０００３】
代表的な落札者と落札価格の決定方法は英国式オークションである。英国式オークションとは、安い価格から徐々に競り上げていき、価格が上昇しなくなったときの価格を落札価格とし、その価格を入札した買手装置にその商品を割当てる（勝者とする）決定法である．
英国式オークションのような単品のオークションだけではなく、複数商品を同時に扱うオークションも行われている。その代表的なものは、米国連邦通信委員会の周波数帯域オークションであり（非特許文献１）、同時多数回オークションと呼ばれる方法が用いられている。同時多数回オークションとは、複数の英国式オークションを同時並行で行う方法である。
同時多数回オークション以外で複数商品オークションを取り扱う方法としては、Ｖｉｃｋｒｅｙ−Ｃｌａｒｋｅ−Ｇｒｏｖｅｓオークション（以下、「ＶＣＧオークション」という。）がある（非特許文献２）。このＶＣＧオークションは、まだ実用にはあまり用いられていないが、理論的には優れた性質を持つとされている．ＶＣＧオークションで生じる架空名義入札問題を解決するオークション方法としては、特許文献１の「複数財の電子式入札方法及びその開札プログラムを記録した記録媒体」が挙げられる。
架空名義入札とは、電気通信システムを用いた電子入札において、単一の入札者が、複数の名義（例えば、異なる電子メールアドレスなど）を用いて、複数の入札を行うことであり、詳細は特許文献１に委ねる。
【０００４】
次に、オークション方法においては、動的環境で商品割当てを行うことが必要であることを説明する。
例えば、テニスコートの割当て問題を取り上げる。ここで、商品はテニスコートのある時間枠での使用権であり、テニスコートの管理者サイト、あるいは、オークション電子式入札装置のサイトで販売されているとする。このテニスコートの使用権を複数の利用希望する買手装置が獲得しようとしているとする。さて、屋根なしのテニスコートの価値は、当日雨が降れば、晴れていた場合に比べてその価値は下がるであろう。このように、価値は当日の天候などに依存したものとなる。よって、買手装置が入札を行う際には、当日の天候を予測して入札値を決定することが必要となる。しかし、予測がつねに正しいとは限らず、晴れと予測して使用権を獲得したにもかかわらず、当日の天候が雨になれば、コートの利用から得られる恩恵に比べて、費用の支払いが過大なものとなるであろう。これは、買手装置の満足度が低下し、オークションという方法自体がうまく機能しなくなることにつながる。
【０００５】
この問題は、商品の再割り当てを行うことで緩和されるかもしれない。しかし、再割り当ては買手装置の入札行動に影響を与える。つまり、本来のオークションでは、買手装置は、電子式入札装置に送信する入札値を低い値にしたり、高い値にしたり自由に決定することで、商品の割当て結果や支払額を所望するものとなるよう誘導する。再割り当てを行えば、買手装置が入札値の設定を変えることによって、割当て結果や支払額が操作される可能性が増える。買手装置にとって安定的な戦略が存在しなければ、コート管理者サイトやオークション電子式入札装置のサイトでは、どのような割当て結果が得られるかという予測ができなくなる。従って、買手装置の行動が戦略的なものとなれば再割当ては行えず、電子式入札装置を用いるにもかかわらず、このオークションは、商品の適切な割り当てに失敗することになる。
【０００６】
再割り当てに付随する別の問題は、割当ての変更に費用が発生する点である。テニスコートの利用希望する買手装置が、屋外コートから屋内コートに場所を変更する場合、用具等に関して費用が発生するかもしれない。このため、買手装置は、この種の費用を含めて入札値を決定しなければならないが、その決定は難しく、過大な入札をして支払額が多くなったり、過小な入札をしてオークションに負けるといったことが生じる。
再割り当てに起因する問題を回避する方法の一つは、事前に割り当てを行わず、利用の当日に割り当てを行うことである。しかし、これでは参加者を集めにくく、結局コート管理者サイトやオークション電子式入札装置のサイトの収入を下げることになる。
よって、オークション方法には動的環境で商品の割当てを行うことが必要である。
【０００７】
また、オークション方法にはさらに望まれる性質が２つある。それは、個人合理性とパレート効率性である。
個人合理性とは、買手装置が合理的な行動を取る限りは、オークションに参加しても損をしないことを意味する。パレート効率性とは、他の買手装置の効用を下げることなしには、ある買手装置の効用を増加させることができない状態を指す。
買手装置の効用とは、その買手装置にとっての商品の評価値と落札による支払額との差である。
オークションにおいては、パレート効率性が満たされることは社会的効用が最大化されることと等価である。社会的効用とは、売手装置の効用と買手装置の効用との和であり、売手装置の効用とは、落札による収入と売手装置にとっての商品の評価値の差である。
オークション方法の設計には、誘因両立性の制約を課してよい。誘因両立性の制約とは買手装置が入札者から得た商品の評価値を電子式入札装置にそのまま送信すること（真実申告）が入札者にとって最善となることを意味する。誘因両立性の制約を課しても、議論の一般性は失われないことが知られており、所望の方法を探索する費用を減少させ得る。また、計算機環境では、この制約が成り立てば、個々の買手装置は他の買手装置の評価値をスパイする必要がなくなるためシステム全体の安定化に寄与する。
【０００８】
次に、動的環境で商品の割当てを行う従来のオークション方法をモデルを用いて説明する。このモデルは以下のような条件を備えたものである。
【０００９】
取引の場には、電子式入札装置と、売手装置と、買手装置ｉ（ｉ＝１、…、ｎ）とが存在する。ここでは、モデルを簡単にするため売手装置は一台とし、複数の商品ｇ１、ｇ２、…、ｇｍを保有しているとする。
【００１０】
（条件１）
商品の落札決定と、落札された商品を実際に使用するまでには、ある時間間隔が存在し、その間に環境条件が判明する。
環境条件とは、例えば当日の天気や当日前日の天気など、その出品された商品の評価値に影響を与える外部的要因である。
（条件２）
価値モデルとして個人価値を条件する。すなわち、ある買手装置が持つ商品の評価値と他の買手装置が持つ評価値との間に依存関係はない。
商品から得られる恩恵は、実際の使用から得られる恩恵と、事前に割り当てられることから得られる恩恵がある。テニスコートの例では、前者はテニスコートでテニスをすることから得られる恩恵であり、後者は、例えば一月前にコートの割当てを受けることで大会開催を周知するなどして参加者を広く集められることから得られる二次的な恩恵と見なせる。
【００１１】
（条件３）
買手装置ｉの評価値を以下のように記述する。
ｖi（）＝ｖiP（）＋ｖiS（）
ｖiP（）は、割当てを受けた商品の使用から直接得られる恩恵である。ｖiS（）は、事前に商品割当てを受けることから得られる二次的恩恵を表わす。
ｖiS（）に関しては、視点を変えれば損害と見ることもできる。例えば、テニス大会の企画者がある時間枠のコート使用権を得たが、その後、何らかの事情で使用するコートが変更になれば、企画者はテニス大会会場の変更を参加予定者に連絡しなくてはいけない。これには費用が発生する。よって、これ以降、ｖiS（）を再割り当てによる損害と呼ぶ。企画者は、コートの使用期日が来ていなければ、コート使用権を他者に譲り渡すことができる。ただし、大会会場変更の連絡費用は、回収不可能な出費であることを注意しておく。
加えて、ｖiP（）は、商品が実際に使用されるときの環境条件に依存する。
【００１２】
（条件４）
環境条件は、確率変数の組として、｛ｃｏｎｄ｝＝｛ｃｏｎｄ1、ｃｏｎｄ2、…、ｃｏｎｄt｝で表現する。
さらに、以下を条件とする。
（条件５）
確率変数が取る候補値は、あらかじめ与えられており、電子式入札装置、売手装置と全ての買手装置にとって確率変数の確率分布ｐは共通知識である。
例えば、テニスコートの例では天候を表わす確率変数が取る値は、晴れと曇りの区別は重要でないため、晴れと雨の二つであり、天気予報が電子式入札装置、売手装置と買手装置によって共有されているとする。
買手装置ｉの評価値ｖiP（）を以下のように表現する。
（条件６）
Ｇを商品の割当てとし、ＧiをＧの中で買手装置ｉに割り当てられた商品とする。
買手装置ｉにとって、商品の組Ｇiに対する評価値は、ｖiP（）＝ｖiP（Ｇi；ｃｏｎｄ1、ｃｏｎｄ2、…、ｃｏｎｄt）と表現される。
混乱が生じない場合には、ｖiP（Ｇi；ｃｏｎｄ1、ｃｏｎｄ2、…、ｃｏｎｄt）の代わりに、ｖiP（Ｇi）という標記を用いる。
次に、買手装置ｉの再割り当てによる損害ｖiS（）を以下のように表現する。
【００１３】
（条件７）
買手装置ｉにとって、ｖiS（）はｖiS（ＧiPrev、Ｇicurrent）と表現される。ここで、ＧiPrevは買手装置ｉに対する変更前の割当てを表わし、ＧiCurrentは買手装置ｉに対する変更後の割当てを表わす。
図５は、買手装置１、２、３の評価値ｖiP（）の例を示す。
買手装置が、あるテニスコートのある時問枠の使用権を獲得しようとしているとする。ｇ１とｇ２は、それぞれ人工芝のコートと土のコートを表わす。（ｇ１、ｇ２）は、人工芝のコートと土のコートの両方の時間枠を同時に獲得することを表わす。この場合、同じ時刻に離れた場所にある二つのコートの使用はできないため、各買手装置にとってどちらか一方のコートを確保すれば十分である。ここで｛ｃｏｎｄ｝＝｛天候｝（要素）とし、取る値は、｛晴れ、雨｝のいずれかとする。
図６は、再割り当てによる買手装置ｉの損害額ｖiS（）を表わす。異なる買手装置は異なる損害額の大きさを持つ。ｎｕｌｌは商品が何も割り当てられないことを意味する。ｎｕｌｌからコートｇ１への変更によって生じる損害は、ｇ１が事前に割り当てられておらず、使用の直前になって割り当てられることになって、ｇ１の使用に関する十分な準備期間がないことによる損害を表わす。一方、コートｇ１からｎｕｌｌへの変更によって生じる損害は、例えば、コートｇ１が使用できなくなり、テニス大会が中止になったことを参加者に連絡するための費用などが含まれる。
【００１４】
商品の全体としての価値は、オークションにおける商品の最終的な割当てである最終割当てと、商品の評価値に影響を与える外部的要因である環境条件と、オークション終了直後に実施される商品の仮割当てである初期割当てから最終割当てに至るまでの割当て変更に起因する損害とによって決まる。
社会的効用を最大化するには、つまり、売手装置の効用と買手装置の効用の和を最大化するには、割当てそのものに加えて、割当て変更による損害を計算に含める必要がある。この取扱いを可能にするために、割当て計画を導入する。割当て計画は、（１）初期割当てと（２）確率変数のある値が実現したときに割当ての変更の仕方を規定する遷移規則とから構成される。図７に割当て計画の例を示す。（ｇ１、ｇ２）＝（買手装置１、買手装置２）が初期割当てであり、雨が降れば割当てを（ｇ１、ｇ２）＝（買手装置２、買手装置１）に変更する、つまり買手装置１と買手装置２でコート使用権を交換することを意味する。また、晴れれば、割当ての変更は行わない。
【００１５】
次に、効用の表現法を以下に示す。
（条件８）
買手装置ｉの期待効用ｕi（）を以下に示す。
ｕi（）＝ｖi（ＡＰ）−ｐａｙｍｅｎｔi（ＡＰ）
＝ｖiP（Ｇifinal；｛ｃｏｎｄ｝）＋ｖiS（ＡＰ）−ｐａｙｍｅｎｔi（ＡＰ）
ＡＰは割当て計画を表わす。Ｇifinalは最終割当てで買手装置ｉに割り当てられた商品を表わす。
支払額ｐａｙｍｅｎｔiを決める方法は後述する。ここでは、主要な恩恵は最終割当てと環境条件にのみ依存すると条件し、損害ｖiSは割当ての遷移経路に沿って足し合わせるものとする。
確率変数の確率分布ｐを既知としているので、割当て計画ＡＰが与えられれば、期待効用を計算できる。
【００１６】
次に、以上の条件を基に３つの従来のオークション方法を説明する。
まず第１の方法として、電子式入札装置がＶＣＧオークションを用いて割当てを決め、それ以降変更しない方法（以下、「割当て固定法」という。）を説明する。
【００１７】
ＶＣＣオークションは社会的効用の期待値が最大となる割当てを選択し、以下の支払いを買手装置ｉに課す。
【００１８】
【数１】
2007026383.tif 000003
【００１９】
ここで、Ｇは、社会的効用の期待値が最大となる割当てを表し、Ｇ-iは、買手装置ｉが存在しないとした場合に社会的効用の期待値を最大にする割当てを表す。
【００２０】
例１として以下を考える。
買手装置１、買手装置２、買手装置３がコートｇ１、ｇ２を競っているとする。
買手装置の評価値は図５で与えられている。また、再割り当てによる損害は、各買手装置にとって、割当ての変更があれば−０．５、割当ての変更がなければ０とする。加えて、ｐ（天候＝晴れ）＝０．５、ｐ（天候＝雨〉＝０．５を条件する。
電子式入札装置は、オークションが行われた時点、つまり、使用当日晴れる確率が０．５、雨が降る確率が０．５という予報結果をもとに期待効用を計算する。これは図９に示される。これらの値に基づいて、ｇ１とｇ２は買手装置１と買手装置２に割り当てられる。買手装置１と買手装置２の支払額は、各々４．５、２．５と計算される。
この割当て固定法では、環境の変化に対応して柔軟に割当てを変更できないため、最終的に得られる社会的効用は減少する。
ここで、当日になって、天候が雨とわかったときに、買手装置１と買手装置２がコートｇ１とｇ２の使用権を交換すれば、社会的効用は６＋７−５−５−０．５−０．５＝２だけ増加する。ここで、０．５が二度引かれているのは、再割り当てによって買手装置１と買手装置２に発生する損害である。再割り当てによる損害は発生するものの、全体としては効用は増加する。従って、割当て固定法は、この社会的効用増加の機会を見逃してしまい、社会的効用を最大化できずパレート効率性を満たさない。
【００２１】
第２の方法は、環境条件の結果が判明するまで何も割り当てないことである。しかし、ｎｕｌｌから別の割当てに変更するときに生じる損害が大きければ、社会的効用は小さくなってしまい、パレート効率性を満たさない。例えば、テニス大会は、あらかじめ開催を案内しておかなければ、多くの参加者逢集めることは難しい。
【００２２】
第３の方法は、環境変化が生じる度に再割り当てを行うことである。しかし、この方法は、誘因の問題を生じさせる。すなわち、買手装置は割当て済みの商品が再び市場に出てくるのを待つか、別の代替商品を探すかという選択をしなければならない。しかし、例えば、買手装置が電子式入札装置に送信する入札値を低い値にしたり、高い値にしたりすることで、商品の割当て結果や支払額が異なる。幾つかある戦略の中で最善な戦略である均衡戦略がないと、この選択を正しく行うのは難しい。
例２として例１と同じ状況を考える。
割当てと支払いは図９に基づいて決定され、買手装置１はコートｇ１の使用権を獲得し、４．５を支払う。買手装置２はコートｇ２の使用権を獲得し、２．５を支払う。これらの支払額は、ＶＣＣオークションでの支払額の計算式から計算される。
ここで、買手装置３がコートｇ１に対する評価値を過大申告し、晴れた場合の評価値を３ではなく５と電子式入札装置に送信したとしよう。このとき、買手装置１の支払額は５．５となる。この場合、当日になって天候が雨と判明すれば、買手装置１の効用は負の値となる。
すなわち、ｕ1＝ｖ1P（ｇ１；雨）−ｐａｙｍｅｎｔ1＝５−５．５＝−０．５。
よって、買手装置１はコートｇ１の使用権を売ろうとし、買手装置３はコートｇ１の使用権を購入するチャンスが生じる。つまり、買手装置３はコートの割当てを操作できる。
以上より、環境変化に応じて割当てを変更し、誘因の問題を回避するには、割当てのどの部分を変更するかを注意深く選ぶ必要がある。そうしなければ、個人合理性を満たさない。
【００２３】
なお、出願人は、本明細書に記載した先行技術文献情報で特定される先行技術文献以外には、本発明に関連する先行技術文献を出願時までに発見するには至らなかった。
【特許文献１】特開２００１−２４３３６２号公報
【非特許文献１】Ｐ．Ｍｉｌｇｒｏｍ．ＰｕｔｔｉｎｇＡｕｃｔｉｏｎＴｈｅｏｒｅｙｔｏＷｏｒｋ．ＣａｍｂｒｉｄｇｅＵｎｉｖｅｒｓｉｔｙＰｒｅｓｓ，２００４．
【発明の開示】
【発明が解決しようとする課題】
【００２４】
以上のように、動的環境で商品の割当てを行う従来のオークション方法において、さらに個人合理性とパレート効率性とを兼ね備えたオークション方法はない。
そこで本発明は、動的環境で商品の割当てを行うオークション方法においてさらに個人合理性とパレート効率性とを兼ね備えたオークション方法を目的とする。
【課題を解決するための手段】
【００２５】
そこで、本発明である電子式入札装置は、売手装置が出品する商品の情報をネットワークを介して取得する売手情報取得手段と、前記売手情報取得手段から得た情報を買手装置に公開し、前記買手装置より入札対象となる任意の商品の組と、前記商品の組にかかる商品価値を変動させる外部的要因の中から任意に選択した環境条件と、前記商品の組と前記環境条件とにかかる入札価格である評価値と、買手装置に対する商品の変更前の割当てと、変更後の割当てと、その変更に付随する損害額とをネットワークを介して取得する買手情報取得手段と、前記買手情報取得手段により取得した情報に基づき、前記環境条件の要素ごとに実行可能な商品の割当てに対する社会的効用と、商品の割当て遷移規則とからなる割当て計画を作成する割当て計画作成手段と、前記外部的要因の各要素が決定されるたびに、前記遷移規則に従って社会的効用が最大の割当てを選び出すことによって、最終的な割当てを決定する最終割当て決定手段と、前記最終割当て決定手段により割当てられた買手装置がその商品を出品した売手装置に支払う額を買手装置の参加による他の買手装置の期待評価値の減少分に等しい額として算出する支払額算出手段とを備え、前記社会的効用は、売手装置の効用と買手装置の効用との総和とすることを特徴とする。
【００２６】
また、前記割当て計画作成手段は、一つの商品が同時に複数の買手装置に割当てられないよう商品割当てを計算する割当て計算手段と、前記割当て計算手段により計算された各割当てに対して社会的効用を計算する効用計算手段と、前記環境条件の要素における値の組み合わせにより増減する遷移規則のうち前記社会的効用が最大となる遷移規則を最適遷移規則とする値最適遷移規則決定手段と、前記値最適遷移規則決定手段を前記環境条件の全要素において行う要素最適遷移規則決定手段とからなるとしてもよい。
【発明の効果】
【００２７】
本発明によれば、動的環境で商品の割当てを行うオークション方法を備えた電子式入札装置において、個人合理性とパレート効率性を兼ね備えたオークション方法とすることができる。その理由を以下に示す。
まず、個人合理性について説明する。
買手装置ｉの入札が最終割当てに影響を与えなければ、それは一時的な割当てにも含まれず、その効用は０である。一方、もし買手装置ｉの入札が最終割当てに含まれるならば買手装置ｉの効用は買手装置ｉの参加による社会的効用の増分に等しくなる。加えて、何も割り当てられないという可能性もあるので、再割り当てによって大きな損害が発生する場合、その入札は最終割当てに含まれないはずである。よって、再割り当てによる損害が発生するとしても、期待値の上での個人合理性は満たされる。
従って、本発明は期待値の上での個人合理性を満たす。
なお、この命題は期待値の上での議論であることに注意が必要である。ある場合に買手装置の効用が負になることは生じうるが、期待効用が負の値になることはない。後述するように、条件付きの支払いを買手装置に課す場合は、買手装置の効用は、期待効用でなくても負の値になることはない。
【００２８】
次に、パレート効率性について説明する。
本発明によると、各買手装置の効用は以下のように計算される。
【００２９】
【数２】
2007026383.tif 000004
【００３０】
上式を見れば、第５項は買手装置ｉの入札から独立である、すなわち、買手装置ｉは第５項を操作できない。また、第１項から第４項は電子式入札装置が最大化しようとする目的関数に等しい。よって、買手装置ｉにとって、真実申告が最善である。
よって本発明において、各買手装置にとって、真実申告が最善であることがわかる。
また、割当て固定法によって得られる割当ても本発明の割当て計画の候補の中に含まれる。そして、本発明で選ばれた割当て計画は、全ての可能な割当て計画の中で社会的効用が最大となる割当て計画である。よって、本発明は割当て固定法に比べて社会的効用の期待値を増加させられるか、少なくとも、割当て固定法と同じ社会的効用の期待値を得られる。
さらに、本発明は、買手装置から評価値の真値を送信させることができ、その値に基づいて社会的効用の期待値を最大化する割当て計画を選び出すことができる。よって、本発明は社会的効用の期待値を最大化する割当てを実現できる。
上述したように、パレート効率性が満たされることは、社会的効用が最大化されることと等価であるので、本発明がパレート効率性を兼ね備えたものであるといえる。
【００３１】
従って、本発明は個人合理性とパレート効率性とを兼ね備えた電子式入札装置であり、買手装置は入札者が入力した商品の評価値をそのまま電子式入札装置に送信するだけで複雑な入札値計算を行うことなく、商品の最適な割当てを実現することができる。
【発明を実施するための最良の形態】
【００３２】
以下に、本発明の実施の形態について図面を参照しながら説明する。
【００３３】
図１に示すように、本実施の形態にかかる電子式入札装置１０の構成は、売手管理データベース１４、入札管理データベースＡ１５−１、入札管理データベースＢ１５−２、制御手段１７、および通信手段１８により構成される。
売手管理データベース１４は、売手装置１１（売手装置１、売手装置２）と販売商品に関する情報（以下、「商品情報」という。）を格納する。個々のレコードは、売手装置ＩＤ、販売商品ＩＤ、販売個数から構成される（図２）。入札管理データベースＡ１５−１は、買手装置１２（買手装置１、買手装置２、買手装置３）から送信された入札情報を格納する。個々のレコードは、買手装置ＩＤ、環境条件、商品の組、その評価値から構成される（図３）。
入札管理データベースＢ１５−２は、割当て変更による損害額を格納する。個々のレコードは、買手装置ＩＤ、変更前割当て、変更後割当て、この変更による損害額から構成される（図４）。
売手登録手段１６は、売手装置１１から送信された商品情報を売手管理データベース１４に登録する。入札登録手段２０は、買手装置１２から送信された入札情報を入札管理データベース１５−１または１５−２に登録する。落札者・落札価格決定手段は、落札者と落札価格を決定する。制御手段１７は、全体の制御を行う。通信手段１８は、電子式入札装置１０と売手装置１１、買手装置１２との間でネットワーク１３を介して情報の送受信を行う。
ここで、売手登録手段１６と制御手段１７と通信手段１８は、ネットワーク１３を介して、売手装置１１から商品情報を取得する売手情報取得手段として作用する。
また、入札登録手段２０と制御手段１７と通信手段１８は、ネットワーク１３を介して、売手装置１１から入札情報を取得する買手情報取得手段として作用する。
【００３４】
本実施の形態にかかる環境の変化に応じて商品の再割当を行うオークション方法を述べる。
まず割当て計画の作成方法を説明する。
割当て計画は、割当てと支払額の決定に用いられる。全ての場合の数え上げには膨大な計算を要するので、ここでは動的計画法を用いる。
ここで、確率変数は、ｃｏｎｄ1、ｃｏｎｄ2、…、ｃｏｎｄtという順序で判明するとして、以下のように割当て計画を作成する。
【００３５】
（手順１）売手装置１１は、商品情報を電子式入札装置１０に送信し、これを登録する。  このときの電子式入札装置１０の具体的動作は、まず、ネットワーク１３を介して、複数ある売手装置１１（売手装置１、売手装置２）からオークション出品の申し込みを受け付ける。
申し込みを受けた電子式入札装置１０は、申し込みをした売手装置１１から商品情報、例えば図２に示すように出品者を特定する売手装置ＩＤと、その売手装置ＩＤが出品した商品を特定する商品ＩＤと、その商品ＩＤで特定される商品の個数とを取得して売手管理データーベース１４に登録する。
【００３６】
（手順２）電子式入札装置１０は、オークションの開始時刻／終了時刻を含めた情報、具体的には、出品した商品の商品情報とその商品の入札開始時刻と終了時刻とをサイトに掲示することにより、公開する。
これにより出品された商品を紹介し、その商品に対する入札者を募ることができる。
（手順３）買手装置１２は、そのサイトから商品情報等を受信し、どの商品に入札するかを決定する。
【００３７】
（手順４）買手装置１２は、電子式入札装置１０に任意の入札対象となる任意の商品の組と、その商品の組にかかる環境条件（確率変数の値の任意の組）と、その商品の組とその環境条件とにかかる入札価格である評価値とを電子式入札装置１０に送信する。
また、電子式入札装置１０は、任意の商品の組と、環境条件と、評価値の組とを、ネットワーク１３を介して取得し、その情報を入札管理データベースＡ１５−１に記録することができる。
（手順５）買手装置１２は、再割当てに関して電子式入札装置１０に変更前の割当て、変更後の割当て、その変更に付随する損害額の組を電子式入札装置１０に送信する。
これらの情報は、（手順４）で受信した情報において仮に入札した商品が割り当てられ（変更前の割当て）、その後ある別の商品（割当てなしも含む）が再割当てされた（変更後の割当て）場合に生じる損害額である。
これらは、入札管理データベースＢ１５−２に記録される。
図４は、このような変更前の割当てと、変更後の割当てと、その変更に付随する損害額の組とをまとめて例示したものである。
【００３８】
以上の（手順２）から（手順５）までの処理を、入札の終了時刻になるまで入札希望者毎に行う。
終了時刻経過後に、電子式入札装置１０は、集積された３つのデータベース（売手管理データベース１４、入札管理データベースＡ１５−１、入札管理データベースＢ１５−２）に基づいて落札者・落札価格決定手段１９により商品の最終割当てを決定する。
以下の手順で、電子式入札装置１０における落札者・落札価格決定手段１９の詳細な流れを説明する。
【００３９】
（手順６）電子式入札装置１０は、割当て実行可能性を満たすように買手装置から送信されてきた入札の組合わせを数え上げ、商品の組と、環境条件とで組み合わされた全ての割当てパターンを算出する。ここで、割当て実行可能性とは一つの商品が同時に複数の買手装置１２に割り当てられないことを意味する。
【００４０】
（手順７）電子式入札装置１０は、各場合、つまり（手順６）で数え上げた環境条件毎の全割当てパターンそれぞれににおける社会的効用を計算する。
【００４１】
（手順８）電子式入札装置１０は、確率変数ｃｏｎｄtの値が判明する前の状態を数え上げる。可能な割当ての各々に対して、最適な遷移規則を見つける。ここで最適とは、社会的効用の期待値が最大化されることを意味する。可能な割当ての中には、ある商品が誰にも割り当てられない割当ても含む。
このようにして、確率変数ｃｏｎｄtから動的計画法により最適な遷移規則を見つけるための最初の計算が実行される。
【００４２】
（手順９）電子式入札装置１０は、確率変数ｃｏｎｄt-1とｃｏｎｄtが判明する前の状態を数え上げ、そこでの社会的効用を計算する。可能な割当ての各々に対して、電子式入札装置１０は、最適な遷移規則を選び出す。
【００４３】
（手順１０）電子式入札装置１０は、全ての確率変数の値が判明するまで（手順９）と同様の操作を繰り返す。すなわち、確率変数ｃｏｎｄtから確率変数ｃｏｎｄ1までの遷移規則から動的計画法により最適な遷移規則を見つけるために（手順９）と同様の再帰的計算を行う。この時点において、初期割当てと遷移規則からなる割当て計画が作成されている。
【００４４】
（手順１１）電子式入札装置１０は、社会的効用の期待値を最大化する割当て計画を選び出す。もし社会的効用の期待値を最大化する割当て計画が複数あれば、ランダムに一つの割当て計画を選び出す。
従って、（手順６）から（手順１１）により各確率変数が確定する毎の割当てを求めることができる割当て計画を算出し、その中から社会的効用の期待値を最大化する割当て計画を作成する割当て計画作成手段により、電子式入札装置１０は、最適な割当て計画を得る。
【００４５】
つぎに、作成された割当て計画を以下のように実行する。
（手順１２）電子式入札装置１０は、割当て計画を売手装置１１と買手装置１２に送信し、当該割当て計画中に記載された初期割当てを現在の割当てとする。
（手順１３）確率変数ｃｏｎｄ1の値が判明すれば電子式入札装置１０は、当該割当て計画に記載された遷移規則に従って現在の割当てを変更し、それを売手装置１１と買手装置１２に送信する。
（手順１４）全ての確率変数の値が判明した後、最終割当てが決定し、それを売手装置１１と買手装置１２に送信する。
従って、（手順１２）から（手順１４）により最終的な割当てを決定する最終割当て決定手段が示せた。
【００４６】
最終的な割当ての決定により商品の落札者が決定する。
以下に落札者（買手装置１２）がその商品を出品した出品者（売手装置１１）に支払う額を算出する支払額算出手段について説明する。
【００４７】
（手順１５）買手装置１２は売手装置１１に以下の支払いを行う。支払いは電子マネーを用いる、あるいは、銀行口座間で電信振替するなど様々な実装が可能である。
【００４８】
【数３】
2007026383.tif 000005
【００４９】
（手順１６）売手装置１１は、商品の送付が必要な場合には商品を買手装置１２に送付する。使用権などのように送付が不要なものについては、送付は行わず、買手装置１２が使用権を行使する。
なお、（手順１５）と（手順１６）は順序を入れ替えてもよい。
【００５０】
ここでは、割当て計画の作成、および、割当て計画の実行法を例を用いて説明する。
上述した例２と同じ問題設定を考える。発明方法の（手順６）において、電子式入札装置１０は、買手装置１２から送信された入札の組み合わせを数え上げる。そして、（手順７）において社会的効用を計算する。それは図１０に示される。
【００５１】
（手順８）において、遷移規則の組み合わせが調べられる。値を簡単にするために割当てなし（ｎｕｌｌ）を除くと全部で８１通りの遷移規則がある。それは図１１に示される。
この例では、確率変数を一つしか含まないので、（手順９）、（手順１０）はスキップされる。（手順１１）において、電子式入札装置１０は、社会的効用の期待値を最大化する割当て計画を選び出す。例２における確率変数の要素数は、｛晴れ｝と｛雨｝の二つであるので、電子式入札装置１０は、最適な割当て計画を二つ選び出すことになる。その二つの割当て計画については、それぞれ図７と図８に示す。図７における割当て計画の社会的効用は、以下のように計算される。もし晴れれば、再割り当てによる損害は０であり、最終割当てにおける社会的効用は、図５（ａ）より１０＋６＝１６となる。一方、雨になれば、再割り当てによる損害は、それぞれ−０．５としているので−０．５−０．５＝−１となり、最終割当てにおける社会的効用は、図５（ｂ）より７＋６＝１３となる。従って、ｐ（天候＝晴れ）＝０．５、ｐ（天候＝雨）＝０．５であるので社会的効用の期待値は、０．５×１６＋０．５×（一１＋１３）＝１４となる（結果は、図１０となる）。この図７の割当て計画が社会的効用の期待値を最大化するものである。社会的効用の期待値を最大化する割当て計画は、もう一つ存在し、それを図８に示す。
【００５２】
電子式入札装置１０は、この二つの割当て計画から一つをランダムに選択する。ここでは、図７にある割当て計画が選ばれたとする。
買手装置１の支払額は、以下のように計算される。最初に、買手装置１は、オークションに参加しないと仮定する。この場合、社会的効用の期待値を最大にする割当て計画は、図１２のようになる。
従って、図５、７及び１２より買手装置１の支払額ｐａｙｍｅｎｔ1は、上述したように、買手装置１がオークションに参加しない場合の買手装置２または買手装置３の評価値と、買手装置１がオークションに参加する場合の買手装置１以外の買手装置の評価値との差であり、晴れの確率及び雨の確率はそれぞれ０．５，割当て変更による損害額は−０．５とするので、以下のように計算される。
ｐａｙｍｅｎｔ1＝０．５×（６＋３）＋０．５×（５＋６）−（０．５×６＋０．５×（７−０．５））
＝３．７５
上式は、晴れの場合と雨の場合に分けることで、以下のように書ける。
ｐａｙｍｅｎｔ1＝０．５×（６＋３）＋０．５×（５＋６）一（０．５×６＋０．５×（７−０．５））
＝０．５×（６＋３−６）＋０．５×（５＋６−（７−０．５））
＝０．５×３＋０．５×４．５
【００５３】
従って、電子式入札装置１０は、（１）晴れ、雨どちらの場合でも買手装置１から３．７５を徴収する、あるいは、（２）雨の場合には４．５を徴収し、晴れの場合には３を徴収する。そして買手装置１の効用は、どちらの場合も負とならない。買手装置２についても同様に、その支払額ｐａｙｍｅｎｔ2は、４．７５と計算される。
【００５４】
例２において、買手装置３は割当てを操作できると指摘した。本発明方法では、そのような操作ができないことを確認する。ここでは、買手装置３が虚偽申告をして、晴れの場合のｇ１に１０−εを、雨の場合のｇ１に７−εという評価値を送信した場合を考える。εは微少値であるとする。本発明方法が用いられた場合、買手装置１の支払額は３．７５ではなく、７．７５（晴れの場合１０一ε、雨の場合５．５−ε）となる。このとき、買手装置１の効用は、晴れの場合、１０一（１０−ε）＝ε、雨の場合６−０．５一（５．５−ε）＝εとなり、買手装置１は損害を被らない。もし買手装置３がさらに過大申告すれば、割当て計画そのものが変化する。この場合、買手装置３の効用は負の値になることが容易に確かめられる。よって、買手装置３は虚偽申告によって利益を得ることができない。
なお、上述した電子式入札装置１０は、ＣＰＵと主記憶装置と外部記憶装置とネットワーク接続装置などを備えたコンピュータ機器であり、主記憶装置に展開されたプログラムによりＣＰＵが動作することで、上述した各手段または各データベースが実現される。また、この各手段または各データベースは、複数のコンピュータ機器に分散させるようにしてもよい。
【図面の簡単な説明】
【００５５】
【図１】本発明の実施の形態にかかる構成図である。
【図２】売手管理データベースのレコード形式例を示す図である。
【図３】入札管理データベースＡのレコード形式例を示す図である。
【図４】入札管理データベースＢのレコード形式例を示す図である。
【図５】条件付きの商品の評価値例を示す図である。
【図６】再割当による損害額の例を示す図である。
【図７】割当て計画の例を示す図である。
【図８】割当て計画の例を示す図である。
【図９】商品の期待評価値の計算例を示す図である。
【図１０】例２における社会的効用を示す図である。
【図１１】図１０の遷移規則例を示す図である。
【図１２】買手装置１を除いた場合における社会的効用の期待値を最大にする割当て計画の例を示す図である。
【符号の説明】
【００５６】
１０…電子式入札装置、１１…売手装置、１２…買手装置、１３…ネットワーク、１４…売手管理データベース、１５−１，２…入札管理データベース、１６…売手登録手段、１７…制御手段、１８…通信手段、１９…落札者・落札価格決定手段、２０…入札登録手段。
【図１】
2007026383.tif 000006
【図２】
2007026383.tif 000007
【図３】
2007026383.tif 000008
【図４】
2007026383.tif 000009
【図５】
2007026383.tif 000010
【図６】
2007026383.tif 000011
【図７】
2007026383.tif 000012
【図８】
2007026383.tif 000013
【図９】
2007026383.tif 000014
【図１０】
2007026383.tif 000015
【図１１】
2007026383.tif 000016
【図１２】
2007026383.tif 000017