공평한 분할

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
- 2.1. 용어
- 2.2. 공정성의 기준
3. 분할 문제의 유형
- 3.1. 분할 대상의 특성
- 3.2. 조합 및 특수한 경우
4. 공정한 분할 방법
5. 역사
6. 대중 문화
참조

1. 개요

공평한 분할은 여러 명의 참여자가 자원, 재화 또는 악재(예: 케이크, 토지, 잡일)를 공정하게 나누는 문제를 다룬다. 분할 대상의 특성, 참여자들의 가치 평가, 공정성의 기준에 따라 다양한 유형의 분할 문제가 존재하며, 각 참여자는 주관적인 효용 함수를 통해 대상에 대한 가치를 평가한다. 공정성의 기준에는 비례 분할, 초과 비례 분할, 무시 분할, 공평한 분할, 정확한 분할 등이 있다. 공정한 분할 알고리즘은 참여자들이 자신의 가치에 따라 합리적으로 행동할 때 공정한 분할을 보장하며, 자르고 고르기, 슈타인하우스 방법, 바나흐-크나스터 마지막 절단자 방법 등 다양한 방법들이 존재한다. 공정한 분할 이론은 2차 세계 대전 중 휴고 슈타인하우스, 브로니스와프 크나스터, 스테판 바나흐에 의해 고안되었으며, 일상생활, 수학 문제, 대중 문화 등 다양한 분야에서 활용된다.

더 읽어볼만한 페이지

후생경제학 - 혼합 경제
혼합경제는 시장경제와 계획경제의 요소를 결합하여 경제적 효율성과 사회적 형평성을 추구하는 경제 시스템으로, 역사적으로 다양한 형태로 존재해왔으며 정부 개입 정도, 민간 및 공공 부문 비중, 시장 및 계획경제 결합 방식 등에 따라 여러 유형으로 나타난다.
후생경제학 - 경쟁법
경쟁법은 시장 경제의 발전에 따라 등장하여 담합 금지, 시장 지배적 지위 남용 금지, 기업 결합 제한을 기본 원칙으로 하며, 각국의 경제 상황과 디지털 경제 발전에 맞춰 발전해 온 경제 법이다.
게임 이론 - 대연정
대연정은 의원내각제 또는 이원집정부제 국가에서 대립하는 거대 정당들이 국가적 위기 극복, 정치적 봉쇄, 또는 비례대표제 하의 연립 내각 구성의 필요에 따라 연합하는 정부 형태로, 정치적 안정과 국민 통합에 기여할 수 있지만 유권자 선택권 제한 및 소수 정당 약진의 우려도 있다.
게임 이론 - 완전 정보
완전 정보 게임은 게임 이론에서 모든 플레이어가 게임의 모든 정보를 공유하는 게임을 의미하며, 체스, 틱택토, 오목 등이 이에 해당한다.
수학 - 회귀 분석
회귀 분석은 종속 변수와 하나 이상의 독립 변수 간의 관계를 모델링하고 분석하는 통계적 기법으로, 최소 제곱법 개발 이후 골턴의 연구로 '회귀' 용어가 도입되어 다양한 분야에서 예측 및 인과 관계 분석에 활용된다.
수학 - 수학적 최적화
수학적 최적화는 주어진 집합에서 실수 또는 정수 변수를 갖는 함수의 최댓값이나 최솟값을 찾는 문제로, 변수 종류, 제약 조건, 목적 함수 개수에 따라 다양한 분야로 나뉘며 여러 학문 분야에서 활용된다.

공평한 분할
개요
분야	수학, 경제학, 정치학
문제	자원의 공평한 분배
목표	모든 참가자가 공정하다고 느끼는 분배 달성
유형
물품 유형	개별 물품 연속 물품
참가자 유형	협조적 비협조적
해결 방법
절차	분할 후 선택 조정된 승자 절차 균등 분배
기준	비례성 시기심 없음 공평성
관련 개념
게임 이론	협상 게임
사회 선택 이론	공정한 할당

2. 정의

공정한 분할 문제는 참여자, 분할 대상, 공정성의 기준으로 정의된다.

분할 대상은 분할 가능 여부(케이크, 주스 vs 자동차, 피아노), 동질/이질 여부(돈 vs 케이크), 가치(탐나는 것 vs 달갑잖은 것)에 따라 분류된다.

