Comment on 'What's the Matter with Tie-Breaking: Improving Efficiency in School Choice'

이 논문은 Erdil & Ergin (2008) 의 학교 선택 연구에서 사용된 코드의 버그를 수정하여 불안정한 매칭 문제를 해결하고, 수정된 실험 결과에 따라 개선된 학생의 비율은 약간 감소하지만 순위 개선 폭은 더 크다는 사실을 규명했습니다.

핵심

이 논문은 학교 입학 배정 시스템에서 발견된 작은 '버그(오류)에 대해 이야기합니다. 마치 정교한 레고 조립 지시서에 실수로 한 줄이 잘못 적혀 있어서, 완제품이 의도한 대로 조립되지 않았던 상황을 비유로 들어 설명해 드릴게요.

1. 배경: 학교 입학 배정 시스템은 어떻게 작동할까요?

학교 입학 (특히 공립학교) 은 단순히 "선호하는 학교"만 고르면 되는 게 아닙니다. 학생들의 선호도와 학교의 우선순위 (예: 거주지, 형제자매 등) 를 모두 고려해야 합니다.

• DA(Deferred Acceptance)라는 알고리즘이 기본적으로 쓰이는데, 이는 안정적이지만 '최적'은 아닐 수 있습니다.
• **에르딜과 에르긴 **(2008)이라는 연구자들은 "안정적인 개선 사이클"이라는 추가 공식을 만들어, DA 로 배정된 학생들 중 더 좋은 학교로 갈 수 있는 기회를 더 많이 주겠다고 제안했습니다. 이는 마치 "이미 배정받았지만, 서로 교환하면 모두 더 행복해지는 경우"를 찾아내는 과정입니다.

2. 문제: "완벽해 보이지만, 사실은 틀린" 코드

에르딜과 에르긴은 이 이론을 컴퓨터 코드로 구현했고, 전 세계 학계는 이 결과를 믿고 연구했습니다. 하지만 토메 데뮬레메스터라는 연구자가 이 코드를 다시 확인하다가 치명적인 오류를 발견했습니다.

🍕 피자 배달 비유로 이해하기:
가상 상황을 상상해 보세요.

• 학생 A는 처음에 피자 가게 1 번에 배정받았습니다.
• 알고리즘이 작동해서 학생 A 는 더 좋은 피자 가게 2 번으로 가게 되었습니다. (이게 1 단계 개선)
• 하지만 학생 A 는 피자 가게 2 번보다 피자 가게 3 번이 더 좋습니다. (그런데 3 번은 2 번보다 나쁘지만, 원래 1 번보다는 좋습니다.)

여기서 오류가 발생합니다:
코드는 학생 A 가 2 번 가게로 갔으니, "이 학생은 2 번 가게보다 좋은 곳을 원하지 않는다"고 착각하고, 2 번 가게에서 학생 A 의 이름을 지웠습니다.
하지만 코드가 잊어버린 것은, 학생 A 가 여전히 3 번 가게를 원할 수 있다는 사실입니다.

• 결과: 코드는 학생 A 를 3 번 가게에 다시 배정해 버립니다.
• 문제: 학생 A 는 2 번 가게가 3 번 가게보다 더 좋았는데, 3 번 가게로 다시 가게 된 것입니다. 이는 학생 A 가 더 불행해지는 결과를 낳고, 시스템 전체가 불안정해집니다. (누군가는 "나 2 번 가게가 더 좋았는데 왜 3 번으로 보냈어?"라고 항의하게 됩니다.)

3. 해결책: 코드의 작은 수정

연구자는 이 오류의 원인을 정확히 짚어냈습니다. 학생이 더 좋은 학교로 이동할 때, 이전 학교보다 나쁘지만 새로운 학교보다는 좋은 모든 학교에 대한 신청 기록을 지워주지 않았기 때문입니다.

그는 코드를 아주 간단하게 수정했습니다.

"학생이 A 학교에서 B 학교로 이동했다면, B 학교보다 나쁘지만 A 학교보다는 좋은 모든 중간 학교에 대한 신청도 함께 취소해라."

이 작은 수정으로 시스템이 다시 정상적으로 작동하게 되었습니다.

4. 수정 후의 결과: "작은 실수, 큰 영향"

이 오류가 실제 데이터에 어떤 영향을 미쳤는지 다시 계산해 보니 흥미로운 결과가 나왔습니다.

