The Distribution of Envy in Matching Markets

논문 개요

이 논문은 지연 수용 (Deferred Acceptance, DA) 알고리즘이 적용된 무작위 양면 매칭 시장 (random matching markets) 에서 '질투 (envy)'의 분포를 분석합니다. 특히, **아무도 질투하지 않는 학생 (students whom nobody envies)**과 **아무도 질투하지 않는 학생 (students who envy nobody)**의 수를 정량화하고, 이를 무작위 순서 독재 (Random Serial Dictatorship, RSD) 메커니즘의 결과와 비교합니다.

1. 연구 문제 및 배경

• 배경: 학교 선택 (School Choice) 등 매칭 시장에서는 '정당한 질투 (justified envy)'가 없는 안정적인 매칭이 핵심 목표입니다. 그러나 '정당한' 여부와 관계없이 '전체적인 질투'가 없는 상태 (envy-free) 는 공정성의 또 다른 중요한 척도입니다.
• 문제 제기: DA 는 파레토 효율적 (Pareto-efficient) 인 매칭을 보장하지 않으므로, 효율적인 메커니즘에서 성립하는 질투 관련 결론 (예: 질투하지 않는 학생이 반드시 존재함) 이 DA 에도 적용되는지 불확실합니다.
• 연구 목적:
  1. DA 하에서 '아무도 질투하지 않는 학생'과 '질투하지 않는 학생'의 기대 수를 계산.
  2. 이 두 집합이 파레토 개선 (Pareto-improvement) 의 범위를 어떻게 제한하는지 분석 (두 집합에 속한 학생은 DA 결과에서 더 나은 상태로 개선될 수 없음).
  3. DA 와 RSD 의 결과를 비교하여 질투 분포의 특성을 규명.

2. 모델 및 방법론

• 모델 설정:
  • $n$명의 학생과 $n$개의 학교가 있는 양면 매칭 시장.
  • 모든 학생과 학교는 상대방에 대한 엄격한 선호도 (strict preferences) 를 가지며, 이는 독립적이고 균일하게 무작위 (i.i.d.) 로 생성됨.
  • 각 학교의 정원은 1 명.
• 주요 도구:
  • 지연 수용 (DA) 알고리즘: McVitie 와 Wilson (1971) 이 제안한 순차적 구현 방식을 사용.
  • 쿠폰 수집 문제 (Coupon Collector Problem): DA 실행 과정을 쿠폰 수집 과정과 연결하여 확률론적 분석을 수행.
  • 점근적 분석 (Asymptotic Analysis): 시장 규모 $n$이 커질 때의 거동을 분석.

3. 주요 결과 (Key Results)

가. 아무도 질투하지 않는 학생 (Students whom nobody envies)

• 정의: 배정된 학교가 '과수요 (under-demanded)'인 학생들. 즉, 해당 학교를 원하는 다른 학생이 없는 경우.
• 결과 (Proposition 1):
  • $n$크기의 무작위 시장에서 아무도 질투하지 않는 학생의 기대 수 ($NEn$) 는 정확히 **$n$번째 조화수 (Harmonic number, $H_n$)**와 같습니다.
  • 수식: $NEn = H_n = \sum_{k=1}^n \frac{1}{k}$
  • 근사값: $H_n \approx \ln n + \gamma$ (여기서 $\gamma$는 오일러 - 마스케로니 상수).
  • 의미: 시장 규모 $n$이 커질수록 질투받지 않는 학생의 수는 로그 ($\log n$) 수준으로만 증가하므로, 시장 전체에서 차지하는 비율 ($H_n/n$) 은 0 에 수렴합니다. (예: $n=10,000$일 때 약 10 명 미만).

나. 질투하지 않는 학생 (Students who envy nobody)

• 정의: 자신의 최선 선호 학교 (top choice) 에 배정된 학생들.
• 결과 (Proposition 2 및 Corollary 1):
  • DA 하에서 학생의 순위 분포는 모수 $1/H_n$인 **기하 분포 (Geometric distribution)**로 근사됩니다.
  • 질투하지 않는 학생의 기대 수 ($EN_n$) 는 다음과 같이 근사됩니다:
    $$EN_n \approx \frac{n}{H_n}$$
  • 의미: 아무도 질투하지 않는 학생보다 수는 많지만, 여전히 시장 전체의 작은 부분 ($\frac{n}{\log n}$) 을 차지합니다. (예: $n=10,000$일 때 약 1,100 명).

다. 무작위 순서 독재 (RSD) 와의 비교

• 질투하지 않는 학생 (Top choice):
  • RSD 에서는 학생의 약 절반 ($(n+1)/2$) 이 최선 선호 학교를 받습니다. 이는 DA ($\approx n/\log n$) 보다 훨씬 큽니다.
• 아무도 질투하지 않는 학생 (Unenvied):
  • 놀라운 발견: DA 와 RSD 모두에서 아무도 질투하지 않는 학생의 기대 수는 정확히 $H_n$으로 동일합니다.
  • 이는 두 메커니즘의 구조가 완전히 다르지만, 무작위 시장에서의 '과수요 학교'의 수에 대한 통계적 속성은 동일함을 시사합니다.

4. 논의 및 의의

• 파레토 개선의 한계: DA 결과에서 '아무도 질투하지 않는' 혹은 '질투하지 않는' 학생들은 교환을 통해 더 나은 결과를 얻을 수 없는 '개선 불가능 (unimprovable)' 집단입니다. 이 두 집합의 크기가 시장 전체에 비해 매우 작다는 것은, DA 결과에서 파레토 개선을 통해 얻을 수 있는 이득의 잠재력이 제한적일 수 있음을 의미합니다.
• 메커니즘의 본질: DA 가 RSD 에 비해 최선 선호 학교 배정률 (welfare) 이 현저히 낮음에도 불구하고, '아무도 질투하지 않는 학생'의 수는 두 메커니즘에서 동일하게 유지됩니다. 이는 이 수치가 특정 메커니즘의 결함이 아니라 무작위 매칭 시장 자체의 근본적인 통계적 속성임을 보여줍니다.
• 확장성: 시뮬레이션 결과, 다대일 (many-to-one) 시장이나 선호도가 상관관계를 가질 경우에도 개선 불가능한 학생의 비율은 여전히 낮거나 더 감소하는 경향을 보입니다.

5. 결론

이 논문은 적용 확률론과 쿠폰 수집 문제를 활용하여 DA 알고리즘 하에서 질투의 분포를 정밀하게 분석했습니다. 주요 기여는 무작위 시장에서 질투받지 않는 학생의 수가 $H_n$으로 정확히 계산됨을 보였으며, 이는 DA 와 RSD 를 막론하고 무작위 매칭 시장의 보편적 특성임을 입증한 것입니다. 또한, DA 가 효율성 측면에서 RSD 보다 열등함에도 불구하고, '무질투' 측면에서는 두 메커니즘이 동일한 결과를 산출한다는 역설적인 사실을 규명했습니다.