분할의 종류에는 비례적인 분할(각자 1/n 이상), 질투 없는 분할(자신이 가장 많이 가져감), 정확한 분할(모두 똑같이) 등이 있다.^[1]

주관적 가치 이론에 따르면, 객관적 공정성은 불가능하므로, 대부분의 연구는 주관적 공정성에 초점을 맞춘다. 각 참여자는 개인적인 효용 함수(가치 함수) $V_i$ 를 가지며, 이는 분할 대상의 각 부분에 수치 값을 할당한다.^[2]

2. 1. 용어

n^영어명의 참여자가 집합 X^영어를 n^영어개의 집합으로 분할하여 각 부분집합을 한 참여자가 가져가는 것을 가정한다. 이때 분할은 다음과 같이 표현된다.

:X^영어 = X^영어 ⊔ X^영어 ⊔ ... ⊔ X^영어

분할 대상은 다음과 같이 분류할 수 있다.

'''분할 가능/불가능 여부''': 케이크나 주스처럼 '''분할 가능한 것'''과 자동차, 피아노처럼 '''분할 불가능한 것'''으로 나뉜다.
'''동질/이질 여부''': 돈과 같이 '''동질적인 것'''과 케이크처럼 각 부분마다 성분이나 맛이 다른 '''이질적인 것'''으로 나뉜다.
'''가치''': 양의 가치를 지닌 '''탐나는 것'''과 음의 가치를 지닌 '''달갑잖은 것'''(쓰레기 청소 등)으로 나뉜다.

분할의 종류는 다음과 같다.

'''비례적인 분할''': 1/n^영어 이상을 가져가는 분배
'''질투 없는 분할''': 자신이 가장 많이 가져간 분할 (남의 떡이 더 커 보이지 않는 분할)
'''정확한 분할''': 누구나 똑같이 가져간 분할

공정성 외에도, 때로는 분할이 파레토 효율성을 갖기를 원한다. 즉, 다른 사람을 더 나쁘게 만들지 않고서는 누군가를 더 좋게 만들 수 없는 분배를 의미한다. "효율성"이라는 용어는 경제학의 효율적 시장 개념에서 유래했다. 한 명의 플레이어가 모든 것을 얻는 분할은 이 정의에 따라 최적이기 때문에, 이것만으로는 공정한 몫조차 보장하지 않는다. 효율적인 케이크 자르기 및 공정성의 가격도 참조하라.

현실에서는 사람들이 다른 플레이어가 재화를 어떻게 평가하는지 정확하게 알고, 이에 대해 매우 신경 쓰는 경우가 있다. 서로의 평가에 대한 완전한 지식을 가진 경우는 게임 이론으로 모델링할 수 있다. 부분적인 지식은 모델링하기 매우 어렵다. 공정한 분할의 실질적인 측면에서 중요한 부분은 그러한 부분적 지식이나 작은 실수에도 불구하고 잘 작동하는 절차를 고안하고 연구하는 것이다.

추가적인 요구 사항은 공정한 분할 절차가 전략적 무결성을 가져야 한다는 것이다. 즉, 참가자가 자신의 진정한 평가를 보고하는 것이 지배 전략이어야 한다. 이 요구 사항은 일반적으로, 특히 공정성 및 파레토 효율성과 결합할 때 충족하기 매우 어렵다. 그 결과, 종종 인센티브 호환성으로 약화되는데, 이는 플레이어가 특정 해결 개념에 따라 행동하는 경우에만 자신의 진정한 평가를 보고하도록 요구한다.

2. 2. 공정성의 기준

주관적 가치 이론에 따르면, 각 항목의 가치를 객관적으로 측정할 수 없다. 따라서, 다른 사람들이 각 항목에 서로 다른 가치를 부여할 수 있으므로 ''객관적 공정성''은 불가능하다. 사람들이 공정성의 개념을 어떻게 정의하는지에 대한 경험적 실험은 결정적인 결과를 내지 못했다.^[2]

따라서, 공정성에 대한 대부분의 현재 연구는 ''주관적 공정성''의 개념에 초점을 맞추고 있다. 여기서 각

n

명의 사람들은 개인적이고 주관적인 ''효용 함수'' 또는 ''가치 함수'' (

V_i

)를 가진다고 가정하며, 이 함수는

