(57)【要約】  アイテムが、そのアイテムに大きく異なる評価をする2人の入札者の間で割り当てられる。割当ては、入札者のそれぞれがアイテムを割り当てられる確率に基づく。それぞれの入札者がアイテムを割り当てられる確率は、入札者から受信される値付けに適用される非線形関数に基づいて決定される。アイテムは、各入札者がアイテムを割り当てられる確率にしたがって半ランダムに割り当てられ得る。入札者は、アイテムを割り当てられるときにのみ自身の値付け価格を支払うことを要求される可能性があるか、または各入札者は、どの入札者がアイテムを割り当てられるかに関わらず全員負担価格を支払うことを要求される可能性がある。複数のオークションでアイテムが割り当てられる場合、入札者は、確率に基づく、整数で表される最小の回数だけアイテムを割り当てられることを保証され得る。
2012516517.tif 000002
【特許請求の範囲】
【請求項１】
第1の入札者および第2の入札者からアイテムに対する値付けデータを受信するステップと、
前記第1の入札者および前記第2の入札者のそれぞれに関して、前記入札者が前記アイテムを割り当てられる確率を定義する、前記入札者に対する割当て確率データを生成するステップと、
前記割当て確率データに基づいて前記アイテムを割り当てるステップと、
を含み、
前記値付けデータは、前記第1の入札者および前記第2の入札者のそれぞれに関する、前記アイテムの割当てに対するそれぞれの値付けを定義することを特徴とするコンピュータにより実施される方法。
【請求項２】
前記アイテムに対する全員負担価格を決定するステップをさらに含み、
前記全員負担価格は、どの入札者が前記アイテムを割り当てられるかに関わらず各入札者が支払う価格であることを特徴とする請求項1に記載の方法。
【請求項３】
前記アイテムに対する前記全員負担価格は、最低競売価格に基づいており、
前記最低競売価格は、前記アイテムのプロバイダが前記アイテムの割当てに対して許容する最小額であることを特徴とする請求項2に記載の方法。
【請求項４】
前記アイテムは、前記第1の入札者と前記第2の入札者の間で半ランダムに割り当てられ、
前記第1の入札者と前記第2の入札者の間での前記半ランダムな割当ては、前記割当て確率データに基づいて重み付けされることを特徴とする請求項1に記載の方法。
【請求項５】
前記割当て確率データは、前記それぞれの値付けの非線形関数に基づくことを特徴とする請求項1に記載の方法。
【請求項６】
前記非線形関数は、対数関数であることを特徴とする請求項5に記載の方法。
【請求項７】
前記生成するステップおよび前記割り当てるステップは、前記第1の入札者からの第1の値付けが、前記第2の入札者からの第2の値付けの少なくとも2倍以上であることを条件とすることを特徴とする請求項1に記載の方法。
【請求項８】
前記第1の値付けが、前記第2の値付けよりも高いが、前記第2の値付けの2倍未満である場合に、前記第1の入札者に前記アイテムを常に割り当てるステップをさらに含むことを特徴とする請求項7に記載の方法。
【請求項９】
割当て確率データを生成するステップは、
前記第1の入札者に関する第1の値付けの指数関数を決定するステップと、
前記第2の入札者に関する第2の値付けの指数関数を決定するステップと、
前記第1の値付けの前記指数関数の、前記第1の値付けの前記指数関数と前記第2の値付けの前記指数関数の合計に対する比に基づいて前記第1の入札者に対する割当て確率を決定するステップと、
前記第1の入札者に対する前記割当て確率の補数に基づいて前記第2の入札者に対する割当て確率を決定するステップと、
を含み、
前記第1の値付けの前記指数関数は、前記第1の値付けの、0から1の間の指数による累乗であり、
前記第2の値付けの前記指数関数は、前記第2の値付けの、0から1の間の指数による累乗であることを特徴とする請求項1に記載の方法。
【請求項１０】
値付けデータが受信された複数の入札者から第1の入札者および第2の入札者を特定するステップをさらに含み、
前記第1の入札者は、最も高い値付けが受信された入札者であり、
前記第2の入札者は、2番目に高い値付けが受信された入札者であることを特徴とする請求項1に記載の方法。
【請求項１１】
前記アイテムは、広告スロットであることを特徴とする請求項1に記載の方法。
【請求項１２】
広告を表示するためにパブリッシャーのプロパティ上で利用可能なスロットを定義するスロット構成データを受信し、第1の入札者および第2の入札者から前記スロットに対する値付けデータを受信する1つまたは複数のプロセッサを含む広告管理システムであって、前記値付けデータは、前記第1の入札者および前記第2の入札者のそれぞれに関する、前記スロットの割当てに対するそれぞれの値付けを定義する、広告管理システムと、
前記スロット構成データおよび前記それぞれの値付けを記憶する、前記広告管理システムに結合されたデータストアと、
前記スロットが前記第1の入札者および前記第2の入札者のそれぞれに割り当てられる確率を定義する割当て確率データを決定し、前記割当て確率データに基づいて前記第1の入札者と前記第2の入札者の間で前記スロットを割り当てるように動作可能な、前記広告管理システムおよび前記データストアに結合されたオークションサブシステムと、
を含むことを特徴とするシステム。
【請求項１３】
前記オークションサブシステムは、どの入札者が前記スロットを割り当てられるかに関わらず各入札者が支払う全員負担価格を決定するようにさらに動作可能であることを特徴とする請求項12に記載のシステム。
【請求項１４】
前記全員負担価格は、前記スロットを提供するパブリッシャーが前記スロットの割当てに対して許容する最小額を定義する最低競売価格に基づくことを特徴とする請求項13に記載のシステム。
【請求項１５】
前記割当て確率データは、前記それぞれの値付けの非線形関数に基づくことを特徴とする請求項12に記載のシステム。
【請求項１６】
前記スロットの前記割当ては、前記第1の入札者と前記第2の入札者の間での疑似ランダムな割当てであることを特徴とする請求項12に記載のシステム。
【請求項１７】
前記確率データに基づく前記割当ては、前記第1の入札者からの第1の値付けが、前記第2の入札者からの第2の値付けの少なくとも4倍以上であることを条件とすることを特徴とする請求項12に記載のシステム。
【請求項１８】
前記オークションサブシステムは、前記第1の値付けが、前記第2の値付けよりも高いが、前記第2の値付けの4倍未満である場合に、前記第1の入札者に前記スロットを割り当てるように動作可能であることを特徴とする請求項17に記載のシステム。
【請求項１９】
前記広告主管理システムおよび前記オークションサブシステムは、分散処理ネットワーク内の独立した処理システムとして実装されることを特徴とする請求項12に記載のシステム。
【請求項２０】
前記第1の入札者に対する前記割当て確率データは、第1の値付けの指数関数の、前記第1の値付けの前記指数関数と第2の値付けの前記指数関数の合計に対する比に基づくことを特徴とする請求項12に記載のシステム。
【請求項２１】
前記第2の入札者に対する前記割当て確率データは、前記第1の入札者に対する前記割当て確率データの補数に基づくことを特徴とする請求項20に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書は、アイテムの割当てに関する。
【背景技術】
【０００２】
ウェブページのパブリッシャーは、ウェブページの広告スロットを定義することができる。広告スロットは、ウェブページ上で広告が表示され得る、ウェブページの部分である。同様に、印刷メディアまたはその他の通信メディアのパブリッシャーは、発行されるメディアにとって適切な広告スロットを定義することができる(例えば、印刷メディアの広告スロット、ラジオメディアおよびテレビメディアの広告スポットなど)。
【０００３】
広告は、広告スロットのオークションに基づいて、広告スロットでの表示のために選択される可能性がある。オークションは、入札者から受信される値付けに基づいて、各広告スロットが割り当てられる入札者を特定することができる。広告スロットの割当てに対して入札者が支払う価格は、入札者から受信される次に高い値付けに基づく可能性がある。例えば、一般化されたセカンドプライスオークションにおいては、広告スロットは、広告スロットが割り当てられ得る入札者の中で最も高い値付けで入札した入札者に割り当てられる。広告スロットが割り当てられる入札者は、広告主によって入札された次に高い値付けに等しい価格を支払う。
【０００４】
広告スロットは広告スロットに対して最も高い値付けをした入札者に一貫して割り当てられ得るが、広告スロットを最も高い値付けをした入札者に割り当てることは、最適ではない結果をもたらす可能性がある。例えば、2人の入札者が、広告スロットに対して全く異なる最大限の値付けをする場合、広告主に対する広告スロットの価値は、最も高い値付けをした入札者に広告スロットを長期間割り当て続けることによっては実現されない可能性があり、その理由は、最も高い値付けをした入札者が、広告スロットを継続的に割り当てられることを踏まえて自分の値付けを引き下げる可能性があるからである。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】米国特許第6,285,999号
【非特許文献】
【０００６】
【非特許文献１】S. BrinおよびL. Page、「The Anatomy of a Large-Scale Hypertextual Search Engine」、Seventh International World Wide Web Conference、Brisbane、Australia
【発明の概要】
【課題を解決するための手段】
【０００７】
概して、本明細書に記載の対象の一態様は、第1の入札者および第2の入札者からアイテムに対する値付けデータを受信するアクションであって、値付けデータは、第1の入札者および第2の入札者のそれぞれに関する、アイテムの割当てに対するそれぞれの値付けを定義する、アクションと、第1の入札者および第2の入札者のそれぞれに関して、入札者がアイテムを割り当てられる確率を定義する、入札者に対する割当て確率データを生成するアクションと、割当て確率データに基づいてアイテムを割り当てるアクションとを含む方法で実施され得る。この態様のその他の実施形態は、対応するシステム、装置、およびコンピュータプログラム製品を含む。
【０００８】
これらのおよびその他の実施形態は、場合によっては、以下の特徴のうちの1つまたは複数を含む可能性がある。方法は、アイテムに対する全員負担価格(all-pay price)を決定するアクションをさらに含む可能性があり、全員負担価格は、どの入札者がアイテムを割り当てられるかに関わらず各入札者が支払う価格である。アイテムに対する全員負担価格は、最低競売価格に基づくことができ、最低競売価格は、アイテムのプロバイダがアイテムの割当てに対して許容する最小額である。アイテムは、第1の入札者と第2の入札者の間で半ランダムに割り当てられる可能性があり、第1の入札者と第2の入札者の間での半ランダムな割当ては、割当て確率データに基づいて重み付けされる。割当て確率データは、それぞれの値付けの非線形関数に基づくことができる。非線形関数は、対数関数であってよい。生成するアクションおよび割り当てるアクションは、第1の入札者からの第1の値付けが、第2の入札者からの第2の値付けの2倍以上であることを条件とする可能性がある。割当て確率データを生成するアクションは、第1の入札者に関する第1の値付けの指数関数を決定するアクションであって、第1の値付けの指数関数は、第1の値付けの、0から1の間の指数による累乗である、アクションと、第2の入札者に関する第2の値付けの指数関数を決定するアクションであって、第2の値付けの指数関数は、第2の値付けの、0から1の間の指数による累乗である、アクションと、第1の値付けの指数関数の、第1の値付けの指数関数と第2の値付けの指数関数の合計に対する比に基づいて第1の入札者に対する割当て確率を決定するアクションと、第1の入札者に対する割当て確率の補数に基づいて第2の入札者に対する割当て確率を決定するアクションとを含み得る。方法は、値付けデータが受信された複数の入札者から第1の入札者および第2の入札者を特定するアクションをさらに含む可能性があり、第1の入札者は、最も高い値付けが受信された入札者であり、第2の入札者は、2番目に高い値付けが受信された入札者である。アイテムは、広告スロットであってよい。
【０００９】
本明細書に記載の対象の特定の実施形態は、以下の利点のうちの1つまたは複数を実現するように実施され得る。広告スロットを総割当てのうちのある割合で2番目に高い値付けをした入札者に割り当てることによって、広告主に対する広告スロットの価値をより忠実に表す収入が得られる可能性がある。入札者は、入札者の値付けに基づいて広告スロットの総割当てのうちのある割合を保証され得る。入札者は、入札者が全員負担価格を払うことを要求される場合、広告スロットの最小回数の割当てを保証され得る。
【００１０】
本明細書に記載の対象の1つまたは複数の実施形態の詳細が、添付の図面および以下の説明に記載されている。対象のその他の特徴、態様、および利点は、それらの説明、図面、および特許請求の範囲から明らかになるであろう。
【図面の簡単な説明】
【００１１】
【図１】例示的なオンライン環境の構成図である。
【図２】広告スロットが割り当てられ得る例示的ウェブページの図である。
【図３Ａ】非線形スロット割当てのための例示的プロセスのフローチャートである。
【図３Ｂ】割当て確率データを生成するための例示的プロセスのフローチャートである。
【図３Ｃ】全員負担オークション(all-pay auction)のための広告スロットの非線形割当てのための例示的プロセスのフローチャートである。
【図４】広告スロットの非線形割当てを容易にするために使用され得る例示的なコンピュータシステムの構成図である。
【発明を実施するための形態】
【００１２】
さまざまな図面における同様の参照番号および参照指示は、同様の要素を示す。
【００１３】
オークションサブシステムが、プロバイダからのアイテムを、そのアイテムに大きく異なる評価をする2人の入札者の間で半ランダム（semi-random）に割り当てる。割当ては、1人の入札者のアイテムに対する値付けが、その他の入札者のアイテムに対する値付けの最小の倍数(例えば、2倍、3倍、またはその他の倍数)であることを条件とする可能性がある。各入札者に対するアイテムの相対的価値は、アイテムに対する入札者から受信された値付けによって表される。値付けは、入札者がアイテムの割当てに対して支払ってもよい最大限の額である。
【００１４】
アイテムの半ランダムな割当ては、入札者のそれぞれがアイテムを割り当てられる確率にしたがう。例えば、第1の入札者が、アイテムを割り当てられる確率が25%であり、第2の入札者が、アイテムを割り当てられる確率が75%である場合、半ランダムな割当ては、それぞれの確率が満足されるように実行され得る。それぞれの入札者がアイテムを割り当てられる確率は、その入札者の値付けに非線形関数が適用された結果とその他の入札者の値付けに非線形関数が適用された結果の合計に対する、その入札者の値付けに適用された非線形関数に基づく。このようにしてアイテムを割り当てることは、入札者によるアイテムの最大限の評価に非線形に対応する総収入をもたらす。一部の実施形態において、アイテムは広告スロットである。
【００１５】
本明細書を通じて、ウェブページのための広告スロットを割り当てることについて言及するが、広告スロットを割り当てるための以下で説明される方法およびシステムは、その他のコンテンツ環境(例えば、印刷メディアにおける構成、またはテレビメディアもしくはラジオメディアの時間帯の構成)に対して実施されてもよい。さらに、以下で説明される方法およびシステムは、その他のアイテムを割当てまたは販売するために実施されてもよい。
【００１６】
§1.0  広告の発行および追跡
図1は、例示的なオンライン環境100の構成図である。オンライン環境100は、コンテンツアイテム、例えば、ウェブページ、広告などを特定し、それらをユーザに対して提供することを容易にすることができる。ローカルエリアネットワーク(LAN)、広域ネットワーク(WAN)、インターネット、またはそれらの組合せなどのコンピュータネットワーク101は、広告主102、広告管理システム104、パブリッシャー106、ユーザデバイス108、および検索エンジン110を接続する。オンライン環境100は、何千もの広告主102、パブリッシャー106、およびユーザデバイス108を含み得る。
【００１７】
一部の実施形態において、1人または複数の広告主102は、広告管理システム104内の広告情報を直接的または間接的に入力し、保守し、追跡することができる。広告情報は、パブリッシャーのウェブページ上での表示のために広告主102が提供した広告を含むことができる。広告は、バナー広告などのグラフィカルな広告、テキストのみの広告、画像広告、音声広告、映像広告、そのような構成要素のいずれかの1つもしくは複数を組み合わせた広告など、または任意のその他の種類の電子広告ドキュメントの形態であってよい。また、広告は、リンク、メタ情報、および/またはHTMLもしくはJavaScript(登録商標)などの機械実行可能命令などの埋め込み情報を含んでもよい。広告情報、対応する広告および他の広告データは、広告管理システム104に結合された広告主データストア120に記憶され得る。
【００１８】
ユーザデバイス108は、ページコンテンツ要求112をパブリッシャー106または検索エンジン110に送ることができる。一部の実施形態において、ページコンテンツ114が、要求112に応答してユーザデバイス108に提供され得る。ページコンテンツ114は、広告管理システム104によって提供された広告を含む可能性があるか、または広告管理システム104からの広告を要求するためにユーザデバイス108で実行され得る実行可能命令、例えば、JavaScript(登録商標)を含む可能性がある。例示的なユーザデバイス108は、パーソナルコンピュータ、移動体通信デバイス、テレビのセットトップボックスなどを含む。
【００１９】
広告の要求は、パブリッシャー106からも受信され得る。例えば、1人または複数のパブリッシャー106は、広告管理システム104に1つまたは複数の広告の広告要求を送ることができる。システム104は、パブリッシャーのウェブプロパティ(例えば、ウェブサイト、およびその他のネットワークで配信されるコンテンツ)のうちの1つまたは複数で表示される広告スロットに掲載するための広告を要求元のパブリッシャー106に送信することによって応答する。広告は、ユーザがパブリッシャーのウェブプロパティ上に表示される広告を選択したときにユーザデバイス108が導かれるランディングページ(例えば、広告主102のウェブサイト上のページ)への埋め込みリンクを含むことができる。また、広告の要求は、コンテンツ要求情報を含む可能性がある。このコンテンツ要求情報は、コンテンツ自体(例えば、ページまたはその他のコンテンツドキュメント)、コンテンツまたはコンテンツ要求に対応するカテゴリ(例えば、芸術、ビジネス、コンピュータ、芸術-映画、芸術-音楽など)、コンテンツ要求の一部またはすべて、コンテンツの古さ、コンテンツの種類(例えば、テキスト、グラフィックス、映像、音声、混合メディアなど)、地理的位置情報などを含み得る。
【００２０】
一部の実施形態において、パブリッシャー106は、要求されたコンテンツを、システム104によって提供された広告のうちの1つまたは複数と組み合わせることができる。この組み合わされた要求されたコンテンツおよび広告が、コンテンツを要求したユーザデバイス108に、ビュアー(例えば、ブラウザまたはその他のコンテンツ表示システム)に表示するためのページコンテンツ114として送信され得る。パブリッシャー106は、広告がどのように、いつ、および/またはどこに表示されるべきかを(例えば、HTMLまたはJavaScript(登録商標)で)記述する情報を含む、広告についての情報を広告管理システム104に送り返すことができる。
【００２１】
パブリッシャー106は、コンテンツ(例えば、記事、議論のスレッド、音楽、映像、グラフィックス、検索結果、ウェブページの一覧、情報のフィードなど)の要求を受信し、その要求に応答して要求されたコンテンツを取り出す通常のコンテンツサーバを含んでよい。例えば、ニュースコンテンツプロバイダ、小売業者、個人運営のブログ、ソーシャルネットワークサイト、またはネットワーク101を介してコンテンツを提供する任意のその他の主体に関連するコンテンツサーバが、パブリッシャー106であり得る。
【００２２】
また、広告は、検索エンジン110を使用して提供され得る。検索エンジン110は、検索クエリを受信することができる。それに応答して、検索エンジン110は、(例えば、ウェブページのインデックスから)ドキュメントのインデックスにアクセスし、クエリに応じたドキュメントを特定する検索結果を生成する。例示的な検索エンジン110は、論文、S. BrinおよびL. Page、「The Anatomy of a Large-Scale Hypertextual Search Engine」、Seventh International World Wide Web Conference、Brisbane、Australiaおよび米国特許第6,285,999号に記載されている。検索結果は、例えば、ウェブページのタイトル、ウェブページから抽出されたテキストの断片、およびそれらのウェブページへのハイパーテキストリンクを含み得る。検索結果は、あらかじめ決められた数(例えば、10個)の検索結果にグループ分けされてもよい。
【００２３】
広告主102、ユーザデバイス108、および/または検索エンジン110が、広告管理システム104に利用情報を提供することもできる。この利用情報は、例えば、広告に関連するコンバージョンまたは選択が行われたか否かなど、提供された広告に関連する、測定または観察されたユーザの挙動を含み得る。システム104は、利用情報に基づいてパブリッシャー106への支払いおよび広告主102への請求などの金銭的な取引を行う。また、そのような利用情報は、インプレッション数、クリック率(「CTR」)、コンバージョン率などのパフォーマンス評価尺度を測定するために処理され得る。
【００２４】
インプレッションは、広告がユーザに対して表示されるときに起こる。インプレッション数は、広告がユーザに対して表示された回数を追跡する。例えば、ユーザデバイス108がウェブページを要求するとき、複数の広告が、ウェブページとともにユーザデバイス108に提供され得る。ウェブページとともに提供される広告のそれぞれは、広告インプレッションが起こったので、インプレッションカウンタをインクリメントすることができる。
【００２５】
クリックスルーは、例えば、ユーザデバイス108のユーザが、パブリッシャー106または広告管理システム104によって返されるコンテンツアイテムへのリンクを選択または「クリック」するときに起こり得る。CTRは、コンテンツアイテム、例えば、ランディングページへのリンク、広告、または検索結果をクリックしたユーザの数を、コンテンツアイテムがユーザデバイス108に送られた回数で割ることによって得られるパフォーマンス評価尺度である。
【００２６】
コンバージョンは、ユーザが、前に提供された広告に関連するトランザクションを完了するときに起こる。何がコンバージョンを構成するかは、場合によって異なる可能性があり、さまざまな方法で決定され得る。例えば、コンバージョンは、ユーザが広告をクリックし、広告主のウェブページに導かれ、そのウェブページを離れる前にそこで購入を完了するときに起こり得る。コンバージョンを構成するその他のアクションも、使用され得る。
【００２７】
§2.0  広告スロットの割当て
上で検討されたように、パブリッシャーのウェブページは、広告が表示され得る広告スロットを含むことができる。広告スロットがウェブページ上に表示される構成は、概して、パブリッシャー106によって決定される。例えば、パブリッシャー106は、ウェブページがユーザデバイス108に提供される度に広告が表示され得る単一の広告スロットを定義することができる。あるいは、パブリッシャー106は、広告をウェブページ上に表示するために2つ以上の広告スロットを定義することができる。
【００２８】
広告管理システム104は、利用可能な広告スロットの数、それぞれの利用可能な広告スロットのサイズ、およびそれぞれの利用可能な広告スロットの位置を定義する、パブリッシャー106に関するスロット構成データを受信する。一部の実施形態において、パブリッシャー106に関するスロット構成データは、ユーザデバイス108からのページ要求に応答してパブリッシャー106によって提供されるか、または代替的に、デバイス108でページが表示されるときにユーザデバイス108によって提供される。スロット構成データを受信すると、広告管理システム104は、広告スロットのオークションを行う。
【００２９】
広告主102は、広告主102が広告を掲載するために料金を支払うターゲットウェブページを特定するために使用され得るデータを広告管理システム104に提供することができる。例えば、広告主102は、広告管理システム104にアクセスし、ウェブページを広告のターゲットに設定するために使用され得るキーワードを入力することができる。
【００３０】
広告主102は、広告主102が広告スロットに対して支払ってもよい最高額を指定する値付けデータを広告管理システム104に送ることもできる。広告主102から受信された値付けは、広告主データストア120に記憶され、インデックス付けされてよい。ウェブページ上の広告スロットは、受信される値付けデータに基づいて広告主102に割り当てられる。
【００３１】
一部の実施形態において、広告主は、オークションの前に特定の広告スロットに入札することができる。広告管理システム104は、パブリッシャー106からスロット構成データを受信することができ、スロット構成データをパブリッシャーデータストア118に記憶し、インデックス付けすることができる。広告主102は、広告管理システム104に広告クエリを与えることによってパブリッシャーのウェブページを検索することができる。例示的な広告クエリは、キーワード、利用者層パラメータ、およびトピックパラメータを含む。
【００３２】
広告管理システム104は、パブリッシャーデータストア118にアクセスし、広告主102によって与えられた広告クエリを満足するターゲットウェブページを特定する。特定されるそれぞれのターゲットウェブページに関して、広告管理システム104は、ターゲットウェブページを特定する情報、ターゲットウェブページ上で利用可能な広告スロットの数、およびターゲットウェブページに関連するその他の情報(例えば、利用者層情報、パフォーマンス情報など)を広告主102に提供することができる。それに応じて、次に、各広告主102は値付けを提供することができ、特定のウェブページのスロットが、そのウェブページがユーザデバイス108に提供されることに応じてオークションされる。
【００３３】
図2は、広告スロットが割り当てられ得る例示的ウェブページ200の図である。例示的なウェブページ200は、3つの広告スロット202、204、および206を有し、それらの広告スロットの中に3つの広告203、205、および207が表示され得る。広告スロット202、204、および206は、例示的なウェブページ200の右側に縦に配列される。広告スロット204および206は、広告205および207がこれらの広告スロットに選択的に表示され得ることを示すために破線で表される。例えば、パブリッシャー106が、単一の広告203が広告スロット202に表示されるかどうか、または広告205および/もしくは207も広告スロット204および/もしくは206に表示されるかどうかを決定することができる。
【００３４】
広告管理システム104は、広告スロット202、204、および206のそれぞれに表示される広告203、205、および207の履歴的パフォーマンスに基づいて広告スロット202、204、および206をランク付けすることができる。広告スロット202、204、および206に表示される広告203、205、および207の履歴的パフォーマンスは、CTR、インプレッション数、コンバージョン数、または広告のその他のパフォーマンス評価尺度に基づいて測定され得る。
【００３５】
例えば、広告スロット202、204、および206に表示される広告のCTRが、ある期間にわたって監視される可能性があり、その結果、広告スロット202、204、および206のそれぞれの広告203、205、および207に関して、統計的に関連のあるインプレッション数およびクリック数が得られる。広告スロット202、204、および206のそれぞれに表示される広告203、205、および207のクリック数は、広告スロット202、204、および206のそれぞれに表示される広告203、205、および207のクリック率を決定するために、広告スロット202、204、および206に関するインプレッション数で除算されてよい。そして次に、広告スロット202、204、および206が、それらのそれぞれのクリック率に基づいて(例えば、クリック率の降順に)ランク付けされ得る。
【００３６】
広告スロットがランク付けされる場合、広告スロットは、値付けの降順の広告主102にランクの降順に割り当てられてよい。例えば、最も高くランク付けされた広告スロット(例えば、202)が、最も高い値付けが受信された広告主102に割り当てられてよい。同様に、2番目に高くランク付けされた広告スロットおよび3番目に高くランク付けされた広告スロット(例えば、204および206)が、それぞれ、2番目に高い値付けおよび3番目に高い値付けが受信された広告主102に割り当てられてよい。
【００３７】
本明細書を通じて、例示の目的で、例示的なウェブページ200において、広告スロット202が最も高くランク付けされた広告スロットであり、広告スロット204が2番目に高くランク付けされた広告スロットであり、広告スロット206が3番目に高くランク付けされた広告スロットであると仮定する。
【００３８】
広告スロットが上述のように割り当てられる場合、各広告主が広告スロットに対して支払う価格は、広告スロットに対して受信された次に高い値付けに基づいて決定され得る。一般化されたセカンドプライスオークションにおいて、最も高い値付けが受信される広告主102は、広告スロット202を割り当てられ、受信された次に高い値付けに等しい価格を支払う。例えば、広告主Aおよび広告主Bから広告スロット202に対して$3および$2のCPCの値付けがそれぞれ受信される場合、広告主Aが、広告スロット202を割り当てられ、広告がユーザによって選択される場合に広告スロットに対して$2を支払う。
【００３９】
同様に、広告スロットは、ファーストプライスオークションで上述のように割り当てられてもよい。ファーストプライスオークションにおいて、最も高い値付けが受信される広告主102は、広告スロット202を割り当てられ、広告スロット202に対するその広告主102の値付けに等しい価格を支払う。例えば、広告主Aが$3の値付けに基づいて広告スロット202を割り当てられる場合、広告主Aは、ファーストプライスオークションにおいて、広告スロット202の割当てに対して$3を支払う。
【００４０】
説明された広告スロットのオークションのそれぞれにおいて、広告スロット202は、最も高い値付けが受信された広告主102に割り当てられる。しかし、上述のように最も高い値付けをした入札者に広告スロットを割り当て続けることは、最適ではないオークション結果をもたらす可能性がある。
【００４１】
例えば、2人の入札者が、広告スロット202に対して全く異なる最大限の値付けをする場合、広告スロット202の価値は、実現されない可能性がある。広告主Aから$100の値付けが受信され、広告主Bから$1の値付けが受信された、広告主Aと広告主Bの間での単一の広告スロット202のオークションについて考える。広告スロットが、単純に、最も高い値付けが受信された広告主102に割り当てられる場合、広告スロット202は、一貫して広告主Aに割り当てられる。しかし、広告主Aが、その最大限の値付けに基づいて最高$100まで広告スロットを評価するとしても、広告主Aがセカンドプライスオークションにおいて支払う価格は$1になる。各広告主に対する広告スロット202の真の価値は、$1および$100以外の価値である可能性がある。しかし、広告スロット202に対して得られる収入は、2番目に高い値付けが$1のままである限り$1のままである。
【００４２】
時間の経過につれて、広告スロット202に対するファーストプライスオークションにより得られる収入も、広告主AおよびBに関する与えられた値付けに基づいて$1に近づくものと思われる。広告主Aの値付けが$100である場合、広告主Aは、ファーストプライスオークションにおいて広告スロット202の割当てに対して$100を支払うが、広告主Aは、広告スロット202に対する次に高い値付けを特定するために、その後のオークションで自身の値付けを継続的に下げる可能性がある。したがって、広告主Aは、広告スロット202に対する次に高い値付け$1を見つけ出し、広告スロット202の割当てを受けるために、次に高い値付けよりも増分額(例えば、1セント)だけ高い値付けをする。したがって、時間の経過につれて、ファーストプライスオークションによって得られる収入は、2番目に高い値付けよりほんの少し高いだけになる可能性があり、最も高い値付けをした入札者に対する広告スロットの価値をおそらく反映しなくなる。
【００４３】
上で示されたように、広告主102に対する広告スロットの価値の間に大きな差異が存在する場合、広告スロットに対して得られる収入は、最も高い値付けが受信された広告主に対する広告スロットの価値を反映しない可能性がある。
【００４４】
広告主102に対する広告スロットの価値をより忠実に反映する収入は、広告スロットに対する値付けの非線形関数に基づいて広告スロットを割り当てることによって得られる可能性がある。広告スロットに対する値付けの非線形関数に基づくこの広告スロット割当ては、広告スロットが広告主の値付け価格の非線形な割合に基づいて広告主に割り当てられるので、非線形割当てと呼ばれる。さらに、広告スロットに対して得られる収入は、広告主102から受信される値付けに非線形に対応する。
【００４５】
§2.1  非線形割当て
広告管理システム104のオークションサブシステム116は、各広告スロットに対して得られる収入が広告主102に対する広告スロットの価値をより忠実に反映するように、広告スロットの非線形割当てを実行する。一部の実施形態において、オークションサブシステム116は、各広告主102が広告スロットを割り当てられる確率にしたがって、広告主102に疑似ランダムに広告スロットを割り当てる。各広告主102が広告スロットを割り当てられる確率は、以下で説明されるように、広告スロットに対する値付けに適用される非線形関数に基づくことができる。広告スロットの疑似ランダムな割当てが検討されるが、(例えば、確率に関数が適用された結果に基づく)その他の割当て技術が使用されてもよい。
【００４６】
以下の広告スロットの非線形割当ての検討は、2人の広告主102が単一の広告スロットに対して入札し、広告スロットが2人の広告主102の間で割り当てられる割当てシナリオに焦点を当てる。しかし、3人以上の広告主102に対する2つ以上の広告スロットの非線形割当てが、実行され得る。
【００４７】
オークションサブシステム116は、広告スロットに対する広告主102からの値付けを表す値付けデータを受信する。値付けは、広告主102が、広告をウェブページ上の広告スロットに表示させるために支払ってもよい最高価格を指定する。
【００４８】
例えば、値付けは、例示的なウェブページ200によって満足されるキーワードを与えた2人の特定の広告主AおよびBから受信され得る。広告主AおよびBから受信された値付けは、広告主データストア120に記憶されてよい。例示的なウェブページ200の広告スロット202がオークションされているとき、オークションサブシステム116は、広告主AおよびBによって与えられた値付けを取得することができる。オークションサブシステム116によって取得された値付けは、例えば、Table 1(表1)に与えられた全く異なるCPCの値付けである可能性がある。
【００４９】
【表１】
2012516517.tif 000003
【００５０】
各広告主に対する広告スロット202の真の価値はそれらの広告主のそれぞれの値付けとは異なる可能性があるが、広告スロット202に対して各広告主102が付ける額は、広告主102に対する広告スロットの相対的価値の大きさとみなされ得る。例えば、広告主Aが、広告スロット202に対して$100のCPCを支払ってもよい一方、広告主Bは、広告スロット202に対して$1のCPCしか支払いたくない。したがって、広告主Aは、広告スロット202を、広告主Aが受けるクリックごとに$100と評価するとみなされ得る一方、広告主Bは、広告スロット202を、広告スロット202において広告主Bが受けるクリックごとに$1と評価するとみなされる。
【００５１】
広告主102から受信された値付けに基づいて、オークションサブシステム116は、各広告主102が広告スロット202を割り当てられる確率を定義する割当て確率データを生成する。各広告主102が広告スロットを割り当てられる確率は、その広告主の値付けに非線形関数が適用された結果の、その広告主の値付けに非線形関数が適用された結果とその他の広告主の値付けに非線形関数が適用された結果の合計に対する比である。一部の実施形態において、非線形関数は、指数関数(例えば、a^x、ここでaは広告主の値付けであり、xは値付けに適用される指数である)である。
【００５２】
広告主Aが広告スロットを割り当てられる確率は、式1によって表され得る。
【００５３】
【数１】
2012516517.tif 000004
【００５４】
式1
ここで、
P(A) =広告主Aが広告スロットを割り当てられる確率であり、
bA =広告主Aから受信された最大限の値付けであり、
bB =広告主Bから受信された最大限の値付けであり、
αは、[0,1]から選択される。
【００５５】
同様に、広告主Bが広告スロットを割り当てられる確率は、式2によって表され得る。
【００５６】
【数２】
2012516517.tif 000005
【００５７】
式2
ここで、
P(B) =広告主Bが広告スロットを割り当てられる確率であり、
bA =広告主Aから受信された最大限の値付けであり、
bB =広告主Bから受信された最大限の値付けであり、
αは、[0,1]から選択される。
【００５８】
上記の例について続けると、α= 1/2であるときの、式1に基づく、広告主Aが広告スロット202を割り当てられる確率は、10/11(例えば、(100^.5) / (100^.5 + 1^.5))である。同様に、α= 1/2であるときの、式2に基づく、広告主Bが広告スロットを割り当てられる確率は、1/11(例えば、(1^.5) / (100^.5 + 1^.5))である。一部の実施形態において、広告主Bが広告スロットを割り当てられる確率は、1と、広告主Aが広告スロットを割り当てられる確率との差であると決められてもよい。
【００５９】
各広告主102に対して割当て確率が決定されると、オークションサブシステム116は、確率にしたがって広告スロット202を割り当てることができる。一部の実施形態において、オークションサブシステム116は、各広告主102に対する割当て確率を疑似ランダムな割当てに対する制約として使用して、広告主102の間で疑似ランダムに広告スロット202を割り当てる。
【００６０】
上記の例について続けると、オークションサブシステム116は、広告主Aが10/11の確率で広告スロット202を割り当てられ、広告主Bが1/11の確率で広告スロット202を割り当てられるように、広告主Aまたは広告主Bのいずれかに疑似ランダムに広告スロット202を割り当てることができる。したがって、最も高い値付けが広告主Bから受信されなかったとしても、広告主Bが広告スロット202を割り当てられる1/11の可能性がある。
【００６１】
例示の目的で指数関数が検討されたが、その他の非線形関数が、各広告主102が広告スロットを割り当てられる確率を決定するために使用され得る。例えば、上述の確率の比は、式3に与えられるように任意の2人の広告主xおよびyに対して一般化され得る。
【００６２】
【数３】
2012516517.tif 000006
【００６３】
式3
ここで、
P(x) =広告主xが広告スロットを割り当てられる確率であり、
F(x) =広告主xからの値付けに適用される非線形関数であり、
F(y) =広告主yからの値付けに適用される非線形関数である。
【００６４】
広告主xおよび広告主yからの値付けに適用され得る非線形関数Fは、例えば、log関数(例えば、F(x) = log(x+1)またはF(x) = log(log(x+1)+1))であってよい。
【００６５】
一部の実施形態において、広告スロットは、3人以上の広告主102の間で割り当てられ得る。例えば、値付けが3人以上の広告主102から受信される場合、オークションサブシステム116は、それらの値付けの中から最も高い値付けおよび2番目に高い値付けを特定することができる。そして次に、オークションサブシステム116は、上述のように2人の最も高い値付けをした広告主の間で非線形割当てを実行することができる。代替的に、オークションサブシステム116は、広告主102のそれぞれが広告スロットを割り当てられる確率に基づいて3人以上の広告主102の間で広告スロットを割り当てることによって、3人以上の広告主102の間で広告スロットを割り当てることができる。オークションサブシステム116は、広告主のそれぞれが広告スロットを割り当てられる確率を、例えば、広告主の値付けに非線形関数を適用することによって決定することができる。式4は、複数の広告主の中のそれぞれの広告主が広告スロットを割り当てられる確率を決定するための例示的な一般化された式である。
【００６６】
【数４】
2012516517.tif 000007
【００６７】
式4
ここで、
P(x) =広告主xが広告スロットを割り当てられる確率であり、
F(x) =広告主xからの値付けに適用される非線形関数であり、
F(y) =広告主yからの値付けに適用される非線形関数であり、
F(z) =広告主zからの値付けに適用される非線形関数である。
【００６８】
2つ以上の広告スロットがオークションサブシステム116によって割り当てられているとき、広告スロットのそれぞれは、上述のように個別に割り当てられ得る。一部の実施形態において、広告スロットは、広告スロットのランク(例えば、履歴的パフォーマンスに基づくランク)の順序で割り当てられ得る。例えば、最も高くランク付けされた広告スロットが、2つの最も高い値付けが受信された2人の広告主のうちの1人に割り当てられてよい。次に高くランク付けされた広告スロットは、最も高くランク付けされた広告スロットを割り当てられなかった方の広告主102に割り当てられ得るか、または次の2つの最も高い値付けを有し、最も高くランク付けされた広告スロットを割り当てられなかった、広告主102の中の広告主のうちの1人に割り当てられ得る。割当てプロセスは、ページ上のすべての広告スロットが割り当てられるまで繰り返されてよい。
【００６９】
広告主の値付けに応じて広告主102に広告スロットを割り当てることは、より高い値付けを与えた広告主102が次に高い値付けの値を特定することができる見込みを小さくする。したがって、より高い値付けを与えた広告主102は、広告主102が時間が経ったときにセカンドプライスオークションに対して与える値付けよりも高い値付けを、時間が経ったときに非線形オークションに対して与え続ける見込みがより高い。したがって、非線形オークションから得られる最小の収入は、セカンドプライスオークションから得られる最小の収入よりも高くなる。非線形オークションから得られる最小の収入はセカンドプライスオークションに対する収入よりも高くなるが、非線形オークションから得られる実際の収入は、広告スロットが価格決定される方法に依存する可能性がある。
【００７０】
§2.2  全員負担オークションにおける非線形割当て
一部の実施形態において、オークションサブシステム116は、広告主102が広告スロットを割り当てられるときに限り、各広告主102がそれらの広告主102の値付け価格を支払うことを可能にすることができる。上記の例について続けると、広告主Aは、広告スロット202におけるその広告主Aの広告のクリックごとにその広告主Aの値付け$100を支払う。同様に、広告主Bは、広告スロット202においてその広告主Bの広告が受けるクリックごとに$1を支払う。広告主AおよびBは、それらの広告主のそれぞれの広告が広告スロット202に表示され、ユーザによって選択されるときにのみ支払いをする。
【００７１】
その他の実施形態において、オークションサブシステム116は、広告主102が広告スロットを割り当てられるかどうかに関わらず各広告主102が支払いをすることを要求する。広告主102が広告スロットを割り当てられるかどうかに関わらず、オークションで広告スロットを競るために各広告主102が支払いをするオークションは、全員負担オークションと呼ばれる。
【００７２】
一部の実施形態において、オークションサブシステム116は、全員負担オークションで広告スロットを競るために広告主が支払わなければならない全員負担価格を決定することができる。全員負担オークションで広告スロットを競っている各広告主は、広告主が広告スロットを割り当てられるかどうかに関わらず全員負担価格を支払わなければならない。例えば、広告スロットを割り当てられる広告主102は、広告スロットに対する自らの値付け価格を支払う可能性があり、一方、広告スロットを割り当てられなかった各広告主102は、全員負担オークションで競るために、自身の値付け、自身の値付けのほんの一部(例えば、10%)、決められた料金(例えば、$1.00)、または何らかのその他の価格を支払うことを要求される可能性がある。
【００７３】
一部の実施形態において、全員負担価格は、広告スロットに対する最低競売価格であってよい。最低競売価格は、広告スロットを提供するパブリッシャーが、広告スロットの割当てに対して許容する最小額である。例えば、パブリッシャー106は、自身のウェブページ上の広告スロットの割当てに対して$10のCPCという最低競売価格を指定することができる。したがって、$10のCPC未満の値付けをする広告主102は、広告スロットを割り当てられない。全員負担オークションにおいて、オークションで広告スロットを競りたい各広告主102は、全員負担価格を支払うことを要求される可能性がある。
【００７４】
全員負担オークションは、各広告主102が広告スロットを割り当てられるかどうかに関わらず各広告主102が自らの値付け価格を支払うように、非線形割当てと組み合わされ得る。広告主の値付けに等しい全員負担価格と組み合わされた広告スロットの非線形割当ては、各広告主102がその広告主102の値付け価格に基づいて何らかの確率で広告スロットを割り当てられるので、各広告主102にとって事前個人合理的(ex-ante individually rational)である。しかし、一部の広告主102は、たとえ広告主102が広告スロットを割り当てられないとしても支払いを要求するオークションで競りたくない可能性がある。例えば、単一の広告スロットが単一のオークションで割り当てられる場合、広告主102は、見返りとして広告スロットの割当てを受けることを保証されないまま全員負担価格を支払うことに抵抗する可能性がある。したがって、オークションサブシステム116は、広告主102が、見返りとして広告スロットの割当てを受けることなしに全員負担価格を支払うことがないことを保証するように非線形割当てを調整することができる。
【００７５】
一部の実施形態において、オークションサブシステム116は、広告主102が、広告スロットの最小回数を超えるオークションで広告スロットを割り当てられない限り支払いをしないことを保証することができる。例えば、広告スロットがk回オークションされることになっている場合、オークションサブシステム116は、広告主102が広告スロットを割り当てられる確率を1/kと比較することができる。広告主102が広告スロットを割り当てられる確率が1/k未満である場合、オークションサブシステム116は、広告主102に広告スロットを割り当てず、広告主102からの支払いを要求しない。広告主102が広告スロットを割り当てられる確率が1/k以上である場合、オークションサブシステム116は、k回のオークションのうち、その確率とkの積以下である最も大きな整数に等しい回数のオークションで広告主に広告スロットを割り当てる(すなわち、割当て≦確率×k)。
【００７６】
上記の例について続けると、広告スロット202が10回以下の回数オークションされることになっている場合(すなわち、k≦10)、広告主Bが広告スロット202を割り当てられる確率(すなわち、1/11)は、1/k(すなわち、1/10)未満である。したがって、オークションサブシステム116は、広告スロット202が広告主Bに割り当てられることを防止し、広告主Bが自身の値付け価格または何らかのその他の全員負担価格を請求されることを防止することができる。しかし、広告スロット202が11回以上オークションされることになっている場合(すなわち、k≧11)、オークションサブシステム116は、広告主Bが広告スロットを割り当てられる確率とオークションの回数の積以下の最も大きな整数(すなわち、INT(1/11×k))に等しい回数だけ広告主Bに広告スロット202を割り当てることができる。
【００７７】
一部の実施形態において、オークションサブシステム116は、k回のオークションのうちで広告主102が広告スロットを割り当てられる回数に基づいて広告主102に全員負担価格を請求することによって、上記の最小割当て結果を達成することができる。最も高い値付けが受信される広告主102は、その広告主102に対する整数回の割当てに対して自身の値付け価格を支払い、整数回の割当ては上述のように決定される。しかし、2番目に高い値付けが受信される広告主102は、その広告主102に対する整数回の割当てに対して要求される最小額を表す価格を支払うだけであり、この価格は、その広告主102の値付け価格未満であってよい。2番目に高い値付けが受信された広告主102によって支払われる価格は、例えば、式5を満足する価格zとして決定され得る。
【００７８】
【数５】
2012516517.tif 000008
【００７９】
式5
ここで、
zx =2番目に高い値付けが受信された広告主によって支払われる最小価格であり、
bx =2番目に高い値付けであり、
k =広告スロットのオークションの回数であり、
by =最も高い値付けであり、
αは、[0,1]から選択される。
【００８０】
整数回の割当てを受けるために要求される最小価格に基づく広告スロットの割当ておよび価格決定は、広告スロットを割り当てられない広告主102が全員負担価格を支払うことを防止する。さらに、このようにして広告スロットを割り当てることは、広告スロットに対して2番目に高い値付けが受信される広告主102が、その広告主102に対する整数回の割当てを受けるために要求される最小額を請求されるのみであることを保証する。
【００８１】
§2.3  条件付き非線形割当て
一部の実施形態において、広告スロットの非線形割当ては、最小の値付けの差異が満たされることを条件とする。一部の実施形態において、オークションサブシステム116は、第1の入札者からの第1の値付けが第2の入札者からの第2の値付けの4倍以上である場合にのみ非線形割当てを実行する。最小の値付けの差異が満たされない場合、オークションサブシステム116は、別のオークション割当て方法(例えば、一般化されたセカンドプライスオークションもしくはファーストプライスオークション)に基づいて広告スロットを割り当てることができるか、またはオークションサブシステム116は、最も高い値付けが受信された入札者に広告スロットを一貫して割り当てることができる。係数4は、例示の目的で与えられる。その他の最小の値付けの差異が、非線形割当ての条件として使用されてもよい。
【００８２】
§3.0  例示的なプロセスフロー
図3Aは、非線形スロット割当てのための例示的プロセス300のフローチャートである。プロセス300は、例えば、図1のオークションサブシステム116および/または広告管理システム104によって実施され得る。スロットは、例えば、パブリッシャーのウェブプロパティ上に表示される広告スロット、または印刷メディアもしくはその他の広告メディアに表示される広告スポットであってよい。プロセスは、入札者の間でその他のアイテムを割当てまたは販売するために使用されてもよい。
【００８３】
スロットに対する値付けデータが、第1の入札者および第2の入札者から受信される(302)。一部の実施形態において、値付けデータは、第1の入札者および第2の入札者のそれぞれに対するスロットの割当てに対するそれぞれの値付けを定義する。一部の実施形態において、第1の入札者および第2の入札者に関するそれぞれの値付けは、第1の入札者に関する第1の値付けおよび第2の入札者に関する第2の値付けを含む。一部の実施形態において、第1の入札者は、最も高い値付けが受信される入札者であり、第2の入札者は、2番目に高い値付けが受信される入札者である。値付けデータは、例えば、オークションサブシステム116によって受信され得る。値付けデータは、入札者から直接受信され得るか、またはデータストアから取得され得る。
【００８４】
割当て確率データが、第1の入札者および第2の入札者のそれぞれに対して生成される(304)。一部の実施形態において、割当て確率データは、第1の入札者および第2の入札者のそれぞれがスロットを割り当てられる確率を定義する。割当て確率データは、それぞれの値付けの非線形関数に基づいて決定され得る。一部の実施形態において、非線形関数は指数関数であってよい。一部の実施形態において、非線形関数は対数関数であってよい。割当て確率データは、例えば、オークションサブシステム116によって生成され得る。
【００８５】
スロットが、割当て確率データに基づいて割り当てられる(306)。一部の実施形態において、スロットは、第1の入札者と第2の入札者の間で疑似ランダムに割り当てられ、その疑似ランダムな割当ては、割当て確率データに基づいて重み付けされる。スロットは、例えば、オークションサブシステム116によって割り当てられ得る。
【００８６】
図3Bは、割当て確率データを生成するための例示的プロセス350のフローチャートである。プロセス350は、例えば、図1のオークションサブシステム116および/または広告管理システム104によって実施され得る。プロセス350は、スロットに対する値付けが受信される各広告主に対して繰り返し実行されてよい。
【００８７】
第1の入札者に関する第1の値付けの指数関数が、決定される(352)。一部の実施形態において、第1の値付けの指数関数は、第1の値付けを0から1の間の指数で累乗した結果である。第1の値付けの指数関数は、例えば、オークションサブシステム116によって決定され得る。
【００８８】
第2の入札者に関する第2の値付けの指数関数が、決定される(354)。一部の実施形態において、第2の値付けの指数関数は、第2の値付けを0から1の間の指数で累乗した結果である。一部の実施形態において、第2の値付けが累乗される指数は、第1の値付けが累乗された指数と同じである。第2の値付けの指数関数は、例えば、オークションサブシステム116によって決定され得る。
【００８９】
第1の入札者に対する割当て確率が、決定される(356)。一部の実施形態において、第1の入札者の割当て確率は、第1の値付けの指数関数の、第1の値付けの指数関数と第2の値付けの指数関数の合計に対する比に基づく。第1の入札者の割当て確率は、例えば、オークションサブシステム116によって決定され得る。
【００９０】
第2の入札者の割当て確率が、決定される(358)。一部の実施形態において、第2の入札者の割当て確率は、第1の入札者の割当て確率の補数に基づく。例えば、割当て確率は、1と、第1の入札者に対する割当て確率との差であってよい。一部の実施形態において、第2の入札者の割当て確率は、第2の値付けの指数関数の、第2の値付けの指数関数と第1の値付けの指数関数の合計に対する比に基づくことができる。第2の入札者の割当て確率は、例えば、オークションサブシステム116によって決定され得る。
【００９１】
図3Cは、全員負担オークションのための広告スロットの非線形割当てのための例示的プロセス370のフローチャートである。プロセス370は、例えば、図1のオークションサブシステム116および/または広告管理システム104によって実施され得る。プロセス370は、ウェブページ上の割り当てられるべき各広告スロットに対して繰り返し実行されてよい。
【００９２】
広告スロットの割当て回数が、特定される(372)。一部の実施形態において、割当ての回数は、広告スロットが定義されるウェブページのパブリッシャーによって指定され得る。一部の実施形態において、割当ての回数は、同じ値付けを用いて実行される、連続的にオークションされる広告スロットに関する割当ての回数(例えば、100回の割当て)であってよい。割当ての整数で表される回数は、例えば、オークションサブシステム116によって特定され得る。
【００９３】
第1の入札者および第2の入札者のそれぞれに対する割当て確率データが、生成される(374)。一部の実施形態において、割当て確率データは、第1の入札者および第2の入札者のそれぞれがスロットを割り当てられる確率を定義する。割当て確率データは、それぞれの値付けの非線形関数に基づいて決定され得る。一部の実施形態において、非線形関数は指数関数であってよい。一部の実施形態において、非線形関数は対数関数であってよい。割当て確率データは、例えば、オークションサブシステム116によって生成され得る。
【００９４】
第1の入札者および第2の入札者のそれぞれに対する割当て確率データが、割当て回数の逆数と比較される(376)。割当て確率データは、例えば、オークションサブシステム116によって割当て回数の逆数と比較され得る。
【００９５】
割当て確率データが割当て回数の逆数を満足する各入札者が、全員負担価格を請求される(378)。全員負担価格は、例えば、オークションを実施する度にオークションサブシステム116によって請求され得る。
【００９６】
広告スロットが、割当て確率データに基づいて、全員負担価格を支払った各入札者に割り当てられる(380)。一部の実施形態において、全員負担価格を支払った各入札者は、割当て回数のうち、割当て回数と入札者に対する割当て確率データの積未満の最も大きな整数に等しい回数だけ割当てを受ける。広告スロットは、例えば、オークションサブシステム116によって割り当てられ得る。
【００９７】
§4.0  例示的なコンピュータシステム
図4は、広告スロットの非線形割当てを容易にするために使用され得る例示的なコンピュータシステム400の構成図である。システム400は、プロセッサ410、メモリ420、記憶装置430、および入力/出力デバイス440を含む。コンポーネント410、420、430、および440のそれぞれは、例えば、システムバス450を用いて相互接続され得る。プロセッサ410は、システム400内で実行するための命令を処理することができる。1つの実施形態において、プロセッサ410は、シングルスレッドプロセッサである。別の実施形態において、プロセッサ410は、マルチスレッドプロセッサである。プロセッサ410は、メモリ420または記憶装置430に記憶された命令を処理することができる。
【００９８】
メモリ420は、システム400内で情報を記憶する。1つの実施形態において、メモリ420は、コンピュータ可読媒体である。1つの実施形態において、メモリ420は、揮発性メモリユニットである。別の実施形態において、メモリ420は、不揮発性メモリユニットである。
【００９９】
記憶装置430は、システム400に大容量ストレージを提供することができる。1つの実施形態において、記憶装置430は、コンピュータ可読媒体である。さまざまな異なる実施形態において、記憶装置430は、例えば、ハードディスクデバイス、光ディスクデバイス、または何らかのその他の大容量記憶装置を含み得る。
【０１００】
入力/出力デバイス440は、システム400に入力/出力操作を与える。1つの実施形態において、入力/出力デバイス440は、ネットワークインターフェースデバイス、例えばイーサネットカード、シリアル通信デバイス、例えばRS-232ポート、および/または無線インターフェースデバイス、例えば802.11カードのうちの1つまたは複数を含み得る。別の実施形態において、入力/出力デバイスは、入力データを受信し、その他の入力/出力デバイス、例えば、キーボード、プリンター、およびディスプレイデバイス460に出力データを送信するように構成されたドライバデバイスを含み得る。
【０１０１】
オークションサブシステム116および/または広告管理システム104は、実行されると1つまたは複数の処理デバイスに上述のプロセスおよび機能を実行させる命令によって実現され得る。そのような命令は、例えば、スクリプト命令、例えば、JavaScript（登録商標）命令もしくはECMAScript命令などの解釈される命令、または実行可能コード、またはコンピュータ可読媒体に記憶されたその他の命令を含み得る。オークションサブシステム116および/または広告管理システム104は、サーバファームなどのネットワーク上に分散して実施され得るか、または単一のコンピュータデバイスで実施され得る。
【０１０２】
例示的な処理システムが図4に示されたが、本明細書に記載の対象の実施形態および機能的動作は、本明細書で開示された構造およびそれらの構造的均等物を含む、その他の種類のデジタル電子回路、またはコンピュータソフトウェア、ファームウェア、もしくはハードウェア、またはそれらのうちの1つもしくは複数の組合せで実施され得る。本明細書に記載の対象の実施形態は、1つまたは複数のコンピュータプログラム製品、すなわち、処理システムによる実行のために、または処理システムの動作を制御するために有形のプログラム媒体上に符号化されたコンピュータプログラム命令の1つまたは複数のモジュールとして実装され得る。コンピュータ可読媒体は、機械可読記憶装置、機械可読記憶基板、メモリデバイス、機械可読伝播信号を生じる組成物、またはそれらのうちの1つもしくは複数の組合せである可能性がある。
【０１０３】
用語「処理システム」、「処理デバイス」、および「サブシステム」は、例として、1つのプログラム可能なプロセッサ、1台のコンピュータ、または複数のプロセッサもしくはコンピュータを含む、データを処理するためのすべての装置、デバイス、およびマシンを包含する。処理システムは、ハードウェアに加えて、問題にしているコンピュータプログラムのための実行環境を生成するコード、例えば、プロセッサのファームウェア、プロトコルスタック、データベース管理システム、オペレーティングシステム、またはそれらのうちの1つもしくは複数の組合せを構成するコードを含み得る。
【０１０４】
コンピュータプログラム(プログラム、ソフトウェア、ソフトウェアアプリケーション、スクリプト、またはコードとしても知られる)は、コンパイラ型言語もしくはインタープリタ型言語、または宣言型言語もしくは手続き型言語を含む任意の形態のプログラミング言語で記述可能であり、独立型プログラムとしての形態、またはモジュール、コンポーネント、サブルーチン、もしくはコンピューティング環境での使用に適したその他の単位としての形態を含む、任意の形態で配置され得る。コンピュータプログラムは、必ずしもファイルシステム内のファイルに対応しない。プログラムは、その他のプログラムもしくはデータを保持するファイルの一部(例えば、マークアップ言語のドキュメントに記憶された1つもしくは複数のスクリプト)、問題にしているプログラムに専用の単一のファイル、または複数の組織されたファイル(例えば、1つもしくは複数のモジュール、サブプログラム、もしくはコードの一部を記憶するファイル)に記憶され得る。コンピュータプログラムは、1つのコンピュータ上で、または1つの場所に置かれるか、もしくは複数の場所にわたって分散され、通信ネットワークによって相互接続されている複数のコンピュータ上で実行されるように配置され得る。
【０１０５】
コンピュータプログラム命令およびデータを記憶するのに適したコンピュータ可読媒体は、例として、半導体メモリデバイス、例えば、EPROM、EEPROM、およびフラッシュメモリデバイス、磁気ディスク、例えば、内蔵ハードディスクまたはリムーバブルディスク、光磁気ディスク、ならびにCD ROMディスクおよびDVD ROMディスクを含む、すべての形態の不揮発性メモリ、メディア、およびメモリデバイスを含む。プロセッサおよびメモリは、専用の論理回路によって補完されるか、または専用の論理回路に組み込まれる可能性がある。
【０１０６】
本明細書に記載の対象の実施形態および機能的動作は、本明細書で開示された構造およびそれらの構造的均等物を含む、デジタル電子回路、またはコンピュータソフトウェア、ファームウェア、もしくはハードウェア、またはそれらのうちの1つもしくは複数の組合せで実施され得る。本明細書に記載の対象の実施形態は、1つまたは複数のコンピュータプログラム製品、すなわち、データ処理装置による実行のために、またはデータ処理装置の動作を制御するために有形のプログラム媒体上に符号化されたコンピュータプログラム命令の1つまたは複数のモジュールとして実装され得る。
【０１０７】
本明細書に記載の対象の実施形態は、バックエンドコンポーネントを、例えば、データサーバとして含むか、またはミドルウェアコンポーネント、例えば、アプリケーションサーバを含むか、またはフロントエンドコンポーネント、例えば、それによってユーザが本明細書に記載の対象の実施形態とインタラクションすることができるグラフィカルユーザインターフェースもしくはウェブブラウザを有するクライアントコンピュータを含むか、または1つもしくは複数のそのようなバックエンドコンポーネント、ミドルウェアコンポーネント、もしくはフロントエンドコンポーネントの任意の組合せを含むコンピューティングシステムで実装され得る。システムのコンポーネントは、任意の形態または媒体のデジタルデータ通信、例えば、通信ネットワークによって相互接続され得る。
【０１０８】
本明細書は多くの具体的な実施形態の詳細を含むが、これらは、いかなる発明の範囲、または特許請求され得るものの範囲に対する限定ともみなされるべきではなく、むしろ、特定の発明の特定の実施形態に特有である可能性がある特徴の説明とみなされるべきである。別個の実施形態の文脈で本明細書に記載されているある特徴が、単一の実施形態で組み合わせて実施されてもよい。反対に、単一の実施形態の文脈で説明されているさまざまな特徴が、複数の実施形態に別々に、または任意の適切な部分的組合せで実施されてもよい。さらに、特徴は、ある組合せで機能するように上で説明されている可能性があり、最初にそのように主張されてさえいる可能性があるが、主張された組合せの1つまたは複数の特徴は、場合によってはその組合せから削除されてよく、主張された組合せは、部分的組合せ、または部分的組合せの変形を対象とする可能性がある。
【０１０９】
同様に、オペレーションが図中に特定の順序で示されているが、これは、そのようなオペレーションが、示された特定の順序で、もしくは逐次的順序で実行されること、または所望の結果を達成するために、示されたすべてのオペレーションが実行されることを必要とすると理解されるべきでない。ある状況において、マルチタスクおよび並列処理が、有利である可能性がある。さらに、上述の実施形態におけるさまざまなシステムコンポーネントの分割は、すべての実施形態においてそのような分割を必要とすると理解されるべきでなく、説明されたプログラムコンポーネントおよびシステムは、概して、単一のソフトウェア製品に一緒に統合されるか、または複数のソフトウェア製品にパッケージングされる可能性があることを理解されたい。
【０１１０】
本明細書に記載の対象の特定の実施形態が、説明された。その他の実施形態は、添付の特許請求の範囲の範囲内にある。例えば、特許請求の範囲に挙げられた動作は、異なる順序で実行されてよく、それでも所望の結果を達成することができる。一例として、添付の図面に示されたプロセスは、所望の結果を達成するために、必ずしも、示された特定の順序、または逐次的順序である必要はない。ある実施形態において、マルチタスクおよび並列処理が、有利である可能性がある。広告を配信することについて言及されているが、その他の形態のスポンサーの付いたコンテンツを含むその他の形態のコンテンツが配信され得る。
【０１１１】
本明細書は、本発明の最良の形態を示し、本発明を説明し、当業者が本発明を作製および使用することを可能にする例を提供する。本明細書は、本発明を、記載された表現に厳密に限定しない。したがって、本発明が上述の例を参照して詳細に説明されたが、当業者は、本発明の範囲を逸脱することなく、それらの例に改変、修正、および変更を行うことができる。
【符号の説明】
【０１１２】
100  オンライン環境
101  コンピュータネットワーク
102  広告主
104  広告管理システム
106  パブリッシャー
108  ユーザデバイス
110  検索エンジン
112  ページコンテンツ要求
114  ページコンテンツ
116  オークションサブシステム
118  パブリッシャーデータストア
120  広告主データストア
400  コンピュータシステム
410  プロセッサ
420  メモリ
430  記憶装置
440  入力/出力デバイス
450  システムバス
460  ディスプレイデバイス
【図１】
2012516517.tif 000009
【図２】
2012516517.tif 000010
【図３Ａ】
2012516517.tif 000011
【図３Ｂ】
2012516517.tif 000012
【図３Ｃ】
2012516517.tif 000013
【図４】
2012516517.tif 000014
【国際調査報告】
2012516517.tif 000015
2012516517.tif 000016