주택 할당 문제

House allocation problem

경제학과 컴퓨터 과학에서, 주택 할당 문제는 다른 선호도를 가진 사람들에게 객체를 할당하는 문제이며, 그래서 각 사람이 정확히 하나의 객체를 받게 된다."주택 할당"이라는 이름은 학생들에게 [1]기숙사 주택을 할당하는 주된 동기 부여 어플리케이션에서 유래했다.일반적으로 사용되는 다른 용어는 할당 문제와 단측 일치입니다.중개업자가 이미 집을 소유하고 있는 경우(그리고 다른 중개업자와 거래할 수 있는 경우), 이 문제를 흔히 주택 [2]시장이라고 부릅니다.주택 할당 문제에서는 화폐 이전이 허용되지 않는다고 가정한다. 화폐 이전이 허용되는 변형은 임대 조화라고 알려져 있다.

정의들

n명의 사람(에이전트라고도 함)과 m개의 오브젝트(하우스라고도 함)가 있습니다.에이전트마다 주택에 대한 선호도가 다를 수 있습니다.선호도를 다양한 방법으로 표현할 수 있습니다.

  • 바이너리 평가: 각 에이전트는 각 하우스를 1(에이전트가 집을 좋아한다는 의미) 또는 0(에이전트가 집을 싫어한다는 의미)으로 평가합니다.
  • 선호도 순위: 각 에이전트는 주택의 순위를 최고에서 최저로 매깁니다.순위는 엄격하거나(무관심), 약할 수 있다(유추 허용).
  • 기본 유틸리티: 각 에이전트는 각 하우스에 음수가 아닌 숫자 값을 할당합니다.

주택 배분을 위한 알고리즘을 설계할 때 몇 가지 고려사항이 중요할 수 있다.

  • Pareto Efficiency(PE; 파레토 효율) - 일부 에이전트에 대해 더 나은 할당은 없으며 모든 에이전트에 대해 더 나쁜 할당은 없습니다.
  • 공정성 - 예를 들어 envy-freeness (EF) 등 다양한 방법으로 정의할 수 있습니다.에이전트는 다른 에이전트를 부러워해서는 안 됩니다.
  • Strategyproofness(SP) - 각 에이전트는 알고리즘에 대한 진정한 선호도를 보고하도록 인센티브를 받습니다.
  • 개별 합리성(IR) - 에이전트가 알고리즘에 참여하는 것으로 손해를 보는 일은 없습니다.

효율적인 할당

경제학에서 주택 할당의 주요 효율성 요건은 PE입니다.다양한 설정으로 PE 할당을 실현하는 다양한 알고리즘이 있습니다.

아마도 가장 간단한 주택 할당 알고리즘은 시리얼 독재일 것입니다.에이전트는 임의의 순서(예를 들어 연공서열)로 정렬되고 각 에이전트는 자신의 취향에 따라 최적의 남은 주택을 선택합니다.이 알고리즘은 분명히 SP입니다.에이전트의 기본 설정이 엄격한 경우 PE 할당을 찾습니다.그러나 마지막으로 선택한 에이전트에게는 매우 불공평할 수 있습니다.그것은 순서를 무작위로 균일하게 선택함으로써 더 공정해질 수 있다; 이것은 무작위 연쇄 독재라고 불리는 메커니즘으로 이어진다.메커니즘은 PE ex-post이지만 PE ex-ante는 아닙니다.다른 랜덤화된 메커니즘의 공정한 랜덤 할당을 참조하십시오.

각 에이전트가 이미 주택을 소유하고 있는 경우 공정성에 대한 고려는 덜 중요하며 참여(IR)로 인해 손실되지 않음을 에이전트에게 보증하는 것이 더 중요합니다.상위 거래 사이클 알고리즘은 IR, PE 및 SP를 보장하는 고유한 알고리즘입니다.엄격한 프리퍼런스를 사용하여 TTC는 고유한 코어 안정 [3]할당을 찾습니다.

Abdulkadiroglu와 Sönmez는[1] 일부 에이전트가 이미 집을 소유하고 있는 반면 다른 에이전트는 집이 없는 확장 환경을 고려하고 있습니다.메커니즘은 IR, PE 및 SP입니다.이들은 이 메커니즘을 구현하는 두 가지 알고리즘을 제시합니다.

