同時摂食アルゴリズム

同時摂食アルゴリズム（SE）は、順序嗜好を持つエージェント間で分割可能なオブジェクトを割り当てるアルゴリズムである。^{[ 1 ]}

「順序選好」とは、各エージェントがアイテムを最良から最悪まで順位付けできるものの、各アイテムに数値を与えることができない（または与えたくない）ことを意味します。SE配分はSD効率性を満たします。SD効率性とは、パレート効率性の弱い順序版です（つまり、エージェントのアイテム順位付けと整合する加法効用関数の少なくとも1つのベクトルに対して、配分がパレート効率的であることを意味します）。

SE は、各エージェントの「摂食速度」によってパラメータ化されます。すべてのエージェントに同じ摂食速度が与えられると、SE の割り当ては SD 羨望フリー性を満たします。これは、羨望フリー性の強い順序的変種です(割り当てが、エージェントのアイテムランキングと一致するすべての加法効用関数のベクトルに対して羨望フリーであることを意味します)。この特定の SE 変種は、確率的直列ルール(PS)と呼ばれます。^{[ 1 ]}

SEは、各エージェントが各アイテムに対して受け取る割合を確率として解釈する公平なランダム割り当て問題の解決策として、エルヴェ・ムーランとアンナ・ボゴモルナイアによって開発されました。すべてのエージェントの摂食速度の積分が1であれば、各エージェントに割り当てられた割合の合計は1となるため、割合の行列は、各エージェントがちょうど1つのアイテムを受け取る割り当てのくじ引きに分解できます。摂食速度が等しい場合、くじ引きは、エージェントのアイテムランキングと整合するすべての効用関数ベクトルに対して、期待値（事前）において羨望フリーとなります。

SEの変種は、割り当てが決定論的（ランダムではない）なケーキカットにも適用された。 ^{[ 2 ]}

各アイテムはパン（またはその他の食品）として表現されます。最初に、各エージェントは自分の好きなアイテムのところへ行き、食べ始めます。複数のエージェントが同時に同じアイテムを食べることもあります。

アイテムが完全に食べ尽くされると、それを食べたエージェントはそれぞれ自分の好きな残りのアイテムのところへ行き、同じように食べ始めます。これをすべてのアイテムが食べ尽くされるまで繰り返します。

各アイテムについて、各エージェントが食べた割合が記録されます。ランダム割り当ての文脈では、これらの割合は確率とみなされます。これらの確率に基づいて、くじ引きが行われます。くじ引きの種類は問題によって異なります。

• 各エージェントが任意の数のアイテムを受け取ることができる場合、アイテムごとに個別の抽選を行うことができます。各アイテムは、そのアイテムの一部を食べ​​たエージェントのうち、そのアイテムの確率分布に従ってランダムに選ばれた1人に与えられます。
• 各エージェントがちょうど1つのアイテムを受け取る場合、決定論的な割り当ての集合上の何らかの確率分布に基づいて割り当てを選択する単一の抽選が必要となります。これを行うには、n × nの確率行列を順列行列の凸結合に分解する必要があります。これは、バーコフアルゴリズムによって実行できます。順列行列の数が最大でn² ^- 2n + 2となる組み合わせが必ず見つかります。

SEにおける重要なパラメータの一つは、各エージェントの摂食速度です。最も単純なケースでは、すべてのエージェントが同じ権利を持っている場合、すべてのエージェントが常に同じ速度で摂食するのが理にかなっています。しかし、エージェントが異なる権利を持っている場合、より特権的なエージェントに高い摂食速度を与えることが可能です。さらに、摂食速度を時間とともに変化させることもできます。重要なのは、各エージェントの摂食速度の積分が、そのエージェントが受け取るべきアイテムの総数と等しくなることです（割り当て設定では、各エージェントは正確に1つのアイテムを受け取るべきなので、すべての摂食速度関数の積分は1になるはずです）。

エージェントは4人、アイテムは4つ（w、x、y、zと表記）あります。エージェントの選好は以下のとおりです。

• アリスとボブは、w を x より好み、x より y より z より好む。
• キャロルとダナは、x、w、z、yの順で好む。

エージェントは平等な権利を持つため、1分間に1単位という均一な摂食速度でSE（摂食効率）を適用します。

最初に、アリスとボブはwへ、キャロルとダナはxへ行きます。それぞれのペアは同時に自分の食べ物を食べます。30秒後、アリスとボブはそれぞれwの半分を食べ、キャロルとダナはそれぞれxの半分を食べます。

次に、アリスとボブはy（残りのアイテムの中で一番好きなもの）のところへ行き、キャロルとダナはz（残りのアイテムの中で一番好きなもの）のところへ行きます。30秒後、アリスとボブはそれぞれyの半分を、キャロルとダナはそれぞれzの半分を持っています。

分数の行列は次のようになります。

摂取された割合に基づいて、アイテム w はアリスまたはボブに等しい確率で与えられ、アイテム y も同様です。アイテム x はキャロルまたはダナに等しい確率で与えられ、アイテム z も同様です。エージェントごとに正確に 1 つのアイテムを与える必要がある場合は、確率行列は次の 2 つの割り当て行列に分解されます。

これらの割り当てのうち1つが、1/2の確率で無作為に選ばれる。

その他の例は、MatchU.aiのウェブサイトで生成できます。

