매칭이론과 수강신청

  제가 듣는 김진우 교수님의 수업시간 중에 매칭이론(Matching Theory)을 다룰 기회가 있었습니다. 오늘은 매칭 이론에 관한 몇 가지 중요한 개념을 살펴보고 이를 우리 주변 상황에 적용할 수는 없을지 한 번 생각해 보고자 합니다.

  매칭이란 개인들의 짝이 이어지는 것을 말합니다. 남녀 결혼이 그 대표적인 예라 할 수 있고 노동시장과 장기기증, 물물거래도 경제학에서 중요한 매칭 주제라 할 수 있습니다. 사실 교환이란 건 애초에 혼자서 할 수 있는 게 아니지요? 거래가 발생하기 위해서는 먼저 두 당사자가 짝지어져야 하기 때문에 경제학과 매칭은 본래 땔래야 땔 수 없는 관계일 것입니다.

  매칭은 개별 경제 주체들이 각자 알아서 짝을 찾아가는 분권화된 매칭(Decentralized Matching)과 제 3자가 대신 짝을 맺어주는 집권화된 매칭(Centralized Matching)으로 나눌 수 있는데, 매칭 이론은 이 중에서 후자에 주목합니다. 어떻게 하면 개인들의 선호관계를 최대한 잘 반영할 수 있을지? 어떻게 하면 사람들로 하여금 사회 전체에 바람직한 전략을 취하도록 유도할 수 있을지? 어떻게 매칭의 효율성을 달성할 수 있을지? 와 같은 물음에 답하고자 하는 것이 매칭 이론의 목표라고 할 수 있습니다.


  1. 좋은 매칭이란 무엇인가?
 
  매칭 방식은 여러 가지가 있습니다. 무작위로 배치할 수도 있고 사람들의 선호도를 반영하여 특정한 규칙, 알고리즘에 따라 이어줄 수도 있습니다. 이때 문제는 모든 사람을 만족시키는 매칭이 존재하기가 힘들다는 것입니다. 사람들의 선호체계는 겹치기 마련이고 이에 따라 인기 있는 상대방을 두고 경쟁이 발생합니다. 심지어 사람들은 더 인기 있는 상대방과 매칭되기 위하여 거짓말도 불사합니다. 쉬운 문제만은 아닌 것이지요.

  따라서 매칭 알고리즘을 고안하기에 앞서 우리가 먼저 고민해야 할 부분은 바람직한 매칭이 가져야 할 특성일 것입니다. 한 가지 예시를 통해 살펴 보도록 하겠습니다. 결혼정보업체에 선남선녀 3쌍이 매칭을 기다리고 있다고 합시다. 각자가 커플 메니저에게 밝힌 선호체계는 아래와 같습니다.

