공정분할

공정한 분배는 게임 이론의 문제이며, 각각의 사람들이 그들의 정당한 몫을 받을 수 있도록 그들에게 자격이 있는 여러 명의 사람들 사이에서 자원을 나누는 것이다.이 문제는 상속분할, 파트너십 해소, 이혼 합의, 전자 주파수 할당, 공항 교통 관리, 지구 관측 위성 개발 등 다양한 현실 환경에서 발생한다.수학, 경제학(특히 사회적 선택 이론), 분쟁 해결 등에서 활발한 연구 분야입니다.공정분할의 핵심 원칙은 그러한 분할은 선수 스스로 수행해야 한다는 것이다. 아마도 중재자를 사용하겠지만, 선수만이 그들이 상품을 어떻게 평가하는지 알고 있기 때문에 확실히 중재자를 사용해서는 안 된다.

전형적인 공정분할 알고리즘은 나눗셈과 선택이다.이는 서로 다른 취향을 가진 두 에이전트가 케이크를 나누어 자신이 최고의 조각을 얻었다고 믿게 할 수 있다는 것을 보여준다.공정분할 연구는 이 절차의 다양한 복잡한 환경으로의 확장으로 볼 수 있다.

공정분할 문제는 분할하는 상품의 성격, 공정성의 기준, 참가자의 성격과 선호도, 그리고 그 밖의 분할의 질을 평가하는 기준에 따라 여러 가지 종류가 있다.

나눌 수 있는 것

형식적으로 공정한 분할 문제는 $세트$C(종종 "더 케이크$"$라고 불린다)와$$n명의 $플레이어$로 $구성$된 그룹에 의해 정의됩니다.디비전은 C$\$$displaystyle$$$C를$$ $n개$의$$\$displaystyle$n개의 분리된$$ 서브셋으로 $분할$한 것입니다.$C{\displaystyle }$ $=$ ${\displaystyle {X\mathrm{}}_{}}$ 1${\displaystyle {}_{}{}_{}}$ X ${\displaystyle {2\mathrm{}}_{}\bigsqcup \bigsqcup }$ ${\displaystyle {}_{}}$ \ $displaystyle C$= X _ {$1}$ \ $sqcup X _$ {2} \ $cdots$\$cup X _$ n$$} 。

$세트{\displaystyle }$ C$(\displaystyle$ C$)$에는 다양한 유형이 있습니다.

