デマンドオラクル

アルゴリズムゲーム理論（コンピュータ科学と経済学の両方の分野）において、需要オラクルとは、価格ベクトルが与えられた場合に、エージェントの需要を返す関数です。これは、オンライン市場における価格設定や最適化に関連する多くのアルゴリズムで使用されています。通常、需要オラクルは、アイテムの集合が与えられた場合に、エージェントがそれらのアイテムに割り当てた価値を返す関数である価値オラクルと対比されます。

エージェントの需要とは、ある一定の価格が与えられた場合に、エージェントが最も好む商品の組み合わせのことである。例として、3つの商品と1人のエージェントが存在する市場を考えてみよう。それぞれの商品の価値と価格は以下のとおりである。

エージェントの効用関数が加法的（＝バンドルの価値はバンドルに含まれるアイテムの価値の合計）かつ準線形（＝バンドルの効用はバンドルの価値から価格を引いたもの）であると仮定します。すると、価格が与えられた場合、エージェントの需要は{バナナ、チェリー}の集合となり、効用は(4+6)-(3+1)=6となります。他のすべての集合は、エージェントにそれよりも小さな効用を与えます。たとえば、空の集合は効用0を与え、すべてのアイテムの集合は効用(2+4+6)-(5+3+1)=3を与えます。

加法的な評価であれば、需要関数は簡単に計算でき、「オラクル」は必要ありません。しかし、一般に、エージェントは組み合わせ的な評価を行う場合があります。これは、アイテムの組み合わせごとに異なる値を持つ可能性があり、その値は必ずしも個々のアイテムの値の合計ではないことを意味します。m 個のアイテムについてこのような関数を記述するには、最大2 ^{m 個の}数値（各サブセットに対応する数値）が必要になる場合があります。m が大きい場合、これは非現実的になる可能性があります。そのため、多くの市場アルゴリズムでは、2 種類のオラクルを使用します。

• 値オラクルは値クエリに応答できます。つまり、バンドルが与えられると、その値を返します。
• 需要オラクルは需要に関するクエリに答えることができます。価格ベクトルが与えられると、準線形効用（価値から価格を引いた値）を最大化するバンドルを返します。

需要オラクルを利用したアルゴリズムの例をいくつか挙げます。

• 福祉最大化: n個のエージェントとm個のアイテムがあります。各エージェントは、価値オラクルと需要オラクルで表されます。アイテムをエージェント間で割り当てて、価値の合計を最大化する必要があります。一般にこの問題は NP 困難ですが、劣モジュラ評価などの特殊なケースについては近似が知られています(これは「劣モジュラ福祉問題」と呼ばれます)。一部のアルゴリズムは価値オラクルのみを使用します。^{[ 1 ]}他のアルゴリズムは需要オラクルも使用します。^{[ 2 ] [ 3 ]}
• 嫉妬のない価格設定： n個のエージェントとm個のアイテムが存在する。各エージェントは、価値オラクルと需要オラクルによって表される。エージェントが嫉妬しないような価格ベクトルとアイテムの配分を見つけ、その制約の下で販売者の収益を最大化する必要がある。
• 市場均衡の計算。^{[ 4 ]}
• 強力な代替品の需要を学習する。^{[ 5 ]}

• オラクルマシン
• 需要曲線
• ロバートソン・ウェッブ・クエリモデル- ケーキカットの分野における同様のクエリモデル。