우리는 일상에서 수많은 선택과 만남을 경험합니다. 만약 인기 아이돌 그룹 멤버들이 서로 짝을 맺어야 한다면, 단순히 좋아하는 순서대로 연결하는 것이 최선일까요? 이러한 의문에 답을 제시하는 학문이 바로 매칭이론입니다. 이는 2012년 로이드 섀플리와 앨빈 로스에게 노벨 경제학상을 안겨준 분야로, 복잡한 이해관계 속에서 최적의 짝을 찾아내는 알고리즘을 연구합니다. 그 중심에는 수학자 데이비드 게일과 경제학자 로이드 섀플리가 고안한 게일-섀플리 알고리즘이 자리 잡고 있습니다.

가장 단순한 상황을 가정해 봅시다. 두 쌍의 남녀가 서로 선호하는 순위가 겹칠 때, 우리는 두 가지 매칭 방식을 생각할 수 있습니다. 하나는 인기 있는 사람끼리 맺어주는 평행 매칭이고, 다른 하나는 이를 교차하여 연결하는 교차 매칭입니다. 행복의 총량이라는 관점에서는 두 방식 모두 만족하는 사람과 그렇지 못한 사람이 생기기에 차이가 없어 보일 수 있습니다. 하지만 과학적인 관점에서 상황을 바라보면, 단순히 감정적인 선호도를 넘어 자연 현상에서 더 빈번하게 발생하는 특정 규칙이 존재함을 발견하게 됩니다.

자연에서 더 많이 관찰되는 방식은 바로 안정성을 확보한 안정 매칭입니다. 교차 매칭의 경우, 현재의 파트너보다 서로를 더 선호하는 남녀가 존재한다면 기존의 관계를 깨고 새로운 짝을 찾으려는 유인이 발생합니다. 반면 안정 매칭은 외부의 작은 교란에도 관계가 유지되는 계곡 속의 공과 같은 상태를 의미합니다. 즉, 누군가는 조금 덜 행복할지라도 전체 시스템이 붕괴되지 않고 유지될 수 있는 구조가 과학적으로는 더 중요한 가치를 지니게 되는 것입니다. 이러한 안정성은 자연 현상을 설명하는 핵심 개념입니다.

위대한 사람은 항상 한 걸음 더 나아갑니다. '왜'라는 문제를 해결했다면 이제는 '어떻게'라는 실천적인 문제에 도전할 차례입니다.

그렇다면 이러한 안정 매칭 상태에 도달하기 위한 구체적인 방법은 무엇일까요? 게일-섀플리 알고리즘은 단계별 과정을 통해 이를 해결합니다. 먼저 남성들이 자신이 가장 선호하는 여성에게 청혼하고, 여성은 제안 중 가장 마음에 드는 상대를 선택해 잠정적인 약혼 상태를 유지합니다. 이후 선택받지 못한 남성들이 다음 순위의 여성에게 다시 청혼하는 과정을 반복합니다. 이 과정에서 여성은 더 나은 상대가 나타나면 기존의 약혼을 파기할 수 있으며, 최종적으로는 모든 구성원이 더 이상 이탈할 마음이 없는 안정적인 짝을 찾게 됩니다.

이 알고리즘이 위대한 이유는 단순히 짝짓기 문제를 해결했기 때문만이 아닙니다. 관찰을 통해 현상을 파악하고, 왜 그런 일이 발생하는지 질문하며, 구체적인 해결 방안을 도출해 검증하는 과학적 사고의 정수를 보여주기 때문입니다. 수학자들은 이 알고리즘이 어떤 상황에서도 항상 안정적인 결과를 도출한다는 사실을 논리적으로 증명해 냈습니다. 결국 매칭이론은 우리 삶의 복잡한 문제들을 논리적이고 체계적인 시각으로 바라볼 때 비로소 최선의 해답을 찾을 수 있음을 시사하며, 이는 수학적 사고가 가진 진정한 힘이라 할 수 있습니다.