Critical Relaxed-Stable Matchings with Ties in the Many-to-Many Setting

1. 문제 정의 (Problem Definition)

이 논문은 **양측 선호도 (two-sided preferences)**를 가진 다대다 (many-to-many) 이분 매칭 문제를 연구합니다. 기존 연구들을 일반화하여 다음과 같은 복잡한 제약 조건들을 동시에 다룹니다.

• 입력: 이분 그래프 $G = (A \cup B, E)$.
• 선호도 (Preferences): 각 정점 (에이전트) 은 이웃에 대한 선호 순서를 가지며, 이 순서에는 **동일한 순위 (ties)**가 포함될 수 있습니다.
• 쿼터 (Quotas):
  • 상한 쿼터 ($q^+(u)$): 정점 $u$가 가질 수 있는 최대 매칭 수.
  • 하한 쿼터 ($q^-(u)$): 정점 $u$가 반드시 매칭되어야 하는 최소 수. $q^-(u) > 0$인 정점을 lq-vertex라고 부릅니다.
• 목표:
  1. 임계성 (Criticality): 모든 정점의 하한 쿼터 미달 (deficiency) 을 최대화하여 최소화하는 매칭을 찾는 것. (즉, 하한 쿼터를 최대한 충족시키는 매칭).
  2. 최적성 (Optimality): 선호도에 기반한 안정성 (Stability) 또는 인기도 (Popularity) 를 만족하는 것.

핵심 난제:

• 선호도에 동점 (ties) 이 있거나 하한 쿼터가 존재할 때, **임계적이면서 약하게 안정적 (weakly stable)**인 매칭이 존재하지 않을 수 있습니다.
• 또한, 동점이 있는 환경에서 인기 있는 (popular) 매칭이 존재하지 않을 수도 있습니다.
• 따라서, 기존 개념을 완화한 **완화된 안정성 (Relaxed Stability)**을 도입하여 해결책을 모색합니다.

---

2. 방법론 (Methodology)

저자들은 Király 의 알고리즘 (동점이 있는 다대일 매칭에서의 근사 알고리즘) 과 Nasre 등 (하한 쿼터가 있는 다대다 매칭에서의 인기 임계 매칭 알고리즘) 의 아이디어를 결합하여 새로운 알고리즘을 제안합니다.

2.1. 완화된 안정성 (Relaxed Stability) 의 일반화

기존의 HRLQ (Hospital/Residents with Lower Quotas) 설정에서 정의된 완화된 안정성을 다대다 (many-to-many) 설정으로 확장했습니다.

• 정의: 매칭 $M$이 **완화된 안정적 (RSM)**이라는 것은, 차단 쌍 (blocking pair) $(a, b)$가 존재하더라도, 그 쌍이 **정당화 (justified)**될 수 있어야 함을 의미합니다.
  • $a$가 이미 상한 쿼터로 가득 차 있고, $a$가 $b$를 선호하는 현재 파트너 $b'$들이 모두 하한 쿼터 미달 (deficient) 상태라면, $a$의 관점에서 차단 쌍은 정당화됩니다.
  • $b$의 관점에서도 동일한 조건이 성립하면 정당화됩니다.
• 결과: 이 정의 하에서 임계적이면서 완화된 안정적인 매칭 (CRITICAL-RSM) 은 항상 존재함을 증명했습니다.

2.2. 제안된 알고리즘 (Algorithm Overview)

알고리즘은 제안 기반 (proposal-based) 방식이며, 다단계 (multi-level) 구조를 가집니다. 총 $s+t+2$개의 레벨 ($0$부터$s+t+1$까지) 을 사용합니다. 여기서$s$와$t$는 각각 집합$A$와$B$의 하한 쿼터 합계입니다.

1. 레벨 $0 \sim t-1$ (B 측 임계성 확보):
   • $A$의 정점들은 $B$의 **lq-vertex(하한 쿼터가 있는 정점)**에게만 제안합니다.
   • 이 단계는 $B$ 측의 하한 쿼터를 최대한 충족시키는 것을 목표로 합니다.
