해럴드 쿤(Harold W. Kuhn)

해럴드 쿤은 1925년 캘리포니아주 샌타모니카에서 태어났습니다. 그가 수학자가 된 1940년대 말 미국에서는 전쟁이 남긴 물음 하나가 수학의 새 분야들을 낳고 있었습니다. 한정된 비행기와 연료와 사람을 어떻게 나누어야 가장 좋은가. 1944년 폰 노이만과 경제학자 모르겐슈테른은 『게임 이론⁠(game theory)⁠과 경제 행동』으로 이해가 엇갈리는 사람들의 선택을 수학으로 다루기 시작했고, 1947년 공군의 단치히는 선형 계획법⁠(linear programming)⁠과 그것을 푸는 단체법⁠(simplex method)⁠을 만들었습니다. 해군 연구청(ONR) 같은 군의 연구 기관이 이런 수학에 연구비를 대던 시절, 프린스턴의 작은 연구 모임에서 쿤은 이 두 분야를 최적화의 한 이론으로 묶는 일을 거들었습니다.

나이 세 ·

그는 캘리포니아 공과대학에서 공부하다 2차 세계대전 중 육군에 들어갔고, 군은 그에게 일본어를 가르쳐 통역 요원으로 길렀습니다. 새 언어를 문법책과 사전으로 익히는 일에 이때 익숙해진 셈인데, 이 경험은 뒤에 뜻밖의 곳에서 쓰입니다. 1947년 졸업한 뒤 프린스턴 대학원에 들어가 위상수학자 랠프 폭스의 지도로 군을 연구해 1950년 박사 학위를 받았습니다. 생성원과 관계로 주어진 군에서 부분군⁠(subgroup)⁠들이 어떤 모양인지를 다루는 순수한 대수학이었습니다.

그러는 사이 그의 진로를 바꾼 일이 일어났습니다. 1948년 봄 단치히가 폰 노이만을 만나러 프린스턴에 왔고, 수학과의 앨버트 터커가 그를 기차역까지 태워 주며 선형 계획법 이야기를 들었다고 전합니다. 곧 터커는 해군 연구청의 지원을 받아 선형 계획법과 게임 이론의 관계를 연구하는 모임을 꾸렸고, 대학원생 데이비드 게일과 쿤이 첫 연구원이 되었습니다. 1951년 세 사람은 선형 계획의 쌍대성⁠(duality)⁠ 정리를 증명했습니다. 빵과 과자를 구워 이윤을 가장 크게 하려는 제과점이 있다고 합시다. 밀가루와 설탕은 정해진 양만 있습니다. 이제 한 상인이 그 밀가루와 설탕을 통째로 사들이려 하는데, 제과점이 거절하지 못하도록 빵 하나, 과자 하나를 만드는 데 드는 재료의 값이 그 제품의 이윤보다 적지 않게 값을 매기되 전체 지불액은 가장 작게 하려 합니다. 두 문제 모두 조건을 만족하는 답이 하나라도 있으면, 제과점의 최대 이윤과 상인의 최소 지불액은 언제나 같다는 것이 쌍대성입니다. 게일, 쿤, 터커는 두 사람이 서로 상대의 몫을 빼앗는 영합 게임⁠(zero-sum game)⁠의 최소최대 정리⁠(minimax theorem)⁠가 바로 이 쌍대성과 같은 내용임을 보였습니다(쌍대성).

같은 무렵 쿤은 게임을 적는 방법 자체를 새로 세웠습니다. 폰 노이만과 모르겐슈테른은 게임을 갈래 길이 뻗어 나가는 나무로 그렸는데, 포커처럼 상대의 패가 가려진 게임을 나무로 적으려면 '나는 지금 이 갈래들 가운데 어디에 있는지 모른다'는 것을 나타내야 합니다. 쿤은 한 사람이 서로 구별하지 못하는 자리들을 한데 묶은 것을 '정보 집합⁠(information set)⁠'이라 부르고, 1950년과 1953년 논문에서 임의의 나무 위에서 이 개념을 다듬었습니다. 이것이 오늘날의 확장형 게임입니다. 그의 정리에 따르면, 자기가 전에 알았던 것과 한 일을 잊지 않는 사람(완전 회상⁠, perfect recall⁠)에게는 게임 전체의 작전표를 통째로 제비뽑는 전략과, 정보 집합에 이를 때마다 그 자리에서 따로 주사위를 던지는 훨씬 단순한 전략이 똑같은 결과를 냅니다. 또 정보가 모두 드러난 유한 게임에는 확률⁠(probability)⁠을 섞을 필요 없는 균형 전략이 늘 있다는 것도 보였는데, 체르멜로가 1913년 체스를 두고 보인 사실을 넓힌 것입니다.

