Proporcjonalne krojenie tortu z różnymi uprawnieniami

W problemie krojenia tortu wspólnicy często mają różne uprawnienia. Na przykład zasób może należeć do dwóch udziałowców, tak że Alice posiada 8/13, a George 5/13. Prowadzi to do kryterium proporcjonalności ważonej $displaystyle$ WPR): istnieje kilka wag , ${i }$ sumują się do 1, a każdy partner powinien otrzymać przynajmniej ułamek $} \displaystyle w_{i}}$ zasobu według własnej wyceny.

Natomiast w prostszym proporcjonalnym ustawieniu krojenia ciasta wagi są równe: ${\ Displaystyle w_ {i} = 1/n}$ dla wszystkich ${\ displaystyle i}$

Do znalezienia podziału WPR można użyć kilku algorytmów.

Klonowanie

$mianowniku$ że wszystkie wagi są liczbami wymiernymi o wspólnym . Więc wagi są następujące: ${\ displaystyle p_ {1}/D, \ kropki, p_ {n}/D}$ z ${\ displaystyle p_ {1}+\cdots +p_{n}=D}$ . Dla każdego gracza stwórz ${\ displaystyle i}$${\ displaystyle p_ {i}}$ klony z tą samą miarą wartości. Całkowita liczba klonów to ${\ displaystyle D}$ . Znajdź wśród nich proporcjonalny przydział ciasta. $Na$ daj każdemu partnerowi $.$ jego

Robertson i Webb $prostszą$ procedurę dla dwóch partnerów: Alice kroi ciasto na kawałki równe w jej oczach; $pozostałe$ wybiera najcenniejsze w jego oczach elementy, $Alice$ .

Ta prosta procedura wymaga $,$ być bardzo duże. Na przykład, jeśli Alicja ma prawo do 8/13, a George ma prawo do 5/13, to w początkowym podziale potrzebne są cięcia 13-1=12.

Liczba wymaganych zapytań to ${\ Displaystyle D \ lceil \ log _ {2} (D) \ rceil.}$

Partycje Ramseya

Załóżmy, że tort musi zostać podzielony między Alicję i George'a, Alicja ma prawo do 8/13, a George ma prawo do 5/13. Ciasto można podzielić w następujący sposób.

• Alicja kroi ciasto na 6 kawałków ze współczynnikami wyceny 5:3:2:1:1:1 .
• Jerzy zaznacza elementy, które mają dla niego co najmniej wartość wymienioną przez Alicję.

Istnieją teraz dwa „dobre” przypadki – przypadki, w których możemy użyć tych elementów do uzyskania proporcjonalnego podziału uwzględniającego różne uprawnienia:

Przypadek 1: Istnieje podzbiór zaznaczonych elementów, których suma wynosi 5. Np. jeśli George zaznacza 3-elementowy i trzy 1-elementowy. Następnie ten podzbiór jest przekazywany George'owi, a reszta Alicji. George ma teraz co najmniej 5/13, a Alicja dokładnie 8/13.

Przypadek 2: Istnieje podzbiór nieoznakowanych elementów, których suma wynosi 8. Np. jeśli George zaznacza 3-elementowy i tylko jeden 1-elementowy. Następnie ten podzbiór jest przekazywany Alicji, a reszta George'owi. Alicja ma teraz dokładnie 8, a Jerzy zrezygnował z sumy mniejszej niż 8, więc ma co najmniej 5/13.

Można udowodnić, że dobre przypadki są jedynymi możliwymi przypadkami. Oznacza to, że każdy podzbiór 5:3:2:1:1:1 ALBO ma podzbiór, którego suma wynosi 5, ALBO jego uzupełnienie ma podzbiór, którego suma wynosi 8. Dlatego powyższy algorytm zawsze znajduje alokację WPR z podanym proporcje. Liczba użytych cięć to tylko 5.

McAvaney, Robertson i Webb uogólniają ten pomysł, używając koncepcji partycji Ramseya (nazwanej na cześć teorii Ramseya ).

Formalnie: jeśli ${\ displaystyle k_ {1}}$ i $k_ {2}}$$displaystyle$ są dodatnimi liczbami całkowitymi, partycja k $\ displaystyle k_ {1} + k_ {2}}$ nazywa się partycją Ramseya dla pary ${\ Displaystyle k_ {1}, k_ {2}}$ , jeśli dla dowolnej listy podrzędnej ${\ Displaystyle L \ subseteq P}$ , albo istnieje podlista $,$$wynosi$$suma$ wynosi ${\ displaystyle k_ {1}}$ , albo istnieje podlista której $\displaystyle k_{2}}$ .