• $(\displaystyle$ C$)$는 분할할 수 없는 아이템의 유한 세트(예: $C{\displaystyle }$ ${\displaystyle =}$ { ${\displaystyle p}$ i ${\displaystyle a}$ ${\displaystyle \mathrm{no}}$ ${\displaystyle ,}$ ${\displaystyle c}$ ${\displaystyle ar}$ , ${\displaystyle a}$ ${\displaystyle r}$ ${\displaystyle r}$ t ${\displaystyle m}$ ${\displaystyle e}$ n t$$ { $display style$ C = \ {$piano$ ,$car$ , apartment$$\ $\}$ )일 수 있습니다.이러한 아이템은 모두 한 사람에게 주어져야 합니다.
• $(\displaystyle$ C$)$는 분할 가능한 자원을 나타내는 무한 집합(예: 돈 또는 케이크)입니다.수학적으로 분할 가능한 자원은 종종 실제 공간의 서브셋으로 모델링됩니다. 예를 들어 섹션 [0,1]은 병렬로 절단해야 하는 길고 좁은 케이크를 나타낼 수 있습니다.장치 디스크는 애플 파이를 나타낼 수 있습니다.

또한 분할되는 세트는 다음과 같습니다.

• 동종 – 금액만 문제가 되는 돈, 또는
• 이종 – 다른 성분, 다른 아이싱 등을 가진 케이크 등

마지막으로, 분할할 항목이 다음과 같은지 여부에 대해 몇 가지 가정을 하는 것이 일반적이다.

• 상품 – 자동차, 케이크, 또는
• 집안일 같은 나쁜 일.

이러한 차이를 바탕으로 공정분할 문제의 몇 가지 일반적인 유형이 연구되었다.

• 공정한 품목 할당 - 분리할 수 없는 상품과 이질적인 상품 세트를 나눕니다.
• 공정한 자원 할당 - 분할 가능한 상품과 균질한 상품 세트를 분할합니다.특수한 경우는 단일 동종 자원의 공평한 분배입니다.
• 공평한 케이크 커팅 - 분리 가능한 이질적인 상품을 나누는 것.특별한 경우는 케이크가 동그라미일 때인데, 이 문제는 페어 파이 커팅이라고 불립니다.
• 공평한 잡무 구분 - 분할할 수 있는 이질적인 나쁜 일을 구분합니다.

조합과 특수한 경우도 자주 있습니다.

• 임대 조화(동거인 문제라고도 함) - 분리할 수 없는 이질적인 상품 세트(예: 아파트 방)를 분할하는 동시에 균질적인 분할 불량(아파트 임대료)을 분할합니다.
• 공정한 하천 공유 - 국제 하천을 흐르는 물을 하천을 따라 있는 국가 간에 분배합니다.
• 공정한 무작위 할당(분할 복권을 분할하는 것)은 분리할 수 없는 상품을 할당할 때 특히 흔하다.

공정성의 정의

일반적으로 공정 분할이라고 불리는 것의 대부분은 중재 사용 때문에 이론상 그렇게 간주되지 않는다.이런 상황은 실생활의 문제에서 따온 수학 이론에서 꽤 자주 발생한다.부동산이 파산했을 때의 권리 부여에 관한 Talmud의 결정은 ^[1]공정성에 대한 상당히 복잡한 생각을 반영하고 있으며, 대부분의 사람들은 그것을 공정하다고 생각한다.그러나 이는 청구인의 평가에 따른 분할이 아니라 랍비들의 법적 논쟁의 결과이다.

주관적 가치 이론에 따르면, 각 항목의 가치에 대한 객관적인 척도는 있을 수 없습니다.따라서 각 항목에 다른 가치를 부여할 수 있기 때문에 객관적인 공정성은 불가능하다.공정성의 개념을 정의하는^[2] 방법에 대한 경험적 실험은 결론에 이르지 못하는 결과를 낳는다.

따라서 공정성에 대한 대부분의 최근 연구는 주관적 공정성의 개념에 초점을 맞추고 있다.$(\$$displaystyle$ n$)$의 각 사용자는$$$C$의$$각 서브셋에 수치값을 할당하는 $(\$$displaystyle$$V_{$i$\})$라는 개인적이고 주관적인 효용 함수 또는 값 함수를 가지고 있다고 가정합니다.많은 경우 함수는 정규화된 것으로 간주되므로 빈 집합은 0(${\displaystyle {}_{}}$)으로 평가됩니다.${\displaystyle i_{}}$ ${\displaystyle )}$ ) ${\displaystyle =}$ $(모든$ i에 대해 0(\$style$ V_${i}(\emptyset$)=$0$$)$이며, 전체 항목 집합은 1(${\displaystyle V_{}}$i (${\displaystyle C)}$ $=$ 1(모든 i에 대해 1$(모든$ i에 대해 1\$style$ V_${i}(C$)=$1$$})$로 지정되며, 바람직하지 않은 경우에는 -1로 지정됩니다.예를 들면 다음과 같습니다.

• C$(\displaystyle$ C$)$가 분할할 수 없는 항목 세트인 $경우{\displaystyle }$, Alice는 각 항목에 1/3의 값을 할당할 수 있습니다. 즉, 각 항목은 다른 항목과 동일하게 중요함을 의미합니다.밥은 {car, aparty}세트에 1의 값을 할당하고 X를 제외한 다른 모든 세트에 0의 값을 할당할 수 있습니다. 즉, 차와 아파트만 함께, 또는 아파트만 혼자, 또는 피아노와 함께 하는 것은 그에게 가치가 없습니다.
• C$(\displaystyle$ C$)$가 길고 좁은 케이크(간격 [0,1]로 모델링됨)인 경우 Alice는 각 서브셋에 길이에 비례하는 값을 할당할 수 있습니다. 즉, 아이싱에 관계없이 가능한 한 많은 케이크를 원합니다.예를 들어, Bob은 [0.4, 0.6]의 부분 집합에만 값을 할당할 수 있습니다. 왜냐하면 케이크의 이 부분에는 체리가 포함되어 있고 Bob은 체리에만 신경을 쓰기 때문입니다.

이러한 주관적 가치 함수에 기초하여, 공정분할에 대해 널리 사용되는 많은 기준이 있다.이들 중 일부는 서로 충돌하지만 종종 결합될 수 있습니다.여기서 설명하는 기준은 각 참가자가 동일한 금액을 받을 수 있는 경우에만 적용됩니다.

• 비례분할은 모든 사람이 자신의 가치 함수에 따라 최소한 정당한 몫을 받는 것을 의미한다.예를 들어, 3명이 케이크를 분할하면 각각 자신의 가치로 3분의 1 이상을 얻을 수 있습니다. 즉, 각 n명이 전체 값의 1/n 이상으로 평가하는 C$(\displaystyle$ C$)$의 서브셋을 얻을 수 있습니다.
  • ${\displaystyle {}_{}{}_{}}$ i${\displaystyle {}_{}}$( ${\displaystyle X_{}}$i ${\displaystyle )\ge }$ ${\displaystyle {}_{}{i}_{}}$ (${\displaystyle C}$) /$$ \ $displaystyle V_{i}(X_{i})\geq V_{i}(C)/n$$.$
• 초비례 부문은 각 선수가 1/n 이상을 받는 부문이다(이러한 부문은 선수들이 다른 평가를 받는 경우에만 존재한다).
  • $displaystyle V_{i}$$i$> $V_{i}(C)/n} ($모든 i)
• 질투가 없는 부문은 어느 누구도 자신의 몫보다 다른 사람의 몫을 원하지 않는다는 것을 보증합니다. 즉, 모든 사람이 최소한 다른 모든 주식만큼 자신이 가치있게 여기는 몫을 얻게 됩니다.
  • ${\displaystyle {}_{}{}_{}}$ i${\displaystyle {}_{}}$( X${\displaystyle {}_{}}$i )${\displaystyle {}_{}}$ V${\displaystyle {}_{}{i}_{}}$ ( ${\displaystyle {}_{}{j}_{}}$) \ $displaystyle V_{i}(X_{i})\geq V_{i}(X_$${j})$
• 그룹이 없는 분할은 에이전트의 서브셋이 같은 크기의 다른 서브셋을 부러워하지 않음을 보증합니다.이는 envy-freeness보다 훨씬 강력합니다.
• 공평한 분배는 모든 사람이 정확히 같은 행복을 느낀다는 것을 의미합니다. 즉, 플레이어가 자신의 평가로 받는 케이크의 비율은 모든 플레이어에게 동일합니다.이는 참가자가 자신의 평가를 묻는다면 진실할 필요가 없기 때문에 어려운 목표이다.
  • $displaystyle V_{i}(X_{$$$$= 모든$ i 및 j에 대해$V_{$j}($X_{$j$$})
• 정확한 부문(일명 컨센서스 부문)은 모든 참가자가 각 주식의 가치에 동의하는 부문이다.
  • $displaystyle V_{i}(X_{i)$= $모든$ i 및 j에 대해$V_{$j}($X_{$i$$$})}.$

위의 모든 기준은 참가자가 동등한 자격을 가지고 있다고 가정합니다.참가자가 다른 권리를 가지고 있는 경우(예를 들어, 각 파트너가 다른 금액을 투자한 파트너십에서), 그에 따라 공정성 기준을 조정해야 합니다.다양한 자격을 가진 비례 케이크 커팅을 참조하십시오.

기타 요건

공정성뿐만 아니라, 때로는 분할이 파레토에 최적인 것이 바람직하다. 즉, 다른 할당은 다른 누군가를 더 나쁘게 만들지 않고 누군가를 더 좋게 만들 수 없다.효율성이라는 용어는 효율적인 시장의 경제적 아이디어에서 유래합니다.한 명의 선수가 모든 것을 얻는 부문은 이 정의에 의해 최적화되므로 그것만으로는 공정한 점유율조차 보장되지 않는다.효율적인 케이크 커팅 및 공정성 가격도 참조하십시오.

현실에서 사람들은 때때로 다른 선수들이 상품을 어떻게 평가하는지 매우 정확하게 알고 있으며 그들은 그것에 대해 매우 관심을 가질 수 있다.그들이 서로의 평가에 대해 완전히 알고 있는 경우는 게임 이론에 의해 모델화될 수 있다.부분적인 지식은 모델화하기가 매우 어렵다.공정분할의 실용적인 측면의 주요 부분은 그러한 부분적인 지식이나 작은 실수에도 불구하고 잘 작동하는 절차를 고안하고 연구하는 것이다.

또 다른 요구사항은 공정분할 절차가 진실한 메커니즘이어야 한다는 것이다. 즉, 참여자가 자신의 진정한 가치를 보고하는 지배적인 전략이 되어야 한다.이 요건은 보통 공정성과 파레토 효율성의 조합으로 충족시키기가 매우 어렵습니다.

절차들

공정분할절차는 가시적인 자료와 그 평가의 관점에서 참가자가 수행해야 할 조치를 열거한다.유효한 절차는 자신의 평가에 따라 합리적으로 행동하는 모든 참가자에게 공정한 분배를 보장하는 절차이다.행동이 참가자의 평가에 따라 달라지는 경우 절차는 합리적인 참가자가 따를 전략을 기술하는 것입니다.플레이어는 하나의 작품이 다른 가치를 지닌 것처럼 행동할 수 있지만 일관성이 있어야 합니다.예를 들어 첫 번째 플레이어가 케이크를 두 부분으로 똑같이 자른 후 두 번째 플레이어가 한 조각을 선택한다면 첫 번째 플레이어가 두 번째 플레이어가 더 많이 받았다고 주장할 수 없다.

플레이어의 역할은 다음과 같습니다.

• 공정한 분배의 기준에 합의하다
• 올바른 절차를 선택하고 해당 규칙을 따르십시오.

각 플레이어의 목적은 얻을 수 있는 최소량을 최대화하는 것, 즉 최대치를 달성하는 것이라고 가정합니다.

절차는 이산 절차와 연속 절차로 나눌 수 있습니다.예를 들어 개별 절차는 한 번에 한 사람만 케이크를 자르거나 표시해야 합니다.연속 절차는 한 선수가 칼을 움직이며 다른 선수가 "정지"라고 말하는 것과 같은 것을 포함합니다.또 다른 유형의 연속 절차는 케이크 모든 부분에 값을 할당하는 사람을 포함합니다.

공정분할 절차 목록은 범주를 참조하십시오.공정분할규정.

내선번호

최근에는 공정분할 모델이 개별 대리점에서 가족 대리점(사전 결정 집단)으로 확대되고 있다.그룹 간 공정한 분할을 참조하십시오.

역사

솔 가펑클에 따르면, 케이크 자르기 문제는 20세기 ^[3]수학에서 가장 중요한 미해결 문제 중 하나였는데, 그 때 문제의 가장 중요한 변형이 1995년 스티븐 브램스와 앨런 테일러에 의해 브램스와 테일러 절차로 마침내 풀렸다.

나눗셈과 선택의 기원은 기록되지 않았다.협상과 물물교환의 관련 활동 또한 오래되었다.두 사람 이상이 참여하는 협상도 꽤 흔한데, 포츠담 회의는 주목할 만한 최근의 사례이다.

공정분할론은 2차 세계대전이 끝난 시점까지 거슬러 올라간다.그것은 폴란드 수학자 휴고 스타인하우스, 브로니스와프 크나스터, 스테판 바나흐가 리보프의 스코틀랜드 카페에서 만나곤 했다.1944년에 '라스트 디미니셔'라고 불리는 선수 수에 관계없이 비례하는 (공정 부문)가 만들어졌다.이는 1947년 9월 17일 워싱턴 D.C.에서 열린 계량경제학회 회의에서 처음으로 문제를 공개했을 때 스타인하우스의 바나흐와 크나스터 덕분이었다.이 회의에서 그는 또한 그러한 부문들에 필요한 최소한의 삭감 수를 찾는 문제를 제안했다.

부러움 없는 케이크 커팅의 역사는 부러움 없는 케이크 커팅을 참고하세요.

대중문화에서

• 저림3rs 시즌3 에피소드 "One Hour"에서 찰리는 납치범이 요구하는 돈의 액수에 적용되는 케이크 자르기 문제에 대해 이야기한다.
• 휴고 스타인하우스는 그의 책 Mathemical Snapshots에서 공정분할의 많은 변형에 대해 썼다.그의 책에서 그는 1944년 베르데추프의 G. 크로흐마이니와 L Kott ^[4]여사에 의해 특별 3인용 공정분할이 고안되었다고 말한다.
• 마틴 가드너와 이안 스튜어트는 둘 다 이 ^[5][6]문제에 대한 섹션이 있는 책을 출판했다.마틴 가드너는 그 문제의 잡무 구분 형식을 도입했다.Ian Stewart는 Scientific American과 New Scientist에 기고한 글들로 공정분할 문제를 널리 알렸다.
• 공룡 만화 연재물은 케이크 커팅 문제에 ^[7]바탕을 두고 있다.
• 이스라엘 영화 세인트 클라라에서 러시아 이민자가 이스라엘 수학 교사에게 어떻게 원형 케이크를 7명이 공평하게 나눌 수 있느냐고 묻는다.그의 대답은 가운데를 3번 똑바로 잘라 8조각으로 만드는 것이다.7명밖에 없으니 공산주의 정신으로 한 조각은 버려야 한다.

「 」를 참조해 주세요.

• 온라인 공정분할은 공정분할의 변형으로 분할 시점에 모든 항목이나 대리인을 이용할 수 있는 것은 아니다.
• 자본(경제학)
• 국제 무역
• 정의(경제학)
• 배낭 문제
• 공정분할 미해결 문제 목록
• 내쉬 협상 게임
• 피자 정리
• 공정성 가격
• 앙심(게임 이론)
• 전략공정부문
• 반소문의 비극
• 공동체의 비극

레퍼런스

교재

• Young, Peyton H. (1995). Equity: in theory and practice. Princeton University Press.
• Brams, Steven J.; Taylor, Alan D. (1996). Fair division: from cake-cutting to dispute resolution. Cambridge University Press. ISBN 0-521-55644-9.
• Robertson, Jack; Webb, William (1998). Cake-Cutting Algorithms: Be Fair If You Can. Natick, Massachusetts: A. K. Peters. ISBN 978-1-56881-076-8. LCCN 97041258. OL 2730675W.
• Herve Moulin (2004). Fair Division and Collective Welfare. Cambridge, Massachusetts: MIT Press. ISBN 9780262134231.
• Barbanel, Julius B.; with an introduction by Alan D. Taylor (2005). The geometry of efficient fair division. Cambridge: Cambridge University Press. doi:10.1017/CBO9780511546679. ISBN 0-521-84248-4. MR 2132232. 간단한 요약은 다음 사이트에서 구할 수 있습니다.
• Steven J. Brams (2008). Mathematics and Democracy: Designing Better Voting and Fair-Division Procedures. Princeton, NJ: Princeton University Press. ISBN 9780691133218.

조사 기사

• 빈센트 P.크로포드(1987년)."공정한 분열", The New Palgrave: 경제 사전, v. 2, 274-75페이지.
• 할 바리안(1987년)."공정성", The New Palgrave: 경제 사전, v. 2, 275-76페이지.
• Bryan Skyrms(1996년).캠브리지 대학 출판부의 사회계약의 진화.ISBN 978-0-521-55583-8
• Hill, T.P. (2000). "Mathematical devices for getting a fair share". American Scientist. 88 (4): 325–331. Bibcode:2000AmSci..88..325H. doi:10.1511/2000.4.325.
• Brandt, Felix; Conitzer, Vincent; Endriss, Ulle; Lang, Jérôme; Procaccia, Ariel D. (2016). Handbook of Computational Social Choice. Cambridge University Press. ISBN 9781107060432. (무료 온라인 버전), 11~13장.
• Christian Klamler의 공정 부문 - 그룹 결정 및 협상 핸드북 페이지 183–202.
• 케이크 커팅: Claudia Lindner와 Jörg Rothe에 의한 분배 가능한 상품의 공정 분할 - 경제 및 계산 pp 395–491.
• 제롬 랑과 외르크 로테의 경제 및 계산 pp 493 – 550에 의한 분할할 수 없는 상품의 공정한 분할.

외부 링크

• 볼더에 있는 콜로라도 대학의 이산 수학 프로젝트 공정 부문.
• 공정 부문:마커 방법
• 공정 부문:인감 입찰 방법