Proporcjonalne cięcie ciasta

Proporcjonalne krojenie ciasta jest rodzajem sprawiedliwego krojenia ciasta . Jest to podział heterogenicznego zasobu („ciasta”), który spełnia proporcjonalności , a mianowicie, że każdy partner czuje, że jego przydzielony udział jest wart co najmniej 1/ n całości.

Przy omawianiu proporcjonalności przyjmuje się zwykle dwa założenia:

Wyceny partnerów są nieatomowe , tzn. nie ma niepodzielnych elementów o wartości dodatniej.
Wyceny partnerów są addytywne , tzn. gdy kawałek jest podzielony, wartość kawałka jest równa sumie jego części.

Definicje formalne

Ciasto jest oznaczone przez do $\ displaystyle C}$ . Są ${\ displaystyle n}$ . Każda osoba $\$ funkcję wartości . $displaystyle V_ {i}}$ . $_$ tortu _ _ _

${\ Displaystyle V_ {i} (X_ {i}) \ geq V_ {i} (C) / n}$ dla każdej osoby ${\ Displaystyle i \ w \ {1, \ ldots, n \}}$ .

Procedury

Klasyczne rozwiązanie dla dwóch osób to dziel i wybieraj . Jedna osoba dzieli zasoby na to, co uważa za równe połowy, a druga osoba wybiera „połówkę”, którą woli. Założenie braku atomowości gwarantuje, że krajalnica rzeczywiście może pokroić ciasto na dwie równe części; założenie addytywności gwarantuje, że obaj partnerzy oceniają swoje figury co najmniej 1/2.

Istnieje wiele sposobów na rozszerzenie tej procedury na więcej niż 2 osoby. Każdy sposób ma swoje zalety i wady.

Proste procedury

Ostatni zmniejszacz to najwcześniejsza procedura dzielenia proporcjonalnego opracowana dla n osób:

Jeden z partnerów jest proszony o wylosowanie figury, którą ocenia na co najmniej 1/ n .
Pozostali partnerzy z kolei mają możliwość twierdzenia, że aktualna figura jest rzeczywiście warta więcej niż 1/ n ; w takim przypadku proszeni są o zmniejszenie go tak, aby pozostała wartość wynosiła 1/ n zgodnie z ich własną wyceną.
Ostatni partner, który pomniejszył obecny kawałek, otrzymuje go.
Pozostały tort jest następnie dzielony w ten sam sposób pomiędzy pozostałe n − 1 osoby.

Poprzez indukcję można udowodnić, że każdy partner przestrzegający zasad ma zagwarantowane uzyskanie wartości 1/ n , niezależnie od tego, co robią pozostali partnerzy. Jest to dyskretna procedura, którą można rozgrywać na zmianę. W najgorszym przypadku potrzebne są działania ${\ Displaystyle n \ razy (n-1)/2 = O (n ^ {2})} : jedna akcja na$ gracza na turę. Jednak większość z tych działań można wykonać na papierze; tylko rz − W rzeczywistości potrzeba 1 kawałka ciasta. Stąd, jeśli ciasto jest ciągłe, to można zagwarantować, że każdy kawałek jest ciągły.

Dubinsa-Spaniera z ruchomym nożem jest wersją Last Diminisher działającą w czasie ciągłym.

Nóż przesuwa się po cieście, równolegle do siebie, od jednego końca do drugiego.
$,$ gdy myśli, że się po lewej stronie noża Następnie ciasto jest cięte i dostają ten kawałek.
Powtarza się to z pozostałym ciastem i partnerami. ostatni partner otrzymuje resztę tortu.

Protokół Finka to algorytm kontynuujący dzielenie na coraz mniejsze „równe” części.