C

의 각 부분 집합에 수치 값을 할당한다.

이러한 주관적인 가치 함수를 기반으로, 공정한 분할을 위한 여러 기준들이 제시되었다. 이 기준들은 때로는 서로 충돌하지만, 종종 결합될 수 있다. 아래 설명된 기준은 각 참여자가 동일한 양을 받을 자격이 있을 때만 해당된다.

비례 분할: 모든 참여자가 ''자신의 가치 함수에 따라'' 최소한 자신의 몫을 받는 것을 의미한다. 예를 들어, 세 사람이 케이크를 나눈다면, 각 사람은 자신의 평가에 따라 최소한 3분의 1을 얻는다. 즉, ''n''명의 각 사람은 전체 가치의 최소 1/''n''으로 평가하는 '' $C$ ''의 부분 집합을 얻는다.
$V_i(X_i) \ge V_i(C)/n$ (모든 i에 대해)
초과 비례 분할: 각 참여자가 1/''n''보다 엄격하게 더 많이 받는 분할이다. (이러한 분할은 참여자들이 서로 다른 평가를 가지고 있는 경우에만 존재한다.)
$V_i(X_i) > V_i(C)/n$ (모든 ''i''에 대해)
무시 분할: 아무도 다른 사람의 몫을 자신의 몫보다 더 원하지 않도록 보장한다. 즉, 모든 사람은 자신의 몫을 다른 모든 몫만큼, 혹은 그 이상으로 평가한다.
$V_i(X_i) \ge V_i(X_j)$ (모든 i와 j에 대해)
집단 무시 분할: 에이전트의 하위 집합이 동일한 크기의 다른 하위 집합을 시기하지 않도록 보장한다. 이는 무시 분할보다 더 강력한 조건이다.
공평한 분할: 모든 참여자가 자신의 조각에 대한 평가가 동일하다는 것을 의미한다. 즉, 각 참여자가 동일한 가치를 받거나 "동일한 행복"을 경험한다. 참여자에게 평가를 묻는 경우 진실하지 않아도 되기 때문에 이는 달성하기 어려운 목표이다.
$V_i(X_i) = V_j(X_j)$ (모든 i와 j에 대해)
정확한 분할(합의 분할): 모든 참여자가 각 몫의 가치에 동의하는 분할이다.
$V_i(X_i) = V_j(X_i)$ (모든 i와 j에 대해)

참가자가 느끼는 공평성의 기준은 다음과 같이 요약할 수 있다.

기준	설명
비율적 공평	각자의 가치 기준으로, 자신의 몫이 전체 가치의 1/n 이상이라고 생각하는 경우
부러움 없는 공평	자신의 몫의 가치가 다른 사람의 몫의 가치 이상이라고 생각하는 경우
정확한 공평	자신의 몫과 다른 사람의 몫 모두 정확히 전체 가치의 1/n이라고 생각하는 경우

위 기준들 사이의 관계는 다음과 같다.

부러움 없는 공평이 실현되면 자동적으로 비율적 공평도 실현된다.
정확한 공평이 실현되면 부러움 없는 공평과 비율적 공평도 자동적으로 실현된다.

3. 분할 문제의 유형

공정한 항목 할당, 공정한 자원 할당, 공정한 케이크 자르기 등 분할 대상의 특성에 따라 다양한 유형의 공정한 분할 문제가 연구된다.

분할 문제는 $n$ 명의 참여자가 집합 $X$ 를 $n$ 개의 부분집합으로 나누어 각자 가져가는 방식으로 이루어진다. 이때, 분할 대상은 다음과 같이 여러 유형으로 나뉜다.

분할 가능성: 케이크나 주스처럼 분할 가능한 것과 자동차, 피아노처럼 분할 불가능한 것이 있다.
동질성: 돈과 같이 모든 부분이 동일한 가치를 지니는 동질적인 것과 케이크처럼 부분마다 다른 가치를 지니는 이질적인 것이 있다.
가치: 양의 가치를 지닌 탐나는 것과 음의 가치를 지닌 달갑잖은 것(쓰레기 청소 등)이 있다.

이러한 구분에 따라 공정한 항목 할당, 공정한 자원 할당, 공정한 케이크 자르기, 공정한 잡일 분담 등 여러 유형의 공정한 분할 문제가 연구되었다. 분할 대상에는 참가자 모두가 좋아하거나 싫어하는 것, 균질하거나 이질적인 것, 자유롭게 분할이 가능하거나 불가능한 것 등 다양한 설정이 가능하다.

