박종하의 <다르게 생각하는 연습>에는 이런 이야기가 나온다. 콜럼버스가 대서양을 건너기로 마음먹은 계기는 계산을 잘못했기 때문이라는 것이다. 주경철이 <그해, 역사가 바뀌다>에서 설명하듯, 콜럼버스의 시대에 지구가 둥글다는 것은 상식이었다. 하지만 지구의 크기에 대해서는 의견이 엇갈렸다. 콜럼버스는 프톨레마이오스의 주장을 믿었다. 그 주장에 따르면 지구의 둘레는 약 2만 9000km다. 이를 토대로 콜럼버스는 인도까지의 거리를 4345km라고 계산하고 과감하게, 인도를 향해 바다를 가로질러 갈 생각을 한 것이다.
불확실성에 도전하라
콜럼버스의 계산보다 인도는 사실 6배나 더 멀리 있었다. 콜럼버스의 항해에 포르투갈이 지원을 거부한 이유는 지구의 둘레에 대한 견해가 달랐기 때문이었다. 포르투갈은 지구의 둘레에 관한 에라토스테네스의 견해를 지지했다. 박종하의 책에는 40,000km라고 나오지만, 사실 에라토스테네스의 계산은 약 46,000km다. 어쨌든, 에라토스테네스의 계산이 지구의 크기에 훨씬 더 근접한 값이다. 즉, 포르투갈은 타당한 믿음에 근거하여 콜럼버스의 벤처에 투자하기를 거부했다.
박종하는 콜럼버스처럼 무식하게 도전하라고 말한다. 불확실성에 도전하지 않으면 아무것도 얻을 수 없다는 것이다. 성공하는 사람들은 운이 좋은 경향이 있다. 영국의 심리학자 리처드 와이즈만은 운이 좋은 사람들의 특징을 연구했다. 그의 연구 결과에 따르면, 운이 좋은 사람들은 불확실성을 즐기는 공통점이 있었다. 확실하게 계산이 가능한 일에는 대박도 없고 큰 기회도 없지만, 불확실한 세계에 도전하다 보면 운이 따르게 된다는 것이다.
네덜란드의 사회학자 홉스테드 교수는 불확실성에 대한 각 사회의 태도를 연구했다. 그는 이를 불확실성 기피 지수(Uncertainty Avoidance Index)로 정리했는데, 한국은 이 지수가 상당히 높다고 한다. OECD 혁신역량 순위가 높은 스웨덴, 덴마크, 미국 등은 불확실성 기피 지수가 낮다고 한다. 홉스테드 교수는 이렇게 정리했다. 불확실함을 피해 확실한 현재에 안주하면 미래가 불확실해진다. 그 반대로 불확실한 현재를 견뎌내면 미래가 확실해진다는 것이다.
그런데 나는 여러 권을 책을 동시에 읽는 버릇이 있다. 나는 박종하의 책과 동시에 김민형의 <수학이 필요한 순간>을 읽고 있었다. 산수 수준에서 위상수학의 맛보기를 보여주는 등, 수학에 관한 흥미로운 이야기 일곱 가지가 실려 있다. 그중 하나가 짝짓기에 관련한 내용이다. 짝짓기 문제는 다양한 상황에서 발생한다. 앨빈 로스는 짝짓기 문제만을 다룬 <매칭>이란 책을 내기도 했다. (이 책도 예전에 읽고 말았다.)
게일-섀플리 알고리즘
앨빈 로스의 주 종목이었던 장기 기증자와 수혜자의 짝짓기 외에도, 학교와 학생, 회사와 구직자, 그리고 남녀 간의 결혼이 대표적인 짝짓기의 사례일 것이다. 짝짓기와 관련해서는 데이비드 게일과 로이드 섀플리가 고안한 게일-섀플리 알고리즘이라는 것이 유명하다. 잠정 수락(deferred acceptance) 알고리즘이라고도 불리는 이 방법을 사용하면, 어떤 선호도가 주어지더라도 깨지지 않고 유지되는 안정적인 짝짓기 해를 구할 수 있다.
그 방법은 다음과 같다. 김민형의 책에 있는 예를 들어 설명하겠다. 여자 A, B, C, D, 그리고 남자 1, 2, 3, 4가 있고, 그들의 상대에 대한 선호도가 다음과 같다.
남자 1: A-B-C-D
남자 2: B-D-C-A
남자 3: B-D-A-C
남자 4: A-D-B-C
여자 A: 3-2-1-4
여자 B: 4-3-1-2
여자 C: 2-3-1-4
여자 D: 2-1-3-4
어쩐지 내가 남자4인 것 같아 불안하지만, 게일-섀플리 해를 구해보자. 남자가 여자에게 구혼하고, 여자는 자신의 선호도에 따라 승낙 또는 거절을 하는 방식으로 진행한다. 첫 라운드에서 우선 남자 1과 4는 여자 A에게, 남자 2와 3은 여자 B에게 구혼한다. 제1 지망에 대시하는 것이다. 여자 A는 남자 1과 4의 구혼을 받았는데, 4보다는 1을 선호하므로, 1의 구혼을 받아들인다. 마찬가지로, 여자 B는 3과 짝지어진다.
(A, 1)과 (B, 3)의 짝이 탄생했으므로, 이들을 제외하고 다음 라운드로 진행한다. 남자 2는 남은 여자들 중 가장 선호도가 높은 D에게 청혼하는데, 남자 4 역시 남은 여자들 중에서는 D를 가장 선호하므로 그녀에게 대시한다. 여자 D는 남자 2와 4 중에서 2를 선호하므로 남자 2와 맺어지게 된다. 그렇게 되면 (D, 2)의 쌍이 탄생한다.
이 알고리즘이 '잠정 수락' 알고리즘이라 불리는 이유는 그다음 단계 때문이다. 아직도 짝이 안 지어진 것은 남자 4와 여자 C다. 남자 4는 선호도 1, 2순위에서 구혼에 실패하였으므로 선호도 3순위인 여자 B에게 청혼할 차례다. 여자 B는 현재 남자 3과 짝지어져 있지만, 남자 4에 대한 선호가 더 높으므로 짝을 갈아타게 된다. 그래서 (B, 4)가 짝지어지고, 남자 3이 탈락하게 된다. 탈락한 남자 3은 자신의 차순위 선호 대상인 여자 D에게 청혼하지만, 그녀는 자신의 최선호 대상인 남자 2와 이미 짝지어져 있다. 따라서 남자 3은 선호도 3위인 여자 A에게 청혼해서 성공한다. 여자 A에게는 이미 짝지어져 있던 남자 1보다 새로 구혼해온 남자 3이 더 나은 선택이기 때문이다.
이제 탈락한 남자 1이 자신의 2순위인 여자 B에게 대시하지만, 그녀는 자신의 선호도 1순위인 남자 4와 짝지어져 있다. 남자 1은 다음 순위인 여자 C에게 대시하고, 여자 C는 짝이 없으므로 구혼을 받아들인다. 이제 모든 짝이 완성된다. (A, 3), (B, 4), (C, 1), (D, 2).
이렇게 구해진 네 개의 쌍이 안정적인 이유는, 짝지어진 각자가 자신의 선호도 순위의 위쪽 상대와 맺어지는 방법이 없기 때문이다. 예컨대 남자 2는 현재의 짝인 D보다는 여자 B를 더 좋아하기는 하지만, 여자 B는 자신의 최선호 상대인 남자 4와 맺어져 있기 때문에 현재의 매칭 상태를 무너뜨릴 이유가 없다. 이런 식으로 검증해 보면 현재의 상태는 '내부로부터 무너지지 않는' 안정한 상태임을 확인할 수 있다.
용기 있는 자가 미인을 얻는 수학적 이유
그런데 게일-섀플리의 해가 여러 개인 경우가 있다. 다음의 사례를 보자. 역시 책에서 가져왔다.
남자 1: A-B-C
남자 2: B-C-A
남자 3: C-A-B
여자 A: 2-3-1
여자 B: 3-1-2
여자 C: 1-2-3
앞의 규칙대로 남자가 대시하는 경우를 계산해보자. 남자 1, 2, 3은 각각 여자 A, B, C에게 구혼하고, 여자들은 선택의 여지가 하나뿐이기 때문에 구혼을 승낙하게 된다. (1, A), (2, B), (3,C)의 짝짓기가 되는데, 남자들에게는 최선이지만, 여자들은 각자 자신이 제일 싫어하는 짝과 맺어지고 말았다.
규칙을 바꿔보자. 여자가 구혼하고 남자가 가부를 결정한다. 여자 1, 2, 3은 각각 남자 2, 3, 1에게 구혼하고, 남자들은 선택의 여지가 하나뿐이므로 승낙, (A, 2), (B, 3), (C, 1)의 짝이 탄생한다. 이번에는 앞의 경우와 정반대의 결과다. 여자들은 자신의 최선호 상대와 맺어졌지만, 남자들은 최후순위 상대와 맺어졌다.
게일-섀플리 이야기를 길게 한 이유는 이거다. 먼저 대시하는 자가 유리하다는 결론을 수학-경제학 이론이 지지한다는 사실을 확인하지 않았나? 먼저 대시해야 하는 사람은 불안하다. 불확실한 상태에 자신을 던져야 하기 때문이다. 하지만 그 열매는 달다. 리처드 와이즈만의 결론, 즉 불확실성에 도전하는 사람들이 대박을 터뜨린다는 결론과 같다. 역시 독서는 즐겁다.