Pierwszy partner dzieli zasoby na to, co uważa za równe połowy.
Następnie drugi wybiera połowę, pozostawiając resztę pierwszemu partnerowi
Następnie każdy z tych dwóch partnerów dzieli swoje porcje na trzy części.
Trzeci partner wybiera dwie z otrzymanych porcji: jedną od pierwszego partnera i jedną od drugiego partnera.
Jeśli jest czterech partnerów, każdy z pierwszych trzech partnerów dzieli swoje porcje na czwarte i proces jest kontynuowany.

Zaletą tego protokołu jest to, że można go przeprowadzić online – w miarę wejścia nowych partnerów do partii, istniejący podział jest dostosowywany do nich, bez konieczności ponownego uruchamiania całego procesu podziału. Wadą jest to, że każdy partner otrzymuje dużą liczbę odłączonych elementów zamiast pojedynczego elementu połączonego.

Samotny dzielnik to procedura polegająca na równym podziale dokonanym przez jednego agenta. Jego zaletą jest to, że można go uogólnić, aby uzyskać symetryczne uczciwe krojenie ciasta .

Zobacz też:

Rekurencyjne zmniejszanie o połowę

Wykorzystując strategię dziel i zwyciężaj, możliwe jest osiągnięcie proporcjonalnego podziału w czasie O( n log n ). Dla uproszczenia procedura jest opisana tutaj dla parzystej liczby partnerów, ale można ją łatwo dostosować do dowolnej liczby partnerów:

Każdy partner jest proszony o narysowanie linii dzielącej ciasto na dwa kawałki, które jego zdaniem mają taką samą wartość. Cięcia muszą się nie przecinać; prostym sposobem zagwarantowania tego jest zezwolenie tylko na linie poziome lub tylko linie pionowe.
Algorytm sortuje n wierszy w porządku rosnącym i kroi ciasto na środku wierszy. Np. jeśli jest 4 partnerów, którzy rysują linie w x = 1, x = 3, x = 5 i x = 9, to algorytm przecina tort pionowo na x = 4.
Algorytm przypisuje każdej z dwóch połówek n /2 partnerów – partnerów, których linia znajduje się wewnątrz tej połówki. Np. partnerzy, którzy narysowali linie w x = 1 i x = 3 są przypisani do zachodniej połowy, a pozostali dwaj partnerzy są przypisani do wschodniej połowy. Każda połowa jest dzielona rekurencyjnie między n /2 przypisanych do niej partnerów.

Można udowodnić przez indukcję, że każdy partner grający zgodnie z regułami ma zagwarantowaną figurę o wartości co najmniej 1/ n , niezależnie od tego, co robią pozostali partnerzy.

Dzięki strategii dziel i zwyciężaj liczba iteracji wynosi tylko O(log n ), w przeciwieństwie do O( n ) w procedurze Last Diminisher. W każdej iteracji każdy partner musi zrobić jeden znak. W związku z tym całkowita liczba wymaganych ocen wynosi O( n log n ).

Ten algorytm ma losową wersję, której można użyć do zmniejszenia liczby ocen; patrz Algorytm Even-Paz .

Procedury selekcji

Innym podejściem do krojenia ciasta jest pozwolenie każdemu partnerowi na wylosowanie określonej liczby elementów w zależności od liczby partnerów, p ( n ) i przekazanie każdemu partnerowi jednego z wybranych przez siebie elementów, tak aby elementy się nie nakładały.

Jako prosty przykład procedury selekcji załóżmy, że ciasto jest jednowymiarowym interwałem i że każdy partner chce otrzymać jeden ciągły interwał. Użyj następującego protokołu:

Każdy partner prywatnie dzieli tort na n przedziałów, które uważa za równe; są to tak zwane elementy kandydujące .
Protokół porządkuje n ^2 kandydatów, zwiększając kolejność ich wschodniego (z zachodu na wschód) i wybierając przedział z najbardziej wysuniętym na zachód wschodnim krańcem. Ten interwał nazywany jest utworem końcowym .
Protokół przekazuje ostatni kawałek jego właścicielowi i usuwa wszystkich przeciętych przez niego kandydatów. Krok #2 jest następnie powtarzany z pozostałymi interwałami pozostałych n - 1 partnerów.