3. 1. 분할 대상의 특성

분할 대상은 여러 가지 특성을 가질 수 있다. 우선, 케이크나 주스처럼 '''분할 가능한 것'''과 자동차나 피아노처럼 '''분할 불가능한 것'''으로 나눌 수 있다. 돈처럼 모든 부분이 동일한 가치를 가지는 '''동질적인 것'''과 케이크처럼 부분마다 다른 가치를 가지는 '''이질적인 것'''으로도 나눌 수 있다.

분할 대상은 또한 가치에 따라 분류할 수 있는데, 양의 가치를 지닌 것은 '''탐나는 것''', 음의 가치를 지닌 것은 '''달갑잖은 것'''(쓰레기 청소 등)으로 불린다.

이러한 특성에 따라 공정한 분할 문제는 다음과 같이 세분화된다.

분할 대상의 특성	문제 유형
분할 불가능, 이질적	공정한 항목 할당
분할 가능, 동질적	공정한 자원 할당 (특수한 경우: 단일 동질적 자원의 공정한 분할)
분할 가능, 이질적	공정한 케이크 자르기 (특수한 경우: 공정한 파이 자르기)
분할 가능, 이질적 (악재)	공정한 잡일 분담

이 외에도 다음과 같은 복합적인 문제 유형이 존재한다.

임대 조화 (룸메이트 문제): 분할 불가능하고 이질적인 재화(방)와 동질적이고 분할 가능한 악재(임대료)를 동시에 분할한다.
공정한 강 공유: 국제 하천의 물을 하천을 따라 흐르는 국가들 사이에 분할한다.
공정한 임의 할당: 분할에 대한 복권 분할 – 분할 불가능한 재화를 할당할 때 특히 일반적이다.

3. 2. 조합 및 특수한 경우

공정한 분할 문제는 집합

C

(보통 "케이크"라고 부름)와

n

명의 플레이어 간의 분할 문제로 정의된다. 분할은

C

를

n

개의 서로소 부분 집합으로 나누는 것이다. 즉,

C = X_1 \sqcup X_2 \sqcup\cdots \sqcup X_n

과 같이 각 플레이어에게 하나의 부분 집합을 할당한다.

집합

C

는 다음과 같은 유형이 있을 수 있다.

분할 불가능한 항목의 유한 집합: $C = \{\text{피아노}, \text{자동차}, \text{아파트}\}$ 처럼 각 항목이 한 사람에게 온전히 주어져야 하는 경우이다.
분할 가능한 자원을 나타내는 무한 집합: 돈, 케이크 등이 이에 해당한다. 수학적으로 분할 가능한 자원은 실수 공간의 부분 집합으로 표현되기도 한다. 예를 들어 구간 [0,1]은 긴 케이크를, 단위 원반은 파이를 나타낼 수 있다.

분할될 집합은 다음과 같이 구분할 수 있다.

동질적: 돈처럼 양만 중요한 경우이다.
이질적: 여러 재료와 아이싱이 섞인 케이크처럼 다양한 요소가 혼합된 경우이다.

분할될 항목에 대한 가정은 다음과 같다.

재화: 자동차나 케이크처럼 선호되는 대상이다.
악재: 집안일처럼 싫어하는 대상이다.

이러한 구분에 따라 여러 유형의 공정한 분할 문제가 연구되었다.

공정한 항목 할당: 분할 불가능하고 이질적인 재화를 분할한다.
공정한 자원 할당: 분할 가능하고 동질적인 재화를 분할한다. 단일 동질적 자원의 공정한 분할이 특수한 경우이다.
공정한 케이크 자르기: 분할 가능하고 이질적인 재화를 분할한다. 케이크가 원형인 경우는 공정한 파이 자르기라고 한다.
공정한 잡일 분담: 분할 가능하고 이질적인 악재를 분할한다.

조합 및 특수한 경우는 다음과 같다.

임대 조화(룸메이트 문제): 분할 불가능하고 이질적인 재화(방)와 분할 가능한 악재(임대료)를 함께 분할한다.
공정한 강 공유: 강물을 따라 위치한 국가 간에 국제 하천의 물을 분할한다.
공정한 임의 할당: 분할 불가능한 재화 할당 시 복권을 활용하는 방식이다.

