Mechanism Design
The Science of Rule Making
Algorithmic Game Theory 라.. 과연 컴퓨터 과학에서 다루는 게임 이론이란 어떤 걸까?
얼마전 학회 리셉션에서 밥을 먹으며 옆에 앉아있던 사람과 잠깐 대화를 할 기회가 있었다. 학회에 참석하러 런던에서 이타카까지 온 그는 경제학에서 이론 연구 쪽은 죽어가고 있는데 여기 컴퓨터 과학에서는 게임 이론 연구가 굉장히 활발한 것 같다고 했었다. 경제학에서 이론을 하는 교수 자리는 한 학교에 한두개 밖에 없다고 잡 마켓을 걱정하길래 아 그래? 그럼 너는 박사 마치고 뭘 할 생각이야라고 물어봤더니 아 본인은 이미 교수라서 괜찮다고 했던 재미난 분이셨다. (그래 교수도 청바지를 내려 입을 수 있지..) 학회 첫 참석자의 판단 오류는 어려보이고 학생같이 옷을 입었다고 학생이라 착각하는 것이다.
아무튼 이 글에서는 Mechanism Design이 어떤 것을 다루는 학문이고 어떤 매력이 있는지 소개하려 한다.
저번 글에서 월드컵 토너먼트의 디자인의 헛점을 설명하면서 이 룰 안에서는 서로 지려고 하는 경기도 있을 수 있다고 말했다. 실제로 같은 토너먼트 규칙을 갖고 있는 2012년 런던 올림픽에서 한국과 중국의 여자 배드민턴 경기에서 이와 같은 일이 일어났다. 두 팀 중 이긴 팀은 4강에서 더 강한 중국팀이랑 경기해야 했고 진 팀은 더 쉬운 덴마크 팀과 경기를 해야 했던 상황이었다. 두 팀의 선수들은 덴마크 팀과 붙으면 더 높은 메달을 받을 수 있는 가능성이 높아지니 당연히 고의적으로 지려고 했고 경기 후 비난이 거세지자 나중에 위원회에서는 두 팀 다 실격 처리를 하였다.
4년간 올림픽을 준비했던 선수들은 실망스러운 경기를 했고 팬과 위원회는 그 행동에 분노했다. 하지만 한번 더 생각해보면, 메달이 걸려있는 다음 경기를 위해 질 수밖에 없었던 배드민턴 선수들을 욕할 수 있을까. 그들도 올림픽에 나와 사람들에게 지는 모습을 보여주려고 지난 4년간 땀흘리며 운동하고 노력하진 않았을 것이다.
왜 이런 일이 벌어졌을까?
토너먼트에서는 참여자들의 인센티브와 올림픽 위원회와 팬들의 인센티브가 다르기 때문이다.
4년간이나 노력해서 출전한 선수들이 이 토너먼트에서 원하는 것은 무엇보다 더 높은 메달을 따는 것인데, 올림픽 위원회는 이 토너먼트에서 위원회가 원하는 결과는 무엇인지에(어떻게 하면 재밌고 긴장감 넘치는 경기를 만들 수 있을까) 대해 많은 고민을 하지 못했던 것 같다. 이 일의 잘못은 선수들이 아니라 룰을 제대로 만들지 못했던 올림픽 위원회에 있다는 뜻이다.
Let's ask "what's wrong with the rules?",
not "what's wrong with these people?"
메커니즘 디자인이란 참여자들이 서로 다른 전략을 가졌어도 그 메커니즘 안에서 디자이너가 원하는 결과를 낼 수 있도록 룰을 과학적인 방식으로 디자인하는 학문이다. 다시 말해, 참여자들은 디자이너가 모르는 그들 각자만의 private한 valuation을 갖고 있을 것이고(private information, preferences) 그에 따라 서로 다른 전략적인 행동을 할텐데 이 때 어떻게 룰들을 세팅하면 디자이너가 바라는 합의점(social choice)에 도달할 수 있을까를 연구하는 학문이다.
현실 세계에서도 과연 이 학문이 실용적으로 사용될까?
메커니즘 디자인 이론들을 현실 문제에 적용해 기존보다 더 많은 돈을 벌었다든가 (인터넷 서치 광고 옥션, 무선 주파수 옥션), 더 많은 사람들을 살릴 수 있었다든가 (신장 이식 매칭, 환자-병원 매칭), 더 많은 아이들에게 그들이 원하는 교육의 기회를 주었다든가(학교-학생 매칭)하는 실제 사례들은 많이 존재한다. 앞으로 인터넷의 영향력이 더 커지면서 나는 더 많은 어플리케이션들이(선거, 옥션, 매칭 시장, 또는 정부 정책들) 이 학문의 도움을 받아 만들어질 것이라 생각한다.
메커니즘 디자인이 기존 경제학 이론과 차별화되는 점이 여기 있다. 컴퓨터 과학자들이 어떤 알고리즘이나 프로토콜, 시스템을 디자인하고 만들어 내듯이 메커니즘 디자인도 무언가를 만들어 내는 엔지니어로서의 관점을 전제하고 있다는 점이다.
그렇다면 컴퓨터 과학은 경제학에서 나온 메커니즘 디자인에 어떤 부분들은 기여하는 것일까.
컴퓨터 과학은 computation 의 학문이니 computational efficiency와 approximate optimality 측면에서 메커니즘 디자인을 접근한다. 이는 우리가 실제 세상에서 메커니즘 디자인을 도입해서 시스템을 만들고 싶을 때 여러 computing 영역의 제한들이 있기 때문이다.
Braess's Paradox 를 살펴보며 컴퓨터 과학자들이 어떻게 경제학자들과 어떻게 다른 관점을 갖고 있는지 알아보자.
from CS364A by Tim Roughgardens에서 t로 가는 두가지 종류의 path가 있다고 하자. 하나는 s->v->t 로 가는 길과 다른 하나는 s->w->t로 가는 길이다. 도로를 건너는 시간은 차가 얼마나 지나가는지와 상관없이 v->t, s->w 는 1시간이 걸리고 s->v, w->t는 x가 도로를 지나는 차량의 수라고 할 때 x/60시간이 걸린다고 하자. 총 60대의 차량이 s에서 t로 간다면 전체 차량의 반은 s->v->t를 선택해서 가고 반은 s->w->t를 선택하는 것이 equilibrium이다. 이런 equilibrium에 도달했다면 한 차량이 s에서 t까지 가는 데에는 총 1과 1/2, 즉 90분이 걸릴 것이다.
이 상태에서 그림 b와 같이 차량의 수랑은 상관없이 v에서 w로 시간이 0이 걸리는 엄청난 고속도로를 지었다고 생각해보자. 운전자들은 이제 어떻게 도로 선택을 할까? x/60 은 항상 1보다 같거나 작을테니 운전자들은 다들 s->v->w->t라는 길을 선택할 것이다. (x/60 + x/60 <= 1 + x/60이므로) 모든 운전자들이 이 path를 선택한다면 2, 120분이 걸리게 되어 도로가 없을 때보다 더 비효율적인 교통이 된다. 직감적으로 이 빠른 고속도로를 놓으면 교통이 더 좋아질 거 같은데 말이다.
Braess's paradox는 운전자들이 이기적으로 행동했을 때 항상 바람직한 결과를 낳지 않는다는 것을 보여주는 사례다. 우리가 어떤 룰을 적용해서 다시 a과 같은 선택을 하도록 운전자들을 유도한다면 도착시간을 25%나 줄일 수 있을 것이다. 경제학자들은 대부분의 equilibrium(모든 사람들이 이기적으로 행동했을 때 나오는 균형 상태)들이 비효율적이라고 생각할 뿐이지만 컴퓨터 과학자들은 더 나아가 이 비율을 수량화하고 (quantify) 연산하는 것에(computation) 관심이 있다. 그래서 그들은 시스템의 최고 퍼포먼스와 메커니즘 디자인을 잘해서 플레이어들이 이기적으로 행동했을 때의 최고 퍼포먼스 간의 비율(위의 경우는 4/3 (2 : 3/2) )을 Price of Anarchy(POA)라 처음 정의하였고 이 비율이 1에 도달하는 것을 목표로 세웠다.
다음으로는 Computational issues of Nash Equilibrium 을 살펴보자.
모든 bimatrix game(플레이어가 두명인 게임) 에는 적어도 하나 이상의 Nash Equilibrium 이 존재한다는 것이 Nash's Theorem 이다. 이 Nash equilibrium 을 찾아내는 데 어느 정도의 연산 시간이 필요할까. 연산하는 것이 엄청 어렵다면 equilibrium 의 의미가 있을까. 컴퓨터 과학자들은 zero-sum-game에서는 polynomial time 이 걸리지만 non-zero-sum-game 에서는 polynomial time보다 더 걸린다는 사실을 발견했다. 경제학자들은 해결책에 강조를 하고 메커니즘 디자인을 연구하지만 그것이 어떻게 연산될지에 대해서는 관심이 없었다. 컴퓨터 과학자들은 그 해결책이 현실적인지 판단하고 싶어한다. 즉, 그들은 equilibrium을 연산하는 데 어느 정도의 시간이 걸리는지, 어느 정도의 근사치를 가지는지를 알고 싶어한다.
미국 대학교들에는 Econ-cs라는 연계 전공이 있는 곳도 있고 EconCs라는 리서치 그룹이 있는 학교도 있다. 경제학을 이용해서 컴퓨터 과학의 문제들을 해결하거나 반대로 컴퓨터 과학을 이용하여 경제학 문제들을 해결하려는 것들의 모든 노력들을 크게 Econ-CS라 지칭할 수 있는데 자세히는,
경제학을 이용해 컴퓨터 과학 문제 접근:
컴퓨터 네트워크 환경에서 메세지 라우팅, 스케줄 관리, 메모리 할당과 같은 문제들을 풀기 위해 메커니즘 디자인의 관점에서 알고리즘을 만들어야 한다. 리소스를 관리하는 각각의 플레이어들과 리퀘스트를 요청하는 각각의 플레이어들이 그들의 선호에 따라 다른 전략을 구사해도 알고리즘은 잘 돌아가야 하기 때문이다. 이를 Algorithmic Mechanism Design 이라고 한다.
컴퓨터 과학을 이용해 경제학 접근:
인터넷이 커지면서 인터넷에서의 경제적인 교류 활동은(마켓, 옥션, 공급망 등) 더욱 더 복잡해질 것이고 그것을 아주 합리적으로 관리할 수 있는 소프트웨어 플랫폼을 디자인해야 할텐데 이를 Electronic Market Design 이라고 한다.
Industry에서는 이 학문을 어떻게 바라보고 있을까.
많은 큰 테크 회사들이 스폰서를 하고 있지만 페이스북 리서치 그룹이 최근에 이 학문에 대한 서포트를 많이 하고 있는 것 같다.
How should one design mechanisms on top of such an online platform to build community in a way that alleviates these social ills?
메커니즘 디자인의 가장 큰 매력은 Social Good을 위한 학문이라는 점 아닐까.
