과학 포털 iKAOS

5 Contents

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

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

카오스재단술술과학

수학

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

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

김두얼, 한순구

카오스재단카오스강연

수학
융합

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

카오스 강연 시리즈는 '유리알 유희'라는 이름 아래 수학과 과학의 성취를 대중과 나누고자 기획되었습니다. 헤르만 헤세의 소설 제목에서 따온 이 명칭은 상아탑 속에 갇힌 학문적 성과를 세상 밖으로 끌어내어 보통 사람들의 삶 속에서 구현하려는 의지를 담고 있습니다. 수학은 단순한 계산을 넘어 현대 문명을 지탱하는 핵심적인 역할을 수행하며, 인문학과의 경계를 허무는 융합의 계기를 마련합니다. 지적 성찰과 대화가 살아 움직이는 무대를 통해 우리는 수학이 가진 진정한 가치를 재발견하게 됩니다. 많은 이들이 수학을 일상생활과는 거리가 먼, 어렵고 따분한 과목으로 여기곤 합니다. 하지만 수학적 사고는 복잡한 현대 사회를 이해하고 논리적으로 판단하는 데 필수적인 기초가 됩니다. 더하기와 빼기 같은 단순한 계산을 넘어, 세상의 이면을 관찰하고 그 속에 숨겨진 규칙을 발견하는 즐거움을 선사하기 때문입니다. 수학에 대한 막연한 거부감을 떨쳐내고 이를 친숙한 지적 탐구의 대상으로 받아들일 때, 우리는 비로소 현대 문명이 쌓아 올린 거대한 지식의 체계에 한 걸음 더 가까이 다가갈 수 있게 될 것입니다. 수학 분야에는 노벨상이 존재하지 않지만, 그에 버금가는 권위를 가진 필즈상이 4년마다 수여됩니다. 세계수학자대회는 전 세계 수학자들이 모여 학문적 성과를 공유하는 축제의 장으로, 특히 개발도상국의 젊은 수학자들을 지원하며 지식의 나눔을 실천합니다. 이러한 국제적인 교류는 수학이 특정 국가나 계층의 전유물이 아니라 인류 공동의 자산임을 보여줍니다. 수학적 성취를 사회와 나누려는 노력은 학문의 공익적 가치를 높이며, 미래 세대에게 새로운 영감과 기회를 제공하는 밑거름이 됩니다. 인류가 아주 오래전부터 직면해 온 난제 중 하나는 바로 '매칭' 문제입니다. 한정된 자원이나 인원을 어떻게 효율적이고 공정하게 배분할 것인가에 대한 고민은 현대에 이르러 수학적 모델을 통해 해결의 실마리를 찾았습니다. 2012년 노벨 경제학상을 받은 섀플리와 로스는 사실 수학적 방법론을 통해 이 문제를 해결한 학자들이었습니다. 이들의 연구는 단순한 남녀의 만남을 넘어 학교 배정이나 장기 기증 이식 등 사회 전반의 복잡한 매칭 시스템에 혁신적인 해결책을 제시하며 수학의 실천적 힘을 증명했습니다. 매칭 문제를 해결하기 위해 가장 먼저 필요한 것은 각 주체의 '선호도'에 대한 정보입니다. 누가 누구를 더 좋아하는지, 어떤 조건을 우선시하는지에 대한 데이터가 확보되어야 비로소 수학적 분석이 가능해집니다. 단순히 무작위로 짝을 짓는 것이 아니라, 개개인의 의사를 존중하면서도 전체적인 만족도를 높일 수 있는 최선의 조합을 찾아내는 것이 핵심입니다. 이는 감정적인 영역으로 치부되기 쉬운 선택의 문제를 과학적이고 체계적인 시각으로 접근하여, 모두가 납득할 수 있는 합리적인 결론을 도출하는 과정이라 할 수 있습니다. 수학적 매칭에서 가장 핵심적인 개념은 바로 '안정성'입니다. 이는 자연계의 물리적 평형 상태와도 유사한 개념으로, 외부의 작은 충격에도 쉽게 변하지 않고 유지되는 상태를 의미합니다. 불안정한 평형은 잠시 유지될 수 있으나 결국 붕괴하기 마련이지만, 안정적인 상태는 시스템 내의 구성원들이 현재의 결과에 만족하며 이탈할 동기가 없는 상태를 말합니다. 자연 현상을 관찰하여 이론을 정립하는 과학자들처럼, 매칭 문제에서도 어떤 상태가 지속 가능한 안정성을 확보하는지를 파악하는 것이 문제 해결의 결정적인 열쇠가 됩니다. 안정적인 매칭이란 구성원들이 서로 바람을 피울 기회나 동기가 없는 상태를 뜻합니다. 만약 현재의 파트너보다 서로를 더 선호하는 남녀 쌍이 존재한다면 그 시스템은 언제든 무너질 수 있는 불안정한 상태입니다. 반면, 자신이 원하는 상대가 이미 더 선호하는 파트너와 매칭되어 있다면 새로운 관계를 맺을 가능성이 차단되어 시스템은 안정적으로 유지됩니다. 섀플리와 로스의 알고리즘은 바로 이러한 안정적 매칭을 찾아내는 체계적인 방법론을 제공합니다. 이는 복잡한 이해관계 속에서도 질서를 찾으려는 수학적 노력의 결실입니다.

