ロバートソン・ウェッブクエリモデル

コンピュータサイエンスにおいて、ロバートソン・ウェッブ（RW）クエリモデルは、公平なケーキの切り分け問題に対するアルゴリズムで使用される計算モデルです。この問題では、「ケーキ」と呼ばれるリソースと、ケーキに対する異なる価値尺度を持つ複数のエージェントが存在します。目標は、各エージェントが自身の価値尺度に基づいて自分のピースを「公平」とみなすように、ケーキをエージェント間で分割することです。エージェントの評価は非常に複雑になる可能性があるため、一般に、公平分割アルゴリズムへの入力として与えることはできません。RWモデルは、公平分割アルゴリズムがエージェントに尋ねる可能性のある2種類のクエリ、 EvalとCutを規定しています。非公式には、Evalクエリはエージェントに特定のケーキピースに対する自身の価値を指定するように求め、Cutクエリ（Markクエリとも呼ばれる）はエージェントに特定の価値を持つケーキピースを指定するように求めます。

このモデルは単純であるにもかかわらず、多くの古典的なケーキ分割アルゴリズムは、この2つのクエリだけで記述できる。一方で、RWモデルでは有限個のクエリでは解決できないことが証明されている公平なケーキ分割問題も存在する。

Eval クエリと Cut クエリは、 Jack M. RobertsonとWilliam A. Webbの著書で初めて説明されました。^{[ 1 ]}「Robertson–Webb モデル」という名称は、Woeginger と Sgall によって考案され、形式化されました。^{[ 2 ]}

標準的なRWモデルでは、ケーキは区間、通常は区間[0,1]であると仮定します。エージェントはn個あり、各エージェントiはケーキ上の値尺度v _iを持っています。アルゴリズムはv _iを知りませんが、2種類のクエリを使用してv iにアクセスできます。

• evalクエリ：2つの実数xとyが与えられた場合、Eval _i ( x , y )はエージェントiに区間[ x , y ]の値、つまりv _i ([ x , y ])を報告するように要求します。
• マーククエリ（カットクエリとも呼ばれる）：2 つの実数xとr が与えられたとき、マーク_i ( x , r )はエー​​ジェントiに、 v _i ([ x , y ]) = rとなるような値yを報告するように要求します。

2人の子供の間でケーキを切り分けるための古典的な分割選択アルゴリズムは、4つのクエリを使用して実行できます。

• アリスにEval(0,1)クエリを尋ねてください。V 1を答えとします（_これはアリスが考えるケーキ全体の価値です）。
• アリスにMark(0, V ₁ / 2)クエリを尋ねます。x 1を答えとします（_これはアリスの目から見て2つのピースが等しいというマークです）。
• GeorgeにEval(0, x ₁ )とEval( x ₁ , 1)のクエリを尋ねてください。
• 前者の値が大きい場合は、ジョージに(0, x _{1 )を、アリスに(} x ₁ ,1)を与えます。そうでない場合は、アリスに(0, x _{1 )を、ジョージに(} x ₁ ,1)を与えます。

