(57)【特許請求の範囲】
【請求項１】
購入者用装置が、購入者評価値の上限値を含む入札希望通知を購入者用装置により主催者用装置へ通信ネットワークを介して送信し、販売者用装置が、販売者評価値の下限値を含む入札希望通知を販売者用装置により主催者用装置へ通信ネットワークを介して送信し、主催者が主催者用装置を用いて取引を決定するネットワークオークション方法において、
上記主催者用装置の閾値格納部に閾値価格ｒが格納されており、
上記主催者用装置の通信手段が、入札希望通知を受信するステップと、
上記通信手段が入札希望通知を受信すると、上記主催者用装置の制御手段が、その購入者又は販売者を特定する情報と、当該購入者又は販売者の評価値とを対応づけて記憶部に記憶するステップと、
上記制御手段が、入札締切り期限になったか否か調べるステップと、
上記制御手段が、入札締切り期限になったと判断すると、
評価値配列手段が、上記記憶部に格納されている購入者を示す情報と購入者の評価値との組から当該購入者の評価値を読み出すステップと、
上記評価値配列手段が、その読み出された購入者の評価値を大きい順に配列して購入者評価値配列を生成するステップと、
上記評価値配列手段が、上記記憶部に格納されている販売者を示す情報と販売者の評価値との組から当該販売者の評価値を読み出すステップと、
上記評価値配列手段が、その読み出された販売者の評価値を小さい順に配列して販売者評価値配列を求めるステップと、
順位決定手段が、上記購入者評価値配列の中で、上記閾値価格ｒ以上であり、最小である購入者評価値の配列中の順番ｉを決定するステップと、
上記順位決定手段が、上記販売者評価値配列の中で、上記閾値価格ｒ以下であり、最大である販売者評価値の配列中の順番ｊを決定するステップと、
判定手段が、ｉとｊが等しいかを判定するステップと、
ｉとｊが等しいと判定されると、取引決定手段が、上記購入者評価値配列及び上記販売者評価値配列における１番目からｉ番目までの評価値に対応する購入者及び販売者を取引成立者として決定し、上記閾値価格ｒを、当該購入者の支払い額及び当該販売者の受取り額として決定するステップと、
ｉがｊと等しいと判定されないと、上記判定手段が、ｉがｊより大であるかを判定するステップと、
ｉがｊより大であると判定されると、上記取引決定手段が、上記購入者評価値配列及び上記販売者評価値配列における１番目からｊ番目までの評価値に対応する購入者及び販売者を取引成立者として決定し、ｊ＋１番目の購入者の評価値を、取引成立者である購入者の支払い額として決定し、上記閾値価格ｒを、取引成立者である販売者の受取り額として決定するステップと、
ｉがｊより大でないと判定されると、上記取引決定手段が、上記購入者評価値配列及び上記販売者評価値配列における１番目からｉ番目までの評価値に対応する購入者及び販売者を取引成立者として決定し、上記閾値価格ｒを、取引成立者である購入者の支払い額として決定し、ｉ＋１番目の販売者の評価値を、取引成立者である販売者の受取り額として決定するステップと、
により、取引内容を決定するステップと、
上記通信手段が、取引成立者として決定された各購入者の購入者用装置に、決定された支払い額を含む取引成立通知を送信し、取引成立者として決定された各販売者の販売者用装置に、決定された受取り額を含む取引成立通知を送信し、取引成立者として決定されなかった各購入者の購入者用装置及び各販売者の販売者用装置にそれぞれ取引不成立通知を送信するステップと、
を有することを特徴とするネットワークオークション方法。
【請求項２】
購入者用装置が、購入者評価値の上限値を含む入札希望通知を購入者用装置により主催者用装置へ通信ネットワークを介して送信し、販売者用装置が、販売者評価値の下限値を含む入札希望通知を販売者用装置により主催者用装置へ通信ネットワークを介して送信し、主催者が主催者用装置を用いて取引を決定するネットワークオークション方法において、
(A) 上記主催者用装置の通信手段が、評価値が記された入札希望通知を販売者装置及び購入者装置から受信するステップと、
(B) 通信手段が、上記入札希望通知を受信すると、上記主催者用装置の制御手段が、それらの購入者及び販売者を特定する情報と当該購入者及び販売者の評価値を対応づけて記憶部に記憶するステップと、
(C) 上記制御手段が、入札締切り期限になったか否か調べるステップと、
(D) 上記制御手段が、入札締切り期限になったと判断すると、
(a)  評価値配列手段が、上記記憶部から購入者の評価値を読み出し、大きい順に配列して購入者評価値配列を求め、上記記憶部から販売者の評価値を読み出し、小さい順に配列して販売者評価値配列を求めるステップと、
(b)  順位決定手段が、上記購入者評価値配列における予め主催者が決めた閾値価格ｒ以上の最小評価値の順位ｉと、上記販売者評価値配列における上記閾値価格ｒ以下の最大の評価値の順位ｊとを決定するステップと、
(c)  判定手段が、上記順位ｉとｊの大きさの関係を判定するステップと、
(d)  上記ステップ(c) で上記順位ｉとｊが等しいと判定されると、取引決定手段が、上記購入者評価値配列及び上記販売者評価値配列における１番目からｉ番目までの評価値に対応する購入者及び販売者を取引成立者として決定し、上記閾値価格ｒを、当該購入者及び当該販売者の取引価格として決定するステップと、
(e)  上記ステップ(c) で上記順位ｉがｊより大であると判定されると、上記取引決定手段が、上記購入者評価値配列及び上記販売者評価値配列における１番目からｊ番目までの評価値に対応する購入者及び販売者を取引成立者として決定し、ｊ＋１番目の購入者の評価値を、取引成立者である購入者の取引価格として決定し、上記閾値価格ｒを、取引成立者である販売者の取引価格として決定するステップと、
(f)  上記ステップ(c) で上記順位ｉがｊより小であると判定されると、上記取引決定手段が、上記購入者評価値配列及び上記販売者評価値配列における１番目からｉ番目までの評価値に対応する購入者及び販売者を取引成立者として決定し、上記閾値価格ｒを、取引成立者である購入者の取引価格として決定し、ｉ＋１番目の販売者の評価値を、取引成立者である販売者の取引価格として決定するステップと、
により、取引内容を決定するステップと、
(E) 上記通信手段が、取引成立者として決定された各購入者の購入者用装置及び販売者の販売者用装置にそれぞれ決定された取引価格を含む取引成立通知を送信し、取引成立者として決定されなかった各購入者の購入者用装置及び各販売者の販売者用装置にそれぞれ取引不成立通知を送信するステップと、
を含むネットワークオークション方法。
【請求項３】
請求項２記載の方法をコンピュータに実行させるためのプログラムを記録したコンピュータ読取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、通信ネットワーク上に分散配置された複数の販売者と複数の購入者が電子的手段によって入札を行う双方向の電子式入札方法、その装置及びプログラム記録媒体に関するものである。
【０００２】
【従来の技術】
ある商品に関して、販売者と購入者が複数存在し、それらが互いに希望する販売／購入価格を提示して取引を行う双方向の入札方式はダブルオークションと呼ばれ、株、証券、外貨等の取引において広く一般に用いられている。従来、提案されてきたダブルオークション方法の一つとして、ＰＭＤプロトコル（R.P.McAfee：A Dominant Strategy Double Auction,Journal of Economic Theory, Vol.56, pp.434-450,1992）が存在する。以下、この方式の説明を行う。
【０００３】
図１に示すように通信ネットワーク１１上に複数の販売者用装置1-1,…,1-nと複数の購入者用装置2-1,…,2-mが分散配置され、更に通信ネットワーク１１に主催者用装置１２が接続されている。つまりｍ人の購入者とｎ人の販売者が存在するとする。各購入者は、単一種類の財を、一単位のみ必要としていると仮定し、また、各販売者は単一種類の財を一単位保有していると仮定する。
ｍ人の購入者はその装置2-1，…,2-mをそれぞれ用いて、評価値b1,…,bm （それを越す金額は支払う意思がないことを示す値、真とは限らない）を含む入札希望通知を主催者用装置１２へ送り、またｎ人の販売者はその装置1-1,…,1-nを用いて評価値s1,…,sn （それ未満では売る意思がない値、真とは限らない）を含む入札希望通知を主催者用装置１２へ送信する。
【０００４】
主催者用装置１２は図２に示すように、各販売者用装置1-1,…,1-n、各購入者用装置2-1,…,2-mから入札希望通知を受信すると（ステップＳ１）、その受信した入札希望通知の販売者又は購入者とその評価値を記憶部に記憶し（ステップＳ２）、入札締切り期限になったかを調べ（ステップＳ３）、締切り期限になっていなければ、ステップＳ１に戻り入札希望通知の受信を待つ。例えば平日の午前何時から入札希望通知を受付け、午後何時に入札締切ることが予め決められており、販売者、購入者はこれらの時間に合せて、入札希望通知を主催者用装置１２に送る。
【０００５】
主催者用装置１２は、締切り期限になると、記憶部から全購入者の表価値を読み出し、表明された購入者の評価値b1,…,bm を大きい順に、
b(1) ＞ b(2) ＞ …＞ b(m) 
と配列し（ステップＳ４）、また表明された全販売者の評価値s1 ，…,sn を記憶部から読み出し、小さい順に
s(1) ＜ s(2) ＜… ＜ s(n) 
と配列する（ステップＳ５）。ここで、b(i) は購入者が表明した評価値中のｉ番目に大きい値であり、s(i) は販売者が表明した評価値中のｉ番目に小さい値である。なお同一評価値が複数ある場合（タイブレークの場合）、その配列順はランダム（くじ引き等）に行う。
【０００６】
また、プロトコルの記述を簡潔にするため、b(m+1) を購入者の可能な最小の評価値（例えば０）、s(n+1) を、販売者の可能な最大の評価値（例えば１００億ドル）とする。更に、b(m+1)＜s(n+1) が成立するものと仮定する。
あるｋに関して、b(k) ＞ s(k) 及びb(k+1) ＜ s(k+1) が成立するｋを探す（ステップＳ６）。このｋが見つかれば、最初からｋ番目までの評価値に関しては、購入者の評価値は販売者の評価値と等しいかそれより大きいため、最大ｋ個の取引が可能である。見つからない場合は、取引不成立通知を各入札者に送り（ステップＳ１２）、終了する。
【０００７】
また、取引価格の候補p0 を以下のように定義し、この値p0 を計算する（ステップＳ７）。
p0 ＝(b(k+1)＋s(k+1))/２
プロトコルは以下のように記述される。
s(k) ＜p0 ＜b(k) が成立するか否かを調べ（ステップＳ８）、
ケース(a)：s(k) ＜p0 ＜b(k) が成立する場合
(1)番目から(k)番目までの購入者及び販売者が、価格p0 で取引を行う。つまりこれら購入者の装置、販売者の装置にそれぞれ価格p0 で取引が成立したことを通知する（ステップＳ９）。
【０００８】
ケース(b)：s(k)＜p0 ＜b(k)が成立しない場合
(1)番目から(k-1)番目までの購入者及び販売者が取引を行う。k-1人の全ての購入者はb(k)を支払い、k-1人の全ての販売者はs(k)を受け取る。つまりこれらの購入者の装置にb(k)で取引が成立したこと、これらの販売者の装置にs(k)で取引が成立したことを通知する（ステップＳ１０）。
上記ケース(a), (b)の何れの場合も、取引が成立しなかった購入者用装置、販売者用装置には取引が不成立であったことを通知する（ステップＳ１１）。
【０００９】
ステップＳ８の条件が成立しない場合、即ち、ケース(b)の場合、購入者の支払う価格b(k) は販売者の受け取る価格s(k) と等しいかそれより大きいため、(k-1)(b(k)−s(k))の金額が余ることになる。この差分はオークションの主催者が得ることとする。
以下に示す架空名義入札が存在しない場合、各入札者は、財の割当方法に対して、正しい評価値、即ち、購入者にとってはそれを越す金額は支払う意思がない、上限の評価値、販売者にとっては、それ未満では売る意思のない、下限の評価値を入札することにより、自分の利益を最大化できることが知られている。この性質は誘因両立性と呼ばれる。誘因両立性が成立する場合、通常の電子式入札方法のように、入札値を他の入札者に知られないように秘匿する必要がなく、電子式入札を容易に行うことが可能になる。
【００１０】
【発明が解決しようとする課題】
インターネットに代表される、電気通信システムを用いた電子入札においては、単一の入札者が、複数の名義（例えば異なる電子メールアドレス）を用いて、複数の入札を行うことが容易に可能である。これを架空名義入札と呼ぶ。
架空名義入札が可能な場合に、ＰＭＤプロトコルは誘因両立性を満足しない。以下に例を示す。
例１：購入者／販売者の評価値は以下の通りであるとする。
【００１１】
・購入者の評価値：９＞８＞７＞４
・販売者の評価値：２＜３＜４＜５
参加者が真の評価値を表明した場合、
b(3) ＝７＞ s(3) ＝４、
b(4) ＝４＜ s(4) ＝５、
p0 ＝(b(4)＋s(4))/2 ＝ (4＋5)/2＝4.5、
s(3) ＝４＜ p0 ＝ 4.5 ＜ b(3) ＝７、
でありプロトコルのケース(a)が適用され、販売者及び購買者の(1)番目から(3)番目までが取引を行い、取引価格p0 ＝4.5となる。一方、(1)番目から(3)番目までのいずれかの販売者が、購入者になりすまして4.8なる評価値を表明した場合、
・購入者の評価値：９＞８＞７＞4.8＞４
・販売者の評価値：２＜３＜４＜５
となり、b(3)＝７＞ s(3)＝４及びb(4)＝4.8 ＜ s(4)＝５が成り立ち、(1)番目から(3)番目までが取引を行うことは変わらないが、p0＝(b(4)＋s(4))/２＝(4.8＋5)/2＝4.9となり、かつb(3)＝７＞ p0＝4.9 ＞ s(3)＝４が成立するため、取引価格はp0 となり販売者は4.9を得ることになる。つまり販売者は、購入者になりすました架空名義入札を行うことにより利益を0.4増やすことが可能であり、ＰＭＤプロトコルは架空名義入札に対して頑健でない。
例２：購入者／販売者の評価値は以下の通りであるとする。
【００１２】
・購入者の評価値：９＞８＞７＞４
・販売者の評価値：２＜３＜４＜１２
参加者が真の評価値を表明した場合、
b(3) ＝７＞ s(3)＝４，
b(4) ＝４＜ s(4)＝１２、
p0 ＝(b(4)＋s(4))/2＝(4＋12)/2＝８、
となり、s(3)＜ p0＜ b(3)とならず、プロトコルのケース(b)が適用され、(1)番目から(2)番目までが取引を行い、購入者(1), (2)はb(3)＝７を支払い、販売者(1), (2)はs(3)＝４を得る。
例３：一方、上記例２において販売者(3)は、別の販売者になりすまして、６なる評価値を表明することが可能である。この結果、
・購入者の評価値：９＞８＞７＞４
・販売者の評価値：２＜３＜４＜６＜１２
となり、
b(3)＝７＞ s(3)＝４、
b(4)＝４＜ s(4)＝６、
p0 ＝(b(4)＋s(4))/２＝(4＋6)/2＝５、
s(3)＝４＜ p0＝５＜ b(3)＝７
となりプロトコルのケース(a)が適用され、(1)番目から(3)番目までが取引を行い、取引価格はp0 ＝５となる。販売者(3)は、上記例２のように正直に申告した場合は取引を行えないので利益は０であるが、例３のように上記の架空名義入札をした場合は、販売に成功する上に、販売価格が例２で示した希望より５−４＝１だけ高くなり、それだけ大きい利益を得ることが可能となる。
【００１３】
この発明の目的は、このような問題点を改め、架空名義入札が可能な場合においても、誘因両立性が保証される取引決定方法、それを使ったネットワークオークション方法、その主催者装置及び方法をコンピュータで実行するプログラムが記録された記録媒体を提供することにある。
【００１４】
【課題を解決するための手段】
この発明による、双方向電子式入札の主催者用装置における取引成立決定方法は、
(a) 入札された購入者の評価値と販売者の評価値が記憶された記憶部から購入者の評価値を読み出し、大きい順に配列して購入者評価値配列を求め、上記記憶部から販売者の評価値を読み出し、小さい順に配列して販売者評価値配列を求めるステップと、
(b) 上記購入者評価値配列における予め主催者が決めた閾値価格以上の最小評価値の順位ｉと、上記販売者評価値配列における上記閾値価格以下の最大の評価値の順位ｊとを決定するステップと、
(c) 上記順位ｉとｊの大きさの関係を判定するステップと、
(d) 上記ステップ(c) で上記順位ｉとｊが等しいと判定されると１番目からｉ番目までの購入者と販売者に対し、上記閾値価格を取引価格として取引成立を決定するステップと、
(e) 上記ステップ(c) で上記順位ｉがｊより大であると判定されると、１番目からｊ番目の購入者に対し、ｊ＋１番目の購入者評価値を取引価格として取引成立を決定し、１番目からｊ番目の販売者に対し上記閾値価格を取引価格として取引成立を決定するステップと、
(f) 上記ステップ(c) で上記順位ｉがｊより小であると判定されると、１番目からｉ番目の購入者に対し上記閾値価格を取引価格として取引成立を決定し、１番目からｉ番目の販売者に対しｉ＋１番目の販売者評価値を取引価格として取引成立を決定するステップ、
とを含む。
【００１５】
上記取引成立決定方法のステップ(e) 及び(f) の代わりに、
(e) 上記ステップ(c) で上記順位ｉがｊより大であると判定されると、入札した評価値が１番目からｊ番目までにｋ個含まれている購入者に対し、
【００１６】
【数３】
0003723757.tif 000002
【００１７】
をｋ個のユニットに対する支払額とする取引成立を決定し、１番目からｊ番目の販売者に対し上記閾値価格ｒを取引価格として取引成立を決定するステップと、ただし、max(b, r)はｂとｒのうち大きいほうの値を表し、b(h)~xは、購入者ｘの評価値をのぞいて、ｈ番目に大きい評価値を表し、
(f) 上記ステップ(c) で上記順位ｉがｊより小であると判定されると、１番目からｉ番目の購入者に対し上記閾値価格ｒを取引価格として取引成立を決定し、１番目からｉ番目の各ｋ個のユニットを販売する販売者に対し
【００１８】
【数４】
0003723757.tif 000003
【００１９】
の値を取引価格として取引成立を決定するステップ、ただし、min(s, r)はｓとｒのうち小さいほうの値を表し、s(h)~yは、販売者ｙの評価値をのぞいて、ｈ番目に小さい評価値を表し、
を実行してもよい。
この発明によるネットワークオークション方法は、
(A) 評価値が記された入札希望通知を販売者及び購入者から受信するステップと、
(B) 上記入札希望通知を受信すると、それらの購入者及び販売者とその評価値を対応づけて記憶部に記憶するステップと、
(C) 入札締切り期限になったか否か調べるステップと、
(D) 入札締切り期限になると、前記記載のいずれかの取引成立決定方法により、取引の成立を決定するステップと、
(E) 取引の成立が決定した各購入者の購入者用装置及び販売者の販売者用装置それぞれ決定した取引価格を含む取引成立通知を送信し、取引が成立しなかった各購入者の購入者用装置及び各販売者の販売者用装置にそれぞれ取引不成立通知を送信するステップ、
とを含む。
【００２０】
この発明による双方向電子式入札の主催者装置は、
購入者用装置、販売者用装置とネットワークを介して通信することができる通信装置と、
各上記購入者用装置及び販売者用装置から上記通信装置により受信した評価値が記された入札希望通知を、その購入者、販売者とその評価値を対応させて記憶する記憶部と、
主催者が予め決めた閾価格値ｒが格納された閾値格納部と、
上記記憶部から購入者の評価値を読み出し、大きい順に配列して購入者評価値配列を求め、上記記憶部から販売者の評価値を読み出し、小さい順に配列して販売者評価値配列を求める評価値配列生成部と、
上記購入者評価値配列における上記閾値価格以上の最小評価値の順位ｉと、上記販売者評価値配列における上記閾値価格以下の最大の評価値の順位ｊとを決定する順位決定部と、
上記順位ｉとｊの大きさの関係を判定する判定部と、
上記判定部により上記順位ｉとｊが等しいと判定されると１番目からｉ番目までの購入者と販売者に対し、上記閾値価格を取引価格として取引成立を決定し、
上記順位ｉがｊより大であると判定されると、１番目からｊ番目の購入者に対し、ｊ＋１番目の購入者評価値を取引価格として取引成立を決定し、１番目からｊ番目の販売者に対し上記閾値価格を取引価格として取引成立を決定し、
上記順位ｉがｊより小であると判定されると、１番目からｉ番目の購入者に対し上記閾値価格を取引価格として取引成立を決定し、１番目からｉ番目の販売者に対しｉ＋１番目の販売者評価値を取引価格として取引成立を決定する取引決定部と、
決定された取引が入力され、入札結果通知を生成し、これら通知を上記通信装置により対応する購入者用装置及び販売者用装置に送信させる入札結果通知生成部、
とを含むように構成される。
【００２１】
【発明の実施の形態】
発明の原理
この発明では、財の双方向電子式入札により取引する際に、財に関して閾値価格（購入者に対しその価格未満では販売しない下限、及び販売者に対しその価格より高い価格では購入しない上限の価格）ｒを設定し、この閾値価格ｒを用いて、取引の数及び取引価格の制御を行う。この発明の方法を閾値価格ダブルオークションプロトコル（Threshold Price Double Auction Protocol,TPD Protocol）と呼ぶ。以下この発明の原理を説明する。
【００２２】
オークションの主催者は閾値価格ｒを設定する。次に、購入者／販売者は評価値を表明する。表明された評価値は以下の通りであるとする。
・表明された購入者の評価値：b(1) ＞b(2) ＞…＞b(i) ＞ｒ＞b(i+1) ,…
・表明された販売者の評価値：s(1) ＜s(2) ＜…＜s(j) ＜ｒ＜s(j+1) ,…
プロトコルは以下のように記述される。
(a) ｉ＝ｊの場合：(1)番目から(i)番目までの購入者及び販売者が、価格ｒで取引を行う。
【００２３】
(b) ｉ＞ｊの場合：(1)番目から(j)番目までの購入者及び販売者が取引を行う。購入者はb(j+1) を支払い、販売者はｒを得る。オークションの主催者はｊ・（b(j+1) −ｒ）を得る。
(c) ｉ＜ｊの場合：(1)番目から(i)番目までの購入者及び販売者が取引を行う。購入者はｒを支払い、販売者はs(i+1) を得る。オークションの主催者はi(r−s(i+1))を得る。
上記条件(b) において、ｉ＞ｊ、即ちｉ>j+1なので、b(j+1)＞b(i)が成立する。従って(b(j+1)-r)＞(b(i)-r)＞0が成立する。同様に上記条件(c) において、ｉ＜ｊ，即ちi+1＜jなので、s(i+1)＜s(j)が成立する。従って(r-s(i+1))＞r-s(j)＞0が成立する。
【００２４】
以下、この発明の方法が誘因両立性を満足することを証明する。以下、購入者と販売者は対称であるため、購入者にとってこの方法が誘因両立性を満たすことを示す。販売者にとって真の評価値を申告することが誘因両立性を満たすことは、同様に証明可能である。
まず、以下の性質を証明する。
性質１：このプロトコルで購入者が、架空名義入札を用いて複数の購入者として入札を行う場合と比べ、単一の名義で入札した方がその購入者にとって利益は同じか増加する。
【００２５】
証明は以下の通りである。購入者ｘが、x'，x"なる二つの名義で、bx', bx" なる入札を行っているとする（bx'＞bx" と仮定する）。ここで、購入者ｘがx"の名義での入札bx" を取りやめて、bx'のみを入札した方が、利益は同じか増加することを示す。
購入者の支払価格は、プロトコルの条件(a)及び(c)のいずれかが成立する場合は閾値価格ｒであり、条件(b)が成立する場合は(j+1)番目に高い購入者の評価値であるb(j+1) である。いずれの場合でも、bx" の入札を取りやめれば、支払額は同じか減少する。
【００２６】
以下、架空名義を用いていた場合にｘが得ていた財の数で分類して証明を行う。
(i) 架空名義を用いた場合に、財を二単位得られた場合：各購入者の需要は一単位であることを仮定しているため、一単位余分に購入することになり、明らかにbx" の入札を取りやめた方が利益は増加する。
(ii) 架空名義を用いた場合に、財を一単位得られた場合：bx" の入札を取りやめてもbx'＞bx" であるから財が一単位得られることは変らない。支払額がｒであればx"を入札しないのと同じである。支払額がb(j+1)の場合、b(j+1)＞b(j+2)なので、もしbx" ＝b(j+1) であったとすると、bx"を入札しなかった場合より支払額は大となるか等しいため、bx" の入札を取りやめた方が利益は同じか増加する。
【００２７】
なお厳密にはランダムなタイブレークを考慮する必要があるが、タイブレークの対象となる場合は、財を得ても利益は０であり、財を得ない場合と利益は同じである。
(iii) 架空名義を用いた場合に、財が得られない場合：bx" の入札を取りやめても財を得られることはなく、利益は０で変化しない。
以上で、購入者が架空名義入札を用いて二人の購入者として入札を行う場合と比べ、単独の名義で入札を行った方が利益は同じか増加することが示された。同様に、３つ以上の名義で入札を行った場合でも、単独の名義で入札を行った方が利益は同じか増加することを示すことができる。
【００２８】
次に、以下の性質を証明する。
性質２：このプロトコルで購入者が、架空名義入札を用いて販売者の入札を行う場合、この架空名義入札によって取引数／購入者の支払額が変化するのは、架空名義の販売者の入札が取引の対象となる場合のみである。
販売者の入札が増えることで取引数／購入者の支払額が変化するのは、架空名義入札が無い場合に、プロトコルでｉ＞ｊの場合のみである。明らかにｉ＜ｊであれば（閾値価格以下の販売者の入札の方が、閾値価格以上の購入者の入札よりも同じか多ければ）、新しく販売者の入札を加えても、取引数及び購入者の支払額は変化しない。一方、ｉ＞ｊの場合、購入者ｘがｙなる名義で、sy なる販売者の入札を行ったとする。明らかに、sy ＜ｒでなければ、取引数及び購入者の支払額は変化しない。しかしながら、sy ＜ｒなる入札を行うと、この入札sy は取引対象となる。
【００２９】
実際には購入者ｘは財を保有していないため、sy が取引対象となってしまうと、架空名義入札をしたことが露見してしまう。露見した架空名義入札に対して十分大きなペナルティが課せられるとすれば、購入者は販売者になりすます架空名義入札を行わない方が利益は同じかより大きくなる。
なお、販売者の側から考えると、販売者が架空名義を用いて購入者の入札を出した場合、この入札が取引対象となっても、この販売者は財を購入することが可能で、架空名義入札は露見しない。しかしながらこの場合には、販売者は財を一単位売って一単位買うことになり、販売者の価格は必ず購入者の価格以下であるため、正の利益を得ることは不可能である。
【００３０】
性質１，２より、以下の性質が導かれる。
性質３：露見した架空名義入札に十分大きなペナルティが課せられる場合、購入者は架空名義入札を用いないで入札した方が利益は同じか増加する。
性質３より、購入者は単独の名義で入札した方が利益は同じか増加することが示された。次に、以下の性質を証明する。
性質４  購入者が架空名義を用いずに単一の名義で入札をする場合、真の評価値を表明することにより自身の利益が最大化される。
【００３１】
購入者ｘの真の評価値をbxtとする。まず、bxt＜ｒの場合は、支払額がｒ未満になることはないため、評価値を過大に申告することは無駄である。また、bxt＞ｒで、ｘが正直に申告して財を得られる場合には、過大／過少申告しても、財を得ている限り支払額は変化せず、過大／過少申告しても利益はない。また、bxt＞ｒで、ｘが正直に申告した場合に財を得られないとすると、プロトコルの条件(b) が成立しており、支払額はb(j+1) である。b(j+1) ＞bxtであり、過大申告しても支払額はb(j+1) 未満になることはなく、ｘは正の利益を得ることはできない。上記より、真の評価値を表明することが支配戦略であることが導かれる。
【００３２】
これらの性質より、露見した架空名義入札に十分大きなペナルティが課せられる場合には、このプロトコルにおいて、各購入者は、架空名義入札を行わず、真の評価値を表明することにより、自身の利益が最大化されることが得られた。
これらの性質より、この発明により誘因両立性が保証されることが示される。
実施例
以下この発明の実施例を説明する。この発明の方法が適用されるネットワークオークションシステムの構成例は例えば図１に示した構成と同様なものである。このシステムにおいて、各販売者は販売者用装置1-1，…,1-nにより、これ未満では売る意思がない、下限の評価値を含む入札希望通知を主催者用装置１２へ送信し、また各購入者は購入者用装置2-1，…,2-mにより、これを越す金額は支払う意思がない、上限の評価値を含む入札希望通知を主催者用装置１２へ送信する。
【００３３】
主催者用装置１２は例えばコンピュータによりプログラムを実行させることにより動作させることができる。つまり例えば図３に示すように、図１に示した通信ネットワーク１１を通じて販売者用装置1-1，…,1-n、購入者用装置2-1，…,2-mと通信することができる通信装置２１、記憶部２２、閾値価格ｒを格納する閾値格納部２３、キーボードなどの入力装置２４、時計２５、プログラムを格納したメモリ２６、ＣＰＵ２７がバス２８に接続され、ＣＰＵ２７がメモリ２６のプログラムを実行して、主催者用装置１２の動作を行う。主催者は入力装置２４により閾値価格ｒを閾値格納部２３に予め格納しておく。閾値価格ｒは任意の値でよいが、取引が成立する数が最大になるような値を予測して決める。例えば株や為替相場等の場合、閾値設定前の価格の推移から予測計算を行って決定する。あるいは単純には、主催者のそれまでの競争入札での売買実績から決定するなどが考えられる。
【００３４】
この主催者用装置１２は例えば図４に示すような処理手順を実行する。図４中のステップＳ１〜Ｓ５は図２中のステップＳ１〜Ｓ５と同様な処理である。つまり入札希望通知を受信すると（ステップＳ１）、その入札希望通知の購入者又は販売者とその評価値を組として記憶部２２に記憶する（ステップＳ２）、入札締切り期限が来るまで、入札希望通知を受信する。入札締切り期限が来ると（ステップＳ３）、記憶部２２から購入者評価値を読み出し、大きい順に配列して記憶部２２に格納し（ステップＳ４）、また記憶部２２から販売者評価値を読み出し、小さい順に配列して記憶部２２に格納する（ステップＳ５）。
【００３５】
この実施例では記憶部２２から購入者評価値、販売者評価値を読み出し、また格納部２３から閾値価格ｒを取出し、ｒ以上の最小購入者評価値b(i) の順位ｉと、ｒ以下の最大販売者評価値s(j) の順位ｊを決定する（ステップＳ６）。つまり下記の関係を求める。
b(1) ＞b(2) ＞…＞b(i) ＞ｒ＞b(i+1) …                (1)
s(1) ＜s(2) ＜…＜s(j)＜ｒ＜s(j+1) …                (2)
つぎにステップＳ６で決定したｉとｊが存在したかを確認し（ステップＳ７）、共に存在していたら、ｉ＝ｊかを判断し（ステップＳ８）、ｉ＝ｊであれば、１番目からｉ＝ｊ番目の各評価値の各購入者と各販売者に対し取引価格ｒを決定する（ステップＳ９）。
【００３６】
ステップＳ８でｉ＝ｊでなければ、ｉ＞ｊかを調べ（ステップＳ１０）、ｉ＞ｊであれば、１番目からｊ番目の各購入者に対し取引価格b(j+1) を、各販売者に取引価格ｒをそれぞれ決定する（ステップＳ１１）。ｉ＞j+1なので、取引価格b(j+1)の値はb(j+1)＞b(i)＞rを満足している。ステップＳ１０でｉ＞ｊでなけば、即ちｉ＜ｊであれば、１番目からｉ番目の各購入者に対し取引価格ｒを、各販売者に対し取引価格s(i+1) とそれぞれ決定する（ステップＳ１２）。i+1＜ｊなので、取引価格s(i+1)はs(i+1)＜s(j)＜rを満足している。
【００３７】
ステップＳ９あるいはステップＳ１１又はステップＳ１２でそれぞれ決定された購入者とその取引価格（支払う価格）及び販売者とその取引価格（受取る価格）をそれぞれその購入者の装置、販売者の装置に取引成立通知として送信し、取引成立通知を行わない残りの購入者用装置及び販売者用装置に取引不成立通知を行う（ステップＳ１３）。またステップＳ７でｉとｊの少なくとも一方が存在しなかった場合は、全ての購入者用装置及び販売者用装置に取引不成立通知を送信する（ステップＳ１４）。
【００３８】
以上の動作を行う主催者用装置１２の機能構成は図５に示すようになる。つまり通信装置２１、記憶部２２、閾値格納部２３、入力装置２４、時計２５、制御部２７、評価値を大小順に配列する評価値配列部３１、閾値価格ｒ以上の最小購入者評価値の順位ｉ、ｒ以下の最大販売者評価値の順位ｊを決定する順位決定部３４、順位ｉ，ｊの大小関係を判定する判定部３５、購入者及び販売者とその各取引価格を決定する取引決定部３２、入札結果、つまり取引成立通知、及び取引不成立通知を生成する入札結果生成部３３よりなり、これらは共通バス２８により互いに接続されている。
【００３９】
通信装置２１に受信した入札希望通知は記憶部２２に記憶される。入札締切りになると、評価値配列部３１は記憶部２２から評価値を読み出し、購入者の評価値は大きい順に、販売者の評価値は小さい順にそれぞれ配列して購入者評価値配列と販売者評価値配列を生成する。順位決定部３４はこれら評価値配列と、閾値価格ｒから、閾値価格ｒ以上の最小購入者評価値の順位ｉと、ｒ以下の最大販売者評価値の順位ｊとを決定し、判定部３５はこれら順位ｉ，ｊ間の大小関係を判定する。取引決定部３２は順位ｉとｊの大小関係に基づいて、図４中のステップＳ９、Ｓ１１及びＳ１２の取引の決定を行う。入札結果通知生成部３３はその結果に基づいて、取引成立通知、取引不成立通知を生成し、これら入札結果通知を通信装置２１により、対応する購入者用装置、販売者用装置へ送信する。制御部２７は上記各部の処理の制御と、それら間のデータ転送の制御を行う。
【００４０】
図５の主催者装置をコンピュータにより実現する場合は、評価値配列部３１、取引決定部３２、入札結果生成部３３、順位決定部３４及び判定部３５はそれぞれの処理を実行する一連のプログラムとして記録媒体３０に記録されており、制御部２７はそのプログラムの実行を制御する。
次にこの発明によれば、従来技術で問題となったことが解決されることを以下に具体的な適用例を上げて示す。
例４：評価値は例１と同様で、以下の通りとする。
【００４１】
・購入者の評価値：９＞８＞７＞４
・販売者の評価値：２＜３＜４＜５
また、閾値価格ｒが4.5であるとする。この場合、b(i)＝b(3)＝7及びs(j)＝s(3)＝５となりプロトコルの条件(a)が成立し、(1)番目から(3)番目までが取引を行い、取引価格はｒ＝4.5となる。
例１の場合と同様に(1)番目から(3)番目までのいずれかの販売者が、購入者になりすまして4.8なる評価値を表明した場合、評価値配列は
・購入者の評価値：９＞８＞７＞4.8＞４
・販売者の評価値：２＜３＜４＜５
である。これらからb(i)＝b(4)＝4.8及びs(j)＝s(3)＝４となり、従ってｉ＝４＞ｊ＝３なのでプロトコルの条件(b)が成立し、(1)番目からｊ＝３番目の購入者、販売者が取引を行い、購入者の支払額はb(j+1)＝b(4)＝4.8、販売者の得る額はｒ＝4.5となり、購入者の支払額は増えるが、販売者の得る金額は閾値価格の4.5で変化しない。即ち、販売者が購入者に成りすましても得をしない。
【００４２】
例５：評価値は例２と同様で、以下の通りとする。
・購入者の評価値：９＞８＞７＞４
・販売者の評価値：２＜３＜４＜１２
閾値価格ｒが６であれば、プロトコルの条件(a)が成立し、(1)番目から(3)番目までが取引を行い、価格は６である。
例２の場合と同様に(3)番目の販売者が別の販売者になりすまして６なる評価値を表明すると、評価値配列は
・購入者の評価値：９＞８＞７＞４
・販売者の評価値：２＜３＜４＜６＜１２
である。これらからb(i)＝b(3)＝7及びs(j)＝s(4)＝6となり、従ってｉ＝３＜ｊ＝４なのでプロトコルの条件(c)が成立し、(1)番目から(3)番目までの購入者、販売者が取引を行い、購入者はｒ＝６を支払い、販売者はs(i+1)＝s(4)＝６を得る。従って、(3)番目の販売者は受ける価格は同一となる。
【００４３】
一方、閾値価格ｒが7.5の場合は、(3)番目の販売者がなりすましをしない場合は、b(i)＝b(2)＝8, s(j)＝s(3)＝4, ｉ＝２＜ｊ＝３となり、プロトコルの条件(c)が成立し、(1)番目から(2)番目の購入者、販売者が取引を行い、購入者はｒ＝7.5を支払い、販売者はs(i+1)＝s(3)＝４を得る。
(3)番目の販売者が別の販売者になりすまして、６なる評価値を表明すると、b(i)＝b(2)＝8及びs(j)＝s(4)＝6となり、従ってｉ＝２＜ｊ＝４なので(1)番目から(2)番目の購入者と販売者が取引を行い、なりすましがなされない場合と同一条件となり、販売者は得をすることはない。
【００４４】
上述したこの発明によるＴＰＤプロトコルにおける閾値価格ｒは基本的にはどのような方法で決めてもよいが、社会的利益ができるだけ大となるように、例えば次のようにして決めてもよい。
オークションの主催者は、過去のデータなどを用いて、どのような販売者／購入者が、どれだけの数存在するかについての確立モデルを構築する。例えば、販売者／購入者の評価値は０〜100までの一様分布（どの評価値も同じくらい存在し得る）で、販売者、購入者の数はそれぞれ例えば500名程度とする。
【００４５】
上記のモデルを用いて、生じ得る入札状況の候補を生成する。例えば、乱数を用いて、評価値が０〜100の間の販売者／購入者をそれぞれ500生成したものを１つの候補とする。
このような候補を十分な数、例えば1000通り生成する。生成された各候補に関して、閾値価格ｒを適当な間隔で変化させ、それぞれ得られる社会的余剰を計算し、各閾値価格ｒに対するすべての候補の社会的余剰の平均を求める。社会的余剰とは、与えられた閾値価格ｒに対し、オークションのプロトコルに従って決定された販売者の受け取り金額及び購入者の支払い金額と、それらに対応する販売者及び購入者の評価値との差である利益（余剰）を全入札成功者について加算した金額と、オークション主催者が得る金額との合算値である。このような社会的余剰をそれぞれの閾値価格ｒについて計算する。
【００４６】
図６はそのようにして求めた閾値価格ｒの変化に対する平均社会的余剰の変化を示す。図６の例では1000個の候補のそれぞれについて閾値価格ｒを０から100間で１０ずつ変化させ、各閾値価格ｒに対し求めた1000個の社会的余剰の平均を曲線６ａで示し、主催者の利益を除いた社会的余剰の平均を曲線６ｂで示す。また、曲線６ａの社会的余剰の最大値をPareto Efficientな社会的余剰として直線６ｃで示す。図６に基づいて、平均社会的余剰を最大にする閾値価格ｒの値を５０に決定する。このような手順で閾値価格ｒを決めることにより、販売者、購入者、主催者の全てに公平な落札価格を決めることができる。
【００４７】
前述のこの発明によるＴＰＤプロトコルでは、各販売者及び各購入者も財１ユニットの売買について入札を行う場合を示したが、各販売者及び購入者が複数ユニットの財をそれぞれ所望の評価値で入札する場合の入札プロトコルに拡張することができる。以下に拡張ＴＰＤプロトコルについて説明する。
ダブルオークションで扱われる典型的な財である外貨、証券、株などの取引を考えた場合、需要／供給が複数ユニットであることがほとんどであり、このような拡張は実用上きわめて重要である。すべての参加者でユニットの限界効用が逓減する場合には、前述のＴＰＤプロトコルの簡単な拡張により対応することができる。ユニットの限界効用とは、財１ユニットの追加に対する効用の増加分を意味する。例えば、どうしても100株必要といったような特殊な場合を除き、限界効用が逓減するという仮定は妥当である。
【００４８】
購入者ｘの評価値をbx,1, bx,2, bx,3, ...のように記述する。ここで、bx,kは、購入者ｘのｋ個目のユニットに対する限界効用、即ち、すでにk-1個のユニットを保有していると仮定した場合に、更にもう１つのユニットを得た場合の効用の増分を表す。限界効用逓減という仮定により、すべてのｘ，ｋに関して、bx,k＞ bx,k+1 が成立する。限界効用逓減という仮定は、外貨、証券、株などの取引を考えた場合には自然であると考えられる。同様に、販売者ｙの財１ユニットに対する効用をsy,1, sy,2, sy,3, ...のように記述する。注意すべき点は、３ユニットの財を販売しようとしている販売者ｙの、最初の１つの財を販売する（従って２個の財を手元に残す）場合の、許容できる最低の販売価格はsy,1ではなく、sy,3で表現されることである。同様に、２個の財を販売する場合の許容できる最低の販売価格はsy,2+sy,3となる。
【００４９】
図７は複数ユニットの入札を可能とする拡張ＴＰＤプロトコルに基づく主催者用装置の処理手順を示す。ステップＳ１〜Ｓ１０及びＳ１３、Ｓ１４は図４の実施例における処理ステップと全く同様であり、以下には主要な処理ステップのみを説明する。
閾値価格をｒとして、全ての購入者の１ユニットに対する全ての評価値を大きい順にソートした列を
b(1)＞b(2)＞...＞b(i)＞ｒ＞b(i+1)＞...           (3)
とし（ステップＳ４）、全ての販売者の１ユニットに対する全ての評価値を小さい順にソートした列を
s(1)＜s(2)＜...＜s(j)＜ｒ＜s(j+1)＜...            (4)
とする（ステップＳ５）。これらの評価値配列(3), (4)に基づいて閾値価格ｒ以上の最小購入者評価値b(i)の順位ｉと、閾値価格ｒ以下の最大販売者評価値s(j)の順位ｊを決める（ステップＳ６）。
【００５０】
プロトコルは以下のように記述される。
(a) ｉ＝ｊの場合：(1)から(i)までの購入者／販売者が、各ユニットに関して価格ｒで取引を行う（ステップＳ８，Ｓ９）。
(b) ｉ＞ｊの場合：(1)から(j)までの購入者／販売者が取引を行う。販売者は各ユニットに関して販売金額ｒで取引を行う。入札した評価値が１番目からｊ番目までにｋ個含まれている購入者ｘは、ｋ個のユニットに対し合計
【００５１】
【数５】
0003723757.tif 000004
【００５２】
を支払う（ステップＳ１０，Ｓ１１）。ただし、max(b, r)はｂとｒのうち大きいほうの値を表し、b(h)~xは、購入者ｘの評価値をのぞいて、ｈ番目に大きい評価値を表す。販売者と購入者の支払額の差額はオークションの主催者が得る。
(c) ｉ＜ｊの場合：(1)から(i)までの購入者／販売者が取引を行う。購入者は各ユニットに関してｒを支払い、ｋ個のユニットを手放した販売者ｙは、合計
【００５３】
【数６】
0003723757.tif 000005
【００５４】
を得る（ステップＳ１２）。ただし、min(s, r)はｓとｒのうち小さいほうの値を表し、s(h)~yは、販売者ｙの評価値をのぞいて、ｈ番目に小さい評価値を意味する。販売者と購入者の支払額の差額はオークションの主催者が得る。
プロトコルの適用例を以下に示す。購入者／販売者の評価値は以下のとおりであるとする。
・購入者の評価値：９＞８＞７＞６＞４
・販売者の評価値：２＜３＜４＜５＜７
閾値価格ｒを4.5とし、購入者の評価値９と８は同じ購入者ｘのもので、他の評価値はすべて異なる販売者／購入者のものであるとする。プロトコルの２番目の条件が成立し、上記３つの入札に関して取引が行われる。販売者は閾値価格である4.5を得る。２ユニットを得ている購入者ｘの支払額は以下のように計算される。
【００５５】
【数７】
0003723757.tif 000006
【００５６】
購入者ｘの評価値９、８を除く２番目に大きい評価値はb(2)~x＝６であり、購入者の評価値９、８を除く３番目に大きい評価値はb(3)~x＝４である。前者は4.5より大きいのでmax(b(2)~x, 4.5)＝６となり、後者は4.5より小さいのでmax(b(3)~x, 4.5)＝4.5となり、従って、支払額は6＋4.5=10.5となる。一方、１ユニットのみを得ている評価値７の購入者の支払額は、この購入者の評価値７を除いて３番目に大きい評価値である６となる。
限界効用が逓減するという仮定により、購入者のｋ番目のユニットに関する評価値が取引に含まれる場合は、必ずk-1番目のユニットに関する評価値も取引に含まれる。また、販売者に関しても、販売者のｋ番目のユニットに関する評価値が取引に含まれる場合は、k+1番目のユニットに関する評価値も（存在するならば）取引に含まれている。一方、限界効用が逓増する場合は、この性質が成立せず、このプロトコルのように各参加者の各ユニットに対する評価値をソートして取引を決定することはできない。
【００５７】
【発明の効果】
以上説明したように、この発明によれば、単一の入札者が複数の名義を用いる架空名義入札を行っても、入札者が利益を得ることがなく、各財に関する正しい評価値を入札することにより、各入札者の利益が最大化されることが保証される。
【図面の簡単な説明】
【図１】この発明が対象とする従来の電子式入札システムの一例を示す図。
【図２】従来の方法における主催者用装置の処理方法を示す流れ図。
【図３】この発明の主催者用装置の構成例を示す図。
【図４】この発明のＴＰＤプロトコルに基づく主催者用装置の処理手順を示す流れ図。
【図５】この発明の主催者用装置の他の実施例の機能構成を示す図。
【図６】閾値価格を決める方法を説明するためのグラフ。
【図７】この発明の拡張ＴＰＤプロトコルに基づく主催者用装置の処理手順を示す流れ図。
【図１】
0003723757.tif 000007
【図２】
0003723757.tif 000008
【図３】
0003723757.tif 000009
【図４】
0003723757.tif 000010
【図５】
0003723757.tif 000011
【図６】
0003723757.tif 000012
【図７】
0003723757.tif 000013