• 불안정한 배정: 원래 코드에서는 아주 드물게 (약 25,000 건 중 2 건) 불안정한 결과가 나왔습니다. 하지만 대부분의 경우, 코드가 다른 학생에게 다른 학교를 배정했습니다.
• 학생들의 만족도:
  • 더 좋은 학교를 얻는 학생 수: 원래 보고된 것보다 조금 줄어듭니다. (과장되었던 숫자가 정정됨)
  • 하지만, 개선된 학생들의 만족도: 그 학생들이 얻은 학교의 순위는 원래 보고된 것보다 훨씬 더 좋아졌습니다. (적은 수의 학생이 더 큰 혜택을 봄)
• 전반적인 결론: 전체적으로 학생들의 평균 만족도는 원래 알고리즘보다 여전히 높지만, 에르딜과 에르긴이 주장했던 것만큼 "대박"은 아니라는 것입니다.

5. 요약: 이 논문이 우리에게 주는 메시지

이 논문은 "에르딜과 에르긴의 이론이 틀렸다"는 것이 아니라, **"그들의 컴퓨터 코드가 약간의 실수를 해서, 이론의 효과를 약간 과장해서 보여줬다"**는 것을 밝힌 것입니다.

• 핵심: 큰 이론 (학교 배정 시스템의 개선) 은 여전히 유효합니다.
• 교훈: 과학적 연구에서 **코드 **(프로그램)는 매우 중요합니다. 아주 작은 실수 (한 줄의 코드) 가 전체 결과의 해석을 바꿀 수 있습니다.
• 미래: 이 논문은 수정된 코드를 공개하여, 앞으로의 연구자들이 더 정확한 데이터를 바탕으로 학교 배정 시스템을 개선할 수 있도록 도와줍니다.

결국, 이 논문은 과학의 자기 수정 능력을 보여주는 좋은 사례입니다. 작은 실수를 찾아내고 고침으로써, 우리가 학교 입학 시스템을 더 공정하고 효율적으로 만들 수 있는 길을 다시 한번 다듬어 준 것입니다.

기술 요약

논문 요약: 학교 선택 (School Choice) 에서의 안정적 개선 사이클 (Stable Improvement Cycles) 알고리즘 버그 수정

1. 문제 제기 (Problem)

이 논문은 Erdil 과 Ergin (2008) 의 seminal 연구인 "School Choice with Ties"에서 제안된 안정적 개선 사이클 (Stable Improvement Cycles) 알고리즘의 구현 코드에 존재하는 치명적인 버그를 발견하고 이를 수정하는 것을 목적으로 합니다.

• 배경: 학교 선택 문제에서 학생들의 선호도가 동점 (tie) 을 가질 때, 우선순위 (priority) 를 무작위로 깨뜨리는 방식은 비효율적인 매칭을 초래할 수 있습니다. Erdil 과 Ergin (2008) 은 동점 처리 후에도 '안정적 개선 사이클'을 통해 더 효율적이면서도 안정성을 유지하는 매칭을 찾을 수 있음을 이론적으로 증명했습니다.
• 발견된 문제: Erdil 과 Ergin (2008) 이 사용한 계산 실험 코드가 실제로는 **불안정 매칭 (unstable matching)**을 생성하는 경우가 있었습니다. 즉, 알고리즘이 이론적으로 보장된 '약한 안정성 (weak stability)' 조건을 위반하는 결과를 도출했습니다.

2. 방법론 및 버그 분석 (Methodology & Bug Analysis)

저자는 구체적인 반례 (Counterexample) 를 통해 버그의 원인을 규명하고, 이를 수정한 코드를 제시했습니다.

• 버그의 원인:

  • 알고리즘은 학생이 현재 배정된 학교보다 선호하는 학교로 이동할 때, 해당 학생이 이전 학교보다 선호하지만 새로 배정된 학교보다는 덜 선호하는 중간 순위 학교들에 대한 제안 (proposals) 을 제대로 제거하지 못했습니다.
  • 구체적으로, 학생 $i$가 학교 $x$에서 학교 $y$ ($y \succ_i x$) 로 이동했을 때, 코드는 학생 $i$를 $y$에 대한 우선순위 목록에서 제거하지만, $x$와 $y$ 사이에 있는 학교 $z$ ($x \succ_i z \succ_i y$) 에 대한 학생 $i$의 제안은 제거하지 않았습니다.
  • 이로 인해 학생 $i$는 이미 더 나은 학교 ($y$) 를 얻었음에도 불구하고, 덜 선호하는 학교 ($z$) 와의 사이클에 다시 참여하게 되어, 최종적으로 더 나쁜 학교로 이동하거나 불안정한 매칭이 생성되는 오류가 발생했습니다.

