분할하여 선택

Divide and choose

나누기 및 선택(자르기 및 선택 또는 내가 선택)은 두 당사자 간에 케이크와 같은 연속적 자원을 공정하게 분할하기 위한 절차다. 그것은 이질적인 재화나 자원("케이크")과 케이크 부분보다 다른 선호를 가진 두 파트너를 포함한다. 프로토콜은 다음과 같이 진행된다: 한 사람("커터")은 케이크를 두 조각으로 자르고, 다른 사람("커터")은 조각 중 하나를 선택하고, 커터는 남은 조각을 받는다.[1]

이 절차는 고대부터 토지, 케이크, 그리고 다른 자원들을 두 당으로 나누는 데 사용되어 왔다. 현재, 공정한 케이크 커팅이라고 불리는 연구 전 분야가 있으며, 커트 앤 선택 방식의 다양한 확장 및 일반화에 전념하고 있다.[2][3]

역사

분열과 선택은 성경의 창세기(13장)에 언급되어 있다. 아브라함과 롯이 가나안 땅에 이르렀을 때에, 아브라함이 그 땅을 그들에게 나누어 달라고 제안하였다. 그러자 아브라함은 남쪽에서 와서 땅을 "왼쪽" (서쪽) 부분과 "오른쪽" (동쪽) 부분으로 나누고 롯을 선택하게 한다. 롯은 소돔과 고모라가 들어 있는 동쪽을 택하고, 아브라함은 브엘세바, 헤브론, 베이트엘, 세겜이 들어 있는 서쪽을 택한다.

유엔해양법협약은 국가 간 해양지역 할당에 대해 분할 선택과 유사한 절차를 적용한다. 바다에서 광물을 채굴하는 허가를 신청하는 선진국은 대략 비슷한 값의 두 지역을 준비해야 하고, 유엔 당국이 개발도상국에게 광물 채굴 허가를 위해 그 중 하나를 선택하도록 하고, 다른 하나는 채굴을 위해 구해야 한다.[4][5]

"각 응용 프로그램... 전체 면적을 커버해야 한다. ...의 두 채굴을 허용하기에 충분히 크고 충분한 상업적 가치를 지닌. 상업적 가치가 같은... 이러한 데이터를 받은 후 45일 이내에, 당국은 기업 또는 개발도상국과의 제휴를 통해 당국이 수행하는 활동만을 위해 유보해야 할 부분을 지정해야 한다. 지정된 지역은 비예비구역에 대한 작업계획이 승인되고 계약이 체결되는 즉시 예비구역이 된다.[6]

분석

두 조각으로 자른 케이크

분배와 선택은 다음과 같은 의미에서는 부러움이 없다: 두 파트너 각각은 각자의 주관적 취향에 따라 다른 파트너가 무엇을 하든 상관없이 할당 몫이 적어도 다른 공유만큼 가치가 있다는 것을 보증하는 방식으로 행동할 수 있다. 각 파트너의 행동은 다음과 같다.[2][3]

  • 커터는 그들이 동등하다고 생각하는 케이크를 두 조각으로 자를 수 있다. 그리고 나서, 선택자가 무엇을 하든 간에, 그들은 다른 작품만큼 가치 있는 작품을 남겨둔다.
  • 선택자는 그들이 더 가치 있다고 생각하는 작품을 선택할 수 있다. 그렇다면 커터가 케이크를 매우 불평등한 조각으로 나누었다고 해도(추가의 눈에는) 추어가는 자신의 눈으로 더 가치 있는 조각을 선택했기 때문에 여전히 불평할 이유가 없다.

외부 시청자에게는 분할이 불공평하게 보일 수 있지만, 관련된 두 파트너에게는 분할이 공정하다. 어떤 파트너도 다른 파트너의 몫을 부러워하지 않는다.

파트너의 가치 함수가 부가 함수인 경우, 각 파트너는 할당된 몫이 전체 케이크 값의 1/2 이상임을 보장하는 방식으로 행동할 수 있다. 부가 가치로 볼 때 모든 무 부러움 분할도 비례하기 때문이다.

이 프로토콜은 바람직한 자원을 나누는 것(공정한 케이크 자르기)과 바람직하지 않은 자원을 나누는 것(안무 분업)에 모두 효과가 있다.

분할과 선택은 당사자들이 동등한 자격을 가지고 있고 분할을 스스로 결정하거나 중재보다는 중재를 사용하기를 원한다고 가정한다. 상품은 어떤 식으로든 분할할 수 있다고 가정하지만, 각 당사자는 비트를 다르게 평가할 수 있다.

커터는 가능한 한 공정하게 나눌 동기가 있다. 그렇지 않으면 바람직하지 않은 부분을 받게 될 것이다. 이 규칙은 무지개념의 베일을 구체적으로 적용한 것이다.

나누기와 선택 방법은 각 개인이 자신의 가치에 의해 정확히 절반의 케이크를 얻는다는 것을 보장하지 않으며, 따라서 정확한 나누기가 아니다. 정확한 분할을 위한 한정된 절차는 없지만, 두 개의 움직이는 칼을 사용하여 할 수 있다; 오스틴 움직이는 칼 절차를 참조하라.

일반화 및 개선

둘 이상의 정당으로 나누기