그는 이론을 시험할 작은 게임도 만들었습니다. 오늘날 '쿤 포커'라 불리는 이 게임에는 카드가 J, Q, K 세 장뿐이고, 두 사람이 한 장씩 받아 한 번만 걸기를 주고받습니다. 쿤은 이 게임을 끝까지 풀어, 균형에서 먼저 두는 사람이 가장 약한 J를 들고도 정해진 비율로 허세를 부려야 하며 그래도 한 판에 평균⁠(mean)⁠ 1/18만큼 잃는다는 것을 보였습니다. 허세가 속임수가 아니라 계산된 최선의 일부라는, 폰 노이만이 강조한 점을 손으로 확인할 수 있는 예였습니다. 쿤 포커는 지금도 불완전 정보 게임을 푸는 알고리즘⁠(algorithm)⁠의 첫 시험 문제로 쓰입니다.

1951년 쿤과 터커는 「비선형 계획」에서 부등식 제약 아래의 최적화 조건을 내놓았습니다. 등식 제약 아래의 최댓값에서는 라그랑주가 보였듯 목적 함수⁠(function)⁠의 기울기⁠(slope)⁠가 제약 함수들의 기울기의 일차 결합이 됩니다. 울타리가 둘러진 땅에서 가장 높은 곳을 찾는다고 해 봅시다. 가장 높은 곳은 땅 한가운데의 봉우리이거나(그곳에서는 기울기가 0입니다) 울타리 위의 한 점인데, 울타리 위라면 오르막 방향이 울타리 바깥을 곧장 가리켜야 합니다. 그렇지 않으면 울타리를 따라 더 오를 수 있으니까요. 위의 식이 이 말을 옮긴 것입니다. 제약 $g_i(x) \le 0$마다 수 $\lambda_i$가 붙는데, 울타리는 밀어낼 뿐 끌어당기지 않으므로 $\lambda_i \ge 0$이고, 닿지 않은 울타리는 아무 역할이 없으므로 $\lambda_i g_i = 0$입니다. 이것은 가장 높은 곳이 반드시 만족해야 하는 조건(필요조건⁠, necessary condition⁠)이고, 울타리가 뾰족하게 꺾이는 점 같은 예외를 막는 가벼운 가정이 필요합니다. 거꾸로 이 조건을 만족한다고 가장 높은 곳이라는 보장은 없지만, 땅의 모양이 볼록한 경우(목적 함수가 오목하고 제약 함수들이 볼록할 때)에는 충분조건⁠(sufficient condition)⁠도 됩니다. 뒤에 알고 보니 시카고 대학의 윌리엄 카루시가 1939년 석사 논문에서 같은 조건을 얻어 두었고, 1970년대에 쿤이 이 사실을 널리 알리면서 오늘날에는 카루시–쿤–터커(KKT) 조건이라 부릅니다(라그랑주 승수법). 이 조건은 기계 학습⁠(machine learning)⁠의 서포트 벡터 머신⁠(support vector machine)⁠부터 경제학의 소비자 이론까지 제약 있는 최적화가 있는 곳마다 쓰입니다.

