효율적인 케이크 커팅

효율적인 케이크 커팅은 경제와 컴퓨터 과학의 문제이다.토핑이 다른 케이크나 커버가 다른 땅과 같이 분할할 수 있는 것으로 간주되는 이종 자원을 수반한다.-그 가치를 훼손하지 않고 임의로 작은 조각을 자를 수 있다.자원은 케이크의 다른 부분보다 다른 선호도를 가진 여러 파트너들 사이에서 분배되어야 합니다. 즉, 어떤 사람들은 초콜릿 토핑을 선호하고, 어떤 사람들은 체리를 선호하고, 어떤 사람들은 가능한 한 큰 조각을 원합니다.할당은 경제적으로 효율적일 것입니다.효율성에 대한 몇 가지 개념이 연구되었습니다.

가장 일반적인 개념은 파레토 효율입니다.이것은 적어도 한 명의 참가자에게, 그리고 적어도 모든 참가자에게 더 나은 배정은 없다는 것을 의미합니다.
더 약한 개념은 비낭비입니다.자신에게 0, 다른 에이전트의 경우 0보다 큰 케이크 조각을 받는 에이전트가 없는 경우 할당은 낭비되지 않습니다.

대부분의 경우 효율성은 공정성과 관련하여 연구되며, 효율성과 공정성 기준을 모두 충족하는 부문을 찾는 것이 목표입니다.

정의들