남1 : 태희 > 수지 > 아이유                          태희 : 남1 > 남3 > 남2  
남2 : 태희 > 아이유 > 싱글로 남기             수지 : 남2 > 남1 > 남3
남3 : 수지 > 아이유 > 태희                          아이유: 남3 > 남1 > 남2
 
  이때 커플 메니저가 고심 끝에 남1-아이유, 남2-수지, 남3-태희을 매칭해 주었다고 해봅시다. 딱 보아도 뭔가 문제가 있겠지요? 여기에는 두 가지 문제점이 있습니다. 첫째, 남2는 수지를 만나는 것 보다 차라리 싱글을 선호합니다. 그렇기에 남2는 이러한 매칭 결과를 거부할 유인이 있습니다. 이를 'Blocked by individual'이라 부릅니다. 둘째, 남1은 자신에게 배정된 아이유보다 태희를 선호하는 한편, 태희도 지금의 남3 보다 남1을 더 선호합니다. 따라서 남1과 태희는 주어진 매칭을 거부하고 이들 둘만 따로 떠나갈 유인이 있습니다. 이처럼 두 사람이 서로 협조하는 경우에도 매칭 이탈 가능성이 생길 수 있는 데 이를 'Blocked by pair'라고 부릅니다.

  따라서 어떤 알고리즘을 따랐을 때 위 두 블락이 발생하지 않는다면 이는 좋은 매칭 알고리즘이라 할 수 있습니다. 이렇게 나타난 매칭 결과를 안정된 매칭(Stable Matching)라고 부릅니다. 안정된 매칭은 그 원리 상 파레토 옵티멀과 같은 개념이기에 안정성은 매칭 알고리즘이 가져야 할 좋은 특성이라 할 수 있습니다. 반대로 안정성이 보장되지 못하는 알고리즘은 여러 불만과 문제를 초래할 수 있습니다.

   다음으로 매칭 알고리즘이 가져야 할 중요한 요건으로 전략적 무용성(Strategy Proofness)을 꼽을 수 있습니다. 단어가 다소 낯설 수 있는데 쉽게 설명하자면 모든 사람이 정보를 솔직하게 밝힐 유인이 있다는 것입니다. 아까 예시에서는 사람들의 선호를 모두 공개된 정보로 두었습니다. 그러나 실제 현실에서는 각 플레이어가 이를 솔직하게 공개할 수도 또는 때에 따라 거짓으로 공개할 수도 있습니다. 일종의 게임 상황인 것이지요. 만약 주어진 매칭 규칙 하에서 모든 사람들이 솔직하게 자신의 선호를 밝히는 게 우월전략이 된다면 모든 정보가 오픈될 것입니다. 반대로 전략적 무용성이 만족되지 않아 일부 사람들이 정보공개를 회피한다면 (죄수의 딜레마처럼) 사회 전체에 바람직하지 않을 수 있습니다. 정확하게 공개된 정보가 적을수록 매칭을 이어주는 제3자에 입장에서 최적 매칭을 달성하기 힘들기 때문입니다.

   제 생각에 우리학교 사회과학대학의 전공진입 매칭이야 말로 이를 극명하게 나타내는 사례일 것 같습니다. 사회대에서는 매년 2학년에 올라가는 학생들을 대상으로 전공진입을 실시합니다. 이때 학생들이 제출한 전공 선호순위가 중요한 요인으로 작용합니다. 첫 번째 단계에서는 해당 학과를 1순위 전공으로 제출한 학생들만을 두고 진입여부를 결정합니다. 기준은 학점 순입니다. 만약 여석이 발생한 경우에는 두 번째 단계에서 2순위 전공으로 제출한 학생들을 두고 다시 진입여부를 결정합니다. 이때 학점이 높지 않은 학생들은 아무리 경제학부를 가장 선호한다 하더라도 선호순위 제출 시에는 경제학부를 1순위로 두지 않을 유인이 있습니다. 경제학부를 1순위로 두었다가 만에 하나 떨어졌을 경우 자신이 두 번째, 세 번째로 선호하는 전공으로도 배정되지 않을 가능성이 있기 때문입니다. 실제로 그간 전공진입 과정을 보면 학생들이 자신의 전공진입 가능성과 실제 선호도를 저울질 하여 거짓된 선호 정보를 과 사무실에다 제출하는 경우가 빈번하게 발생해왔습니다.

   이처럼 지금까지 소개한 안정성와 전략적 무용성은 바람직한 매칭이 가져야 할 가장 중요한 두 요건이라 할 수 있습니다. 물론 두 개를 모두 완벽하게 달성할 수는 없습니다. 사실 항상 Stable한 결과를 도출하고 모든 사람이 strategy proof한 매칭 알고리즘은 존재할 수 없다는 것이 이미 증명되어 있습니다. 다만 매칭 알고리즘에 따라 한쪽 측면을 더 잘 달성하는 것은 가능합니다. 따라서 여러 알고리즘 중에서 특정 매칭 상황의 여러 현실적 요건에 보다 적합한 알고리즘을 선택하는 것이 우리에게 필요한 지혜라고 할 수 있습니다. 


2. 매칭 알고리즘의 종류와 실제 응용

   가장 대표적인 매칭 알고리즘으로는 1) Gale-Shapley Deferred Acceptance Algorithms(DA Algorithms)과 2) Top Trading Cycle Algorithms이 있습니다. 바로 지난해 노벨 경제학자 수상자인 샤플리가 고안하고 로스가 실제 사례에 적용한 방법인 것이지요. 그리 복잡한 알고리즘은 아닌데 자세한 방법은 링크로 대신하겠습니다.

