로이드 섀플리(Lloyd Shapley)

로이드 섀플리는 1923년 미국 매사추세츠주 케임브리지에서 태어났습니다. 아버지 할로 섀플리는 우리 은하가 생각보다 훨씬 크고 태양이 그 한가운데가 아니라 변두리에 있다는 것을 보인 천문학자로, 하버드 천문대의 대장이었습니다. 섀플리가 수학자로 일한 1950–70년대는 냉전의 시대였고, 캘리포니아 샌타모니카의 RAND 연구소는 미 공군의 돈으로 수학자들에게 전략을 생각하게 하는 곳이었습니다. 그곳에서 게임 이론은 핵 억지 같은 대결의 수학으로 출발했지만, 섀플리는 평생 그 반대쪽 물음을 붙들었습니다. 사람들이 힘을 합쳤을 때 번 것을 어떻게 나누어야 공정한가, 그리고 누가 누구와 짝을 지어야 모두가 그 결과를 받아들이는가.

나이 세 ·

하버드에서 수학을 공부하던 그는 1943년 징집되어 육군 항공대의 기상 관측병으로 중국 쓰촨성의 청두에 배치되었습니다. 그곳에서 소련의 기상 전문 암호를 풀어 동성 훈장을 받았다는 일화가 전합니다. 전쟁 뒤 1948년 하버드를 졸업하고 RAND에서 1년을 일한 다음 프린스턴 대학원에 들어가 앨버트 터커의 지도를 받았습니다. 그 무렵 프린스턴 수학과에는 존 내시, 마틴 슈빅 같은 젊은 게임 이론가들이 모여 있었고, 섀플리는 그들과 함께 이기려면 반드시 동맹을 배신해야 하는 보드게임 '소 롱 서커'를 만들어 놀았습니다. 심판만 전체 판을 보는 눈가림 체스 크릭슈필의 명수이기도 했습니다.

1953년 그는 오늘날 섀플리 값이라 불리는 답을 내놓았습니다. 사람들의 집합⁠(set)⁠ $N$의 부분 모임(연합) $S$마다 그 연합이 스스로 벌 수 있는 금액 $v(S)$가 정해져 있다고 합시다. 모두가 힘을 합쳐 번 $v(N)$을 어떻게 나눌까요? 섀플리의 생각은 이렇습니다. 사람들이 무작위 순서로 한 명씩 방에 들어온다고 상상하고, 들어오는 사람에게는 자기가 들어오면서 방 안의 연합이 버는 돈을 늘린 만큼, 곧 그의 한계 기여를 줍니다. 그리고 $n!$가지 순서 모두에 대해 이 몫을 평균⁠(mean)⁠합니다. 위의 식이 그 평균을 셈한 것입니다.

작은 예를 봅시다. A는 왼쪽 장갑 한 짝을, B와 C는 오른쪽 장갑 한 짝씩을 가지고 있고, 짝이 맞는 장갑 한 켤레는 1만큼의 값에 팔립니다. 들어오는 순서 여섯 가지 가운데 A가 맨 처음이 아닌 네 가지에서 A는 먼저 와 있던 오른쪽 장갑과 켤레를 맞춰 1을 더하므로 A의 몫은 4/6 = 2/3입니다. B가 1을 더하는 것은 A, B, C 순서뿐이므로 B의 몫은 1/6, C도 1/6이고, 셋을 더하면 1입니다. 드문 쪽을 가진 사람이 더 많이 받습니다. 섀플리는 이 규칙이 네 가지 당연해 보이는 요구, 곧 번 것을 남김없이 나눌 것, 똑같은 역할의 두 사람은 똑같이 받을 것, 어떤 연합에도 보탬이 안 되는 사람은 0을 받을 것, 두 게임을 합친 게임의 몫은 각 게임의 몫의 합일 것을 모두 만족하는 유일한 규칙임을 증명했습니다. 공정함에 대한 막연한 느낌을 공리⁠(axiom)⁠로 적고 그 공리를 만족하는 답이 하나뿐임을 보인 것입니다.

