実用的なケーキカット

功利主義的ケーキカット（最大和ケーキカットとも呼ばれる）は、ケーキや土地などの異質なリソースを、異なる基数効用関数を持つ複数のパートナー間で、パートナーの効用の合計が最大になるように分割するルールです。これは、功利主義的社会的選択ルールの特殊なケースです。功利主義的ケーキカットは「公平」ではないことがよくあります。そのため、功利主義は公平なケーキカットとしばしば矛盾します。

チョコレートとバニラの 2 つの部分と、アリスとジョージという 2 人のパートナーからなるケーキを考えてみましょう。その評価は次のようになります。

功利主義のルールでは、それぞれのパーツは最も効用の高いパートナーに与えられます。この場合、功利主義のルールでは、チョコレート全体がアリスに与えられ、バニラ全体がジョージに与えられます。最大値は 13 です。

功利主義的な分割は公平ではありません。ジョージが受け取るのはケーキの合計額の半分未満なので比例的ではなく、ジョージがアリスを羨んでいるので羨望の的となります。

このケーキは と呼ばれます。これは通常、有限の 1 次元セグメント、2 次元の多角形、または多次元ユークリッド平面の有限のサブセットのいずれかであると想定されます。 ${\displaystyle C}$${\displaystyle \mathbb {R} ^{d}}$

パートナーがいます。各パートナーには、サブセット（「ピース」）を数字に マッピングする個人の価値関数があります。${\displaystyle n}$${\displaystyle i}$${\displaystyle V_{i}}$${\displaystyle C}$

${\displaystyle C}$は、パートナーごとに 1 つのピースずつ、互いに素なピースに分割する必要があります。パートナーに割り当てられたピースは、 と呼ばれます。 ${\displaystyle n}$${\displaystyle i}$${\displaystyle X_{i}}$${\displaystyle C=X_{1}\sqcup ...\sqcup X_{n}}$

次の式を最大化する 分割は、功利主義的、功利主義最大、または最大和と呼ばれます。${\displaystyle X}$

${\displaystyle \sum _{i=1}^{n}{V_{i}(X_{i})}}$

この概念は、各パートナーに異なる重みを割り当てることによって一般化されることがよくあります。次の式を最大化する 分割は、加重効用最大(WUM)と呼ばれます。${\displaystyle X}$

${\displaystyle \sum _{i=1}^{n}{\frac {V_{i}(X_{i})}{w_{i}}}}$

ここで、 には正の定数が与えられます。 ${\displaystyle w_{i}}$

正の重みを持つすべての WUM 分割は、明らかにパレート効率的です。これは、分割が分割をパレート優位にする場合、 における重み付き効用合計がにおけるよりも確実に大きくなるため、WUM 分割にはならないためです。 ${\displaystyle Y}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle X}$

さらに驚くべきことは、ある重みの選択に対して、すべてのパレート効率的な分割がWUMであるということです。 ^[1]

クリストファー・P・チェンバースはWUM規則の特徴づけを提案している。 ^[2]この特徴づけは除算規則Rの以下の性質に基づいている。

• パレート効率 (PE) : ルールR は、パレート効率の高い分割のみを返します。
• 分割の独立性 (DI) : ケーキが複数のサブケーキに分割され、各ケーキがルールRに従って分割されると、結果は元のケーキがRに従って分割された場合と同じになります。
• 実行不可能な土地の独立性 (IIL) : サブケーキがRに従って分割される場合、その結果は他のサブケーキのパートナーの効用に依存しません。
• 同等の肯定的扱い (PTE) : すべてのパートナーが同じ効用関数を持つ場合、R は各パートナーに正の効用を与える少なくとも 1 つの部門を推奨します。
• スケール不変性 (SI) : パートナーの効用関数に定数 (パートナーごとに異なる定数の可能性あり) を掛けても、Rによって提供される推奨事項は変わりません。
• 連続性 (CO) : 固定されたケーキの場合、特定の割り当てにマップされる効用プロファイルの集合は、点ごとの収束の下で閉じた集合です。

正のサイズを持つすべてのケーキに正の効用を割り当てるパートナーについては、次のことが証明されています。