Ergin은[4] 규칙도 일관되게 고려합니다.즉, 그 예측은 할당이 실현되는 순서에 의존하지 않습니다.

컴퓨터 과학 및 운영 연구에서, 1차 효율 요건은 유틸리티의 합계를 최대화하는 것입니다.효용 합계를 최대화하는 주택 할당을 찾는 것은 가중 초당 그래프에서 최대 가중치 일치를 찾는 것과 같다. 할당 문제라고도 한다.

공평한 할당

매칭의 공정성과 관련된 알고리즘 문제는 여러 맥락에서 연구되어 왔다.

에이전트가 이진수 값을 갖는 경우 에이전트와 하우스 집합에 대해 "좋아요" 관계가 초당 그래프를 정의합니다.선망 없는 주택 할당은 이 그래프에서 선망 없는 매칭에 해당합니다.다음과 같은 알고리즘 문제가 연구되었습니다.

  • 완전한 EF 할당이 존재하는지 여부를 판단합니다.이는 모든 에이전트를 포화시키는 매칭이 존재하는 경우 유지되며, 이는 초당 그래프에서 최대 카디널리티 매칭을 찾는 것만으로 다항 시간 내에 결정할 수 있습니다.
  • 최대 카디널리티의 부분 EF 할당 찾기이것은 다항식 시간에 [5]: Thm.1.6(a) 할 수 있다.
  • 최대 카디널리티 및 최소 비용의 일부 EF 할당(각 엣지에는 사회에 대한 사전 지정된 비용이 있음)을 찾습니다.이것도 다항식 시간에 [5]: Thm.1.6(b) 할 수 있다.
  • 완전한 EF 할당 찾기(불침투성 에이전트 수가 최대화됨).이 문제는 NP하드입니다.그 증거는 최소 커버리지([6]: Thm.3.5 일명 초당적 확장) 문제에서 감소하는 것입니다.