분할-선택은 두 당사자에 한한다. 당사자가 더 많은 경우, 마지막 감산기 또는 이븐-파즈 프로토콜과 같은 다른 절차를 사용할 수 있다. 마틴 가드너는 1959년 5월 사이언티픽 아메리칸에서 "수학적 게임" 칼럼에서 더 큰 그룹을 위해 유사한 공정 절차를 설계하는 문제를 대중화했다.[7] 비례 케이크 커팅을 참조하십시오. 새로운 방법은 Scientific American에 보고되어 있다.[8] 아지즈와 매켄지에 의해 개발되었다.[9] 원칙적으로는 이전의 방법보다 빠르지만, 그것은 여전히 잠재적으로 매우 느리다. 부러움 없는 케이크 커팅을 보십시오.

효율적인 할당

분할 선택으로 비효율적인 할당을 산출할 수 있다. 흔히 사용되는 예로는 바닐라 반과 초콜릿 반인 케이크가 있다. 밥이 초콜릿만 좋아하고 캐롤은 바닐라만 좋아한다고 가정해보자. 밥이 커터인데 캐롤이 좋아하는 것을 모른다면, 그의 안전한 전략은 케이크를 나누어 각 반쪽이 동일한 양의 초콜릿을 포함하도록 하는 것이다. 그러나 그 후, 캐롤의 선택과 상관없이 밥은 초콜릿의 절반만 받게 되고, 그 할당량은 분명히 파레토 효율적이지 않다. 밥이 무지에서 바닐라(그리고 초콜릿의 양)를 모두 한 몫 더 많이 넣었을 가능성이 완전히 있기 때문에 캐롤은 그가 협상을 통해 얻을 수 있는 것보다 적게 받으면서도 그녀가 원하는 모든 것을 얻는다.

밥이 캐롤의 취향을 알고 그녀를 좋아한다면, 그는 케이크를 초콜릿 조각과 바닐라 조각으로 자를 수 있을 것이고, 캐롤은 바닐라 조각을 선택하고, 밥은 초콜릿을 모두 얻을 수 있을 것이다. 반면에, 그가 캐롤을 좋아하지 않는다면, 그는 케이크를 한 부분에 바닐라 반 이상, 나머지 부분에 바닐라 그리고 다른 부분에 있는 모든 초콜릿으로 자를 수 있다. Carol은 또한 Bob을 괴롭히기 위해 초콜릿과 함께 그 역할을 하고 싶은 동기가 생길 수도 있다. 이마저도 해결하는 절차가 있지만 작은 판단 착오에도 매우 불안정하다.[10] 최적성을 보장하지는 못하지만 분할과 선택보다 훨씬 나은 보다 실용적인 해결책, 특히 조정된 승자 절차([11]AW)와 잉여 절차(SP)가 고안됐다.[12] 효율적인 케이크 자르기를 참조하십시오.

참고 항목

  • 시장 창출자 – 주식 시장 거래 기업, 지정된 가격으로 구입하거나 매도할 것을 제안하는 금융 시장 참여자( 스프레드 포함)
  • 리소스 할당 – 가능한 용도 중 리소스 할당

참고 및 참조

  1. ^ Steinhaus, Hugo (1948). "The problem of fair division". Econometrica. 16 (1): 101–4. JSTOR 1914289.
  2. ^ a b Brams, Steven J.; Taylor, Alan D. (1996). Fair division: from cake-cutting to dispute resolution. Cambridge University Press. ISBN 0-521-55644-9.
  3. ^ a b 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.
  4. ^ Young, H. Peyton (1995-01-01). Equity. Princeton University Press. doi:10.1515/9780691214054. ISBN 978-0-691-21405-4.
  5. ^ Walsh, Toby (2011). Brafman, Ronen I.; Roberts, Fred S.; Tsoukiàs, Alexis (eds.). "Online Cake Cutting". Algorithmic Decision Theory. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. 6992: 292–305. doi:10.1007/978-3-642-24873-3_22. ISBN 978-3-642-24873-3. S2CID 501890.
  6. ^ United nations (1982-12-10). "Annex III: Basic conditions of prospecting, exploration and exploitation. Article 8". un.org.
  7. ^ Gardner, Martin (1994). My Best Mathematical and Logic Puzzles. Dover Publications. ISBN 978-0486281520.
  8. ^ Klarreich, Erica (October 13, 2016). "The Mathematics of Cake Cutting". Quanta Magazine (Scientific American).
  9. ^ AZIZ, HARIS; MACKENZIE, SIMON (2017). "A Discrete and Bounded Envy-free Cake Cutting Protocol for Any Number of Agents". arXiv:1604.03655. Bibcode:2016arXiv160403655A. Cite 저널은 필요로 한다. journal= (도움말)
  10. ^ 케이크 커팅 전문 지식 데이비드 맥퀼런 1999(검토되지 않음)
  11. ^ 스티븐 J. 브램스와 앨런 D. 테일러(1999년). 윈/윈 솔루션: 노튼 페이퍼백에 공정한 주식 보장 ISBN 0-393-04729-6
  12. ^ Steven J. Brams, Michael A의 "케이크를 자르는 더 좋은 방법" 2006년 12월 미국수학협회의 공지에 실린 존스, 그리고 크리스찬 클람러.