섀플리 값은 여러 곳으로 퍼졌습니다. 1954년 섀플리와 슈빅은 투표를 게임으로 보아, 한 사람의 힘을 '무작위 순서로 찬성표가 모일 때 그 사람의 표가 가결을 결정짓는 확률⁠(probability)⁠'로 재는 지수를 내놓았습니다. 오늘날의 유엔 안전보장이사회처럼 상임이사국 다섯이 모두 찬성하고 전체 15개국 가운데 아홉 나라가 찬성해야 가결되는 규칙으로 계산하면, 상임이사국 하나의 힘은 약 0.196, 비상임이사국 하나의 힘은 약 0.0019로, 거부권이 백 배가 넘는 차이를 만듭니다. 2017년 무렵부터는 기계 학습⁠(machine learning)⁠에서 모형의 예측을 설명하는 데 섀플리 값이 쓰입니다. 입력의 특성 하나하나를 '사람'으로, 예측값을 '번 돈'으로 보고 각 특성이 예측에 기여한 몫을 나누는 것입니다.

같은 1953년 그는 '확률 게임'도 정의했습니다. 게임이 여러 상태 사이를 옮겨 다니며 판마다 두 사람이 수를 고르면, 그 선택에 따라 보수가 주어지고 다음 상태가 확률적으로 정해집니다. 판마다 게임이 끝날 확률이 조금씩이라도 있으면 전체 보수는 유한합니다. 섀플리는 이런 게임에도 값이 있고, 지금 상태만 보고 행동을 정하는 전략으로 그 값을 얻을 수 있음을 보였습니다. 각 상태의 값은 '이번 판의 보수와 다음 상태 값의 기댓값⁠(expected value)⁠을 합친 게임의 값'이라는 식을 만족하는데, 이 식을 거듭 적용하면 오차가 매번 일정한 비율로 줄어 하나의 답, 곧 고정점⁠(fixed point)⁠으로 모입니다. 몇 해 뒤 리처드 벨먼의 동적 계획법⁠(dynamic programming)⁠과 마르코프 결정 과정⁠(Markov decision process)⁠, 그리고 오늘날의 강화 학습⁠(reinforcement learning)⁠이 한 사람짜리 판에서 같은 생각을 씁니다(마르코프 연쇄⁠, Markov chain⁠).

협력 게임⁠(cooperative game)⁠에서 섀플리 값과 함께 중요한 개념이 코어입니다. 모두가 함께 번 것을 나누되, 어떤 연합도 따로 떨어져 나가서 더 많이 벌 수 없도록 나누는 방법들의 모임입니다. 식으로는 모든 연합 $S$에 대해 그 사람들이 받는 몫의 합이 $v(S)$ 이상이라는 조건입니다. 코어는 비어 있을 수 있습니다. 세 사람 가운데 누구든 둘이면 1을 벌고 셋이 모여도 1밖에 못 번다면, 세 쌍의 조건을 모두 더해 몫의 합의 두 배가 3 이상이어야 하지만 나눌 것은 1뿐입니다. 1963년 소련의 올가 본다레바와 1967년 섀플리는 따로, 코어가 비어 있지 않을 필요충분조건을 찾았습니다. 증명의 열쇠는 선형 계획⁠(linear programming)⁠의 쌍대성⁠(duality)⁠이었습니다(쌍대성).

1962년 브라운 대학의 데이비드 게일과 함께 낸 논문은 그의 이름을 가장 널리 알렸습니다. 학생과 대학, 또는 남녀를 짝지을 때, 서로 지금 짝보다 상대를 더 원하는 두 사람(막는 쌍⁠, blocking pair⁠)이 하나도 없는 배정을 안정하다고 합니다. 게일이 이런 배정이 늘 있느냐고 묻자 섀플리가 곧 답을 찾았다고 전합니다. 한쪽이 가장 원하는 상대에게 청혼하고, 청혼받은 쪽은 지금까지 받은 청혼 가운데 가장 나은 것 하나만 '보류'하고 나머지는 거절합니다. 거절당한 사람은 다음 상대에게 청혼하고, 이것을 거절이 없을 때까지 되풀이합니다. 누구도 같은 상대에게 두 번 청혼하지 않으니 이 과정은 끝나고, 결과는 언제나 안정합니다. 내가 지금 짝보다 더 원하는 상대가 있다면 나는 그에게 먼저 청혼했다가 거절당했을 것이고, 그가 나를 거절한 것은 더 나은 청혼을 받았기 때문이며, 그가 보류하는 상대는 갈수록 나아질 뿐이기 때문입니다. 이 안정 매칭에서 청혼하는 쪽은 모든 안정 배정 가운데 가장 좋은 짝을 얻습니다.

