(57)【要約】【課題】複数の属性値を有する財に対応可能な電子入札方法、電子入札システム、開札者用装置、入札者用装置、プログラムおよび記憶媒体を提供する【解決手段】入札者用装置２は、入札者のタイプθを開札者用装置１に通知する。開札者用装置１は、受信したタイプθに基づいて価格ｐを算出し、入札者用装置２に通知する。入札者用装置２は、受信した価格ｐから効用を算出し、最も効用が高くなる高いバンドルと属性値を選択し、開札者用装置１に通知する。これにより、複数の属性値を有するタスクのオークションに対応することが可能となる。【選択図】  図１
2006018579.tif 000002
【特許請求の範囲】
【請求項１】
財を購入する単一の買い手が使用する開札者用装置と、前記財を提供する複数の入札者が使用する入札者用装置と、前記開札者用装置および前記入札者用装とを接続するネットワークとを備え、複数の属性値を有する財に対して入札を行う電子入札方法であって、
前記入札者用装置から前記財に対する評価値を前記開札者用装置に送信する第１のステップと、
前記開札者用装置において受信した前記評価値に基づいて前記財に対する前記属性値ごとの価格を算出し、この価格を前記入札者用装置に送信する第２のステップと、
前記入札者用装置において受信した前記価格に基づいて前記入札者が実際に提供する前記財と属性値の組み合わせを決定し、この組み合わせを前記開札者用装置に送信する第３のステップと
を有することを特徴とする電子入札方法。
【請求項２】
前記第２のステップは、任意の入札者用装置から提供される前記財に対する価格を、前記任意の入札者用装置以外の入札者用装置から受信した前記評価値に基づいて算出する
ことを特徴とする請求項１記載の電子入札方法。
【請求項３】
前記第２のステップは、前記入札者用装置が提供可能な財と各財の属性の全ての組み合わせそれぞれについて価格を算出する
ことを特徴とする請求項１または２記載の電子入札方法。
【請求項４】
前記第２のステップは、同一の財が複数の入札者に割り当てられないように前記価格を算出する
ことを特徴とする請求項１乃至３の何れか１項に記載の電子入札方法。
【請求項５】
財を購入する単一の買い手が使用する開札者用装置と、前記財を提供する複数の入札者が使用する入札者用装置と、前記開札者用装置および前記入札者用装とを接続するネットワークとを備え、複数の属性値を有する財に対して入札を行う電子入札システムであって、
前記入札者用装置は、
前記財に対する評価値を前記開札者用装置に送信する第１の送信手段と、
前記開札者用装置から受信する前記財に対する価格に基づいて、前記入札者が実際に提供する前記財と属性値の組み合わせを決定する決定手段と、
この決定手段により決定された前記組み合わせを前記開札者用装置に送信する第２の送信手段と
を有し、
前記開札者用装置は、
前記入札者用装置から受信する前記評価値に基づいて前記属性値ごとの前記価格を算出する算出手段と、
この算出手段により算出された前記価格を前記入札者用装置に送信する第３の送信手段と
を有することを特徴とする電子入札システム。
【請求項６】
前記算出手段は、任意の入札者用装置から提供される前記財に対する価格を、前記任意の入札者用装置以外の入札者用装置から受信した前記評価値に基づいて算出する
ことを特徴とする請求項５記載の電子入札システム。
【請求項７】
前記算出手段は、前記入札者用装置が提供可能な財と各財の属性値の全ての組み合わせそれぞれについて価格を算出する
ことを特徴とする請求項５または６記載の電子入札システム。
【請求項８】
前記算出手段は、同一の財が複数の入札者に割り当てられないように前記価格を算出する
ことを特徴とする請求項５乃至７の何れか１項に記載の電子入札システム。
【請求項９】
複数の属性値を有する財を提供する複数の入札者が使用する入札者用装置とネットワークにより接続され、前記財を購入する買い手が使用する開札者用装置であって、
前記入札者用装置から受信する前記財に対する評価値に基づいて前記財に対する前記属性値ごとの価格を算出する算出手段と、
この算出手段により算出された前記価格を前記入札者用装置に送信する送信手段と
を有することを特徴とする開札者用装置。
【請求項１０】
前記算出手段は、任意の入札者用装置から提供されるする前記財に対する価格を、前記任意の入札者用装置以外の入札者用装置から受信した前記評価値に基づいて算出する
ことを特徴とする請求項９記載の開札者用装置。
【請求項１１】
前記算出手段は、前記入札者用装置が提供可能な財と各財の属性の全ての組み合わせそれぞれについて価格を算出する
ことを特徴とする請求項９または１０記載の開札者用装置。
【請求項１２】
前記算出手段は、同一の財が複数の入札者に割り当てられないように前記価格を算出する
ことを特徴とする請求項９乃至１１の何れか１項に記載の開札者用装置。
【請求項１３】
財を購入する単一の買い手が使用する開札者用装置とネットワークにより接続され、複数の属性値を有する財を提供する入札者が使用する入札者用装置であって、
前記財に対する評価値を前記開札者用装置に送信する第１の送信手段と、
前記開札者用装置から受信する前記財に対する価格に基づいて、前記入札者が実際に提供する前記財と属性値の組み合わせを決定する決定手段と、
この決定手段により決定された前記組み合わせを前記開札者用装置に送信する第２の送信手段と
を有することを特徴とする入札者用装置。
【請求項１４】
財を購入する単一の買い手が使用する開札者用装置と、前記財を提供する複数の入札者が使用する入札者用装置と、前記開札者用装置および前記入札者用装とを接続するネットワークとを備え、複数の属性値を有する財に対して入札を行う電子入札のプログラムであって、
前記入札者用装置から前記財に対する評価値を前記開札者用装置に送信する第１のステップと、
前記開札者用装置において受信した前記評価値に基づいて前記財に対する前記属性値ごとの価格を算出し、この価格を前記入札者用装置に送信する第２のステップと、
前記入札者用装置において受信した前記価格に基づいて前記入札者が実際に提供する前記財と属性値の組み合わせを決定し、この組み合わせを前記開札者用装置に送信する第３のステップと
を有することを特徴とするプログラム。
【請求項１５】
前記第２のステップは、任意の入札者用装置から提供される前記財に対する価格を、前記任意の入札者用装置以外の入札者用装置から受信した前記評価値に基づいて算出する
ことを特徴とする請求項１４記載のプログラム。
【請求項１６】
前記第２のステップは、前記入札者用装置が提供可能な財と各財の属性の全ての組み合わせそれぞれについて価格を算出する
ことを特徴とする請求項１４または１５記載のプログラム。
【請求項１７】
前記第２のステップは、同一の財が複数の入札者に割り当てられないように前記価格を算出する
ことを特徴とする請求項１４乃至１６の何れか１項に記載のプログラム。
【請求項１８】
請求項１４乃至１７の何れか１項に記載のプログラムを記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワーク上に分散配置された複数の入札者が電子的手段によって入札を行う電子入札方法、電子入札システム、開札者用装置、入札者用装置、プログラムおよび記憶媒体に関するものである。
【背景技術】
【０００２】
電子入札等の組み合わせオークションにおいて、ＰＯＲＦ(Price-Oriented Rationing-Free)プロトコルを用いた技術が提案されている（例えば、非特許文献１，２参照。）。このＰＯＲＦプロトコルについて、以下に説明する。
【０００３】
ＰＯＲＦプロトコルでは、単一の買い手０、この買い手に対して売り手または入札者（以下、入札者という）の集合Ｎ＝｛１，２，・・・，ｎ｝、入札者が提供する仕事や物等の財の集合Ｔ＝｛ｔ1，・・・，ｔm｝が存在する。
財の入札者への可能な割り当ては、式（１）で表される。ここで、バンドルＢi⊆Ｔであり、ｉ≠ｋであれば式（２）が成り立つ。なお、バンドルＢとは、任意の財の組み合わせのことを意味する。
財の組み合わせがＢiのとき、入札者のコストはｃ（θi，Ｂi）で表され、式（３）の条件を満たす。
各入札者の財に対する価格をｐiで表し、各入札者の効用は準線形であることを仮定すると、各入札者ｉの効用はｐi−ｃ（θi，Ｂi）で表される。また、買い手の効用は式（４）で表される。
【０００４】
ここで、各入札者ｉは、財に対する評価を示す評価値等を意味し式（５）で表される自分のタイプを申告する。このとき、入札者ｉは真のタイプθiを申告するとは限らない。
タイプを申告すると、入札者ｉには任意のバンドルＢ⊆Ｔに対する価格ｐB，iが決定される。この価格ｐB，iは、他の入札者の申告したタイプに基づいて決定される。
ここで、Ｂ⊆Ｂ’の場合、式（６）と仮定する。
入札者ｉには、式（７）で表される効用を最大化するバンドルＢが割り当てられる。価格ｐB，iは、効用を最大化するバンドルが複数存在する場合には、それらのいずれか一つが割り当てられる。
割り当て結果は、割り当て可能性を満たすように決定する。すなわち、入札者ｉ，ｊに割り当てられるバンドルＢi，Ｂjに関して、式（２）が成立するように決定される。
【０００５】
このようなＰＯＲＦプロトコルは、価格が自分の申告したタイプとは無関係に決定され、自分の効用を最大化するバンドルを得ることができる。例えば、インターネット、LAN(Local Area Network)、WAN(Wide Area Network)等の電気通信システムを用いたオークションでは、例えば異なるメールアドレスを用意することにより複数の名義を設定し、単一の入札者が複数の入札を行う架空名義入札が可能である。しかしながら、ＰＯＲＦプロトコルにより上記電気通信システムを用いたオークションを設計すると、入札者自身では自分の価格を操作することができない、すなわち戦略的操作が不可能となる。したがって、ＰＯＲＦプロトコルは、架空名義入札に対して頑強なプロトコルであると言える。
また、ＰＯＲＦプロトコルでは、各入札者の各バンドルに対する価格は、同じ財が同時に複数の入札者に割り当てないよう適切に決定する必要がある。しかし、ＰＯＲＦプロトコルでは、入札者ｉに対して効用を最大化するバンドルが複数存在する場合、そのいずれか一つを割り当てるが、どれを割り当てるかは規定していない。したがって、オークションの主催者は、割り当て可能性が満足されるように、割り当てを調整する。
【０００６】
上述したＰＯＲＦプロトコルを用いたオークションにおける価格の決定例を以下に示す。なお、上述したようにＰＯＲＦプロトコルは戦略的操作不可能であるため、以下の例では各入札者ｉは真のタイプθiを申告するものとする。
【０００７】
単一の財のオークションの場合、バンドルＢ＝Ｍの価格は、ｐB，i＝ｍａｘj≠iｖ（Ｂ，θj）で与えられる。このプロトコルはVickreyオークションと等価である。
複数の財の組み合わせオークションの場合、プロトコルの記述の簡単化のため、入札者の集合Ｘと財の集合Ｂに対して、Ｖ＊（Ｘ、Ｂ）をＢがＸに最適に割り当てられたときのＸの評価値の合計とすると、価格ｐB，iは以下の式で表される。
ｐB，i＝Ｖ＊（Ｎ＼｛ｉ｝，Ｍ）−Ｖ＊（Ｎ＼｛ｉ｝，Ｍ＼Ｂ）
この式は、Vickrey-Clarke-Groves(VCG)メカニズムと等価である。
【０００８】
【数１】
2006018579.tif 000003
【０００９】
なお、出願人は、本明細書に記載した先行技術文献情報で特定される先行技術文献以外には、本発明に関連する先行技術文献を出願時までに発見するには至らなかった。
【非特許文献１】M. Yokoo、 Characterization of strategy/false-name proof combinatorial auction protocols: Price-oriented, rationing-free protocol、 IJCAI03、 pp 481-488、2003
【非特許文献２】伊藤孝行、横尾真、松原繁夫、多様な興味を持つ専門家と素人が存在する場合の組み合わせオークションの設計、The 18th Annual Conference of the Japanese Society for Artificial Intelligence、2004、［平成１６年６月２３日検索］、インターネット<URL:http://www-kasm.nii.ac.jp/jsai2004_schedule/pdf/000156.pdf>
【発明の開示】
【発明が解決しようとする課題】
【００１０】
複数の財をオークションにより売却する場合、各財間に依存関係が存在することがある。また、各財に対して品質などの属性値が設定される場合もある。
しかしながら、ＰＯＲＦプロトコルにより設計された従来のオークションでは、複数の属性値を持つ複数の財のオークションに対応することができなかった。
そこで、本発明は、上述したような課題を解決するためになされたものであり、複数の属性値を有する財に対応可能な電子入札方法、電子入札システム、開札者用装置、入札者用装置、プログラムおよび記憶媒体を提供することを目的とする。
【課題を解決するための手段】
【００１１】
上述したような課題を解決するために、本発明に係る電子入札方法は、財を購入する単一の買い手が使用する開札者用装置と、財を提供する複数の入札者が使用する入札者用装置と、開札者用装置および入札者用装とを接続するネットワークとを備え、複数の属性値を有する財に対して入札を行う電子入札方法であって、入札者用装置から財に対する評価値を開札者用装置に送信する第１のステップと、開札者用装置において受信した評価値に基づいて財に対する属性値ごとの価格を算出し、この価格を入札者用装置に送信する第２のステップと、入札者用装置において受信した価格に基づいて入札者が実際に提供する財と属性値の組み合わせを決定し、この組み合わせを開札者用装置に送信する第３のステップとを有することを特徴とする。
【００１２】
上記電子入札方法において、第２のステップは、任意の入札者用装置から提供される財に対する価格を、任意の入札者用装置以外の入札者用装置から受信した評価値に基づいて算出するようにしてもよい。
【００１３】
上記電子入札方法において、第２のステップは、入札者用装置が提供可能な財と各財の属性の全ての組み合わせそれぞれについて価格を算出するようにしてもよい。
【００１４】
上記電子入札方法において、第２のステップは、同一の財が複数の入札者に割り当てられないように価格を算出するようにしてもよい。
【００１５】
また、本発明に係る電子入札システムは、財を購入する単一の買い手が使用する開札者用装置と、財を提供する複数の入札者が使用する入札者用装置と、開札者用装置および入札者用装とを接続するネットワークとを備え、複数の属性値を有する財に対して入札を行う電子入札システムであって、入札者用装置は、財に対する評価値を開札者用装置に送信する第１の送信手段と、開札者用装置から受信する財に対する価格に基づいて、入札者が実際に提供する財と属性値の組み合わせを決定する決定手段と、この決定手段により決定された組み合わせを開札者用装置に送信する第２の送信手段とを有し、開札者用装置は、入札者用装置から受信する評価値に基づいて属性値ごとの価格を算出する算出手段と、この算出手段により算出された価格を入札者用装置に送信する第３の送信手段とを有することを特徴とする。
【００１６】
上記電子入札システムにおいて、算出手段は、任意の入札者用装置から提供される財に対する価格を、任意の入札者用装置以外の入札者用装置から受信した評価値に基づいて算出するようにしてもよい。
【００１７】
上記入札システムにおいて、算出手段は、入札者用装置が提供可能な財と各財の属性値の全ての組み合わせそれぞれについて価格を算出するようにしてもよい。
【００１８】
上記入札システムにおいて、算出手段は、同一の財が複数の入札者に割り当てられないように価格を算出するようにしてもよい。
【００１９】
また、本発明に係る開札者用装置は、複数の属性値を有する財を提供する複数の入札者が使用する入札者用装置とネットワークにより接続され、財を購入する買い手が使用する開札者用装置であって、入札者用装置から受信する財に対する評価値に基づいて財に対する属性値ごとの価格を算出する算出手段と、この算出手段により算出された価格を入札者用装置に送信する送信手段とを有することを特徴とする。
【００２０】
上記開札者用装置において、算出手段は、任意の入札者用装置から提供されるする財に対する価格を、任意の入札者用装置以外の入札者用装置から受信した評価値に基づいて算出するようにしてもよい。
【００２１】
上記開札者用装置において、算出手段は、入札者用装置が提供可能な財と各財の属性の全ての組み合わせそれぞれについて価格を算出するようにしてもよい。
【００２２】
上記開札者用装置において、算出手段は、同一の財が複数の入札者に割り当てられないように価格を算出するようにしてもよい。
【００２３】
また、本発明に係る入札者用装置は、財を購入する単一の買い手が使用する開札者用装置とネットワークにより接続され、複数の属性値を有する財を提供する入札者が使用する入札者用装置であって、財に対する評価値を開札者用装置に送信する第１の送信手段と、開札者用装置から受信する財に対する価格に基づいて、入札者が実際に提供する財と属性値の組み合わせを決定する決定手段と、この決定手段により決定された組み合わせを開札者用装置に送信する第２の送信手段とを有することを特徴とする。
【００２４】
また、本発明に係るプログラムは、財を購入する単一の買い手が使用する開札者用装置と、財を提供する複数の入札者が使用する入札者用装置と、開札者用装置および入札者用装とを接続するネットワークとを備え、複数の属性値を有する財に対して入札を行う電子入札のプログラムであって、入札者用装置から財に対する評価値を開札者用装置に送信する第１のステップと、開札者用装置において受信した評価値に基づいて財に対する属性値ごとの価格を算出し、この価格を入札者用装置に送信する第２のステップと、入札者用装置において受信した価格に基づいて入札者が実際に提供する財と属性値の組み合わせを決定し、この組み合わせを開札者用装置に送信する第３のステップとを有することを特徴とする。
【００２５】
上記プログラムにおいて、第２のステップは、任意の入札者用装置から提供される財に対する価格を、任意の入札者用装置以外の入札者用装置から受信した評価値に基づいて算出するようにしてもよい。
【００２６】
上記プログラムにおいて、第２のステップは、入札者用装置が提供可能な財と各財の属性の全ての組み合わせそれぞれについて価格を算出するようにしてもよい。
【００２７】
上記プログラムにおいて、第２のステップは、同一の財が複数の入札者に割り当てられないように価格を算出するようにしてもよい。
【００２８】
また、本発明に係る記録媒体は、上記プログラムを記録したことを特徴とする。
【発明の効果】
【００２９】
本発明によれば、入札者用装置から受信した財の評価値に基づいて入札者用装置が提供可能な財について価格を算出し、この価格に基づいて入札者が実際に提供する財と属性値の組み合わせを決定することにより、複数の属性値を有する財の入札に対応することが可能となる。
【発明を実施するための最良の形態】
【００３０】
以下、図面を参照して、本発明の実施の形態について詳細に説明する。
図１は、本実施の形態に係るオークションシステムの構成を示すブロック図である。
本実施の形態に係るオークションシステムは、オークションを取り仕切るオークショニアや入札者から仕事や物等の財を買う買い取り者である開札者が用いる開札者用装置１と、開札者に財を提供する入札者が用いる複数の入札者用装置２と、開札者用装置１と入札者用装置２とが接続されたネットワーク３とから構成される。
【００３１】
図２は、開札者用装置の構成を示すブロック図である。
開札者用装置１は、ネットワーク３を介して入札者用装置２と各種情報の送受信を行う送受信部１１と、開札者の操作入力を検出する入力部１２と、オークションに関する各種情報を表示する表示部１３と、入札者用装置２から受信するタイプ、財およびこの財の属性値などのオークションに関する各種情報を記憶する記憶部１４と、入札者が提供する財に対する価格を算出する価格演算部１５と、これらの開札者用装置１の各機能部の動作を制御する制御部１６とを備え、これらの開札者用装置１の各機能部はバス等の公知の通信回線１７により接続されている。
【００３２】
このような開札者用装置１は、ＣＰＵ等の演算装置、メモリ、HDD等の記憶装置、入札者用装置２と各種情報の送受を行うＩ/Ｆ装置、キーボード、マウス等の入力装置、CRT(Cathode Ray Tube)、LCD(Liquid Crystal Display)、FED(Field Emission Display)または有機EL(Electro Luminescence)等の表示装置などを備えたコンピュータと、このコンピュータにインストールされたプログラムとからそれぞれ構成されており、上記ハードウェア装置がプログラムによって制御されることによって、すなわちハードウェア資源とソフトウェアが協働することによって、上述した送受信部１１、入力部１２、表示部１３、記憶部１４、価格演算部１５、制御部１６および通信回線１７を実現する。
【００３３】
図３は、入札者用装置の構成を示すブロック図である。
入札者用装置２は、ネットワーク３を介して開札者用装置１と各種情報の送受信を行う送受信部２１と、入札者の操作入力を検出する入力部２２と、オークションに関する各種情報を表示する表示部２３と、開札者用装置１から受信する価格などのオークションに関する各種情報を記憶する記憶部２４と、開札者用装置１により算出された価格に基づいて財の効用を算出する効用演算部２５と、これらの入札者用装置２の各機能部の動作を制御する制御部２６とを備え、これらの入札者用装置２の各機能部はバス等の公知の通信回線２７により接続されている。
【００３４】
このような入札者用装置２は、ＣＰＵ等の演算装置、メモリ、HDD等の記憶装置、開札者用装置１と各種情報の送受を行うＩ/Ｆ装置、キーボード、マウス等の入力装置、CRT(Cathode Ray Tube)、LCD(Liquid Crystal Display)、FED(Field Emission Display)または有機EL(Electro Luminescence)等の表示装置などを備えたコンピュータと、このコンピュータにインストールされたプログラムとからそれぞれ構成されており、上記ハードウェア装置がプログラムによって制御されることによって、すなわちハードウェア資源とソフトウェアが協働することによって、上述した送受信部２１、入力部２２、表示部２３、記憶部２４、効用演算部２５、制御部２６および通信回線２７を実現する。
【００３５】
ネットワーク３は、インターネット、LAN(Local Area Network)、WAN(Wide Area Network)等の公知の電気通信システムから構成される。
【００３６】
次に、図４を参照して、本実施の形態に係るオークションシステムの情報の送受について説明する。図４は、本実施の形態に係るオークションシステムの情報の送受を説明するためのシーケンス図である。
なお、本実施の形態に係るオークションシステムは、ＰＯＲＦプロトコルを拡張したプロトコルにより設計される。この本実施の形態に用いられる拡張ＰＯＲＦプロトコルの詳細については後述する。
【００３７】
まず、入札者用装置２は、入札者のタイプθを開札者用装置１に通知する（ステップＳ４０１）。ここで、タイプθとは、入札者が提供する財のコストなど入札者の財に対する評価を表すものであり、入札者が提供する仕事や物等の財と、この財の品質などを表す属性値とを少なくとも含む。開札者用装置２に通知されるタイプθには、財と属性値の全ての組み合わせそれぞれについて評価値が設定される。
【００３８】
開札者用装置１は、受信したタイプθに基づいて価格ｐを算出し、入札者用装置２に通知する（ステップＳ４０２）。ここで、開札者用装置１は、入札に参加する全ての入札者用装置２からタイプθを受信してから、価格ｐを算出する。この価格ｐは、任意の入札者用装置２の価格ｐを算出する場合、その任意の入札者以外から受信したタイプθに基づいて算出される。また、価格ｐは、入札者用装置２から受信したタイプθに含まれる財のバンドルと属性値との全ての組み合わせについて算出される。
【００３９】
入札者用装置２は、受信した価格ｐから効用を算出し、最も効用が高くなる高いバンドルと属性値を選択し、開札者用装置１に通知する（ステップＳ４０３）。このようにすることにより、複数の属性値を有する複数の財のオークションに対応することが可能となる。
【００４０】
次に、図５を参照して、開札者用装置１の動作について説明する。図５は、開札者用装置の動作を説明するフローチャートである。
まず、開札者用装置１は、オークションに参加する入札者の入札者用装置２それぞれからタイプθを受信する（ステップＳ５０１）。ネットワーク３を介して入札者用装置２から送信されたタイプθは、送受信部１１により受信され、記憶部１４に格納される。
この受信動作は、オークションに参加する全ての入札者の入札者用装置２からタイプθを受信するまで行われる。したがって、全ての入札者の入札者用装置２からタイプθを受信していない場合（ステップＳ５０２：ＮＯ）、開札者用装置１は、ステップＳ５０１の処理に戻る。
制御部１６は、全ての入札者の入札者用装置２からタイプθを受信したか否かの判断を、予め特定しておいた全ての入札者用装置２からタイプθを受信したことを確認する、予め設定した終了時刻までにタイプθを受信した入札者を全ての入札者とする等の方法により行う。
【００４１】
全ての入札者からタイプθを受信すると（ステップＳ５０２：ＹＥＳ）、開札者用装置１は、受信したタイプθに基づいて価格ｐを算出する（ステップＳ５０３）。この価格ｐの算出は価格演算部１５により行われ、算出された価格ｐは記憶部１４に記憶される。
価格ｐは、タイプθを送信した全ての入札者用装置２に対して行われ、タイプθに含まれる財のバンドルと属性値の全ての組み合わせについて算出される。このとき、価格演算部１４は、同一の財が複数の入札者に割り当てられないよう価格を算出する。
なお、価格ｐの算出方法の詳細については、後述する。
【００４２】
価格ｐを算出すると、開札者用装置１は、その算出した価格ｐを入札者用装置２に送信する（ステップＳ５０４）。この価格ｐの送信動作は、送受信部１１により行われる。送受信部１１は、タイプθを送信した全ての入札者用装置２に価格ｐを送信する。
【００４３】
価格ｐを送信すると、開札者用装置１は、入札者用装置２から選択情報を受信する（ステップＳ５０５）。オークションに参加した全ての入札者の入札者用装置２、すなわち価格ｐを送信した全ての入札者用装置２から選択情報を受信すると（ステップＳ５０６）、オークションに関する全ての処理を終了する。
【００４４】
次に、図６を参照して、入札者用装置２の動作について説明する。図６は、入札者用装置の動作を説明するフローチャートである。
入札者用装置２は、入札者がオークションに参加する旨の操作入力を入力部２２が検出すると、この検出した操作入力に基づいて、提供する財とこの財の属性値とを含むタイプθを開札者用装置１に送信する（ステップＳ６０１）。このタイプθの送信動作は、送受信部２１により行われる。送信したタイプθは、記憶部２４に記憶される。
【００４５】
タイプθを送信すると、入札者用装置２は、開札者用装置１から価格ｐを受信する（ステップＳ６０２）。この価格ｐの受信動作は、送受信部２１により行われる。受信した価格ｐには、送信したタイプθに含まれる財のバンドルと属性値の全ての組み合わせそれぞれに対する価格に関する情報が含まれる。受信した価格ｐは、記憶部２４に記憶される。
【００４６】
価格ｐを受信すると、入札者用装置２は、価格ｐから効用を算出する（ステップＳ６０３）。この効用の算出は、効用演算部２５により行われる。効用演算部２５は、財のバンドルと属性値の全ての組み合わせについて効用を算出する。算出した効用は、記憶部２４に記憶される。
なお、効用の算出動作の詳細については後述する。
【００４７】
効用を算出すると、入札者用装置２は、効用が正となる、すなわち入札者が損をしないバンドルと属性値の組み合わせがあるか否かを判定する（ステップＳ６０４）。この判定動作は、効用演算部２５により行われる。
【００４８】
効用が正となるバンドルと属性値の組み合わせがある場合（ステップＳ６０４：ＹＥＳ）、入札者用装置２は、その組み合わせの中から効用が最大となるバンドルと属性値を選択し、開札者用装置１に送信する（ステップＳ６０５）。効用が最大となるバンドルと属性値の選択動作は効用演算部２５により行われ、選択されたバンドルと値は送受信部２１により送信される。
【００４９】
効用が正となるバンドルと属性値の組み合わせがない場合（ステップＳ６０４：ＮＯ）、入札者用装置２は、入札から降りることを開札者用装置１に送信する（ステップＳ６０６）。入札から降りることの判断は効用演算部２５により行われ、下した判断は送受信部２１により送信される。
【００５０】
このように、本実施の形態によれば、入札者用装置から受信した財の評価値に基づいて入札者用装置が提供可能な財について価格を算出し、この価格に基づいて入札者が実際に提供する財と属性値の組み合わせを決定することにより、複数の属性値を有する複数の財のオークションに対応することが可能となる。
また、本実施の形態によれば、入札者は、効用が最大となる、すなわち入札者にとって最も利益があるバンドルと属性値の組み合わせを得ることが可能となる。さらに、本実施の形態によれば、入札者にとって不利益となる場合は、入札から降りることを選択することが可能となる。したがって、本実施の形態に係るオークションシステムは、入札者にとってとても使い勝手がよい。
【００５１】
［拡張ＰＯＲＦプロトコル］
次に、本実施の形態に係るオークションに用いられる拡張ＰＯＲＦプロトコルについて説明する。
拡張ＰＯＲＦプロトコルは、個人合理的である、すなわちどの入札者にもコストが支払額を超えるという損失が生じないものであり、かつ、入力が同じであれば常に同じ結果が得られるものである。このような拡張ＰＯＲＦプロトコルのモデル、すなわち環境を以下のように定義する。
【００５２】
単一の買い手０，この買い手に対して入札者の集合集合Ｎ＝｛１，２，・・・，ｎ｝、入札者が提供する仕事や物等の財の集合Ｔ＝｛ｔ1，・・・，ｔm｝が存在する。
各入札者はタイプθiを保持している。タイプθiは集合Θの要素である。
各財ｔiに対して、クオリティｑiが定義される。クオリティｑiは集合Ｑの要素である。なお、クオリティｑiとは、属性値に含まれるものであり、特に財の品質等を意味する。
財の入札者への可能な割り当ては式（８）で表される。ここで、バンドルＢi⊆Ｔであり、ｉ≠ｋであれば式（９）が成り立つ。
クオリティのプロファイルは式（１０）で表される。
クオリティプロファイルとバンドルＢi＝｛ｔi，1，ｔi，2，．．．｝に対して、クオリティプロファイルへのＢiの射影を式（１１）で表す。
財の割り当てがＢiで、このときに達成されるクオリティプロファイルが式（１２）の場合、入札者のコストは式（１３）で表される。ここで、コストｃは式（１４）により正規化されているものとする。
クオリティプロファイルが式（１５）のとき、買い手０のグロスの効用は式（１６）で表される。この買い手０の効用とは、買い手にとってどれほど価値があるのかを示す指標である。
各入札者の財に対する買い手からの支払額、すなわち価格はｐiで表される。
各入札者の効用は準線形であることを仮定すると、各入札者の効用は式（１７）で表される。また、買い手０にとってのネットの効用は式（１８）で表される。
割り当てられない財ｔjのクオリティはｑ0∈Ｑとする。売り手の効用Ｖは、式（１９）により、式（２０）が導出される。
財のクオリティを表すパラメータはｑjの一つであるが、これはクオリティが一次元であることを示すのではなく、ｑjは複数の属性値を持つベクトルとすることができる。
【００５３】
このようなモデルの具体例について述べる。
入札者が二人、Ｎ＝｛１，２｝、財が二つＴ＝｛ｔ1，ｔ2｝、クオリティプロファイルが式（２１）であり、ｑjが一次元の場合の入札者１のコスト関数を式（２２）〜（２４）とする。また、買い手の効用が式（２５）であり、入札者２のコストは常に入札者１よりも大きいものとする。
このような場合に、ｔ1とｔ2の両方が式（２６）で入札者１に割り当てられたとすると、入札者１のコストは式（２７）で表され、社会的余剰は式（２８）となる。
【００５４】
【数２】
2006018579.tif 000004
【００５５】
【数３】
2006018579.tif 000005
【００５６】
［価格ｐの算出方法］
次に、価格ｐの算出方法について説明する。
まず、各入札者ｉ、各バンドルＢ⊆Ｔ、式（２９）に示す各クオリティプロファイルに対して、式（３０）に示す価格を定義する。この価格は、他の入札者のタイプに依存するが、入札者ｉ自身が申告した式（３１）で示すタイプとは無関係に決定される。
バンドルＢの割り当ては、割り当て可能性を満たすように決定される。例えば、入札者ｉ，ｊに対して、それぞれに割り当てられたバンドルＢi＊，Ｂj＊は、式（３２）が成り立つ。
【００５７】
ここで、入札者ｉはバンドルＢ＊が割り当てられ、このクオリティプロファイルである式（３３）を実行したとする。このとき、入札者の得られる最大の効用は、式（３４）で表される。入札者ｉのバンドルＢ＊の価格は式（３５）となる。もし、入札者ｉの効用を最大化するバンドルが複数存在する場合は、そのうち一つが割り当てられる。
【００５８】
上述したように、拡張ＰＯＲＦプロトコルは選択的操作不可能であり、各バンドルとクオリティプロファイルに対して、入札者ｉが受け取る価格は入札者ｉが申告したタイプとは独立に決定される。入札者は、他の入札者の割り当てとは独立に効用を最大化するようなクオリティのバンドルが割り当てられる。
一方、ＰＯＲＦプロトコルでは、価格をバンドルの割り当て可能性を満たすように決定しなければならない。ＰＯＲＦプロトコルの定義では、もし効用を最大化するバンドルが複数存在する場合、オークショニアが割り当て可能性を満足するために複数の入札者への割り当てを調整することができる。
【００５９】
【数４】
2006018579.tif 000006
【００６０】
［価格決定の具体例］
次に、本実施の形態において、価格を決定する具体的な方法について説明する。まず、以下のような条件を定義する。
まず各入札者ｉが、バンドルＢの財ｑBで実行した場合の支払額が式（３６）で定義される。入札者ｉは、式（３７）を最大化するＢ，ｑBを選択する。
入札者ｉにとって式（３７）を最大化するＢ，ｑBが複数存在するときは、買い手が買い手自身の効用を最大とするＢ，ｑBを選択する。
このような条件下で、価格は次のように決定される。
【００６１】
［Ｖが加算形の場合］
Ｖ（ｑ）がＶi（ｑi）の加算形、すなわちＶ（ｑ）＝Ｖ1（ｑ1）＋．．．＋Ｖm（ｑm）と表現できる場合、価格は以下に示すように決定される。
バンドルＢと式（３８）のクオリティプロファイルが入札者ｉに割り当てられたとき、入札者ｉが受け取る式（３９）で示される価格は次のように決定される。
まず、ｓi，Bを式（４０）で示すように定義し、このときＢ’をバンドルＢとコンフリクトする任意のバンドル、すなわち式（３９）が成り立つとする。すると、価格は式（４１）で表される。
【００６２】
このように価格を決定した場合、本実施の形態に用いられるプロトコルは割り当て可能性を満足することを説明する。
財ｔkを含む任意のバンドルＢに対してＶB（ｑB）−ｃ（θj，Ｂ，ｑB）を最大化する式（４２）を選択すると、他の利用者ｉにとって、財ｔkを含む任意のバンドルＢ’をｑB‘で実行した場合の価格は、式（４３）で表され、効用は式（４４）となる。この式（４４）において、最大化の条件から二項目の方が大きいので、全体としては負となる。したがって、割り当て可能性を満たしていることになる。
【００６３】
また、上記プロトコルが架空名義操作不可能であることを説明する。
Ｂ＝Ｂ１∪Ｂ２を、一つの名義でクオリティｑBで行った場合の価格はＶB（ｑB）−ｓi，Bとなる。ここで、架空名義を用いた場合の支払額は式（４５）となる。よって、ｓi，B≦ｓi，B1＋ｓi，B2であれば架空名義操作不可能であると言えるが、これはｓi，B＝ｍａｘ（ｓi，B1，ｓi，B2）より明らかである。
また、上記プロトコルは入札者と買い手の両方にとって個人合理的である。入札者は財を提供しないという選択肢があるため、効用は最低でも０である。また、買い手にとっては、ｓi，Bは非負である。このため、式（４６）で示されるクオリティプロファイルで可能な任意の割り当てのときの価格の合計は式（４７）を下回る。
【００６４】
【数５】
2006018579.tif 000007
【００６５】
次に、Ｖが加算形の場合の具体的な計算例について説明する。
まず、第１の計算例は、財が２、入札者が２、すなわちＴ＝｛ｔ１，ｔ２｝，Ｎ＝｛１，２｝，ｑ＝（ｑ１、ｑ２）とし、各入札者の各財のクオリティに対するコストを表１と想定する。
【００６６】
【表１】
2006018579.tif 000008
【００６７】
ｔ1，ｔ2の両方の財を行う場合のコストは、ｔ1，ｔ2のコストの和とし、買い手の効用Ｖは、式（４８）とする。
各財のバンドルＢは、｛ｔ1，ｔ2｝，｛ｔ1｝，｛ｔ2｝，および式（４９）の４通りが考えられる。
ここでは、入札者１にｔ1、入札者２にｔ2を割り当てる場合を考える。最初に、クオリティごとの入札者１の財に対する価格と効用を計算する。
【００６８】
まず、ｓi，Bを上式（４０）から算出する。このためには、式（５０）に該当する全ての組み合わせを計算して、その最大値を求める必要がある。例えば、ｊ＝２（入札者２）、Ｂ’＝｛ｔ2｝、（ｑ1，ｑ2）＝（１，４）という値を式（５０）に当てはめると、式（５１）に示すように演算される。同様に、該当する全ての組み合わせを計算すると、その最大値は２（１／２）となる。よって、ｓi，B＝２（１／２）となる。
【００６９】
次に、上式（３９）に示す価格を算出する。例えば、クオリティが（ｑ1，ｑ2）＝（１，１）の場合、買い手の効用Ｖは式（５２）となる。すると、上式（４１）により、価格ｐは２−２（１／２）＝−１／２となる。このときの効用は、−１／２−１／４＝−３／４となる。その他のクオリティも同様にして算出する。この算出結果を表２に示す。
【００７０】
【表２】
2006018579.tif 000009
【００７１】
表２によると、入札者１の効用の最大値は１／２である。同様にして、その他のバンドルに関して同様に入札者１の効用の最大値を算出する。この算出結果を表３に示す。
【００７２】
【表３】
2006018579.tif 000010
【００７３】
表３から入札者１の最良の選択は、財ｔ1のみをクオリティ４で行い、価格３／２，効用１／２を得ることとなる。
この場合の社会的余剰は２となる。
【００７４】
次に、Ｖが加算形の場合の第２の計算例について説明する。
財が２、入札者が２、すなわちＴ＝｛ｔ1，ｔ2｝，Ｎ＝｛１，２｝，ｑ＝（ｑ1．ｑ2）の場合について説明する。このとき、各入札者の各財のクオリティに対するコストを表４に示す通りとする。
【００７５】
【表４】
2006018579.tif 000011
【００７６】
第１の計算例の場合と同様に各入札者の効用について算出すると、入札者１の効用が正になることはなく、入札者２の効用が正となるバンドルは表５に示す１通りのみである。
【００７７】
【表５】
2006018579.tif 000012
【００７８】
この場合、入札者１の効用は０なので、入札者１は選択を行わない。入札者２の効用は１／２である。このときの社会的余剰は１／２であり、買い手の効用は０である。
【００７９】
【数６】
2006018579.tif 000013
【００８０】
［Ｖが一般の場合］
次に、Ｖが加算形でない場合について説明する。この場合、Ｖi’（ｑi）が、式（５３）に示す全てのクオリティプロファイルに対して式（５４）が成り立つと仮定する。
プロトコルの説明の項目でも上述したように、式（５５）で示す買い手の効用を式（５６）とする。
【００８１】
Ｖが一般の場合のプロトコルも、Ｖが加算形の場合と同様、割り当て可能性と架空名義操作不可能を満足する。また、このプロトコルは入札者と買い手の双方にとって個人合理的である。買い手にとって、クオリティプロファイルが可能な任意の割り当てで、価格の合計が式（５６）を下回る。上述したように、式（５４）が成り立つので、このプロトコルは、買い手にとって個人合理的である。
【００８２】
【数７】
2006018579.tif 000014
【００８３】
本実施の形態に係るオークションシステムは、例えば、工事のような入札に適用することができる。一般に、工事は、設計、施工などいくつかの工程を経て仕事が完了し、設計の質や工期などにより価格が変わる。また、請け負う側では複数の工程を同時に請け負うことにより価格を下げることができることもある。このような場合に、本実施の形態に係るオークションシステムで入札を行うことにより、複数の工程とその属性値などを含めて同時に入札することができ、買い手と入札者の双方に利益となる入札が可能となる。
【図面の簡単な説明】
【００８４】
【図１】本実施の形態に係るオークションシステムの構成を示すブロック図である。
【図２】開札者用装置の構成を示すブロック図である。
【図３】入札者用装置の構成を示すブロック図である。
【図４】本実施の形態に係るオークションシステムのシーケンス図である。
【図５】開札者用装置の動作を説明するフローチャートである。
【図６】入札者用装置の動作を説明するフローチャートである。
【符号の説明】
【００８５】
１…開札者用装置、２…入札者用装置、３…ネットワーク、１１…送受信部、１２…入力部、１３…表示部、１４…記憶部、１５…価格演算部、１６…制御部、１７…通信回線、２１…送受信部、２２…入力部、２３…表示部、２４…記憶部、２５…効用演算部、２６…制御部、２７…通信回線。
【図１】
2006018579.tif 000015
【図２】
2006018579.tif 000016
【図３】
2006018579.tif 000017
【図４】
2006018579.tif 000018
【図５】
2006018579.tif 000019
【図６】
2006018579.tif 000020