(57)【特許請求の範囲】
【請求項１】
少なくともノード数、ノード内適用メカニズムおよびノード間リンク情報を含む、電子的にオークションを実行するルールを規定したメカニズムの仕様データを入力する仕様入力手段と、
入力された仕様データのノード内適用メカニズムについて、各種のノード内適用メカニズムにつき戦略的操作不可能性が満たされるか否かの判定情報が予め記載されているメカニズムテーブルを参照し、全てのノード内適用メカニズムについて戦略的操作不可能性が満たされるか否かをチェックするノード内適用メカニズム判定手段と、
前記仕様データのノード間リンク情報の始点ノードと終点ノードに着目してリンクの接続関係を追跡し、一のノードから出発したリンクが同じノードに戻ってくるリンクサイクルが生じている場合にその抽出を行うリンクサイクル抽出手段と、
抽出されたリンクサイクルのリンクタイプに着目し、高々１つの情報リンクを含むようなリンクサイクルが存在するか否かを判定するリンクサイクル判定手段と、
前記ノード内適用メカニズム判定手段の判定結果および／もしくは前記リンクサイクル判定手段の判定結果により、前記メカニズムが戦略的操作可能であるか戦略的操作不可能であるかの判定を行う判定手段と
を備えたことを特徴とするオークションメカニズム戦略的操作不可能性判定装置。
【請求項２】
少なくともノード数、ノード内適用メカニズムおよびノード間リンク情報を含む、電子的にオークションを実行するルールを規定したメカニズムの仕様データを入力する仕様入力工程と、
入力された仕様データのノード内適用メカニズムについて、各種のノード内適用メカニズムにつき戦略的操作不可能性が満たされるか否かの判定情報が予め記載されているメカニズムテーブルを参照し、全てのノード内適用メカニズムについて戦略的操作不可能性が満たされるか否かをチェックするノード内適用メカニズム判定工程と、
当該ノード内適用メカニズム判定工程が全てのノード内適用メカニズムについて戦略的操作不可能性が満たされていると判定した場合に、前記仕様データのノード間リンク情報の始点ノードと終点ノードに着目してリンクの接続関係を追跡し、一のノードから出発したリンクが同じノードに戻ってくるリンクサイクルが生じている場合にその抽出を行うリンクサイクル抽出工程と、
当該リンクサイクル抽出工程に続き、抽出されたリンクサイクルのリンクタイプに着目し、高々１つの情報リンクを含むようなリンクサイクルが存在するか否かを判定するリンクサイクル判定工程と、
前記ノード内適用メカニズム判定工程の判定結果および／もしくは前記リンクサイクル判定工程の判定結果により、前記メカニズムが戦略的操作可能であるか戦略的操作不可能であるかの判定を行う判定工程と
を備えたことを特徴とするオークションメカニズム戦略的操作不可能性判定制御方法。
【請求項３】
少なくともノード数、ノード内適用メカニズムおよびノード間リンク情報を含む、電子的にオークションを実行するルールを規定したメカニズムの仕様データを入力する仕様入力工程と、
入力された仕様データのノード間リンク情報の始点ノードと終点ノードに着目してリンクの接続関係を追跡し、一のノードから出発したリンクが同じノードに戻ってくるリンクサイクルが生じている場合にその抽出を行うリンクサイクル抽出工程と、
抽出されたリンクサイクルのリンクタイプに着目し、高々１つの情報リンクを含むようなリンクサイクルが存在するか否かを判定するリンクサイクル判定工程と、
当該リンクサイクル判定工程が高々１つの情報リンクを含むようなリンクサイクルが存在しないと判定した場合に、前記仕様データのノード内適用メカニズムについて、各種のノード内適用メカニズムにつき戦略的操作不可能性が満たされるか否かの判定情報が予め記載されているメカニズムテーブルを参照し、全てのノード内適用メカニズムについて戦略的操作不可能性が満たされるか否かをチェックするノード内適用メカニズム判定工程と、
前記リンクサイクル判定工程の判定結果および／もしくは前記ノード内適用メカニズム判定工程の判定結果により、前記メカニズムが戦略的操作可能であるか戦略的操作不可能であるかの判定を行う判定工程と
を備えたことを特徴とするオークションメカニズム戦略的操作不可能性判定制御方法。
【請求項４】
少なくともノード数、ノード内適用メカニズムおよびノード間リンク情報を含む、電子的にオークションを実行するルールを規定したメカニズムの仕様データを入力する仕様入力工程と、
入力された仕様データのノード内適用メカニズムについて、各種のノード内適用メカニズムにつき戦略的操作不可能性が満たされるか否かの判定情報が予め記載されているメカニズムテーブルを参照し、全てのノード内適用メカニズムについて戦略的操作不可能性が満たされるか否かをチェックするノード内適用メカニズム判定工程と、
当該ノード内適用メカニズム判定工程と非同期に並行して実行され、前記仕様データのノード間リンク情報の始点ノードと終点ノードに着目してリンクの接続関係を追跡し、一のノードから出発したリンクが同じノードに戻ってくるリンクサイクルが生じている場合にその抽出を行うリンクサイクル抽出工程と、
抽出されたリンクサイクルのリンクタイプに着目し、高々１つの情報リンクを含むようなリンクサイクルが存在するか否かを判定するリンクサイクル判定工程と、
前記ノード内適用メカニズム判定工程の判定結果および前記リンクサイクル判定工程の判定結果により、前記メカニズムが戦略的操作可能であるか戦略的操作不可能であるかの判定を行う判定工程と
を備えたことを特徴とするオークションメカニズム戦略的操作不可能性判定制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子的にオークションを実行するルールを規定したメカニズムを設計する際の支援技術に関する。
【背景技術】
【０００２】
インターネットオークションは、多数の企業や消費者による様々な財（リソース）の取引に利用されており、電子商取引の主要な一分野となっている。また、インターネットオークションは、エージェント技術の有望な適用領域として人工知能やマルチエージェントシステムなどの研究分野で活発に研究が行われている。
【０００３】
一般的なオークションでは、財を販売する売手が存在しているため、落札者から集めた支払額は売手に与えられる。しかしながら、複数人が共有する財の使用権を決定するようなオークションでは、オークションの対象の財が共同所有であるため、売手に値する者が存在せず、集めた支払額をどうするかが問題となる。例えば、共同で車を所有し、週末に誰がその車を使用するかを決定するためにオークションを行うような場合である。
【０００４】
このように、オークションの落札者と支払額を割り当てるだけでなく、支払額の配分も決定するメカニズムを再配分メカニズムと呼ぶ。再配分メカニズムの設計は、最近、メカニズムデザインの研究において注目されている研究トピックスである。
【０００５】
オークションの対象となる財としては単一である場合や複数である場合があり、複数の場合であっても同じ財が複数（複数ユニット）である場合と、種類の異なる財の組み合わせである場合とがある。以下では複数ユニットについてのオークションに限って話を進める。
【０００６】
ところで、オークションにおける好ましい性質として、戦略的操作不可能性（strategy-proofness）と個人合理性（individual rationality）と強予算均衡（strongly budget balance）とが存在する。戦略的操作不可能性とは、各入札者にとって、真の評価値を申告することが支配戦略、すなわち他の入札者の行動に関わらず最適な戦略となることである。個人合理性とは、各入札者が支配戦略を用いた場合、オークションに参加したことにより、参加しない場合と比較して効用が減少することがないことである。強予算均衡とは、再配分額の総和が支払額の総和と一致することを意味する。より弱い条件として、再配分額の総和が支払額の総和を超えることはない、すなわち、再配分額が足りなくなることがないことを非損失（non-deficit）という。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Cavallo, R.: Optimal decision-making with minimal waste: strategyproof redistribution of VCG payments, in Proceedings of the 5th international joint conference on Autonomous agents and Multiagent Systems (AAMAS'06), pp. 882-889 (2006)
【非特許文献２】Faltings, B.: A Budget-Balanced, Incentive-Compatible Scheme for Social Choice, in Agent-Mediated Electronic Commerce Workshop (AMEC'04), pp. 30-43 (2004)
【非特許文献３】Guo, M. and Conitzer, V.: Better redistribution with inefficient allocation in multi-unit auctions with unit demand, in In Proceedings of the 9th ACM Conference on Electronic Commerce (EC'08), pp. 210-219 (2008)
【非特許文献４】Borgs, C., Chayes, J., Immorlica, N., Mahdian, M., and Saberi, A.: Multi-unit auctions with budget-constrained bidders, in Proceedings of the 7th ACM Conference on Electronic Commerce (EC'05), pp. 44-51 (2005)
【発明の概要】
【発明が解決しようとする課題】
【０００８】
従来、オークションメカニズム設計では、入札者の効用は財に対する評価値と支払額の差分で与えられる準線形効用であるという仮定の下で議論が行われてきた。このような仮定の元において、複数ユニットについての再配分を伴う使用権のオークションに対し、Ｃａｖａｌｌｏメカニズム（例えば、非特許文献１参照。）やＦａｌｔｉｎｇｓメカニズム（例えば、非特許文献２参照。）や区分メカニズム（例えば、非特許文献３参照。）が戦略的操作不可能性を満たすことが知られている。
【０００９】
Ｃａｖａｌｌｏメカニズムでは、ＶＣＧ（Vickrey Clarke Groves）メカニズムによって勝者と支払額を決定する。ＶＣＧメカニズムでは、最も高い入札額の入札者が落札者となり、落札者の支払額は２番目に高い入札額となる。Ｃａｖａｌｌｏメカニズムにおける各入札者の再配分額は、自分を除いたときのＶＣＧメカニズムにおける支払額の均等割りである。
【００１０】
Ｆａｌｔｉｎｇｓメカニズムでは、一人の入札者を除外してｎ−１人に対してＶＣＧメカニズムを適用して割り当てを決定する。除外入札者が集められた支払額を全て受け取る。
【００１１】
非特許文献３では、複数ユニットオークションで各入札者は１財だけを必要とする場合において、上述の一人の入札者を除外するアイデアを一般化し、財と入札者を２つの区分（グループ）に分け、それぞれでＶＣＧメカニズムを適用し、その支払額を相手のグループで再配分するという区分メカニズムのクラスを提案している。
【００１２】
しかしながら、現実的には入札者はある財に対して非常に高い評価値を持っていても、その評価値と同額の支払額を請求された場合、それに対する支払能力が常にあるとは限らない。理論的には、評価値よりも低い金銭的な上限は予算制約（budget limitation）と呼ばれる。予算制約を持つ入札者の効用は準線形効用では表現できない。このような予算制約は現実的な選好の典型的な例の一つである。例えば、複数の町が複数の健康診断車両の使用権をオークションで決定する状況など、公共設備の使用権の割り当てなどが想定される。公共設備の使用権は住民のニーズが高いとき、非常に高い価値を持つかもしれない。しかしながら、その一方で予算上の制約があることが予想される。従って，再配分メカニズムにおいて、入札者が予算制約を持つ場合のメカニズムを設計することは実用上有益であると考える。
【００１３】
しかしながら、上述したＣａｖａｌｌｏメカニズムやＦａｌｔｉｎｇｓメカニズムや区分メカニズムは、予算制約がある状況での複数ユニットについての再配分を伴う使用権のオークションに対し戦略的操作不可能性を満たさない。
【００１４】
以下、既存の再配分メカニズムについて、予算制約付き入札者が存在した場合の影響を示す。なお、財ひとつ分の評価値は入札者ｉのみが観察できるシグナルであるタイプとしてθｉと標記し、入札者ｉが財をｋ個だけ得た時の財に対する評価値（グロス効用）をｖ（θｉ，ｋ）と標記する。支払額ｐがある場合の効用はｕ（θｉ，ｋ，ｐ）となり、ｐがゼロの場合の効用がグロス効用ｖ（θｉ，ｋ）である。
【００１５】
Ｃａｖａｌｌｏメカニズムでは、単一財の場合においても、予算制約付き入札者が存在した場合、戦略的操作不可能性を満たさない。以下、例を用いて示す。
【００１６】
先ず、予算制約を考慮せずにｖ（θｉ，１）に基づいてＣａｖａｌｌｏメカニズムを適用した場合、戦略的操作不可能性を満たさないことを示す。
【００１７】
３人の入札者が存在するとする。各入札者のグロス効用ｖ（θｉ，１）と予算ｂｉの組み合せ（ｖ（θｉ，１），ｂｉ）を申告する。入札者＃１は（１０，４）、入札者＃２は（５，５）、入札者＃３は（１，１）を入札するとする。このとき、入札者＃１が財を得ることになる。「５」を支払い、「１／３」を再配分額として受け取ることができるが、最終的な支払額は「１４／３」となり、予算「４」を超えてしまう。従って、財を得ることができない。
【００１８】
ここで、入札者＃２が（３，５）というように評価値を低く入札すれば、入札者＃１の最終的な支払額は「３−１／３＝８／３」となり、支払うことができるため、入札者＃２も再配分額「１／３」を得ることができる。
【００１９】
次に、予算制約を考慮してｍｉｎ（ｖ（θｉ，１），ｂｉ）に基づいてＣａｖａｌｌｏメカニズムを適用しても戦略的操作不可能性を満たさないことを示す。
【００２０】
上記の例と同様の状況を考える。入札者＃１は（１０，４）、入札者＃２は（５，５）、入札者＃３は（３，３）を入札するとする。
【００２１】
このとき、入札者＃２が財を得ることができる。しかしながら、入札者＃１が予算を「６」と過大申告すれば、入札者＃１に財を割り当てられ、支払額も「５−１＝４」となるため、支払うことができる。
【００２２】
次に、Ｆａｌｔｉｎｇｓメカニズムについて説明する。Ｆａｌｔｉｎｇｓメカニズムは、単一財の場合と限界効用が逓減する場合は、予算制約付き入札者が存在したときでもｍｉｎ（ｖｉ（１），ｂｉ）に基づいて割り当てを決定すれば、戦略的操作不可能性を満たす。しかしながら、非特許文献４で示されているが、限界効用が逓増する場合はＶＣＧメカニズムが戦略的操作不可能性を満たさないため、戦略的操作不可能性を満たすことができない。
【００２３】
以下、ＶＣＧメカニズムが戦略的操作不可能性を満たさない例を示す。この例では、各入札者は単一の単位価格で構成されるとする。
【００２４】
２ユニットの財のオークションに二人の入札者が参加しているとする。入札者＃１の真のグロス効用と予算を（ｖ（θ１，１），ｂ１）＝（１０，１０）、入札者＃２は（ｖ（θ２，１），ｂ２）＝（３，５）とする。ｖ（θｉ，２）＝２ｖ（θｉ，１）とする。このとき、ＶＣＧメカニズムを（ｖ'（θｉ，１），ｖ'（θｉ，２））＝（ｍｉｎ（ｖ（θｉ，１），ｂｉ），ｍｉｎ（２ｖ（θｉ，１），ｂｉ））の値（評価ベクトル）に適用する。これは支払額が予算以下になることを保証するためである。
【００２５】
入札者＃１と入札者＃２の評価ベクトルはそれぞれ、（１０，１０）と（３，５）になる。従って、入札者＃１と入札者＃２に１ユニットずつ割り当てるのが最適となる。結果、入札者＃１の支払額は「５−３＝２」、入札者＃２の支払額は「１０−１０＝０」となる。よって、入札者＃１の効用は「１０−２＝８」となる。
【００２６】
さて、入札者＃１がグロス効用を過少申告して（ｖ（θ１，１），ｂ１）＝（５，１０）としたとき、支払額「５−０＝５」で２ユニット得ることができる。結果、入札者＃１の効用は「２０−５＝１５」となり、過少申告によって効用を増加させることが可能である。
【００２７】
一方、近年、再配分を伴わない一般のオークションに対して、戦略的操作不可能性を満たすメカニズムがいくつか提案されている。例えば、非特許文献４では、区分メカニズムのアイデアと同様に入札者と財を二つの区分に分け、片方の区分の入札額を用いて、もう一方の区分での販売価格を決定することにより、予算制約下で適切な価格を決定する方法を提案している。ここでは、このメカニズムをＢｏｒｇｓメカニズムと呼ぶ。
【００２８】
しかしながら、このＢｏｒｇｓメカニズムであっても、予算制約がある状況での複数ユニットについての再配分を伴う使用権のオークションに対しては、戦略的操作不可能性を満たさない。
【００２９】
以下、Ｂｏｒｇｓメカニズムが戦略的操作不可能性を満たさない例を示す。ＡとＢの２つのグループに分割し、Ａの価格ｐＢはＢの入札者らによって決定される。従って、Ａで集まった支払額をＢで再配分することで強予算均衡を満たすことができるが、Ｂの入札者らには自分の入札額が再配分額に直接影響するため、過大申告することで再配分額を増やすことができる。従って、支払額の再配分を行う場合、Ｂｏｒｇｓメカニズムでは戦略的操作不可能性を満たさない。
【００３０】
我々の知る限り、入札者が予算制約を持つ場合を対象とした、戦略的操作不可能な再配分メカニズムの提案は行われていない。
【００３１】
本発明は上記の従来の問題点に鑑み提案されたものであり、その目的とするところは、予算制約がある状況での複数ユニットについての再配分を伴う使用権のオークションに対して、そのメカニズムが戦略的操作不可能性を満たすか否かを容易に判定することのできるオークションメカニズム戦略的操作不可能性判定装置を提供することにある。
【課題を解決するための手段】
【００３２】
上記の課題を解決するため、本発明にあっては、請求項１に記載されるように、少なくともノード数、ノード内適用メカニズムおよびノード間リンク情報を含む、電子的にオークションを実行するルールを規定したメカニズムの仕様データを入力する仕様入力手段と、入力された仕様データのノード内適用メカニズムについて、各種のノード内適用メカニズムにつき戦略的操作不可能性が満たされるか否かの判定情報が予め記載されているメカニズムテーブルを参照し、全てのノード内適用メカニズムについて戦略的操作不可能性が満たされるか否かをチェックするノード内適用メカニズム判定手段と、前記仕様データのノード間リンク情報の始点ノードと終点ノードに着目してリンクの接続関係を追跡し、一のノードから出発したリンクが同じノードに戻ってくるリンクサイクルが生じている場合にその抽出を行うリンクサイクル抽出手段と、抽出されたリンクサイクルのリンクタイプに着目し、高々１つの情報リンクを含むようなリンクサイクルが存在するか否かを判定するリンクサイクル判定手段と、前記ノード内適用メカニズム判定手段の判定結果および／もしくは前記リンクサイクル判定手段の判定結果により、前記メカニズムが戦略的操作可能であるか戦略的操作不可能であるかの判定を行う判定手段とを備えるオークションメカニズム戦略的操作不可能性判定装置を要旨としている。
【００３３】
また、請求項２に記載されるように、少なくともノード数、ノード内適用メカニズムおよびノード間リンク情報を含む、電子的にオークションを実行するルールを規定したメカニズムの仕様データを入力する仕様入力工程と、入力された仕様データのノード内適用メカニズムについて、各種のノード内適用メカニズムにつき戦略的操作不可能性が満たされるか否かの判定情報が予め記載されているメカニズムテーブルを参照し、全てのノード内適用メカニズムについて戦略的操作不可能性が満たされるか否かをチェックするノード内適用メカニズム判定工程と、当該ノード内適用メカニズム判定工程が全てのノード内適用メカニズムについて戦略的操作不可能性が満たされていると判定した場合に、前記仕様データのノード間リンク情報の始点ノードと終点ノードに着目してリンクの接続関係を追跡し、一のノードから出発したリンクが同じノードに戻ってくるリンクサイクルが生じている場合にその抽出を行うリンクサイクル抽出工程と、当該リンクサイクル抽出工程に続き、抽出されたリンクサイクルのリンクタイプに着目し、高々１つの情報リンクを含むようなリンクサイクルが存在するか否かを判定するリンクサイクル判定工程と、前記ノード内適用メカニズム判定工程の判定結果および／もしくは前記リンクサイクル判定工程の判定結果により、前記メカニズムが戦略的操作可能であるか戦略的操作不可能であるかの判定を行う判定工程とを備えるオークションメカニズム戦略的操作不可能性判定制御方法として構成することができる。
【００３４】
また、請求項３に記載されるように、少なくともノード数、ノード内適用メカニズムおよびノード間リンク情報を含む、電子的にオークションを実行するルールを規定したメカニズムの仕様データを入力する仕様入力工程と、入力された仕様データのノード間リンク情報の始点ノードと終点ノードに着目してリンクの接続関係を追跡し、一のノードから出発したリンクが同じノードに戻ってくるリンクサイクルが生じている場合にその抽出を行うリンクサイクル抽出工程と、抽出されたリンクサイクルのリンクタイプに着目し、高々１つの情報リンクを含むようなリンクサイクルが存在するか否かを判定するリンクサイクル判定工程と、当該リンクサイクル判定工程が高々１つの情報リンクを含むようなリンクサイクルが存在しないと判定した場合に、前記仕様データのノード内適用メカニズムについて、各種のノード内適用メカニズムにつき戦略的操作不可能性が満たされるか否かの判定情報が予め記載されているメカニズムテーブルを参照し、全てのノード内適用メカニズムについて戦略的操作不可能性が満たされるか否かをチェックするノード内適用メカニズム判定工程と、前記リンクサイクル判定工程の判定結果および／もしくは前記ノード内適用メカニズム判定工程の判定結果により、前記メカニズムが戦略的操作可能であるか戦略的操作不可能であるかの判定を行う判定工程とを備えるオークションメカニズム戦略的操作不可能性判定制御方法として構成することができる。
【００３５】
また、請求項４に記載されるように、少なくともノード数、ノード内適用メカニズムおよびノード間リンク情報を含む、電子的にオークションを実行するルールを規定したメカニズムの仕様データを入力する仕様入力工程と、入力された仕様データのノード内適用メカニズムについて、各種のノード内適用メカニズムにつき戦略的操作不可能性が満たされるか否かの判定情報が予め記載されているメカニズムテーブルを参照し、全てのノード内適用メカニズムについて戦略的操作不可能性が満たされるか否かをチェックするノード内適用メカニズム判定工程と、当該ノード内適用メカニズム判定工程と非同期に並行して実行され、前記仕様データのノード間リンク情報の始点ノードと終点ノードに着目してリンクの接続関係を追跡し、一のノードから出発したリンクが同じノードに戻ってくるリンクサイクルが生じている場合にその抽出を行うリンクサイクル抽出工程と、抽出されたリンクサイクルのリンクタイプに着目し、高々１つの情報リンクを含むようなリンクサイクルが存在するか否かを判定するリンクサイクル判定工程と、前記ノード内適用メカニズム判定工程の判定結果および前記リンクサイクル判定工程の判定結果により、前記メカニズムが戦略的操作可能であるか戦略的操作不可能であるかの判定を行う判定工程とを備えるオークションメカニズム戦略的操作不可能性判定制御方法として構成することができる。
【発明の効果】
【００３６】
本発明のオークションメカニズム戦略的操作不可能性判定装置にあっては、予算制約がある状況での複数ユニットについての再配分を伴う使用権のオークションに対して、戦略的操作不可能性を満たすか否かを容易に判定することができる。
【図面の簡単な説明】
【００３７】
【図１】リンクの例を示す図（その１）である。
【図２】リンクの例を示す図（その２）である。
【図３】本発明の一実施形態にかかるシステムの構成例を示す図である。
【図４】仕様データの例を示す図である。
【図５】メカニズムテーブルの例を示す図である。
【図６】オークションメカニズム戦略的操作不可能性判定装置のハードウェア構成例を示す図である。
【図７】実施形態の処理例を示すフローチャートである。
【図８】戦略的操作不可能性の判定例を示す図である。
【発明を実施するための形態】
【００３８】
以下、本発明の好適な実施形態につき説明する。
【００３９】
＜原理＞
本実施形態による判定手法は、処理の対象となる区分間に存在する、入札者に関する情報、再配分、および、売れ残った財の流れに着目し、どのような条件を満たせば戦略的操作不可能なメカニズムとなるか否かを判定するものである。そのための十分条件を満たすメカニズムのクラス（集合）を一般化区分メカニズム（ＧＰＭ：Generalized Partition Mechanism for budget constrained bidders）と呼ぶこととする。
【００４０】
ここでは条件を明確化するために、有向グラフを用いて区分間の関係を示す。グラフにおいてノードは区分を示し、ノード間には３つの種類のリンクが存在する。リンクはそれぞれ、入札者から申告されたグロス効用と再配分額を受け取る前の予算に基づく情報のリンク（情報リンク：information link）、再配分額のリンク（マネーリンク：money link）、売れ残った財のリンク（アイテムリンク：goods link）から構成される。
【００４１】
図１において、ｉは情報リンク、ｍはマネーリンク、ｇはアイテムリンクを示す。図１（ａ）は、区分Ａと区分Ｂの関係を示す。この図では、区分Ａから区分Ｂへ情報リンクｉ、マネーリンクｍ、アイテムリンクｇが張られており、区分Ａの入札者の情報、支払額と売れ残った財が区分Ｂに流れることとなる。
【００４２】
ここでは、区分Ｂでの割り当ての決定は以下の方法で行われると仮定する。
（１）情報リンクｉが区分Ａから区分Ｂへ張られているとき、区分Ｂで適用される割り当てルールのパラメータ、例えば、販売単位価格などを区分Ａの入札者が申告したグロス効用と予算に基づいて決定する。このとき、区分Ａから区分Ｂへのマネーリンクｍ、アイテムリンクｇは考慮しない。もし情報リンクｉが張られていない場合は、区分Ｂのみの入札者の情報だけで、割り当てを決定する。
（２）情報リンクｉだけでなく、マネーリンクｍ、アイテムリンクｇが存在する場合、まず、区分Ｂの入札者らへ再配分額を与え、次に、過程（１）で決定した割り当てルールに従って、区分Ａから受け取った財と区分Ｂで本来割り当てられる予定である財を含めて割り当てを行う。
【００４３】
以上の前提から、次の定理を見出すことができる。
【００４４】
定理１・・・高々１つの情報リンクを含むようなサイクル（リンクサイクル）が存在せず、各区分では戦略的操作不可能なメカニズムを適用するとき、入札者が予算制約を持っていても、再配分メカニズムは戦略的操作不可能性を満たす。
【００４５】
図１（ｂ）に示しているように、流入する情報リンクｉは流出するマネーリンクｍとアイテムリンクｇに影響を与えるが、流出する情報リンクｉには影響を与えない。これは、流出する情報リンクｉは、その出元の区分の入札者の情報だけに基づいて構成されるからである。一方、図１（ｃ）に示しているように、流入するマネーリンクｍやアイテムリンクｇは、流出するマネーリンクｍやアイテムリンクｇに影響する。しかしながら、これらのリンクは、流出する情報リンクｉには影響を与えない。よって、高々１つの情報リンクｉを含むようなサイクルが存在せず、各区分で戦略的操作不可能なメカニズムを適用すれば、全体としても戦略的操作不可能なメカニズムとなる。
【００４６】
例えば、図２（ａ）では、区分Ａ、Ｂ、Ｃの間にサイクルが存在し、そのサイクルには、情報リンクｉが区分Ｃと区分Ａの間にしか存在せず、区分Ａと区分Ｂ、区分Ｂと区分Ｃの間にマネーリンクｍとアイテムリンクｇが存在する。ここでは、区分Ａ、Ｂ、Ｃという順に割り当てが決定され、区分Ｃの入札者には区分Ａへ流す入札情報を操作することで、区分Ａから区分Ｂへ流れる再配分額を操作することが可能であり、さらに、その操作は区分Ｂから区分Ｃへの再配分額に伝播する。従って、戦略的操作可能なケースとなる。
【００４７】
一方、図２（ｂ）では区分Ａ、Ｂ、Ｃの間にサイクルが存在するが、３つの情報リンクｉがある一方で、マネーリンクｍとアイテムリンクｇは１つしか存在していない。よって、マネーリンクｍ、アイテムリンクｇを通して操作の伝播が行われないため、戦略的操作不可能なケースとなる。
【００４８】
＜システム構成＞
図３は本発明の一実施形態にかかるシステムの構成例を示す図である。
【００４９】
図３において、インターネット等のネットワーク１には、ユーザが操作するＰＣ（Personal Computer）、携帯電話、ＰＤＡ（Personal Digital Assistants）等のユーザ端末２Ａ、２Ｂ、・・が複数接続されている。ユーザ端末２Ａ、２Ｂ、・・は、一般的なブラウザ（Ｗｅｂブラウザ）２１Ａ、２１Ｂ、・・を備えている。ブラウザ２１Ａ、２１Ｂ、・・は、インターネットの標準プロトコルであるＨＴＴＰ（Hyper Text Transfer Protocol）等に従い、ＨＴＭＬ（Hyper Text Markup Language）等の言語で記述されたページデータの要求・取得・表示およびフォームデータの送信等を行う機能を有している。
【００５０】
一方、ネットワーク１には、ユーザの操作するユーザ端末２Ａ、２Ｂ、・・のブラウザ２１Ａ、２１Ｂ、・・からアクセスが可能なオークションメカニズム戦略的操作不可能性判定装置３が接続されている。
【００５１】
オークションメカニズム戦略的操作不可能性判定装置３は、機能部として、オークションメカニズム仕様入力部３０１とノード内適用メカニズム判定部３０２とリンクサイクル抽出部３０３とサイクル特性判定部３０４と判定結果出力部３０５とを備えている。これらの機能部は、オークションメカニズム戦略的操作不可能性判定装置３を構成するコンピュータのＣＰＵ（Central Processing Unit）、ＲＯＭ（Read Only Memory）、ＲＡＭ（Random Access Memory）等のハードウェア資源上で実行されるコンピュータプログラムによって実現されるものである。これらの機能部は、単一のコンピュータ上に配置される必要はなく、必要に応じて分散される形態であってもよい。
【００５２】
また、オークションメカニズム戦略的操作不可能性判定装置３は、管理するデータを保持するデータ格納部３０６を備えている。データ格納部３０６はＨＤＤ（Hard Disk Drive）やＲＡＭ等の記憶媒体により構成される。
【００５３】
オークションメカニズム仕様入力部３０１は、オークションメカニズムの検証を行おうとするユーザからオークションメカニズムの仕様を入力する機能を有している。オークションメカニズム仕様入力部３０１はユーザ端末２Ａ、２Ｂ、・・のブラウザ２１Ａ、２１Ｂ、・・に仕様入力画面を表示し、所定の項目を選択あるいは入力させることにより仕様入力を行う。入力された仕様データはデータ格納部３０６に格納される。
【００５４】
図４は仕様データの例を示す図であり、「ノード数」「ノード内適用メカニズム」「ノード間リンク情報」等の項目を有している。
【００５５】
「ノード数」は、オークションメカニズムの処理の区分となるノードの数である。ノードは、複数の入札者を含むグループである場合もあるし、入札者の個々となる場合もある。
【００５６】
「ノード内適用メカニズム」は、ノード内の処理に適用されるオークションメカニズムを特定する名称もしくはＩＤである。オークションメカニズムとしては、ＭＦＭ（Modified Faltings Mechanism）、ＭＢＭ（Modified Borgs Mechanism）、ＲＰＭ（Redistributable Partition Mechanism）、ＳＰＭ（Sequential Partition Mechanism）、Ｃａｖａｌｌｏメカニズム、Ｆａｌｔｉｎｇｓメカニズム、Ｂｏｒｇｓメカニズム等が存在する。「ノード内適用メカニズム」はノード毎に設定される。
【００５７】
「ノード間リンク情報」は、２つのノードの間に張られるリンク（情報の流れ）の個々についての情報である。「ノード間リンク情報」は、リンク毎に、「始点ノード」「終点ノード」「リンクタイプ」が設定される。「始点ノード」はリンクの始点となるノードを特定する名称もしくはＩＤである。「終点ノード」はリンクの終点となるノードを特定する名称もしくはＩＤである。「リンクタイプ」は、リンクの種別を特定する名称もしくはＩＤであり、前述した情報リンクとマネーリンクとアイテムリンクとがある。
【００５８】
図３に戻り、オークションメカニズム仕様入力部３０１は、仕様入力に際し、ノードに適用されるメカニズム名称の入力を簡略化するために、データ格納部３０６に格納されたメカニズムテーブルから取得したメカニズム名称を選択候補として用いることができる。
【００５９】
図５はメカニズムテーブルの例を示す図であり、「メカニズムＩＤ」「メカニズム名称」「戦略的操作不可能性」等の項目を有している。「メカニズムＩＤ」は、オークションメカニズムを識別する記号である。「メカニズム名称」はオークションメカニズムの一般的な名称である。「戦略的操作不可能性」は当該オークションメカニズムについて、複数ユニットかつ再配分が行われるオークションにおいて、予め戦略的操作不可能性が満たされるかどうかの情報である。「ＯＫ」は戦略的操作不可能性が満たされることを示し、「ＮＧ」は戦略的操作不可能性が満たされないことを示す。
【００６０】
図３に戻り、ノード内適用メカニズム判定部３０２は、ユーザにより入力された仕様データのノード内適用メカニズムについてメカニズムテーブルを参照し、全てのノード内適用メカニズムについて戦略的操作不可能性が満たされているか否かをチェックする機能を有している。いずれか一つでも戦略的操作不可能性が満たされないノードがある場合、全体のオークションメカニズムについて戦略的操作不可能性が満たされない旨を判定結果出力部３０５に通知する。
【００６１】
リンクサイクル抽出部３０３は、ユーザにより入力された仕様データのノード間リンク情報の始点ノードと終点ノードに着目してリンクの接続関係を追跡し、一のノードから出発したリンクが同じノードに戻ってくるリンクサイクルが生じている場合にその抽出を行う機能を有している。抽出したリンクサイクルデータ（リンクサイクルを構成するリンク番号およびリンクタイプの対を複数並べたデータ）はデータ格納部３０６に格納される。
【００６２】
サイクル特性判定部３０４は、リンクサイクル抽出部３０３が出力したリンクサイクルデータに基づき、リンクタイプに着目して、高々１つの情報リンクを含むようなリンクサイクルが存在するか否かにより、戦略的操作可能であるか戦略的操作不可能であるかの判定を行い、判定結果を判定結果出力部３０５に出力する機能を有している。高々１つの情報リンクを含むようなリンクサイクルが一つでも存在する場合は戦略的操作可能であり、高々１つの情報リンクを含むようなリンクサイクルが一つも存在しない場合は戦略的操作不可能であるとの判定結果を出力する。判定結果はデータ格納部３０６にも格納される。
【００６３】
なお、ノード内適用メカニズム判定部３０２において全てのノード内適用メカニズムについて戦略的操作不可能性が満たされている場合にのみリンクサイクル抽出部３０３およびサイクル特性判定部３０４による処理を行うものとしているため、サイクル特性判定部３０４では高々１つの情報リンクを含むようなリンクサイクルが一つでも存在する場合は仕様データの示すメカニズムが戦略的操作可能であり、一つも存在しない場合は戦略的操作不可能であると判定している。
【００６４】
反対に、リンクサイクル抽出部３０３およびサイクル特性判定部３０４による処理を先に行い、サイクル特性判定部３０４において高々１つの情報リンクを含むようなリンクサイクルが一つも存在しない場合にのみノード内適用メカニズム判定部３０２による処理を行い、全てのノード内適用メカニズムについて戦略的操作不可能性が満たされている場合に戦略的操作不可能であると判定するようにしてもよい。
【００６５】
また、ノード内適用メカニズム判定部３０２による処理とリンクサイクル抽出部３０３およびサイクル特性判定部３０４による処理を、順序を問わず非同期に並列に行い、両者の判定結果を総合することで仕様データの示すメカニズムが戦略的操作可能であるか戦略的操作不可能であるかの判定を行うようにしてもよい。
【００６６】
判定結果出力部３０５は、サイクル特性判定部３０４の出力した判定結果を、依頼元のユーザに応答出力する機能を有している。判定結果出力部３０５はユーザ端末２Ａ、２Ｂ、・・のブラウザ２１Ａ、２１Ｂ、・・に判定結果表示画面を表示し、判定結果の表示を行う。
【００６７】
図６はオークションメカニズム戦略的操作不可能性判定装置３のハードウェア構成例を示す図である。
【００６８】
図６において、オークションメカニズム戦略的操作不可能性判定装置３は、システムバス３００１に接続されたＣＰＵ３００２、ＲＯＭ３００３、ＲＡＭ３００４、ＮＶＲＡＭ（Non-Volatile Random Access Memory）３００５、Ｉ／Ｆ（Interface）３００６と、Ｉ／Ｆ３００６に接続された、キーボード、マウス、モニタ、ＣＤ／ＤＶＤ（Compact Disk/Digital Versatile Disk）ドライブ等のＩ／Ｏ（Input/Output Device）３００７、ＨＤＤ３００８、ＮＩＣ（Network Interface Card）３００９等を備えている。Ｍはプログラムもしくはデータが格納されたＣＤ／ＤＶＤ等のメディア（記録媒体）である。
【００６９】
＜動作＞
図７は上記の実施形態の処理例を示すフローチャートである。
【００７０】
図７において、処理を開始すると（ステップＳ１０１）、オークションメカニズム仕様入力部３０１により、オークションメカニズムの仕様を入力する（ステップＳ１０２）。
【００７１】
次いで、ノード内適用メカニズム判定部３０２により、ノード内適用メカニズムの判定を行う（ステップＳ１０３）。すなわち、ユーザにより入力された仕様データのノード内適用メカニズムについてメカニズムテーブルを参照し、全てのノード内適用メカニズムについて戦略的操作不可能性が満たされているか否かをチェックし、結果をリンクサイクル抽出部３０３に通知する。いずれか一つでも戦略的操作不可能性が満たされないノードがある場合、全体のオークションメカニズムについて戦略的操作不可能性が満たされない旨を判定結果出力部３０５にも通知する。
【００７２】
いずれか一つでも戦略的操作不可能性が満たされないノードがある場合（ステップＳ１０４のＹｅｓ）、後述する判定結果出力の処理（ステップＳ１０７）に移行する。なお、いずれか一つでも戦略的操作不可能性が満たされないノードがある場合においても、その後のリンクサイクル抽出部３０３およびサイクル特性判定部３０４による処理を行うようにすることができ、その場合は分岐処理（ステップＳ１０４）を設ける必要はない。
【００７３】
全てのノードで戦略的操作不可能性を満たす場合（ステップＳ１０４のＮｏ）、リンクサイクル抽出部３０３により、リンクサイクルを抽出する（ステップＳ１０５）。すなわち、ユーザにより入力された仕様データのノード間リンク情報の始点ノードと終点ノードに着目してリンクの接続関係を追跡し、一のノードから出発したリンクが同じノードに戻ってくるリンクサイクルが生じていないかどうかを判断し、リンクサイクルが存在する場合には、リンクサイクルを構成するリンク番号およびリンクタイプの対を複数並べたリンクサイクルデータを出力する。リンクの接続関係の追跡にあたっては、例えば、第１のノードに着目し、当該第１のノードを始点ノードとするリンクを検索する。存在すれば、続いてそのリンクの終点ノードを始点ノードとするリンクを検索し、存在すれば、そのリンクの終点ノードが第１のノードに一致するか否か判断する。一致すれば、サイクルが存在すると判断する。一致しない場合、同様に処理を繰り返し、リンクが検索されなくなった時点で終了する。
【００７４】
次いで、サイクル特性判定部３０４により、リンクサイクル抽出部３０３が出力したリンクサイクルデータに基づき、リンクタイプに着目して、高々１つの情報リンクを含むようなリンクサイクルが存在するか否かにより、戦略的操作可能であるか戦略的操作不可能であるかの判定を行う（ステップＳ１０６）。高々１つの情報リンクを含むようなリンクサイクルが一つでも存在する場合は戦略的操作可能であり、高々１つの情報リンクを含むようなリンクサイクルが一つも存在しない場合は戦略的操作不可能であるとの判定結果を判定結果出力部３０５に出力する。
【００７５】
次いで、判定結果出力部３０５により、サイクル特性判定部３０４の出力した判定結果を、依頼元のユーザに応答出力し（ステップＳ１０７）、処理を終了する（ステップＳ１０８）
図８は戦略的操作不可能性の判定例を示す図である。ここでは、我々が開発した再配分可能区分メカニズム（ＲＰＭ：Redistributable Partition Mechanism）と呼ぶメカニズムについて判定する場合を考える。なお、この再配分可能区分メカニズムによるオークションは次の手順により行う。
【００７６】
（１）同じ財（共有リソース）がＫ個存在し、入札者はｎ人とすると、分割数を例えば「２」として、入札者はｎ／２人ずつ、財はＫ／２ずつ、２つのグループＸ、Ｙに分割する。なお、分割数は「２」に限らないが「２」が望ましい。また、ｎ、Ｋは偶数となるように調整することで２つのグループでの入札者と財の数がそれぞれ同じとなるのが望ましいが、一方に余りが発生してもよい。
【００７７】
（２）グループＸで、入札者の財に対する需要の個数と落札可能な財の供給の個数が一致する閾値価格ｐＸを決定する。一致する価格が存在しなければ、需要＞供給を満たす最大価格を閾値価格ｐＸとして決定する。具体的には次のような手順で決定する。グループＹでも同様に閾値価格ｐＹを決定する。
【００７８】
（２−１）主催者が単位価格（unit price）をアナウンスする。
【００７９】
（２−２）入札者らは、アナウンスされた単位価格に応じて購入希望個数を申告する。
【００８０】
（２−３）入札者らの購入希望個数の和≦Ｋ／２になった時点で終了する。購入希望個数の和と供給数Ｋ／２が一致する場合はその時点で告知している単位価格をそのグループの閾値価格に決定し、そうでなければ、購入希望個数の和が供給数より低くなる直前の単位価格をそのグループの閾値価格に決定する。
【００８１】
（３）グループＸの閾値価格とグループＹの閾値価格を入れ替える。
【００８２】
（４）グループＸ、Ｙにおいて、それぞれの入札者をランダムに並べ替える。
【００８３】
（５）グループＸにおいて、並び順に入札者を選択し、入札者が閾値価格ｐＹで購入できる個数を申告する。
【００８４】
（６）購入された場合、その支払額は、グループＸの未選択の残りの入札者らに、事前に決定した方法（均等割りなど）で配分する。
【００８５】
（７）全ての財が販売されるまで入札者を選ぶ。
【００８６】
（８）最後の入札者に財が残っている場合は無料で与える。
【００８７】
（９）グループＹでも閾値価格ｐＸに基づいて、同様に処理を行う。
【００８８】
図８においては、簡単のため、グループＸの入札者をＡ、Ｂ、グループＹの入札者をＣ、Ｄのそれぞれ二人としている。図８の左側の第１階層ではグループＸ、Ｙ間に情報リンクｉが存在するだけでサイクルが存在するかどうかが分からないが、より下位の第２階層に展開して右側のようにすることで、複数のサイクルが存在することが分かる。ユーザは、この状態の仕様データをオークションメカニズム戦略的操作不可能性判定装置３に入力するものとする。なお、入札者Ａ、Ｂ、Ｃ、Ｄに対応するノードの区分では、アナウンスに対して希望購入個数を入力するだけであるため、各区分には戦略的操作不可能なメカニズムが適用されることになる。
【００８９】
この場合、Ａ→Ｂ→Ｃ、Ａ→Ｄ→Ｃ、Ｂ→Ｄ→Ｃ等の複数のサイクルが抽出されるが、いずれのサイクルにも情報リンクｉが２つあり、高々１つの情報リンクを含むようなサイクルが存在しないことになり、かつ、各区分では戦略的操作不可能なメカニズムが適用されるため、全体として戦略的操作不可能なメカニズムと判定される。
【００９０】
＜総括＞
以上説明したように、本実施形態によれば、予算制約がある状況での複数ユニットについての再配分を伴う使用権のオークションに対して、戦略的操作不可能性を満たすか否かを容易に判定することができる。
【００９１】
以上、本発明の好適な実施の形態により本発明を説明した。ここでは特定の具体例を示して本発明を説明したが、特許請求の範囲に定義された本発明の広範な趣旨および範囲から逸脱することなく、これら具体例に様々な修正および変更を加えることができることは明らかである。すなわち、具体例の詳細および添付の図面により本発明が限定されるものと解釈してはならない。
【符号の説明】
【００９２】
１                  ネットワーク
２Ａ、２Ｂ          ユーザ端末
２１Ａ、２１Ｂ      ブラウザ
３                  オークションメカニズム戦略的操作不可能性判定装置
３０１              オークションメカニズム仕様入力部
３０２              ノード内適用メカニズム判定部
３０３              リンクサイクル抽出部
３０４              サイクル特性判定部
３０５              判定結果出力部
３０６              データ格納部
【図１】
0005456559.tif 000002
【図２】
0005456559.tif 000003
【図３】
0005456559.tif 000004
【図４】
0005456559.tif 000005
【図５】
0005456559.tif 000006
【図６】
0005456559.tif 000007
【図７】
0005456559.tif 000008
【図８】
0005456559.tif 000009