This is a good article. Click here for more information.

게일-샤플리 알고리즘

Gale–Shapley algorithm

게일-샤플리 알고리즘[1](Gale-Shapley algorithm)[1][2]은 수학, 경제학, 컴퓨터 과학에서 안정 매칭 문제의 해결책을 찾기 위한 알고리즘입니다. 이름은 데이비드 게일(David Gale)과 1962년에 출판한 로이드 샤플리(Lloyd Shapley)의 이름을 따서 지어졌지만, 1950년대 초부터 전국 주민 매칭 프로그램(National Resident Matching Program)에 사용되었습니다. 샤플리와 앨빈 E. Roth는 이 알고리즘을 포함한 연구로 2012년 노벨 경제학상을 수상했습니다.

안정 매칭 문제는 각 참가자의 선호도를 사용하여 두 가지 유형의 참가자를 동일한 수의 짝을 이루려고 합니다. 페어링은 안정적이어야 합니다. 어떤 참가자도 할당된 매치보다 서로를 선호해서는 안 됩니다. Gale-Shapley 알고리즘의 각 라운드에서 한 유형의 일치하지 않는 참가자는 선호도 목록에서 다음 참가자에게 일치를 제안합니다. 각 제안은 수신자가 현재 일치하는 것보다 선호하는 경우 수락됩니다. 결과적인 절차는 제안 참가자의 관점에서 진실된 메커니즘이며, 그들은 안정성과 일치하는 가장 선호되는 페어링을 받습니다. 반대로, 제안의 수신자는 가장 선호하지 않는 페어링을 받습니다. 알고리즘은 참가자 수에서 시간 2차적으로 실행되고 알고리즘에 대한 입력의 크기에서 선형적으로 실행되도록 구현될 수 있습니다.

안정적인 매칭 문제와 이를 해결하는 게일-샤플리 알고리즘은 미국 의대생들을 주거지에, 프랑스 대학 지원자들을 학교에 매칭하는 것을 포함하여 광범위한 실제 응용 프로그램을 가지고 있습니다. 자세한 내용은 안정적인 결혼 문제 § 응용 프로그램을 참조하십시오.

배경

주 기사: 안정매칭문제

가장 기본적인 형태로 안정적인 매칭 문제는 두 유형의 참가자(예를 들어 n명의 입사 지원자와 n명의 고용주)의 입력과 다른 유형의 참가자 중 누구와 매칭될 것인지에 대한 선호를 제공하는 각 참가자에 대한 순서를 취합니다. 일치는 한 유형의 각 참가자와 다른 유형의 참가자를 쌍으로 만듭니다. 다음과 같은 경우 일치가 안정적이지 않습니다.

  1. A가 이미 매칭된 요소보다 제2 매칭된 세트의 일부 주어진 요소 B를 선호하는 제1 매칭된 세트의 요소 A가 존재하고,
  2. B는 또한 B가 이미 일치하는 요소보다 A를 선호합니다.

즉, 두 참가자가 일치하는 파트너보다 서로를 선호하는 쌍(A, B)이 없을 때 일치가 안정적입니다. 그러한 쌍이 존재하는 경우, 이 쌍의 구성원들은 시스템을 떠나 서로 매칭되기를 선호하기 때문에 다른 참가자들과 매칭되지 않을 수 있습니다. 안정적인 매칭은 항상 존재하며, 게일-샤플리 알고리즘에 의해 해결된 알고리즘 문제는 하나를 찾는 것입니다.[3]

안정 매칭 문제는 남녀 간의 결혼이라는 비유를 사용하여 안정 결혼 문제라고도 불렸으며, 많은 자료에서 결혼 제안의 관점에서 게일-샤플리 알고리즘을 설명하고 있습니다. 그러나 이 은유는 성차별적이고 비현실적이라는 비판을 받아왔습니다: 알고리즘의 단계들은 전형적이거나 심지어 전형적인 인간의 행동을 정확하게 반영하지 못한다는 것입니다.[4][5]

해

게일-샤플리 알고리즘의 예를 보여주는 애니메이션