• 수정 방안:

  • improve_allocations 함수 내에서 학생이 새로운 학교로 이동할 때, 새로운 학교와 이전 학교 사이의 모든 선호도 순위에 해당하는 학교들에 대한 학생의 제안 목록을 명시적으로 제거하는 로직을 추가했습니다.
  • 수정된 코드는 GitHub 를 통해 공개되었습니다.

3. 주요 기여 (Key Contributions)

1. 버그 식별 및 수정: Erdil 과 Ergin (2008) 의 코드가 불안정 매칭을 생성할 수 있음을 증명하는 구체적인 반례를 제시하고, 이를 해결하는 정확한 알고리즘 구현을 제공합니다.
2. 이론적 무결성 유지: 이 버그는 Erdil 과 Ergin (2008) 의 이론적 발견 (이론적 증명) 에는 영향을 주지 않습니다. 즉, 안정적 개선 사이클이 존재한다는 이론적 사실은 변함이 없으며, 단지 기존 코드의 구현 오류를 수정한 것입니다.
3. 계산 결과의 정밀화: 수정된 코드를 사용하여 Erdil 과 Ergin (2008) 의 계산 실험을 재현하여, 버그가 실제 결과에 미친 영향을 정량적으로 분석했습니다.

4. 결과 (Results)

저자는 1,000 명의 학생과 20 개의 학교로 구성된 200 개의 시나리오 (총 25,200 회 시뮬레이션) 를 통해 원본 코드와 수정된 코드를 비교했습니다.

• 불안정성 발생률: 원본 코드는 25,200 건 중 2 건에서 불안정 매칭을 생성했습니다.
• 매칭 결과의 차이: 안정적 개선 사이클 알고리즘이 기존 DA (Deferred Acceptance) 방식보다 개선을 보일 수 있었던 사례 중 **90.6%**에서 수정된 코드가 원본 코드와 다른 매칭 결과를 도출했습니다.
• 성능 지표 변화:
  • 개선된 학생의 비율: 원본 보고서보다 약간 감소했습니다. (버그로 인해 일부 학생이 부당하게 개선된 것으로 잘못 계산됨)
  • 평균 순위 개선폭: 원본 보고서보다 더 크게 증가했습니다. (버그로 인해 일부 학생이 더 나쁜 학교로 이동하거나, 개선의 질이 낮게 평가되었으나, 수정 후 실제 개선 효과가 더 뚜렷하게 나타남)
  • 전체 평균 순위: 수정된 코드를 적용했을 때, 학생들의 평균 순위 (average rank) 가 원본 코드보다 더 낮아졌습니다 (즉, 더 선호하는 학교에 배정됨).
  • 최대 개선 효과: $\alpha$ (선호도 상관관계) 와 $\beta$ (지리적 근접성 민감도) 파라미터에 따라 평균 순위 개선 폭이 원본 대비 최대 약 **5%**까지 증가했습니다.

5. 의의 및 결론 (Significance)

• 실증 연구의 신뢰성 확보: 학교 선택 및 매칭 이론 분야에서 널리 인용되고 있는 Erdil 과 Ergin (2008) 의 계산 실험 결과가 버그로 인해 왜곡되었음을 시정함으로써, 해당 분야의 후속 연구들이 더 정확한 데이터를 바탕으로 진행될 수 있게 했습니다.
• 정책적 함의: 버그 수정 후에도 Erdil 과 Ergin (2008) 의 핵심 통찰 (stable improvement cycles를 통해 효율성을 높일 수 있다는 점) 은 유효함이 확인되었습니다. 다만, 실제 정책 설계 시 예상되는 효율성 개선 폭이 기존 보고서보다 다소 작을 수 있으나, 개선된 학생들의 만족도 (순위) 는 더 높게 개선될 수 있음을 시사합니다.
• 코드 재현성: 저자가 공개한 수정된 코드는 향후 관련 연구자들이 안정적 개선 사이클을 올바르게 구현하고 재현하는 데 중요한 기준이 될 것입니다.

결론적으로, 이 논문은 기존 연구의 이론적 틀을 부정하지 않으면서, 구현 단계의 오류를 수정하여 계산 결과의 정확성을 높이고, 학교 선택 시스템의 효율성 개선 효과를 더 정밀하게 평가할 수 있는 기반을 마련했습니다.