게일-섀플리

3 Contents

[카오스 술술수학] 수학, 사랑을 결정하다? 두근두근 짝짓기 알고리즘

우리는 일상에서 수많은 선택과 만남을 경험합니다. 만약 인기 아이돌 그룹 멤버들이 서로 짝을 맺어야 한다면, 단순히 좋아하는 순서대로 연결하는 것이 최선일까요? 이러한 의문에 답을 제시하는 학문이 바로 매칭이론입니다. 이는 2012년 로이드 섀플리와 앨빈 로스에게 노벨 경제학상을 안겨준 분야로, 복잡한 이해관계 속에서 최적의 짝을 찾아내는 알고리즘을 연구합니다. 그 중심에는 수학자 데이비드 게일과 경제학자 로이드 섀플리가 고안한 게일-섀플리 알고리즘이 자리 잡고 있습니다. 가장 단순한 상황을 가정해 봅시다. 두 쌍의 남녀가 서로 선호하는 순위가 겹칠 때, 우리는 두 가지 매칭 방식을 생각할 수 있습니다. 하나는 인기 있는 사람끼리 맺어주는 평행 매칭이고, 다른 하나는 이를 교차하여 연결하는 교차 매칭입니다. 행복의 총량이라는 관점에서는 두 방식 모두 만족하는 사람과 그렇지 못한 사람이 생기기에 차이가 없어 보일 수 있습니다. 하지만 과학적인 관점에서 상황을 바라보면, 단순히 감정적인 선호도를 넘어 자연 현상에서 더 빈번하게 발생하는 특정 규칙이 존재함을 발견하게 됩니다. 자연에서 더 많이 관찰되는 방식은 바로 안정성을 확보한 안정 매칭입니다. 교차 매칭의 경우, 현재의 파트너보다 서로를 더 선호하는 남녀가 존재한다면 기존의 관계를 깨고 새로운 짝을 찾으려는 유인이 발생합니다. 반면 안정 매칭은 외부의 작은 교란에도 관계가 유지되는 계곡 속의 공과 같은 상태를 의미합니다. 즉, 누군가는 조금 덜 행복할지라도 전체 시스템이 붕괴되지 않고 유지될 수 있는 구조가 과학적으로는 더 중요한 가치를 지니게 되는 것입니다. 이러한 안정성은 자연 현상을 설명하는 핵심 개념입니다. 그렇다면 이러한 안정 매칭 상태에 도달하기 위한 구체적인 방법은 무엇일까요? 게일-섀플리 알고리즘은 단계별 과정을 통해 이를 해결합니다. 먼저 남성들이 자신이 가장 선호하는 여성에게 청혼하고, 여성은 제안 중 가장 마음에 드는 상대를 선택해 잠정적인 약혼 상태를 유지합니다. 이후 선택받지 못한 남성들이 다음 순위의 여성에게 다시 청혼하는 과정을 반복합니다. 이 과정에서 여성은 더 나은 상대가 나타나면 기존의 약혼을 파기할 수 있으며, 최종적으로는 모든 구성원이 더 이상 이탈할 마음이 없는 안정적인 짝을 찾게 됩니다. 이 알고리즘이 위대한 이유는 단순히 짝짓기 문제를 해결했기 때문만이 아닙니다. 관찰을 통해 현상을 파악하고, 왜 그런 일이 발생하는지 질문하며, 구체적인 해결 방안을 도출해 검증하는 과학적 사고의 정수를 보여주기 때문입니다. 수학자들은 이 알고리즘이 어떤 상황에서도 항상 안정적인 결과를 도출한다는 사실을 논리적으로 증명해 냈습니다. 결국 매칭이론은 우리 삶의 복잡한 문제들을 논리적이고 체계적인 시각으로 바라볼 때 비로소 최선의 해답을 찾을 수 있음을 시사하며, 이는 수학적 사고가 가진 진정한 힘이라 할 수 있습니다.

[카오스 술술수학] 수학, 사랑을 결정하다? 두근두근 짝짓기 알고리즘
카오스재단술술과학
  • 수학

[강연] 게임이론 - 인간의 행동을 예측하다 (5) _ by한순구 | 2018 봄 카오스 강연 '모든 것의 수數다' 6강 | 6강 ⑤

