09. 케이크 나누기 알고리즘

<알고리즘 행성 여행자들을 위한 안내서>

사진: pakutaso.com 

아빠와 두 명의 아이가 있는데, 케이크는 하나밖에 없다. 케이크 때문에 다툼이 벌어지는 것을 막기위해 아빠는 케이크를 정확하게 똑같은 크기로, 즉 절반으로 나누려고 한다. 그리고 아이들에게 한 조각씩 나눠준다. 가장 좋은 건 두 아이 모두 서로 상대방 것을 가지겠다며 소리를 지르는 상황이다. 그럼 그냥 서로 케이크를 바꿔주면 간단하게 끝난다. 그런데 한 아이만 소리를 지르고 떼를 쓰기 시작하면 상황이 골치 아파진다. 아이들이란!

사실 이런 상황에서 아이들에게 진짜로 중요한 건 케이크가 아니다. 아이들에게 중요한 건 상대방의 것을 갖는 것이다(이처럼 비합리적인 시기심이 발동하는 경우를 우리는 자주 본다). 이런 생각이 들 때면, 어쩌면 내가 너무 부정적인 건 아닌가 하는 자괴감이 들기도 한다. 아이들이 옳을 수도 있다. 시기심과는 거리가 먼 행동일 수도 있다. 내가 케이크의 정중앙을 잘라서 똑같은 크기로 공평하게 나눠주는 데 집착하는 건 나의 편협한 믿음에서 비롯된 행동인지도 모른다. 아이들이 케이크에서 무엇을 보는지, 무엇 때문에 그 두 조각 중 하나를 가지고 그렇게 울고불고 하는지, 나는 그걸 보지 못하고 있는 것이다.

옛날옛적부터 현명한 부모들은 다음과 같이 해왔다. 두 아이 중 한 명에게 칼을 준다. 칼을 받은 아이는 자기가 하고 싶은 대로 케이크를 두 조각으로 나눈다. 그런 다음 나머지 아이에게 그 두 조각 중 어느 것을 먹을지 선택하게 한다. 확실한 것은, 칼을 든 아이는 자기만의 기준에 따라 완벽하게 양쪽 모두 좋아 보이도록 케이크를 두 조각으로 나눌 수 있다는 점이다. 그래서 다른 아이가 결정을 내리기까지 편안한 마음으로 기다릴 수 있다. 두 번째 아이가 어떤 케이크 조각을 선택하든, 첫 번째 아이는 만족스러워 보이는 케이크 절반을 갖게 될 테니 말이다. 두 번째 아이는 훨씬 더 쉽다. 그냥 더 마음에 드는 걸 고르기만하면 된다. 이로써 이 두 번째 아이 역시 최소한 케이크에서 자신이 좋아하는 절반을 갖게 된다.

이 방법의 비밀은 무엇일까? 여기엔 어떤 특징이 있을까? 가장 중요한 특징은, 두 아이 모두 자신의 결정으로 적어도 공정하게 케이크의 일부를 받을 수 있다는 점이다. 첫 번째 아이가 자기 기준에 따라 케이크를 절반으로 자르면, 이 아이는 두 번째 아이가 어느 쪽을 선택하든간에 만족스러운 나머지 절반을 갖게 된다. 두 번째 아이는 첫 번째 아이의 결정에 의존하지 않고 케이크에서 적어도 자기가 마음에 드는 절반을 가질 수 있다.

케이크 분할 알고리즘: 이 방법의 비밀은 뭘까?

둘째, 이 알고리즘은 중앙의 기획자가 알지 못하는 정보에 대한 실질적인 접근을 보장한다. 아이들은 케이크에 대한 취향이 서로 완전히 다를 수 있다. 그리고 아빠는 이것에 대해 전혀 알지 못한다.이런 상황에서 결정의 형식, 즉 알고리즘은 각각의 아이가 케이크에서 자기가 좋다고 생각되는 것의 적어도 절반을 받을 수 있도록 해준다. 그 기준을 정확하게 설명할 필요도 없이 말이다.

셋째, 아빠는 과잉 존재다(그렇다, 아빠는 어쩌면 칼을 조심하라며 거기에만 신경 쓰고 있을지도 모른다). 이 방법으로 자기가 케이크에서 좋아하는 것의 적어도 절반을 반드시 받을 수 있다는 것을 이해하는 한, 아이들은 이 방법에 자발적으로 합의할 것이다. 아빠가 나설 필요 없이, 케이크 분할 알고리즘이 스스로를 추천해 아이들의 자발적 합의를 독려하는 셈이다.