에이전트의 기본 평가가 있는 경우 에이전트와 하우스의 그래프는 가중치 초당 그래프가 됩니다.다음과 같은 알고리즘 문제가 연구되었습니다.

  • 완전한 EF 할당이 존재하는지 여부를 판단합니다.
    • m=n이면 모든 하우스를 할당해야 하므로 각 에이전트가 가장 높은 값을 가진 하우스를 얻을 경우 할당은 EF가 됩니다.따라서 원래 그래프를 가중치 없는 그래프로 축소하여 각 에이전트가 가장 높은 값의 주택에만 인접하는 경우 이 그래프에서 완벽한 일치를 찾을 수 있습니다.
    • m>n의 경우 모든 하우스를 할당할 필요는 없기 때문에 위의 알고리즘이 동작하지 않을 수 있습니다.모든 에이전트에 의해 단일 하우스가 가장 우선되는 경우에도 이 특정 하우스가 할당되지 않은 완전한 EF 할당이 존재할 수 있습니다.Gan, Suksompong 및 Voudouis는[7] mµn에 대해 완전한 EF 할당이 존재하는지 여부를 다항 시간 내에 결정하는 다항 시간 알고리즘을 제시한다.이들의 알고리즘은 서브루틴으로서 포함 최소 홀 위반자를 찾기 위한 알고리즘을 사용합니다.
  • 완전한 로컬 기반 할당이 존재하는지 여부를 판단합니다.로컬 엔비프리란 에이전트가 소셜네트워크상에 있는 것을 의미하며, 그 네트워크 내의 네이버만 부러워합니다.Beynier, Chevaleyre, Gourves, Harutyunyan, Lesca, Maudet 및 Wilczynski는[8] 다양한 네트워크 구조에 대해 m=n에 대해 완전한 로컬 무배당 할당이 존재하는지 여부를 결정하는 문제를 연구한다.
  • 완전한 EF 할당 찾기(불침투성 에이전트 수가 최대화됨).일반적인 복잡성 이론상 가정 하에서 이 문제는 근사하기 어렵다.만약 NPsubexponential 시간에 해결될 수 없습니다. 특히, 그러는 nγ{\displaystyle n^{\gamma}의 일부 γ 을에 대한 인자};0{\displaystyle \gamma>0}내에, 작은 첫발들 내딧었을 확장 가설이 맞다면, 이것에 nγ의 요인{\displaystyle n^{\ga 내에 가깝 수 없할 수 없다.mma} < \ display \ \ 1 의 , 개산은 간단합니다한쪽 에이전트가 마음에 드는 집을 지정하고 다른 에이전트는 임의로 할당합니다.그 증거는 최대 균형 양립 [6]: Thm.3.1 문제에서 감소하는 것이다.
  • 완전한 비례 할당이 존재하는지 여부를 판단합니다.이 문제는 정확히 3세트 [6]: Thm.4.1 커버에서 감소하여 NP-완전입니다.
  • 완전한 공평한 할당이 존재하는지 여부를 판단한다.이 문제는 다항식 [6]: Thm.5.1 시간으로 해결할 수 있다.
  • 최대 카디널리티의 부분 EF 할당 찾기이 문제의 런타임 복잡성은 해결되지 않았습니다.[5]: open question 2

관련 문제

  • 할당 문제 - 각 에이전트는 단일 개체를 얻어야 합니다.목표는 평가의 합계를 최대화하거나 비용 합계를 최소화하는 것입니다.
  • 균등하게 랜덤 할당 - 각 에이전트는 단일 개체를 얻어야 합니다.랜덤화가 허용됩니다.배분은 기대에서 공정하고 효율적이어야 한다.
  • 렌탈 조화 - 각 대리점은 하나의 오브젝트를 구입하여 대가를 지불해야 합니다.오브젝트+가격의 할당은 부러움이 없어야 합니다.
  • 질투 없는 일치 - 할당된 집이 마음에 들지 않는 한 일부 에이전트는 할당되지 않은 상태로 남아 있을 수 있습니다.
  • 공정한 항목 할당 - 각 에이전트가 원하는 수의 개체를 가져올 수 있습니다.

레퍼런스

  1. ^ a b Abdulkadiroğlu, Atila; Sönmez, Tayfun (1999-10-01). "House Allocation with Existing Tenants". Journal of Economic Theory. 88 (2): 233–260. doi:10.1006/jeth.1999.2553. ISSN 0022-0531.
  2. ^ Aziz, Haris; Keijzer, Bart de (2012). "Housing Markets with Indifferences: A Tale of Two Mechanisms". Proceedings of the AAAI Conference on Artificial Intelligence. 26 (1): 1249–1255. ISSN 2374-3468.
  3. ^ Roth, Alvin E. (1982-01-01). "Incentive compatibility in a market with indivisible goods". Economics Letters. 9 (2): 127–132. doi:10.1016/0165-1765(82)90003-9. ISSN 0165-1765.
  4. ^ Ergin, Haluk İ. (2000-08-01). "Consistency in house allocation problems". Journal of Mathematical Economics. 34 (1): 77–97. doi:10.1016/S0304-4068(99)00038-5. hdl:11693/18154. ISSN 0304-4068.
  5. ^ a b c Segal-Halevi, Erel; Aigner-Horev, Elad (2022). "Envy-free matchings in bipartite graphs and their applications to fair division". Information Sciences. 587: 164–187. arXiv:1901.09527. doi:10.1016/j.ins.2021.11.059. S2CID 170079201.
  6. ^ a b c d Kamiyama, Naoyuki; Manurangsi, Pasin; Suksompong, Warut (2021-07-01). "On the complexity of fair house allocation". Operations Research Letters. 49 (4): 572–577. arXiv:2106.06925. doi:10.1016/j.orl.2021.06.006. ISSN 0167-6377. S2CID 235422019.
  7. ^ Gan, Jiarui; Suksompong, Warut; Voudouris, Alexandros A. (2019-09-01). "Envy-freeness in house allocation problems". Mathematical Social Sciences. 101: 104–106. arXiv:1905.00468. doi:10.1016/j.mathsocsci.2019.07.005. ISSN 0165-4896. S2CID 143421680.
  8. ^ Beynier, Aurélie; Chevaleyre, Yann; Gourvès, Laurent; Harutyunyan, Ararat; Lesca, Julien; Maudet, Nicolas; Wilczynski, Anaëlle (2019-09-01). "Local envy-freeness in house allocation problems". Autonomous Agents and Multi-Agent Systems. 33 (5): 591–627. doi:10.1007/s10458-019-09417-x. ISSN 1573-7454. S2CID 51869987.