(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）と呼ばれる。予算制約を持つ入札者の効用は準線形効用では表現できない。このような予算制約は現実的な選好の典型的な例の一つである。例えば、複数の町が複数の健康診断車両の使用権をオークションで決定する状況など、公共設備の使用権の割り当てなどが想定される。公共設備の使用権は住民のニーズが高いとき、非常に高い価値を持つかもしれない。しかしながら、その一方で予算上の制約があることが予想される。従って，再配分メカニズムにおいて、入札者が予算制約を持つ場合のメカニズムを設計することは実用上有益であると考える。
【００１３】
しかしながら、上述したＣａｖａｌｌｏメカニズムやＦａｌｔｉｎｇｓメカニズムや区分メカニズムは、予算制約がある状況での複数ユニットについての再配分を伴う使用権のオークションに対し戦略的操作不可能性を満たさない。
【００１４】
以下、既存の再配分メカニズムについて、予算制約付き入札者が存在した場合の影響を示す。なお、財ひとつ分の評価値は入札者ｉのみが観察できるシグナルであるタイプとしてθｉと標記し、入札者ｉが財をｋ個だけ得た時の財に対する評価値（グロス効用）をｖ（θｉ，ｋ）と標記する。支払額ｐがある場合の効用はｕ（θｉ，ｋ，ｐ）となり、ｐがゼロの場合の効用がグロス効用ｖ（θｉ，ｋ）である。
【００１５】
Ｃａｖａｌｌｏメカニズムでは、単一財の場合においても、予算制約付き入札者が存在した場合、戦略的操作不可能性を満たさない。以下、例を用いて示す。
【００１６】
先ず、予算制約を考慮せずにｖ（θｉ，１）に基づいてＣａｖａｌｌｏメカニズムを適用した場合、戦略的操作不可能性を満たさないことを示す。
【００１７】
３人の入札者が存在するとする。各入札者のグロス効用ｖ（θｉ，１）と予算ｂｉの組み合せ（ｖ（θｉ，１），ｂｉ）を申告する。入札者＃１は（１０，４）、入札者＃２は（５，５）、入札者＃３は（１，１）を入札するとする。このとき、入札者＃１が財を得ることになる。「５」を支払い、「１／３」を再配分額として受け取ることができるが、最終的な支払額は「１４／３」となり、予算「４」を超えてしまう。従って、財を得ることができない。
【００１８】
ここで、入札者＃２が（３，５）というように評価値を低く入札すれば、入札者＃１の最終的な支払額は「３−１／３＝８／３」となり、支払うことができるため、入札者＃２も再配分額「１／３」を得ることができる。
【００１９】
次に、予算制約を考慮してｍｉｎ（ｖ（θｉ，１），ｂｉ）に基づいてＣａｖａｌｌｏメカニズムを適用しても戦略的操作不可能性を満たさないことを示す。
【００２０】
上記の例と同様の状況を考える。入札者＃１は（１０，４）、入札者＃２は（５，５）、入札者＃３は（３，３）を入札するとする。
【００２１】
このとき、入札者＃２が財を得ることができる。しかしながら、入札者＃１が予算を「６」と過大申告すれば、入札者＃１に財を割り当てられ、支払額も「５−１＝４」となるため、支払うことができる。
【００２２】
次に、Ｆａｌｔｉｎｇｓメカニズムについて説明する。Ｆａｌｔｉｎｇｓメカニズムは、単一財の場合と限界効用が逓減する場合は、予算制約付き入札者が存在したときでもｍｉｎ（ｖｉ（１），ｂｉ）に基づいて割り当てを決定すれば、戦略的操作不可能性を満たす。しかしながら、非特許文献４で示されているが、限界効用が逓増する場合はＶＣＧメカニズムが戦略的操作不可能性を満たさないため、戦略的操作不可能性を満たすことができない。
【００２３】
以下、ＶＣＧメカニズムが戦略的操作不可能性を満たさない例を示す。この例では、各入札者は単一の単位価格で構成されるとする。
【００２４】
２ユニットの財のオークションに二人の入札者が参加しているとする。入札者＃１の真のグロス効用と予算を（ｖ（θ１，１），ｂ１）＝（１０，１０）、入札者＃２は（ｖ（θ２，１），ｂ２）＝（３，５）とする。ｖ（θｉ，２）＝２ｖ（θｉ，１）とする。このとき、ＶＣＧメカニズムを（ｖ'（θｉ，１），ｖ'（θｉ，２））＝（ｍｉｎ（ｖ（θｉ，１），ｂｉ），ｍｉｎ（２ｖ（θｉ，１），ｂｉ））の値（評価ベクトル）に適用する。これは支払額が予算以下になることを保証するためである。
【００２５】
入札者＃１と入札者＃２の評価ベクトルはそれぞれ、（１０，１０）と（３，５）になる。従って、入札者＃１と入札者＃２に１ユニットずつ割り当てるのが最適となる。結果、入札者＃１の支払額は「５−３＝２」、入札者＃２の支払額は「１０−１０＝０」となる。よって、入札者＃１の効用は「１０−２＝８」となる。
【００２６】
さて、入札者＃１がグロス効用を過少申告して（ｖ（θ１，１），ｂ１）＝（５，１０）としたとき、支払額「５−０＝５」で２ユニット得ることができる。結果、入札者＃１の効用は「２０−５＝１５」となり、過少申告によって効用を増加させることが可能である。
【００２７】
一方、近年、再配分を伴わない一般のオークションに対して、戦略的操作不可能性を満たすメカニズムがいくつか提案されている。例えば、非特許文献４では、区分メカニズムのアイデアと同様に入札者と財を二つの区分に分け、片方の区分の入札額を用いて、もう一方の区分での販売価格を決定することにより、予算制約下で適切な価格を決定する方法を提案している。ここでは、このメカニズムをＢｏｒｇｓメカニズムと呼ぶ。
【００２８】
しかしながら、このＢｏｒｇｓメカニズムであっても、予算制約がある状況での複数ユニットについての再配分を伴う使用権のオークションに対しては、戦略的操作不可能性を満たさない。
【００２９】
以下、Ｂｏｒｇｓメカニズムが戦略的操作不可能性を満たさない例を示す。ＡとＢの２つのグループに分割し、Ａの価格ｐＢはＢの入札者らによって決定される。従って、Ａで集まった支払額をＢで再配分することで強予算均衡を満たすことができるが、Ｂの入札者らには自分の入札額が再配分額に直接影響するため、過大申告することで再配分額を増やすことができる。従って、支払額の再配分を行う場合、Ｂｏｒｇｓメカニズムでは戦略的操作不可能性を満たさない。
【００３０】
我々の知る限り、入札者が予算制約を持つ場合を対象とした、戦略的操作不可能な再配分メカニズムの提案は行われていない。
【００３１】
本発明は上記の従来の問題点に鑑み提案されたものであり、その目的とするところは、予算制約がある状況での複数ユニットについての再配分を伴う使用権のオークションに対して戦略的操作不可能性を満たすことのできる電子オークション装置を提供することにある。
【課題を解決するための手段】
【００３２】
上記の課題を解決するため、本発明にあっては、請求項１に記載されるように、複数人が複数の所定の財を共有し、当該複数の財の使用権の取得を決定する電子オークション装置であって、予め登録された複数の入札者および財を複数のグループに均等に分割するグループ分割手段と、分割された各グループにおいて入札者の財に対する購入希望個数の和である需要の個数と落札可能な財の供給の個数が一致する単位価格、もしくは需要の個数が供給の個数以下となる直前の最大の単位価格を閾値価格として決定する第１の入札処理手段と、決定された前記閾値価格をグループ間で入れ替えて販売価格とし、グループ内の入札者をランダムな順序で選択し、当該入札者に前記販売価格を告知し、当該入札者から申告された購入希望個数の財を落札させる第２の入札処理手段と、落札した財の個数と販売価格を乗じた支払額から、選択されていない入札者への再配分額を計算する計算手段とを備える電子オークション装置を要旨としている。
【００３３】
また、請求項２に記載されるように、請求項１に記載の電子オークション装置において、前記第２の入札処理手段は、財に残りがあり、かつ、選択されていない残りの入札者が一人の場合、当該入札者に無料で財を割り当てるようにすることができる。
【００３４】
また、請求項３に記載されるように、請求項１または２のいずれか一項に記載の電子オークション装置において、前記第１および第２の入札処理手段は、入札者に対して所属するグループの情報を伝達しないようにすることができる。
【００３５】
また、請求項４に記載されるように、複数人が複数の所定の財を共有し、当該複数の財の使用権の取得を決定する電子オークション装置の制御方法であって、予め登録された複数の入札者および財を複数のグループに均等に分割するグループ分割工程と、分割された各グループにおいて入札者の財に対する購入希望個数の和である需要の個数と落札可能な財の供給の個数が一致する単位価格、もしくは需要の個数が供給の個数以下となる直前の最大の単位価格を閾値価格として決定する第１の入札処理工程と、決定された前記閾値価格をグループ間で入れ替えて販売価格とし、グループ内の入札者をランダムな順序で選択し、当該入札者に前記販売価格を告知し、当該入札者から申告された購入希望個数の財を落札させる第２の入札処理工程と、落札した財の個数と販売価格を乗じた支払額から、選択されていない入札者への再配分額を計算する計算工程とを備える電子オークション制御方法として構成することができる。
【発明の効果】
【００３６】
本発明の電子オークション装置にあっては、予算制約がある状況での複数ユニットについての再配分を伴う使用権のオークションに対して戦略的操作不可能性を満たすことができる。また、全ての支払額が入札者らに再配分され、支払額がオークション運営者側に残ることがなく、強予算均衡も図ることができる。
【図面の簡単な説明】
【００３７】
【図１】再配分可能区分メカニズムの区分間のリンクの例を示す図である。
【図２】本発明の一実施形態にかかるシステムの構成例を示す図である。
【図３】電子オークション装置のハードウェア構成例を示す図である。
【図４】実施形態におけるオークションの処理例を示すフローチャート（その１）である。
【図５】実施形態におけるオークションの処理例を示すフローチャート（その２）である。
【図６】実施形態における閾値価格の決定の例を示す図（その１）である。
【図７】実施形態における閾値価格の決定の例を示す図（その２）である。
【図８】実施形態における落札の例を示す図である。
【発明を実施するための形態】
【００３８】
以下、本発明の好適な実施形態につき説明する。
【００３９】
＜原理＞
本実施形態によるメカニズムを再配分可能区分メカニズム（ＲＰＭ：Redistributable Partition Mechanism）と呼ぶこととする。
【００４０】
本実施形態によるオークションは次の手順により行う。
【００４１】
（１）同じ財（共有リソース）がＫ個存在し、入札者はｎ人とすると、分割数を例えば「２」として、入札者はｎ／２人ずつ、財はＫ／２ずつ、２つのグループＸ、Ｙに分割する。なお、分割数は「２」に限らないが「２」が望ましい。また、ｎ、Ｋは偶数となるように調整することで２つのグループでの入札者と財の数がそれぞれ同じとなるのが望ましいが、一方に余りが発生してもよい。
【００４２】
（２）グループＸで、入札者の財に対する需要の個数と落札可能な財の供給の個数が一致する閾値価格ｐＸを決定する。一致する価格が存在しなければ、需要＞供給を満たす最大価格を閾値価格ｐＸとして決定する。具体的には次のような手順で決定する。グループＹでも同様に閾値価格ｐＹを決定する。
【００４３】
（２−１）主催者が単位価格（unit price）をアナウンスする。
【００４４】
（２−２）入札者らは、アナウンスされた単位価格に応じて購入希望個数を申告する。
【００４５】
（２−３）入札者らの購入希望個数の和≦Ｋ／２になった時点で終了する。購入希望個数の和と供給数Ｋ／２が一致する場合はその時点で告知している単位価格をそのグループの閾値価格に決定し、そうでなければ、購入希望個数の和が供給数より低くなる直前の単位価格をそのグループの閾値価格に決定する。
【００４６】
（３）グループＸの閾値価格とグループＹの閾値価格を入れ替える。
【００４７】
（４）グループＸ、Ｙにおいて、それぞれの入札者をランダムに並べ替える。
【００４８】
（５）グループＸにおいて、並び順に入札者を選択し、入札者が閾値価格ｐＹで購入できる個数を申告する。
【００４９】
（６）購入された場合、その支払額は、グループＸの未選択の残りの入札者らに、事前に決定した方法（均等割りなど）で配分する。
【００５０】
（７）全ての財が販売されるまで入札者を選ぶ。
【００５１】
（８）最後の入札者に財が残っている場合は無料で与える。
【００５２】
（９）グループＹでも閾値価格ｐＸに基づいて、同様に処理を行う。
【００５３】
次に、このメカニズムが戦略的操作不可能性を満たすことを示す。
【００５４】
オークションメカニズムの処理の区分となるノードにつき、区分間に存在する、入札者に関する情報、再配分、売れ残った財の流れにそれぞれ対応する情報リンク（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）やＲＡＭ等の記憶媒体により構成される。
【００６２】
ユーザ登録部３０１は、電子オークション装置３を利用するユーザの登録を行う機能を有している。ユーザ登録部３０１はユーザ端末２Ａ、２Ｂ、・・のブラウザ２１Ａ、２１Ｂ、・・にユーザ登録画面を表示し、所定の項目を選択あるいは入力させることによりユーザ登録の手続を行う。ユーザ登録データ（ユーザＩＤ、氏名、連絡先、パスワード等）はデータ格納部３１３に格納される。
【００６３】
オークション対象登録部３０２は、オークションの対象となる複数ユニットの共有リソースの登録を行う機能を有している。オークション対象登録部３０２はユーザ端末２Ａ、２Ｂ、・・のブラウザ２１Ａ、２１Ｂ、・・にオークション対象登録画面を表示し、所定の項目を選択あるいは入力させることにより登録の手続を行う。共有リソース登録データ（共有リソースＩＤ、共有リソース名称、供給個数、共有者ユーザＩＤ、タイプ等）はデータ格納部３１３に格納される。
【００６４】
利用申込受付部３０３は、共有リソースの利用申込を受け付ける機能を有している。利用申込受付部３０３はユーザ端末２Ａ、２Ｂ、・・のブラウザ２１Ａ、２１Ｂ、・・に利用申込受付画面を表示し、所定の項目を選択あるいは入力させることにより利用申込受付の手続を行う。利用申込データ（共有リソースＩＤ、ユーザＩＤ、利用個数、利用希望日時等）はデータ格納部３１３に格納される。
【００６５】
オークション要否決定部３０４は、共有リソース毎に利用申込データの利用希望日時の重複があるか否かをチェックすることにより、オークションによる決定が必要であるか否かを決定する機能を有している。
【００６６】
グループ分割部３０５は、オークション要否決定部３０４がオークションによる決定が必要であると決定した場合に、入札者と共有リソースを複数（例えば２つ）のグループにそれぞれ均等に分割する機能を有している。入札者数もしくは共有リソースの供給数が奇数となる場合は、予め偶数となるように調整するか、余りをいずれかのグループに入れる。分割されたグループを特定するグループＩＤと各グループに属する入札者ＩＤ群と各グループの共有リソースの供給数のデータはデータ格納部３１３に格納される。
【００６７】
入札受付部３０６は、オークションの開始により、分割されたグループ毎に閾値価格を決定するための競り上げ方式による入札、すなわち低めの単位価格からグループ内の入札者に告知を開始し、その単位価格に対する購入希望個数の入札を受け付ける機能を有している。この際、入札者同士の結託を防止するため、各入札者に対して各自が所属するグループの情報を伝えないものとする。入札受付部３０６は、単位価格の告知に対し、各入札者から高々１回の入札を受け付けることにより入札の受付を終了する。入札受付部３０６はユーザ端末２Ａ、２Ｂ、・・のブラウザ２１Ａ、２１Ｂ、・・に入札受付画面を表示し、所定の項目を選択あるいは入力させることにより入札受付の手続を行う。具体的には、一例として、単位価格の告知はユーザ端末２Ａ、２Ｂ、・・のブラウザ２１Ａ、２１Ｂ、・・の画面上に単位価格を表示することにより行えばよい。また、入札受付は、ユーザ端末２Ａ、２Ｂ、・・のブラウザ２１Ａ、２１Ｂ、・・から単位価格での購入希望個数の入力受付を行うようにすればよい。各グループのグループＩＤと告知する単位価格のデータと、入札内容を示す入札者ＩＤと購入希望個数のデータはデータ格納部３１３に格納される。
【００６８】
なお、入札受付部３０６では、終了条件を満たすまで競り上げ方式により単位価格を上げていき、その都度に入札者から購入希望個数の入札を受け付ける場合について例示しているが、入札者全員から購入可能な上限価格と購入希望個数をいっせいに入札するようにしてもよい。この場合、個人情報である予算内容がオークション運営者側に伝わってしまうというデメリットがあるが、競り上げを必要としないため、運営を簡略かつ迅速に行うことができるというメリットがある。
【００６９】
閾値価格決定部３０７は、各入札者からの購入希望個数の和（需要）が供給数（供給）以下となった場合に、購入希望個数の和と供給数が一致する場合はその時点で告知している単位価格をそのグループの閾値価格に設定し、そうでなければ、購入希望個数の和が供給数より低くなる直前の単位価格（最大の単位価格）をそのグループの閾値価格に設定する機能を有している。各グループのグループＩＤと最終的に決定された閾値価格のデータはデータ格納部３１３に格納される。
【００７０】
閾値価格入替部３０８は、グループ毎に最終的に決定された閾値価格をグループ間で入れ替えて販売価格とする機能を有している。グループが２つの場合は互いの閾値価格を入れ替えて販売価格とする。グループＩＤと閾値価格のデータを実際に入れ替えてもいいし、入れ替えは概念上だけとして、後の処理において入れ替え先のグループの閾値価格を参照するようにしてもよい。
【００７１】
入札者ランダム並べ替え部３０９は、各グループの入札者をランダムに並べ替える機能を有している。並べ替えた後の入札者ＩＤ列のデータはデータ格納部３１３に格納される。
【００７２】
入札受付部３１０は、分割されたグループ毎に、並べ替えられた入札者の並び順に、全ての共有リソースが落札されるまで、販売価格（既に決定されて入れ替えられた他のグループの閾値価格）に基づく購入希望個数の入札を受け付ける機能を有している。入札受付部３１０はユーザ端末２Ａ、２Ｂ、・・のブラウザ２１Ａ、２１Ｂ、・・に入札受付画面を表示し、所定の項目を選択あるいは入力させることにより入札受付の手続を行う。具体的には、一例として、販売価格をユーザ端末２Ａ、２Ｂ、・・のブラウザ２１Ａ、２１Ｂ、・・の画面上に表示し、ユーザ端末２Ａ、２Ｂ、・・のブラウザ２１Ａ、２１Ｂ、・・から購入希望個数の入力受付を行うようにすればよい。この際、入札者同士の結託を防止するため、各入札者に対して各自が所属するグループの情報を伝えないものとする。再配分額は、共有リソースの落札が行われた場合に支払額計算部３１２により計算される。入札内容を示す入札者ＩＤと購入希望個数のデータはデータ格納部３１３に格納される。
【００７３】
落札者決定部３１１は、入札受付部３１０での入札者の購入希望個数が１以上である場合に、当該入札者を落札者とする機能を有している。また、全ての共有リソースが落札されておらず、すなわち共有リソースに残りがあり、各グループ内で選択されていない残りの入札者が一人である場合、その入札者に無料で残りの共有リソースを割り当てる機能を有している。落札内容を示す落札者ＩＤと落札個数のデータはデータ格納部３１３に格納される。
【００７４】
支払額計算部３１２は、落札者を含む各入札者について、支払額と再配分額（支給される金額でありマイナスの値）を含む支払額を計算する機能を有している。再配分額は、各グループにおいて、まだ選択されていない入札者に等分に割り当てられる。入札者ＩＤと支払額のデータはデータ格納部３１３に格納される。
【００７５】
図３は電子オークション装置３のハードウェア構成例を示す図である。
【００７６】
図３において、電子オークション装置３は、システムバス３００１に接続されたＣＰＵ３００２、ＲＯＭ３００３、ＲＡＭ３００４、ＮＶＲＡＭ（Non-Volatile Random Access Memory）３００５、Ｉ／Ｆ（Interface）３００６と、Ｉ／Ｆ３００６に接続された、キーボード、マウス、モニタ、ＣＤ／ＤＶＤ（Compact Disk/Digital Versatile Disk）ドライブ等のＩ／Ｏ（Input/Output Device）３００７、ＨＤＤ３００８、ＮＩＣ（Network Interface Card）３００９等を備えている。Ｍはプログラムもしくはデータが格納されたＣＤ／ＤＶＤ等のメディア（記録媒体）である。
【００７７】
＜動作＞
図２において、電子オークション装置３は、ユーザ登録部３０１によりユーザ登録が行われ、オークション対象登録部３０２によりオークション対象の共有リソースの登録が行われ、利用申込受付部３０３により利用申込の受付が行われた後、オークション要否決定部３０４により利用時間帯等の競合によりオークションによる決定が必要であると決定されたものとする。
【００７８】
図４および図５は上記の実施形態におけるオークションの処理例を示すフローチャートである。なお、入札者と共有リソースを２つのグループＸ、Ｙに分割するものとしている。
【００７９】
図４において、処理を開始すると（ステップＳ１０１）、グループ分割部３０５により、入札者と共有リソースをグループＸ、Ｙにそれぞれ分割する（ステップＳ１０２）。
【００８０】
次いで、グループＸ、Ｙのそれぞれにおいて並行してそれぞれ閾値価格ｐＸ、ｐＹを決定する処理を行う。
【００８１】
ここでは、グループＸについて説明する。
【００８２】
先ず、入札受付部３０６により、グループＸの入札者へ単位価格の告知を行い（ステップＳ１０３）、入札者からの購入希望個数の受付を行う（ステップＳ１０４）。
【００８３】
次いで、閾値価格決定部３０７により、購入希望個数の和（需要）が共有リソースの供給数（供給）以下であるか否か判断する（ステップＳ１０５）。購入希望個数の和（需要）が共有リソースの供給数（供給）以下でない場合（ステップＳ１０５のＮｏ）、単位価格の告知（ステップＳ１０３）に戻る。次回からの単位価格は所定の幅で増額したものとなる。
【００８４】
購入希望個数の和（需要）が共有リソースの供給数（供給）以下である場合（ステップＳ１０５のＹｅｓ）、閾値価格決定部３０７により、購入希望個数の和（需要）と供給数（供給）が一致する場合はその時点の単位価格を閾値価格ｐＸに設定し、そうでなければ、購入希望個数の和が供給数より低くなる直前の単位価格（最大の単位価格）を閾値価格ｐＸに設定する（ステップＳ１０６）。
【００８５】
グループＹについても同様の処理を行う（ステップＳ１０７〜Ｓ１１０）。
【００８６】
次いで、図５において、閾値価格入替部３０８により、グループＸ、Ｙ間での閾値価格の入替を行い、それぞれのグループＸ、Ｙでの販売価格とする（ステップＳ１１１）。すなわち、グループＹでの閾値価格ｐＹをグループＸでの販売価格とし、グループＸでの閾値価格ｐＸをグループＹでの販売価格とする。
【００８７】
次いで、グループＸ、Ｙのそれぞれにおいて並行してそれぞれ落札のための処理を行う。
【００８８】
ここでは、グループＸについて説明する。
【００８９】
先ず、入札者ランダム並べ替え部３０９により、グループＸ内の入札者のランダムな並べ替えを行う（ステップＳ１１２）。
【００９０】
次いで、入札受付部３１０により、並び順に入札者を一人選択し（ステップＳ１１３）、販売価格ｐＹでの購入希望個数の受付を行う（ステップＳ１１４）。入札者は、今までの再配分額を考慮し、購入希望個数を申告する。
【００９１】
次いで、落札者決定部３１１により、購入希望個数が１以上であるか否か判断する（ステップＳ１１５）。
【００９２】
購入希望個数が１以上である場合（ステップＳ１１５のＹｅｓ）、落札者決定部３１１により、その入札者に購入希望個数の共有リソースが落札されたものとし、支払額計算部３１２により支払額の再配分額を計算する（ステップＳ１１６）。落札者からの支払額（販売価格に落札個数を乗じた値）は、グループＸにおいてまだ選択されていない入札者に対し、再配分額として等分に割り当てられる。
【００９３】
なお、落札の都度に落札者からの支払額を再配分する場合について例示しているが、共有リソースが全て落札あるいは割り当てられた後に、選択されていない入札者に販売価格の合計を再配分するようにしてもよい。ただし、落札の都度に再配分する場合の方が、再配分額が入札者の予算額を緩和していくことになるため、共有リソースのはけやすさという観点では優れている。
【００９４】
次いで、落札者決定部３１１により、共有リソースが全て落札されたか否か判断し（ステップＳ１１７）、共有リソースが全て落札された場合（ステップＳ１１７のＹｅｓ）は処理を終了する（ステップＳ１２８）。
【００９５】
共有リソースが全て落札されていない場合（ステップＳ１１７のＮｏ）、落札者決定部３１１により、続いて残りの入札者が一人であるか否か判断する（ステップＳ１１８）。
【００９６】
残りの入札者が一人でない場合（ステップＳ１１８のＮｏ）、入札者の選択（ステップＳ１１３）に戻る。
【００９７】
残りの入札者が一人である場合（ステップＳ１１８のＹｅｓ）、落札者決定部３１１により、残りの入札者に無料で共有リソースの割り当てを行う（ステップＳ１１９）。
【００９８】
グループＹについても同様の処理を行う（ステップＳ１２０〜Ｓ１２７）。
【００９９】
次に、具体的なオークションの流れにつき、図６〜図８に基づいて説明する。なお、グループはＸ、Ｙの２つに分割し、入札者はそれぞれ２人の計４人、共有リソースはそれぞれ１個の計２個とする。また、入札者＃１の共有リソースに対する評価値は「＄１００」、予算は「＄３０」、入札者＃２の共有リソースに対する評価値は「＄８０」、予算は「＄４０」、入札者＃３の共有リソースに対する評価値は「＄７０」、予算は「＄４５」、入札者＃４の共有リソースに対する評価値は「＄８０」、予算は「＄３５」であるとする。これらの評価値や予算は、各入札者の内心に留められたものであり、システムに直接に入力される必要はないが、購入希望個数の申告という形で間接的にシステムに伝えられる。
【０１００】
図６において、グループＸでアナウンスされる単位価格が「＄２０」であるとすると、入札者＃１、＃２とも予算以下であるため、両者とも購入希望個数「１」を申告する。従って、購入希望個数の和は「２」となり、供給数「１」よりも大きいため、入札終了の条件を満たさない。同様に、グループＹでアナウンスされる単位価格も「＄２０」であるとすると、入札者＃３、＃４とも予算以下であるため、両者とも購入希望個数「１」を申告する。従って、購入希望個数の和は「２」となり、供給数「１」よりも大きいため、入札終了の条件を満たさない。従って、グループＸ、Ｙでアナウンスされる単位価格が競り上がっていく。
【０１０１】
図７において、グループＸでアナウンスされる単位価格が「＄３１」になると、入札者＃１は予算「＄３０」を超えてしまうため、購入希望個数は「０」となる。入札者＃２は予算「＄４０」以下であるため、購入希望個数は「１」となる。従って、購入希望個数の和は「１」となり、供給数「１」と一致し、入札終了の条件を満たす。この場合、その時点の単位価格「＄３１」がグループＸでの閾値価格となる。
【０１０２】
同様に、グループＹでアナウンスされる単位価格が「＄３６」になると、入札者＃３は予算「＄４５」以下であるため、購入希望個数は「１」となる。入札者＃４は予算「＄３５」を超えてしまうため、購入希望個数は「０」となる。従って、購入希望個数の和は「１」となり、供給数「１」と一致し、入札終了の条件を満たす。この場合、その時点の単位価格「＄３６」がグループＹでの閾値価格となる。
【０１０３】
続いて、図８において、グループＸとグループＹとで閾値価格を入れ替えて互いの販売価格とする。すなわち、グループＸでの販売価格を「＄３６」、グループＹでの販売価格を「＄３１」とする。
【０１０４】
グループＸにおいて、ランダムに並べ替えた順に、例えば入札者＃２が最初に選択されたとすると、販売価格「＄３６」に対して入札者＃２は予算「＄４０」以下であるため、購入希望個数は「１」となる。従って、共有リソースは入札者＃２に落札され、入札者＃２からの支払額「＄３６」がまだ選択されていない入札者＃１に再配分され、グループＸでの処理を終了する。
【０１０５】
同様に、グループＹにおいて、ランダムに並べ替えた順に、例えば入札者＃３が最初に選択されたとすると、販売価格「＄３１」に対して入札者＃３は予算「＄４５」以下であるため、購入希望個数は「１」となる。従って、共有リソースは入札者＃３に落札され、入札者＃３からの支払額「＄３１」がまだ選択されていない入札者＃４に再配分され、グループＹでの処理を終了する。
【０１０６】
＜総括＞
以上説明したように、本実施形態によれば、次のような利点がある。
（１）予算制約がある状況での複数ユニットについての再配分を伴う使用権のオークションに対して戦略的操作不可能性を満たすことができる。
（２）全ての支払額が入札者らに再配分され、支払額がオークション運営者側に残ることがなく、強予算均衡も図ることができる。
（３）残った財を最後の入札者に無料で割り当てることで、財が落札されずに残ることを防止することができる。
（４）入札者に対して所属するグループの情報を伝達しないことで、入札者同士の結託を防止することができる。
【０１０７】
以上、本発明の好適な実施の形態により本発明を説明した。ここでは特定の具体例を示して本発明を説明したが、特許請求の範囲に定義された本発明の広範な趣旨および範囲から逸脱することなく、これら具体例に様々な修正および変更を加えることができることは明らかである。すなわち、具体例の詳細および添付の図面により本発明が限定されるものと解釈してはならない。
【符号の説明】
【０１０８】
１                  ネットワーク
２Ａ、２Ｂ          ユーザ端末
２１Ａ、２１Ｂ      ブラウザ
３                  電子オークション装置
３０１              ユーザ登録部
３０２              オークション対象登録部
３０３              利用申込受付部
３０４              オークション要否決定部
３０５              グループ分割部
３０６              入札受付部
３０７              閾値価格決定部
３０８              閾値価格入替部
３０９              入札者ランダム並べ替え部
３１０              入札受付部
３１１              落札者決定部
３１２              支払額計算部
３１３              データ格納部
【図１】
0005456558.tif 000002
【図２】
0005456558.tif 000003
【図３】
0005456558.tif 000004
【図４】
0005456558.tif 000005
【図５】
0005456558.tif 000006
【図６】
0005456558.tif 000007
【図７】
0005456558.tif 000008
【図８】
0005456558.tif 000009