W powyższym przykładzie ${\ Displaystyle k_ {1} = 8}$ i ${\ Displaystyle k_ {2} = 5}$ , a podział to 5: 3: 2: 1: 1: 1, która jest partycją Ramseya. Co więcej, jest to w tym przypadku najkrótsza przegroda Ramseya, dzięki czemu możemy zastosować niewielką liczbę cięć.

Partycje Ramseya zawsze istnieją. Co więcej, zawsze istnieje unikalna najkrótsza partycja Ramseya. Można go znaleźć za pomocą prostego wariantu algorytmu euklidesowego . Algorytm opiera się na następującym lemacie:

${\ Displaystyle p_ {1}<a <b}$ za i ${\ Displaystyle P = (p_ {1}, \ kropki, p_ {n$ jest partycją ${\ Displaystyle b}$ i ${\ Displaystyle P'= (b, p_ {1}, \ kropki, p_ {n}) }$ , to $displaystyle$ partycją za $a + b$ . Ponadto ${\ displaystyle P '}$$dla$ pary ${\ displaystyle a, b}$ wtedy i tylko wtedy, gdy jest minimalną partycją Ramseya dla pary ${\ Displaystyle a, ba}$ .

Ten lemat prowadzi do następującego algorytmu rekurencyjnego.

$\ Displaystyle FindMinimalRamsey (a, b)}$ :

1. Uporządkuj dane wejściowe tak, aby za $\ displaystyle a <b}$ .
2. pchnij ${\ displaystyle a}$ .
3. Jeśli $}$${ \$ , następnie naciśnij zakończ
4. b ${\ Displaystyle ba \ neq 1}$$\ Displaystyle FindMinimalRamsey (a, ba)$ to .

Po znalezieniu minimalnej partycji Ramseya można jej użyć do znalezienia podziału WPR uwzględniającego uprawnienia.

Algorytm wymaga co najmniej cięć ${\ Displaystyle \ log _ {\ phi} \ min (a, b)}$ , gdzie ${\ Displaystyle \ phi = (1+{\sqrt {5}})/2}$ to złoty podział. $W$ większości przypadków liczba ta jest Ale jeśli ${\ displaystyle a = 1}$${\ Displaystyle b = a + b-1}$ za potrzebne są cięcia, ponieważ jedyną partycją Ramseya z pary ${\ Displaystyle b, 1}$ sekwencja z ${ \displaystyle b+1}$ jedynek.

Pokrojone na pół

Załóżmy ponownie, że Alicja ma prawo do 8/13, a George ma prawo do 5/13. Ciasto można podzielić w następujący sposób.

• George kroi ciasto na dwie części w proporcjach 7:6.
• Alicja wybiera jeden z elementów, który jest dla niej wart co najmniej zadeklarowanej wartości. Rozważ dwa przypadki:
  • Alicja wybiera 7. Wtedy Alicji przysługuje jeszcze 1 figura, a pozostałą część należy podzielić w stosunku 5:1.
  • Alicja wybiera 6. Wtedy Alicja ma prawo do jeszcze 2, a pozostałą część należy podzielić w stosunku 5:2.
• W obu przypadkach pozostała część jest mniejsza, a stosunek jest mniejszy. W końcu stosunek wynosi 1:1, a pozostałe ciasto można podzielić za pomocą opcji wytnij i wybierz .

Ogólna idea jest podobna do ${\ Displaystyle CutNearHalves (a, b)}$ Even-Paz : :

1. Uporządkuj dane wejściowe tak, aby za $\ displaystyle a <b}$ . Załóżmy, że Alicja ma prawo do ${\ Displaystyle b / (a ​​+ b)}$ , a George ma prawo do ${\ Displaystyle a / (a ​​+ b)}$ .
2. Poproś George'a, aby pokroił ciasto prawie na pół, tj.:
   • jeśli $,$ to George kroi ciasto na dwie równe części w jego oczach
   • jeśli $jest nieparzysty,$$Displaystyle (a +b-1)/2:(a+b+1)/2}$ współczynnik wyceny wynosi w jego oczach.