• R がPE DI および IIL である場合、Rによって推奨されるすべての部門がこれらの重みを持つ WUM であるような重みのシーケンスが存在します (すべての PE 部門が何らかの重みを持つ WUM であることはわかっています。つまり、 Rによって推奨されるすべての部門が同じ重みを持つ WUM であるということです。これは DI プロパティから得られます)。${\displaystyle w_{1},\dots ,w_{n}}$
• R がPE DI IIL かつ PTE である場合、Rによって推奨されるすべての分割は功利主義最大です (言い換えると、すべての分割は WUM でなければならず、すべてのエージェントは等しい重みを持つ必要があります。これは PTE プロパティに従います)。
• Rが PE DI IIL かつ SI である場合、R は独裁的なルールであり、ケーキ全体を 1 人のパートナーに渡します。
• R がPE DI IIL および CO である場合、R がこれらの重みを持つ WUM ルールとなるような重みのシーケンスが存在します (つまり、 R はこれらの重みを持つすべての WUM 部門のみを推奨します)。${\displaystyle w_{1},\dots ,w_{n}}$

価値関数が加法的な場合、最大和の分割は常に存在します。直感的には、上記の例のように、ケーキの各部分を最も価値の高いパートナーに与えることができます。同様に、WUM 分割は、ケーキの各部分を比率が最大のパートナーに与えることによって見つけることができます。 ${\displaystyle V_{i}/w_{i}}$

このプロセスは、ケーキが部分的に均質である場合、つまり、ケーキを有限個のピース​​に分割して、各ピースの値密度がすべてのパートナーに対して一定である場合には 簡単に実行できます。

ケーキが部分的に均質でない場合は、考慮すべき異なる「ピース」が無限に存在するため、上記のアルゴリズムは機能しません。

最大和分割はまだ存在します。これはデュビンス-スパニエのコンパクト性定理の系であり、ラドン-ニコディム集合を使用して証明することもできます。

しかし、有限アルゴリズムでは最大和の除算を見つけることはできません。証明: ^{[3] [4] : 反証2}有限アルゴリズムは、有限個のピース​​についてのみ価値データを持ちます。つまり、アルゴリズムがパートナーの評価を知っているケーキのサブセットは有限個しかありません。サブセットについての価値データを取得した後、アルゴリズムが停止したとします。ここで、すべてのパートナーが、同じ価値尺度を持っているかのようにすべてのクエリに回答した可能性があります。この場合、アルゴリズムが達成できる最大の功利的価値は 1 です。ただし、ピースの 1 つの奥深くに、2 人のパートナーが異なる価値を持つサブセットがある可能性があります。この場合、各パートナーが を超える値を受け取る超比例除算が存在するため、効用の合計は必ず 1 を超えます。したがって、有限アルゴリズムによって返される除算は最大和ではありません。 ${\displaystyle k}$${\displaystyle k}$${\displaystyle 1/n}$

ケーキが 1 次元でピースをつなげる必要がある場合、各ピースを最も価値の高いエージェントに割り当てるという単純なアルゴリズムは、区分的に一定の評価であっても機能しなくなります。この場合、UM 分割を見つける問題はNP 困難であり、さらにP=NP でない限りFPTASは不可能です。

8因子近似アルゴリズムと、プレイヤー数に対して指数関数的に変化する固定パラメータの扱いやすいアルゴリズムがある。 ^[5]

正の重みのすべてのセットに対して、WUM 分割が存在し、同様の方法で見つけることができます。

最大和の分割は常に公平であるとは限りません。上記の例を参照してください。同様に、公平な分割は常に最大和であるとは限りません。

この対立を解決する 1 つの方法は、「公平性の価格」を制限することです。つまり、公平性に必要な効用の合計の減少量の上限と下限を計算します。詳細については、「公平性の価格」を参照してください。

効率性と公平性を組み合わせるもう 1 つのアプローチは、すべての可能な公平な分割の中で、効用の合計が最も高い公平な分割を見つけることです。

以下のアルゴリズムは、各人が切断されたピースを受け取る可能性があり、価値関数が加算的である場合、1次元の区間であるケーキに対して、効用の合計が最大となる嫉妬のないケーキカットを見つけるために使用できます。^[6]