김민형

카오스재단카오스콘서트

수학

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

두 사람 사이의 관계에서 안정성을 결정하는 요인은 무엇일까요? 단순히 서로 짝을 짓는 것 이상의 복잡한 문제가 그 안에 숨어 있습니다. 만약 현재의 파트너보다 서로를 더 선호하는 두 사람이 존재한다면, 그 관계는 언제든 깨질 수 있는 불안정한 상태가 됩니다. 이러한 상황을 방지하고 모두가 납득할 수 있는 최선의 조합을 찾는 것이 바로 안정적 짝짓기 문제의 핵심입니다. 이론적으로는 간단해 보이지만, 실제 상황에서는 고려해야 할 변수가 매우 많습니다. 참여하는 인원이 늘어날수록 문제는 기하급수적으로 복잡해집니다. 예를 들어 남녀 각각 100명이 있는 상황에서 모든 선호도를 고려해 안정적인 짝을 찾는 것은 결코 쉬운 일이 아닙니다. 항상 안정적인 결과가 도출될 수 있는지, 혹은 그 과정이 너무 복잡해 해결이 불가능한 것은 아닌지에 대한 의문이 생기기 마련입니다. 주먹구구식 방법으로는 한계가 명확하기에, 이를 체계적으로 해결할 수 있는 수학적 방법론과 알고리즘의 등장이 절실해집니다. 게일-섀플리 알고리즘은 이러한 복잡한 문제를 순차적인 라운드 방식으로 해결합니다. 첫 번째 단계에서 모든 남성은 자신이 가장 좋아하는 여성에게 청혼을 합니다. 청혼을 받은 여성은 그중에서 자신이 가장 선호하는 남성을 선택하여 '약혼' 상태가 됩니다. 여기서 중요한 점은 이것이 최종적인 결혼이 아니라 임시적인 약혼이라는 사실입니다. 여성은 더 나은 선택지가 나타날 때까지 결정을 유보할 수 있는 권한을 가지며, 이를 통해 전체적인 안정성을 찾아갑니다. 라운드가 거듭될수록 약혼하지 못한 남성들은 자신의 선호도 명단에서 다음 순위에 있는 여성에게 청혼합니다. 이미 약혼한 여성이라 할지라도 새로 청혼한 남성이 현재의 약혼자보다 더 마음에 든다면 기존의 약혼을 파기하고 새로운 남성을 선택할 수 있습니다. 이러한 방식은 모든 남성이 청혼할 대상을 잃거나 모든 여성이 짝을 찾을 때까지 반복됩니다. 겉보기에는 냉정해 보일 수 있으나, 이는 수학적으로 가장 효율적인 매칭을 찾아가는 과정이라 할 수 있습니다. 이 알고리즘의 놀라운 점은 어떤 선호도 표가 주어지더라도 반드시 안정적 짝짓기 결과가 도출된다는 수학적 정리입니다. 인원수가 아무리 많아도 알고리즘은 결국 끝이 나며, 그 결과물에서는 서로 바람날 가능성이 있는 쌍이 존재하지 않게 됩니다. 이 단순해 보이는 원리는 경제학 및 사회학 전반에 엄청난 영향을 미쳤으며, 공로를 인정받아 노벨 경제학상까지 수상하게 되었습니다. 수천 년간 풀리지 않던 난제가 발상의 전환을 통해 명쾌하게 해결된 것입니다. 알고리즘의 구조를 살펴보면 청혼하는 주체인 남성과 선택권을 가진 여성의 역할이 극명하게 나뉩니다. 과연 이 방식은 누구에게 더 유리할까요? 주도적으로 선택하는 남성일까요, 아니면 끝까지 비교하며 최선을 고르는 여성일까요? 이에 대한 답은 수학적으로 명확히 증명되어 있습니다. 비록 증명 과정은 복잡할 수 있지만, 정답이 존재한다는 사실 자체가 흥미롭습니다. 이는 우리가 일상에서 마주하는 선택과 결정의 순간들이 수학적 논리 안에서 해석될 수 있음을 시사합니다. 헤르만 헤세의 소설 '유리알 유희'는 학문적 이상과 현실 세계 사이의 관계를 다룹니다. 고귀한 상상의 세계에만 머무는 것이 아니라, 어지러운 현실의 관계 속으로 들어가 보편적인 진리를 실천하는 것이 학자의 진정한 역할이라는 교훈을 줍니다. 안정적 짝짓기 이론 역시 추상적인 수학 공식에 그치지 않고, 실제 사회의 복잡한 이해관계를 조정하는 도구로 사용됩니다. 결국 학문이란 세상을 더 깊이 이해하고, 그 안에서 더 나은 조화를 찾아가는 끝없는 유희와 같습니다.

