住宅割り当て問題

経済学とコンピュータサイエンスにおいて、住宅割り当て問題とは、異なる嗜好を持つ人々にオブジェクトを割り当てる問題であり、各人が正確に 1 つのオブジェクトを受け取るようにします。「住宅割り当て」という名前は、主な動機付けのアプリケーションである学生への寮の割り当てに由来しています。^[1]他のよく使用される用語には、割り当て問題や片側マッチングがあります。エージェントがすでに住宅を所有している場合 (他のエージェントと交換できる場合)、この問題は住宅市場と呼ばれることがよくあります。^[2]住宅割り当て問題では、金銭の移動が許可されていないと想定されています。金銭の移動が許可されているバリエーションは、レンタルハーモニーとして知られています。

n人の人 (エージェントとも呼ばれる) と m 個のオブジェクト (家とも呼ばれる)が存在します。エージェントは家に対して異なる好みを持つ場合があります。エージェントはさまざまな方法で好みを表現します。

• バイナリ評価: 各エージェントは各家を 1 (エージェントがその家を気に入っていることを意味する)、または 0 (エージェントがその家を気に入っていないことを意味する) のいずれかで評価します。
• 優先順位付け: 各エージェントは、家を最高から最低まで順位付けします。順位付けは厳密(無差別なし) または緩い(無差別を許可)です
• 基数効用: 各エージェントは各家に負でない数値を割り当てます。

住宅割り当てのアルゴリズムを設計する際には、いくつかの考慮事項が重要になる場合があります。

• パレート効率(PE) - 一部のエージェントにとってより良い割り当ては存在せず、すべてのエージェントにとって悪い割り当ては存在しません。
• 公平性- さまざまな方法で定義できます。たとえば、羨望のなさ (EF) -どのエージェントも他のエージェントを羨んではなりません。
• 戦略耐性(SP) - 各エージェントには、自分の本当の好みをアルゴリズムに報告するインセンティブがあります。
• 個別合理性 (IR) - アルゴリズムに参加することで損失を被るエージェントは存在しません。

経済学では、住宅配分における主な効率要件は PE です。さまざまな設定で PE 配分を達成するさまざまなアルゴリズムがあります。

おそらく最も単純な住宅割り当てアルゴリズムは、シリアル独裁制です。エージェントは任意の順序（たとえば、年功序列）で並べられ、各エージェントは順番に自分の好みで残っている最良の住宅を選択します。このアルゴリズムは明らかに SP です。エージェントの好みが厳密な場合は、PE 割り当てを見つけます。ただし、最後に選択したエージェントに対しては非常に不公平になる可能性があります。順序を一様にランダムに選択することで、より公平にすることができます（期待値）。これは、ランダムシリアル独裁制と呼ばれるメカニズムにつながります。このメカニズムは事後 PE ですが、事前 PE ではありません。事前 PE である他のランダム化メカニズムについては、 公平なランダム割り当てを参照してください。

各エージェントがすでに家を所有している場合、公平性の考慮はそれほど重要ではなく、参加することで損失が出ないことをエージェントに保証すること（IR）の方が重要です。トップトレーディングサイクルアルゴリズムは、IR、PE、SPを保証するユニークなアルゴリズムです。厳格な優先順位により、TTCはユニークなコア安定割り当てを見つけます。^[3]

AbdulkadirogluとSönmez ^[1]は、一部のエージェントがすでに家を所有している一方で、他の一部のエージェントは家を持っていないという拡張された設定を検討しています。彼らのメカニズムはIR、PE、SPです。彼らはこのメカニズムを実装する2つのアルゴリズムを提示しています。

エルギン^[4]は、一貫性のある、つまり予測が割り当てが実現される順序に依存しない 規則も検討している。

コンピュータサイエンスとオペレーションズリサーチでは、効率性に関する主な要件は効用の合計を最大化することです。効用の合計を最大化する住宅割り当てを見つけることは、重み付き二部グラフで最大重みマッチングを見つけることと同等であり、割り当て問題とも呼ばれます。

マッチングの公平性に関連するアルゴリズムの問​​題は、さまざまな状況で研究されてきました。

エージェントがバイナリ評価を持つ場合、それらの「類似」関係は、エージェントと家のセット上の二部グラフを定義します。羨望のない家の割り当ては、このグラフ内の羨望のないマッチングに対応します。次のアルゴリズムの問​​題が研究されています。

