의사 매칭 알고리즘 원리: 선호 순위만으로 안정적 배정을 만드는 시장 설계의 작동 방식

핵심 메시지

• 시장은 물건을 사고파는 곳만이 아니라 한쪽과 다른 쪽을 짝지어 주는 장치이기도 하며, 의대생과 수련 프로그램의 매칭이 그 대표 사례다.
• 지원과 면접이 끝나면 양쪽이 각각 선호 순위 목록을 제출하고, 알고리즘이 그 목록만으로 누구를 어디에 배정할지 결정한다.
• 핵심 절차는 '임시 배정'과 '밀려남'이다. 더 선호되는 지원자가 나타나면 앞서 임시로 자리를 잡았던 지원자가 밀려나고, 밀려난 사람은 다음 순위로 이동한다.
• 결과는 안정적이다. 양쪽 모두에게 이득이 되는 맞바꿈이 더는 존재하지 않아, 겉보기에 아쉬운 배정도 실은 뒤집을 방법이 없다.
• 또 하나의 성질은 선호를 속일 이유가 없다는 것이다. 까다로워 보이려고 순위 목록을 짧게 줄이면 오히려 아무도 뽑지 못하는 결과로 되돌아온다.

쉽게 이해하기

경제학을 공부한 진행자가 자신이 배운 것 중 가장 흥미로웠던 분야로 시장 설계를 꼽으며 이야기를 시작한다. 보통 시장이라고 하면 물건과 돈이 오가는 장면을 떠올리지만, 시장의 본질은 한쪽과 다른 쪽을 연결하는 것이라는 관점이다. 미국에서 의대생을 수련 프로그램에 배정하는 매칭 제도가 그 관점을 가장 잘 보여 주는 예로 소개된다.

절차는 네 단계다. 지원자가 여러 프로그램에 지원하고, 프로그램이 지원자를 불러 면접을 보고, 그다음 양쪽이 각각 선호 순위를 매긴 목록을 만든다. 지원자는 가고 싶은 곳을 위에서부터 적고, 가고 싶지 않은 곳은 아예 빼도 된다. 프로그램도 마찬가지로 뽑고 싶은 지원자 목록을 만든다. 마지막으로 이 목록들을 넣고 매칭 알고리즘을 돌린다.

영상은 지원자 다섯 명과 정원 두 자리씩인 프로그램 세 곳을 놓고 절차를 한 단계씩 따라간다. 규칙은 단순하다. 상대 목록에 이름이 없으면 그곳에 갈 수 없고, 자리가 남아 있으면 임시로 배정한다. 자리가 찼는데 더 선호되는 지원자가 오면 가장 덜 선호되는 기존 지원자가 밀려나고, 밀려난 지원자는 자기 목록의 다음 순위로 넘어간다.

끝나고 보면 다섯 명 중 네 명이 배정되고 한 명은 어디에도 가지 못한다. 프로그램 한 곳은 아무도 뽑지 못한다. 언뜻 비효율처럼 보이지만, 진행자는 어떤 조합을 시도해도 한쪽이 반드시 손해를 본다는 것을 하나씩 확인해 보인다. 남는 지원자를 어딘가에 넣으려면 다른 프로그램의 더 나은 배정을 빼앗아야 하고, 그것은 양쪽이 합의할 수 있는 거래가 아니다.

마지막으로 짚는 것이 전략적 행동의 문제다. 아무도 뽑지 못한 프로그램이 사실은 마지막 지원자도 받을 의향이 있었는데 까다로워 보이려고 목록에서 뺐다고 가정해 보면, 그 선택이 자기 발등을 찍은 셈이 된다. 목록에 남겨 두었더라면 갈 곳이 없던 지원자와 자연스럽게 이어질 수 있었기 때문이다.

주요 인사이트

• 매칭 결과가 '최선'이 아니라 '안정적'이라는 표현을 쓰는 이유가 여기서 드러난다. 모두를 만족시키는 배정이 아니라, 양쪽이 함께 이득을 보는 맞바꿈이 더는 남아 있지 않은 상태를 뜻한다.
• 지원자가 1지망을 못 받는 것 자체는 알고리즘의 실패가 아니다. 그 자리를 얻으려면 그 프로그램이 더 선호하는 지원자를 밀어내야 하는데, 그러면 프로그램 쪽이 손해를 보므로 합의 가능한 거래가 성립하지 않는다.
• 이 제도의 두 번째 성질인 '속일 이유가 없음'은 참가자에게 실용적인 조언으로 이어진다. 안 가느니 낫다고 생각하는 선택지라면 순위 아래쪽이라도 목록에 적어 두는 편이 항상 유리하다.
• 선호 목록을 짧게 줄여 협상력을 높이려는 시도는 시장 설계의 규칙에 따라 결과가 갈린다. 이 시장에서는 그런 전략이 통하지 않지만, 규칙이 다른 시장에서는 실제로 이득이 되는 경우도 있다는 점을 진행자는 함께 짚는다.
• 돈이 전혀 개입하지 않는데도 자원 배분이 이뤄진다는 점이 이 사례의 매력이다. 가격 대신 양쪽의 선호 순위가 정보로 쓰이고, 비교적 단순한 절차만으로 안정적인 배분에 도달한다.

자주 묻는 질문

관련 AI 소식