Note on the size of a stable matching

기술 요약: 안정적 매칭의 크기에 관한 노트

문제 제기
본 논문은 일대일 양측 매칭 시장(노동자와 단일 직위 기업)에서 안정적 매칭(stable matching)의 크기와 최대 개별 합리적(maximum individually rational) 매칭의 크기 사이의 관계를 조사한다. Gale-Shapley 프레임워크는 안정적 매칭의 존재를 보장하지만, 이러한 매칭이 고용된 노동자나 채워진 직위의 수를 극대화한다는 것을 보장하지는 않는다. 저자들은 다음의 질문을 다룬다: 최대 개별 합리적 매칭이 $n$개의 쌍을 포함하는 시장이 주어졌을 때, 모든 안정적 매칭의 쌍의 개수에 대한 하한선은 무엇인가? 나아가, 이들은 안정적 매칭을 최대치에 비해 최대한 작게 만드는 구체적인 선호 구조를 규명하고, 안정적 쌍과 최대 매칭 쌍 사이의 중첩을 분석한다.

방법론
저자들은 매칭 시장을 모델링하기 위해 무방향 및 유방향 그래프 형식을 모두 활용하여 그래프 이론적 접근 방식을 채택한다.

1. 무방향 그래프 형식: 시장은 수용 가능한 쌍을 나타내는 에지(edge)를 가진 이분 그래프 $G = (W, F; E)$로 모델링된다. 저자들은 극대(maximal) 및 최대(maximum) 매칭의 성질을 활용하여 경계값을 설정한다.
2. 유방향 그래프(Digraph) 형식: 선호 구조를 규명하기 위해, 저자들은 Maffray(1992)가 제안한 매칭 유방향 그래프 형식을 채택한다. 이 유방향 그래프 $D = (V, A)$에서 정점은 수용 가능한 쌍 $(w, f)$를 나타내며, 아크(arc)는 선호 순위를 나타낸다 (예: $(w, f)$에서 $(w, f')$로 향하는 아크는 노동자 $w$가 $f$보다 $f'$를 선호함을 의미함).
3. 매력 없는 대안의 반복 제거(IDUA): 저자들은 시장을 "표준형(normal form)"으로 축소하기 위해 IDUA 절차(Balinski and Ratier, 1997; Gutin et al., 2023)를 활용한다. 이 과정은 어떤 쌍이 안정적 매칭에 속할 수 없는 경우(예: 참여자 한쪽이 더 선호하는 파트너가 미매칭 상태인 동안 다른 파트너와 매칭된 경우) 해당 쌍을 반복적으로 제거한다.
4. 구성적 규명: 저자들은 최대 안정적 매칭을 가진 기본 시장을 확장하여, 기존의 안정적 참여자들에게 "매력 없게" 구조화된 선호를 가진 새로운 참여자들을 추가함으로써 특정 클래스의 시장($G_n$ 및 $F_n$)을 정의한다.

주요 기여 및 결과

• 정리 1 (크기 경계): 주요 결과는 최대 개별 합리적 매칭의 크기가 $n$인 모든 시장에서, 모든 안정적 매칭은 반드시 $\lceil n/2 \rceil$ 이상의 크기를 가져야 함을 확립한다.

  • 증명 논리: 증명은 두 가지 사실에 의존한다: (i) 안정적 매칭은 극대 매칭(maximal matching)이다 (즉, 양측 모두 미매칭 상태인 수용 가능한 쌍이 존재하지 않음), (ii) 그래프에서의 모든 극대 매칭은 최대 매칭 크기의 최소 절반 이상이다.
  • 시사점: 최대치가 개별 합리적일 경우, 균형 고용률은 결코 최대 달성 가능 고용량의 50% 미만으로 떨어질 수 없다.

• 정리 2 (극한 선호의 규명): 본 논문은 이 하한값에 도달하는 선호 프로파일($F_n$)의 클래스를 규명한다.

  • 시장이 (안정적 크기 = $\lceil n/2 \rceil$, 최대 크기 = $n$)의 경계값에 도달할 필요충분조건은 해당 시장이 클래스 $F_n$에 속하는 것이다.
  • 구조적 특성: 이러한 시장에서 안정적 매칭에 나타나지 않는 참여자들(균형 상태에서의 "미매칭자")은 서로를 수용 불가능하게 여겨야 한다. 만약 그들이 서로를 수용 가능하다면, 그들은 차단 쌍(blocking pair)을 형성하여 안정적 매칭의 크기를 증가시킬 것이기 때문이다.
  • 상단의 일치(Agreement at the Top): 이러한 시장들의 자연스러운 하위 클래스는 참여자들이 자신의 가장 덜 선호하는 안정적 파트너보다 모든 새로운 비안정적 참여자들을 낮게 순위 매기는 "상단의 일치" 현상을 보인다.

• 정리 3 (중첩과 희생): 저자들은 안정적 매칭($\mu^*$)과 최대 매칭($\mu$)에 포함된 쌍의 집합 사이의 교집합을 분석한다.

  • $r$을 공통 쌍의 수라고 하자. 정리는 $|\mu^*| \geq (|\mu| + r) / 2$임을 명시한다.
  • 시사점: 안정적 매칭이 최소화될 때 (즉, $|\mu^*| = \lceil |\mu|/2 \rceil$), $r$은 반드시 0이어야 한다. 이는 시장이 안정적 매칭을 가능한 한 작게 만들도록 구조화된 경우, 안정적 매칭에 포함된 쌍 중 어느 것도 최대 매칭에 나타나지 않음을 의미한다.
  • 안정성의 비용: 고용을 극대화하는 것(모든 공석을 채우는 것)은 더 작은 규모의 안정적 구성에 존재했을 법한 모든 균형 쌍들을 "희생"하는 것을 요구할 수 있다.

의의 및 범위
본 논문은 자신의 분석을 "안정성의 비용"에 대한 탐구로 규정한다. 저자들은 안정성과 효율성(매칭 크기로 측정됨) 사이의 상충 관계를 정량화한다. 저자들은 안정성이 차단 쌍을 방지하지만, 특히 정리 2에서 식별된 선호 구조를 가진 시장에서는 이론적 최대치에 비해 고용된 노동자 수의 상당한 감소를 초래할 수 있음을 지적한다.

저자들은 결과의 범위를 일대-일 양측 매칭 시장으로 명시적으로 제한한다. 저자들은 이 프레임워크가 널리 적용 가능함에도 불구하고(예: 학생-대학, 의사-병원), 여기서 도출된 특정 경계값과 규명 방식이 일대다(many-to-one) 시장, 커플이 포함된 시장, 또는 일방향 "룸메이트" 문제와 같은 더 복잡한 환경으로 자동 확장되지는 않는다는 점을 인정한다. 본 논문은 새로운 알고리즘이나 실험적 응용을 제안하기보다는, 고용률의 최악의 시나리오에 대한 이론적 경계와 구조적 규명을 제공하는 데 목적이 있다.