김민형

카오스재단카오스콘서트

수학

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

수학은 오랫동안 고립된 학문으로 여겨져 왔으나, 최근에는 상아탑을 넘어 세상과 대화하려는 시도가 늘고 있습니다. 헤르만 헤세의 소설 '유리알 유희'처럼 지적인 나눔을 통해 현실과 교류하려는 노력은 수학계에서도 중요한 흐름이 되었습니다. 혼자만의 공부에서 벗어나 다양한 분야와 소통할 때, 수학은 비로소 살아 있는 학문으로서의 가치를 증명하게 됩니다. 이러한 지적 나눔은 공부하는 이들에게 고립감을 해소해 주고 새로운 가능성을 열어 주는 소중한 기회가 됩니다. 수학의 '짝짓기 문제'는 경제학에서 매우 중요한 위치를 차지하고 있습니다. 실제로 이 주제는 노벨 경제학상 수상으로 이어질 만큼 그 가치를 인정받았습니다. 겉보기에는 단순한 짝짓기처럼 보이지만, 그 이면에는 자원을 효율적으로 배분하기 위한 정교한 수학적 알고리즘이 숨어 있습니다. 이는 구체적인 상황을 넘어 보편적인 구조를 탐구하는 수학의 특성을 잘 보여줍니다. 추상적인 수학적 관점이 현실의 복잡한 경제 문제를 해결하는 강력한 열쇠가 되는 셈입니다. 짝짓기 알고리즘은 실생활의 다양한 영역에 적용되고 있습니다. 뉴욕의 고등학교 배정 시스템이나 병원의 레지던트 배치, 심지어 장기 이식 대기자와 기증자를 연결하는 과정에서도 수학이 사용됩니다. 어떻게 하면 모든 참여자가 가장 만족할 수 있는 결과를 얻을 수 있을지를 수학적으로 증명하고 이를 실제 시스템에 도입하는 것입니다. 이는 수학이 단순히 숫자를 다루는 학문을 넘어, 사회 구성원들의 행복을 극대화하는 실천적인 도구로 활용될 수 있음을 시사합니다. 게임 이론은 현대 경제학의 근간을 이루는 수학적 이론 중 하나입니다. 영화 '뷰티풀 마인드'의 모델인 존 내쉬가 정립한 '내쉬 평형'은 개별 주체들이 서로의 전략을 고려할 때 도달하게 되는 안정적인 상태를 설명합니다. 노벨 경제학상 수상자 중 상당수가 게임 이론 분야에서 배출되었다는 사실은 수학과 경제학의 밀접한 관계를 잘 보여줍니다. 복잡한 사회적 상호작용을 수학적 모델로 분석함으로써, 우리는 인간의 의사결정 구조를 더욱 깊이 있게 이해할 수 있게 되었습니다. 데이터와 통계의 힘은 정치와 스포츠 분야에서도 혁신을 일으키고 있습니다. 미국의 선거 전문가 네이트 실버는 통계학적 방법론을 통해 50개 주의 선거 결과를 완벽하게 예측하며 세상을 놀라게 했습니다. 또한 야구계의 '머니볼' 사례처럼, 철저한 통계 분석을 통해 저평가된 선수를 발굴하고 팀을 승리로 이끄는 방식도 수학의 승리라고 할 수 있습니다. 과거의 방대한 데이터를 가공하고 조건부 확률을 적용하여 미래를 예측하는 일은 현대 사회에서 수학이 가진 가장 강력한 힘 중 하나입니다. 현대 마케팅 분야에서도 수학적 알고리즘의 중요성은 날로 커지고 있습니다. 특히 소셜 미디어 시대에 파워 블로거의 영향력을 분석하고, 제한된 자원으로 홍보 효과를 극대화할 수 있는 대상을 찾는 과정에 그래프 이론과 알고리즘이 활용됩니다. 단순히 친구가 많은 사람을 찾는 것이 아니라, 네트워크 구조 내에서 정보의 확산 기댓값이 가장 높은 지점을 수학적으로 찾아내는 것입니다. 이러한 연구는 기업의 마케팅 전략을 더욱 정교하게 만들며 사회적 현상을 수치화하여 분석하는 토대가 됩니다. 수학 교육의 본질은 단순한 문제 풀이의 반복이 아니라, 논리적 사고를 통해 세상을 이해하는 능력을 기르는 데 있습니다. 많은 학생이 수학을 실생활과 동떨어진 과목으로 느끼며 어려움을 겪지만, 수학은 경제, 정치, 스포츠, 마케팅 등 우리 삶의 모든 곳에 스며들어 있습니다. 수학을 하나의 놀이이자 세상을 바라보는 창으로 받아들일 때, 학생들은 비로소 수학의 진정한 가치를 발견할 수 있습니다. 융합의 시대에 수학적 사고력은 미래를 설계하는 가장 기초적이면서도 강력한 무기가 될 것입니다.

김민형, 박형주

카오스재단카오스콘서트

수학