Reguła wyboru w kroku 2 gwarantuje, że w każdej iteracji usuwany jest co najwyżej jeden interwał każdego partnera. Dlatego po każdej iteracji liczba interwałów na partnerów jest nadal równa liczbie partnerów, a proces może przebiegać, dopóki każdy partner nie otrzyma interwału.

Protokół ten wymaga, aby każdy partner odpowiedział na n zapytań, więc złożoność zapytania wynosi O( n ² ), podobnie jak w przypadku Last Diminisher.

Randomizowane wersje

Istnieje możliwość zastosowania randomizacji w celu zmniejszenia liczby zapytań. Pomysł polega na tym, że każdy partner zgłasza nie cały zbiór n kandydatów, ale tylko stałą liczbę d kandydatów wybranych losowo. Złożoność zapytania wynosi O( n ), co oczywiście jest najlepsze z możliwych. W wielu przypadkach nadal możliwe będzie przydzielenie każdemu partnerowi jednego kandydata, tak aby kandydaci się nie pokrywali. Istnieją jednak scenariusze, w których taka alokacja będzie niemożliwa.

Nadal możemy kroić ciasto za pomocą zapytań O( n ), jeśli pójdziemy na kilka kompromisów:

Zamiast gwarantować pełną proporcjonalność, gwarantujemy częściową proporcjonalność , tzn. każdy ze wspólników otrzymuje pewien stały ułamek f ( n ) całkowitej wartości, gdzie f ( n )<1/ n .
Zamiast dawać każdemu partnerowi pojedynczy ciągły element, dajemy każdemu partnerowi połączenie jednego lub więcej rozłącznych elementów.

Ogólny schemat jest następujący:

Każdy partner prywatnie dzieli tort na kawałki o równej subiektywnej wartości. Te n⋅an nazywane są elementami kandydującymi .
losowo jednolicie losuje 2 d kandydujących elementów, ze zwracaniem. Kandydaci są pogrupowani w pary d , które partner zgłasza do algorytmu. Te n⋅d nazywane są nawiasami ćwierćfinałowymi .
Z każdej drabinki ćwierćfinałowej algorytm wybiera jedną figurę – figurę, która przecina mniejszą liczbę innych kandydujących figur. Te n⋅d utwory nazywane są utworami półfinałowymi .
Dla każdego partnera algorytm wybiera pojedynczą sztukę; nazywane są końcowymi kawałkami . Końcowe kawałki wybiera się w taki sposób, aby każdy punkt ciasta był przykryty co najwyżej 2 końcowymi kawałkami (patrz poniżej). Jeśli to się powiedzie, przejdź do kroku 5. Jeśli to się nie powiedzie, rozpocznij od kroku 1.
Każda część ciasta, która należy tylko do jednego końcowego kawałka, jest przekazywana właścicielowi tego kawałka. Każda część ciasta, która należy do dwóch końcowych kawałków, jest dzielona proporcjonalnie przez dowolny deterministyczny algorytm podziału proporcjonalnego.

Algorytm gwarantuje, że z prawdopodobieństwem O(1 a ² ) każdy partner otrzyma co najmniej połowę jednej ze swoich kandydujących figur, co implikuje (jeśli wartości są addytywne) wartość co najmniej 1/2 an . W kroku nr 5 jest O( n ) fragmentów kandydujących i O( n ) dodatkowych podziałów, z których każdy zajmuje O(1) czasu. Stąd całkowity czas działania algorytmu wynosi O( n ).

Głównym wyzwaniem w tym schemacie jest wybranie ostatnich elementów w kroku 4. Aby uzyskać szczegółowe informacje, zobacz protokół Edmonds – Pruhs .

Wyniki twardości

