Asymptotic Equivalence of Immediate and Deferred Acceptance

당신이 모든 아이가 학교에 자리를 잡아야 하지만, 학생 수와 학교의 좌석 수가 정확히 일치하는 북적이는 도시의 시장이라고 상상해 보십시오. 문제는 단순히 '어떤' 자리를 찾는 것이 아닙니다. 바로 '적절한' 자리를 찾는 것입니다. 모든 가족은 "나의 꿈의 학교"부터 "정 안 되면 여기라도 가야지"까지, 자신이 좋아하는 학교 목록을 가지고 있습니다. 도시에는 규칙도 있습니다. 예를 들어, 근처에 사는 아이나 이미 형제자매가 다니고 있는 아이에게 우선권을 주는 학교가 있을 수 있습니다. 결정권자들의 큰 고민은 이것입니다: 아이들을 어떻게 매칭해야 모두가 최대한 행복할 수 있을까?

수십 년 동안 전문가들은 이 문제를 해결하는 두 가지 주요 방식에 대해 논쟁해 왔습니다. 첫 번째는 **지연 수락(Deferred Acceptance, DA)**이라고 불립니다. 이것은 느리고 신중한 춤과 같습니다. 학생들은 자신의 최선책에 지원합니다. 학교는 선호하는 지원자를 붙잡아 두되, 영원히 "예"라고 말하지는 않고 그저 "아마도"라고 말합니다. 더 나은 학생이 나중에 나타나면 학교는 그 학생으로 교체할 수 있습니다. 이 과정은 모두가 정착될 때까지 반복됩니다. 이 방식은 공정하고 속임수가 불가능하기로 유명하지만, 다소 복잡하고 비효율적일 수 있습니다.

두 번째 방법은 즉시 수락(Immediate Acceptance, IA), 흔히 "보스턴 메커니즘"이라 불리는 방식입니다. 이것은 마치 정신없는 경주와 같습니다. 학생들은 줄을 서서 자신의 최선책에 지원합니다. 학교는 줄을 보고 우선순위에 따라 가장 선호하는 학생을 뽑아 즉시 "당신은 합격입니다!"라고 말합니다. 만약 당신이 탈락한다면, 당신은 즉시 두 번째 선택지로 달려가야 합니다. 문제는 만약 당신이 최선책에 늦게 지원한다면, 당신이 그 학교를 아무리 간절히 원하더라도 더 높은 우선순위를 가진 사람이 먼저 지원했을 경우 자리를 잃을 수 있다는 점입니다. 이 때문에 IA는 종-종 불공정하거나 조작하기 쉽다는 비판을 받습니다. 그러나 IA에는 강력한 초능력이 하나 있습니다. 만약 모든 사람이 자신이 원하는 것을 진실하게 말한다면, IA는 누군가를 불행하게 만들지 않고서는 아무도 더 행복하게 만들 수 없는 결과를 보장한다는 것입니다. 이를 "파레토 효율성(Pareto efficiency)"이라고 합니다.

여기 백만 달러짜리 질문이 있습니다: IA의 초능력이 실제로 큰 차이를 만들어낼까요? IA가 학생들을 그들이 훨씬 더 좋아하는 학교에 들어가게 할까요, 아니면 그 차이가 아주 작고 보이지 않는 점 수준에 불과할까요? 이것이 바로 조수에 오르테가(Josué Ortega)가 그의 논문에서 다루는 퍼즐입니다.

---

위대한 학교 경주: 두 메커니즘의 이야기

퀸즈 벨파스트 대학교의 연구자인 조수에 오르테가는 이 논쟁을 종결짓기 위해 거대한 사고 실험을 실행하기로 했습니다. 그는 역사와 정치가 뒤섞인 실제 도시를 관찰하는 대신, 모든 학생의 선호 학교 목록이 마치 이름표를 뽑는 것처럼 완전히 무작위로 결정되는 "무작위 시장(random market)"을 상상했습니다. 이 세상에는 $n$명의 학생과 $n$개의 학교가 있습니다.

오르테가는 "평균 순위"를 측정하고자 했습니다. 모든 학생이 배정받은 학교가 자신의 목록에서 몇 번째에 있었는지에 따라 점수를 받는다고 상상해 보십시오. 만약 당신이 1순위 학교에 배정받았다면 순위는 1입니다. 만약 100순위 학교에 배정받았다면 순위는 100입니다. 목표는 이 숫자를 최대한 낮게 유지하는 것입니다.

오랫동안 우리는 느리고 신중한 춤(DA)에 대한 답을 알고 있었습니다. 1970년대에 수학자들은 무작위 시장에서 평균적인 학생이 약 $\log n$ (n의 로그 값) 정도의 순위인 학교에 배정된다는 것을 밝혀냈습니다. 학생이 1,000명이면 평균 순위는 약 7입니다. 학생이 100,000명이면 약 11입니다. 숫자가 늘어나긴 하지만, 매우 느리게 증가합니다.

그렇다면 정신없는 경주(IA)는 어떨까요? IA는 작동 방식이 다르기 때문에—지원 순서가 중요하고 학생들이 늦게 지원했다는 이유로 탈락할 수 있기 때문에—수학자들은 이것이 훨씬 더 복잡할 것이라고 생각했습니다. 일부 컴퓨터 과학자들이 이를 해결하려고 시도했지만, 그들은 특정 순위를 얻을 확률만을 알아낼 수 있었을 뿐, 모두의 평균 순위는 알아내지 못했습니다. 그들은 IA 역시 로그 함수 형태를 띨 것이라고 추측했지만, 아무도 이를 증명하지 못했습니다.