3. Przynajmniej jeden z elementów jest wart dla Alicji co najmniej tyle, ile zadeklarował George; daj ten kawałek Alicji.
4. Załóżmy, że kawałek wzięty przez Alicję jest kawałkiem o wartości do ${\ Displaystyle c / (a ​​+ b)}$ , ${\ Displaystyle c \ w \ {(a + b-1)/2, (a + b)/2, (a + b + 1)/2)}$ . Dzwonić $\ Displaystyle CutNearHalves (b, ac)}$ .

Algorytm przecięcia prawie o połowę wymaga co najwyżej $cięć$ Ramseya .

Algorytm cięcia prawie połówek nie zawsze jest optymalny. Załóżmy na przykład, że stosunek wynosi 7:3.

• Pokrojony prawie na pół może wymagać co najmniej czterech cięć: najpierw George tnie w stosunku 5:5, a Alicja dostaje 5. Następnie Alicja tnie w stosunku 3:2; załóżmy, że George wybiera 2. Następnie George zmniejsza stosunek 2:1; załóżmy, że Alicja wybiera 1. Na koniec wybierają resztę.
• Możemy zrobić lepiej, pozwalając George'owi na cięcie w stosunku 6:4. Jeśli Alicja wybierze 4, wówczas stosunek wynosi 3:3 i możemy od razu skorzystać z opcji wycinania i wybierania. Jeśli Alicja wybierze 6, wówczas stosunek wynosi 3:1. Alice tnie w stosunku 2:2, George wybiera 2, a my potrzebujemy jeszcze jednego kroku wycinania i wybierania. W sumie potrzebne są co najwyżej trzy cięcia.

Otwartą kwestią pozostaje, jak znaleźć najlepszą obniżkę wstępną dla każdego wskaźnika uprawnień.

Algorytm można uogólnić na n agentów; liczba wymaganych zapytań to ${\ Displaystyle n (n-1) \ lceil \ log _ {2} (D) \ rceil.}$

Cseh i Fleiner przedstawili algorytm dzielenia wielowymiarowego tortu pomiędzy dowolną liczbę agentów z dowolnymi uprawnieniami (w tym uprawnieniami irracjonalnymi), w skończonej liczbie zapytań. Ich $_$ _ _ _ dlatego jest bardziej wydajny niż klonowanie agentów i cięcie prawie na pół. Dowodzą, że ta złożoność środowiska wykonawczego jest optymalna.

Algorytmy uprawnień irracjonalnych

Gdy uprawnienia nie są liczbami wymiernymi, nie można zastosować metod opartych na klonowaniu, ponieważ mianownik jest nieskończony. Shishido i Zeng przedstawili algorytm o nazwie mark-cut-choose , który może również obsługiwać irracjonalne uprawnienia, ale z nieograniczoną liczbą cięć.

Algorytm Cseha i Fleinera można również dostosować do pracy z irracjonalnymi uprawnieniami w skończonej liczbie zapytań.

Liczba wymaganych cięć

Oprócz liczby wymaganych zapytań, interesujące jest również zminimalizowanie liczby wymaganych cięć, aby podział nie był zbyt rozdrobniony. Algorytmy Shishido-Zeng $n$ sprawiedliwy podział z co najwyżej ${ \displaystyle 4\cdot 3 ^{n-2}}$ z co cięcia.

$mogą$ najgorszym przypadku najmniej Brams, Jones i Klamler pokazują przykład dla n = 2. Tort składający się z czterech kolejnych regionów należy podzielić między Alicję i Jerzego, których wyceny są następujące:

Wartość Alicji	2	2	2	2
wartość Jerzego	1	3	3	1

Zauważ, że łączna wartość tortu wynosi 8 dla obojga partnerów. Jeśli ${\ Displaystyle w_ {A} \ geq 0,75}$ , to Alicja ma prawo do wartości co najmniej 6. Aby dać Alicji jej należny udział w połączonym kawałku, musimy dać jej albo trzy skrajne lewe plasterki, albo trzy skrajne prawe plasterki. W obu przypadkach George otrzymuje kawałek o wartości tylko 1, czyli mniej niż jego należny udział w wysokości 2. Aby w tym przypadku uzyskać podział WPR, musimy przyznać George'owi jego należny udział w środku tortu, gdzie jego wartość jest stosunkowo duży, ale wówczas Alicja otrzyma dwa rozłączone elementy.

