住宅割り当て問題

経済学とコンピュータサイエンスにおいて、住宅割り当て問題とは、異なる嗜好を持つ人々に、それぞれが正確に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 and Suksompong ^{[6] : Thm.3.5 は}これがNP困難であることを証明している。この証明は、最小被覆問題（別名二部展開問題）からの帰着による。Madathil, Misra and Sethia ^[7]は、各エージェントが最大で2軒の家を評価する場合でもNP困難であり、嫉妬深いエージェントの数でパラメータ化された場合はW[1]困難であることを証明している。この証明は、最大クリーク問題からの帰着による。ただし、家のタイプとエージェントのタイプの総数でパラメータ化された場合は固定パラメータで扱いやすく、エージェントが「極端な間隔」の好みを持つ場合は効率的に解くことができる。
• 単一のエージェントが羨望するエージェントの最大数が最小となる完全なEF割り当てを求める。マダシル、ミスラ、セシア^[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 and Suksompong ^{[6] : Thm.4.1}正確な3セットカバーからの還元により、それがNP完全であることを証明する。
• 完全な公平な割り当てが存在するかどうかの決定。Kamiyama、Manurangsi、Suksompong ^{[6] ：Thm.5.1}は多時間アルゴリズムを提示している。
• 最大カーディナリティを持つ部分EF割り当てを求める。この問題の実行時計算量は未解決である。^{[5] : 未解決問題2}

関連する問題

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

参考文献

1. Abdulkadiroğlu, Atila; Sönmez, Tayfun (1999-10-01). 「既存入居者への住宅割り当て」. Journal of Economic Theory . 88 (2): 233– 260. doi : 10.1006/jeth.1999.2553 . ISSN  0022-0531.
2. ；ケイザー、バート・デ（2012年）「無関心な住宅市場：二つ のメカニズム の物語」AAAI人工知能会議議事録。26 （ 1）：1249-1255。doi：10.1609/aaai.v26i1.8239。ISSN 2374-3468。S2CID 15395473。
3. Roth, Alvin E. (1982-01-01). 「分割不可能な財が存在する市場におけるインセンティブの両立性」. Economics Letters . 9 (2): 127– 132. doi :10.1016/0165-1765(82)90003-9. ISSN  0165-1765.
4. Ergin, Haluk İ. (2000-08-01). 「住宅割り当て問題における一貫性」 . Journal of Mathematical Economics . 34 (1): 77– 97. doi :10.1016/S0304-4068(99)00038-5. hdl : 11693/18154 . ISSN  0304-4068.
5. Segal-Halevi, Erel; Aigner-Horev, Elad (2022). 「二部グラフにおける羨望のないマッチングと公平な分割への応用」. Information Sciences . 587 : 164–187 . arXiv : 1901.09527 . doi :10.1016/j.ins.2021.11.059. S2CID  170079201.
6. 神山尚之; マヌランシ・パシン; スクソンポン・ワルト (2021-07-01). 「公平な住宅割り当ての複雑性について」.オペレーションズ・リサーチ・レターズ. 49 (4): 572– 577. arXiv : 2106.06925 . doi :10.1016/j.orl.2021.06.006. ISSN  0167-6377. S2CID  235422019.
7. Madathil, Jayakrishnan; Misra, Neeldhara; Sethia, Aditi (2023-05-30). 「住宅割り当てにおける嫉妬の最小化の複雑性」.自律エージェントおよびマルチエージェントシステムに関する国際会議2023の議事録. AAMAS '23. サウスカロライナ州リッチランド: 自律エージェントおよびマルチエージェントシステム国際財団: 2673–2675 . ISBN 978-1-4503-9432-1。
8. ガン、ジアルイ;スクソンポン、ワルト。ヴドゥーリス、アレクサンドロス A. (2019-09-01)。 「住宅割り当て問題における妬みの解消」。数学社会科学。101 : 104–106.arXiv : 1905.00468 。​​土井：10.1016/j.mathsocsci.2019.07.005。ISSN  0165-4896。S2CID  143421680。
9. ベニエ、オーレリー;シュヴァレイル、ヤン。グルヴェ、ローラン。ハルトゥニャン、アララト。レスカ、ジュリアン。モーデ、ニコラ。ウィルチンスキー、アナエル (2019-09-01)。 「住宅割り当て問題における地元の羨望の無さ」。自律エージェントとマルチエージェント システム。33 (5): 591–627。土井:10.1007/s10458-019-09417-x。ISSN  1573-7454。S2CID  51869987。