電子入札システム、開札者用装置、入札者用装置、電子入札方法、プログラムおよび記録媒体
【課題】複数の属性値を有する財に対応し、かつ開札者の個人合理性を保証する。
【解決手段】入札者用装置２は、複数の属性値を含む、財に対する評価値を開札者用装置１に送信し、選択された財とその属性値と選択された財に対する支払額とを開札者用装置１から通知されたときに、通知された属性値と支払額に基づいて入札者の効用を算出し、効用に基づいて支払額を承諾するか否かを決定し、結果を開札者用装置１に通知する。開札者用装置１は、入札者が売却する財の組み合わせと属性値の組み合わせの実現可能な複数のパターンを生成し、パターンの中から入札者と開札者に最大の効用を与える財の組み合わせと属性値の組み合わせを選択して入札者への支払額を算出し、財の組み合わせと属性値の組み合わせと支払額とを入札者用装置２に通知する。
【解決手段】入札者用装置２は、複数の属性値を含む、財に対する評価値を開札者用装置１に送信し、選択された財とその属性値と選択された財に対する支払額とを開札者用装置１から通知されたときに、通知された属性値と支払額に基づいて入札者の効用を算出し、効用に基づいて支払額を承諾するか否かを決定し、結果を開札者用装置１に通知する。開札者用装置１は、入札者が売却する財の組み合わせと属性値の組み合わせの実現可能な複数のパターンを生成し、パターンの中から入札者と開札者に最大の効用を与える財の組み合わせと属性値の組み合わせを選択して入札者への支払額を算出し、財の組み合わせと属性値の組み合わせと支払額とを入札者用装置２に通知する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワーク上に分散配置された複数の入札者用装置を用いる複数の入札者が電子的手段によって入札を行う電子入札システム、開札者用装置、入札者用装置、電子入札方法、プログラムおよび記録媒体に関するものである。
【背景技術】
【０００２】
オークションは、資源の効率的な配分を実現するために最も重要なメカニズムの１つである。特に、近年は通信ネットワークを用いた大規模なオークションが一般的になりつつある。通信ネットワークを用いたオークションでは、新しいタイプの不正行為が問題となる。例えば単一の入札者が複数の名義（例えば異なるメールアドレス）を用いて、複数の入札を行うことが容易に可能である。これを架空名義入札と呼ぶ。
【０００３】
そこで、通信ネットワークを用いたオークションにおいて、多様な興味を持つ（すなわち、複数の財に興味を持つ）人が存在する場合でも機能し、かつ架空名義による入札を困難にする技術として、ＰＯＲＦ（Price-Oriented Rationing-Free ）が提案されている（例えば、非特許文献１参照）。このＰＯＲＦプロトコルについて、以下に説明する。
【０００４】
組み合わせオークションの対象領域モデルを定義する。ＰＯＲＦプロトコルでは、単一の買い手（以下、開札者という）０、この開札者に対して売り手（以下、入札者という）の集合Ｎ＝｛１，２，・・・，ｎ｝、入札者が提供する仕事や物等の財ｔの集合Ｔ＝｛ｔ1，・・・，ｔm｝が存在する。各入札者はそれぞれタイプθi を有している。タイプθi は集合Θの要素である。ここで、タイプθi とは、入札者ｉが所有する財に対して、入札者ｉが付与した評価値を意味する。財ｔの入札者への可能な割り当ては、式（１）で表される。
【０００５】
【数１】
【０００６】
ここで、バンドルＢi⊆Ｔ であり、ｉ≠ｋであれば式（２）が成り立つ。なお、バンドルＢとは、任意の財の組み合わせのことを意味する。
【０００７】
【数２】
【０００８】
財の割り当てがバンドルＢiのとき、入札者が入札に要するコストはｃ（θi，Ｂi）で表され、式（３）の条件を満たす。
【０００９】
【数３】
【００１０】
開札者から入札者ｉへの財に関する支払額はｐi で表される。各入札者の効用が準線形であることを仮定すると、各入札者ｉにとっての効用は、ｐi−ｃ（θi，Ｂi） で表される。ここでの入札者の効用とは、支払額ｐi からコストｃ（θi，Ｂi）を引いているため、入札者の利益を表している。また、開札者にとっての効用は式（４）で表される。
【００１１】
【数４】
【００１２】
次に、ＰＯＲＦプロトコルは以下のように定義される。まず、各入札者ｉは、式（５）で表される自分のタイプを申告する。ただし、入札者ｉは真のタイプθi を申告するとは限らない。
【００１３】
【数５】
【００１４】
タイプを申告すると、入札者ｉに関して、任意のバンドルＢ⊆Ｔに対する支払額ｐB,i が決定される。この支払額ｐB,i は、入札者ｉが申告したタイプとは無関係に決定される。なお、支払額ｐB,i は、他者の申告したタイプには依存しても良い。
ここで、Ｂ⊆Ｂ’の場合、式（６）を仮定する。
【００１５】
【数６】
【００１６】
入札者ｉには、式（７）で表される効用を最大化するバンドルＢが割り当てられる。支払額ｐB,i は、式（７）の効用を最大化するバンドルが複数存在する場合には、それらのいずれか１つが割り当てられる。ここで、式（８）は入札者ｉのバンドルＢに対する評価値である。
【００１７】
【数７】
【００１８】
【数８】
【００１９】
割り当て結果は、割り当て可能性を満たすように決定する。すなわち、入札者ｉ，ｊにそれぞれ割り当てられるバンドルＢi，Ｂjに関して、式（９）が成立するように決定される。
【００２０】
【数９】
【００２１】
このようなＰＯＲＦプロトコルによれば、入札者にとっては、バンドルの支払額が自分の申告したタイプとは無関係に決定され、また他者の割り当て結果とは独立に、自分の効用を最大化するバンドルを得ることができる。ＰＯＲＦプロトコルにより通信ネットワークを用いたオークションを実現すると、入札者自身ではバンドルの支払額を操作することができない。すなわち支払額の戦略的操作が不可能となる。
【００２２】
一方、ＰＯＲＦプロトコルでは、各入札者の各バンドルの支払額は、割り当て可能性が満たされるように、すなわち同じ財を同時に複数の入札者に割り当てないよう適切に決定される必要がある。しかし、ＰＯＲＦプロトコルでは、入札者ｉに対して効用を最大化するバンドルが複数存在する場合、そのいずれか１つを割り当てるが、どれを割り当てるかに関しては規定していない。したがって、オークションの主催者は、割り当て可能性が満足されるように、割り当てを調整することが可能である。
【００２３】
ＰＯＲＦプロトコルを用いたオークションにおける支払額の決定例を以下に示す。なお、上述したようにＰＯＲＦプロトコルは戦略的操作不可能であるため、以下の例では各入札者ｉは真のタイプθi を申告するものとする。
【００２４】
単一の財のオークションの場合、唯一のバンドルＢ＝Ｍの支払額は、ｐB,i＝ｍａｘj≠iｖ（Ｂ，θj） で与えられる。このプロトコルはＶｉｃｋｒｅｙオークションと等価である。複数の財の組み合わせオークションの場合、プロトコルの記述の簡単化のため、入札者の集合Ｘと財の集合Ｂに対して、Ｖ*（Ｘ、Ｂ） をＢがＸに最適に割り当てられたときのＸの評価値の合計とする。このとき、入札者への支払額ｐB,i は以下のような式で表される。
ｐB,i＝Ｖ*（Ｎ＼｛ｉ｝，Ｍ）−Ｖ*（Ｎ＼｛ｉ｝，Ｍ＼Ｂ） ・・・（１０）
この式（１０）の支払額の算出は、ＶＣＧ（Vickrey-Clarke-Groves）メカニズムと等価である。
【００２５】
【非特許文献１】Makoto Yokoo，“ Characterization of Strategy/False-name Proof Combinatorial Auction Protocols:Price-oriented, Rationing-free Protocol”，In Proceedings of 19th International Joint Conference on Artifical Intelligence（IJCAI-2003）， p.733-739，2003
【発明の開示】
【発明が解決しようとする課題】
【００２６】
複数の財をオークションにより売却する場合、各財の価値の間に依存関係が存在することが通例である。また、各財に対して品質などの属性値が設定される場合もある。
しかしながら、従来のＰＯＲＦプロトコルにより実現可能な従来のオークションでは、複数の属性値を持つ複数の財のオークションに対応することができないという問題点があった。
【００２７】
また、従来のＰＯＲＦプロトコルにより実現可能な従来のオークションでは、開札者の個人合理性を保証できないという問題点があった。開札者の個人合理性とは、開札者に損失が生じることがない、という意味である。
【００２８】
そこで、本発明は、上述したような課題を解決するためになされたものであり、複数の属性値を有する財に対応可能で、かつ開札者の個人合理性を保証することができる電子入札システム、開札者用装置、入札者用装置、電子入札方法、プログラムおよび記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００２９】
本発明は、財を購入する単一の開札者が使用する開札者用装置と、前記財を提供する複数の入札者が使用する複数の入札者用装置と、前記開札者用装置と前記複数の入札者用装置とを接続するネットワークとを備え、複数の属性値を有する財に対して入札を行う電子入札システムであって、前記入札者用装置は、前記複数の属性値を含む、前記財に対する評価値を前記開札者用装置に送信する第１の送信手段と、前記入札者が売却する財を前記開札者用装置が選択して、この選択された財とその属性値と前記選択された財に対する支払額とを前記開札者用装置から通知されたときに、この通知された属性値と支払額に基づいて前記入札者の効用を算出する効用算出手段と、前記算出された効用に基づいて前記支払額を承諾するか否かを決定する決定手段と、この決定手段の結果を前記開札者用装置に通知する第２の送信手段とを有し、前記開札者用装置は、前記入札者用装置から受信した前記評価値に基づいて、前記入札者が売却する財の組み合わせと属性値の組み合わせの実現可能な複数のパターンを生成する分割セット手段と、これらのパターンの中から前記入札者と前記開札者に最大の効用を与える財の組み合わせと属性値の組み合わせを選択し、選択した組み合わせに基づいて前記入札者への支払額を算出する支払額算出手段と、この支払額算出手段によって選択された財の組み合わせと属性値の組み合わせと前記算出された支払額とを前記入札者用装置に通知する第３の送信手段とを有するものである。
また、本発明の電子入札システムの１構成例において、前記開札者用装置の支払額算出手段は、任意の入札者用装置から提供される前記財に対する支払額を、前記任意の入札者用装置以外の入札者用装置から受信した前記評価値に基づいて算出するものである。
【００３０】
また、本発明は、複数の属性値を有する財を提供する複数の入札者が使用する複数の入札者用装置とネットワークを介して接続され、前記財を購入する開札者が使用する開札者用装置であって、前記複数の属性値を含む、前記財に対する評価値を前記入札者用装置から受信したときに、前記評価値に基づいて、前記入札者が売却する財の組み合わせと属性値の組み合わせの実現可能な複数のパターンを生成する分割セット手段と、これらのパターンの中から前記入札者と前記開札者に最大の効用を与える財の組み合わせと属性値の組み合わせを選択し、選択した組み合わせに基づいて前記入札者への支払額を算出する支払額算出手段と、前記選択された財の組み合わせと属性値の組み合わせと前記算出された支払額とを前記入札者用装置に通知する送信手段とを有するものである。
また、本発明は、財を購入する単一の開札者が使用する開札者用装置とネットワークを介して接続され、複数の属性値を有する財を提供する入札者が使用する入札者用装置であって、前記複数の属性値を含む、前記財に対する評価値を前記開札者用装置に送信する第１の送信手段と、前記入札者が売却する財を前記開札者用装置が選択して、この選択された財とその属性値と前記選択された財に対する支払額とを前記開札者用装置から通知されたときに、この通知された属性値と支払額に基づいて前記入札者の効用を算出する効用算出手段と、前記算出された効用に基づいて前記支払額を承諾するか否かを決定する決定手段と、この決定手段の結果を前記開札者用装置に通知する第２の送信手段とを有するものである。
【００３１】
また、本発明は、財を購入する単一の開札者が使用する開札者用装置と、前記財を提供する複数の入札者が使用する複数の入札者用装置と、前記開札者用装置と前記複数の入札者用装置とを接続するネットワークとを備えた電子入札システムにおいて、複数の属性値を有する財に対して入札を行う電子入札方法であって、前記入札者用装置が、前記複数の属性値を含む、前記財に対する評価値を前記開札者用装置に送信する第１の送信手順と、前記開札者用装置が、前記入札者用装置から受信した前記評価値に基づいて、前記入札者が売却する財の組み合わせと属性値の組み合わせの実現可能な複数のパターンを生成する分割セット手順と、前記開札者用装置が、前記パターンの中から前記入札者と前記開札者に最大の効用を与える財の組み合わせと属性値の組み合わせを選択し、選択した組み合わせに基づいて前記入札者への支払額を算出する算出手順と、前記開札者用装置が、前記選択された財の組み合わせと属性値の組み合わせと前記算出された支払額とを前記入札者用装置に通知する通知手順と、前記入札者用装置が、前記選択された財とその属性値と前記選択された財に対する支払額とを前記開札者用装置から通知されたときに、この通知された属性値と支払額に基づいて前記入札者の効用を算出する効用算出手順と、前記入札者用装置が、前記算出された効用に基づいて前記支払額を承諾するか否かを決定する決定手順と、前記入札者用装置が、この決定手順の結果を前記開札者用装置に通知する第２の送信手順とを有するものである。
また、本発明の電子入札方法の１構成例において、前記算出手順は、任意の入札者用装置から提供される前記財に対する支払額を、前記任意の入札者用装置以外の入札者用装置から受信した前記評価値に基づいて算出するものである。
【００３２】
また、本発明の電子入札プログラムは、前記入札者用装置が、前記財の複数の属性値を含む、前記財に対する評価値を前記開札者用装置に送信する第１の送信手順と、前記開札者用装置が、前記入札者用装置から受信した前記評価値に基づいて、前記入札者が売却する財の組み合わせと属性値の組み合わせの実現可能な複数のパターンを生成する分割セット手順と、前記開札者用装置が、前記パターンの中から前記入札者と前記開札者に最大の効用を与える財の組み合わせと属性値の組み合わせを選択し、選択した組み合わせに基づいて前記入札者への支払額を算出する算出手順と、前記開札者用装置が、前記選択された財の組み合わせと属性値の組み合わせと前記算出された支払額とを前記入札者用装置に通知する通知手順と、前記入札者用装置が、前記選択された財とその属性値と前記選択された財に対する支払額とを前記開札者用装置から通知されたときに、この通知された属性値と支払額に基づいて前記入札者の効用を算出する効用算出手順と、前記入札者用装置が、前記算出された効用に基づいて前記支払額を承諾するか否かを決定する決定手順と、前記入札者用装置が、この決定手順の結果を前記開札者用装置に通知する第２の送信手順とをコンピュータに実行させるようにしたものである。
また、本発明の記録媒体は、電子入札プログラムを記録したものである。
【発明の効果】
【００３３】
本発明によれば、入札者用装置から受信した財の評価値に基づいて、開札者用装置が、入札者が売却する財の組み合わせと属性値の組み合わせの実現可能な複数のパターンを生成し、これらのパターンの中から入札者と開札者に最大の効用を与える財の組み合わせと属性値の組み合わせを選択し、選択した組み合わせに基づいて入札者への支払額を算出することにより、複数の属性値を有する複数の財のオークションに対応することが可能となる。また、本発明では、開札者に最大の効用を与える財の組み合わせと属性値の組み合わせを選択することから、開札者の個人合理性を保証することができる。また、本発明では、入札者にとって使い勝手がよいオークションを実現することができる。さらに、本発明では、単一の入札者が複数の名義を用いる架空名義入札を行っても、入札者が利益を得ることがないようにして、架空名義入札不可能性を実現することができる。
【発明を実施するための最良の形態】
【００３４】
［発明の原理］
本発明は、複数の属性値を持った複数の財を電子入札により売却する際に、全ての入札者の入札値とそれに対応するクオリティを基に、各入札者ごとに各クオリティに対する支払額のリストを決定し、そこから入札者がクオリティと入札額を決定することを特徴とするものである。なお、クオリティとは、財の属性値に含まれるものであり、特に財の品質等を意味する。
【００３５】
従来、オークションのプロトコルが誘因両立であるとは、真のタイプ／評価値を宣言することが入札者にとって最良の戦略であることを意味している。本発明では、誘因両立の定義を拡張して、架空名義入札に対する頑健性も示すことができるようにした。すなわち、オークションプロトコルが誘因両立とは、唯一つのＩＤを用いて真のタイプを宣言することが各入札者にとって最良の戦略であることを意味している。従来の定義と拡張した定義を区別するために、従来の定義を戦略的操作不可能性と呼び、本発明による拡張した定義を架空名義入札不可能性と呼ぶ。
オークションプロトコルが個人合理的であるとは、支配戦略均衡においてはどの入札者も損失が生じることがない、すなわち入札に要するコストが支払額を超えることがない、という意味である。オークションでは、個人合理性は不可欠である。入札者は、財を勝ち取るために使う費用よりも得られる金額が少ないオークションには参加したいとは思わない。それゆえ、本発明では、個人合理的なプロトコルのみに焦点を当てる。また、入札者から入力されるタイプθが同じであれば、常に同じ財の割り当てと支払額が得られるプロトコルのみを扱う。
【００３６】
［拡張ＬＤＳプロトコル］
本発明の拡張ＬＤＳ（Leveled Division Set：レベル付分割セット）プロトコルのモデル、すなわち環境を以下のように定義する。
【００３７】
本発明の拡張ＰＯＲＦプロトコルでは、単一の買い手（開札者）０と、この開札者に対して売り手（入札者）の集合Ｎ＝｛１，２，・・・，ｎ｝が存在し、また入札者が提供する仕事や物等の財ｔの集合Ｔ＝｛ｔ1，・・・，ｔm｝が存在する。各入札者はそれぞれタイプθi を有している。タイプθi は集合Θの要素である。タイプθi とは、入札者ｉが所有する財に対して、入札者ｉが付与した評価値を意味する。
【００３８】
各財ｔj に対して、入札者によりクオリティｑj が定義される。このクオリティｑj は集合Ｑの要素である。クオリティｑj とは、属性値に含まれるものであり、特に財ｔの品質などを意味している。入札者への財ｔの可能な割り当ては、式（１１）のように表される。
【００３９】
【数１０】
【００４０】
ここで、バンドルＢi⊆Ｔであり、ｉ≠ｋであれば式（１２）が成り立つ。なお、バンドルＢとは、任意の財の組み合わせのことを意味する。
【００４１】
【数１１】
【００４２】
クオリティのプロファイルは式（１３）で表される。クオリティプロファイルとは、財のクオリティの集合を意味し、式（１３）のようにベクトルで表記される。
【００４３】
【数１２】
【００４４】
式（１３）のクオリティプロファイルとバンドルＢi＝｛ｔi,1，ｔi,2，．．．｝に対して、クオリティプロファイルへのバンドルＢiの射影（projection ）を以下の式（１４）で表す。
【００４５】
【数１３】
【００４６】
入札者に割り当てる財がバンドルＢiで、このときに達成されるクオリティプロファイルが式（１５）の場合、入札者がオークションの入札に要するコストは式（１６）のように表される。ここで、式（１６）のコストｃは式（１７）により正規化されているものとする。
【００４７】
【数１４】
【００４８】
【数１５】
【００４９】
【数１６】
【００５０】
クオリティプロファイルが式（１３）のように表されるとき、開札者０のグロスの効用は式（１８）で表される。この開札者０のグロスの効用とは、開札者にとってどれほど価値があるのかを示す指標である。
【００５１】
【数１７】
【００５２】
開札者から入札者ｉへの財に関する支払額はｐi で表される。各入札者の効用が準線形であることを仮定すると、各入札者ｉにとっての効用は、支払額ｐi からコストｃを除いた式（１９）で表される。また、開札者にとってのネットワークの効用は、式（１８）のグロスの効用から支払額を除いた式（２０）で表される。
【００５３】
【数１８】
【００５４】
【数１９】
【００５５】
割り当てられてない財ｔj のクオリティをｑ0∈Ｑ とする。この場合の開札者の効用は式（２１）となり、割り当てられない財ｔj のクオリティプロファイルは式（２２）となる。
以上が、本発明の拡張ＰＯＲＦプロトコルのモデル（環境）の定義である。
【００５６】
【数２０】
【００５７】
【数２１】
【００５８】
財のクオリティを表すパラメータはｑjのただ一つであるが、これはクオリティが一次元であることを示すのではなく、ｑjは複数の属性値を持つベクトルとすることができる。このようなモデルの具体例について述べる。
入札者が二人、すなわち入札者の集合Ｎ＝｛１，２｝が存在し、財が二つ、すなわち財の集合Ｔ＝｛ｔ1，ｔ2｝が存在し、クオリティプロファイルが式（２３）であり、ｑj が一次元の場合の入札者１のコスト関数は、式（２４）〜（２６）のように表すことができる。
【００５９】
【数２２】
【００６０】
ｃ（θ1,｛ｔ1｝,（ｑ1））＝（１／４）ｑ1 ・・・（２４）
ｃ（θ1,｛ｔ2｝,（ｑ2））＝（１／２）ｑ2 ・・・（２５）
ｃ（θ1,｛ｔ1,ｔ2｝,（ｑ1,ｑ2））＝（１／４）ｑ1＋（１／２）ｑ2
・・・（２６）
【００６１】
また、開札者のグロスの効用が式（２７）であり、入札者２のコストは常に入札者１のコストよりも大きいものとする。このような場合に、財ｔ1とｔ2の両方が式（２８）のクオリティプロファイルで入札者１に割り当てられたとすると、入札者１のコストはｃ（θ1,｛ｔ1，ｔ2｝,（４，４））＝２となり、社会的余剰はＶ（（４，４））−ｃ（θ1,｛ｔ1，ｔ2｝,（４，４））＝２となる。
【００６２】
【数２３】
【００６３】
【数２４】
【００６４】
［支払額ｐの決定方法］
次に、入札者への支払額ｐの決定方法について説明する。まず、参照入札者という特別な入札者を導入する。この参照入札者は以下のような（Ａ）、（Ｂ）、（Ｃ）の特性を有する。
【００６５】
（Ａ）財を買い取る開札者は、財ｔk がクオリティｑk で参照入札者に割り当てられたときのコストの上界値を知っている。すなわち、開札者は、式（２９）が成立しているときに、コストｃ（θr，｛ｔk｝，（ｑk）） の上界値ｃr,tk,qk を知っている。
【００６６】
【数２５】
【００６７】
（Ｂ）参照入札者のコストは加算的である。すなわち、任意のバンドルＢ、式（３０）のクオリティプロファイルに対して、式（３１）が成り立つ。これにより、式（３２）が成り立つ。
【００６８】
【数２６】
【００６９】
【数２７】
【００７０】
【数２８】
【００７１】
（Ｃ）式（３３）に示す任意のクオリティプロファイルに対して、式（３４）が成り立つ。これはどんなクオリティに対しても、全ての財が参照入札者に割り当てられて、支払額が上界値の合計と等しくなったとき、開札者のネットワークの効用は負にならないことを意味する。
【００７２】
【数２９】
【００７３】
【数３０】
【００７４】
次に、入札者が入力したタイプθに基づいて、入札者へ割り当て可能な財の組み合わせとクオリティの組み合わせを示すＬＤＳを次の（Ｄ）、（Ｅ）のように定義する。
（Ｄ）まず、各組み合わせパターンに固有のレベル１，２，・・・，ｍａｘ＿ｌｅｖｅｌを定義する。
（Ｅ）各レベルに対して、財の組み合わせパターンを示す分割Ｄl と式（３５）に示すクオリティプロファイルを定義する。
【００７５】
【数３１】
【００７６】
各レベルの分割は以下の（Ｆ）、（Ｇ）の性質を満たすものとする。
（Ｆ）Ｄ1 ＝Ｔ、すなわちレベル１の分割は全ての財のバンドルのみからなる集合である。
（Ｇ）各レベルとその分割に対して、その分割に含まれる複数のバンドルの和は常により小さいレベルの分割に含まれ、また同じクオリティである。すなわち、式（３６）が成立し、またＢu＝∪B∈D'で∀ｌ＞１、∀Ｄ’⊆Ｄlとなる。そのとき、Ｂu∈Ｄl'かつ式（３７）が成立する分割Ｄl'があるレベルｌ’＜ｌが存在する。
【００７７】
【数３２】
【００７８】
【数３３】
【００７９】
表１と表２にレベル付分割セットの例を示す。表１では財ｔの数は２で、クオリティは１か２である。また、表２では財ｔの数は３で、クオリティは１か２である。
【００８０】
【表１】
【００８１】
【表２】
【００８２】
例えば、表１において、分割｛（ｔ1，ｔ2）｝は一人の入札者に財ｔ1，ｔ2が割り当てられることを示す。また、分割｛（ｔ1），（ｔ2）｝は一人の入札者に財ｔ1 が割り当てられ、別の入札者に財ｔ2 が割り当てられることを示す。表２の場合も同様である。また、表１において、分割｛（ｔ1，ｔ2）｝に対してクオリティ（ｑ1，ｑ2）が（２，２）であることは、財ｔ1のクオリティｑ1が２であり、財ｔ2のクオリティｑ2も２であることを示す。
【００８３】
分割Ｄl ＝｛Ｂl,1，Ｂl,2，・・・｝と財の実現可能な割り当てを示す式（３８）に対して、以下の条件（Ｈ）、（Ｉ）が満たされたときに分割Ｄl の元で式（３８）が許されると言う。
【００８４】
【数３４】
【００８５】
（Ｈ）ある分割中の同じバンドルに属する財は、同じ入札者に割り当てられなければならない。また、もし同じ分割中の異なるバンドルに属する財は、参照入札者に割り当てられる場合以外は異なる入札者に割り当てられなければならない。すなわち、ｉ≠ｒで、式（３９）が成立するならば、Ｂl,k＝Ｂｉであり、式（４０）が成立するならば、Ｂl,k⊆Ｂrである。
【００８６】
【数３５】
【００８７】
【数３６】
【００８８】
（Ｉ）もし財が分割のどのセットにも属さないならば、その財は参照入札者に割り当てられる。すなわち、全ての財ｔk に対して、もし∀Ｂl,k∈Ｄlと式（４１）が成り立つならば、ｔk∈Ｂrである。
【００８９】
【数３７】
【００９０】
また、分割Ｄl で許される割り当ての集合をレベルｌでの可能な割り当てＳＢl と記述する。
以上のＬＤＳプロトコルを実行するためには、開札者はあらかじめレベル付分割セットを決定しておく必要がある。入札者ｉは前述の式（５）で表される自分のタイプを宣言する。このタイプは真のタイプθi と異なっていてもよい。
【００９１】
財が割り当てられるべきレベルを探索するために、開札者はプロシージャＬＤＳ（ｌ）を呼び出す。ＬＤＳ（ｌ）は再帰的なプロシージャになっており、以下の（Ｊ）、（Ｋ）、（Ｌ）の通り定義する。
【００９２】
（Ｊ）∃Ｂx∈Ｄlと式（４２）に示すコストの条件を満たすただ一人の入札者ｘ∈Ｎが存在する場合は、後述するＶＣＧ（ｌ）プロシージャとＬＤＳ（ｌ＋１）とを比較して、入札者ｘに対してより大きな効用を与えるほうを選択する。このときの入札者ｘをビボタル入札者と呼ぶ。ＬＤＳ（ｌ＋１）の結果が選択された揚合は、入札者ｘ以外の通常の入札者には財は割り当てられない。入札者ｘに割り当てられなかった財は、前述の参照入札者に割り当てられる。
【００９３】
【数３８】
【００９４】
（Ｋ）∃Ｂx1∈Ｄlと∃Ｂx2∈Ｄlと式（４３）、式（４４）に示すコストの条件を満たす少なくとも二人の入札者ｘ1，ｘ2∈Ｎ、ｘ1≠ｘ2が存在する場合は、後述するＶＣＧ（ｌ）プロシージャを適用する。
【００９５】
【数３９】
【００９６】
【数４０】
【００９７】
（Ｌ）前記の（Ｊ）、（Ｋ）の条件を満たさない場合は、ＬＤＳ（ｉ＋１）を実行する。そして、ｉ＝ｍａｘ＿ｌｅｖｅｌの場合は終了する。
【００９８】
次に、プロシージャＬＤＳ（ｌ）中で用いられるＶＣＧ（ｌ）を以下のように定義する。プロシージャＶＣＧ（ｌ）では、式（４５）に示す開札者の効用を最大化するような式（４６）の割り当てを選ぶ。
【００９９】
【数４１】
【０１００】
【数４２】
【０１０１】
入札者ｘ（ｘ≠ｒ）への支払い額ｐx は式（４７）のように計算される。式（４８）はレベルｌでの可能な割り当てＳＢl の中で入札者ｘを除いたときに社会的余剰を最大化する割り当てを示している。
以上のようにして、本発明では、入札者への財の割り当てと財のクオリティと支払額ｐとを開発者側で決定することができる。
【０１０２】
【数４３】
【０１０３】
【数４４】
【０１０４】
［実施の形態］
以下、本発明の実施の形態について図面を参照して説明する。図１は、本実施の形態に係るオークションシステムの構成を示すブロック図である。
本実施の形態のオークションシステムは、オークションを取り仕切るオークショニアや、入札者から仕事や物等の財を買う買い取り者である開札者が用いる開札者用装置１と、開札者に財を提供する複数の入札者がそれぞれ用いる複数の入札者用装置２と、開札者用装置１と入札者用装置２とを接続するネットワーク３とから構成される。
【０１０５】
図２は、開札者用装置１の１構成例を示すブロック図である。開札者用装置１は、ネットワーク３を介して入札者用装置２と各種情報の送受信を行う送受信部１１と、開札者の操作入力を検出する入力部１２と、オークションに関する各種情報を表示する表示部１３と、入札者用装置２から受信するタイプ、財およびこの財の属性値などのオークションに関する各種情報を記憶する記憶部１４と、入札者が提供する財に対する支払額を算出する支払額演算部１５と、これらの開札者用装置１の各機能部の動作を制御する制御部１６とを備え、これらの開札者用装置１の各機能部はバス等の公知の通信回線１７により接続されている。支払額演算部１５は、分割セット手段と支払額算出手段を構成し、送受信部１１は、第３の送信手段を構成している。
【０１０６】
このような開札者用装置１は、ＣＰＵ等の中央処理装置、記憶装置、入札者用装置２と各種情報の送受を行うＩ／Ｆ装置、キーボード、マウス等の入力装置、ＬＣＤ（Liquid Crystal Display）等の表示装置などを備えたコンピュータと、このコンピュータにインストールされたプログラムとから構成されている。中央処理装置がメモリに格納されたプログラムを実行することにより、すなわちハードウェア資源とソフトウェアが協働することにより、上述した送受信部１１、入力部１２、表示部１３、記憶部１４、支払額演算部１５、制御部１６および通信回線１７が実現される。
【０１０７】
図３は、入札者用装置２の１構成例を示すブロック図である。入札者用装置２は、ネットワーク３を介して開札者用装置１と各種情報の送受信を行う送受信部２１と、入札者の操作入力を検出する入力部２２と、オークションに関する各種情報を表示する表示部２３と、開札者用装置１から受信する支払額などのオークションに関する各種情報を記憶する記憶部２４と、開札者用装置１により算出された支払額に基づいて財の効用を算出する効用演算部２５と、これらの入札者用装置２の各機能部の動作を制御する制御部２６とを備え、これらの入札者用装置２の各機能部はバス等の公知の通信回線２７により接続されている。効用演算部２５は、効用算出手段を構成し、送受信部２１は、第１の送信手段と第２の送信手段を構成している。
【０１０８】
このような入札者用装置２は、ＣＰＵ等の中央処理装置、記憶装置、開札者用装置１と各種情報の送受を行うＩ／Ｆ装置、キーボード、マウス等の入力装置、ＬＣＤ等の表示装置などを備えたコンピュータと、このコンピュータにインストールされたプログラムとから構成されている。中央処理装置がメモリに格納されたプログラムを実行することにより、すなわちハードウェア資源とソフトウェアが協働することにより、上述した送受信部２１、入力部２２、表示部２３、記憶部２４、効用演算部２５、制御部２６および通信回線２７が実現される。
【０１０９】
ネットワーク３は、例えばインターネットやＬＡＮ（Local Area Network）、ＷＡＮ（Wide Area Network）等の公知の電気通信システムから構成される。
【０１１０】
次に、図４を参照して本実施の形態のオークションシステムの情報の送受信について説明する。図４は、オークションシステムの情報の送受信を説明するためのシーケンス図である。
まず、開札者は、あらかじめ開札者用装置１を通して（またはその他の何らかの通知手段により）、競争入札を実施する旨の案内を各入札者の入札者用装置２に通知しておく。
【０１１１】
競争入札が開始されると、入札者は入札者用装置２に自身のタイプθを入力する。入札者用装置２の制御部２６は、入力部２２から入力された入札者のタイプθを送受信部２１を通じて開札者用装置１に通知する（図４ステップＳ４０１）。ここで、タイプθとは、入札者が提供する財のコストなど入札者の財に対する評価を表すものであり、入札者が提供する仕事や物等の財と、この財の品質などを表すクオリティ（属性値）とを少なくとも含む。
【０１１２】
なお、本発明の拡張ＰＯＲＦプロトコルによれば、各入札者にとっては真のタイプを入力することが最良の戦略であるため、各入札者が入力するタイプは真の評価値、すなわちコストとしてよい。よって、入札者は、複数の財の全ての組み合わせの、その全てのクオリティに関してコストを入力することとする。
【０１１３】
開札者用装置１の制御部１６は、受信したタイプθを記憶部１４に格納し、このタイプθに基づいて入札者への財の割り当てとクオリティと支払額ｐとを支払額演算部１５に決定させて、決定した財の割り当てとクオリティと支払額ｐとを送受信部１１を通じて入札者用装置２に通知する（ステップＳ４０２）。ここで、制御部１６は、入札に参加する全ての入札者の入札者用装置２からタイプθを受信してから、支払額ｐを算出させる。支払額演算部１５は、前述の支払額ｐの決定方法に基づいて入札者への財の割り当てとクオリティと支払額ｐを入札者毎に決定する。
【０１１４】
入札者用装置２の制御部２６は、開札者用装置１から受信した割り当てとクオリティと支払額ｐとを記憶部２４に格納し、このクオリティと支払額ｐに基づいて効用演算部２５に入札者の効用を算出させて、効用が正の場合、すなわち入札者に損失が生じない場合には、支払額ｐを承諾することを送受信部２１を通じて開札者用装置１に通知し、効用が負の場合、すなわち入札者に損失が生じる場合には、入札から降りることを開札者用装置１に通知する（ステップＳ４０３）。効用演算部２５は、前述の式（１９）により入札者の効用を算出する。このようにすることにより、本実施の形態では、複数の属性値を有する複数の財のオークションに対応することが可能となる。
【０１１５】
次に、図５を参照して、開札者用装置１の動作について説明する。図５は、開札者用装置１の動作を示すフローチャートである。
まず、開札者用装置１は、オークションに参加する各入札者の入札者用装置２からそれぞれタイプθを受信する（図５ステップＳ５０１）。ネットワーク３を通じて入札者用装置２から送信されたタイプθは、送受信部１１により受信されて、記憶部１４に格納される。
【０１１６】
この受信動作は、オークションに参加する全ての入札者の入札者用装置２からタイプθを受信するまで行われる。すなわち、開札者用装置１の制御部１６は、オークションに参加する全ての入札者の入札者用装置２からタイプθを受信したかどうかを判定し（ステップＳ５０２）、タイプθを受信していない場合は（ステップＳ５０２においてＮＯ）、ステップＳ５０１の処理に戻る。
【０１１７】
なお、全ての入札者のタイプθを受信したかどうかは、あらかじめ競争入札に参加する入札者を特定しておいて、これら特定の入札者の入札者用装置２からタイプθを受信したかどうかで判断すればよい。また、あらかじめ入札の終了時刻を設定しておき、その終了時刻までにタイプθを送信した入札者を競争入札に参加する入札者とし、終了時刻が経過した時点で全ての入札者のタイプθを受信したと見なしてもよい。
【０１１８】
制御部１６は、全ての入札者からタイプθを受信すると、受信したタイプθに基づいて入札者への財の割り当てとクオリティと支払額ｐとを支払額演算部１５に決定させる（ステップＳ５０３）。この割り当てとクオリティと支払額ｐとは記憶部１４に記憶される。財の割り当てとクオリティと支払額ｐとは、オークションに参加した入札者用装置２毎（入札者毎）に決定される。このとき、支払額演算部１４は、同一の財が複数の入札者に割り当てられないよう支払額ｐを算出する。
【０１１９】
続いて、制御部１６は、決定した財の割り当てとクオリティと支払額ｐとを送受信部１１を通じて入札者用装置２に送信する（ステップＳ５０４）。このとき、制御部１６は、オークションに参加した各入札者用装置２に対して、それぞれ対応する財の割り当てとクオリティと支払額ｐとを送信する。
【０１２０】
最後に、制御部１６は、入札者用装置２から選択情報（支払額ｐの承諾又は不承諾）を受信する（ステップＳ５０５）。オークションに参加した全ての入札者の入札者用装置２から選択情報を受信すると（ステップＳ５０６においてＹＥＳ）、オークションに関する全ての処理を終了する。
【０１２１】
次に、図６を参照して、入札者用装置２の動作について説明する。図６は、入札者用装置２の動作を示すフローチャートである。
入札者用装置２の制御部２６は、入札者がオークションに参加する旨の操作入力を入力部２２が検出すると、この検出した操作入力に基づいて、提供する財とこの財のクオリティとを含むタイプθを送受信部２１を通じて開札者用装置１に送信する（図６ステップＳ６０１）。このタイプθの送信動作は、送受信部２１により行われる。送信したタイプθは、記憶部２４に記憶される。
【０１２２】
続いて、入札者用装置２は、開札者用装置１から財の割り当てとクオリティと支払額ｐとを受信する（ステップＳ６０２）。この受信動作は、送受信部２１により行われる。受信した割り当てとクオリティと支払額ｐとは、記憶部２４に記憶される。
次に、制御部２６は、記憶部２４に記憶された財のクオリティと支払額ｐに基づいて効用演算部２５に入札者の効用を算出させる（ステップＳ６０３）。算出した効用は、記憶部２４に記憶される。
【０１２３】
そして、制御部２６は、入札者の効用が正となるかどうかを判定し（ステップＳ６０４）、効用が正の場合、支払額ｐを承諾することを送受信部２１を通じて開札者用装置１に通知する（ステップＳ６０５）。また、制御部２６は、効用が負の場合、入札から降りることを開札者用装置１に通知する（ステップＳ６０６）。以上で入札者用装置２における処理が終了する。
【０１２４】
以上のように、本実施の形態によれば、入札者用装置から受信した財の評価値に基づいて、入札者が売却する財の組み合わせと属性値の組み合わせの実現可能な複数のパターンを生成し、これらのパターンの中から入札者と開札者に最大の効用を与える財の組み合わせと属性値の組み合わせを選択し、選択した組み合わせに基づいて入札者への支払額を算出することにより、複数の属性値を有する複数の財のオークションに対応することが可能となる。
また、本実施の形態では、開札者に最大の効用を与える財の組み合わせと属性値の組み合わせを選択することから、開札者の個人合理性を保証することができる。
【０１２５】
また、本実施の形態では、入札者は、効用が最大となる、すなわち入札者にとって最も利益があるバンドルと属性値の組み合わせを得ることが可能となる。さらに、本実施の形態によれば、入札者にとって不利益となる場合は、入札から降りることを選択することが可能となる。したがって、本実施の形態に係るオークションシステムは、入札者にとってとても使い勝手がよい。
【０１２６】
また、本実施の形態では、ＬＤＳプロトコルを導入することで、単一の入札者が複数の名義を用いる架空名義入札を行っても、入札者が利益を得ることがないようにして、架空名義入札不可能性を実現することができる。ＬＤＳプロトコルにより、架空名義入札不可能性を実現できることは、例えば文献「横尾真他，“架空名義入札に頑健なオークションプロトコル”，情報処理学会論文誌，Vol.43，No.6，p.1814-1824，2002 」や、文献「Makoto Yokoo，et al.，“Robust Combinatorial Auction Protocol Against False-name Bids”，Proceedings of the Seventeenth National Conference on Artifical Intelligence（AAAI-2000）， p.110-115，2000」に開示されている。
【産業上の利用可能性】
【０１２７】
本発明に係る電子入札システムは、政府や企業が複数の要素からなり、また品質などにばらつきが出てくるような仕事を発注する場合において、例えば工事のような入札に適用することができる。一般に、工事は、設計、施工などいくつかの工程を経て仕事が完了し、設計の質や工期などにより支払額が変わる。また、請け負う側では複数の工程を同時に請け負うことにより支払額を下げることができることもある。このような場合に、本発明の電子入札システムで入札を行うことにより、複数の工程とその属性値などを含めて同時に入札することができ、開札者と入札者の双方に利益となる入札が可能となる。
【図面の簡単な説明】
【０１２８】
【図１】本発明の実施の形態に係るオークションシステムの構成を示すブロック図である。
【図２】図１のオークションシステムにおける開札者用装置の１構成例を示すブロック図である。
【図３】図１のオークションシステムにおける入札者用装置の１構成例を示すブロック図である。
【図４】図１のオークションシステムにおける情報の送受を説明するためのシーケンス図である。
【図５】図１のオークションシステムにおける開札者用装置の動作を示すフローチャートである。
【図６】図１のオークションシステムにおける入札者用装置の動作を示すフローチャートである。
【符号の説明】
【０１２９】
１…開札者用装置、２…入札者用装置、３…ネットワーク、１１…送受信部、１２…入力部、１３…表示部、１４…記憶部、１５…支払額演算部、１６…制御部、１７…通信回線、２１…送受信部、２２…入力部、２３…表示部、２４…記憶部、２５…効用演算部、２６…制御部、２７…通信回線。
【技術分野】
【０００１】
本発明は、通信ネットワーク上に分散配置された複数の入札者用装置を用いる複数の入札者が電子的手段によって入札を行う電子入札システム、開札者用装置、入札者用装置、電子入札方法、プログラムおよび記録媒体に関するものである。
【背景技術】
【０００２】
オークションは、資源の効率的な配分を実現するために最も重要なメカニズムの１つである。特に、近年は通信ネットワークを用いた大規模なオークションが一般的になりつつある。通信ネットワークを用いたオークションでは、新しいタイプの不正行為が問題となる。例えば単一の入札者が複数の名義（例えば異なるメールアドレス）を用いて、複数の入札を行うことが容易に可能である。これを架空名義入札と呼ぶ。
【０００３】
そこで、通信ネットワークを用いたオークションにおいて、多様な興味を持つ（すなわち、複数の財に興味を持つ）人が存在する場合でも機能し、かつ架空名義による入札を困難にする技術として、ＰＯＲＦ（Price-Oriented Rationing-Free ）が提案されている（例えば、非特許文献１参照）。このＰＯＲＦプロトコルについて、以下に説明する。
【０００４】
組み合わせオークションの対象領域モデルを定義する。ＰＯＲＦプロトコルでは、単一の買い手（以下、開札者という）０、この開札者に対して売り手（以下、入札者という）の集合Ｎ＝｛１，２，・・・，ｎ｝、入札者が提供する仕事や物等の財ｔの集合Ｔ＝｛ｔ1，・・・，ｔm｝が存在する。各入札者はそれぞれタイプθi を有している。タイプθi は集合Θの要素である。ここで、タイプθi とは、入札者ｉが所有する財に対して、入札者ｉが付与した評価値を意味する。財ｔの入札者への可能な割り当ては、式（１）で表される。
【０００５】
【数１】
【０００６】
ここで、バンドルＢi⊆Ｔ であり、ｉ≠ｋであれば式（２）が成り立つ。なお、バンドルＢとは、任意の財の組み合わせのことを意味する。
【０００７】
【数２】
【０００８】
財の割り当てがバンドルＢiのとき、入札者が入札に要するコストはｃ（θi，Ｂi）で表され、式（３）の条件を満たす。
【０００９】
【数３】
【００１０】
開札者から入札者ｉへの財に関する支払額はｐi で表される。各入札者の効用が準線形であることを仮定すると、各入札者ｉにとっての効用は、ｐi−ｃ（θi，Ｂi） で表される。ここでの入札者の効用とは、支払額ｐi からコストｃ（θi，Ｂi）を引いているため、入札者の利益を表している。また、開札者にとっての効用は式（４）で表される。
【００１１】
【数４】
【００１２】
次に、ＰＯＲＦプロトコルは以下のように定義される。まず、各入札者ｉは、式（５）で表される自分のタイプを申告する。ただし、入札者ｉは真のタイプθi を申告するとは限らない。
【００１３】
【数５】
【００１４】
タイプを申告すると、入札者ｉに関して、任意のバンドルＢ⊆Ｔに対する支払額ｐB,i が決定される。この支払額ｐB,i は、入札者ｉが申告したタイプとは無関係に決定される。なお、支払額ｐB,i は、他者の申告したタイプには依存しても良い。
ここで、Ｂ⊆Ｂ’の場合、式（６）を仮定する。
【００１５】
【数６】
【００１６】
入札者ｉには、式（７）で表される効用を最大化するバンドルＢが割り当てられる。支払額ｐB,i は、式（７）の効用を最大化するバンドルが複数存在する場合には、それらのいずれか１つが割り当てられる。ここで、式（８）は入札者ｉのバンドルＢに対する評価値である。
【００１７】
【数７】
【００１８】
【数８】
【００１９】
割り当て結果は、割り当て可能性を満たすように決定する。すなわち、入札者ｉ，ｊにそれぞれ割り当てられるバンドルＢi，Ｂjに関して、式（９）が成立するように決定される。
【００２０】
【数９】
【００２１】
このようなＰＯＲＦプロトコルによれば、入札者にとっては、バンドルの支払額が自分の申告したタイプとは無関係に決定され、また他者の割り当て結果とは独立に、自分の効用を最大化するバンドルを得ることができる。ＰＯＲＦプロトコルにより通信ネットワークを用いたオークションを実現すると、入札者自身ではバンドルの支払額を操作することができない。すなわち支払額の戦略的操作が不可能となる。
【００２２】
一方、ＰＯＲＦプロトコルでは、各入札者の各バンドルの支払額は、割り当て可能性が満たされるように、すなわち同じ財を同時に複数の入札者に割り当てないよう適切に決定される必要がある。しかし、ＰＯＲＦプロトコルでは、入札者ｉに対して効用を最大化するバンドルが複数存在する場合、そのいずれか１つを割り当てるが、どれを割り当てるかに関しては規定していない。したがって、オークションの主催者は、割り当て可能性が満足されるように、割り当てを調整することが可能である。
【００２３】
ＰＯＲＦプロトコルを用いたオークションにおける支払額の決定例を以下に示す。なお、上述したようにＰＯＲＦプロトコルは戦略的操作不可能であるため、以下の例では各入札者ｉは真のタイプθi を申告するものとする。
【００２４】
単一の財のオークションの場合、唯一のバンドルＢ＝Ｍの支払額は、ｐB,i＝ｍａｘj≠iｖ（Ｂ，θj） で与えられる。このプロトコルはＶｉｃｋｒｅｙオークションと等価である。複数の財の組み合わせオークションの場合、プロトコルの記述の簡単化のため、入札者の集合Ｘと財の集合Ｂに対して、Ｖ*（Ｘ、Ｂ） をＢがＸに最適に割り当てられたときのＸの評価値の合計とする。このとき、入札者への支払額ｐB,i は以下のような式で表される。
ｐB,i＝Ｖ*（Ｎ＼｛ｉ｝，Ｍ）−Ｖ*（Ｎ＼｛ｉ｝，Ｍ＼Ｂ） ・・・（１０）
この式（１０）の支払額の算出は、ＶＣＧ（Vickrey-Clarke-Groves）メカニズムと等価である。
【００２５】
【非特許文献１】Makoto Yokoo，“ Characterization of Strategy/False-name Proof Combinatorial Auction Protocols:Price-oriented, Rationing-free Protocol”，In Proceedings of 19th International Joint Conference on Artifical Intelligence（IJCAI-2003）， p.733-739，2003
【発明の開示】
【発明が解決しようとする課題】
【００２６】
複数の財をオークションにより売却する場合、各財の価値の間に依存関係が存在することが通例である。また、各財に対して品質などの属性値が設定される場合もある。
しかしながら、従来のＰＯＲＦプロトコルにより実現可能な従来のオークションでは、複数の属性値を持つ複数の財のオークションに対応することができないという問題点があった。
【００２７】
また、従来のＰＯＲＦプロトコルにより実現可能な従来のオークションでは、開札者の個人合理性を保証できないという問題点があった。開札者の個人合理性とは、開札者に損失が生じることがない、という意味である。
【００２８】
そこで、本発明は、上述したような課題を解決するためになされたものであり、複数の属性値を有する財に対応可能で、かつ開札者の個人合理性を保証することができる電子入札システム、開札者用装置、入札者用装置、電子入札方法、プログラムおよび記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００２９】
本発明は、財を購入する単一の開札者が使用する開札者用装置と、前記財を提供する複数の入札者が使用する複数の入札者用装置と、前記開札者用装置と前記複数の入札者用装置とを接続するネットワークとを備え、複数の属性値を有する財に対して入札を行う電子入札システムであって、前記入札者用装置は、前記複数の属性値を含む、前記財に対する評価値を前記開札者用装置に送信する第１の送信手段と、前記入札者が売却する財を前記開札者用装置が選択して、この選択された財とその属性値と前記選択された財に対する支払額とを前記開札者用装置から通知されたときに、この通知された属性値と支払額に基づいて前記入札者の効用を算出する効用算出手段と、前記算出された効用に基づいて前記支払額を承諾するか否かを決定する決定手段と、この決定手段の結果を前記開札者用装置に通知する第２の送信手段とを有し、前記開札者用装置は、前記入札者用装置から受信した前記評価値に基づいて、前記入札者が売却する財の組み合わせと属性値の組み合わせの実現可能な複数のパターンを生成する分割セット手段と、これらのパターンの中から前記入札者と前記開札者に最大の効用を与える財の組み合わせと属性値の組み合わせを選択し、選択した組み合わせに基づいて前記入札者への支払額を算出する支払額算出手段と、この支払額算出手段によって選択された財の組み合わせと属性値の組み合わせと前記算出された支払額とを前記入札者用装置に通知する第３の送信手段とを有するものである。
また、本発明の電子入札システムの１構成例において、前記開札者用装置の支払額算出手段は、任意の入札者用装置から提供される前記財に対する支払額を、前記任意の入札者用装置以外の入札者用装置から受信した前記評価値に基づいて算出するものである。
【００３０】
また、本発明は、複数の属性値を有する財を提供する複数の入札者が使用する複数の入札者用装置とネットワークを介して接続され、前記財を購入する開札者が使用する開札者用装置であって、前記複数の属性値を含む、前記財に対する評価値を前記入札者用装置から受信したときに、前記評価値に基づいて、前記入札者が売却する財の組み合わせと属性値の組み合わせの実現可能な複数のパターンを生成する分割セット手段と、これらのパターンの中から前記入札者と前記開札者に最大の効用を与える財の組み合わせと属性値の組み合わせを選択し、選択した組み合わせに基づいて前記入札者への支払額を算出する支払額算出手段と、前記選択された財の組み合わせと属性値の組み合わせと前記算出された支払額とを前記入札者用装置に通知する送信手段とを有するものである。
また、本発明は、財を購入する単一の開札者が使用する開札者用装置とネットワークを介して接続され、複数の属性値を有する財を提供する入札者が使用する入札者用装置であって、前記複数の属性値を含む、前記財に対する評価値を前記開札者用装置に送信する第１の送信手段と、前記入札者が売却する財を前記開札者用装置が選択して、この選択された財とその属性値と前記選択された財に対する支払額とを前記開札者用装置から通知されたときに、この通知された属性値と支払額に基づいて前記入札者の効用を算出する効用算出手段と、前記算出された効用に基づいて前記支払額を承諾するか否かを決定する決定手段と、この決定手段の結果を前記開札者用装置に通知する第２の送信手段とを有するものである。
【００３１】
また、本発明は、財を購入する単一の開札者が使用する開札者用装置と、前記財を提供する複数の入札者が使用する複数の入札者用装置と、前記開札者用装置と前記複数の入札者用装置とを接続するネットワークとを備えた電子入札システムにおいて、複数の属性値を有する財に対して入札を行う電子入札方法であって、前記入札者用装置が、前記複数の属性値を含む、前記財に対する評価値を前記開札者用装置に送信する第１の送信手順と、前記開札者用装置が、前記入札者用装置から受信した前記評価値に基づいて、前記入札者が売却する財の組み合わせと属性値の組み合わせの実現可能な複数のパターンを生成する分割セット手順と、前記開札者用装置が、前記パターンの中から前記入札者と前記開札者に最大の効用を与える財の組み合わせと属性値の組み合わせを選択し、選択した組み合わせに基づいて前記入札者への支払額を算出する算出手順と、前記開札者用装置が、前記選択された財の組み合わせと属性値の組み合わせと前記算出された支払額とを前記入札者用装置に通知する通知手順と、前記入札者用装置が、前記選択された財とその属性値と前記選択された財に対する支払額とを前記開札者用装置から通知されたときに、この通知された属性値と支払額に基づいて前記入札者の効用を算出する効用算出手順と、前記入札者用装置が、前記算出された効用に基づいて前記支払額を承諾するか否かを決定する決定手順と、前記入札者用装置が、この決定手順の結果を前記開札者用装置に通知する第２の送信手順とを有するものである。
また、本発明の電子入札方法の１構成例において、前記算出手順は、任意の入札者用装置から提供される前記財に対する支払額を、前記任意の入札者用装置以外の入札者用装置から受信した前記評価値に基づいて算出するものである。
【００３２】
また、本発明の電子入札プログラムは、前記入札者用装置が、前記財の複数の属性値を含む、前記財に対する評価値を前記開札者用装置に送信する第１の送信手順と、前記開札者用装置が、前記入札者用装置から受信した前記評価値に基づいて、前記入札者が売却する財の組み合わせと属性値の組み合わせの実現可能な複数のパターンを生成する分割セット手順と、前記開札者用装置が、前記パターンの中から前記入札者と前記開札者に最大の効用を与える財の組み合わせと属性値の組み合わせを選択し、選択した組み合わせに基づいて前記入札者への支払額を算出する算出手順と、前記開札者用装置が、前記選択された財の組み合わせと属性値の組み合わせと前記算出された支払額とを前記入札者用装置に通知する通知手順と、前記入札者用装置が、前記選択された財とその属性値と前記選択された財に対する支払額とを前記開札者用装置から通知されたときに、この通知された属性値と支払額に基づいて前記入札者の効用を算出する効用算出手順と、前記入札者用装置が、前記算出された効用に基づいて前記支払額を承諾するか否かを決定する決定手順と、前記入札者用装置が、この決定手順の結果を前記開札者用装置に通知する第２の送信手順とをコンピュータに実行させるようにしたものである。
また、本発明の記録媒体は、電子入札プログラムを記録したものである。
【発明の効果】
【００３３】
本発明によれば、入札者用装置から受信した財の評価値に基づいて、開札者用装置が、入札者が売却する財の組み合わせと属性値の組み合わせの実現可能な複数のパターンを生成し、これらのパターンの中から入札者と開札者に最大の効用を与える財の組み合わせと属性値の組み合わせを選択し、選択した組み合わせに基づいて入札者への支払額を算出することにより、複数の属性値を有する複数の財のオークションに対応することが可能となる。また、本発明では、開札者に最大の効用を与える財の組み合わせと属性値の組み合わせを選択することから、開札者の個人合理性を保証することができる。また、本発明では、入札者にとって使い勝手がよいオークションを実現することができる。さらに、本発明では、単一の入札者が複数の名義を用いる架空名義入札を行っても、入札者が利益を得ることがないようにして、架空名義入札不可能性を実現することができる。
【発明を実施するための最良の形態】
【００３４】
［発明の原理］
本発明は、複数の属性値を持った複数の財を電子入札により売却する際に、全ての入札者の入札値とそれに対応するクオリティを基に、各入札者ごとに各クオリティに対する支払額のリストを決定し、そこから入札者がクオリティと入札額を決定することを特徴とするものである。なお、クオリティとは、財の属性値に含まれるものであり、特に財の品質等を意味する。
【００３５】
従来、オークションのプロトコルが誘因両立であるとは、真のタイプ／評価値を宣言することが入札者にとって最良の戦略であることを意味している。本発明では、誘因両立の定義を拡張して、架空名義入札に対する頑健性も示すことができるようにした。すなわち、オークションプロトコルが誘因両立とは、唯一つのＩＤを用いて真のタイプを宣言することが各入札者にとって最良の戦略であることを意味している。従来の定義と拡張した定義を区別するために、従来の定義を戦略的操作不可能性と呼び、本発明による拡張した定義を架空名義入札不可能性と呼ぶ。
オークションプロトコルが個人合理的であるとは、支配戦略均衡においてはどの入札者も損失が生じることがない、すなわち入札に要するコストが支払額を超えることがない、という意味である。オークションでは、個人合理性は不可欠である。入札者は、財を勝ち取るために使う費用よりも得られる金額が少ないオークションには参加したいとは思わない。それゆえ、本発明では、個人合理的なプロトコルのみに焦点を当てる。また、入札者から入力されるタイプθが同じであれば、常に同じ財の割り当てと支払額が得られるプロトコルのみを扱う。
【００３６】
［拡張ＬＤＳプロトコル］
本発明の拡張ＬＤＳ（Leveled Division Set：レベル付分割セット）プロトコルのモデル、すなわち環境を以下のように定義する。
【００３７】
本発明の拡張ＰＯＲＦプロトコルでは、単一の買い手（開札者）０と、この開札者に対して売り手（入札者）の集合Ｎ＝｛１，２，・・・，ｎ｝が存在し、また入札者が提供する仕事や物等の財ｔの集合Ｔ＝｛ｔ1，・・・，ｔm｝が存在する。各入札者はそれぞれタイプθi を有している。タイプθi は集合Θの要素である。タイプθi とは、入札者ｉが所有する財に対して、入札者ｉが付与した評価値を意味する。
【００３８】
各財ｔj に対して、入札者によりクオリティｑj が定義される。このクオリティｑj は集合Ｑの要素である。クオリティｑj とは、属性値に含まれるものであり、特に財ｔの品質などを意味している。入札者への財ｔの可能な割り当ては、式（１１）のように表される。
【００３９】
【数１０】
【００４０】
ここで、バンドルＢi⊆Ｔであり、ｉ≠ｋであれば式（１２）が成り立つ。なお、バンドルＢとは、任意の財の組み合わせのことを意味する。
【００４１】
【数１１】
【００４２】
クオリティのプロファイルは式（１３）で表される。クオリティプロファイルとは、財のクオリティの集合を意味し、式（１３）のようにベクトルで表記される。
【００４３】
【数１２】
【００４４】
式（１３）のクオリティプロファイルとバンドルＢi＝｛ｔi,1，ｔi,2，．．．｝に対して、クオリティプロファイルへのバンドルＢiの射影（projection ）を以下の式（１４）で表す。
【００４５】
【数１３】
【００４６】
入札者に割り当てる財がバンドルＢiで、このときに達成されるクオリティプロファイルが式（１５）の場合、入札者がオークションの入札に要するコストは式（１６）のように表される。ここで、式（１６）のコストｃは式（１７）により正規化されているものとする。
【００４７】
【数１４】
【００４８】
【数１５】
【００４９】
【数１６】
【００５０】
クオリティプロファイルが式（１３）のように表されるとき、開札者０のグロスの効用は式（１８）で表される。この開札者０のグロスの効用とは、開札者にとってどれほど価値があるのかを示す指標である。
【００５１】
【数１７】
【００５２】
開札者から入札者ｉへの財に関する支払額はｐi で表される。各入札者の効用が準線形であることを仮定すると、各入札者ｉにとっての効用は、支払額ｐi からコストｃを除いた式（１９）で表される。また、開札者にとってのネットワークの効用は、式（１８）のグロスの効用から支払額を除いた式（２０）で表される。
【００５３】
【数１８】
【００５４】
【数１９】
【００５５】
割り当てられてない財ｔj のクオリティをｑ0∈Ｑ とする。この場合の開札者の効用は式（２１）となり、割り当てられない財ｔj のクオリティプロファイルは式（２２）となる。
以上が、本発明の拡張ＰＯＲＦプロトコルのモデル（環境）の定義である。
【００５６】
【数２０】
【００５７】
【数２１】
【００５８】
財のクオリティを表すパラメータはｑjのただ一つであるが、これはクオリティが一次元であることを示すのではなく、ｑjは複数の属性値を持つベクトルとすることができる。このようなモデルの具体例について述べる。
入札者が二人、すなわち入札者の集合Ｎ＝｛１，２｝が存在し、財が二つ、すなわち財の集合Ｔ＝｛ｔ1，ｔ2｝が存在し、クオリティプロファイルが式（２３）であり、ｑj が一次元の場合の入札者１のコスト関数は、式（２４）〜（２６）のように表すことができる。
【００５９】
【数２２】
【００６０】
ｃ（θ1,｛ｔ1｝,（ｑ1））＝（１／４）ｑ1 ・・・（２４）
ｃ（θ1,｛ｔ2｝,（ｑ2））＝（１／２）ｑ2 ・・・（２５）
ｃ（θ1,｛ｔ1,ｔ2｝,（ｑ1,ｑ2））＝（１／４）ｑ1＋（１／２）ｑ2
・・・（２６）
【００６１】
また、開札者のグロスの効用が式（２７）であり、入札者２のコストは常に入札者１のコストよりも大きいものとする。このような場合に、財ｔ1とｔ2の両方が式（２８）のクオリティプロファイルで入札者１に割り当てられたとすると、入札者１のコストはｃ（θ1,｛ｔ1，ｔ2｝,（４，４））＝２となり、社会的余剰はＶ（（４，４））−ｃ（θ1,｛ｔ1，ｔ2｝,（４，４））＝２となる。
【００６２】
【数２３】
【００６３】
【数２４】
【００６４】
［支払額ｐの決定方法］
次に、入札者への支払額ｐの決定方法について説明する。まず、参照入札者という特別な入札者を導入する。この参照入札者は以下のような（Ａ）、（Ｂ）、（Ｃ）の特性を有する。
【００６５】
（Ａ）財を買い取る開札者は、財ｔk がクオリティｑk で参照入札者に割り当てられたときのコストの上界値を知っている。すなわち、開札者は、式（２９）が成立しているときに、コストｃ（θr，｛ｔk｝，（ｑk）） の上界値ｃr,tk,qk を知っている。
【００６６】
【数２５】
【００６７】
（Ｂ）参照入札者のコストは加算的である。すなわち、任意のバンドルＢ、式（３０）のクオリティプロファイルに対して、式（３１）が成り立つ。これにより、式（３２）が成り立つ。
【００６８】
【数２６】
【００６９】
【数２７】
【００７０】
【数２８】
【００７１】
（Ｃ）式（３３）に示す任意のクオリティプロファイルに対して、式（３４）が成り立つ。これはどんなクオリティに対しても、全ての財が参照入札者に割り当てられて、支払額が上界値の合計と等しくなったとき、開札者のネットワークの効用は負にならないことを意味する。
【００７２】
【数２９】
【００７３】
【数３０】
【００７４】
次に、入札者が入力したタイプθに基づいて、入札者へ割り当て可能な財の組み合わせとクオリティの組み合わせを示すＬＤＳを次の（Ｄ）、（Ｅ）のように定義する。
（Ｄ）まず、各組み合わせパターンに固有のレベル１，２，・・・，ｍａｘ＿ｌｅｖｅｌを定義する。
（Ｅ）各レベルに対して、財の組み合わせパターンを示す分割Ｄl と式（３５）に示すクオリティプロファイルを定義する。
【００７５】
【数３１】
【００７６】
各レベルの分割は以下の（Ｆ）、（Ｇ）の性質を満たすものとする。
（Ｆ）Ｄ1 ＝Ｔ、すなわちレベル１の分割は全ての財のバンドルのみからなる集合である。
（Ｇ）各レベルとその分割に対して、その分割に含まれる複数のバンドルの和は常により小さいレベルの分割に含まれ、また同じクオリティである。すなわち、式（３６）が成立し、またＢu＝∪B∈D'で∀ｌ＞１、∀Ｄ’⊆Ｄlとなる。そのとき、Ｂu∈Ｄl'かつ式（３７）が成立する分割Ｄl'があるレベルｌ’＜ｌが存在する。
【００７７】
【数３２】
【００７８】
【数３３】
【００７９】
表１と表２にレベル付分割セットの例を示す。表１では財ｔの数は２で、クオリティは１か２である。また、表２では財ｔの数は３で、クオリティは１か２である。
【００８０】
【表１】
【００８１】
【表２】
【００８２】
例えば、表１において、分割｛（ｔ1，ｔ2）｝は一人の入札者に財ｔ1，ｔ2が割り当てられることを示す。また、分割｛（ｔ1），（ｔ2）｝は一人の入札者に財ｔ1 が割り当てられ、別の入札者に財ｔ2 が割り当てられることを示す。表２の場合も同様である。また、表１において、分割｛（ｔ1，ｔ2）｝に対してクオリティ（ｑ1，ｑ2）が（２，２）であることは、財ｔ1のクオリティｑ1が２であり、財ｔ2のクオリティｑ2も２であることを示す。
【００８３】
分割Ｄl ＝｛Ｂl,1，Ｂl,2，・・・｝と財の実現可能な割り当てを示す式（３８）に対して、以下の条件（Ｈ）、（Ｉ）が満たされたときに分割Ｄl の元で式（３８）が許されると言う。
【００８４】
【数３４】
【００８５】
（Ｈ）ある分割中の同じバンドルに属する財は、同じ入札者に割り当てられなければならない。また、もし同じ分割中の異なるバンドルに属する財は、参照入札者に割り当てられる場合以外は異なる入札者に割り当てられなければならない。すなわち、ｉ≠ｒで、式（３９）が成立するならば、Ｂl,k＝Ｂｉであり、式（４０）が成立するならば、Ｂl,k⊆Ｂrである。
【００８６】
【数３５】
【００８７】
【数３６】
【００８８】
（Ｉ）もし財が分割のどのセットにも属さないならば、その財は参照入札者に割り当てられる。すなわち、全ての財ｔk に対して、もし∀Ｂl,k∈Ｄlと式（４１）が成り立つならば、ｔk∈Ｂrである。
【００８９】
【数３７】
【００９０】
また、分割Ｄl で許される割り当ての集合をレベルｌでの可能な割り当てＳＢl と記述する。
以上のＬＤＳプロトコルを実行するためには、開札者はあらかじめレベル付分割セットを決定しておく必要がある。入札者ｉは前述の式（５）で表される自分のタイプを宣言する。このタイプは真のタイプθi と異なっていてもよい。
【００９１】
財が割り当てられるべきレベルを探索するために、開札者はプロシージャＬＤＳ（ｌ）を呼び出す。ＬＤＳ（ｌ）は再帰的なプロシージャになっており、以下の（Ｊ）、（Ｋ）、（Ｌ）の通り定義する。
【００９２】
（Ｊ）∃Ｂx∈Ｄlと式（４２）に示すコストの条件を満たすただ一人の入札者ｘ∈Ｎが存在する場合は、後述するＶＣＧ（ｌ）プロシージャとＬＤＳ（ｌ＋１）とを比較して、入札者ｘに対してより大きな効用を与えるほうを選択する。このときの入札者ｘをビボタル入札者と呼ぶ。ＬＤＳ（ｌ＋１）の結果が選択された揚合は、入札者ｘ以外の通常の入札者には財は割り当てられない。入札者ｘに割り当てられなかった財は、前述の参照入札者に割り当てられる。
【００９３】
【数３８】
【００９４】
（Ｋ）∃Ｂx1∈Ｄlと∃Ｂx2∈Ｄlと式（４３）、式（４４）に示すコストの条件を満たす少なくとも二人の入札者ｘ1，ｘ2∈Ｎ、ｘ1≠ｘ2が存在する場合は、後述するＶＣＧ（ｌ）プロシージャを適用する。
【００９５】
【数３９】
【００９６】
【数４０】
【００９７】
（Ｌ）前記の（Ｊ）、（Ｋ）の条件を満たさない場合は、ＬＤＳ（ｉ＋１）を実行する。そして、ｉ＝ｍａｘ＿ｌｅｖｅｌの場合は終了する。
【００９８】
次に、プロシージャＬＤＳ（ｌ）中で用いられるＶＣＧ（ｌ）を以下のように定義する。プロシージャＶＣＧ（ｌ）では、式（４５）に示す開札者の効用を最大化するような式（４６）の割り当てを選ぶ。
【００９９】
【数４１】
【０１００】
【数４２】
【０１０１】
入札者ｘ（ｘ≠ｒ）への支払い額ｐx は式（４７）のように計算される。式（４８）はレベルｌでの可能な割り当てＳＢl の中で入札者ｘを除いたときに社会的余剰を最大化する割り当てを示している。
以上のようにして、本発明では、入札者への財の割り当てと財のクオリティと支払額ｐとを開発者側で決定することができる。
【０１０２】
【数４３】
【０１０３】
【数４４】
【０１０４】
［実施の形態］
以下、本発明の実施の形態について図面を参照して説明する。図１は、本実施の形態に係るオークションシステムの構成を示すブロック図である。
本実施の形態のオークションシステムは、オークションを取り仕切るオークショニアや、入札者から仕事や物等の財を買う買い取り者である開札者が用いる開札者用装置１と、開札者に財を提供する複数の入札者がそれぞれ用いる複数の入札者用装置２と、開札者用装置１と入札者用装置２とを接続するネットワーク３とから構成される。
【０１０５】
図２は、開札者用装置１の１構成例を示すブロック図である。開札者用装置１は、ネットワーク３を介して入札者用装置２と各種情報の送受信を行う送受信部１１と、開札者の操作入力を検出する入力部１２と、オークションに関する各種情報を表示する表示部１３と、入札者用装置２から受信するタイプ、財およびこの財の属性値などのオークションに関する各種情報を記憶する記憶部１４と、入札者が提供する財に対する支払額を算出する支払額演算部１５と、これらの開札者用装置１の各機能部の動作を制御する制御部１６とを備え、これらの開札者用装置１の各機能部はバス等の公知の通信回線１７により接続されている。支払額演算部１５は、分割セット手段と支払額算出手段を構成し、送受信部１１は、第３の送信手段を構成している。
【０１０６】
このような開札者用装置１は、ＣＰＵ等の中央処理装置、記憶装置、入札者用装置２と各種情報の送受を行うＩ／Ｆ装置、キーボード、マウス等の入力装置、ＬＣＤ（Liquid Crystal Display）等の表示装置などを備えたコンピュータと、このコンピュータにインストールされたプログラムとから構成されている。中央処理装置がメモリに格納されたプログラムを実行することにより、すなわちハードウェア資源とソフトウェアが協働することにより、上述した送受信部１１、入力部１２、表示部１３、記憶部１４、支払額演算部１５、制御部１６および通信回線１７が実現される。
【０１０７】
図３は、入札者用装置２の１構成例を示すブロック図である。入札者用装置２は、ネットワーク３を介して開札者用装置１と各種情報の送受信を行う送受信部２１と、入札者の操作入力を検出する入力部２２と、オークションに関する各種情報を表示する表示部２３と、開札者用装置１から受信する支払額などのオークションに関する各種情報を記憶する記憶部２４と、開札者用装置１により算出された支払額に基づいて財の効用を算出する効用演算部２５と、これらの入札者用装置２の各機能部の動作を制御する制御部２６とを備え、これらの入札者用装置２の各機能部はバス等の公知の通信回線２７により接続されている。効用演算部２５は、効用算出手段を構成し、送受信部２１は、第１の送信手段と第２の送信手段を構成している。
【０１０８】
このような入札者用装置２は、ＣＰＵ等の中央処理装置、記憶装置、開札者用装置１と各種情報の送受を行うＩ／Ｆ装置、キーボード、マウス等の入力装置、ＬＣＤ等の表示装置などを備えたコンピュータと、このコンピュータにインストールされたプログラムとから構成されている。中央処理装置がメモリに格納されたプログラムを実行することにより、すなわちハードウェア資源とソフトウェアが協働することにより、上述した送受信部２１、入力部２２、表示部２３、記憶部２４、効用演算部２５、制御部２６および通信回線２７が実現される。
【０１０９】
ネットワーク３は、例えばインターネットやＬＡＮ（Local Area Network）、ＷＡＮ（Wide Area Network）等の公知の電気通信システムから構成される。
【０１１０】
次に、図４を参照して本実施の形態のオークションシステムの情報の送受信について説明する。図４は、オークションシステムの情報の送受信を説明するためのシーケンス図である。
まず、開札者は、あらかじめ開札者用装置１を通して（またはその他の何らかの通知手段により）、競争入札を実施する旨の案内を各入札者の入札者用装置２に通知しておく。
【０１１１】
競争入札が開始されると、入札者は入札者用装置２に自身のタイプθを入力する。入札者用装置２の制御部２６は、入力部２２から入力された入札者のタイプθを送受信部２１を通じて開札者用装置１に通知する（図４ステップＳ４０１）。ここで、タイプθとは、入札者が提供する財のコストなど入札者の財に対する評価を表すものであり、入札者が提供する仕事や物等の財と、この財の品質などを表すクオリティ（属性値）とを少なくとも含む。
【０１１２】
なお、本発明の拡張ＰＯＲＦプロトコルによれば、各入札者にとっては真のタイプを入力することが最良の戦略であるため、各入札者が入力するタイプは真の評価値、すなわちコストとしてよい。よって、入札者は、複数の財の全ての組み合わせの、その全てのクオリティに関してコストを入力することとする。
【０１１３】
開札者用装置１の制御部１６は、受信したタイプθを記憶部１４に格納し、このタイプθに基づいて入札者への財の割り当てとクオリティと支払額ｐとを支払額演算部１５に決定させて、決定した財の割り当てとクオリティと支払額ｐとを送受信部１１を通じて入札者用装置２に通知する（ステップＳ４０２）。ここで、制御部１６は、入札に参加する全ての入札者の入札者用装置２からタイプθを受信してから、支払額ｐを算出させる。支払額演算部１５は、前述の支払額ｐの決定方法に基づいて入札者への財の割り当てとクオリティと支払額ｐを入札者毎に決定する。
【０１１４】
入札者用装置２の制御部２６は、開札者用装置１から受信した割り当てとクオリティと支払額ｐとを記憶部２４に格納し、このクオリティと支払額ｐに基づいて効用演算部２５に入札者の効用を算出させて、効用が正の場合、すなわち入札者に損失が生じない場合には、支払額ｐを承諾することを送受信部２１を通じて開札者用装置１に通知し、効用が負の場合、すなわち入札者に損失が生じる場合には、入札から降りることを開札者用装置１に通知する（ステップＳ４０３）。効用演算部２５は、前述の式（１９）により入札者の効用を算出する。このようにすることにより、本実施の形態では、複数の属性値を有する複数の財のオークションに対応することが可能となる。
【０１１５】
次に、図５を参照して、開札者用装置１の動作について説明する。図５は、開札者用装置１の動作を示すフローチャートである。
まず、開札者用装置１は、オークションに参加する各入札者の入札者用装置２からそれぞれタイプθを受信する（図５ステップＳ５０１）。ネットワーク３を通じて入札者用装置２から送信されたタイプθは、送受信部１１により受信されて、記憶部１４に格納される。
【０１１６】
この受信動作は、オークションに参加する全ての入札者の入札者用装置２からタイプθを受信するまで行われる。すなわち、開札者用装置１の制御部１６は、オークションに参加する全ての入札者の入札者用装置２からタイプθを受信したかどうかを判定し（ステップＳ５０２）、タイプθを受信していない場合は（ステップＳ５０２においてＮＯ）、ステップＳ５０１の処理に戻る。
【０１１７】
なお、全ての入札者のタイプθを受信したかどうかは、あらかじめ競争入札に参加する入札者を特定しておいて、これら特定の入札者の入札者用装置２からタイプθを受信したかどうかで判断すればよい。また、あらかじめ入札の終了時刻を設定しておき、その終了時刻までにタイプθを送信した入札者を競争入札に参加する入札者とし、終了時刻が経過した時点で全ての入札者のタイプθを受信したと見なしてもよい。
【０１１８】
制御部１６は、全ての入札者からタイプθを受信すると、受信したタイプθに基づいて入札者への財の割り当てとクオリティと支払額ｐとを支払額演算部１５に決定させる（ステップＳ５０３）。この割り当てとクオリティと支払額ｐとは記憶部１４に記憶される。財の割り当てとクオリティと支払額ｐとは、オークションに参加した入札者用装置２毎（入札者毎）に決定される。このとき、支払額演算部１４は、同一の財が複数の入札者に割り当てられないよう支払額ｐを算出する。
【０１１９】
続いて、制御部１６は、決定した財の割り当てとクオリティと支払額ｐとを送受信部１１を通じて入札者用装置２に送信する（ステップＳ５０４）。このとき、制御部１６は、オークションに参加した各入札者用装置２に対して、それぞれ対応する財の割り当てとクオリティと支払額ｐとを送信する。
【０１２０】
最後に、制御部１６は、入札者用装置２から選択情報（支払額ｐの承諾又は不承諾）を受信する（ステップＳ５０５）。オークションに参加した全ての入札者の入札者用装置２から選択情報を受信すると（ステップＳ５０６においてＹＥＳ）、オークションに関する全ての処理を終了する。
【０１２１】
次に、図６を参照して、入札者用装置２の動作について説明する。図６は、入札者用装置２の動作を示すフローチャートである。
入札者用装置２の制御部２６は、入札者がオークションに参加する旨の操作入力を入力部２２が検出すると、この検出した操作入力に基づいて、提供する財とこの財のクオリティとを含むタイプθを送受信部２１を通じて開札者用装置１に送信する（図６ステップＳ６０１）。このタイプθの送信動作は、送受信部２１により行われる。送信したタイプθは、記憶部２４に記憶される。
【０１２２】
続いて、入札者用装置２は、開札者用装置１から財の割り当てとクオリティと支払額ｐとを受信する（ステップＳ６０２）。この受信動作は、送受信部２１により行われる。受信した割り当てとクオリティと支払額ｐとは、記憶部２４に記憶される。
次に、制御部２６は、記憶部２４に記憶された財のクオリティと支払額ｐに基づいて効用演算部２５に入札者の効用を算出させる（ステップＳ６０３）。算出した効用は、記憶部２４に記憶される。
【０１２３】
そして、制御部２６は、入札者の効用が正となるかどうかを判定し（ステップＳ６０４）、効用が正の場合、支払額ｐを承諾することを送受信部２１を通じて開札者用装置１に通知する（ステップＳ６０５）。また、制御部２６は、効用が負の場合、入札から降りることを開札者用装置１に通知する（ステップＳ６０６）。以上で入札者用装置２における処理が終了する。
【０１２４】
以上のように、本実施の形態によれば、入札者用装置から受信した財の評価値に基づいて、入札者が売却する財の組み合わせと属性値の組み合わせの実現可能な複数のパターンを生成し、これらのパターンの中から入札者と開札者に最大の効用を与える財の組み合わせと属性値の組み合わせを選択し、選択した組み合わせに基づいて入札者への支払額を算出することにより、複数の属性値を有する複数の財のオークションに対応することが可能となる。
また、本実施の形態では、開札者に最大の効用を与える財の組み合わせと属性値の組み合わせを選択することから、開札者の個人合理性を保証することができる。
【０１２５】
また、本実施の形態では、入札者は、効用が最大となる、すなわち入札者にとって最も利益があるバンドルと属性値の組み合わせを得ることが可能となる。さらに、本実施の形態によれば、入札者にとって不利益となる場合は、入札から降りることを選択することが可能となる。したがって、本実施の形態に係るオークションシステムは、入札者にとってとても使い勝手がよい。
【０１２６】
また、本実施の形態では、ＬＤＳプロトコルを導入することで、単一の入札者が複数の名義を用いる架空名義入札を行っても、入札者が利益を得ることがないようにして、架空名義入札不可能性を実現することができる。ＬＤＳプロトコルにより、架空名義入札不可能性を実現できることは、例えば文献「横尾真他，“架空名義入札に頑健なオークションプロトコル”，情報処理学会論文誌，Vol.43，No.6，p.1814-1824，2002 」や、文献「Makoto Yokoo，et al.，“Robust Combinatorial Auction Protocol Against False-name Bids”，Proceedings of the Seventeenth National Conference on Artifical Intelligence（AAAI-2000）， p.110-115，2000」に開示されている。
【産業上の利用可能性】
【０１２７】
本発明に係る電子入札システムは、政府や企業が複数の要素からなり、また品質などにばらつきが出てくるような仕事を発注する場合において、例えば工事のような入札に適用することができる。一般に、工事は、設計、施工などいくつかの工程を経て仕事が完了し、設計の質や工期などにより支払額が変わる。また、請け負う側では複数の工程を同時に請け負うことにより支払額を下げることができることもある。このような場合に、本発明の電子入札システムで入札を行うことにより、複数の工程とその属性値などを含めて同時に入札することができ、開札者と入札者の双方に利益となる入札が可能となる。
【図面の簡単な説明】
【０１２８】
【図１】本発明の実施の形態に係るオークションシステムの構成を示すブロック図である。
【図２】図１のオークションシステムにおける開札者用装置の１構成例を示すブロック図である。
【図３】図１のオークションシステムにおける入札者用装置の１構成例を示すブロック図である。
【図４】図１のオークションシステムにおける情報の送受を説明するためのシーケンス図である。
【図５】図１のオークションシステムにおける開札者用装置の動作を示すフローチャートである。
【図６】図１のオークションシステムにおける入札者用装置の動作を示すフローチャートである。
【符号の説明】
【０１２９】
１…開札者用装置、２…入札者用装置、３…ネットワーク、１１…送受信部、１２…入力部、１３…表示部、１４…記憶部、１５…支払額演算部、１６…制御部、１７…通信回線、２１…送受信部、２２…入力部、２３…表示部、２４…記憶部、２５…効用演算部、２６…制御部、２７…通信回線。
【特許請求の範囲】
【請求項１】
財を購入する単一の開札者が使用する開札者用装置と、前記財を提供する複数の入札者が使用する複数の入札者用装置と、前記開札者用装置と前記複数の入札者用装置とを接続するネットワークとを備え、複数の属性値を有する財に対して入札を行う電子入札システムであって、
前記入札者用装置は、
前記複数の属性値を含む、前記財に対する評価値を前記開札者用装置に送信する第１の送信手段と、
前記入札者が売却する財を前記開札者用装置が選択して、この選択された財とその属性値と前記選択された財に対する支払額とを前記開札者用装置から通知されたときに、この通知された属性値と支払額に基づいて前記入札者の効用を算出する効用算出手段と、
前記算出された効用に基づいて前記支払額を承諾するか否かを決定する決定手段と、
この決定手段の結果を前記開札者用装置に通知する第２の送信手段とを有し、
前記開札者用装置は、
前記入札者用装置から受信した前記評価値に基づいて、前記入札者が売却する財の組み合わせと属性値の組み合わせの実現可能な複数のパターンを生成する分割セット手段と、
これらのパターンの中から前記入札者と前記開札者に最大の効用を与える財の組み合わせと属性値の組み合わせを選択し、選択した組み合わせに基づいて前記入札者への支払額を算出する支払額算出手段と、
この支払額算出手段によって選択された財の組み合わせと属性値の組み合わせと前記算出された支払額とを前記入札者用装置に通知する第３の送信手段とを有することを特徴とする電子入札システム。
【請求項２】
請求項１記載の電子入札システムにおいて、
前記開札者用装置の支払額算出手段は、任意の入札者用装置から提供される前記財に対する支払額を、前記任意の入札者用装置以外の入札者用装置から受信した前記評価値に基づいて算出することを特徴とする電子入札システム。
【請求項３】
複数の属性値を有する財を提供する複数の入札者が使用する複数の入札者用装置とネットワークを介して接続され、前記財を購入する開札者が使用する開札者用装置であって、
前記複数の属性値を含む、前記財に対する評価値を前記入札者用装置から受信したときに、前記評価値に基づいて、前記入札者が売却する財の組み合わせと属性値の組み合わせの実現可能な複数のパターンを生成する分割セット手段と、
これらのパターンの中から前記入札者と前記開札者に最大の効用を与える財の組み合わせと属性値の組み合わせを選択し、選択した組み合わせに基づいて前記入札者への支払額を算出する支払額算出手段と、
前記選択された財の組み合わせと属性値の組み合わせと前記算出された支払額とを前記入札者用装置に通知する送信手段とを有することを特徴とする開札者用装置。
【請求項４】
請求項３記載の開札者用装置において、
前記支払額算出手段は、任意の入札者用装置から提供される前記財に対する支払額を、前記任意の入札者用装置以外の入札者用装置から受信した前記評価値に基づいて算出することを特徴とする開札者用装置。
【請求項５】
財を購入する単一の開札者が使用する開札者用装置とネットワークを介して接続され、複数の属性値を有する財を提供する入札者が使用する入札者用装置であって、
前記複数の属性値を含む、前記財に対する評価値を前記開札者用装置に送信する第１の送信手段と、
前記入札者が売却する財を前記開札者用装置が選択して、この選択された財とその属性値と前記選択された財に対する支払額とを前記開札者用装置から通知されたときに、この通知された属性値と支払額に基づいて前記入札者の効用を算出する効用算出手段と、
前記算出された効用に基づいて前記支払額を承諾するか否かを決定する決定手段と、
この決定手段の結果を前記開札者用装置に通知する第２の送信手段とを有することを特徴とする入札者用装置。
【請求項６】
財を購入する単一の開札者が使用する開札者用装置と、前記財を提供する複数の入札者が使用する複数の入札者用装置と、前記開札者用装置と前記複数の入札者用装置とを接続するネットワークとを備えた電子入札システムにおいて、複数の属性値を有する財に対して入札を行う電子入札方法であって、
前記入札者用装置が、前記複数の属性値を含む、前記財に対する評価値を前記開札者用装置に送信する第１の送信手順と、
前記開札者用装置が、前記入札者用装置から受信した前記評価値に基づいて、前記入札者が売却する財の組み合わせと属性値の組み合わせの実現可能な複数のパターンを生成する分割セット手順と、
前記開札者用装置が、前記パターンの中から前記入札者と前記開札者に最大の効用を与える財の組み合わせと属性値の組み合わせを選択し、選択した組み合わせに基づいて前記入札者への支払額を算出する算出手順と、
前記開札者用装置が、前記選択された財の組み合わせと属性値の組み合わせと前記算出された支払額とを前記入札者用装置に通知する通知手順と、
前記入札者用装置が、前記選択された財とその属性値と前記選択された財に対する支払額とを前記開札者用装置から通知されたときに、この通知された属性値と支払額に基づいて前記入札者の効用を算出する効用算出手順と、
前記入札者用装置が、前記算出された効用に基づいて前記支払額を承諾するか否かを決定する決定手順と、
前記入札者用装置が、この決定手順の結果を前記開札者用装置に通知する第２の送信手順とを有することを特徴とする電子入札方法。
【請求項７】
請求項６記載の電子入札システムにおいて、
前記算出手順は、任意の入札者用装置から提供される前記財に対する支払額を、前記任意の入札者用装置以外の入札者用装置から受信した前記評価値に基づいて算出することを特徴とする電子入札方法。
【請求項８】
財を購入する単一の開札者が使用する開札者用装置と、前記財を提供する複数の入札者が使用する複数の入札者用装置と、前記開札者用装置と前記複数の入札者用装置とを接続するネットワークとを備え、複数の属性値を有する財に対して入札を行う電子入札システムの前記開札者用装置と前記入札者用装置としてコンピュータを機能させる電子入札プログラムであって、
前記入札者用装置が、前記財の複数の属性値を含む、前記財に対する評価値を前記開札者用装置に送信する第１の送信手順と、
前記開札者用装置が、前記入札者用装置から受信した前記評価値に基づいて、前記入札者が売却する財の組み合わせと属性値の組み合わせの実現可能な複数のパターンを生成する分割セット手順と、
前記開札者用装置が、前記パターンの中から前記入札者と前記開札者に最大の効用を与える財の組み合わせと属性値の組み合わせを選択し、選択した組み合わせに基づいて前記入札者への支払額を算出する算出手順と、
前記開札者用装置が、前記選択された財の組み合わせと属性値の組み合わせと前記算出された支払額とを前記入札者用装置に通知する通知手順と、
前記入札者用装置が、前記選択された財とその属性値と前記選択された財に対する支払額とを前記開札者用装置から通知されたときに、この通知された属性値と支払額に基づいて前記入札者の効用を算出する効用算出手順と、
前記入札者用装置が、前記算出された効用に基づいて前記支払額を承諾するか否かを決定する決定手順と、
前記入札者用装置が、この決定手順の結果を前記開札者用装置に通知する第２の送信手順とをコンピュータに実行させることを特徴とする電子入札プログラム。
【請求項９】
請求項８記載の電子入札プログラムを記録したことを特徴とする記録媒体。
【請求項１】
財を購入する単一の開札者が使用する開札者用装置と、前記財を提供する複数の入札者が使用する複数の入札者用装置と、前記開札者用装置と前記複数の入札者用装置とを接続するネットワークとを備え、複数の属性値を有する財に対して入札を行う電子入札システムであって、
前記入札者用装置は、
前記複数の属性値を含む、前記財に対する評価値を前記開札者用装置に送信する第１の送信手段と、
前記入札者が売却する財を前記開札者用装置が選択して、この選択された財とその属性値と前記選択された財に対する支払額とを前記開札者用装置から通知されたときに、この通知された属性値と支払額に基づいて前記入札者の効用を算出する効用算出手段と、
前記算出された効用に基づいて前記支払額を承諾するか否かを決定する決定手段と、
この決定手段の結果を前記開札者用装置に通知する第２の送信手段とを有し、
前記開札者用装置は、
前記入札者用装置から受信した前記評価値に基づいて、前記入札者が売却する財の組み合わせと属性値の組み合わせの実現可能な複数のパターンを生成する分割セット手段と、
これらのパターンの中から前記入札者と前記開札者に最大の効用を与える財の組み合わせと属性値の組み合わせを選択し、選択した組み合わせに基づいて前記入札者への支払額を算出する支払額算出手段と、
この支払額算出手段によって選択された財の組み合わせと属性値の組み合わせと前記算出された支払額とを前記入札者用装置に通知する第３の送信手段とを有することを特徴とする電子入札システム。
【請求項２】
請求項１記載の電子入札システムにおいて、
前記開札者用装置の支払額算出手段は、任意の入札者用装置から提供される前記財に対する支払額を、前記任意の入札者用装置以外の入札者用装置から受信した前記評価値に基づいて算出することを特徴とする電子入札システム。
【請求項３】
複数の属性値を有する財を提供する複数の入札者が使用する複数の入札者用装置とネットワークを介して接続され、前記財を購入する開札者が使用する開札者用装置であって、
前記複数の属性値を含む、前記財に対する評価値を前記入札者用装置から受信したときに、前記評価値に基づいて、前記入札者が売却する財の組み合わせと属性値の組み合わせの実現可能な複数のパターンを生成する分割セット手段と、
これらのパターンの中から前記入札者と前記開札者に最大の効用を与える財の組み合わせと属性値の組み合わせを選択し、選択した組み合わせに基づいて前記入札者への支払額を算出する支払額算出手段と、
前記選択された財の組み合わせと属性値の組み合わせと前記算出された支払額とを前記入札者用装置に通知する送信手段とを有することを特徴とする開札者用装置。
【請求項４】
請求項３記載の開札者用装置において、
前記支払額算出手段は、任意の入札者用装置から提供される前記財に対する支払額を、前記任意の入札者用装置以外の入札者用装置から受信した前記評価値に基づいて算出することを特徴とする開札者用装置。
【請求項５】
財を購入する単一の開札者が使用する開札者用装置とネットワークを介して接続され、複数の属性値を有する財を提供する入札者が使用する入札者用装置であって、
前記複数の属性値を含む、前記財に対する評価値を前記開札者用装置に送信する第１の送信手段と、
前記入札者が売却する財を前記開札者用装置が選択して、この選択された財とその属性値と前記選択された財に対する支払額とを前記開札者用装置から通知されたときに、この通知された属性値と支払額に基づいて前記入札者の効用を算出する効用算出手段と、
前記算出された効用に基づいて前記支払額を承諾するか否かを決定する決定手段と、
この決定手段の結果を前記開札者用装置に通知する第２の送信手段とを有することを特徴とする入札者用装置。
【請求項６】
財を購入する単一の開札者が使用する開札者用装置と、前記財を提供する複数の入札者が使用する複数の入札者用装置と、前記開札者用装置と前記複数の入札者用装置とを接続するネットワークとを備えた電子入札システムにおいて、複数の属性値を有する財に対して入札を行う電子入札方法であって、
前記入札者用装置が、前記複数の属性値を含む、前記財に対する評価値を前記開札者用装置に送信する第１の送信手順と、
前記開札者用装置が、前記入札者用装置から受信した前記評価値に基づいて、前記入札者が売却する財の組み合わせと属性値の組み合わせの実現可能な複数のパターンを生成する分割セット手順と、
前記開札者用装置が、前記パターンの中から前記入札者と前記開札者に最大の効用を与える財の組み合わせと属性値の組み合わせを選択し、選択した組み合わせに基づいて前記入札者への支払額を算出する算出手順と、
前記開札者用装置が、前記選択された財の組み合わせと属性値の組み合わせと前記算出された支払額とを前記入札者用装置に通知する通知手順と、
前記入札者用装置が、前記選択された財とその属性値と前記選択された財に対する支払額とを前記開札者用装置から通知されたときに、この通知された属性値と支払額に基づいて前記入札者の効用を算出する効用算出手順と、
前記入札者用装置が、前記算出された効用に基づいて前記支払額を承諾するか否かを決定する決定手順と、
前記入札者用装置が、この決定手順の結果を前記開札者用装置に通知する第２の送信手順とを有することを特徴とする電子入札方法。
【請求項７】
請求項６記載の電子入札システムにおいて、
前記算出手順は、任意の入札者用装置から提供される前記財に対する支払額を、前記任意の入札者用装置以外の入札者用装置から受信した前記評価値に基づいて算出することを特徴とする電子入札方法。
【請求項８】
財を購入する単一の開札者が使用する開札者用装置と、前記財を提供する複数の入札者が使用する複数の入札者用装置と、前記開札者用装置と前記複数の入札者用装置とを接続するネットワークとを備え、複数の属性値を有する財に対して入札を行う電子入札システムの前記開札者用装置と前記入札者用装置としてコンピュータを機能させる電子入札プログラムであって、
前記入札者用装置が、前記財の複数の属性値を含む、前記財に対する評価値を前記開札者用装置に送信する第１の送信手順と、
前記開札者用装置が、前記入札者用装置から受信した前記評価値に基づいて、前記入札者が売却する財の組み合わせと属性値の組み合わせの実現可能な複数のパターンを生成する分割セット手順と、
前記開札者用装置が、前記パターンの中から前記入札者と前記開札者に最大の効用を与える財の組み合わせと属性値の組み合わせを選択し、選択した組み合わせに基づいて前記入札者への支払額を算出する算出手順と、
前記開札者用装置が、前記選択された財の組み合わせと属性値の組み合わせと前記算出された支払額とを前記入札者用装置に通知する通知手順と、
前記入札者用装置が、前記選択された財とその属性値と前記選択された財に対する支払額とを前記開札者用装置から通知されたときに、この通知された属性値と支払額に基づいて前記入札者の効用を算出する効用算出手順と、
前記入札者用装置が、前記算出された効用に基づいて前記支払額を承諾するか否かを決定する決定手順と、
前記入札者用装置が、この決定手順の結果を前記開札者用装置に通知する第２の送信手順とをコンピュータに実行させることを特徴とする電子入札プログラム。
【請求項９】
請求項８記載の電子入札プログラムを記録したことを特徴とする記録媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２００７−３４３６５（Ｐ２００７−３４３６５Ａ）
【公開日】平成１９年２月８日（２００７．２．８）
【国際特許分類】
【出願番号】特願２００５−２１２３２５（Ｐ２００５−２１２３２５）
【出願日】平成１７年７月２２日（２００５．７．２２）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【出願人】（５０４１４５３４２）国立大学法人九州大学 (960)
【公開日】平成１９年２月８日（２００７．２．８）
【国際特許分類】
【出願日】平成１７年７月２２日（２００５．７．２２）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【出願人】（５０４１４５３４２）国立大学法人九州大学 (960)
[ Back to top ]