최근에는 개별 에이전트에서 에이전트 그룹(미리 결정된 그룹)으로 공정한 분할 모델이 확장되었다. (그룹 간의 공평한 분할 참조)

분할 대상은 참가자 모두가 선호하거나 싫어하는 것, 균질하거나 이질적인 것, 자유롭게 분할 가능하거나 불가능한 것 등 다양한 설정이 가능하다.

공평성에 대한 기준은 다음과 같다.

자신의 몫이 전체 가치의 1/n 이상이라고 여기는 경우
자신의 몫이 다른 사람의 몫보다 가치 있다고 여기는 경우
자신과 다른 사람의 몫이 모두 전체 가치의 1/n이라고 여기는 경우

참가자는 2명, 3명, 또는 일반적인

n

명일 수 있다. 의사 결정은 참가자들이 순서대로 진행하거나, 동시에 분할안을 보면서 진행할 수 있다.

공정한 분할 문제 해결을 위한 다양한 알고리즘(근사 해법 포함)이 개발되었지만, 대부분은 공정한 분할법의 존재 증명에 목적을 둔다. 일부는 일상 문제 해결에 유용한 방법으로 개발되기도 했다.

4. 공정한 분할 방법

공정한 분할 절차은 데이터와 각자의 평가에 따라 플레이어가 수행해야 하는 행동을 나열한다. 유효한 절차는 자신의 평가에 따라 합리적으로 행동하는 모든 플레이어에게 공정한 분할을 보장한다. 이때, 각 플레이어의 목표는 자신이 얻을 수 있는 최소량을 최대화하는 맥시민을 달성하는 것이다.

절차는 ''이산'' 절차와 ''연속'' 절차로 나눌 수 있다. 이산 절차는 한 번에 한 사람만 케이크를 자르거나 표시하는 것을 포함하고, 연속 절차는 한 플레이어가 칼을 움직이고 다른 플레이어가 "멈춰"라고 말하는 것과 같은 것을 포함한다.

몇 가지 예를 들면 다음과 같다.

인원 수	방법
2인	분할 및 선택
2인	브람스-테일러 승자 조정법(영어판)
2인	오스틴의 2개 칼 이동법(영어판)
3인	슈타인하우스 방법
3인	셀프리지-콘웨이 방법(영어판)
3인	스트롱키스트 4개의 칼 이동 방법(영어판)
n인	바나흐-크나스터 마지막 절단자 방법(영어판)
n인	듀빈스-스패니어 단일 칼 이동 방법(영어판)
n인	브람스-테일러 절대적 우위 방법(영어판)
n인	시몬스-수 스펄너 채색 근사법(영어판)

각 플레이어가 단일 연결 조각을 받도록 되어 있다면, 유한 프로토콜(무제한인 경우에도)은 3명 이상의 플레이어 간에 질투가 없는 케이크 분할을 보장할 수 없다.^[3] 그러나 이 결과는 해당 작업에 제시된 모델에만 적용되며, 중재자가 플레이어의 평가 기능에 대한 완전한 정보를 가지고 이를 기반으로 분할을 제안하는 경우에는 적용되지 않는다.^[4]

일상생활에서 유용한 공평 분할법으로는 브람스-테일러 승자 조정법이 이혼 부부의 재산 분할에 사용된다. 스페르너 채색 근사법은 단독주택을 여러 사람이 임대하는 경우에 유용하다.^[13]

4. 1. 2인

자르고 고르기는 두 사람 모두 질투 없이 1/2 이상을 가져가는 방법이다. 참가자 2명이 좋아하는 대상물을 자유롭게 분할할 수 있는 경우의 방법으로, 기원전부터 알려진 방법으로 분할 및 선택법(divide and choose)이 있다. 자르는 사람·선택하는 사람의 방법이라고도 불린다. 먼저 한쪽의 자르는 사람이 자신의 가치 기준에 따라 대상물을 가치가 동일한 2개의 부분으로 분할하고, 다음으로 선택하는 사람이 자신의 가치 기준에 따라 더 큰 가치를 선택하며, 마지막으로 나머지를 자른 사람이 받는 방법이다. 이 방법은 어느 쪽도 자신의 몫의 가치가 다른 사람의 몫의 가치 이상이라고 느낄 수 있는 우수한 방법이다. 분할 및 선택법은 싫어하는 것을 참가자 2명이 분할하는 경우에도 이용할 수 있다.

