Justifiable Priority Violations

이 논문은 기수 배정 (DA) 메커니즘의 비효율성을 해결하기 위해 사전 동의에 의존하지 않고, 학생의 직접적 이익이나 파레토 우월 배정 하에서의 개선 불가능성을 기준으로 우선순위 위반의 정당성을 내생적으로 정의하여 새로운 알고리즘을 제안하고, 기존 동의 기반 접근법과 비교하여 그 한계와 실용성을 분석합니다.

핵심

🏫 배경: "기다림의 순서"와 "공정한 배정"의 딜레마

학교 입학 시스템을 생각해보세요. 보통은 **우선순위 (Priority)**가 중요합니다. 예를 들어, "동네에 사는 아이"나 "형제가 다니는 아이"에게 우선권이 주어집니다.
기존의 표준 시스템인 DA(Deferred Acceptance, 지연 수용) 알고리즘은 이 우선순위를 철저히 지키면서 학생들을 배정합니다. 하지만 이 시스템은 때때로 비효율적일 수 있습니다.

• 상황: A 학생은 B 학교를 매우 원하지만, 우선순위가 낮아 C 학교에 갔습니다. 반면, D 학생은 B 학교를 원하지 않았는데, 우선순위가 높아 B 학교에 갔습니다.
• 문제: A 와 D 가 서로 자리를 바꾸면 둘 다 더 좋아지는데, 시스템이 이를 막고 있습니다.

이 비효율성을 해결하려면 우선순위를 어겨야 (Priority Violation) 합니다. 하지만 "누구의 우선순위를 어겨도 될까?"가 핵심 질문입니다.

---

💡 핵심 아이디어: "합리적인 우선순위 위반" (Justifiable Priority Violations)

저자들은 **"누가 이득을 보느냐"**에 따라 우선순위 위반을 허용할지 결정하는 새로운 기준을 제안합니다.

1. 기존 방식: "사전에 허락받기" (Consent-based)

기존의 주류 접근법은 학생들에게 미리 물어보는 것입니다.

"네가 우선순위를 포기하고 다른 친구가 네 자리를 차지해도 괜찮니? (그 친구가 이득을 보고 너는 손해 보지 않는다면)"

이 방식은 EADA라는 알고리즘을 사용합니다. 하지만 문제는 학생들이 미리 "괜찮다"고 동의하기 어렵다는 점입니다. 또한, 동의한 학생들만 참여할 때만 효율이 극대화되고, 일부만 동의하면 시스템이 엉망이 될 수 있습니다.

2. 새로운 방식: "결과가 정당화하는 위반" (Justifiability)

저자들의 아이디어는 **"결과를 보고 판단하자"**는 것입니다. 사전에 허락을 구하지 않고, 배정이 끝난 후 다음과 같은 두 가지 경우에만 우선순위를 어기는 것을 **정당하다 (Justifiable)**고 봅니다.

• 케이스 A (수혜자): 우선순위를 어긴 학생이 결과적으로 더 좋은 학교에 가게 된 경우.
  • 비유: "네가 먼저 도착해서 자리를 차지했는데, 내가 네 자리로 갔을 때 너는 더 좋은 자리에 가게 되었어. 그러니 네가 화낼 이유가 없지!"
• 케이스 B (회복 불가능자): 어떤 방법을 써도 더 좋은 학교에 갈 수 없는 학생.
  • 비유: "네가 아무리 원해도 그 학교는 너에게 줄 수 없는 상황이었어. 내가 네 자리를 가져가도 너는 원래대로 돌아갈 수밖에 없으니, 네가 불만 가질 근거가 없어."

핵심: 만약 어떤 학생이 우선순위를 어겨서 더 나빠지거나, 혹은 더 좋아질 기회를 잃었다면, 그 위반은 **부당 (Unjustifiable)**합니다.

---

🛠️ 어떻게 작동하나요? (SJBC+ 알고리즘)

저자들은 이 아이디어를 실현하는 **SJBC+**라는 알고리즘을 만들었습니다.

1. 초기 단계 (JBC): 우선순위를 어겨도 되는 최소한의 학생들 (더 좋아질 수 없는 학생들) 만을 대상으로 자리를 바꿔줍니다.
2. 확장 단계: 이렇게 자리를 바꾼 학생들 (수혜자) 이 생겼다면, 이제 이 학생들의 우선순위도 '어겨도 되는' 범위에 넣습니다.
3. 반복: 이 과정을 반복하며, 더 많은 학생이 이득을 보도록 자리를 계속 재배치합니다.
4. 종료: 더 이상 이득을 보는 학생을 만들 수 없거나, 이득을 보지 못하는 학생의 우선순위를 어겨야만 하는 단계에 도달하면 멈춥니다.

이 과정은 컴퓨터가 순식간에 계산할 수 있을 정도로 빠릅니다.

---

📊 시뮬레이션 결과: 실제로 효과가 있을까?

저자들은 수천 번의 가상 시나리오를 돌려보았습니다.