Wyniki twardości wyrażone są w modelu zapytań Robertsona-Webba , tj. odnoszą się do procedur zadających agentom dwa rodzaje zapytań: „Oceń” i „Zaznacz”.

Każda deterministyczna procedura podziału proporcjonalnego dla n ≥3 partnerów musi wykorzystywać co najmniej n zapytań, nawet jeśli wszystkie wyceny są identyczne.

Co więcej, każda deterministyczna lub losowa procedura dzielenia proporcjonalnego przydzielająca każdej osobie ciągły element musi wykorzystywać działania Ω( n log n ).

Co więcej, każda deterministyczna procedura dzielenia proporcjonalnego musi wykorzystywać zapytania Ω( n log n ), nawet jeśli procedura może przypisać każdemu partnerowi element będący sumą przedziałów, a nawet jeśli procedura może gwarantować jedynie przybliżoną sprawiedliwość . Dowód opiera się na dolnym ograniczeniu złożoności znalezienia dla pojedynczego gracza kawałka ciasta, który jest zarówno bogaty w wartość, jak i cienki w szerokości.

Te wyniki twardości sugerują, że rekurencyjne dzielenie na pół jest najszybszym możliwym algorytmem do osiągnięcia pełnej proporcjonalności z ciągłymi kawałkami i jest to najszybszy możliwy algorytm deterministyczny do osiągnięcia nawet częściowej proporcjonalności, a nawet z rozłączonymi kawałkami. Jedynym przypadkiem, w którym można to poprawić, są losowe algorytmy gwarantujące częściową proporcjonalność z rozłączonymi elementami.

Jeśli gracze są w stanie ciąć tylko ze skończoną precyzją, to dolna granica Ω(n log n) obejmuje również losowe protokoły.

Poniższa tabela podsumowuje znane wyniki:

Proporcjonalność (pełna/częściowa)	Kawałki (ciągłe/rozłączne)	Typ protokołu (deterministyczny/randomizowany)	Zapytania (dokładne/przybliżone)	#zapytania
pełny	przyległy	det.	dokładny	O( n log n ) Ω( n log n )
pełny	przyległy	det.	przybliżony	Ω( n log n )
pełny	przyległy	skraj.	dokładny	O( n log n ) Ω( n log n )
pełny	przyległy	skraj.	przybliżony	Ω( n log n )
pełny	bezładny	det.	dokładny	O( n log n ) Ω( n log n )
pełny	bezładny	det.	przybliżony	Ω( n log n )
pełny	bezładny	skraj.	dokładny	O( n log n )
pełny	bezładny	skraj.	przybliżony	Ω( n log n )
częściowy	przyległy	det.	dokładny	O( n log n ) Ω( n log n )
częściowy	przyległy	det.	przybliżony	Ω( n log n )
częściowy	przyległy	skraj.	dokładny	O( n log n )
częściowy	przyległy	skraj.	przybliżony	Ω( n log n )
częściowy	bezładny	det.	dokładny	O( n log n ) Ω( n log n )
częściowy	bezładny	det.	przybliżony	Ω( n log n )
częściowy	bezładny	skraj.	dokładny	O( n )
częściowy	bezładny	skraj.	słabo ok. (błąd niezależny od wartości)	O( n )
częściowy	bezładny	skraj.	przybliżony	Ω( n log n )

Warianty

Różne uprawnienia

Kryterium proporcjonalności można uogólnić na sytuacje, w których uprawnienia partnerów nie są równe. 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 (WPR): istnieje kilka wag w _i , które sumują się do 1, a każdy partner powinien otrzymać co najmniej ułamek w _i zasobów według własnej wyceny. Do znalezienia podziału WPR można użyć kilku algorytmów. Głównym wyzwaniem jest to, że liczba cięć może być duża, nawet jeśli jest tylko dwóch partnerów. Zobacz proporcjonalne krojenie tortu z różnymi uprawnieniami .

Podział superproporcjonalny