1962년 데이비드 게일과 로이드 샤플리는 각 유형의 동일한 수의 참가자에 대해 모든 쌍이 안정적인 일치를 항상 찾을 수 있다는 것을 증명했습니다. 그들은 그렇게 하기 위한 알고리즘을 제시했습니다.[6][7] 1984년 앨빈 E. Roth는 National Resident Matching Program에 의해 사용된 "보스턴 풀 알고리즘"과 본질적으로 동일한 알고리즘이 1950년대 초부터 이미 실용화되고 있다고 관찰했습니다.[1][8]

게일-샤플리 알고리즘은 여러 개의 "라운드"(또는 "반복")를 포함합니다. 구직자 및 고용주 측면에서 다음과 같이 표현할 수 있습니다.[9]

  • 매 라운드마다, 한 명 이상의 개방형 일자리를 가진 고용주들이 그들이 아직 제안하지 않은 지원자들 중에서 그들이 선호하는 지원자에게 일자리 제안을 합니다.
  • 제안을 받은 각 지원자는 (제안이 있는 경우) 현재 위치와 비교하여 제안을 평가합니다. 신청자가 아직 고용되지 않았거나, 현재 고용주보다 마음에 드는 고용주로부터 제안을 받은 경우, 그들은 최선의 새로운 제안을 수락하고 새로운 고용주와 일치하게 됩니다(이전 고용주가 자리를 비울 가능성이 있습니다). 그렇지 않으면, 그들은 새로운 제안을 거부합니다.
  • 이 과정은 모든 고용주가 자신의 직책을 채우거나 지원자 명단을 소진할 때까지 반복됩니다.

이행내역 및 시간분석

