公平なランダム割り当て

公平なランダム割り当て(確率的片側マッチングとも呼ばれる) は、公平な分割問題の一種です。

割り当て問題(ハウス割り当て問題または片側マッチングとも呼ばれる)では、 m 個のオブジェクトがあり、各エージェントが最大 1 つのオブジェクトを受け取るように、それらをn個のエージェントに割り当てる必要があります。例としては、労働者への仕事の割り当て、ハウスメイトへの部屋の割り当て、学生への寮の割り当て、共通マシンのユーザーへの時間帯の割り当てなどがあります。

一般的に、公平な割り当ては実現不可能な場合があります。たとえば、アリスとバティアが両方とも西側の部屋よりも東側の部屋を好む場合、どちらか一方だけが東側の部屋を手に入れ、もう一方は嫉妬することになります。ランダム割り当て設定では、くじ引きによって公平性が実現されます。したがって、上記の単純な例では、アリスとバティアは公平なコインを投げ、勝者が東側の部屋を手に入れます。

無作為の割り当てについては聖書にすでに言及されています。カナンの土地をイスラエルの部族に割り当てるためにくじ引きが使われました(民数記 26:55)。

米国では、抽選によって開拓者に公有地を割り当てたり（例：1901年のオクラホマ州）、放送局に無線周波数を割り当てたり（例：FCC 1981-1993）、グリーンカードの割り当てに今でも抽選が使われている。^[1]

「コイントス」方式を、2 つ以上のエージェントが存在し、オブジェクトに対する 異なる優先関係を持つ可能性がある状況に拡張する方法はいくつかあります。

• ランダム優先順位(RP、別名ランダムシリアル独裁制、RSD) は、エージェントが個々のアイテムに対して順序付けを行うことだけを要求する非常にシンプルなメカニズムです。アイテムの優先順位をランダムに選択し、各エージェントが順番に残りのアイテムから好きなものを選択できるようにします。
• 確率的シリアル（PS）^[2]は、アイテムの順序付けでのみ機能する別のメカニズムです。エージェントは一定の速度で残りのお気に入りのアイテムを「食べ」、各エージェントが食べた割合が、そのアイテムを獲得する確率になります。
• 平等所得からの競争均衡（CEEI）^[3]は市場ベースのメカニズムです。各アイテムは分割可能な商品とみなされます。各エージェントには不換紙幣の均等な予算が与えられ、エージェントは価格均衡になるまで取引を行うことができます。これはより複雑なメカニズムであり、エージェントは完全な基数効用関数（または、代わりに宝くじの順位付け）を持っている必要があります。

ランダム割り当てルールの望ましい特性の 1 つは、パレート効率(PE) です。PE には 3 つのバリエーションがあります。

• 事後 PE とは、最終的な配分が決定された後、あるエージェントにとってより良い配分は存在せず、他のエージェントにとっても少なくとも同等に良い配分は存在しないことを意味します。上記の 3 つのルール (RP、PS、CEEI) はすべて事後 PE です。
• 事前 PE は、基数効用を持つエージェントに関連する、より強力なプロパティです。これは、あるエージェントにとって他の宝くじよりも優れているものはなく、他のエージェントにとっては少なくとも同じくらい優れているということを意味します。エージェントが期待効用に基づいて宝くじを比較する場合、CEEI は事前 PE です。
• 可能 PE (または sd-PE) は、順序効用を持つエージェントに関連する中間特性です。これは、エージェントの順序順位と一致するいくつかの評価関数について、割り当てが事前 PE であることを意味します。PS は可能 PE ですが、RP はそうではありません。

PE の場合、意味合いは、事前 → sd(可能) → 事後となります。

もう一つの望ましい特性は、嫉妬されない性質(EF) です。EF にも 3 つの種類があります。