게임이론은 내쉬 이후 약 60년의 역사를 가진 비교적 젊은 학문으로, 여전히 그 범위와 깊이가 확장되고 있습니다. 핵전쟁이나 국가 간 정상회담처럼 반복되지 않는 단 한 번의 사건에 적용될 때, 수치적 검증이 어렵다는 비판을 받기도 합니다. 하지만 이는 데이터의 부재 때문이지 이론의 무용함을 의미하지는 않습니다. 오히려 복잡한 이해관계 속에서 핵심 변수를 파악하고 전략적 사고의 틀을 제공한다는 점에서 게임이론은 현대 사회의 중요한 의사 결정 도구로 자리 잡고 있습니다. 추상적인 논의를 넘어 실생활에 적용되는 대표적인 사례로 게일-섀플리 알고리즘을 들 수 있습니다. 이 알고리즘은 두 집단 사이의 선호도를 바탕으로 최적의 짝을 연결해 주는 방식입니다. 단순히 무작위로 연결하는 것이 아니라, 이미 정해진 짝보다 서로를 더 선호하는 새로운 조합이 나타나지 않도록 '안정적 매칭'을 찾는 것이 핵심입니다. 이러한 논리적 구조는 복잡한 이해관계가 얽힌 사회적 자원 배분 문제에서 불필요한 갈등과 불확실성을 제거하는 데 탁월한 성능을 발휘합니다. 매칭 이론은 노벨 경제학상을 받을 만큼 그 가치를 인정받은 분야입니다. 우리가 원하는 최상의 직장이나 학교에 모두가 갈 수는 없지만, 시스템에 대한 납득을 끌어내는 것이 중요합니다. 만약 부적절한 매칭이 이루어진다면 학생이 반수를 선택하거나 신입 사원이 조기에 퇴사하는 등 막대한 사회적 비용이 발생하게 됩니다. 효율적인 매칭 시스템은 구성원들이 주어진 조건 내에서 더 이상의 나은 선택지가 없음을 인지하게 함으로써 사회 전체의 안정성과 효율성을 높이는 역할을 합니다. 게임이론의 또 다른 핵심 개념인 '커미트먼트'는 약속을 지키겠다는 의지와 보복의 실행력을 의미합니다. 이는 역사를 해석하는 새로운 시각을 제공하기도 합니다. 영국의 명예혁명 당시, 의회는 왕이 재산권을 침해할 경우 반드시 처벌한다는 강력한 커미트먼트를 보여주었습니다. 왕은 이러한 위협이 실재함을 깨닫고 의회와의 계약을 준수하게 되었으며, 이는 결과적으로 민주주의와 의회 정치의 기틀을 마련하는 계기가 되었습니다. 전략적 상호작용이 역사의 흐름을 바꾼 대표적인 사례입니다. 현대 게임이론의 기틀을 마련한 존 내쉬는 수학적으로 균형의 존재를 입증하며 경제학의 패러다임을 바꾸었습니다. 그의 '내쉬 균형'은 단편적인 사례 분석에 머물던 전략 연구를 체계적인 시스템으로 격상시켰습니다. 비록 오랜 시간 조현병으로 고통받았지만, 그의 이론은 멈추지 않고 발전하여 오늘날 거의 모든 경제 활동의 기초가 되었습니다. 내쉬의 업적은 인간의 경쟁과 협력이라는 복잡한 행동 양식을 논리적이고 과학적인 언어로 풀어냈다는 점에서 영원히 기억될 것입니다.

[강연] 게임이론 - 인간의 행동을 예측하다 (5) _ by한순구 | 2018 봄 카오스 강연 '모든 것의 수數다' 6강

김두얼, 한순구

카오스재단카오스강연
  • 수학
  • 융합

[강연] 2012 카오스 콘서트 '유리알유희' 4강 | 3강 ②