일상생활에서 행해지는 또 다른 방법으로, 성분 분할 체적 등분법이 있다. 이는 대상물을 다른 성분으로 분할할 수 있는 경우, 성분별로 분할하고, 각각을 인원수 분의 1의 동일한 체적으로 분할한다. 어떤 참가자도 전체 가치의 인원수 분의 1의 가치를 얻었다고 느낄 수 있다. 단, 이 방법에서는 각자가 느끼는 획득 가치의 합계는 전체 가치의 1배에 머문다.

2인용 분할 및 선택 방법
2인용 브람스-테일러 승자 조정법(영어판)
2인용 오스틴의 2개 칼 이동법 (영어판)

4. 2. 3인 이상

공정한 분할 절차는 보이는 데이터와 평가에 따라 참여자가 수행해야 하는 동작을 나열한다. 유효한 절차는 자신의 평가에 따라 합리적으로 행동하는 모든 참여자에게 공정한 분할을 보장하는 절차이다. 동작이 참여자의 평가에 따라 달라지는 경우, 절차는 합리적인 참여자가 따를 전략을 설명한다. 참여자는 조각의 가치가 다른 것처럼 행동할 수 있지만 일관성을 유지해야 한다. 예를 들어, 절차가 첫 번째 참여자가 케이크를 두 개의 동일한 부분으로 자르고 두 번째 참여자가 조각을 선택하라고 한다면, 첫 번째 참여자는 두 번째 참여자가 더 많이 얻었다고 주장할 수 없다.

참여자는 다음과 같은 작업을 수행한다.

공정한 분할에 대한 기준에 동의한다.
유효한 절차를 선택하고 규칙을 따른다.

각 참여자의 목표는 자신이 얻을 수 있는 최소량을 최대화하는 것, 즉 맥시민을 달성하는 것으로 가정한다.

절차는 ''이산'' 절차와 ''연속'' 절차로 나눌 수 있다. 예를 들어, 이산 절차는 한 번에 한 사람만 케이크를 자르거나 표시하는 것을 포함한다. 연속 절차는 한 참여자가 칼을 움직이고 다른 참여자가 "멈춰"라고 말하는 것과 같은 것을 포함한다. 다른 유형의 연속 절차는 한 사람이 케이크의 모든 부분에 가치를 할당하는 것을 포함한다.

공정한 분할 절차 목록은 :Category:Fair division protocols를 참조할 수 있다.

각 참여자가 단일 연결 조각을 받도록 되어 있다면, 유한 프로토콜(무제한인 경우에도)은 3명 이상의 참여자 간에 질투가 없는 케이크 분할을 보장할 수 없다.^[3] 그러나 이 결과는 해당 작업에 제시된 모델에만 적용되며, 예를 들어 중재자가 참여자의 평가 기능에 대한 완전한 정보를 가지고 이를 기반으로 분할을 제안하는 경우에는 적용되지 않는다.^[4]

다음은 유명한 공평 분할 알고리즘 중 일부를 나타낸 것이다. 2명 이상의 일반적인 인원을 위한 방법은 n명용으로 표기한다.

3인용 슈타인하우스 방법
n인용 바나흐-크나스터 마지막 절단자 방법(영어판)
n인용 듀빈스-스패니어 단일 칼 이동 방법(영어판)
2인용 분할 및 선택 방법
2인용 브람스-테일러 승자 조정법(영어판)
3인용 셀프리지-콘웨이 방법(영어판)
3인용 스트롱키스트 4개의 칼 이동 방법(영어판)
n인용 브람스-테일러 절대적 우위 방법(영어판)
n인용 시몬스-수 스펄너 채색 근사법(영어판)

4. 3. 기타 방법

승자 조정법은 이혼 부부의 재산 분할에 사용되는 공평 분할법이다. 이 방법과 스페르너 채색 근사법은 모두 여러 항목을 점수로 평가하고, 항목 전체 또는 일부만 분할하여 양측 모두 자신의 획득 점수가 상대방 이상이라고 느끼도록 한다.