그 뒤 섀플리는 짝짓기에 돈과 소유를 들였습니다. 1971년 슈빅과 함께 한 연구에서는 집을 사고파는 사람들이 값을 흥정하는 '배정 게임'의 코어가 바로 경쟁 시장의 가격들이고, 이것이 배정 문제⁠(assignment problem)⁠의 선형 계획에서 쌍대 문제⁠(dual problem)⁠의 답과 같다는 것을 보였습니다. 1974년 허버트 스카프와 함께 쓴 논문에서는 저마다 집 한 채씩을 가진 사람들이 집을 맞바꾸는 시장을 다루었습니다. 모두가 가장 원하는 집의 주인을 화살표로 가리키면, 사람마다 화살표가 하나씩 나가므로 따라가다 보면 반드시 고리가 생깁니다. 고리를 이룬 사람들끼리 한꺼번에 집을 바꾸고 빠진 뒤 되풀이하는 이 '최상위 교환 고리⁠(top trading cycles)⁠' 방법은 논문에서 게일의 착상으로 소개되었고, 30년 뒤 앨빈 로스와 동료들이 기증자가 맞지 않는 환자–기증자 쌍들 사이의 신장 교환⁠(kidney exchange)⁠을 설계하는 바탕이 되었습니다(그래프).

섀플리는 1954년부터 1981년까지 RAND에 있다가 UCLA로 옮겼습니다. 2012년 노벨 경제학상은 '안정된 배분의 이론과 시장 설계⁠(market design)⁠의 실천'으로 섀플리와 로스에게 돌아갔습니다. 이론을 세운 섀플리와, 그것을 병원 인턴 배정과 학교 배정과 신장 이식에 옮긴 로스였습니다. 여든아홉의 섀플리는 수상 소식을 들은 뒤, 자신은 경제학 수업을 한 번도 들은 적이 없는 수학자라는 취지로 말했다고 전합니다. 게일은 2008년 세상을 떠나 상을 나눌 수 없었습니다. 섀플리는 2016년 애리조나주 투손에서 세상을 떠났습니다.

이어지는 곳. 협력 게임의 틀은 폰 노이만의 게임 이론에서 왔고, 두 사람 영합 게임⁠(zero-sum game)⁠의 최소최대 정리⁠(minimax theorem)⁠는 선형 계획의 쌍대성과 같은 내용입니다(해럴드 쿤). 안정 매칭 문제를 알고리즘 분석⁠(analysis of algorithms)⁠의 교과서적인 예로 만든 사람은 크누스이고, 선호 없이 짝이 있는지만 묻는 것이 홀의 결혼 정리입니다. 한계 기여를 평균한다는 섀플리 값의 셈은 순열⁠(permutation)⁠과 기댓값의 문제이고, 확률 게임의 값을 되풀이로 구하는 방법은 고정점과 가장 좋은 것 고르기의 이야기와 이어집니다.

관계.

• 영향을 받음 존 폰 노이만 — 폰 노이만과 모르겐슈테른이 1944년 책에서 연합이 스스로 얻을 수 있는 몫으로 협력 게임을 적은 틀 위에서, 섀플리는 그 몫을 한 사람 한 사람에게 나누는 유일한 규칙을 찾았습니다.
• 함께 연구 데이비드 게일 — 1962년 게일이 던진 '안정한 짝짓기가 언제나 있는가'라는 물음에 섀플리가 수용 유보⁠(deferred acceptance)⁠ 방법으로 답해 공동 논문이 되었고, 1974년 집 맞바꾸기 논문의 '최상위 교환 고리'는 게일의 착상으로 소개되었습니다.

연표.

• 1943년 하버드 재학 중 징집되어 중국 청두에서 공군 기상 관측병으로 일하다
• 1948년 하버드를 졸업하고 RAND 연구소에서 일하기 시작하다
• 1953년 프린스턴에서 박사 학위를 받고 섀플리 값과 확률 게임을 발표하다
• 1954년 마틴 슈빅과 투표권의 힘을 재는 지수를 발표하다
• 1962년 게일과 「대학 입학과 결혼의 안정성⁠(stability)⁠」을 발표하다
• 1967년 협력 게임의 코어가 비어 있지 않을 조건을 증명하다
• 1971년 슈빅과 돈이 오가는 배정 게임을 분석하다
• 1974년 허버트 스카프와 집을 맞바꾸는 시장을 분석하다
• 1981년 RAND를 떠나 UCLA 교수가 되다
• 2012년 앨빈 로스와 함께 노벨 경제학상을 받다