Podział superproporcjonalny to podział, w którym każdy partner otrzymuje dokładnie więcej niż 1/ n zasobu według własnej subiektywnej wyceny.

Oczywiście taki podział nie zawsze istnieje: gdy wszyscy partnerzy mają dokładnie takie same funkcje wartości, najlepsze, co możemy zrobić, to dać każdemu partnerowi dokładnie 1/ n . Zatem warunkiem koniecznym istnienia podziału superproporcjonalnego jest to, że nie wszyscy partnerzy mają tę samą miarę wartości.

Zaskakujący jest fakt, że gdy wartościowania są addytywne i nieatomowe, warunek ten jest również wystarczający. To znaczy, gdy jest co najmniej dwóch partnerów, których funkcja wartości jest choć trochę różna, wówczas mamy do czynienia z podziałem superproporcjonalnym, w którym wszyscy partnerzy otrzymują więcej niż 1/ n . Aby uzyskać szczegółowe informacje, zobacz podział superproporcjonalny .

Ograniczenie sąsiedztwa

Oprócz zwykłego ograniczenia polegającego na tym, że wszystkie elementy muszą być połączone, w niektórych przypadkach istnieją dodatkowe ograniczenia. W szczególności, gdy tort do podziału to sporne terytorium leżące między kilkoma krajami, może być wymagane, aby kawałek przydzielony każdemu krajowi sąsiadował z jego obecną lokalizacją. Podział proporcjonalny z tą właściwością zawsze istnieje i można go znaleźć, łącząc protokół Last Diminisher z sztuczkami geometrycznymi obejmującymi odwzorowania konforemne . Zobacz problem podziału gruntów Hilla-Becka .

Dwuwymiarowe więzy geometryczne

Gdy „ciasto”, które ma być podzielone, jest dwuwymiarowe, na przykład nieruchomość gruntowa lub miejsce reklamowe w mediach drukowanych lub elektronicznych, często wymagane jest, aby elementy oprócz łączności spełniały pewne ograniczenia geometryczne. Na przykład może być wymagane, aby każdy element był kwadratem, grubym prostokątem lub ogólnie grubym przedmiotem . Przy takich ograniczeniach dotyczących otłuszczenia zwykle nie istnieje podział proporcjonalny, ale zwykle istnieje podział częściowo proporcjonalny, który można znaleźć za pomocą wydajnych algorytmów.

Efektywny ekonomicznie podział

Oprócz tego, że jest proporcjonalny, często wymaga się, aby podział był efektywny ekonomicznie , tj. maksymalizował dobrobyt społeczny (definiowany jako suma użyteczności wszystkich podmiotów).

Rozważmy na przykład ciasto, które zawiera 500 gramów czekolady i 500 gramów wanilii, podzielone między dwóch partnerów, z których jeden chce tylko czekolady, a drugi tylko wanilii. Wiele protokołów krojenia ciasta da każdemu agentowi 250 gramów czekolady i 250 gramów wanilii. Ten podział jest proporcjonalny, ponieważ każdy partner otrzymuje 0,5 swojej całkowitej wartości, więc znormalizowany dobrobyt społeczny wynosi 1. Jednak ten podział jest bardzo nieefektywny, ponieważ moglibyśmy oddać całą czekoladę jednemu partnerowi, a całą wanilię drugiemu partnerowi, osiągając znormalizowany opieka społeczna 2.

Problem optymalnego podziału proporcjonalnego to problem znalezienia proporcjonalnej alokacji, która maksymalizuje dobrobyt społeczny spośród wszystkich możliwych alokacji proporcjonalnych. Problem ten ma obecnie rozwiązanie tylko dla bardzo szczególnego przypadku, w którym placek jest jednowymiarowym przedziałem, a funkcje gęstości użyteczności są liniowe (tj. u ( x ) = Ax + B ). Generalnie problem jest NP-trudny. Kiedy funkcje użyteczności nie są znormalizowane (tj. pozwalamy każdemu partnerowi mieć inną wartość dla całego tortu), problem jest nawet NP-trudny do przybliżenia w ramach współczynnika 1/ √ rz .

