Uczciwe cięcie ciasta, gdy gracze dołączają późno

Zwykłe stwierdzenie o uczciwym problemie cięcia ciasta zakłada, że ​​wszyscy gracze otrzymują swój udział w tym samym czasie. Jednak w wielu przypadkach gracze przybywają stopniowo. Na przykład, możemy podzielić ciasto na n graczy, ale wtedy pojawia się nowy gracz i chce się podzielić.$n$$n$

Zazwyczaj podział sprawiedliwego ciasta wymaga dużego wysiłku (na przykład wymaga od graczy odpowiedzi na wiele pytań), zwłaszcza gdy liczba graczy jest duża.

Czy można zastosować istniejący podział ciasta na graczy, aby utworzyć nowy podział ciasta na n + 1 graczy, przy minimalnym dodatkowym wysiłku (tj. Znacznie mniej wysiłku niż ponowne rozprowadzenie ciasta od zera)?$n$$n+1$

Powiem z góry, że nie mogę udzielić dobrej odpowiedzi na twoje pytanie (myślę, że możesz wyciągnąć z tego dokument badawczy, jeśli możesz), ale myślę, że mogę pomóc, formalnie definiując problem i określając, gdzie niektóre trudności leżą.

Tło . Pozwól, że jasno przedstawię model krojenia ciasta. Chcemy podzielić przedział między n graczy. Każdy gracz i ma funkcję wyceny v i ( S ) w stosunku do podzbiorów S ciasta. Zakładamy, że ta funkcja jest miarą prawdopodobieństwa; jest nieujemny i addytywny (dla rozłącznego A , B ⊆ [ 0 , 1 ] , v i ( A ∪ B ) = v i$[0,1]$$n$$i$$v_i(S)$$S$$A,B \subseteq [0,1]$ ) i v i ( [ 0 , 1 ] ) = 1 . Rozwiązaniem tego problemu jestprotokółlub algorytm, który odpytuje graczy i przypisuje części przedziału. Pamiętaj, że gracze mogą źle zgłaszać / leżeć w odpowiedziach na pytania.$v_i(A \cup B) = v_i(A) + v_i(B)$$v_i([0,1]) = 1$

Niektóre dokumenty będą miały bardziej szczegółowe ograniczenia; np. funkcje wyceny są ciągłe, liniowo lub częściowo stałe.

$\{S_1,\dots,S_n\}$

• $i$$(1/n)v_i([0,1])$$i$$1/n$
• $v_i(S_i) \geq v_i(S_j)$$j$

Zauważ, że zazdrość pozbawiona wolności oznacza proporcjonalność.

Są też właściwości „operacyjne”, które możemy chcieć, takie jak cięcie na kilka kawałków, wielomianowy czas działania (lub w ogóle obliczalność / konstruowalność - nie chcemy używać Aksjomatu wyboru, aby wybrać podzbiór ciasta! ), i tak dalej.

$1$

Po drugie, zawsze możemy rozwiązać Twój problem, zabierając całe ciasto z powrotem wszystkim i używając znanego algorytmu, aby rozprowadzić je od zera. Pytanie brzmi, czy jest to bardziej elegancki sposób na zrobienie tego. Myślę, że dobrym sposobem na oszacowanie tego jest „kiedy redystrybucja wymaga mniej czasu lub mniej cięć niż od zera; i / lub kiedy gracze mogą zachować znaczną część swojego obecnego wycinka?”

1. $n$$n+1$

$n+1$

1. $n$$n+1$

$1/n$$1$$1/n$$2$$(n-1)/n$$2$$1/n$$3$$(n-1)/n$$n$$1/n$$1$$(n-1)/n$$2$$1$$3$$2$

Jednym z odniesień może być Walsh, Online Cake Cutting , w Algorytmicznej Teorii Decyzji 2011 (link pdf). Ale myślę, że gazeta zakłada, że ​​znamy z góry liczbę przybywających agentów, i zakłada, że ​​graczom należy przydzielić kawałek dokładnie wtedy, gdy odejdą (co jest przed końcem protokołu), więc tak naprawdę nie ma to zastosowania do twojego problemu.

$n$$n+1$$n+1$$n$

$C$$r$$n$$\frac{\pi r^2}{n}$$(n+1)$$n+1$

Wyliczenie liczb jest proste; dla pierwszego nowego gracza wystarczy rozwiązać

$\qquad \pi r_1^2 = \frac{\pi r^2}{n+1}$

aby uzyskać promień jego spisku. Po drugie, rozwiązuj

$\qquad\begin{align} \pi r_1^2 &= \frac{\pi r^2}{n+2} \\ \pi r_2^2 - \pi r_1^2 &= \frac{\pi r^2}{n+2} \end{align}$

$n + i$$r_i = \frac{r\sqrt{i}}{\sqrt{n+k}}$$k$

$n=6$$k=0,1,2,3$

^{[ źródło ]}

$n$$n$