(57)【要約】【課題】架空名義入札に対して頑健な再配分アルゴリズムを備えた電子オークション装置を提供する。【解決手段】複数人が所定の財を共有し、当該財の使用権の取得を決定する電子オークション装置であって、前記財の共有者である入札者および前記財の入札額を特定した入札を受け付ける入札受付手段と、入札者数および初期留保価格に基づいて前記財を落札できる権利が得られる最低入札額である留保価格を計算する留保価格計算手段と、入札者数および初期留保価格に基づいて特定の入札者に配分する再配分額を計算する再配分額計算手段と、留保価格以上であって最も高い入札額の入札者を前記財の使用権の落札者として決定する落札者決定手段と、各入札者の支払額を落札額と再配分額に基づいて計算する支払額計算手段とを備える。【選択図】図８
2011113201.tif 000002
【特許請求の範囲】
【請求項１】
複数人が所定の財を共有し、当該財の使用権の取得を決定する電子オークション装置であって、
前記財の共有者である入札者および前記財の入札額を特定した入札を受け付ける入札受付手段と、
入札者数および初期留保価格に基づいて前記財を落札できる権利が得られる最低入札額である留保価格を計算する留保価格計算手段と、
入札者数および初期留保価格に基づいて特定の入札者に配分する再配分額を計算する再配分額計算手段と、
留保価格以上であって最も高い入札額の入札者を前記財の使用権の落札者として決定する落札者決定手段と、
各入札者の支払額を落札額と再配分額に基づいて計算する支払額計算手段と
を備えたことを特徴とする電子オークション装置。
【請求項２】
請求項１に記載の電子オークション装置において、
前記支払額計算手段は、２番目に高い入札額と留保価格の高い方を落札者の落札額とする
ことを特徴とする電子オークション装置。
【請求項３】
請求項１または２のいずれか一項に記載の電子オークション装置において、
前記支払額計算手段は、各入札者につき他の入札者で留保価格以上の入札者が存在する場合に負の再配分額を支払額に含める
ことを特徴とする電子オークション装置。
【請求項４】
複数人が所定の財を共有し、当該財の使用権の取得を決定する電子オークション装置の制御方法であって、
前記財の共有者である入札者および前記財の入札額を特定した入札を受け付ける入札受付工程と、
入札者数および初期留保価格に基づいて前記財を落札できる権利が得られる最低入札額である留保価格を計算する留保価格計算工程と、
入札者数および初期留保価格に基づいて特定の入札者に配分する再配分額を計算する再配分額計算工程と、
留保価格以上であって最も高い入札額の入札者を前記財の使用権の落札者として決定する落札者決定工程と、
各入札者の支払額を落札額と再配分額に基づいて計算する支払額計算工程と
を備えたことを特徴とする電子オークション制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子的にオークションを実行する技術に関する。
【背景技術】
【０００２】
インターネットオークションは、多数の企業や消費者による様々な財（リソース）の取引に利用されており、電子商取引の主要な一分野となっている。また、インターネットオークションは、エージェント技術の有望な適用領域として人工知能やマルチエージェントシステムなどの研究分野で活発に研究が行われている。
【０００３】
一般的なオークションでは、財を販売する売手が存在しているため、落札者から集めた支払額は売手に与えられる。しかしながら、複数人が共有する財の使用権を決定するようなオークションでは、オークションの対象の財が共同所有であるため、売手に値する者が存在せず、集めた支払額をどうするかが問題となる。例えば、共同で車を所有し、週末に誰がその車を使用するかを決定するためにオークションを行うような場合である。
【０００４】
このように、オークションの落札者と支払額を割り当てるだけでなく、支払額の配分も決定するメカニズムを再配分メカニズムと呼ぶ。再配分メカニズムの設計は、最近、メカニズムデザインの研究において注目されている研究トピックスである。
【０００５】
再配分メカニズムの望ましい性質としては、
・戦略的操作不可能性（strategy-proofness）
・個人合理性（individual rationality）
・パレート効率性（Pareto efficiency）
・非損失（non-deficit）
・強予算均衡（strongly budget balance）
等が挙げられている。
【０００６】
これらの性質について説明する前に、「効用」について説明する。なお、オークションメカニズムは、単一財や組み合せオークションなど様々な状況を対象可能であるが、ここでは財が１つの単一財を対象とする。また、一般的なオークション理論の研究では、理論的な解析の簡単化のため、入札者に関して、財に対する評価値は個人価値であり、効用は準線形効用で表現されると仮定している。ここでもこの仮定を適用する。
【０００７】
入札者の評価値が個人価値であるとは、各入札者は自身の評価値を十分に知っており、他の入札者の評価値に依存せずに決定されることである。入札者ｉの準線形効用は得られた財に対する真の評価値ｖｉと支払額ｐｉの差分ｖｉ−ｐｉで求められる。一方、再配分メカニズムでは再配分額ｐ'ｉを考慮する必要があり、財が割り当てられた場合の効用はｖｉ−（ｐｉ−ｐ'ｉ）  となる。財が割り当てられず、再配分のみを受け取った場合、効用は０−（０−ｐ'ｉ）＝ｐ'ｉとなり、再配分額と一致する。
【０００８】
前述した戦略的操作不可能性につき、再配分オークションメカニズムが支配戦略（効用を最大化する戦略）において戦略的操作不可能的であるとは、各入札者にとって、真の評価値を申告することが支配戦略、すなわち他の入札者の行動に関わらず最適な戦略となることである。
【０００９】
個人合理性は、各入札者が支配戦略を用いた場合、オークションに参加したことにより、参加しない場合と比較して効用が減少することがないことである。
【００１０】
パレート効率性につき、パレート効率的な再配分メカニズムでは、全ての参加者の効用の和、すなわち、社会的余剰が最大化される割り当てを実現する。入札者は金銭により効用を譲渡でき、入札者の効用は準線形であると仮定する場合、パレート効率的な割り当てでは社会的余剰は常に最大化される。
【００１１】
非損失は、再配分額の総和が支払額の総和を超えることはない、すなわち、再配分額が足りなくなることはないことを示す。
【００１２】
強予算均衡は、再配分額の総和が支払額の総和と一致することを意味する。より弱い条件として，再配分額の総和が支払額の総和を超えることはない、すなわち、再配分額が足りなくなることはない非損失となる。
【００１３】
次に、再配分メカニズムの具体的な手法について検討する。
【００１４】
先ず、再配分を行わない通常のオークションにおいて戦略的操作不可能性を満たすメカニズムとしてよく知られているＶｉｃｋｒｅｙオークションを適用した場合を考える。Ｖｉｃｋｒｅｙオークションでは、最も高い入札額の入札者が落札者となり、落札者の支払額は２番目に高い入札額となる。再配分額は、落札者の支払額を入札者全員に均等に再配分するものとする。図１はＶｉｃｋｒｅｙオークションによる再配分の例を示す図であり、入札者＃１が９００円を入札し、入札者＃２が１５００円を入札し、入札者＃３が４５０円を入札したものとしている。この場合、最も入札額の高い入札者＃２が落札し、その支払額は２番目に高い入札額である入札者＃１の９００円となる。従って、再配分額は９００円を３人で割って３００円ずつである。
【００１５】
しかし、このメカニズムでは、２番目に高い入札者が過大申告し、落札者の支払額を高くすることで、再配分額を大きくすることができるため、戦略的操作不可能性が保証されなくなる。図２は、図１において９００円で入札していた入札者＃１が入札額を１２００円とすることで、落札者の支払額が１２００円となり、再配分額が４００円に増えた状態を示している。
【００１６】
再配分メカニズムでは、再配分額の決定においても、評価値を過大／過少申告することで効果がない、真の評価値を申告することが最適な戦略となる戦略的操作不可能性を満たす必要がある。つまり、各入札者の再配分は自分の入札額に依存せずに決定されなければならない。このようなことから、これまで、数多くの戦略的操作不可能性を満たす再配分メカニズムの提案が行われている。なお、戦略的操作不可能性、パレート効率性、かつ、強予算均衡を同時に満たすメカニズムは存在しないことが証明されている。そのため、いずれかの条件を諦めることで再配分メカニズムが提案されている。
【００１７】
以下、戦略的操作不可能性を満たす代表的な再配分メカニズムとして、Ｃａｖａｌｌｏメカニズム（非特許文献１等を参照。）とＦａｌｔｉｎｇｓメカニズム（非特許文献２等を参照。）について説明する。
【００１８】
Ｃａｖａｌｌｏメカニズムの手順は次のようになる。
（１）Ｖｉｃｋｒｅｙオークションを適用して落札者と支払額を決定する。
（２）各入札者への再配分額は、その入札者が存在しなかったときのＶｉｃｋｒｅｙオークションの支払額を入札者数ｎで割った値で決定する。つまり、最高入札額者と２番目に高い入札額者は３番目に高い入札額、他の入札者は２番目に高い入札額の１／ｎを受け取ることになる。
【００１９】
図３はＣａｖａｌｌｏメカニズムによる再配分の例を示す図であり、入札者＃１が９００円を入札し、入札者＃２が１５００円を入札し、入札者＃３が４５０円を入札したものとしている。この場合、最も入札額の高い入札者＃２が落札し、その支払額は２番目に高い入札額である入札者＃１の９００円となる。再配分額は、入札者＃１と入札者＃２は３番目の入札額である４５０円を３人で割った１５０円、入札者＃３は２番目の入札額である９００円を３人で割った３００円となる。
【００２０】
このＣａｖａｌｌｏメカニズムでは、支払額が余るため強予算均衡は満たさないが、パレート効率的な割り当てを実現し、自分の入札額に依存せずに支払額、再配分額が決定されるため戦略的操作不可能性を満たす。
【００２１】
次に、Ｆａｌｔｉｎｇｓメカニズムの手順は次のようになる。
（１）１人の入札者を無作為に選んで除外する。
（２）残ったｎ−１人に対してＶｉｃｋｒｅｙオークションを適用して割り当てを決定する。
（３）除外された入札者は落札者から集めた支払額を受け取る。
【００２２】
図４はＦａｌｔｉｎｇｓメカニズムによる再配分の例を示す図であり、入札者＃１が９００円を入札し、入札者＃２が１５００円を入札し、入札者＃３が４５０円を入札したものとしている。また、ここでは入札者＃２がランダムに除外されたものとしている。この場合、入札者＃１と入札者＃３にＶｉｃｋｒｅｙオークションを適用することで最も入札額の高い入札者＃１が落札し、その支払額は２番目に高い入札額である入札者＃３の４５０円となる。従って、その支払額４５０円が、除外された入札者＃２に再配分される。
【００２３】
このＦａｌｔｉｎｇｓメカニズムは常に強予算均衡を満たし、戦略的操作不可能性も満たすが、パレート効率性を満たさない。
【先行技術文献】
【非特許文献】
【００２４】
【非特許文献１】Cavallo, R.: Optimal Decision-Making With Minimal Waste: Strategyproof Redistribution of VCG Payments, in AAMAS '06: Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, pp. 882-889, New York, NY, USA (2006), ACM
【非特許文献２】Faltings, B.: A Budget-Balanced, Incentive-Compatible Scheme for Social Choice, in AMEC, pp. 30-43 (2004)
【発明の概要】
【発明が解決しようとする課題】
【００２５】
上述したように、主に戦略的操作不可能性を満たす再配分メカニズムが提案されている。
【００２６】
一方、インターネットオークションでは、ネットワークの匿名性を利用した、入札者による新たな不正行為の可能性が指摘されている。そのような不正行為の一つに架空名義入札がある。架空名義入札とは、一人の入札者が複数の名義を用いて複数の入札を行うことをいう。一般的なオークションに対しては架空名義入札の影響の解析が行われている。具体的には、複数の商品を対象とする組合せオークションにおいて、理論的に望ましい性質を満たすと考えられていたオークションメカニズムが、架空名義入札を行うことで効用が増加する、すなわち、架空名義入札に脆弱であることが指摘されている。このことから、一般的なオークションについては、架空名義入札に頑健なメカニズムの提案が行われている。
【００２７】
しかしながら、再配分メカニズムにおける架空名義入札に対する解析は行われていない。例えば、ネットワーク環境で何らかのリソースを共同所有している状況を考える。このとき、メンバーのＩＤ（Identifier）は把握しているが、ネットワーク上でのＩＤと実世界での人との対応付けができていない可能性が生じる。そのような状況で、再配分メカニズムを適用した場合、架空名義入札の問題は深刻になり得る。
【００２８】
このように、再配分メカニズムの望ましい性質として、新たに架空名義入札への頑健性（false-name-proofness）が要求され、前述したＣａｖａｌｌｏメカニズムやＦａｌｔｉｎｇｓメカニズムは架空名義入札に対して脆弱であることが判明してきた。なお、再配分メカニズムが架空名義入札に対して頑健であるとは、各入札者が複数の名義を用いて複数の入札を行ったとしても効果がないことを意味する。すなわち、１つの名義を用いて真の評価値を申告することが支配戦略となる。
【００２９】
以下、既存の再配分メカニズムが架空名義入札に脆弱であることを示す。
【００３０】
図５はＣａｖａｌｌｏメカニズムによる再配分の例を示す図であり、図３の場合に比較して、入札者＃３が入札者＃４および入札者＃５としてそれぞれ入札額５０円の架空名義入札を行ったものとしている。この場合、最も入札額の高い入札者＃２が落札し、その支払額は２番目に高い入札額である入札者＃１の９００円となる点は変わらないが、再配分額は、入札者＃１と入札者＃２は３番目の入札額である４５０円を５人で割った９０円に減り、入札者＃３〜＃５は２番目の入札額である９００円を５人で割った１８０円となる。架空名義入札を行った入札者＃３は、図３の場合に比較して、再配分額が３００円から合計で５４０円に増えており、架空名義入札に脆弱であることがわかる。
【００３１】
図６はＦａｌｔｉｎｇｓメカニズムによる再配分の例を示す図であり、図４の場合に比較して、入札者＃３が入札者＃４として入札額５０円の架空名義入札を行ったものとしている。この場合、入札者＃３は複数名義で入札した方が１つの名義で入札するときよりも除外入札者に選ばれる確率が高くなり、ここでは入札者＃３が除外されたものとする。この場合、入札者＃１、＃２、＃４にＶｉｃｋｒｅｙオークションを適用することで最も入札額の高い入札者＃２が落札し、その支払額は２番目に高い入札額である入札者＃１の９００円となる。従って、その９００円が除外された入札者＃３に再配分される。架空名義入札を行った入札者＃３は、図４の場合に比較して、再配分額が０円から９００円に増えており、架空名義入札に脆弱であることがわかる。
【００３２】
本発明は上記の従来の問題点に鑑み提案されたものであり、その目的とするところは、架空名義入札に対して頑健な再配分アルゴリズムを備えた電子オークション装置を提供することにある。
【課題を解決するための手段】
【００３３】
上記の課題を解決するため、本発明にあっては、請求項１に記載されるように、複数人が所定の財を共有し、当該財の使用権の取得を決定する電子オークション装置であって、前記財の共有者である入札者および前記財の入札額を特定した入札を受け付ける入札受付手段と、入札者数および初期留保価格に基づいて前記財を落札できる権利が得られる最低入札額である留保価格を計算する留保価格計算手段と、入札者数および初期留保価格に基づいて特定の入札者に配分する再配分額を計算する再配分額計算手段と、留保価格以上であって最も高い入札額の入札者を前記財の使用権の落札者として決定する落札者決定手段と、各入札者の支払額を落札額と再配分額に基づいて計算する支払額計算手段とを備える電子オークション装置を要旨としている。
【００３４】
また、請求項２に記載されるように、請求項１に記載の電子オークション装置において、前記支払額計算手段は、２番目に高い入札額と留保価格の高い方を落札者の落札額とするようにすることができる。
【００３５】
また、請求項３に記載されるように、請求項１または２のいずれか一項に記載の電子オークション装置において、前記支払額計算手段は、各入札者につき他の入札者で留保価格以上の入札者が存在する場合に負の再配分額を支払額に含めるようにすることができる。
【００３６】
また、請求項４に記載されるように、複数人が所定の財を共有し、当該財の使用権の取得を決定する電子オークション装置の制御方法であって、前記財の共有者である入札者および前記財の入札額を特定した入札を受け付ける入札受付工程と、入札者数および初期留保価格に基づいて前記財を落札できる権利が得られる最低入札額である留保価格を計算する留保価格計算工程と、入札者数および初期留保価格に基づいて特定の入札者に配分する再配分額を計算する再配分額計算工程と、留保価格以上であって最も高い入札額の入札者を前記財の使用権の落札者として決定する落札者決定工程と、各入札者の支払額を落札額と再配分額に基づいて計算する支払額計算工程とを備える電子オークション制御方法として構成することができる。
【発明の効果】
【００３７】
本発明の電子オークション装置にあっては、架空名義入札に対して頑健な再配分アルゴリズムを提供することができる。
【図面の簡単な説明】
【００３８】
【図１】Ｖｉｃｋｒｅｙオークションによる再配分の例を示す図（その１）である。
【図２】Ｖｉｃｋｒｅｙオークションによる再配分の例を示す図（その２）である。
【図３】Ｃａｖａｌｌｏメカニズムによる再配分の例を示す図（その１）である。
【図４】Ｆａｌｔｉｎｇｓメカニズムによる再配分の例を示す図（その１）である。
【図５】Ｃａｖａｌｌｏメカニズムによる再配分の例を示す図（その２）である。
【図６】Ｆａｌｔｉｎｇｓメカニズムによる再配分の例を示す図（その２）である。
【図７】入札者数ｎと留保価格ｒｎおよび再配分額ｃｎの関係の例を示す図である。
【図８】本発明の一実施形態にかかるシステムの構成例を示す図である。
【図９】電子オークション装置のハードウェア構成例を示す図である。
【図１０】実施形態におけるオークションの処理例を示すフローチャートである。
【図１１】各入札者の支払額の計算の処理例を示すフローチャートである。
【図１２】実施形態における再配分の例を示す図（その１）である。
【図１３】実施形態における再配分の例を示す図（その２）である。
【発明を実施するための形態】
【００３９】
以下、本発明の好適な実施形態につき説明する。
【００４０】
＜原理＞
本実施形態によるオークションは次の手順により行う。
（１）留保価格以上であって最高入札額の入札者が落札者となり、財を割り当てられる。
（２）落札者の支払額は、２番目に高い入札額と留保価格ｒｎの高い方とする。（留保価格付きＶｉｃｋｒｅｙオークション）
（３）自分以外の入札者で、留保価格ｒｎ以上の入札者が存在すれば，再配分額ｃｎを受け取ることができる。そうでなければ，再配分額ｃｎを受け取ることができない。
【００４１】
支払額の再配分を行う場合、架空名義入札への頑健性を保証するためにパレート効率性を諦めなければならない。そこで、本実施形態では留保価格（reserve price）の導入を行っている。留保価格は落札できる権利が得られる最低入札額を意味する。
【００４２】
提案メカニズムのメインアイデアは入札者数ｎに対して留保価格ｒｎと再配分額ｃｎを設定することである。また、本メカニズムはＰＯＲＦメカニズム（Yokoo, M.: The characterization of strategy/false-name proof combinatorial auction protocols: Price-oriented, rationing-free protocol, in Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI2003), pp. 733-742 (2003)）に基づく。ＰＯＲＦメカニズムでは、オークション主催者が入札額から各入札者の支払額を算出し、各入札者にその額を提示する。入札者が額に応じて財の割り当てを受けるかどうかを判断する。ＰＯＲＦメカニズムは戦略的操作不可能性を満たすことが保証されている。
【００４３】
ここで、留保価格ｒｎと再配分額ｃｎは以下の条件を満たすように設定する。
【００４４】
ｒｎ  ≧  ｎ・ｃｎ          （１）
ｃｎ―１  ≧  ２ｃｎ          （２）
ｒｎ  ―  ｒｎ―１  ≧  ２ｃｎ  （３）
式（１）は再配分額が留保価格を超えないこと、式（２）は２つの名義を使って入札しても再配分額が増えないこと、式（３）は人数の増加に伴う留保価格の増分が追加される再配分額以上になることを保証するための条件式である。
【００４５】
具体的な留保価格ｒｎと再配分額ｃｎは式（１）〜（３）より、
ｒｎ  ≧  （２  ―  １／２ｎ―２）ｒ２      （４）
ｃｎ  ≦  ｒ２／２ｎ―１                    （５）
により計算することができる。すなわち、留保価格ｒｎと再配分額ｃｎは初期留保価格ｒ２（入札者数が２の場合の留保価格）に依存して決定できることが分かる。初期留保価格ｒ２は、運用知識に基づいてオークション主催者が決定する。初期留保価格ｒ２が高すぎると入札されにくくなり、低すぎると再配分が少なくなる。
【００４６】
図７は入札者数ｎと留保価格ｒｎおよび再配分額ｃｎの関係の例を示す図であり、初期留保価格ｒ２を５００円とした場合である。この場合、再配分額はｎ＝２の場合は２５０円となり、入札者が１人増える毎に半分となる。従って、一人の入札者が架空名義入札によりもう一人分を入札しても、再配分額の合計は以前と変わらず、不正を働く効果がない。
【００４７】
このメカニズムが架空名義入札に対して頑健であることの証明は次のようになる。
【００４８】
架空名義入札を利用して２つの名義を用いた場合を考える。入札者数はｎ人で、１つの名義で真の評価値を申告している入札者に着目する。このとき、財が割り当てられずに再配分だけを受けているならば、架空名義入札をしても、式（２）より再配分額は増加しない。次に、財が割り当てられている場合、架空名義入札をすることで、式（３）より留保価格がｒｎからｒｎ＋１へ大きくなり、架空名義入札によって再配分を受けても支払額は減少しない。更に、財も再配分も行われていない場合、他の入札者の入札額は留保価格ｒｎよりも低く、さらに、自分の真の評価値は留保価格ｒｎよりも低いことを意味する。このとき、架空名義入札をして財を割り当てられても、真の評価値よりも大きい留保価格ｒｎ＋１を支払わなければならない。よって、再配分を受けても真の評価値よりも大きい値を支払うこととなり、効用は負となる。以上より、架空名義入札に対して頑健であることが保証できる。
【００４９】
＜システム構成＞
図８は本発明の一実施形態にかかるシステムの構成例を示す図である。
【００５０】
図８において、インターネット等のネットワーク１には、ユーザが操作するＰＣ（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）３００９等を備えている。Ｍはプログラムもしくはデータが格納されたＣＤ／ＤＶＤ等のメディア（記録媒体）である。
【００７１】
＜動作＞
図８において、電子オークション装置３は、ユーザ登録部３０１によりユーザ登録が行われ、オークション対象登録部３０２によりオークション対象の共有リソースの登録が行われ、利用申込受付部３０３により利用申込の受付が行われた後、オークション要否決定部３０４により利用時間帯等の競合によりオークションによる決定が必要であると決定されたものとする。この場合、初期留保価格設定部３０５により自動あるいは手動により初期留保価格が設定され、オークションが開始する。
【００７２】
図１０は実施形態におけるオークションの処理例を示すフローチャートである。
【００７３】
図１０において、処理を開始すると（ステップＳ１０１）、入札受付部３０６は、入札者ｉから入札額ｂｉの申告を受け付け、入札者ＩＤと入札額と入札者数ｎをデータ格納部３１３に格納する（ステップＳ１０２）。
【００７４】
次いで、入札受付部３０６は所定時刻への到達等により入札受付終了となったか否か判断し（ステップＳ１０３）、入札受付終了でない場合（ステップＳ１０３のＮｏ）は入札受付（ステップＳ１０２）の待機に戻る。
【００７５】
入札受付終了の場合（ステップＳ１０３のＹｅｓ）、入札額ソート部３０７は、入札額ｂｉを降順に配列化して入札額降順配列を作成する（ステップＳ１０４）。また、入札額ソート部３０７は、各入札者ｉを除いた他の入札額を降順に配列化して各入札者除外降順配列を作成する（ステップＳ１０５）。
【００７６】
次いで、留保価格計算部３０８は留保価格ｒｎを計算する（ステップＳ１０６）。また、再配分額計算部３０９は再配分額ｃｎを計算する（ステップＳ１０７）。
【００７７】
次いで、オークション成立判定部３１０は、入札額ソート部３０７が作成した入札額降順配列を利用して、少なくとも一人の入札額は留保価格ｒｎ以上であるか否かによりオークションが成立するか否か判断する（ステップＳ１０８）。留保価格ｒｎ以上の入札が一人もいない場合（ステップＳ１０８のＮｏ）、オークション不成立を出力し（ステップＳ１１１）、処理を終了する（ステップＳ１１２）。
【００７８】
一方、留保価格ｒｎ以上の入札が一人でもいる場合（ステップＳ１０８のＹｅｓ）、オークション成立とし、落札者決定部３１１は、入札額ソート部３０７が作成した入札額降順配列を利用して、最高入札額の入札者を落札者に決定する（ステップＳ１０９）。
【００７９】
次いで、支払額計算部３１２は、各入札者ｉの支払額ｐｉを計算し（ステップＳ１１０）、処理を終了する（ステップＳ１１２）。
【００８０】
図１１は各入札者の支払額の計算（図１０のステップＳ１１０）の処理例を示すフローチャートである。
【００８１】
図１１において、落札者を含めて各入札者ｉについて処理を開始すると（ステップＳ２０１）、入札額ソート部３０７が作成した各入札者除外降順配列を利用して、ｂ−ｉ（１）≧ｒｎであるか否か、すなわち、入札者ｉ以外の入札者の入札額が留保価格ｒｎ以上であるか否か判断する（ステップＳ２０２）。
【００８２】
ｂ−ｉ（１）≧ｒｎである場合（ステップＳ２０２のＹｅｓ）、続いて、ｂｉ＝ｂ（１）であるか否か、すなわち、その入札者ｉが最高入札額であるか否か判断する（ステップＳ２０３）。
【００８３】
ｂｉ＝ｂ（１）である場合（ステップＳ２０３のＹｅｓ）、その入札者ｉが落札者であり、支払額ｐｉ＝ｂ−ｉ（１）−ｃｎを提示し（ステップＳ２０４）、その入札者ｉの処理を終了する（ステップＳ２０７）。
【００８４】
また、ｂｉ＝ｂ（１）でない場合（ステップＳ２０３のＮｏ）、支払額ｐｉ＝−ｃｎを提示し（ステップＳ２０５）、その入札者ｉの処理を終了する（ステップＳ２０７）。
【００８５】
一方、ｂ−ｉ（１）≧ｒｎでない場合（ステップＳ２０２のＮｏ）、支払額ｐｉ＝ｒｎを提示し（ステップＳ２０６）、その入札者ｉの処理を終了する（ステップＳ２０７）。
【００８６】
図１２は実施形態における再配分の例を示す図であり、入札者数が２の時の留保価格が５００円とし、入札者＃１が９００円を入札し、入札者＃２が４５０円を入札したものとしている。この場合、入札者＃１の入札額９００円が留保価格５００円を超えるためオークションは成立し、最も入札額の高い入札者＃１が落札し、その支払額は２番目に高い入札額である入札者＃２の４５０円と留保価格５００円の高い方の５００円となる。また、入札者＃１は他の入札者（入札者＃２のみ）の入札額が留保価格５００円を超えないため、再配分額は０となる。入札者＃２は他の入札者（入札者＃１のみ）の入札額が留保価格５００円を超えるため、再配分額は２５０円となる。
【００８７】
次に、入札者＃２が入札者＃３として５０円の架空名義入札を行った場合を図１３に示す。入札者＃３が入札を行って入札者数が３になったことで、留保価格は７５０円になっている。この場合、入札者＃１の入札額９００円が留保価格７５０円を超えるためオークションは成立し、最も入札額の高い入札者＃１が落札し、その支払額は２番目に高い入札額である入札者＃２の４５０円と留保価格７５０円の高い方の７５０円となる。また、入札者＃１は他の入札者（入札者＃２、＃３）の入札額が留保価格７５０円を超えないため、再配分額は０となる。入札者＃２は他の入札者（入札者＃１）の入札額が留保価格７５０円を超えるため、再配分額は１２５円となる。入札者＃３も他の入札者（入札者＃１）の入札額が留保価格７５０円を超えるため、再配分額は１２５円となる。よって、実質的に同一人である入札者＃２の再配分額は合計で２５０円となり、架空名義入札を行う前に比べて増加しないため、不正を働く意味がない。
【００８８】
＜総括＞
上述したように、本実施形態によれば、架空名義入札に対して頑健な再配分アルゴリズムを提供することができる。
【００８９】
以上、本発明の好適な実施の形態により本発明を説明した。ここでは特定の具体例を示して本発明を説明したが、特許請求の範囲に定義された本発明の広範な趣旨および範囲から逸脱することなく、これら具体例に様々な修正および変更を加えることができることは明らかである。すなわち、具体例の詳細および添付の図面により本発明が限定されるものと解釈してはならない。
【符号の説明】
【００９０】
１                  ネットワーク
２Ａ、２Ｂ          ユーザ端末
２１Ａ、２１Ｂ      ブラウザ
３                  電子オークション装置
３０１              ユーザ登録部
３０２              オークション対象登録部
３０３              利用申込受付部
３０４              オークション要否決定部
３０５              初期留保価格設定部
３０６              入札受付部
３０７              入札額ソート部
３０８              留保価格計算部
３０９              再配分額計算部
３１０              オークション成立判定部
３１１              落札者決定部
３１２              支払額計算部
３１３              データ格納部
【図１】
2011113201.tif 000003
【図２】
2011113201.tif 000004
【図３】
2011113201.tif 000005
【図４】
2011113201.tif 000006
【図５】
2011113201.tif 000007
【図６】
2011113201.tif 000008
【図７】
2011113201.tif 000009
【図８】
2011113201.tif 000010
【図９】
2011113201.tif 000011
【図１０】
2011113201.tif 000012
【図１１】
2011113201.tif 000013
【図１２】
2011113201.tif 000014
【図１３】
2011113201.tif 000015