공평하게 나누기
내가 자르고 네가 고르면 됩니다
맛있는 조각 케이크 하나를 친구와 둘이서 한 치의 불만도 없이 똑같이 나누어 먹으려면 어떻게 해야 할까요?
한 사람이 칼로 케이크를 두 조각으로 자르고, 다른 사람이 먼저 마음에 드는 조각을 고르게 하면 됩니다. 자른 사람은 공평하게 자를 수밖에 없고 고른 사람은 좋은 것을 고르니 싸움이 없습니다. 셋 이상일 때는 어떻게 나누어야 할까요?
이야기
케이크 하나를 둘이 나눕니다. 어떻게 해야 둘 다 불만이 없을까요?
답은 아주 오래되었습니다. “네가 자르고 내가 고른다.”
자르는 사람은 어느 쪽을 받아도 괜찮게 자릅니다. 크게 자르면 상대가 그것을 가져갈 테니까요. 고르는 사람은 마음에 드는 쪽을 가져갑니다. 둘 다 억울하지 않습니다.
그런데 셋이 되면 갑자기 어려워집니다. 「네가 자르고 내가 고른다」를 어떻게 셋으로 늘릴까요?
방법이 있긴 합니다. 한 사람이 3분의 1이라 생각하는 만큼 자르고, 다른 사람들이 「너무 크다」 싶으면 줄여서 넘깁니다. 마지막으로 줄인 사람이 그 조각을 가져갑니다. 그러면 남은 둘은 다시 「자르고 고르기」를 합니다.
더 어려운 조건도 있습니다. “남의 몫이 부러워서는 안 된다”는 조건입니다. 이것을 네 사람 이상에서 만족시키는 방법은 2016년에야 찾아졌습니다.
이 방법이 공평한 까닭은 자르는 사람이 손해 볼 수 없게 자를 수밖에 없기 때문입니다. 한쪽을 크게 자르면 상대가 그쪽을 가져갑니다. 그러니 자르는 사람은 어느 쪽을 받아도 괜찮도록 자릅니다.
고르는 사람도 불만이 없습니다. 둘 가운데 자기 눈에 더 큰 쪽을 골랐기 때문입니다. 아무도 심판을 보지 않았는데 둘 다 만족합니다.
「내가 자르고 네가 고른다」가 공정 분배의 기본 규칙입니다.
이혼 재산 분할, 국제 협상에서의 자원 배분, 클라우드 서버 자원 나누기에 이 이론이 실제로 쓰입니다.
계단 넷 — 같은 사실을 네 깊이로
과자를 둘이 공평하게 나눠 본다
과자나 빵을 둘이서 나눌 때 "내가 자를 테니 네가 먼저 골라" 놀이를 해 봅니다. 자르는 사람은 조금이라도 한쪽이 크면 상대가 가져갈 것을 알기 때문에 최선을 다해 반으로 자릅니다.
규칙 하나만으로 서로가 만족하는 가장 평화롭고 공평한 나눔의 방법을 직접 손으로 겪어보세요.
네가 자르고 내가 고른다
자르는 사람은 똑같이 자를 수밖에 없습니다 — 남는 쪽을 갖게 되니까요.
⭐ 케이크가 커도 자르는 횟수는 사람 수에만 달렸습니다.
셋 이상일 때의 방법
이 방법을 수학에서는 '분할-선택(Divider-Chooser)' 프로토콜이라 부릅니다. 세 명일 때는 스타인하우스의 '한 사람은 자르고 둘은 다듬기(Lone Divider)' 방법을 씁니다.
한 사람이 케이크를 3등분하고 나머지 두 사람이 만족하는 조각을 표시하여 조율하면, 세 사람 모두 자기 기준으로 전체 가치의 최소 3분의 1 이상을 획득하는 비례적 분할(Proportional Division)을 완성할 수 있습니다.
셋 이상은 어렵습니다
다섯 명부터는 몇 번이면 되는지 아무도 모릅니다.
질투 없는 분할
공정 분할의 더 높은 단계는 남의 몫을 탐내지 않는 질투 없는 분할(Envy-Free Division)입니다. 3인에 대한 셀프리지-콘웨이(Selfridge-Conway) 알고리즘은 조각 다듬기(Trimming) 기법을 사용합니다.
케이크의 토핑 선호도가 사람마다 달라도 연속적인 칼의 이동을 다루는 중간값 정리와 바나흐-크나스터(Banach-Knaster) 정리에 의해 항상 질투 없는 공정 분할이 존재함이 위상수학적으로 증명됩니다.
「공평」에도 종류가 있습니다
뒤엣것이 훨씬 어렵습니다 — 모든 짝을 다 봐야 하니까요.
공정 분할 이론
공정 분할 이론(Fair Division Theory)은 미시경제학과 게임 이론의 핵심 분야입니다. 2016년 아지즈와 매켄지는 명에 대한 질투 없는 유한 단계 분할 알고리즘을 마침내 완성했습니다.
토지 경계 분쟁 해결, 상속 재산 배분, 이혼 시 재산 분할, 국가 간 어업권 쿼터 배분, 항공기 좌석 및 주파수 대역 경매 등 복잡한 사회적 갈등을 수학적으로 해결하는 최적 설계에 널리 활용됩니다.
유한 번에 끝납니다
n=4 만 해도 n^n^n^n^n — 유한하지만 우주의 원자보다 많습니다.
풀어 보기
케이크 나누기와 공정 분할. 가치가 균일하지 않은 케이크를 여러 사람이 공평하게 나누려 한다.
(1) 2명이 케이크를 나눌 때 쓰는 '내가 자르고 네가 고르기' 프로토콜에서 자르는 사람이 불만을 갖지 않는 까닭을 쓰시오.
(2) 명의 참가자가 각자의 주관적 평가로 전체 가치의 최소 이상을 받았다고 느끼는 분할 방식을 무엇이라 부르는가?
(3) 참가자 중 그 누구도 다른 사람의 몫이 자기 몫보다 크다고 생각하지 않는 완벽한 공정 분할 상태를 무엇이라 부르는가?
(2) 비례적 분할(Proportional Division), (3) 질투 없는 분할(Envy-Free Division)입니다.
답과 풀이 보기
(1) 자르는 사람은 자기 눈에 똑같아 보이도록 자릅니다. 그러니 상대가 어느 쪽을 골라도 자기에게 남는 것은 정확히 절반의 가치입니다.
⭐ 핵심은 남이 어떻게 볼지 몰라도 된다는 것입니다. 상대의 취향을 전혀 모르는 채로도 손해 보지 않는 것이 보장됩니다. 이것이 이 규칙의 진짜 힘입니다.
(2) 비례적 분할(proportional division)이라 합니다.
저마다 자기 잣대로 적어도 은 받았다고 느끼는 상태입니다.
(3) 질투 없는 분할(envy-free division)이라 합니다.
비례적 분할보다 더 센 조건입니다. 은 받았어도 옆 사람 것이 더 커 보이면 질투가 남기 때문입니다.
두 사람일 때는 '내가 자르고 네가 고르기'가 이미 질투 없는 분할이지만, 세 사람부터는 훨씬 어려워집니다 (1960 년대 셀프리지·콘웨이가 다섯 자르기로 푸는 방법을 찾아냈습니다).
네 사람 이상에서 자르는 횟수에 한계를 두고 질투 없이 나누는 방법은 2016 년에야 처음 나왔습니다. 케이크 하나 나누는 데 수학이 50 년 걸렸습니다.
여기 「풀어 보기」는 기본 한 벌입니다. 더 풀어 보고 싶으면 행복수학의 그 단원으로 건너가세요.
더 멀리
공정하게 나누는 문제는 수학이면서 사회 문제입니다.
- 유산 상속·이혼 재산 분할 — 실제로 이 이론을 쓰는 서비스가 있습니다
- 주파수 경매·자원 배분 — 같은 갈래의 문제입니다
- 직접 해 보기 — 간식 하나로 「자르고 고르기」를 해 보면 왜 공정한지 몸으로 압니다
이어지는 장
서로 좋아하는 부분이 달라도 모두가 불만 없이 공평하게 몫을 나누는 분할 알고리즘은, 단 한 번의 직선 칼질로 빵과 햄과 치즈를 모두 반씩 잘라내는 위상수학의 제139장 햄 샌드위치 정리와 함께 기하학과 조합론의 유쾌한 만남을 선사합니다.
영감을 받은 곳
한 사람이 케이크를 자르고 다른 사람이 먼저 고르는 고대의 '분할-선택(Divide and Choose)' 규칙에서 출발하여, 1944년 폴란드의 수학자 후고 스타인하우스(Hugo Steinhaus)가 수학적으로 정식화하고 바나흐, 크나스터와 함께 n명에 대한 공평 분할 이론으로 발전시켰습니다.