• 효율성: 이 새로운 방식 (SJBC+) 은 기존 방식 (EADA) 보다 훨씬 더 많은 학생이 더 좋은 학교에 가게 만들었습니다.
• 완벽한 효율: 이론적으로는 '완벽한 효율'과 '정당성'이 충돌할 수 있지만, 실제 상황에서는 60~85% 의 경우에 두 마리 토끼를 다 잡았습니다 (모든 학생이 최대한 좋은 학교에 배정됨).
• 동의 방식의 한계: 기존 방식 (EADA) 은 학생들의 '동의' 비율이 50% 일 때 효율이 급격히 떨어지지만, 새로운 방식은 동의 여부와 상관없이 항상 좋은 결과를 냅니다.

---

🎁 한 줄 요약

"누구의 우선순위를 어겨도 될까?"라는 질문에, "그 위반으로 인해 더 좋은 결과를 얻는 학생이 있거나, 어차피 더 좋아질 수 없는 학생이라면 OK"라고 답하는 새로운 시스템입니다.

이 방식은 사전에 허락을 구하는 번거로움 없이, 결과가 스스로를 정당화하도록 하여 학교 배정을 훨씬 공정하고 효율적으로 만듭니다. 마치 **"누구도 잃지 않고, 많은 이득을 보는 거래"**를 찾아내는 지혜로운 중재자 같은 역할을 하는 셈입니다.

기술 요약

1. 문제 제기 (Problem Statement)

• 배경: 학생 제안형 지연 수용 (DA) 알고리즘은 안정성 (Stability) 을 보장하지만, 파레토 비효율적 (Pareto-inefficient) 인 결과를 초래할 수 있습니다. DA 보다 나은 결과를 얻으려면 반드시 일부 학생의 우선순위 (Priority) 를 위반해야 합니다.
• 핵심 질문: "어떤 우선순위 위반이 정당한 (Justifiable) 것일까?"
• 기존 접근법의 한계:
  • 현재 주류인 접근법은 **사전 동의 (Ex-ante Consent)**입니다. 즉, 학생들에게 자신의 우선순위를 포기할지 여부를 미리 묻고, 동의한 학생들의 우선순위만 위반하는 메커니즘 (예: EADA) 을 사용합니다.
  • 그러나 사전 동의는 학생들의 전략적 행동에 의존하며, 동의하지 않은 학생들의 우선순위를 존중해야 하므로 달성 가능한 효율성 개선의 범위가 제한될 수 있습니다.
  • 또한, 모든 학생이 동의하더라도 EADA 가 항상 정당한 위반을 보장하지는 않으며, 부분 동의 하에서는 효율성을 완전히 회복하지 못하는 경우가 많습니다.

2. 방법론 및 핵심 개념 (Methodology & Key Concepts)

저자들은 내생적 정당성 (Endogenous Justifiability) 개념을 도입하여 사전 동의에 의존하지 않는 새로운 해결책을 제시합니다.

A. 학생 분류

DA 개선이 이루어질 때 영향을 받는 학생들을 세 가지로 분류합니다:

1. 수혜자 (Beneficiaries): DA 결과보다 더 좋은 학교에 배정된 학생.
2. 개선 불가능자 (Unimprovable Students): 어떤 DA 개선 메커니즘을 사용하더라도 DA 결과보다 나아질 수 없는 학생.
3. 개선 가능 비수혜자 (Improvable Non-beneficiaries): 어떤 개선 메커니즘 하에서는 혜택을 받을 수 있었으나, 선택된 메커니즘에서는 혜택을 받지 못한 학생.

B. 정당한 우선순위 위반 (Justifiable Priority Violation)

• 정의: 우선순위 위반이 **수혜자 (Beneficiaries)**나 **개선 불가능자 (Unimprovable Students)**에게만 발생하는 경우, 그 위반은 '정당한 (Justifiable)' 것으로 간주합니다.
• 부정적 위반: 개선 가능 비수혜자의 우선순위를 위반하는 것은 정당화될 수 없습니다. (왜냐하면 그들은 혜택을 받지 못하면서도 자신의 우선순위가 침해당했기 때문입니다.)
• 특징: 이 기준은 사전에 허가를 구하는 것이 아니라, **실현된 개선 결과 (Who benefits)**에 따라 위반의 정당성이 결정되는 내생적 (Endogenous) 기준입니다.

C. 제안된 알고리즘

1. JBC (Just Below Cutoffs):
   • DA 에서 개선 가능한 학생들 중 각 학교의 '컷오프 (cutoff)' 바로 아래에 있는 학생 (가장 우선순위가 높은 개선 가능 학생) 을 찾아 순환 교환 (Cycle) 을 수행합니다.
   • 이 과정은 강하게 정당한 (Strongly Justifiable) 매칭을 생성하며, 이는 개선 가능 비수혜자의 우선순위를 전혀 위반하지 않습니다.