알고리즘을 효율적으로 구현하기 위해서는 각 고용주가 다음 지원자를 빠르게 찾을 수 있어야 하며, 각 지원자는 고용주를 빠르게 비교할 수 있어야 합니다. 한 가지 방법은 각 지원자와 각 고용주의 번호를 에서 n{\ 여기서 n은 고용주와 지원자의 수)로 지정하고 다음과 같은 데이터 구조를 저장하는 것입니다.[10]

  • 자리가 비어 있는 사용자 집합
  • 고용주가 지수화한 1차원 배열로, 고용주가 제안을 보낼 다음 신청자의 선호 지수를 지정하며, 처음에는 각 고용주에 대해 1.
  • 사용자에 의해 색인화된 2차원 배열과 i{\ i가 에서 n{\ n 사이이며 각 의 i 인 지원자의 이름을 기본 설정으로 지정합니다.
  • 지원자가 색인화한 1차원 배열로, 현재 고용주를 지정하며, 처음에는 실업자임을 나타내는 0과 같은 센티넬 값입니다.
  • 신청자와 고용주가 색인화한 2차원 배열로, 신청자의 선호도 목록에서 해당 고용주의 위치를 지정합니다.

이러한 데이터 구조를 설정하는 데 2) 시간이 걸립니다. 이러한 구조를 사용하면 자리가 비어 있는 고용주를 찾고, 해당 고용주로부터 다음 지원자에게 제안을 받고, 제안이 수락되는지 여부를 결정하고, 제안당 일정한 시간 내에 이러한 단계의 결과를 반영하도록 모든 데이터 구조를 업데이트할 수 있습니다. 알고리즘이 종료되면 각 지원자의 고용주 배열에서 결과 일치를 읽을 수 있습니다. 각 고용주가 제시할 제안이 소진되기 전에 O 제안이 있을 수 있으므로 총 시간은 2 O입니다[10]

이 시간 바운드는 참가자 수에서 2차이지만 입력의 크기 측면에서 측정할 때 선형 시간으로 간주될 수 있습니다 O( {\ O의 선호도 두 행렬입니다[11]

정확성 보장

이 알고리즘은 다음을 보장합니다.

모든 사람이 일치합니다.
결국, 일치하지 않는 지원자와 고용주는 있을 수 없습니다. 프로세스가 끝날 때 일치하지 않는 고용주가 모든 지원자에게 제안을 했을 것입니다. 그러나 제안을 받은 지원자는 나머지 과정에서 고용 상태가 유지되므로 실업 지원자는 있을 수 없습니다. 지원자 수와 구인인원이 동일하기 때문에 남은 자리도 없을 수 있습니다.[9]
경기는 안정적입니다.
어떤 지원자 X와 고용주 Y도 자신들의 최종 대결보다 서로를 더 선호할 수 없습니다. 만약 Y가 X에게 제안을 한다면, X는 더 좋은 제안을 받은 후에만 Y를 거절할 것이므로, X는 Y를 그들의 마지막 대결보다 더 선호할 수 없습니다. 그리고 Y가 자신의 선호도 목록에서 X에 도달하기 전에 제안을 중단한다면, Y는 자신의 최종 대결보다 X를 더 선호할 수 없습니다. 어느 경우든 X와 Y는 불안정한 쌍을 이루지 않습니다.[9]

솔루션의 최적성

본문 : 안정적인 정합의 격자

동일한 선호 시스템에 대해 많은 안정적인 일치가 있을 수 있습니다. 그러면 Gale-Shapley 알고리즘에 의해 어떤 매칭이 반환됩니까?라는 질문이 제기됩니다. 지원자, 고용주 또는 중급자 중 어느 쪽이 더 잘 어울리나요? 밝혀진 바에 따르면, 고용주가 지원자에게 제안을 하는 게일-샤플리 알고리즘은 항상 동일한 안정 매칭을 산출합니다(직 제안이 이루어진 순서에 관계없이). 그리고 그 선택은 모든 고용주에게 최고이고 모든 안정 매칭 중 모든 지원자에게 최악인 안정 매칭입니다.[9]

알고리즘의 반대 형태로, 각 라운드는 실업자 지원자가 선호하는 고용주에게 단일 입사 지원서를 작성하고 고용주는 지원서를 수락하거나(기존 직원을 해고할 가능성이 있음) 거부하는 방식으로 구성됩니다. 이는 모든 안정적인 매칭 중 모든 지원자에게 가장 적합하고 모든 고용주에게 가장 적합하지 않은 매칭을 생성합니다. 이 두 개의 매칭은 안정적인 매칭의 격자의 상단 요소와 하단 요소입니다.[12]

알고리즘의 두 가지 형태 모두에서 한 그룹의 참가자가 일치를 제안하고, 다른 그룹은 각 제안을 수락할지 또는 거절할지를 결정합니다. 매칭은 항상 제안을 하는 그룹에 가장 적합하고, 각 제안을 처리하는 방법을 결정하는 그룹에 가장 적합합니다.[12]

전략적 고려사항

제안 측의 관점에서 보면 게일-샤플리 알고리즘은 진실한 메커니즘입니다. 이는 어떤 제안자도 자신의 선호도를 잘못 표현하여 더 나은 매칭을 얻을 수 없음을 의미합니다. 게다가, 게일-샤플리 알고리즘은 제안자들에게 심지어 그룹 전략적 증거입니다. 즉, 제안자들의 어떤 연합도 그들의 선호도에 대한 잘못된 표현을 조정하여 연합의 모든 제안자들이 엄격하게 더 잘 살게 할 수 없습니다.[13] 그러나 일부 연합은 일부 제안자가 더 부유하고 다른 연합은 동일한 파트너를 유지하도록 자신의 선호도를 잘못 표현할 수 있습니다.[14]

Gale-Shapley 알고리즘은 제안하지 않은 참가자에게 진실이 아닙니다. 각각은 자신의 선호도를 잘못 표현하고 더 나은 일치를 얻을 수 있습니다.[15] 특정한 조작 형태는 잘라내기입니다: 맨 위의 대안만 제시하고 맨 아래 대안은 전혀 허용되지 않음을 의미합니다. 완전한 정보 하에서는 절단 전략의 형태에 대한 잘못된 표현을 고려하기에 충분합니다. 그러나 잘못된 표현을 성공시키려면 다른 에이전트의 기본 설정에 대한 지식이 필요합니다. 이러한 지식이 없으면 잘못된 표현은 에이전트에게 더 나쁜 할당을 줄 수 있습니다. 게다가, 에이전트가 최종 매칭을 본 후에도, 그들은 나중에 더 나은 결과를 보장할 전략을 추론할 수 없습니다. 이것은 게일-샤플리 알고리즘을 후회 없는 진실 말하기 메커니즘으로 만듭니다. 게다가 게일-샤플리 알고리즘에서 진실 말하기는 후회 없는 유일한 전략입니다. 게일-샤플리 알고리즘은 분위 안정 매칭 메커니즘 클래스에서 유일하게 후회 없는 메커니즘입니다.[16]

일반화

그 문제에 대한 그들의 원래 연구에서 게일과 샤플리는 안정적인 매칭 문제의 보다 일반적인 형태를 대학과 대학 입학에 적합하다고 생각했습니다. 이 문제는 각 대학이나 단과대학마다 정원이 있을 수 있고, 입학을 신청하는 학생의 수가 정원의 합과 다를 수 있어 반드시 어떤 학생들은 일치하지 않거나 어떤 학생들은 정원이 채우지 못한 상태로 남을 수 있습니다. 추가적으로, 선호도 목록이 불완전할 수 있습니다: 대학이 학생을 명단에서 누락시킨다면, 그것은 그 학생을 입학시키는 것보다 정원을 채우지 않는 것을 선호하고, 학생이 명단에서 대학을 누락시킨다면, 그 대학에 가는 것보다 입학하지 않는 것을 선호한다는 것을 의미합니다. 그럼에도 불구하고 이 보다 일반적인 문제에 대해 안정적인 매칭을 정의하고, 안정적인 매칭이 항상 존재한다는 것을 증명하고, 동일한 알고리즘을 적용하여 하나를 찾는 것이 가능합니다.[6]

게일-샤플리 알고리즘의 한 형태는 컴퓨터에서 계산되는 것이 아니라 실제 프로토콜을 통해 수행되며, 파쿠업 시스템을 통해 2018년부터 프랑스에서 고등교육 입학을 조정하는 데 사용되었습니다. 이 과정에서, 개학 전 여름 동안 지원자들은 입학 제안을 받고, 새로운 제안을 받아들일지의 여부를 매 과정마다 선택해야 합니다(만약 그렇다면, 그들이 수락한 이전 제안을 거절할지도 모릅니다). 이 방법은 문제를 해결하는 것이 안정적인 일치 문제가 아닌 추가적인 제약으로 인해 복잡합니다. 학생들이 프로세스를 시작할 때 자신의 선호도에 전념할 필요가 없고, 오히려 받은 제안 간의 정면 비교를 기반으로 알고리즘이 진행됨에 따라 자신의 선호도를 결정할 수 있다는 장점이 있습니다. 이 과정은 적은 수의 제안을 수행하여 개학일 이전에 종료되도록 하는 것이 중요하지만 이론적으로는 높은 수의 제안이 발생할 수 있지만 실제로는 발생하지 않는 경향이 있습니다.[17] 이론적으로 Gale-Shapley 알고리즘을 조기에 종료해야 하는 경우, 모든 빈 자리가 새로운 제안을 하는 소수의 라운드 후에도 일치하는 참가자와 불안정한 쌍의 비율이 높은 일치를 생성하는 것으로 나타났습니다.[18]

인지도

샤플리와 로스는 "안정적 배분 이론과 시장 설계의 실천"으로 2012년 노벨 경제학상을 수상했습니다. 게일은 2008년에 사망했기 때문에 그 상을 받을 자격이 없었습니다.[19]

참고 항목

참고문헌

  1. ^ a b c Roth, Alvin E. (February 2003). "The origins, history, and design of the resident match". JAMA. 289 (7): 909–912. doi:10.1001/jama.289.7.909.
  2. ^ Carter, Michael W.; Price, Camille C. (2000). Operations Research: A Practical Introduction. CRC Press. p. 102. ISBN 9780849322563.
  3. ^ Gusfield, Dan; Irving, Robert W. (1989). The Stable Marriage Problem: Structure and Algorithms. MIT Press. p. 6. ISBN 9780262515528.
  4. ^ Wagner, Roy (April 2009). "Mathematical marriages: Intercourse between mathematics and semiotic choice". Social Studies of Science. 39 (2): 289–308. doi:10.1177/0306312708099443. hdl:20.500.11850/121579.
  5. ^ Giagkousi, Kyriaki (March 2021). Gender and Computing Algorithms: The case of Stable Matching (PDF) (Master's thesis). National and Kapodistrian University of Athens, Department of History and Philosophy of Science and Department of Informatics and Telecommunications. Retrieved 2023-12-20.
  6. ^ a b Gale, D.; Shapley, L. S. (1962). "College admissions and the stability of marriage". The American Mathematical Monthly. 69 (1): 9–14. doi:10.2307/2312726. JSTOR 2312726. Archived from the original on 2017-09-25. Retrieved 2019-11-20.
  7. ^ Mairson, Harry (1992). "The stable marriage problem". The Brandeis Review. 12.
  8. ^ Bergstrom, Theodore C. (June 1992). "Review of Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis by A. E. Roth and M. A. O. Sotomayor". Journal of Economic Literature. 30 (2): 896–898. JSTOR 2727713.
  9. ^ a b c d Erickson, Jeff (June 2019). "4.5 Stable matching" (PDF). Algorithms. University of Illinois. pp. 170–176. Retrieved 2023-12-19.
  10. ^ a b Kleinberg, Jon; Tardos, Éva (2006). "2.3 Implementing the stable matching algorithm using lists and arrays". Algorithm Design. Addison-Wesley. pp. 42–47.
  11. ^ Gusfield & Irving (1989), p. 182.
  12. ^ a b Knuth, Donald E. (1976). Mariages stables et leurs relations avec d'autres problèmes combinatoires (PDF) (in French). Montréal, Quebec: Les Presses de l'Université de Montréal. ISBN 0-8405-0342-3. MR 0488980. 특히 문제 6, 페이지 87-94를 참조하십시오.
  13. ^ Dubins, L. E.; Freedman, D. A. (1981). "Machiavelli and the Gale–Shapley algorithm". The American Mathematical Monthly. 88 (7): 485–494. doi:10.2307/2321753. JSTOR 2321753. MR 0628016.
  14. ^ Huang, Chien-Chung (2006). "Cheating by men in the Gale-Shapley stable matching algorithm". In Azar, Yossi; Erlebach, Thomas (eds.). Algorithms – ESA 2006, 14th Annual European Symposium, Zurich, Switzerland, September 11–13, 2006, Proceedings. Lecture Notes in Computer Science. Vol. 4168. Springer. pp. 418–431. doi:10.1007/11841036_39. MR 2347162.
  15. ^ Gonczarowski, Yannai A.; Friedgut, Ehud (April 2013). "Sisterhood in the Gale–Shapley matching algorithm". Electronic Journal of Combinatorics. 20 (2): P12:1–P12:18. arXiv:1104.2217. doi:10.37236/3267.
  16. ^ Fernandez, Marcelo Ariel (July 31, 2020). "Deferred acceptance and regret-free truth-telling" (Working paper). Johns Hopkins University Department of Economics.
  17. ^ Mathieu, Claire (2018). "College admission algorithms in the real world" (Invited lecture at the European Symposium of Algorithms). Aalto University.
  18. ^ Floréen, Patrik; Kaski, Petteri; Polishchuk, Valentin; Suomela, Jukka (August 2009). "Almost stable matchings by truncating the Gale–Shapley algorithm". Algorithmica. 58 (1): 102–118. arXiv:0812.4893. doi:10.1007/s00453-009-9353-9.
  19. ^ Bhattacharjee, Yudhijit (October 15, 2012). "Economics Nobel honors matchmaking finesse". Science. 338 (6105): 314. doi:10.1126/science.338.6105.314. PMID 23087221.