2. 레벨 $t$ (Király 의 단계 - 동점 처리):
   • $A$의 정점들이 원래의 선호 리스트 (동점 포함) 를 사용하여 제안합니다.
   • 불확실한 제안 (Uncertain Proposal): Király 의 알고리즘을 다대다 환경에 맞게 수정하여 적용합니다. 동점이 있는 경우, 특정 조건 하에서 제안이 '불확실'로 라벨링되어 나중에 재평가될 수 있게 합니다.
   • 별표 (*) 상태: 모든 이웃에게 제안한 후에도 부족하면 정점이 $*$ 상태가 되어 선호 리스트의 처음부터 다시 제안합니다. 이는 선호도 리스트에서 미세하게 순위가 상승한 것으로 간주됩니다.
   • 이 단계는 불필요한 차단 쌍을 제거하고 매칭의 크기를 보장합니다.
3. 레벨 $t+1 \sim s+t$ (A 측 임계성 확보):
   • 여전히 하한 쿼터 미달인 $A$의 정점들이 $t+1$ 레벨로 올라가 나머지 이웃에게 제안합니다.
   • 이 단계는 $A$ 측의 하한 쿼터 충족을 보장합니다.

기술적 기여:

• 불확실한 제안의 정의 수정: Király 의 원래 정의에서 제안자가 '가득 차 있어야 한다 (fully subscribed)'는 조건은 불필요하며, 이를 제거하여 알고리즘의 안정성을 보장했습니다.
• 다대다 환경 적용: 다대다 설정에서는 한 정점이 여러 개의 불확실한 제안에 동시에 관여할 수 있으므로, 이를 처리하기 위해 제안 순서와 라벨링을 신중하게 관리합니다.
• 선호 리스트 삭제 금지: 기존 Király 알고리즘은 거절된 정점을 리스트에서 삭제하지만, 이 알고리즘은 다단계 프레임워크와 호환되도록 리스트에서 삭제하지 않고 '마킹 (marking)' 개념을 도입했습니다.

---

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

3.1. 존재성 증명

• 선호도에 동점 (ties) 이 있고 양측에 하한 쿼터가 있는 다대다 설정에서 임계적이면서 완화된 안정적인 매칭 (CRITICAL-RSM) 이 항상 존재함을 증명했습니다.

3.2. 근사 알고리즘 및 복잡도

• NP-난해성: 최대 크기의 CRITICAL-RSM 을 찾는 문제는 동점이 있는 경우 최대 안정 매칭 문제와 마찬가지로 NP-난해임을 보였습니다.
• 2/3 근사 알고리즘: 다항 시간 ($O(m^2)$) 내에 최대 크기 CRITICAL-RSM 에 대한 2/3 근사 해를 계산하는 알고리즘을 제시했습니다.
  • 이는 동점이 있는 최대 안정 매칭 문제에 대한 기존 최단 근사 비율 (2/3) 과 일치합니다.
  • Small Set Expansion Hypothesis 하에서 이 근사 비율은 최적일 가능성이 높습니다.

3.3. NP-완전성

• 안정적이면서 임계적인 매칭이 존재하는지 여부를 결정하는 문제가 NP-완전임을 증명했습니다 (하한 쿼터와 동점이 모두 존재하는 경우).

---

4. 의의 및 중요성 (Significance)

1. 모델의 일반화: 기존의 연구들이 다루지 못했던 동점 (ties) 과 하한 쿼터 (lower quotas) 가 양측에 모두 존재하는 다대다 매칭이라는 가장 일반적인 모델을 제시했습니다. 이는 학생 - 과정 배정, 근로자 - 기업 할당 등 실제 응용 사례를 더 잘 반영합니다.
2. 실용성: 제안 기반 알고리즘은 Gale-Shapley 알고리즘의 확장으로, 구현이 용이하고 실제 시스템에 적용하기 좋습니다.
3. 이론적 한계 극복: 동점과 하한 쿼터가 공존할 때 '완전한' 안정성과 임계성을 동시에 만족하는 매칭이 존재하지 않을 수 있다는 문제를, '완화된 안정성'이라는 개념을 통해 우회하여 해결책을 제시했습니다.
4. 최적성 보장: NP-난해한 문제에 대해 이론적으로 가능한 최선의 근사 비율 (2/3) 을 달성하는 알고리즘을 제공함으로써, 이 분야에서 중요한 이론적 진전을 이루었습니다.

요약

이 논문은 복잡한 제약 조건 (동점, 하한 쿼터, 다대다) 하에서 매칭 문제를 해결하기 위해 완화된 안정성 개념을 도입하고, 이를 기반으로 2/3 근사 비율을 보장하는 다항 시간 알고리즘을 개발했습니다. 이는 기존 이론적 한계를 넘어서는 중요한 성과로, 실제 자원 배분 문제의 최적화 기법 발전에 기여합니다.