1. 区分的に一定の評価を持つパートナーの場合: ケーキをm 個の完全に一定の領域に分割します。nm個の変数を持つ線形計画法を解きます。各 (エージェント、領域) ペアには、エージェントに与えられる領域の割合を決定する変数があります。各領域には、この領域からのすべての割合の合計が 1 であるという制約があります。各 (エージェント、エージェント) ペアには、最初のエージェントが 2 番目のエージェントを羨ましがらないという制約があります。この手順によって生成される割り当ては、非常に細分化される可能性があることに注意してください。${\displaystyle n}$
2. 区分線形評価を持つパートナーの場合、ケーキの各ポイントについて、効用間の比率を計算します。パートナー 1 に のポイントを与え、パートナー 2 に のポイントを与えます。ここで、は分割が嫉妬のない状態になるように計算されたしきい値です。 は一般に無理数になる可能性があるため計算できませんが、実際には、評価が区分線形である場合は、「無理数検索」近似アルゴリズムによって近似できます。 の任意の について、アルゴリズムは-EF (各エージェントの価値は少なくとも他の各エージェントの価値から を引いた値である) である割り当てを見つけ、合計が少なくとも EF 割り当ての最大合計である合計を達成します。その実行時間は入力 の多項式であり、 では多項式です。${\displaystyle 2}$${\displaystyle r=u_{1}/u_{2}}$${\displaystyle r\geq r^{*}}$${\displaystyle r<r^{*}}$${\displaystyle r^{*}}$${\displaystyle r^{*}}$${\displaystyle r^{*}}$${\displaystyle \epsilon >0}$${\displaystyle \epsilon }$ ${\displaystyle \epsilon }$${\displaystyle \log(1/\epsilon )}$
3. 一般的な評価を持つパートナーの場合: 区分的定数評価アルゴリズムに基づいて、羨望と効率への加法近似。${\displaystyle n}$

Brams、Feldman、Lai、Morgenstern、Procaccia ^[7]は、嫉妬のない（EF）ケーキ分割と公平な（EQ）ケーキ分割の両方を研究し、それらを最大和とパレート最適性（PO）に関連付けています。上で説明したように、最大​​和の割り当ては常にPOです。ただし、最大和が公平性によって制約されている場合、これは必ずしも真実ではありません。彼らは次のことを証明しています。

• エージェントが 2 つある場合、maxsum-EF、maximum-EQ、maximum-EF-EQ の割り当ては常に PO になります。
• 区分的に均一な評価を持つエージェントが 3 人以上いる場合、maxsum-EF 割り当ては常に PO になります (EF は比例性と同等であり、パレート改善によって維持されるため)。ただし、 PO となる maxsum-EQ 割り当てと maxsum-EQ-EF 割り当てが存在しない場合があります。
• 区分的に一定の評価を持つエージェントが 3 人以上いる場合、PO である maxsum-EF 割り当てが存在しないこともあります。たとえば、3 つの領域と値を持つ 3 つのエージェントを含むケーキを考えてみましょう。

最大和ルールは、エージェント i に領域 i を与えますが、カールがアリスを羨んでいるため、これは EF ではありません。線形プログラムを使用すると、一意の maxsum-EF 割り当てを見つけることができ、アリスとボブの間で領域 1 と領域 2 の両方を共有する必要があることを示すことができます。ただし、アリスとボブはこれらの領域の共有を交換することで両方が利益を得ることができるため、このような割り当ては PO にはなりません。

• すべてのエージェントが区分線形評価を持つ場合、maxsum-EF 割り当ての効用合計は、maxsum-EQ 割り当てと少なくとも同じ大きさになります。この結果は、加法近似までの一般的な評価に拡張されます (つまり、ε -EF 割り当ての効用合計は、少なくとも EQ 割り当て − εになります)。

ピースが切断されている場合、絶対功利主義ルール（正規化されていない効用の合計を最大化する）は、資源単調かつ人口単調です。相対功利主義ルール（正規化された効用の合計を最大化する）は、人口単調ですが、資源単調ではありません。^[8]

ピースが接続されると、このことは当てはまらなくなります。^[9]

• 効率的なケーキカット
• フェアのケーキカット
• ウェラーの定理
• パレート効率的な嫉妬のない分割
• ランク最大割り当て
• 功利主義投票- 異なる文脈における功利主義の原則。