수학자 김민형 교수는 독특한 교육적 배경을 가지고 있습니다. 초중고 졸업장 없이 홈스쿨링을 거친 그는 집에서 음악을 듣고 자유롭게 시간을 보냈던 경험이 수학적 사고의 밑거름이 되었다고 회상합니다. 물론 입시 공부나 사회적 관계 형성에서 어려움을 겪기도 했지만, 이러한 자유로운 환경은 그에게 선명한 기억과 독창적인 시각을 선물했습니다. 제도권 교육의 틀 밖에서 보낸 시간은 그가 수학이라는 심오한 세계를 탐구하는 데 있어 자신만의 속도를 유지하게 해준 소중한 자산이 되었습니다. 한국과 영국의 교육 시스템은 서로 다른 장단점을 지니고 있습니다. 한국은 두꺼운 교재를 바탕으로 철저한 연습과 기초 지식 습득을 강조하는 반면, 영국은 대표 강의 위주로 진행하며 학생 스스로 문제를 해결하는 독립적인 사고력을 중시합니다. 한국 학생들은 탄탄한 기초를 갖추고 있지만 임기응변이 다소 부족할 수 있고, 영국 학생들은 창의적 의지는 강하나 기초 계산 능력이 떨어지는 경우가 있습니다. 두 방식 중 어느 하나가 절대적으로 우월하기보다는 상황에 따라 필요한 기술이 다르다는 점을 이해하는 것이 중요합니다. 한국 학생들의 뛰어난 실력에도 불구하고 필즈상 수상자가 부재했던 이유는 연구 중심 대학의 역사가 짧기 때문입니다. 과거의 교육은 지식 전달 위주였으며, 창의적인 연구 문화가 정착된 지는 얼마 되지 않았습니다. 하지만 현재의 젊은 인재들은 과거보다 훨씬 똑똑하며 세계적인 수준의 경쟁력을 갖추고 있습니다. 이들이 본격적으로 학계에서 활동하며 연구 성과를 쌓아감에 따라, 자연스럽게 세계적인 권위의 상들도 뒤따라올 것입니다. 수학적 역량은 이미 충분하며 이제는 그 결실을 기다리는 단계에 와 있습니다. 학문의 발전은 특정 지역에 집중되기도 하고 전 세계로 분산되기도 합니다. 과거 유럽에서 미국으로, 다시 아시아로 학문의 중심지가 이동하는 경향이 있지만, 중요한 것은 각 나라가 자신만의 특성을 살려 세계 수학계에 기여하는 것입니다. 중앙화된 시스템은 효율적인 교류를 가능케 하고, 분산된 연구는 다양성을 보장합니다. 수학자들은 서로 협조하고 보완하며 학문의 지평을 넓혀갑니다. 세계가 서로 다른 강점을 가지고 발전할 때 수학이라는 거대한 지도는 더욱 풍성하게 채워질 수 있습니다. 순수 수학과 응용 수학, 혹은 융합 학문 사이에서 고민하는 이들에게 중요한 것은 자신의 분야에 충실하면서도 타 학문에 대한 열린 마음을 갖는 것입니다. 추상적인 개념을 다루는 순수 수학은 그 자체로 깊은 가치가 있으며, 다른 분야와 결합할 때 새로운 통찰을 제공합니다. 자신이 하는 일에 전문성을 갖추되 다른 학문의 '팬'이 되어 응원하다 보면 자연스럽게 융합의 기회가 찾아옵니다. 학문의 경계를 허무는 노력은 거창한 선택이 아니라, 주변의 다양한 현상에 호기심을 갖는 것에서 시작됩니다. 수학 실력은 재능의 차이가 있을 수 있으나 기본적으로 투입한 시간에 비례하여 성장하는 함수와 같습니다. 특히 한국 학생들은 고등학교 시절 이미 세계적인 수준의 수학적 훈련을 거치며 높은 평균 실력을 보유하고 있습니다. 스스로 수학을 못 한다고 자책하기보다 자신이 이미 가진 탄탄한 기초를 어떻게 활용할지 고민해야 합니다. 컴퓨터공학이나 생명공학 등 어떤 분야를 전공하더라도 수학적 사고방식은 문제를 해결하는 강력한 무기가 됩니다. 자신감을 가지고 꾸준히 시간을 투자한다면 수학은 인생의 자산이 될 것입니다. 게일-섀플리 알고리즘과 같은 수학적 모델은 복잡한 사회 현상을 단순화하여 핵심적인 구조를 들여다보게 해줍니다. 짝짓기 문제와 같은 인류의 오랜 난제를 수학적으로 분석하는 과정은 현실의 모든 문제를 즉각 해결해주지는 못하지만, 현상을 바라보는 통찰력을 획기적으로 높여줍니다. 핵심적인 부분을 파악해 모델을 만들고 이를 점차 정교하게 발전시켜 나가는 과정이 바로 수학적 모델링의 묘미입니다. 이러한 시도는 현대 문명 곳곳에서 보이지 않는 힘으로 작용하며 우리의 삶을 더욱 효율적으로 설계하는 데 기여하고 있습니다.

[강연]  2012 카오스 콘서트 '유리알유희' 4강

김민형, 박형주

카오스재단카오스콘서트
  • 수학