• 完全な EF割り当てが存在するかどうかを決定します。これは、すべてのエージェントを飽和させるマッチングが存在する場合にのみ当てはまります。これは、二部グラフで最大カーディナリティのマッチングを見つけるだけで、多項式時間で決定できます。
• 最大濃度の部分EF割り当てを見つける。Aigner-HorevとSegal-Halevi ^{[5] ：Thm.1.6(a)は}多時間アルゴリズムを提示する。
• 最大濃度と最小コストの部分EF割り当てを見つける（各エッジには社会に対する事前指定されたコストがある）。Aigner-HorevとSegal-Halevi ^{[5] ：Thm.1.6（b）は}多時間アルゴリズムを提示している。
• 嫉妬深いエージェントの数が最小となる完全なEF割り当てを見つけること。Kamiyama、Manurangsi、Suksompong ^{[6] : Thm.3.5は}、それがNP困難であることを証明しています。この証明は、最小被覆率（別名二部展開）問題からの還元によって行われます。Madathil、Misra、Sethia ^[7]は、各エージェントが最大で2軒の家を評価する場合でもNP困難であり、嫉妬深いエージェントの数でパラメーター化されるとW[1]困難であることを証明しています。この証明は、最大クリーク問題からの還元によって行われます。ただし、家のタイプとエージェントのタイプの合計数でパラメーター化されると、問題は固定パラメータで扱いやすく、エージェントが「極端な間隔」の好みを持つ場合は効率的に解決できます。
• 1人のエージェントが羨むエージェントの最大数が最小となる完全なEF割り当てを見つけること。Madathil、Misra、Sethia ^[7]は、各エージェントが最大2軒の家を評価し、すべての家が一定数のエージェントによって承認され、許容される羨望の最大数がちょうど1である場合でも、NP困難であることを証明しています。証明は、立方グラフ上の最大独立セットからの還元によって行われます。ただし、家のタイプとエージェントタイプの総数でパラメータ化されると、問題は固定パラメータで扱いやすくなり、エージェントが「極端な間隔」の好みを持つ場合は効率的に解決できます。

エージェントが基数評価を持つ場合、エージェントと家のグラフは重み付き二部グラフになります。次のアルゴリズムの問​​題が研究されています。

• 完全な EF割り当てが存在するかどうかを決定します。
  • m = nの場合、すべての家を割り当てる必要があるため、割り当ては各エージェントが最も価値の高い家を取得する場合にのみ EF になります。したがって、元のグラフを重み付けされていないグラフに縮小し、各エージェントが最も価値の高い家にのみ隣接し、このグラフで完全なマッチングを探すことができます。
  • m > nの場合、すべての家を割り当てる必要はないため、上記のアルゴリズムは機能しない可能性があります。つまり、1つの家がすべてのエージェントによって最も好まれる場合でも、この特定の家が割り当てられていない完全な EF 割り当てが存在する可能性があります。Gan、Suksompong、Voudouris ^[8]は、任意のm ≥ nに対して完全な EF 割り当てが存在するかどうかを多項式時間で決定する多項式時間アルゴリズムを提示しています。彼らのアルゴリズムは、サブルーチンとして、包含最小ホール違反を見つけるアルゴリズムを使用しています。
• 完全なローカル羨望のない割り当てが存在するかどうかの決定。ローカル羨望のない割り当てとは、エージェントがソーシャルネットワーク上に位置し、そのネットワーク内の隣人だけを羨むことを意味します。Beynier、Chevaleyre、Gourves、Harutyunyan、Lesca、Maudet、Wilczynski ^{[9]は、さまざまなネットワーク構造に対して、} m = nに対して完全なローカル羨望のない割り当てが存在するかどうかを決定する問題を研究しています。
• 非嫉妬エージェントの数が最大になる完全な EF割り当てを見つける。Kamiyama、Manurangsi、Suksompong。 ^{[6] ：Thm.3.1 は}、一般的な複雑性理論的仮定の下では、この問題を近似することが難しいことを証明しています。特に、NP が指数関数的時間未満で解決できない場合、ある に対しての係数以内に近似することはできません。小集合拡張仮説が正しい場合は、任意の に対しての係数以内に近似することはできません(近似するのは簡単であるため、1 人のエージェントにお気に入りの家を与え、他のエージェントを任意に割り当てるだけです)。証明は、最大バランスのとれた 2 クリーク問題からの簡約によって行われます。${\displaystyle n^{\gamma}}$${\displaystyle \gamma >0}$${\displaystyle n^{\gamma}}$${\displaystyle \gamma <1}$${\displaystyle \gamma =1}$
• 完全な比例配分が存在するかどうかの決定。Kamiyama、Manurangsi、Suksompong ^{[6] ：Thm.4.1は、}正確な3セットカバーからの還元によって、それがNP完全であることを証明する。
• 完全な公平な割り当てが存在するかどうかを決定する。Kamiyama、Manurangsi、Suksompong ^{[6] ：Thm.5.1は}多時間アルゴリズムを提示する。
• 最大基数の部分的なEF割り当てを見つける。この問題の実行時複雑度は未解決である。^{[5] ：未解決問題2}

• 割り当て問題- 各エージェントは単一のオブジェクトを取得する必要があります。目標は、評価の合計を最大化するか、コストの合計を最小化することです。
• 公平なランダム割り当て- 各エージェントは 1 つのオブジェクトを取得する必要があります。ランダム化が許可されます。割り当ては、期待どおりに公平かつ効率的である必要があります。
• レンタルの調和- 各エージェントは単一のオブジェクトを取得し、価格を支払う必要があります。オブジェクトと価格の割り当ては、羨望の的にならないものでなければなりません。
• 羨望のないマッチング- 割り当てられた住宅のいずれも気に入らないエージェントは、割り当てられないままになる場合があります。
• 公平なアイテム割り当て- 各エージェントは任意の数のオブジェクトを取得できます。