Segal-Halevi pokazuje, że jeśli ciasto jest okrągłe (tj. zidentyfikowane są dwa punkty końcowe), to zawsze możliwy jest połączony podział WPR dla dwóch osób; wynika to z twierdzenia Stromquista-Woodalla . Stosując rekurencyjnie to twierdzenie do znalezienia dokładnych podziałów , możliwe jest uzyskanie podziału WPR przy użyciu co najwyżej ${\ Displaystyle 2n \ cdot (\ log _ {2} n-1 )+2}$ przecina, gdy n jest potęgą 2 i podobną liczbą, gdy n jest ogólne.

Crew, Narayanan i Spirkle poprawili tę górną granicę do 3 n -4, stosując następujący protokół:

• Poproś każdego agenta i o zaznaczenie x takiego, że V _i (0, x )=1/2.
• Uporządkuj agentów w rosnącej kolejności według ich znaku, arbitralnie zrywając więzi.
• Dodaj agentów w powyższej kolejności do zbioru P . Zatrzymaj się tuż przed tym, jak całkowita waga środków w P przekroczy 1/2.
• Pierwszy agent, który nie został dodany do P, nazywa się t , a zestaw agentów po t nazywa się Q. Teraz:
  • Wszystkie czynniki w wartości P (0, x ) co najmniej 1/2, a ich łączna waga wynosi co najwyżej 1/2;
  • Wszystkie agenty w wartości Q ( x,1 ) co najmniej 1/2, a ich łączna waga wynosi co najwyżej 1/2;
  • Agent t przyjmuje wartości zarówno (0,x), jak i ( x,1 ) na dokładnie 1/2.
• Jeśli zarówno P , jak i Q są niepuste, to agent t jest podzielony między P i Q w taki sposób, że całkowita waga w każdym zestawie wynosi dokładnie 1/2. Ciasto jest cięte w punkcie x , a procedura przebiega rekurencyjnie. Prowadzi to do następującej relacji rekurencyjnej (gdzie k jest liczbą agentów w P , nie licząc klona agenta t ): ${\ Displaystyle {\ tekst {Cięcia}} (n + 1) \ równoważnik \ max _ {1 \ równoważnik k \ równoważnik n -1}(1+{\text{Cięcia}}(k+1)+{\text{Cięcia}}(n-k+1))}$ . Dodanie warunku początkowego ${\ Displaystyle {\ tekst {Cięcia}} (2) = 2}$ daje deklarowaną liczbę ${\ Displaystyle {\ tekst {Cięcia}} (n) \ równoważnik 3n-4}$ .

• Trudniejszym przypadkiem jest to, że P jest puste (przypadek, że Q jest puste, jest analogiczny). Oznacza to, że waga t wynosi co najmniej 1/2, a wszyscy agenci mają wartość (0, x ) co najwyżej 1/2. W tym przypadku znajdujemy y takie, że agent t ma wartości (0, y ) dokładnie w _t i próbujemy podzielić agentów na P i Q , jak poprzednio. Jeśli znowu jeden z tych zbiorów jest pusty, to wiemy, że wszyscy agenci mają wartość (0, y ) co najmniej w _t . Dlatego z twierdzenia o wartości pośredniej musi istnieć wartość z w ( x , y ), dla której jeden z agentów, który nie jest t , ma wartości (0, z ) dokładnie takie same jak t . Następnie możemy przeciąć ciasto w punkcie z i wykonać rekurencję jak w pierwszym przypadku.

Dokładna liczba wymaganych cięć pozostaje kwestią otwartą. Najprostsza otwarta sprawa ma miejsce, gdy jest 3 agentów, a wagi to 1/7, 2/7, 4/7. Nie wiadomo, czy liczba wymaganych cięć wynosi 4 (jak w dolnej granicy), czy 5 (jak w górnej granicy).

Zobacz też

Zeng przedstawił algorytm przybliżonego krojenia tortu bez zazdrości z różnymi uprawnieniami.

Dall'Aglio i MacCheroni dowiedli istnienia proporcjonalnego krojenia ciasta z różnymi uprawnieniami, nawet jeśli preferencje agentów są opisywane przez nieaddytywne relacje preferencji, o ile spełniają one pewne aksjomaty.