링크: http://www.kipf.re.kr/TaxFiscalpubIssuet/TaxFiscalpubIssuet-View/2-2012-%EB%85%B8%EB%B2%A8-%EA%B2%BD%EC%A0%9C%ED%95%99%EC%83%81%EC%9D%84-%ED%86%B5%ED%95%B4-%EB%B3%B8-%EC%8B%9C%EC%9E%A5-%EC%84%A4%EA%B3%84%EC%9D%98-%EC%9D%B4%EB%A1%A0%EA%B3%BC-%EC%9D%91%EC%9A%A9/30295/18/null/null/null

   1번 DA 알고리즘의 장점으로는 이 규칙을 따랐을 때 항상 Stable matching을 결과로 도출한다는 점입니다. 또한 남/녀, 기업가/노동자, 학교/학생 이라는 매칭의 양 집단이 존재할 때 한 쪽 집단에 한해서는 부분적으로 Strategy Proofness가 만족된다는 것도 매우 좋은 점입니다.
   2번 Top Trading Cycle도 흔히 쓰이는 알고리즘 중에 하나입니다. 이 알고리즘의 경우 Stable matching을 보장하지는 않습니다만 매칭의 양 집단 중 한쪽 집단의 선호를 확실하게 만족시킬 수 있는 방법이라는 점, 그리고 전략적 무용성이 늘 만족된다는 점으로 인해 자주 사용되는 방법입니다. 

   실제로 경제학자들이 그 원리와 유용성을 밝혀낸 이후 미국에서는 수많은 매칭 상황에서 DA, Top Trading Cycle 두 알고리즘이 채택되었습니다. 레지던트와 병원 간 매칭, 공립학교의 학생 배정 매칭, 신장 기증자 간 매칭, 기숙사 방과 학생 매칭 등 실제 사용 예가 광범위 합니다. 한 예로 미국 보스턴 지역 교육 당국은 본래 학생들을 공립학교에 매칭하는 데 있어서 우리학교 사회대 전공진입과 같은 형태의 알고리즘을 사용하였습니다. 그러나 이후 전략적 무용성과 관련하여 많은 문제점을 노출하였고, 잘못된 매칭 알고리즘으로 인한 폐해의 대표적인 사례로 꼽혔습니다 (Abdulkadiroglu 2003) 이후 보스턴 교육 당국은 경제학자들의 직접적인 자문을 토대로 DA 알고리즘으로 전환하여 큰 성과를 거두게 됩니다


2. 다른 가능성?

  사실 저는 매칭 이론에 관한 개념들을 공부하며 우리학교 수강신청의 문제점이 생각났습니다. 선착순만을 매칭 규칙으로 고려하다보니 unstable한 상황이 빈번하게 발생한다고 할까요. 먼저 졸업예정자가 번번히 전공필수 과목 수강신청에 실패하는 것이 가장 큰 문제입니다. 수업의 입장에서 보면 졸업예정자는 가장 높은 순위에 들어갈 사람입니다. 마찬가지로 졸업예정자에게 전필 수업은 가장 높은 선호순위를 갖고요. 이때 문제는 수강신청에 있어서 선착순만을 고려하다 보니 해당 수업을 별로 들을 의지도 필요도 없는 사람에 의해 정원이 다 차게 된다는 점입니다. 이로 인해 정작 필요한 사람들은 못 듣게 되는 것이지요. 그러다 보니 인터넷에서는 강의를 사고 팔고 하는 일이 심심치 않게 발견되곤 합니다.(Blocked by pair) 물론 초안지라는 제도를 통해 이를 해소하고자 하지만 이로 인해 강의실 정원 초과라는 또 다른 불편함이 초래되곤 합니다.

  마찬가지로 전략적 무용성이 만족되지 않는 것도 또 다른 문제로 생각해 볼 수 있습니다. 현 체제 하에서 우리의 수강신청 선호에 대한 정보는 신청 클릭 순서로 나타내집니다,. 기본적으로는 내가 반드시 들어야 하는 과목을 가장 먼저 클릭하도록 되어 있는 구조지요.   하지만 실제로 우리는 졸업필수요건 과목을 가장 먼저 신청하기 보다는 체육이라든지 미술과 같은 인기 교양을 먼저 신청함으로써 전략적으로 성공확률을 높이고자 합니다. 이로인해 발생하는 리스크도 존재하고요. 수강신청 전략을 구상하는 것 자체가 매번 굉장히 피로한 일입니다..

  그런 의미에서 우리 학교 수강신청에 있어서도 게일 샤플리 DA 알고리즘을 적용하면 어떨까란 생각이 들었습니다. 가령 예비수강신청일날 학생들은 수강 과목 선호도 순위를 제출하는 것이지요. 또 반대로 각 수업의 교수 혹은 과 사무실은 학년순, 전공순으로 학생들의 우선순위 기준을 정해서 중앙 시스템에 제출하게 할 수 있습니다. 이후 중앙 시스템은 알고리즘에 의한 배정결과를 발표하고 여석에 한해 추가신청을 받는 제도입니다. 그렇게 하면 수강신청 당일 마다 발생하는 여러 해프닝을 효과적으로 방지할 수 있지 않을까요? 이처럼 여러 이론과 개념이 학교 행정의 효율성을 높이는 데도 적용할 수 있다는게 경제학의 흥미로운 점인 것 같습니다.


<참고자료>

김진우 교수님 경제학 연습 강의 노트
Abdulkadiroglu, Sonmez, "School Choice: A Mechanism Design Approach", AER, 2003