데이비드 게일(David Gale)

데이비드 게일은 1921년 뉴욕에서 태어났습니다. 그가 수학자가 된 2차 세계대전 직후는 경제학이 수학의 언어를 새로 배우던 때였습니다. 수많은 사람이 저마다 사고파는 시장에서 모든 물건의 수요와 공급을 한꺼번에 맞추는 가격이 과연 있는지, 한정된 자원을 여러 생산 활동에 어떻게 나누는 것이 가장 좋은지 같은 물음은 오래된 것이었지만, 1940년대에 폰 노이만의 게임 이론과 단치히의 선형 계획법이 그 물음을 정리와 알고리즘의 문제로 바꾸고 있었습니다. 게일은 이 새 분야를 엄밀한 수학으로 다듬은 사람이었고, 동시에 평생 퍼즐과 놀이를 사랑해 그 속에서 정리를 찾아낸 사람이었습니다.

나이 세 ·

그는 1943년 필라델피아 근교의 스와스모어 칼리지를 졸업하고 미시간 대학에서 석사 학위를 받은 뒤 프린스턴 대학원에 들어갔습니다. 1948년 앨버트 터커가 해군 연구청의 지원으로 선형 계획법과 게임 이론의 관계를 연구하는 모임을 꾸리자 해럴드 쿤과 함께 첫 연구원이 되었고, 이듬해 두 사람이 겨루는 유한 게임에 관한 논문으로 박사 학위를 받았습니다. 1950년 브라운 대학으로 가서 1960년대 중반까지 가르쳤고, 그 뒤로는 캘리포니아 대학 버클리에서 일했습니다.

1951년 게일, 쿤, 터커가 함께 쓴 논문은 게임과 선형 계획이 같은 문제의 두 얼굴임을 보였습니다. 가위바위보처럼 한 사람이 얻는 만큼 다른 사람이 잃는 게임을 생각해 봅시다. 어느 한 손만 고집하면 상대에게 읽히므로 확률⁠(probability)⁠을 섞어 내야 하는데, 가장 나쁜 경우의 기대 이득을 가장 크게 하는 섞는 비율을 찾는 일은 선형 계획 문제로 적힙니다. 상대가 자기의 가장 좋은 비율을 찾는 문제는 바로 그 쌍대 문제⁠(dual problem)⁠가 됩니다. 폰 노이만의 최소최대 정리⁠(minimax theorem)⁠, 곧 두 사람이 각자 최선을 다했을 때 두 사람이 바라보는 게임의 값이 같다는 정리는 선형 계획의 쌍대성 정리, 곧 두 문제의 최적값이 같다는 정리와 같은 내용입니다. 가위바위보라면 두 사람 모두 세 손을 1/3씩 섞고 게임의 값은 0입니다(쌍대성).

1953년 그는 프랭크 스튜어트와 함께 끝나지 않는 게임을 따졌습니다. 두 사람이 번갈아 자연수⁠(natural number)⁠를 하나씩 부르기를 영원히 계속해 무한 수열 하나를 만들고, 그 수열이 미리 정한 집합⁠(set)⁠ $A$에 들어 있으면 먼저 부른 사람이, 아니면 나중 사람이 이긴다고 합시다. 둘 가운데 한 사람이 상대가 어떻게 하든 이기는 전략⁠(winning strategy)⁠을 가지고 있으면 그 게임을 '결정된다'고 합니다. 유한한 게임은 언제나 결정되지만 무한한 게임은 그렇지 않을 수 있습니다. 게일과 스튜어트는 먼저 부른 사람이 이길 때면 언제나 유한한 단계에서 승리가 확정되는 게임(집합 $A$가 '열린' 경우)은 결정된다는 것과, 선택공리⁠(axiom of choice)⁠를 쓰면 결정되지 않는 게임이 있다는 것을 보였습니다. 어떤 집합의 게임이 결정되는지를 묻는 이 연구는 기술 집합론⁠(descriptive set theory)⁠의 중심 줄기가 되었고, 1975년 도널드 마틴은 보렐 집합⁠(Borel set)⁠이라 불리는 넓은 집합들의 게임이 모두 결정된다는 것을 증명했습니다.