승자 조정법: 두 사람이 같은 목록의 여러 대상 항목을 합계 100점이 되도록 점수 평가하고, 1개 이하의 항목만 세분할을 허용한다.
스페르너 채색 근사법: 단독주택을 여러 사람이 임대하는 경우에 유용하다. 예를 들어, 서로 다른 유형의 방 3개를 가진 단독주택을 3명이 공동으로 임대하는 경우, 각자의 첫 번째 희망 방을 할당하는 방법을 찾는다. 이 방법은 연속 수학의 브라우어 고정점 정리의 이산 수학 버전인 스페르너의 보조 정리를 이용한다.^[13]

5. 역사

제2차 세계 대전 말, 폴란드의 수학자 휴고 슈타인하우스, 브로니스와프 크나스터, 스테판 바나흐가 공정한 분할 이론을 고안했다. 이들은 당시 폴란드에 있던 스코티시 카페에서 만나곤 했다.^[5] 1944년에는 임의의 수의 참여자를 위한 비례적 분할(공정한 분할) 방법인 '최후의 축소자' 방법이 고안되었다. 슈타인하우스는 1947년 9월 17일 워싱턴 D.C.에서 열린 계량경제학회 회의에서 이 문제를 처음 공개하면서 바나흐와 크나스터의 공로를 인정했다. 그는 또한 이 분할에 필요한 최소 절단 횟수를 찾는 문제도 제안했다.^[5]

솔 가펀켈에 따르면, 케이크 분할 문제는 20세기 수학에서 가장 중요한 미해결 문제 중 하나였으며, 1995년 스티븐 브람스와 앨런 D. 테일러가 브람스-테일러 절차를 통해 문제의 가장 중요한 변형을 해결했다.^[5]

분할과 선택의 기원은 명확히 문서화되어 있지 않다. 협상과 물물교환 관련 활동은 오래되었으며, 2명 이상이 관련된 협상 또한 매우 흔하다. 포츠담 회담은 최근의 주목할 만한 예시이다.^[5]

질투가 없는 케이크 분할의 역사는 질투가 없는 케이크 분할 문서를 참조하라.

6. 대중 문화

17마리 낙타 상속 문제는 17마리의 낙타(또는 코끼리, 말)를 1/2, 1/3, 1/9의 비율로 공정하게 분할하는 문제이다. 이는 고대에서 유래되었다고 주장되는 인기 있는 수학 문제이지만, 최초로 문서화된 출판물은 18세기 이란에서 이루어졌다.^[6]
TV 드라마 ''넘버스'' 시즌 3 에피소드 "One Hour"에서 찰리는 납치범이 요구하는 금액에 적용되는 케이크 분할 문제에 대해 이야기한다.
이스라엘 영화 성 클라라에서 러시아 이민자는 이스라엘 수학 선생님에게 원형 케이크를 7명에게 어떻게 공정하게 분할할 수 있는지 묻는다. 그의 대답은 케이크 중앙을 가로질러 3번의 직선 절단을 하여 8개의 동일한 조각을 만드는 것이다. 7명밖에 없으므로 공산주의 정신에 따라 한 조각을 버려야 한다.

참조

_[1] 논문 Game Theoretic Analysis of a bankruptcy Problem from the Talmud http://www.elsevier.[...]
_[2] 논문 On dividing justly
_[3] 논문 Envy-free cake divisions cannot be found by finite protocols https://eudml.org/do[...] 2022-10-26
_[4] 간행물 The Efficiency of Fair Division with Connected Pieces https://link.springe[...] Springer 2010
_[5] 서적 More Equal than Others: Weighted Voting COMAP
_[6] 논문 Le partage des dix-sept chameaux et autres arithmétiques attributes à l'immam 'Alî: Mouvance et circulation de récits de la tradition musulmane chiite https://ageron.users[...]
_[7] 서적 Mathematical Snapshots
_[8] 서적 aha! Insight
_[9] 서적 How to cut a cake and other mathematical conundrums
_[10] 웹사이트 Dinosaur Comics! http://www.qwantz.co[...]
_[11] 서적 Fair Division: from Cake-Cutting to Dispute Resolution Cambridge University Press
_[12] 서적 Cake-Cutting Algorithms: Be Fair If You Can A K Peters
_[13] 논문 Rental harmony: Sperner’s Lemma in Fair Division

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com