以下の説明では、すべてのエージェントがリスク中立的な選好を持っている、つまり、宝くじから得られる効用は、結果から得られる効用の期待値に等しいと仮定しています。

SEアルゴリズムは様々な形で拡張されてきた。

• KattaとSethuraman ^{[ 7 ]}は、弱い順序選好（無差別順位）を可能にする拡張PS（EPS）を発表した。このアルゴリズムは、パラメトリックネットワークフローのインスタンスを繰り返し解くことに基づいている。
• ボゴモルナイア^{[ 3 ]}は、レキシミン順序に基づいて、弱い選好に対するPSルールのより単純な定義を提示した。
• Yilmaz ^{[ 8 ]}は無関心と賦与の両方を認めている。
• アタナソグルトとセトゥラマン^{[ 9 ]}は、無差別と任意の量の部分的な賦存を可能にする制御消費（CC）ルールを提示している。
• Budish、Che、Kojima、Milgrom ^{[ 10 ]}は、アイテムごとに複数のユニット、エージェントよりも多くのアイテム、各エージェントが複数のユニットを取得できること、上限クォータ、実行可能な割り当てに対する二階層制約を可能にする一般化PSを発表した。
• Ashlagi、Saberi、Shameli ^{[ 11 ]}は、下限と上限の割り当て、および分布制約 (最終的な割り当てだけでなく確率分布に対する制約) を可能にする別の一般化 PSを提示しています。
• アジズとスターズバーグ^{[ 12 ]}は平等同時予約（ESR）を提示しており、これは公平なアイテムの割り当てだけでなく、無関心の可能性を伴う一般的な社会的選択問題も可能にする。
• アジズとブランドル^{[ 13 ]}は、より一般的な制約を可能にする警戒摂食（VE）を提示している。

前述のとおり、PSによって決定される配分は、事前の公平性は確保されるものの、事後の公平性は確保されません。さらに、各エージェントが任意の数のアイテムを取得できる場合、事後の不公平性は際限なく悪化する可能性があります。理論的には、あるエージェントがすべてのアイテムを取得し、他のエージェントは何も取得できないという事態も起こり得ます。近年、事前の公平性と事後の近似的な公平性の両方を保証するアルゴリズムがいくつか提案されています。

フリーマン、シャー、ヴァイシュ^{[ 14 ]}は以下を示している。

• 再帰的確率逐次アルゴリズム (RecPS) は、1 つのアイテムを除いてすべて羨望のない割り当て (EF1) の確率分布を返します。この分布は事前 EF であり、割り当ては事後 EF1 です。このアルゴリズムの単純なバージョンでは、指数関数的に増加する可能性のある決定論的割り当ての分布が生成され、エージェントと商品の数に関するサポートサイズの多項式で十分であるため、アルゴリズムは多項式時間で実行されます。このアルゴリズムは分離オラクルを使用します。
• 事前最大積配分に基づく別のアルゴリズムは、事前グループ羨望フリー（GEF、EFとPOの両方を意味する）と事後PROP1+EF ₁ ^{1を達成します}_。これは、これらすべての特性を達成する唯一の配分ルールです。EF1配分に分解することはできません。
• これらの特性の組み合わせは最善のものです。事前EF（PROPを含む）と事前POを事後EF1と同時に保証することは不可能です。また、事前EF（PROPを含む）と事後EF1および部分POを同時に保証することも不可能です。
• RecPSは、不良債権に対しても同様の保証（事前EFおよび事後EF1）を達成できるように修正することができる。

アジズ^{[ 15 ]}は以下を示している。

• PS宝くじアルゴリズムでは、事前の割り当てはsd-EFであり、宝くじはsd-EF1である決定論的な割り当ての間でのみ行われます。つまり、EFとEF1の保証は、順序付けと整合する任意の基数効用に対して成り立ちます。さらに、結果は事前と事後の両方でsd-POです。このアルゴリズムは、サブルーチンとしてPSアルゴリズムとBirkhoffアルゴリズムの両方を使用します。事前の割り当てはPSによって返される割り当てと等価です。これは、PSの結果をEF1割り当てに分解できることを示しています。
• バイナリ効用を用いる場合、PS宝くじアルゴリズムはグループ戦略耐性があり、事前PO、事前EF、事後EF1である。
• これらの特性の組み合わせは最良の組み合わせです。事前のsd-EF、事後のEF1、事後のPO、または事前のPOと事前のsd-EFを同時に保証することは不可能です。
• 与えられたランダム割り当てがEF1およびPO割り当てに対する抽選によって実現可能かどうかを検証することはNP困難である。

ババイオフ、エズラ、ファイゲ^{[ 16 ]}は以下を示している。

• 事前比例配分、事後PROP1と1/2分率最大最小配分（および1/2分率切り捨て比例配分）の両方を計算するための多項式時間アルゴリズム。
• これらの特性はほぼ最適であり、事前のPROPを超えること、事後のn /(2 n -1)を超える切り捨て比例配分を保証することは不可能です。

Hoefer、Schmalhofer、Varricchio ^{[ 17 ]}は、「両方の世界のベスト」くじの概念を、異なる権利を持つエージェントに拡張しています。

公平なランダム割り当てに関するページでは、 PSを、ランダム優先順位ルールなど、同じ問題を解決するための他の手順と比較しています。