分割選択アルゴリズム以外にも、多くのケーキカットアルゴリズムは、n（エージェント数）の多項式となる数のRWクエリを使用して実行できます。例えば、ラストディミニッシャーはO( n² ⁾のRWクエリで、イーブンパズプロトコルはO( n log n )のRWクエリで実行できます。同時に、特定の公平な分割問題を完了するには多くのRWクエリが必要であることを証明する多くの困難性結果があります。そのような困難性結果のいくつかを以下に示します。

比例的なケーキカットには、以下のいずれかの場合にΩ( n log n )回のRWクエリ

• 部品は接続されていなければならない、^{[ 2 ]}または
• プロトコルは決定論的である^{[ 3 ]}または
• ケーキを切る精度には限界がある。^{[ 3 ]}
• O( n ) RW クエリを使用する唯一のプロトコルはランダム化プロトコルであり、これは断片的なデータを返す可能性があり、割り当ては部分的な比例にしかならない可能性があります。

異なる権利を持つ比例的なケーキカットには、少なくともΩ( n log( D ))回のRWクエリが必要です。ここでDは権利の共通分母です（特に、権利が無理数の場合は、限定された数のクエリを使用して見つけることはできません）。合理的な権利に対してはO( n log( D ))回のRWクエリを使用するアルゴリズムがあり、無理数に対する有限アルゴリズムがあります。 ^{[ 4 ]}

嫉妬のないケーキカットには

• Ω( n ² ) RW は、ピースが切断される可能性があるときにクエリを実行します。^{[ 5 ]}
• ピースを接続する必要があり、エージェントが少なくとも 3 つある場合、クエリは無限に多くなります。 ^{[ 6 ]}つまり、有限個の RW クエリを使用して、3 つ以上のエージェント間で常に羨望のない割り当てを見つけるアルゴリズムはありません。
• 任意の ε > 0 に対して、ε-envy のない連結ケーキカットには、少なくとも Ω(log ε ⁻¹ ) 回のクエリが必要です。^{[ 7 ]} 3 つのエージェントの場合、O(log ε ⁻¹ ) プロトコルが存在します。4 つのエージェントの場合、O(poly(log ε ⁻¹ )) プロトコルが存在します。^{[ 8 ]} 5 人以上のエージェントの場合、最もよく知られているプロトコルは O( n ε ⁻¹ ) を必要とし、クエリの複雑さに指数関数的なギャップがあることがわかります。

2人のエージェントの場合でも、有限個のRWクエリを使用して公平なケーキカットを行うことはできません。 ^{[ 9 ]}さらに、任意のε > 0に対して：

• 連結ε-公平なケーキカットには、少なくともΩ(log ε ⁻¹ )回のクエリが必要です。^{[ 7 ]} 2エージェントの場合、O(log ε ⁻¹ )プロトコルが存在します。^{[ 10 ]} 3エージェント以上の場合、最もよく知られているプロトコルではO( n (log n + log ε ⁻¹ ))回のクエリが必要です。^{[ 11 ]}
• 接続性がなくても、ε-公平なケーキカットには少なくともΩ(log ε ⁻¹ / log log ε ⁻¹ )回のRWクエリが必要です。^{[ 9 ]}

正確なケーキカット（完全ケーキカットとも呼ばれる）は、2 エージェントの場合でも、有限個の RW クエリを使用して行うことはできません。さらに、任意の ε > 0 に対して、次のようになります。

• 最小カット数でε-完全なケーキカットを行うには、少なくともΩ(log ε ⁻¹ )回のクエリが必要です。2エージェントの場合、O(log ε ⁻¹ )プロトコルが存在します。^{[ 7 ]} 3エージェント以上の場合、既知の最良のプロトコルではO( n ³ ε ⁻¹ )回のクエリが必要です。^{[ 12 ]}

最大最小シェアのケーキカットでは、ピースを正の距離で分離する必要があるため、有限個のRWクエリを使用して実行することはできません。さらに、単一のエージェントであっても、有限個のRWクエリを使用してエージェントの最大最小シェアを計算するアルゴリズムはありません。ただし、 ^{[ 13 ]}

• 任意の ε > 0 に対して、O( n log ε ⁻¹ ) 回の RW クエリを使用して、MMS と MMS-ε の間の値を計算することが可能です。
• ケーキが円形の場合（つまり、公平なパイカットの場合）、O( nε - ¹ )回のRWクエリを使用してMMSとMMS-εの間の値を計算することが可能です。O( nlogε - ¹ )回のRWクエリで十分かどうかは未解決です。

平均比例配分（つまり、 n家族間での配分で、各家族の平均値が合計の少なくとも 1/ nとなるような配分）は、各家族に 2 人のメンバーがいる 2 つの家族がある場合でも、有限個の RW クエリを使用して計算することはできません。証明は、公平配分からの還元によって行われます。^{[ 14 ]}

RWモデルを使用しないケーキカットアルゴリズムは数多く存在する。それらは通常、以下のいずれかのモデルを使用する。

• 需要オラクル（および価値オラクル） - 分割不可能なオブジェクトが存在する環境における、同様のクエリモデル。