1952년 필라델피아 근교의 브린마 칼리지로 옮긴 쿤은 배정 문제를 붙들었습니다. 일꾼 $n$명과 일 $n$가지가 있고, 누가 어떤 일을 하면 드는 비용이 표로 주어져 있습니다. 행마다, 열마다 칸을 하나씩 골라 비용의 합을 가장 작게 하는 문제인데, 고르는 방법은 $n!$가지라 스무 명이면 2×10¹⁸가지가 넘습니다. 그는 쾨니그 데네시의 1936년 책에서, 수가 적힌 행렬⁠(matrix)⁠로 쾨니그의 정리⁠(Kőnig's theorem)⁠를 넓힌 에게르바리 예뇌의 1931년 논문을 알게 되었습니다. 논문은 헝가리어였습니다. 쿤의 회고에 따르면 그는 1953년 헝가리어 문법책과 큰 사전을 들고 스스로 헝가리어를 익혀 이 논문을 번역했습니다.

거기서 얻은 방법은 이렇습니다. 어느 배정이든 각 행과 각 열에서 칸을 정확히 하나씩 쓰므로, 한 행 전체에서 같은 수를 빼도 어떤 배정이 가장 좋은지는 바뀌지 않습니다. 그래서 모든 수가 0 이상으로 남도록 행과 열에서 수를 빼 0을 만들어 갑니다. 서로 다른 행과 열에 있는 0을 $n$개 고를 수 있으면, 그 배정의 비용은 0이고 음수는 없으니 그것이 가장 좋은 배정입니다. 고를 수 있는지는 쾨니그의 정리가 알려 줍니다. 서로 다른 행과 열에서 고를 수 있는 0의 최대 개수는 모든 0을 덮는 데 필요한 가로줄과 세로줄의 최소 개수와 같습니다(홀의 결혼 정리). 줄이 $n$개보다 적게 필요하면, 덮이지 않은 수 가운데 가장 작은 것만큼 다시 조정해 새 0을 만들고 되풀이합니다. 쿤은 1955년 해군 연구청의 학술지에 이것을 발표하며 두 헝가리 수학자를 기려 헝가리안 방법이라 불렀습니다. 행과 열에서 뺀 수들은 선형 계획의 쌍대 문제⁠(dual problem)⁠의 답, 곧 일꾼과 일에 매긴 '가격'이 됩니다. 1957년 제임스 멍크리스는 이 방법이 $n$의 다항식⁠(polynomial)⁠만큼의 걸음 안에 끝난다는 것을 보였습니다(점근 표기법⁠(asymptotic notation)⁠).

이야기에는 뒤늦은 반전이 있습니다. 2000년대에 들어 프랑스의 프랑수아 올리비에가 야코비의 유고에서 사실상 헝가리안 방법과 같은 절차를 찾아냈습니다. 1851년 세상을 떠난 야코비의 라틴어 글이 1890년에 출판되었던 것입니다. 쿤은 말년에 강연으로 이 발견을 직접 알렸습니다. 에게르바리, 카루시, 야코비까지, 쿤은 자기 이름이 붙은 결과의 앞사람들을 스스로 찾아 세상에 알리는 일을 여러 번 했습니다. 1968년에는 브라우어르의 고정점⁠(fixed point)⁠을 실제로 계산하는 방법도 내놓았습니다. 삼각형을 작은 삼각형들로 쪼개고 꼭짓점⁠(vertex)⁠마다 규칙에 따라 1, 2, 3의 딱지를 붙이면 세 딱지를 모두 가진 작은 삼각형이 반드시 있다는 슈페르너의 보조정리⁠(lemma)⁠를, 문을 따라 방에서 방으로 걸어가 그런 삼각형을 찾아내는 절차로 바꾼 것입니다. 그 삼각형이 고정점의 근삿값입니다.

1959년 쿤은 프린스턴으로 돌아와 1995년 은퇴할 때까지 수학과와 경제학과에서 가르쳤습니다. 대학원 시절 동료였던 존 내시가 오랜 정신 질환을 앓는 동안 곁을 지켰고, 1994년 내시가 노벨 경제학상을 받을 때 그 업적을 기리는 노벨 세미나를 이끌었습니다. 2002년에는 내시의 논문을 모은 책을 실비아 네이사와 함께 엮었습니다. 1950년대에 터커와 함께 엮은 『게임 이론에 대한 기여』 연작에는 섀플리의 섀플리 값⁠(Shapley value)⁠을 비롯한 초기 게임 이론의 고전들이 실렸습니다. 1980년 게일, 터커와 함께 존 폰 노이만 이론상을 받았고, 2014년 뉴욕에서 세상을 떠났습니다. 헝가리안 방법은 지금도 영상 속 물체를 프레임마다 짝지어 추적하는 일부터 택시 배차까지 쓰이고, 확장형 게임의 틀은 2010년대 사람을 이긴 포커 인공지능⁠(artificial intelligence)⁠들이 계산한 게임 나무의 언어입니다.

이어지는 곳. 배정 문제는 그래프의 매칭⁠(matching)⁠ 문제이고, 그 뿌리는 홀의 결혼 정리와 필립 홀에 있습니다. 같은 매칭의 세계에서 선호가 있는 짝짓기를 다룬 것이 게일과 섀플리의 안정 매칭⁠(stable matching)⁠이고, 네트워크로 무엇을 얼마나 보낼지는 최대 흐름 최소 절단 정리⁠(max-flow min-cut theorem)⁠가 다룹니다. 배정 문제를 흙더미 옮기기로 넓히면 칸토로비치의 최적 수송⁠(optimal transport)⁠이 되고, 쿤–터커 조건의 계산은 경사 하강법⁠(gradient descent)⁠과 뉴턴 방법⁠(Newton's method)⁠ 같은 반복법으로 이어집니다. 최적화 전체의 큰 그림은 가장 좋은 것 고르기에 있습니다.

관계.

• 영향을 받음 쾨니그 데네시 — 쾨니그의 1936년 그래프 이론⁠(graph theory)⁠ 책에서 매칭의 정리와 에게르바리의 논문을 알게 되었고, 두 사람의 생각으로 만든 배정 알고리즘에 '헝가리안 방법'이라는 이름을 붙였습니다.
• 영향을 받음 조지 댄치그 — 1948년 단치히가 프린스턴을 찾아와 선형 계획법을 설명한 것을 계기로 터커의 연구 모임이 꾸려졌고, 쿤은 게일과 함께 그 첫 대학원생 연구원이 되었습니다.
• 영향을 받음 존 폰 노이만 — 폰 노이만과 모르겐슈테른의 1944년 책이 게임을 나무로 적은 방식을 쿤이 일반화해, 가려진 정보를 '정보 집합'으로 다루는 오늘날의 확장형 게임 이론을 세웠습니다.
• 함께 연구 데이비드 게일 — 1951년 게일, 터커와 함께 선형 계획의 쌍대성 정리를 증명하고 그것이 두 사람 영합 게임의 최소최대 정리와 같은 내용임을 보였습니다.
• 영향을 받음 에른스트 체르멜로 — 체르멜로가 1913년 체스를 두고 보인 사실을 넓혀, 정보가 모두 드러난 유한 게임에는 언제나 확률을 섞지 않는 균형 전략이 있다는 것을 1953년 논문에서 증명했습니다.

연표.

• 1947년 군 복무를 마치고 캘리포니아 공과대학을 졸업하다
• 1948년 프린스턴에서 터커의 게임 이론·선형 계획 연구 모임에 들어가다
• 1950년 군론⁠(group theory)⁠ 연구로 박사 학위를 받고, 확장형 게임에 관한 첫 논문을 내다
• 1951년 게일, 터커와 선형 계획의 쌍대성을 증명하고, 터커와 「비선형 계획」을 발표하다
• 1952년 필라델피아 근교의 브린마 칼리지로 옮기다
• 1953년 헝가리어를 스스로 익혀 에게르바리의 1931년 논문을 번역하다
• 1955년 「배정 문제를 위한 헝가리안 방법」을 발표하다
• 1959년 프린스턴 대학의 수학과와 경제학과 교수가 되다
• 1968년 브라우어르 고정점을 계산하는 단체 분할 방법을 내놓다
• 1980년 게일, 터커와 함께 존 폰 노이만 이론상을 받다
• 1994년 존 내시의 노벨 경제학상 수상을 기념하는 노벨 세미나를 이끌다