경제학에서 그는 경쟁 균형의 존재를 다듬었습니다. 물건마다 값을 매겼을 때 사람들이 사고 싶은 양에서 팔고 싶은 양을 뺀 '초과 수요⁠(excess demand)⁠'가 어느 물건에서도 양수가 아니게 되는 가격이 있을까요? 1955년 게일은, 초과 수요가 가격에 따라 연속적으로 변하고 모든 사람이 자기 예산을 다 쓴다면 그런 가격이 반드시 있다는 보조정리⁠(lemma)⁠를 고정점⁠(fixed point)⁠ 정리로 증명했습니다. 같은 무렵 니카이도 후쿠카네와 제라르 드브뢰도 따로 같은 결과를 얻어, 오늘날 게일–니카이도–드브뢰 보조정리라 부릅니다. 1960년 책 『선형 경제 모형의 이론』은 선형 계획, 게임, 폰 노이만의 성장 모형을 한데 엮어 오랫동안 수리경제학의 교과서로 읽혔습니다.

1962년 그는 RAND 연구소의 로이드 섀플리와 함께 『미국 수학 월보』에 「대학 입학과 결혼의 안정성⁠(stability)⁠」을 실었습니다. 게일이 지원자와 대학을 서로 불만 없이 짝짓는 배정이 언제나 있느냐는 물음을 던졌고, 섀플리가 한쪽이 청혼하고 다른 쪽이 가장 나은 청혼만 보류하는 수용 유보⁠(deferred acceptance)⁠ 방법으로 답했다고 전합니다(안정 매칭). 같은 논문은 양쪽이 나뉘지 않은 경우, 곧 한 무리 안에서 둘씩 방을 나누는 룸메이트 문제⁠(stable roommates problem)⁠에는 안정한 배정이 없을 수도 있음을 보였습니다. 네 사람 가운데 A는 B를, B는 C를, C는 A를 가장 원하고 셋 모두 D를 가장 싫어한다고 합시다. D와 방을 쓰게 된 사람은 누구든, 그를 가장 원하는 사람(그에게는 두 번째 상대)과 서로 지금 짝보다 상대를 더 원하게 됩니다. A가 D와 짝이면, A를 가장 원하는 C는 지금 짝 B보다 A를, A는 D보다 C를 원합니다. 이 논문은 끝에 '수학이란 무엇인가'라는 짧은 덧붙임을 달아, 공식 하나 없이 보통의 말로 이루어진 이 논증도 수학이라고 적었습니다.

그는 게임과 퍼즐을 만드는 사람이기도 했습니다. 1958년 마틴 가드너가 『사이언티픽 아메리칸』 칼럼에 소개한 '브리짓'(게일의 게임)은 두 사람이 격자 위의 점들을 선으로 이어 자기 쪽 두 변을 먼저 잇는 게임입니다. 과자판을 한 입씩 베어 먹다 독이 든 조각을 먹는 사람이 지는 게임 촘프도 1970년대 초 그가 내놓은 형태로 널리 알려졌습니다. 촘프에서는 먼저 두는 사람이 반드시 이길 수 있다는 것이 '전략 훔치기⁠(strategy stealing)⁠' 논증으로 증명됩니다. 먼저 두는 사람이 오른쪽 위 끝 조각 하나만 먹는 수가 지는 수라면, 뒷사람에게는 그에 맞서 이기는 응수가 있을 텐데, 그 응수로 생기는 판은 먼저 두는 사람이 처음부터 곧바로 만들 수 있는 판이기 때문입니다. 이기는 첫 수가 무엇인지는 알려 주지 않고 있다는 것만 보이는 증명입니다.