"쿠폰 수집가"의 비밀

오르테가의 돌파구는 두 메커니즘이 겉보기에는 완전히 달라 보이지만, 비밀리에 같은 게임을 하고 있다는 사실을 깨달은 데 있었습니다. 그는 이 현상을 설명하기 위해 **쿠폰 수집가 문제(Coupon Collector Problem)**라는 고전적인 퍼즐을 사용했습니다.

당신이 $n$ 종류의 서로 다른 트레이딩 카드를 모두 모으려고 한다고 상상해 보십시오. 시리얼 상자를 살 때마다 무작위 카드 한 장을 얻습니다. 모든 카드를 적어도 한 번씩 다 모으려면 총 몇 상자의 시리얼을 사야 할까요?
정답은 대략 $n \times \log n$입니다. 마지막 몇 장의 희귀한 카드를 찾기 위해 많은 양의 상자를 사게 됩니다.

오르테가는 **지연 수락(DA)**이 정확히 이와 같다는 것을 보여주었습니다. 학생들은 모든 학교가 적어도 한 번의 지원을 받을 때까지 계속해서 지원합니다. 모든 사람이 제출한 총 지원 횟수는 대략 쿠폰을 모두 모으기 위해 필요한 시리얼 상자의 수와 비슷합니다. 따라서 평균적인 학생이 하는 지원 횟수는 약 $\log n$이며, 그들의 최종 학교 순위 또한 약 $\log n$이 됩니다.

그런 다음, 오르테가는 시선을 **즉시 수락(IA)**으로 돌렸습니다. 처음에는 학생들이 즉시 계속 지원할 수 없고 "라운드"가 끝나기를 기다려야 하기 때문에 다르게 보였습니다. 하지만 오르테가는 과정을 특정한 방식으로 바라본다면, 이 또한 역시 쿠폰 수집가와 같다는 것을 깨달았습니다.

그는 약간 "건망증이 있는" 버전의 게임을 상상했습니다. 학생이 이미 시도했던 학교를 다시 선택하더라도 계속 무작위로 학교를 고른다고 가정해 봅시다. 만약 이미 시도했던 학교를 고르면, 그 선택은 그냥 무시됩니다(이는 "낭비된" 시도가 됩니다). 오르테가는 이러한 낭비된 시도가 있더라도, 모든 학교를 채우는 데 필요한 실제 지원 횟수는 여전히 쿠폰 수집 문제와 거의 동일하다는 것을 증명했습니다.

대반전

결론은 이렇습니다: 두 방법의 차이는 놀라울 정도로 작습니다.

오르테가는 시장이 거대해짐에 따라(즉, $n$이 매우 커짐에 따라), 즉시 수락(IA) 시스템에서 학생들의 평균 순위 또한 약 $\log n$이라는 것을 수학적으로 증명했습니다.

이는 IA가 (모두가 진실을 말한다는 전제하에) "파레토 효율적"임에도 불구하고, 느린 DA 방식에 비해 학생들이 더 선호하는 학교에 들어가는 데 있어 엄청난 이점을 주지는 않는다는 것을 의미합니다. 즉, "1차적(first-order)" 개선, 즉 눈에 띄는 큰 이득은 존재하지 않습니다.

오르테가의 논문은 대규모 무작위 시장에서 IA가 학생들의 결과를 획기적으로 개선하는 마법의 탄환이라는 생각을 명시적으로 부정합니다. IA가 특정 작은 시나리오나 특정 우선순위 규칙 하에서 약간 더 나을 수는 있지만, 일반적인 경우 두 메커니즘은 **점근적으로 동일(asymptotically equivalent)**하다는 것을 논문은 보여줍니다. 둘 다 시장 규모의 로그 함수 정도의 순위로 학생들을 인도합니다.

이것이 왜 중요한가

이 결과는 "즉시 수락" 시스템의 팬들에게는 다소 실망스러운 소식이겠지만, 수학계에는 반가운 소식입니다. 이는 IA의 "파레토 효율성"이 평균적인 행복 측면에서는 일종의 신기루에 불과하다는 것을 알려줍니다. 불공정하고 조작하기 쉽다고 비판받는 메커니즘이, 공정하고 속이기 어려운 메커니즘보다 실제로 더 나은 평균적 결과를 가져다주지는 않는다는 것입니다.

오르테가의 연구는 이 발견을 다른 변형 모델에도 확장합니다. 학교가 여러 개의 좌석을 가지고 있든(일대다 매칭), 혹은 학생들이 가득 찬 학교를 건너뛸 수 있든(skips가 포함된 IA 변형), 결과는 동일합니다: 평균 순위는 여전히 $\log n$ 근처에 머뭅니다.

그러니 다음에 누군가 "보스턴 메커니즘"이 더 효율적이기 때문에 반드시 사용해야 한다고 주장한다면, 당신은 미소를 지으며 이렇게 말할 수 있을 것입니다. "글쎄요, 효율적일지는 몰라도, 평균적으로 다른 방식보다 아이들을 더 좋은 학교에 보내주는 것은 아니랍니다." 학교 선택이라는 거대한 경주에서, 두 주자는 거의 똑같은 시간에 결승선을 통과하고 있습니다.