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 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 graczy, przy minimalnym dodatkowym wysiłku (tj. Znacznie mniej wysiłku niż ponowne rozprowadzenie ciasta od zera)? $n$ $n+1$

algorithms game-theory online-algorithms

— Erel Segal-Halevi
źródło

Czy pierwsze

graczy zaczęło jeść? Czy to sprawiedliwe, aby dać graczowi wiele elementów, czy też każdy musi zdobyć dokładnie jeden kawałek?

n

$n$

— Raphael

@ Rafael, jestem szczególnie zainteresowany sprawiedliwym podziałem ziemi, dlatego gracze nie mogą dosłownie zacząć jeść swojej części (mogą budować na swojej części, ale na razie zignorujmy ten problem). Lepiej jest dać każdemu graczowi dokładnie jeden kawałek, jednak najwyraźniej nie jest to możliwe w uczciwy sposób, w przypadku przybycia tylko jednej nowej osoby. Prawdopodobnie powinienem zapytać, co się stanie, jeśli przyjdzie

nowych graczy. W takim przypadku możliwe jest (przynajmniej teoretycznie) podzielenie każdej akcji pierwszych

graczy na 2 nowe akcje. W każdym razie wszelkie odniesienia są mile widziane.

n

$n$

n

$n$

— Erel Segal-Halevi

W przypadku nieużywanej ziemi, dlaczego nie rozpowszechniać wszystkiego?

— Raphael

Myślę, że musisz wyjaśnić, jaki jest twój cel. Zminimalizować liczbę aktualizacji cięć? Zminimalizować całkowitą długość nowych cięć? Czy możemy przypisać części starym graczom, czy też jedyni mogą przegrać?

— Raphael

Ach, teraz rozumiem, co masz na myśli: masz na myśli, że niektórzy gracze zaczęli jeść swoją część, a teraz przybywają nowi gracze, a my chcemy sprawiedliwie dzielić przypomnienia, biorąc pod uwagę to, co każdy gracz już zjadł. Chociaż sam w sobie jest to interesujący problem, moja intencja była inna - mam nadzieję, że moja ostatnia edycja to wyjaśni.

— Erel Segal-Halevi

Odpowiedzi:

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 graczy. Każdy gracz ma funkcję wyceny stosunku do podzbiorów ciasta. Zakładamy, że ta funkcja jest miarą prawdopodobieństwa; jest nieujemny i addytywny (dla rozłącznego , $[0,1]$ $n$ $i$ $v_i(S)$ $S$ $A,B \subseteq [0,1]$ ) i . 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?”

$n$ $n+1$

$n+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$

— usul
źródło

Nie jestem pewien, w jaki sposób pomaga ogólny problem (z niejednolitymi preferencjami); ups ? Rozwiązanie problemu niezmiennych graczy (i rozsądnych kształtów) jest łatwe. Myślę, że będziemy musieli ustalić, co „skuteczny” lub „dobry” oznacza wrt wycinki / przydziały i ich zmiany.

— Raphael

@ Rafael - o ile wiem, pytanie dotyczy rozwiązania ogólnego problemu. (Zgadzam się, że powinniśmy użyć dodatkowej struktury, jeśli taka jest określona.)

— usul

Dziękuję, twoja definicja dokładnie uchwyciła moją intencję. Odniesienie do cięcia ciasta online jest interesujące i odpowiednie.

— Erel Segal-Halevi

$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$

przykład ^{[ źródło ]}

$n$ $n$

— Raphael
źródło

Interesujące byłoby porównanie obszaru, który jest ponownie przypisany tą metodą do obszaru, który jest ponownie przypisany przez wstawienie nowego kawałka (tj. Sektora) ciasta i przesunięcie (i zmniejszenie) wszystkich istniejących kawałków zgodnie z ruchem wskazówek zegara. Liczba stron dotkniętych ruchem (nie tylko stratą) różni się tylko stałą. Zauważ również, że pierścienie nie są bardziej skuteczne niż sektory, ale zmiana z jednej metody na drugą pozwala nie przesunąć obszaru przypisanego przez pierwszą metodę.

— frafl

@frafl Zgadzam się. Czy potrafisz przedstawić inne warianty w odpowiedzi? (Masz rację: nie wydaje się, aby istniał dobry powód do mieszania metod. Dla mnie motywacją był problem z ciastem: zakładam, że ciasto zostało już pokrojone, co robić?)

— Raphael

n + 1

$n+1$

To piękne rozwiązanie gemoetryczne, jednak dotyczy tylko jednolitych ciast i jednolitych ciastek. Odniosłem się do ogólnego problemu cięcia ciasta: en.wikipedia.org/wiki/Fair_division, który zakłada, że ciasto może być niejednorodne, a różni gracze mogą mieć różne wyceny dla różnych części ciasta.

— Erel Segal-Halevi