• 事後 EF とは、最終的な割り当てが決定された後、どのエージェントも他のエージェントの割り当てを好まないことを意味します。この強力な特性を満たすルールはありません。実際、分割できないオブジェクトの事後 EF 割り当てを見つけることは不可能かもしれません。
• 事前 EF は、基数効用を持つエージェントに関連する弱い特性です。これは、どのエージェントも他のエージェントのくじを好まないことを意味します。CEEI は、期待効用に関する事前 EF です。
• 必要EF（またはsd-EF）は、順序効用を持つエージェントに関連する中間特性です。これは、エージェントの順序順位と一致するすべての評価関数に対して、割り当てが事前EF（下記参照）であることを意味します。PSは必要EFですが、RPはそうではありません。RPは弱い事前sd-EFです。エージェントが辞書式優位性（ld-EF）で宝くじを比較する場合はEFです。^[4]

EF の場合、含意の方向は効率性とは逆になります。つまり、事後 → 必要 (sd) → 事前です。

3 番目に望ましい特性は、真実性(戦略耐性とも呼ばれる) です。これも、3 つのバリエーションがあります。

• 事前の誠実性は、基数効用を持つエージェントに関係し、偽の評価を報告することでより良い抽選に当選するエージェントはいないことを意味します。これは強力な特性であり、いかなる非自明なメカニズムでも満たされません。

• 可能な真実性は、順序効用を持つエージェントに関連する弱い特性です。エージェントは、偽のランキングを報告することで確率的に優勢な抽選に当たらないことを意味します。この弱い特性は、すべてのランキングが厳密で、1人あたり最大1つのオブジェクトがある場合にPSによって満たされます。この設定では、辞書式優勢性に関しても真実です（ld-truthful）。^[4]ランキングが弱い場合は満たされません。^[5]
• 必要不可欠な真実性は、順序効用を持つエージェントに関連する、より強力な特性です。つまり、誤ったランキングを報告するエージェントは、常に確率的に優勢な抽選に当選します。この強力な特性は RP によって満たされ、人よりもオブジェクトの数が多い一般的なケースにも真実に拡張できます。

次の表は、さまざまなルールの特性を比較したものです（RP列とPS列は^[6]に基づいています）。

上記の 3 つの特性のいくつかの組み合わせは、どのようなメカニズムでも同時に満たすことができません。

• 周^[7]は、基数効用を持つエージェントに対して、事前の効率性、事前の真実性、同等の者同士の平等な扱い（＝同一の効用関数を持つエージェントは同じ効用を得るべきである）を満たすメカニズムは存在しないことを証明している。
• ボゴモルナヤとムーラン^[2]は、厳密な順序効用を持つエージェントについては、可能な効率性、必要な真実性、同等の者に対する平等な扱いを満たすメカニズムは存在しないことを証明した。
• カッタとセトゥラマン^[5]は、弱い順序効用を持つエージェントについては、可能な効率性、可能な真実性、および必要な嫉妬のなさを満たすメカニズムは存在しないことを証明した。

PS ルールと CEEI ルールはどちらも、期待される割り当てのマトリックス、つまり各エージェントが各オブジェクトを受け取る限界確率を計算します。ただし、最終的な割り当てはマッチングでなければならないため、このマトリックスをマッチングの抽選に 分解する必要があります。

m = nの古典的な設定では、これはバーコフアルゴリズムを使用して実行できます。このアルゴリズムは、任意のnバイnのエージェントオブジェクト確率行列を、それぞれがマッチングを表す O( n ² )の順列行列の凸結合に分解できます。ただし、分解は一意ではなく、一部の分解は他の分解よりも優れている場合があります。

Budish、Che、Kojima、Milgrom ^{[1]は、バーコフのアルゴリズムを任意の}mとnに一般化しています。また、制約セットの条件の最大セットの下で、割り当てに制約を追加することもできます。また、異なるマッチング間でエージェントが経験する効用の分散を最小限に抑える分解方法も提示しています。

Demeulemeester、Goossens、Hermans、および Leus ^{[8] は}、オブジェクトを受け取るエージェントの最悪ケース数を最大化する多項式時間分解アルゴリズムを提示しています。彼らのアルゴリズムは、最悪ケースのエージェント数が、切り捨てられたエージェントの期待数と等しくなることを保証します。これは可能な限り最良のものです。彼らは、分解内のすべてのマッチングが事後 PE であることを保証しながら、割り当てられたエージェントの最悪ケース数を最大化する別の分解アルゴリズムを提示しています。2 番目のアルゴリズムは、PS によって出力される分数割り当てにのみ使用でき、RP に対応するものは使用できません。RP の場合、割り当てられたエージェントの最適な最悪ケース数の 1/2 係数近似値しか得られません。一般的な分数割り当ての場合、事後 PE の対象となる割り当てられたエージェントの最悪ケース数を最大化することは NP 困難です。彼らはまた、他の最悪ケース基準を最適化するために使用できる 列生成フレームワークを提示しています。