가장 이름난 것은 1979년의 헥스 논문입니다. 헥스는 육각형 칸으로 된 마름모꼴 판에서 두 사람이 번갈아 칸을 칠해, 한 사람은 위아래 두 변을, 다른 사람은 좌우 두 변을 자기 색 칸으로 잇는 게임으로, 1942년 덴마크의 피트 헤인과 1948년 프린스턴의 존 내시가 따로 발명했습니다. 판을 모두 칠하면 반드시 누군가 한 사람은 이어져 있어 비기는 일이 없습니다. 게일은 이 사실이 브라우어르의 고정점 정리, 곧 정사각형을 자기 자신 안으로 연속적으로 옮기는 사상에는 반드시 제자리에 머무는 점이 있다는 정리와 같은 내용임을 보였습니다. 고정점이 없는 사상이 있다면 그것으로 헥스 판의 칸들을 칠해, 아무도 잇지 못한 채 가득 찬 판을 만들 수 있다는 것입니다. 연속과 위상수학⁠(topology)⁠의 정리를 유한한 놀이판의 조합으로 바꾼 이 논증은 고정점을 실제로 찾는 알고리즘들과도 이어집니다.

게일은 수학의 재미를 알리는 일도 오래 했습니다. 1991년부터 『매스매티컬 인텔리전서』에 '수학의 즐거움' 칼럼을 연재했고, 이 글들은 1998년 『자동 개미를 따라서』라는 책으로 묶였습니다. 제목의 개미는 격자 위에서 칸의 색에 따라 방향을 바꾸며 걷는 단순한 규칙의 개미로, 한동안 뒤죽박죽 걷다가 갑자기 한 방향으로 곧게 길을 내기 시작합니다. 행과 열의 합이 정해진 0과 1의 표가 언제 존재하는지에 대한 게일–라이저 정리(1957)처럼 조합론⁠(combinatorics)⁠에도 그의 이름이 남아 있습니다. 1980년 쿤, 터커와 함께 존 폰 노이만 이론상을 받았고, 2008년 버클리에서 세상을 떠났습니다. 4년 뒤 안정 매칭의 이론이 노벨 경제학상을 받았을 때 그는 이미 없었습니다.

이어지는 곳. 게임의 값과 선형 계획의 쌍대성은 해럴드 쿤과 쌍대성에서, 안정 매칭의 뒷이야기와 시장 설계⁠(market design)⁠는 로이드 섀플리에서 이어집니다. 선호가 없을 때 짝짓기가 가능한지는 홀의 결혼 정리가 답하고, 안정 매칭을 알고리즘 분석⁠(analysis of algorithms)⁠의 문제로 다룬 것은 크누스의 1976년 강의록입니다. 무한 게임의 결정성은 기술 집합론과 공리⁠(axiom)⁠의 문제로, 헥스와 고정점은 고정점과 위상수학으로 이어지며, 가장 좋은 선택을 찾는 수학 전체의 그림은 가장 좋은 것 고르기에 있습니다.

관계.

• 영향을 받음 존 폰 노이만 — 폰 노이만의 최소최대 정리를 선형 계획의 쌍대성으로 다시 증명한 1951년 논문과, 폰 노이만의 경제 성장 모형을 다듬은 연구가 게일의 초기 경력을 이루었습니다.
• 영향을 받음 L. E. J. 브라우어르 — 1979년 헥스 판에서 비기는 일이 없다는 사실이 2차원의 브라우어르 고정점 정리⁠(Brouwer fixed-point theorem)⁠와 같은 내용임을 보여, 놀이판 위의 증명을 내놓았습니다.

연표.

• 1943년 스와스모어 칼리지를 졸업하다
• 1947년 미시간 대학에서 석사 학위를 받다
• 1949년 유한 게임에 관한 논문으로 프린스턴에서 박사 학위를 받다
• 1950년 브라운 대학 교수진에 합류하다
• 1951년 쿤, 터커와 선형 계획의 쌍대성과 게임의 관계를 증명하다
• 1953년 스튜어트와 무한 게임의 결정성을 다룬 논문을 내다
• 1960년 『선형 경제 모형의 이론』을 펴내다
• 1962년 섀플리와 「대학 입학과 결혼의 안정성」을 발표하다
• 1979년 「헥스 게임과 브라우어르 고정점 정리」를 발표하다
• 1980년 쿤, 터커와 함께 존 폰 노이만 이론상을 받다