Prawdziwy podział

Prawdomówność nie jest właściwością podziału, ale właściwością protokołu. Wszystkie protokoły podziału proporcjonalnego są słabo zgodne z prawdą , ponieważ każdy partner działający zgodnie ze swoją prawdziwą oceną ma gwarancję uzyskania co najmniej 1/ n (lub 1/ an w przypadku protokołu częściowo proporcjonalnego) niezależnie od tego, co robią inni partnerzy. Nawet jeśli wszyscy inni partnerzy utworzą koalicję, której jedynym celem jest wyrządzenie mu krzywdy, nadal otrzyma swoją gwarantowaną proporcję.

Jednak większość protokołów nie jest bardzo prawdomówna , ponieważ niektórzy partnerzy mogą mieć motywację do kłamstwa, aby otrzymać nawet więcej niż gwarantowany udział. Dzieje się tak nawet w przypadku prostego dziel i wybieraj : jeśli krajacz zna preferencje wybierającego, może uciąć kawałek, który wybierający ocenia jako nieco mniejszy niż 1/2, ale który sam krajający ocenia na znacznie więcej niż 1 /2.

Istnieją prawdziwe mechanizmy osiągania idealnego podziału ; ponieważ doskonały podział jest proporcjonalny, są to również prawdziwe mechanizmy podziału proporcjonalnego.

Mechanizmy te można rozszerzyć, aby zapewnić podział superproporcjonalny, jeśli istnieje:

Poproś każdego partnera o podanie całej swojej miary wartości.
Wybierz losową partycję (zobacz więcej szczegółów).
Jeśli przypadkowy podział jest superproporcjonalny zgodnie z podanymi miarami wartości, zaimplementuj go. W przeciwnym razie użyj prawdziwego mechanizmu zapewniającego doskonały podział.

Gdy istnieje podział superproporcjonalny, istnieje dodatnia szansa, że zostanie on wybrany w kroku 2. Stąd wartość oczekiwana każdego prawdomównego partnera jest ściśle większa niż 1/ n . Aby przekonać się, że mechanizm jest prawdziwy, rozważmy trzy przypadki: (a) jeśli wybrany podział jest naprawdę superproporcjonalny, to jedynym możliwym skutkiem kłamstwa jest wprowadzenie mechanizmu w błąd, aby myślał, że tak nie jest; spowoduje to, że mechanizm wdroży idealny podział, który będzie gorszy dla wszystkich partnerów, w tym dla kłamcy. (b) Jeśli wybrany podział nie jest superproporcjonalny, ponieważ daje tylko kłamcy wartość 1/ n lub mniej, to jedynym skutkiem kłamstwa jest przekonanie mechanizmu, że podział jest superproporcjonalny i wdrożenie go, co tylko szkodzi samemu kłamcy. (c) Jeśli wybrany podział naprawdę nie jest superproporcjonalny, ponieważ daje innemu partnerowi wartość 1/ n lub mniejszą, to kłamstwo nie ma żadnego efektu, ponieważ podział i tak nie zostanie zrealizowany.

Proporcjonalny podział obowiązków

Kiedy zasób do podziału jest niepożądany (jak w podziale obowiązków ), podział proporcjonalny definiuje się jako podział dający każdej osobie co najwyżej 1/ n zasobu (tj. znak nierówności jest odwrócony).

Większość algorytmów podziału proporcjonalnego można w prosty sposób dostosować do podziału zadań.

Zobacz też

Podsumowanie procedur podziału proporcjonalnego i innych znajduje się w: Austin, AK (1982). „Podziel się ciastem”. Gazeta Matematyczna . 66 (437): 212–215. doi : 10.2307/3616548 . JSTOR 3616548 .