ホセイニ、ラーソン、コーエン^[6]は、様々な設定でRPとPSを比較しています。彼らは次のことを示しています。

• オブジェクトが最大 2 個、エージェントが最大 3 個ある場合、RP と PS は同じ割り当てを返します。
• オブジェクトが最大 2 個ある場合、エージェントの数に関係なく、PS は sd 真実であり、RP は sd 羨望がなく、ほとんどの場合、特にエージェントが 4 人以上の場合は、PS が RP を支配します。
• 3 つ以上のオブジェクト (および 3 つ以上のエージェント) がある場合、RP と PS は異なる割り当てを返すことがあり、割り当てが他方をパレート優位にすることはありません。たとえば、3 つのオブジェクト a、b、c と、優先順位が (1) a>c>b、(2) a>b>c、(3) b>a>c である 3 つのエージェントがあるとします。この場合、エージェント (1) に対しては、RP と PS の両方が 1/2 a + 1/2 c を返します。エージェント (2) に対しては、RP は 1/2 a + 1/6 b + 1/3 c を返しますが、PS は確率的に優位な1/2 a + 1/4 b + 1/4 cを返します。エージェント (3) に対しては、RP は 5/6 b + 1/6 c を返しますが、PS は確率的に優位な 3/4 b + 1/4 c を返します。したがって、(1)は無関心、(2)はPSを厳密に優先、(3)はRPを厳密に優先します。
• PS が RP を sd 優位にする選好プロファイルの割合は、エージェントとオブジェクトの数が異なる場合は大きくなりますが、数が等しい場合は 0 に近づきます。ld 優位の場合も同様です。
• エージェントがリスク中立である場合、 PS の期待される社会的厚生は RP よりも大きくなりますが、その差が大きくなるのはn≠mのときだけです。RP では、 n ≥ mの場合、嫉妬深いエージェントの割合はゼロに近くなります。 PS は操作可能であり、 m > nの場合、操作による利益が増加します。
• エージェントがリスク志向である場合、PS の期待される社会的厚生は RP よりも大きく、n≠m の場合、その差は急速に大きくなります。対照的に、n = m の場合、ほとんどの場合、RP の方が社会的厚生が高くなります。RP では、 n ≥ mの場合、嫉妬深いエージェントの割合はほぼゼロですが、 m>nの場合は嫉妬を生み出します。リスク志向が高まると、RP の嫉妬は減少します。エージェントがリスク志向が高まると、PS を操作することによる利得は減少します。
• エージェントがリスク回避的である場合、RP と PS 間の社会福祉格差は小さくなります (ただし、統計的には依然として有意です)。RP における嫉妬深いエージェントの割合は増加しますが、n ≥ mの場合、嫉妬は 0.01 未満のままです。m / nが増加すると、PS の操作可能性は 1 になります。

タオとコール^[9]は、効用が非線形（補完関係を持つことができる）である場合のPEとEFのランダム割り当ての存在を研究している。

Yilmaz ^[10]は、エージェントが財産を持っている場合のランダム割り当て問題を研究している。

Shen、Wang、Zhu、Fain、Munagala ^[11]は、エージェントが優先順位を持っている（優先順位の高いエージェントは優先順位の低いエージェントよりも先に好みの商品を手に入れるべきである）が、優先順位が不確実な場合のランダム割り当て問題を研究した。

ダディ^[12]は平等主義的ランダム割り当てを研究している。

• レンタルハーモニーは、ランダム化ではなく金銭の支払いを使用して公平性を達成する割り当て問題の変形です。
• 公平なアイテム割り当ては、エージェントが複数のアイテムを取得できる設定です。
• 抽選- 政治関係者の無作為な選出。
• ランダムな両面マッチング- 主にスポーツトーナメントで使用されます。