2. SJBC+ (Sequential Just Below Cutoffs):
   • JBC 로부터 시작하여, 1 단계에서 생성된 수혜자들을 기반으로 추가적인 교환을 허용하는 반복적 확장 (Iterative Expansion) 알고리즘입니다.
   • 각 단계에서 기존 수혜자들의 우선순위 위반을 허용하여 새로운 수혜자를 창출하고, 이를 바탕으로 다음 단계의 위반을 정당화합니다.
   • 수렴성: 더 이상 수혜자 집합을 확장할 수 없을 때까지 반복하며, 최종적으로 파레토 개선이 불가능한 (Justifiable 매칭 내에서) 결과를 도출합니다.
   • 복잡도: 다항 시간 (Polynomial-time) 내에 계산 가능합니다.

3. 주요 기여 및 이론적 결과 (Key Contributions & Results)

1) 정당한 개선의 존재성 및 구조 (Theorem 1)

• DA 가 비효율적일 때, 항상 강하게 정당한 (Strongly Justifiable) 개선이 존재함을 증명했습니다.
• JBC 알고리즘은 이러한 강하게 정당한 매칭 중 가장 큰 집합 (최대 순환 교환) 을 선택합니다.

2) 효율성과의 상충 관계 (Proposition 1)

• 정당성 (Justifiability) 과 완전한 파레토 효율성 (Full Pareto-efficiency) 은 일반적으로 양립할 수 없습니다.
• 완전한 효율성을 달성하려면 개선 가능 비수혜자의 우선순위를 위반해야 하는 경우가 발생하며, 이는 저자들의 정의상 '부당한' 위반이 됩니다. 따라서 SJBC+ 는 '제약된 효율성 (Constrained Efficiency)'을 목표로 합니다.

3) 기존 메커니즘 (EADA) 과의 비교 (Theorem 3)

• EADA(Consent-based) 와의 차이: EADA 는 모든 학생이 동의하더라도 정당한 위반을 보장하지 않을 수 있으며, 반대로 저자들의 '정당한 매칭'은 어떤 동의 집합 하에서도 EADA 로 달성할 수 없는 결과를 만들어낼 수 있습니다.
• 사전 동의의 한계 (Theorem 4): 사전 동의 메커니즘은 '동의 유도 (Incentivizing consent)', '제약된 효율성 (Constrained efficiency)', '가능할 때의 효율성 (Efficiency whenever possible)'이라는 세 가지 속성을 동시에 만족할 수 없습니다. 즉, 부분 동의 하에서는 EADA 와 같은 메커니즘이 항상 효율적인 결과를 보장하지 못합니다.

4) 시뮬레이션 결과 (Section 6)

• SJBC+ 의 성능: 무작위 시장 시뮬레이션에서 SJBC+ 는 60% 이상의 경우 완전한 파레토 효율성을 달성했습니다.
• EADA 대비 우위:
  • 50% 동의 (Partial Consent): EADA 의 효율성 달성률은 10% 미만 (상관된 선호도의 경우 0%) 인 반면, SJBC+ 는 70% 이상을 유지했습니다.
  • 수혜자 수: SJBC+ 는 EADA(완전 동의 포함) 보다 더 많은 학생을 DA 결과보다 개선시켰습니다.
  • 정당성: SJBC+ 는 설계상 항상 정당성을 만족하지만, EADA 는 시장 크기가 커지거나 선호도가 상관될수록 정당성을 만족하는 비율이 급격히 떨어집니다 (100 명 기준 상관 선호도에서 0.3% 까지 하락).

4. 의의 및 결론 (Significance & Conclusion)

• 이론적 기여: 학교 선택 분야에서 우선순위 위반의 정당성을 판단하는 새로운 규범적 기준 (Normative Criterion) 을 제시했습니다. 이는 사전 동의에 의존하지 않고, 결과의 공정성과 효율성을 내생적으로 조화시키는 새로운 방향을 제시합니다.
• 실용적 기여: 교육 당국이 DA 의 비효율성을 해결하면서도 법적/규제적 우선순위를 존중해야 하는 상황에서, SJBC+ 알고리즘은 기존 메커니즘보다 더 많은 학생을 개선시키고, 더 높은 확률로 효율적인 결과를 도출하는 실용적인 대안이 됩니다.
• 한계 및 향후 연구: 제안된 메커니즘은 전략적 조작 (Manipulation) 에 취약할 수 있으며, 이는 향후 연구 과제로 남겼습니다. 또한, 정당성과 효율성 사이의 이론적 상충 관계는 여전히 존재하지만, 실제 시장에서는 그 상충이 자주 발생하지 않음을 시뮬레이션을 통해 보였습니다.

요약하자면, 이 논문은 "누가 혜택을 받았는가"에 기반한 내생적 정당성 개념을 통해 DA 의 비효율성을 해결하는 새로운 메커니즘을 제안하며, 기존 사전 동의 기반 메커니즘 (EADA) 보다 더 넓은 범위에서 효율성과 공정성을 동시에 달성할 수 있음을 이론적, 실증적으로 입증했습니다.