$케이크$ C(\ $displaystyle$ C $C$ 가 있습니다. 보통 유한한 1차원 세그먼트, 2차원 폴리곤 또는 다차원 유클리드 $\mathbb {R} ^{d}$ $\mathbb {R} ^{d}$ d $(\$ 의 유한 서브셋으로 가정합니다.

$파트너$ 는 $n$ $없습니다.$ $각$ $i$ 는 $i$ $C$ 의 서브셋을 숫자에 매핑하는 주관적 가치 $V_{i}$ $({$ $displaystyle$ $V_{i$ })를 $V_{i}$ 가진다 $C$ .

$\displaystyle$ C를 n개의 $C$ $displaystyle$ n개의 $n$ displaystyle $n$ 으로 분할하여 각 사용자가 displaystyle subset을 받아야 합니다. $개인$ i $(\displaystyle$ i $)$ 에 $i$ 할당된 조각을 $(\$ 라고 $X_{i}$ . $C=X_{1}\sqcup ...\sqcup X_{n}$ C $C=X_{1}\sqcup ...\sqcup X_{n}$ $C=X_{1}\sqcup ...\sqcup X_{n}$ 1 $C=X_{1}\sqcup ...\sqcup X_{n}$ ... $C=X_{1}\sqcup ...\sqcup X_{n}$ X n $C=X_{1}\sqcup ...\sqcup X_{n}$ \ $displaystyle$ C= $X_{1$ } \ $sqcup ...$ $\sqcup X_{n$

다음 줄에서는 초콜릿, 바닐라, 레몬, 설탕의 4가지 부분과 2가지 약제가 포함된 케이크를 고려합니다.Alice와 George의 평가는 다음과 같습니다.

	초콜렛	바닐라	레몬	설탕
앨리스의 가치	7	1	2	0
조지의 가치	6	4	0	0

할당 $({displaystyle$ X})는 $X$ 어떤 에이전트에 대해 값이 0이지만 다른 에이전트에 대해 값이 0 이상인 부분을 할당하는 경우 낭비라고 불립니다.기호:

$V$ $V_{i}(Z)=0~{\text{and}}~V_{j}(Z)>0}$ 및 $\exists {i,j}:\exists Z\subseteq X_{i}:V_{i}(Z)=0~~{\text{and}}~~V_{j}(Z)>0$ $\exists {i}:V_{i}(Y_{i})>V_{i}(X_{i})$ : $\exists {i}:V_{i}(Y_{i})>V_{i}(X_{i})$ i ( $\exists {i}:V_{i}(Y_{i})>V_{i}(X_{i})$ )> $\exists {i}:V_{i}(Y_{i})>V_{i}(X_{i})$ i ( $\exists {i}:V_{i}(Y_{i})>V_{i}(X_{i})$ i ) $\exists {i}:V_{i}(Y_{i})>V_{i}(X_{i})$ \ $display$ style \ $i$ : $V_{i}(Y_{i})>$ $V_{i}(X_{i$

그 이외의 경우는, 비폐기물(NW)이라고 불립니다.이 케이크 예에서 모든 케이크를 앨리스에게 주는 할당은 NW이지만, 모든 케이크를 조지에게 주는 할당은 레몬 부분이 "마모"되었기 때문에 낭비입니다.다른 많은 NW 할당이 있습니다. 예를 들어, George에게 초콜릿을 주고 Alice에게 남은 케이크는 NW입니다.

$Y$ $($ 디스플레이 $Y$ 스타일)가 X $디스플레이 스타일)$ 보다 낫다고 느끼는 사람이 적어도 한 명 있고 기호에서 Y $(디스플레이$ 스타일 $)$ 가 X $디스플레이$ $스타일$ )보다 나쁘다고 $느끼는$ 사람은 없을 경우 할당 Y( $디스플레이$ 스타일 $)$ 파레토 $Y$ (Pareto)가 $할당$ X(\ $displaystyle$ X $X$ 를 지배합니다.

\forall {i}:\ V_{i}(Y_{i})\geq V_{i}(X_{i})

\forall {i}:\ V_{i}(Y_{i})\geq V_{i}(X_{i})

:

\forall {i}:\ V_{i}(Y_{i})\geq V_{i}(X_{i})

\forall {i}:\ V_{i}(Y_{i})\geq V_{i}(X_{i})

(

\forall {i}:\ V_{i}(Y_{i})\geq V_{i}(X_{i})

Y

\forall {i}:\ V_{i}(Y_{i})\geq V_{i}(X_{i})

)

v

(

\forall {i}:\ V_{i}(Y_{i})\geq V_{i}(X_{i})

i ) \

displaystyle

\

forall {

i} ( Y

_

{i } \

geq

V _

\forall {i}:\ V_{i}(Y_{i})\geq V_{i}(X_{i})

{

i

} (

X

_ {i } )

및

i :

\exists {i}:V_{i}(Y_{i})>V_{i}(X_{i})

\exists {i}:V_{i}(Y_{i})>V_{i}(X_{i})

(

\exists {i}:V_{i}(Y_{i})>V_{i}(X_{i})

) >

\exists {i}:V_{i}(Y_{i})>V_{i}(X_{i})

V

\forall {i}:\ V_{i}(Y_{i})\geq V_{i}(X_{i})

\exists {i}:V_{i}(Y_{i})>V_{i}(X_{i})

(

\exists {i}:V_{i}(Y_{i})>V_{i}(X_{i})

i ) \

exstyle

{ i :

V_{i}(Y_{i})>

V_{i}(X_{i})

$할당$ X $($ 표시 $스타일$ X $)$ 는 $X$ 다른 사업부가 파레토 지배하지 않는 경우, 즉 이의 없이 개선할 수 없는 경우 파레토 최적(PO)이라고 합니다.이 케이크 예에서 케익 전체를 앨리스에게 주는 것은 PO이지만, 케익 전체를 밥에게 주는 것은 앨리스에게 레몬 부분을 주는 할당에 의해 파레토 지배적입니다.일반적으로 (연결 요건이 없는 경우) 모든 불필요한 할당은 파레토 주도로 이루어지기 때문에 모든 PO 할당은 NW입니다.단, 그 반대는 아닙니다.예를 들어, George에게 초콜릿을 주고 Alice에게 남은 케이크를 주는 할당은 NW이지만, 그것은 Pareto가 아니라 George에게 바닐라와 초콜릿의 절반을 주는 할당에 의해 지배된다.이는 최초 할당에서 (Alice, George)의 효용은 (3, 6)인 반면, 대체 할당에서는 효용은 (5.5, 7)이기 때문이다.

존재와 계산

효율적인 할당은 항상 존재합니다.예를 들어, 모든 실용적인 최적 케이크 커팅은 PO이므로 NW도 마찬가지입니다.

그러나 이러한 할당을 찾는 것은 어려울 수 있습니다.한정된 수의 "mark" 쿼리 및 "eval" 쿼리를 사용하여 NW 케이크 할당을 찾는 것이 불가능할 수 있습니다.단, 균일한 평가를 ^[1]^{: 9, Clm.3}하는 에이전트는 2개뿐입니다.이는 이러한 쿼리 수가 유한한 후 알고리즘은 한정된 수의 간격에 관한 정보만을 가지고 있기 때문에 간격 내의 낭비를 막을 수 없기 때문입니다.에이전트에 대한 간격 할당의 경우 이 에이전트는 이 간격의 일부를 0으로, 다른 에이전트는 같은 부분을 1로 평가할 수 있습니다.따라서 PO 또한 유한 ^[2]^{: 560, Thm.5}프로토콜로는 달성할 수 없습니다.

이 문제는 엄격한 긍정성(각 에이전트의 각 포인트는 0보다 엄밀하게 높은 값)을 가정하면 쉬워집니다.각 에이전트의 할당은 NW로, 1개의 에이전트에 모든 케이크를 제공하는 할당은 PO로 되어 있습니다(다른 모든 할당은 이 에이전트의 효용성을 엄격하게 낮춥니다.

이 문제는 쿼리 대신 직접 노출을 사용하는 알고리즘에서도 쉽습니다.다이렉트 폭로 알고리즘에서는 각 에이전트가 자신의 평가 함수 전체를 알고리즘에 공개합니다.예를 들어, 이것은 부분적인 일정한 평가로 가능합니다.직접 공개하면 (각 부분을 가장 중시하는 에이전트에게 전달함으로써) 실용적인 최적 할당을 쉽게 찾을 수 있으며, 이러한 할당은 PO 및 NW도 마찬가지입니다.

효율과 공정성을 겸비하다

종종 다양한 공정성 개념에 따라 효율적일 뿐만 아니라 공정한 배분을 찾아야 한다.존재는 아직 유지되고 있습니다.

비례하는 PO 할당도 항상 존재합니다.예를 들어, 비례의 대상이 되는 값의 합을 최대화하는 할당은 항상 존재하며(모든 비례 할당 집합이 작기 때문에), PO이다(비례성이 파레토 개선에 의해 보존되기 때문에).
또한 시기심이 없는 PO 할당이 항상 존재합니다.이것은 파레토 개선으로 질투가 없는 것이 보존되지 않기 때문에 위의 주장과 직접적으로 이어지는 것은 아니다.그러나 그것은 웰러의 정리로서 명백하게 증명되었다.

그러한 배분을 찾는 것은 계산 모델에 따라 엄격하게 양의 평가일지라도 어려울 수 있다.

쿼리 모델에서는 각 에이전트에 양의 일부를 부여하는 유한 알고리즘이 PO가 될 수 없습니다.단, 엄격하게 양의 값을 갖는 두 에이전트만 있어도 마찬가지입니다.이는 유한 알고리즘이 항상 최종적으로 다수의 인터벌 값을 알고 있기 때문에 인터벌 내의 비효율성을 피할 수 없기 때문입니다.인터벌의 할당에 대해서는 알고리즘이 검출할 수 없는 서브 인터벌의 교환이 유효하게 되는 경우가 있습니다.
직접 폭로 모델(부분적으로 일정한 가치 평가)에서 시장균형^[3] 알고리즘은 PO와 시기 없는(따라서 비례적) 할당을 임의의 수의 에이전트에 대해 다항식 시간에 산출한다.

효율성, 공정성 및 연결성 결합

종종 효율적이고 공평할 뿐만 아니라 조각에 기하학적 제약이 있습니다.예를 들어 케이크가 간격인 경우 각 에이전트에 연속 간격인 조각이 필요할 수 있습니다.이 추가 요건이 있는 경우:

비례하는 PO 할당도 항상 존재합니다.이는 모든 비례 연속 할당 집합이 여전히 작고, 파레토 개선으로 비례성이 여전히 보존되기 때문이다.
에이전트가 3개 이상 있는 경우, 에이전트가 분할적으로 일정한 ^[4]^{: Example 5.1}평가를 받는 경우에도 부럽지 않은 PO 할당이 존재하지 않을 수 있습니다.

계산의 관점에서 보면:

일반적인 평가에서는 가치 밀도가 완전히 양의 값일 때 두 에이전트에 대해 PO와 비례로 나누어 선택합니다.예를 들어, 앨리스가 자르고 조지가 가장 왼쪽 조각을 선택하고 앨리스가 가장 오른쪽 조각을 얻었다고 가정합니다.George가 왼쪽을 얻고 Alice가 오른쪽을 얻는 대체 할당은 Pareto의 개선이 될 수 없습니다. (엄격한 긍정의 가정 하에) 절단 위치를 왼쪽으로 이동하면 George가 다치고 Alice가 오른쪽으로 이동하면 다치기 때문입니다.George가 오른쪽을 얻고 Alice가 왼쪽을 얻는 대체 할당은 Pareto의 개선이 될 수 없습니다. 왜냐하면 이러한 할당에서는 적어도 1개가 총 값의 1/2 미만을 얻어야 하지만 원래 할당에서는 둘 다 최소 1/2를 얻어야 하기 때문입니다.
균등화 알고리즘은 부품별로 일정한 가치평가에 의해 반드시 연결된 부품을 생산하지 않기 때문에 작동하지 않습니다.단, O $O(m^{n})$ n $)\displaystyle$ O $(m^{n})}$ 개의 $O(m^{n})$ 선형 프로그램(여기서 m은 조각 수)을 $O(m^{n})$ 으로써 에이전트 수의 유틸리티 합계를 최대화하는 비례 할당을 찾을 수 있습니다.

엄격한 양의 평가를 가진 3개 이상의 에이전트에 대해 연결된 비례 PO 할당이 한정된 수의 쿼리를 사용하여(쿼리 모델에서) 찾을 수 있는지 또는 다항식 알고리즘을 사용하여(직접 폭로 모델에서) 찾을 수 있는지 여부는 현재 알려져 있지 않다.

비가산 평가

케이크가 1차원 간격이고 각 개인이 연결된 간격을 받아야 하는 경우, 다음과 같은 일반적인 결과가 유지됩니다. 값 함수가 엄격히 단조로운 경우(즉, 각 개인이 적절한 하위 집합보다 조각을 엄격히 선호함) 모든 EF 부문은 PO입니다(에이전트가 분리된 PIEC를 받을 수 있는 경우 이는 사실이 아님에 유의하십시오.es) 따라서 Simmons-Su 프로토콜은 PO+EF 분할을 생성합니다.

케이크가 1차원 원(즉, 두 끝점이 위상적으로 식별되는 간격)이고 각 사람이 연결된 호를 받아야 하는 경우, 이전 결과는 유지되지 않습니다. EF 분할이 반드시 PE인 것은 아닙니다.또한 PO+EF 나눗셈이 존재하지 않는 (무가산) 값 함수 쌍이 있습니다.단, 2개의 작용제가 존재하며 그 중 적어도 1개의 작용제가 가법치 함수를 갖는 경우에는 PO+EF 분할이 존재합니다.^[6]

「」를 참조해 주세요.

레퍼런스

^ Ianovski, Egor (2012-03-01). "Cake Cutting Mechanisms". arXiv:1203.0100 [cs.GT].
^ Kurokawa, David; Lai, John K.; Procaccia, Ariel D. (2013-06-30). "How to Cut a Cake Before the Party Ends". Twenty-Seventh AAAI Conference on Artificial Intelligence.
^ Aziz, Haris; Ye, Chun (2014). Liu, Tie-Yan; Qi, Qi; Ye, Yinyu (eds.). "Cake Cutting Algorithms for Piecewise Constant and Piecewise Uniform Valuations". Web and Internet Economics. Lecture Notes in Computer Science. Springer International Publishing. 8877: 1–14. doi:10.1007/978-3-319-13129-0_1. ISBN 978-3-319-13129-0. S2CID 18365892.
^ Segal-Halevi, Erel; Sziklai, Balázs R. (2018-09-01). "Resource-monotonicity and population-monotonicity in connected cake-cutting". Mathematical Social Sciences. 95: 19–30. arXiv:1703.08928. doi:10.1016/j.mathsocsci.2018.07.001. ISSN 0165-4896. S2CID 16282641.
^ Alijani, Reza; Farhadi, Majid; Ghodsi, Mohammad; Seddighin, Masoud; Tajik, Ahmad S. (2017-02-10). "Envy-Free Mechanisms with Minimum Number of Cuts". Thirty-First AAAI Conference on Artificial Intelligence.
^ Thomson, W. (2006). "Children Crying at Birthday Parties. Why?". Economic Theory. 31 (3): 501–521. doi:10.1007/s00199-006-0109-3. S2CID 154089829.

[1] Ianovski, Egor (2012-03-01). "Cake Cutting Mechanisms". arXiv:1203.0100 [cs.GT].

[2] Kurokawa, David; Lai, John K.; Procaccia, Ariel D. (2013-06-30). "How to Cut a Cake Before the Party Ends". Twenty-Seventh AAAI Conference on Artificial Intelligence.

[3] Aziz, Haris; Ye, Chun (2014). Liu, Tie-Yan; Qi, Qi; Ye, Yinyu (eds.). "Cake Cutting Algorithms for Piecewise Constant and Piecewise Uniform Valuations". Web and Internet Economics. Lecture Notes in Computer Science. Springer International Publishing. 8877: 1–14. doi:10.1007/978-3-319-13129-0_1. ISBN 978-3-319-13129-0. S2CID 18365892.

[4] Segal-Halevi, Erel; Sziklai, Balázs R. (2018-09-01). "Resource-monotonicity and population-monotonicity in connected cake-cutting". Mathematical Social Sciences. 95: 19–30. arXiv:1703.08928. doi:10.1016/j.mathsocsci.2018.07.001. ISSN 0165-4896. S2CID 16282641.

[5] Alijani, Reza; Farhadi, Majid; Ghodsi, Mohammad; Seddighin, Masoud; Tajik, Ahmad S. (2017-02-10). "Envy-Free Mechanisms with Minimum Number of Cuts". Thirty-First AAAI Conference on Artificial Intelligence.

[t07-6] Thomson, W. (2006). "Children Crying at Birthday Parties. Why?". Economic Theory. 31 (3): 501–521. doi:10.1007/s00199-006-0109-3. S2CID 154089829.

[1]

[2]

[3]

[4]

[6]

Search

효율적인 케이크 커팅

네임스페이스

더

목차

정의들

존재와 계산

효율과 공정성을 겸비하다

효율성, 공정성 및 연결성 결합

비가산 평가

「」를 참조해 주세요.

레퍼런스

Search

효율적인 케이크 커팅

정의들

존재와 계산

효율과 공정성을 겸비하다

효율성, 공정성 및 연결성 결합

비가산 평가

「 」를 참조해 주세요.

레퍼런스

「」를 참조해 주세요.