Tăierea geloasă a tortului

Tăierea prăjiturii invidioase [1] este un fel de tăiere corectă a prăjiturii . Este vorba de tăierea unei resurse eterogene („tort”) cu satisfacerea criteriului absenței invidiei , și anume, că orice participant are sentimentul că partea care i-a fost alocată (după propria sa evaluare subiectivă) nu este mai mică. decât piesele date celorlalți participanți.

Dacă sunt doar doi participanți, problema este simplă și a fost rezolvată în vremurile biblice prin protocolul Deliver-and-Choose . Dacă există trei sau mai mulți participanți, sarcina devine substanțial mai dificilă.

Au fost studiate două variante principale ale problemei:

piese conectate, de exemplu, în cazul unui segment unidimensional, fiecare participant trebuie să primească un subinterval separat. Dacă sunt trei participanți, aveți nevoie de reduceri totale. $n$ $n-1$
bucăți de formă generală, de exemplu, în cazul unui segment unidimensional, fiecare participant trebuie să obțină o uniune de sub-segmente care nu se intersectează.

Scurt istoric

Cercetările moderne privind problema tăierii prăjiturii corecte au început în anii 1940. Primul criteriu de corectitudine a fost împărțirea proporțională , iar în curând a fost găsită o procedură pentru n participanți .

Un criteriu mai strict pentru absența invidiei a fost introdus în problema tăierii prăjiturii de către Georgy Gamow și Marvin Stern în anii 1950 [2] .

Procedura pentru trei participanți și aspectul general al pieselor a fost găsit în 1960. Procedura pentru trei participanți și piese conectate a fost găsită abia în 1980.

Împărțirea invidioasă pentru patru sau mai multe persoane a fost o problemă deschisă până în anii 1990, când au fost publicate trei proceduri pentru forma generală a pieselor și o procedură pentru piesele conexe. Toate aceste proceduri sunt nelimitate - pot necesita o serie de pași care nu sunt limitate în prealabil. Procedura pentru piesele conectate poate necesita chiar un număr infinit de pași.

Două limite inferioare ale complexității timpului de rulare a problemei diviziunii invidioase au fost publicate în anii 2000:

pentru piesele de formă generală, limita inferioară este egală cu ; $\Omega (n^{2})$
pentru piesele conectate, limita inferioară este egală cu infinitul - poate că nu există un protocol final pentru trei sau mai mulți participanți.

În anii 2010 au fost publicate unele proceduri și proceduri de aproximare pentru cazuri speciale. Întrebarea dacă există proceduri cu un timp limitat de rulare pentru piesele de formă generală a rămas deschisă mult timp. Problema a fost în cele din urmă rezolvată în 2016. Haris Aziz și Simon McKenzie au propus un protocol de divizare discret, invidios, care nu necesită mai multe interogări. Există încă un decalaj uriaș între limita inferioară și valoarea dată de procedură. Până în august 2016, complexitatea de timp exactă a problemei diviziunii invidioase a rămas necunoscută. ${\displaystyle n^{n^{n^{n^{n^{n)))))))$

În cazul pieselor conectate, s-a observat că rezultatul de dificultate presupune că întreaga piesă trebuie împărțită. Dacă această cerință este înlocuită cu cerința mai slabă ca orice participant să primească o valoare proporțională (din cel puțin întreaga bucată conform propriei estimări), atunci procedura limitată pentru trei participanți este cunoscută, dar rămâne încă o întrebare deschisă dacă există proceduri cu timp limitat de funcționare pentru patru sau mai mulți membri. ${\tfrac {1}{n)}$

Piese conectate

Dovada existenței

O diviziune invidioasă a n agenți cu piese conectate există întotdeauna sub următoarele ipoteze [3] .

nici un agent nu preferă o piesă goală (un set gol de puncte) unei piese nevide;
preferinţele agenţilor sunt continue.

Nu este necesar ca preferințele agenților să fie reprezentate de o funcție aditivă .

Conceptul principal al demonstrației este simplexul de partiție . Să presupunem că tortul este un segment [0;1]. Fiecare partiție cu piese conectate poate fi reprezentată în mod unic prin n − 1 numere în intervalul [0;1], fiecare număr reprezentând locația tăieturii. Unirea tuturor partițiilor este un simplex.

Pentru orice partiție, orice agent are una sau mai multe piese pe care le preferă. De exemplu, pentru o partiție reprezentată prin numerele „0,3;0,5”, un agent poate prefera piesa #1 (segmentul [0;0.3]), în timp ce un alt agent poate prefera piesa #2 (segmentul [0, 3;0.5]) , iar al treilea agent preferă ambele piese #1 și #2 (ceea ce înseamnă, în opinia sa, că nu există nicio diferență între ele, dar sunt mai bune decât piesa #3).

Pentru orice agent, simplexul de partiționare este acoperit de n părți, eventual suprapuse una pe cealaltă de-a lungul granițelor lor, astfel încât pentru toate partițiile din partea i , agentul preferă piesa i . În interiorul părții i , agentul preferă numai piesa i , deși la limita părții i , agentul preferă și alte piese. Astfel, pentru orice i , există o anumită regiune în partiția simplex în care cel puțin un agent preferă numai piesa i . Să numim această zonă . Folosind o lemă topologică (care este similară cu lema Knaster-Kuratowski-Mazurkiewicz ), se poate demonstra că intersecția tuturor U i este nevidă . Prin urmare, există o partiție în care fiecare piesă este singura pe care o preferă agentul. Deoarece numărul de bucăți este egal cu numărul de agenți, putem aloca fiecare bucată unui agent care o preferă și să obținem o distribuție fără invidie. $U_{i}$

Proceduri

Pentru trei agenți, o partiție fără invidie poate fi găsită folosind mai multe proceduri diferite:

Procedura „Moving Knife” a lui Stromkvist folosește patru cuțite care se mișcă simultan - un cuțit este mutat de arbitru, iar celelalte trei - unul pentru fiecare agent;
Procedura Barbanel-Brahms Moving Knife folosește două cuțite care se mișcă simultan;
Procedura „Moving Knife” de la Robertson-Webb poate fi utilizată atunci când tortul este bidimensional și este folosit doar un cuțit în mișcare.

Există proceduri continue - se bazează pe mișcări continue și simultane ale cuțitelor de către o persoană. Aceste proceduri nu pot fi finalizate într-un număr finit de pași discreti.

Pentru n participanți, o împărțire fără invidie poate fi găsită prin protocolul Simmons-Su de tăiere a prăjiturii . Protocolul folosește un simplex de partiționare , similar cu cel folosit în demonstrarea existenței lui Stromquist. Protocolul formează o secvență de partiții care converg către o partiție fără invidie. Convergența poate necesita o infinitate de pași.

Nu este o coincidență că toți acești algoritmi necesită un număr infinit de solicitări. După cum vom arăta în următoarea subsecțiune, este posibil să nu fie posibil să găsiți tăieturi de tort fără invidie cu bucăți conectate cu un număr finit de interogări.

Rezultate după dificultate

O partiție fără invidie cu piese conectate pentru 3 sau mai mulți agenți nu poate fi găsită prin protocolul finit [4] . Motivul acestui rezultat nu contrazice algoritmii menționați mai sus, întrucât aceștia nu sunt finiți în sens matematic [5] .

Dovada imposibilității folosește un sistem de măsurare rigidă ( RMS) - un sistem de n măsuri de evaluare, pentru care împărțirea fără invidie ar trebui să taie tortul în locuri foarte specifice. Atunci căutarea diviziunii fără invidie se reduce la căutarea acestor locuri specifice. Presupunând că tortul este un interval real [0;1], căutarea unei partiții fără invidie folosind interogări asupra participanților este echivalentă cu căutarea numerelor reale în intervalul [0;1] folosind întrebări da/nu. Acest lucru poate necesita un număr infinit de întrebări.

RMS pentru trei participanți poate fi construit după cum urmează. Fie x , y , s și t parametri care îndeplinesc condițiile

$0<x<y<1,$
$0<s<{\tfrac {1}{3}}<t<{\tfrac {1}{2)),$
$s+2t=1.$

Să construim un set de trei măsuri cu două proprietăți:

densitatea fiecărei măsuri este strict între și (astfel încât, pentru o anumită piesă, estimările agenților nu diferă cu cel mult un factor de doi); ${\tfrac {\sqrt {2}}{2}}$ ${\sqrt {2}}$
valorile pieselor definite de numerele x și y sunt date în tabel:

Agent	[0; x ]	[ x ; y ]	[ y ;1]
A	t	t	s
B	s	t	t
C	t	s	t

Atunci orice partiție fără invidie între Alice, Bob și Carl trebuie să aibă tăieturi la x și y (există exact două astfel de partiții), deoarece orice alte locuri vor duce la invidie:

dacă se fac tăieturi la stânga lui x și la dreapta lui y , atunci Alice și Bob vor insista asupra piesei din mijloc;
dacă tăieturile sunt făcute la dreapta lui x și la stânga lui y , niciunul dintre participanți nu va dori să ia piesa din mijloc;
dacă se fac tăieturi la dreapta lui x și la dreapta lui y (să zicem, la x* > x și y* > y ), atunci atât Alice, cât și Carl vor prefera piesele din stânga față de cele din dreapta, deci Bob va trebui să fie de acord să ia piesa cea mai potrivită. Aceasta înseamnă că Bob trebuie să evalueze piesa [ x ; x* ] este de cel puțin două ori mai mare decât [ y ; y* ]. Dar din cauza restricției privind densitatea prețului, aceasta înseamnă că atât Alice, cât și Carl au estimarea [ x ; x* ] este mai mare decât [ y ; y* ], deci vor insista asupra pieselor lasate;
al patrulea caz (tăierea la stânga lui x și la stânga lui y ) este similar cu cel precedent.

Pentru orice RMS, orice agent i și orice constantă , există un RMS ușor diferit cu următoarele proprietăți: $\varepsilon >0$

noua măsură a estimărilor agentului i este complet identică cu vechea lui măsură a estimărilor;
noile măsuri de estimări ale celorlalți doi agenți sunt identice cu vechile lor măsuri peste tot, cu excepția vecinătăților punctelor x și y . $\varepsilon$

Aceasta înseamnă că, dacă o interogare răspunde la ceva în afara cartierelor x și y , agentul i nu are de unde să știe dacă a fost vechiul RMS sau noul RMS.

Cu aceste cunoștințe, este posibil să obstrucționați orice protocol de diviziune invidios, astfel încât să dureze la infinit:

Să începem cu orice RMS, de exemplu, cu parametrii ; $x={\tfrac {1}{3});y={\tfrac {2}{3));s=0,3;t=0,35$
dacă protocolul face tăieturi în afara x și y , continuați;
când protocolul îi cere participantului i să facă o tăietură la x sau y , comutați la un alt RMS cu și , asigurându-vă că valorile sunt aceleași ca pentru tăieturile anterioare. $x'\neq x$ $y'\neq y$

Acest protocol nu poate tăia niciodată în punctele x și y corecte care sunt necesare pentru o împărțire fără invidie.

Aproximații

Deoarece tăierea prăjiturii fără invidie cu piese conectate nu se poate face într-un timp finit, tăietorii de tort trebuie să încerce cumva să rezolve această problemă.

O abordare este de a căuta diviziuni care sunt doar aproximativ libere de invidie . Există două moduri de a defini o aproximare - în unități de lungime sau în unități de evaluare .

Aproximarea bazată pe lungime utilizează următoarele definiții.

O divizare a tortului este reprezentată de n lungimi de segmente pe care le creează despărțirea. Astfel, (0,2;0,5;0,3) este o partiție a segmentului unitar în trei subintervale cu lungimi 0,2, 0,5 și 0,3 (partiția se formează prin tăierea segmentului unitar la punctele 0,2 și 0, 7).
O multipartiție este un set de mai multe partiții diferite. Se spune că o multipartiție a lui X este lipsită de invidie dacă există o permutare a participanților astfel încât pentru orice i există un element din X, astfel încât i --lea participant preferă i --lea segment. -multipartition este o multipartiție în care pentru fiecare pereche de partiții diferența dintre coordonatele lor nu depășește . De exemplu: {(0,2+ ;0,5;0,3), (0,2;0,5+ ;0,3), (0,2;0,5;0,3+ )}. $\delta$ $\delta$ $\delta$ $\delta$ $\delta$

Parametrul reprezintă toleranța participanților în unități de lungime. De exemplu, dacă o bucată de pământ este împărțită și participanții sunt de acord că o abatere de 0,01 metri nu contează pentru ei, atunci este logic să priviți o partiție multiplă de 0,01 fără invidie. Deng, Key și Sabery [6] au propus o modificare a protocolului Simmons de tăiere a tortului , care conține o partiție multiplă bazată pe interogări fără invidie . Mai mult, au demonstrat limita inferioară în interogări. Chiar și atunci când funcțiile de utilitate sunt date în mod explicit de algoritmi de timp polinomial, tăierea prăjiturii fără invidie este o problemă dificilă . $\delta$ $\delta$ $O[(1/\delta )^{n-2}]$ $\Omega [{\tfrac {(1/\delta )^{n-2}}{2^{(n-1)(n-2)))}]$

Aproximarea bazată pe valoare folosește următoarea notație:

o partiție X este numită fără invidie dacă există o permutare a participanților astfel încât pentru orice i valoarea piesei i -a plus nu este mai mică decât valoarea oricărei alte piese: ; $\varepsilon$ $\varepsilon$ $\forall i,j:V_{i}(X_{i})+\varepsilon \geqslant V_{i}(X_{j})$
se spune că o măsură de evaluare este Lipschitz continuă dacă există o constantă K astfel încât, pentru orice pereche de segmente, diferența dintre valorile lor nu depășește lungimea K - fold a diferenței lor simetrice . $\exists K:\forall j:|V_{i}(X_{i})-V_{i}(X_{j})|\leqslant K\cdot \mathrm {lungime} (X_{i}\ setminus X_{j}\cup X_{j}\setminus X_{i})$

Dacă toate măsurile estimatorilor sunt continue Lipschitz, atunci cele două definiții ale aproximării sunt legate. Lasă . Atunci orice partiție în -multipartiție fără invidie este -liberă de invidie [6] . Prin urmare, rezultatele lui Deng, Key și Sabury demonstrează că, dacă toți participanții au limite continue Lipschitz, o partiție fără invidie poate fi găsită folosind interogări. $\varepsilon =2K\delta$ $\delta$ $\varepsilon$ $\varepsilon$ $\Theta [(1/\varepsilon )^{n-2}]$

Calculul offline este a doua soluție care găsește distribuția complet fără invidie, dar numai pentru o clasă limitată de estimări. Dacă toate măsurile de evaluare sunt polinoame de cel mult d , atunci există un algoritm care este polinom în n și d [7] . Dacă d este dat, algoritmul solicită agenților d + 1 solicitări de evaluare, ceea ce produce d + 1 puncte pe diagrama de măsurare a ratingului. Se știe că d +1 puncte sunt suficiente pentru a interpola un polinom de gradul d . Prin urmare, algoritmul poate interpola toate măsurile estimărilor tuturor agenților și poate găsi o distribuție fără invidie în mod autonom. Numărul de cereri necesare este de . $O(n^{2}d)$

Aruncarea este o a treia soluție care păstrează cerința ca tăietura rezultată să fie complet fără invidie și funcționează pentru toate măsurile de evaluare, dar cerința ca întregul tort să fie împărțit este omisă în acest caz. Adică, este permis să împărțiți un subset al tortului și să aruncați restul. Fără cerințe suplimentare, problema este banală, deoarece se rezolvă prin aruncarea întregului tor fără a aloca piesele agenților. Astfel, scopul real este de a oferi fiecărui agent o valoare strict pozitivă. Fiecare distribuție de tort poate fi caracterizată printr-un nivel de proporționalitate , care este valoarea agentului cel mai puțin norocos. Spărgerea întregului tort fără invidie este, de asemenea, o împărțire proporțională, iar nivelul de proporționalitate în acest caz nu este mai mic decât , cea mai bună valoare posibilă. Dar în cazul în care este activată eliminarea, alocarea fără invidie poate avea un nivel mai scăzut de proporționalitate, iar scopul este de a găsi o împărțire fără invidie cu cea mai mare proporționalitate posibilă. Frontiere cunoscute în prezent: $1/n$

pentru 3 agenți proporționalitatea este , adică împărțirea invidioasă și împărțirea proporțională sunt realizabile într-un timp limitat [8] ; $1/3$
pentru 4 agenți proporționalitatea este [8] ; $1/7$
pentru n agenţi proporţionalitatea este [9] . $1/(3n)$

Nu se știe dacă există o procedură de împărțire proporțională limitată în timp fără invidie pentru patru sau mai mulți participanți în cazul pieselor conectate.

Opțiuni

Majoritatea procedurilor de tăiere a unui tort cu bucăți conectate presupun că tortul este un segment unidimensional și piesele sunt subintervale. Este adesea de dorit ca piesele să aibă o anumită formă geometrică, cum ar fi un pătrat. Având în vedere o astfel de constrângere, este posibil să nu fie posibilă împărțirea întregului tort (de exemplu, un pătrat nu poate fi împărțit în două pătrate), așa că trebuie să existe bucăți nedistribuite. După cum sa explicat mai sus, atunci când sunt permise bucăți nealocate, procedurile sunt măsurate prin nivelul lor de proporționalitate - valoarea pe care o garantează fiecărui participant. În prezent se cunosc următoarele [10] :

pentru doi participanți, atunci când se împart un tort pătrat și se dorește să obțină bucăți pătrate, proporționalitatea este egală și acesta este cel mai bun care poate fi garantat chiar și fără invidie; $1/4$
pentru trei participanți, atunci când împărțiți un tort pătrat și doriți să obțineți bucăți pătrate, proporționalitatea este . Cel mai bun care poate fi garantat în absența invidiei este . $1/10$ $1/6$

Piese deconectate

Proceduri

Pentru trei participanți, procedura discretă Selfridge-Conway realizează o divizare invidioasă cu cel mult 5 tăieturi. Alte proceduri care folosesc cuțite în mișcare necesită mai puține incizii:

Procedura Levmore's Moving Knife - Cook necesită maxim 4 incizii;
procedura de rotație a cuțitelor Brahms-Taylor-Zwicker pentru tăierea prăjiturii necesită nu mai mult de 3 tăieturi (acesta este rezultatul pentru trei bucăți conectate când tortul este un cerc, dar în cazul unui tort sub formă de segment există vor fi patru bucăți);
folosind procedura Austin „Moving Knife” pentru doi participanți, se poate obține o separare fără invidie pentru 3 participanți cu cel mult 3 tăieturi. Această idee este atribuită lui William Webb [11] .

Pentru patru participanți , procedura Brahms-Taylor-Zwicker realizează împărțirea fără invidie cu cel mult 11 tăieturi [12] . Pentru cinci participanți, procedura lui Sabery și Wang face împărțirea fără invidie un număr limitat de tăieturi [13] . Ambele proceduri folosesc procedura Austin pentru doi participanți și diviziuni comune ca pas inițial. Prin urmare, aceste proceduri ar trebui considerate infinite - nu pot fi finalizate într-un număr finit de pași.

Pentru patru sau mai mulți participanți, există trei algoritmi care sunt finiți, dar nu sunt limitați - nu există o limită fixă a numărului de tăieturi necesare [14] . Există trei astfel de algoritmi:

procedura Brahms-Taylor , publicată pentru prima dată într-o lucrare din 1995 și mai târziu într-o carte din 1996;
Protocolul Robertson-Webb , publicat pentru prima dată într-un articol din 1997 și mai târziu într-o carte din 1998;
Protocolul lui Pikhurko [15] a fost publicat în 2000.

Deși protocoalele diferă, ideea lor principală rămâne similară - împărțim tortul într-un număr finit, dar nu limitat, de „fărâmituri”, fiecare dintre ele fiind atât de mic încât toți participanții își neglijează valoarea. Apoi combinăm firimiturile într-un mod sofisticat pentru a obține diviziunea dorită. William Gassar a comparat trei algoritmi nerestricționați folosind numere ordinale [16] .

Întrebarea dacă tăierea tortului se poate face fără invidie într-un timp limitat pentru patru sau mai mulți participanți a rămas o problemă deschisă de mulți ani. În cele din urmă, a fost rezolvată în 2016 de Hariz Aziz și Simon McKenzie. Inițial, au dezvoltat un algoritm de timp limitat pentru patru participanți [17] . Apoi și-au extins algoritmul pentru a lucra cu orice număr de participanți [9] . Algoritmul lor nu necesită mai multe solicitări. Deși numărul este limitat, este foarte departe de limita inferioară . Deci întrebarea de câte întrebări sunt necesare pentru a tăia tortul fără invidie rămâne deschisă. ${\displaystyle n^{n^{n^{n^{n^{n)))))))$ $\Omega (n^{2})$

Aproximații și soluții parțiale

O versiune închisă a protocolului last-down găsește o aproximare aditivă fără invidie a partiției într-un timp limitat. În special, pentru orice constantă , algoritmul returnează o partiție în care valoarea fiecărui membru este cel puțin cea mai mare valoare minus , în timp . $\varepsilon >0$ $\varepsilon$ $n^{2}/\varepsilon$

Dacă toate măsurile sunt liniare pe bucăți , există un algoritm [18] care este polinom în dimensiunea reprezentării funcțiilor de evaluare . Numărul cererilor sale este , unde este egal cu numărul de lacune în derivatele funcțiilor de densitate estimărilor. $O(n^{6}k\ln {k})$ $k$

Rezultate după dificultate

Orice procedură de divizare invidioasă pentru n oameni necesită cel puțin solicitări [19] . Dovada se bazează pe o analiză atentă a cantității de informații pe care algoritmul o are de la fiecare participant. $\Omega (n^{2})$

Să presupunem că tortul este un interval unidimensional [0;1] și că valoarea întregului tort pentru fiecare dintre participanți este normalizată la 1. La fiecare pas, algoritmul cere unui anumit participant fie să evalueze un anumit interval conținut. în [0;1], Sau marcați intervalul cu o anumită valoare. În ambele cazuri, algoritmul colectează informații doar despre intervalele ale căror puncte finale au fost menționate în cerere sau în răspuns. Să numim aceste puncte finale etape . Inițial, reperele pentru i sunt doar 0 și 1, deoarece algoritmul știe doar despre participantul i că . Dacă algoritmul cere participantului i să evalueze [0,2;1], atunci după răspuns, reperele pentru i sunt {0;0,2;1}. Algoritmul poate calcula , dar nu orice interval al cărui punct final este diferit de 0,2. Numărul de repere crește cu maximum 2 cu fiecare întrebare. În special, valoarea segmentului [0;0,2] poate fi concentrată aproape de 0, sau aproape de 0,2, sau undeva între aceste valori. $v_{i}([0;1])=1$ $v_{i}([0;0,2])$

Intervalul dintre două etape consecutive pentru membrul i se numește interval de reper al membrului i . Când algoritmul decide să aloce o bucată de tort membrului i , trebuie să aloce o piesă al cărei punctaj total pentru i nu este mai mic decât oricare dintre membrii i. intervalul de reper al lui . Dovada prin contradicție - să presupunem că există un anumit interval de repere J a căror valoare pentru i este mai mare decât valoarea reală alocată membrului i . Un alt participant, să zicem j , va primi în mod necesar o parte din intervalul de reper J . Conform punctului A, există posibilitatea ca întreaga valoare a intervalului J să fie concentrată în interiorul porțiunii alocate participantului j . Atunci voi invidia j și partiția nu va fi scutită de invidie.

Să presupunem că toți participanții au răspuns la toate întrebările ca și cum scorurile lor ar fi omogene (adică valoarea intervalului este egală cu lungimea acestuia). Conform articolului B, algoritmul poate aloca o piesă participantului i numai dacă aceasta este mai lungă decât toate intervalele de reper pentru participantul i . Cel puțin participanții trebuie să primească un interval nu mai mare de 2/ n . Prin urmare, toate intervalele lor de reper trebuie să aibă lungimi care să nu depășească 2/ n . Prin urmare, acestea trebuie să aibă cel puțin intervale de repere și, prin urmare, numărul de repere trebuie să fie de cel puțin . ${\tfrac {n}{2))$ ${\tfrac {n}{2))$ ${\tfrac {n}{2))$

Fiecare întrebare la care a răspuns participantul i introduce cel mult două obiective noi, astfel încât numărul de etape pentru participantul i să crească cu cel mult 2. Prin urmare, în cazul descris la punctul C, algoritmul trebuie să interogheze fiecare dintre participanți, oferind cel puțin cel puțin n /4 întrebări. Numărul total de întrebări nu va fi apoi mai mic de . ${\tfrac {n}{2))$ ${\tfrac {n^{2}}{8}}=\Omega (n^{2})$

Rămâne o întrebare deschisă dacă există un algoritm restrâns pentru funcțiile de evaluare arbitrare. Astfel, există un decalaj uriaș între limita inferioară și cel mai bun algoritm cunoscut în prezent, care este finit, dar nu limitat. $\Omega (n^{2})$

Dovezi de existență și variante

Pe lângă dovezile de existență în forma generală care decurg din algoritmii descriși mai sus, există dovezi pentru existența partițiilor fără invidie cu proprietăți suplimentare:

există o împărțire exactă , care, în special, este lipsită de invidie ( teoremele Dubins-Spanier );
există o distribuție fără invidie care este și Pareto eficientă ( teorema lui Weller ).

Ambele dovezi funcționează numai pentru măsuri aditive de evaluare non-atomică și se bazează pe capacitatea de a aloca un număr mare de piese deconectate fiecărui participant.

Diviziune invidioasă cu acțiuni diferite

O generalizare a criteriului de non-invidie este de a permite fiecărui participant să aibă cote diferite. Adică, pentru orice participant i există o pondere care descrie partea din tort pe care i se atribuie să o furnizeze (suma tuturor acțiunilor w i este egală cu 1). Apoi, o partiție ponderată fără invidie este definită după cum urmează. Pentru orice agent i cu o măsură a estimărilor și pentru orice alt agent k : $w_{i}$ $V_i$

$V_{i}(X_{i})/w_{i}\geqslant V_{i}(X_{j})/w_{j)$

Adică, orice participant consideră că cota alocată de acesta, corespunzătoare cotei sale preconizate, nu este mai mică decât cota alocată, corespunzătoare cotei preconizate a altor participanți.

Când toate ponderile sunt încă aceleași (și egale ), această definiție se reduce la definiția standard a non-invidiei. ${\tfrac {1}{n)}$

Dacă piesele pot fi deconectate, o partiție ponderată fără invidie există întotdeauna și poate fi găsită folosind protocolul Robertson-Webb pentru orice set de greutăți. Zeng a propus un algoritm alternativ pentru partiţionarea ponderată aproximativă fără invidie care necesită un număr mic de tăieturi [20] .

Dar când piesele trebuie conectate, este posibil să nu existe o partiție ponderată fără invidie. Pentru a înțelege acest lucru, rețineți că orice partiție ponderată fără invidie este, de asemenea, ponderată proporțional cu același vector de greutate. Aceasta înseamnă că orice agent i cu o măsură de estimări V i :

$V_{i}(X_{i})/w_{i}\geqslant V_{i}(C)$

Se știe că o distribuție proporțională ponderată cu piese conectate poate să nu existe: vezi împărțirea proporțională a unei prăjituri cu părți diferite , de exemplu.

Rețineți că există o definiție alternativă a unei distribuții ponderate fără invidie, în care ponderile sunt atribuite pieselor și nu agenților. Pentru această definiție, se știe că există o distribuție ponderată fără invidie în următoarele cazuri (fiecare caz generalizează cazul anterior):

funcții de evaluare aditivă, tort unidimensional (segment), piesele trebuie să fie segmente conectate [21] ;
funcții de evaluare aditivă, tort multidimensional ca simplex , piesele trebuie să fie simplexe [22] . Demonstrarea folosește teorema Sperner , lema Knaster-Kuratowski-Mazurkiewicz , lema de acoperire Gale și lema punctelor coincidente Ki Fan ;
funcții de evaluare non-aditive, tort multidimensional simplex , piesele trebuie să fie poliedre [23] .

Împărțirea tortului „rău”

În unele cazuri, „tortul” care poate fi partajat are o valoare negativă. De exemplu, ar putea fi o bucată de gazon care trebuie tunsă sau o bucată de teren pustiu care trebuie curățată. În acest caz, tortul este un „rău eterogen” și nu un „bun eterogen”.

Unele proceduri de tăiere a prăjiturii fără invidie pot fi adaptate pentru astfel de prăjituri slabe, dar adaptarea nu este adesea banală.

Tabelele finale

Proceduri după rezultate

Nume	Tip de	Tort	piese	Număr de participanți ( n )	Numărul de cereri	Numărul de tăieturi	invidie	Proporționalitate [24]	Comentarii
Delhi-și-alege	procedură discretă	Orice	mesageri	2	2	1 (optimal)	Nu	1/2
Stromquist	Procedura de mutare a cuțitului	Segment de linie	mesageri	3	$\infty$	2 (optimal)	Nu	1/3
Selfridge-Conway	procedură discretă	Orice	Deconectat	3	9	5	Nu	1/3
Brahms-Taylor-Zwicker	Procedura de mutare a cuțitului	Orice	Deconectat	patru	$\infty$	unsprezece	Nu	1/4
Sabury-Wonga [13]	procedură discretă	Orice	Deconectat	patru	Limitat	Limitat	Nu	1/4	posibilă piesă aruncată
Aziza - Mackenzie [17]	procedură discretă	Orice	Deconectat	patru	203	584	Nu	1/4
Sabury-Wonga [13]	Procedura de mutare a cuțitului	Orice	Deconectat	5	$\infty$	Limitat	Nu	1/5
Stromquist	Existenţă	Segment de linie	mesageri	n	—	n −1	Nu	1/ n
Simmons	procedură discretă	Segment de linie	mesageri	n	$\infty$	n −1	Nu	1/ n
Denga - Cheie - Sabury	procedură discretă	Segment de linie	mesageri	n	$\left({\frac {1}{\varepsilon }}\right)^{n-2}$	n −1	$\varepsilon$	$\left({\tfrac {1}{n}}\right)-\varepsilon$	Numai când limitele sunt Lipschitz continue
Branzei [7]	procedură discretă	Segment de linie	mesageri	n	$n^{2}d$	necunoscut	Nu	1/ n	Doar atunci când densitățile estimatorului sunt polinomiale cu gradul maxim d .
„ Grăbește-te – fă oamenii să râdă ”	procedură discretă	Segment de linie	mesageri	3	9	patru	Nu	1/3	Posibilă piesă aruncată
„ Grăbește-te – fă oamenii să râdă ”	procedură discretă	Orice	mesageri	patru	16	6	Nu	1/7	Posibilă piesă aruncată
„ Grăbește-te – fă oamenii să râdă ”	procedură discretă	Orice	mesageri	n	$2^{n}$	$2^{n-1}-1$	Nu	${\frac {1}{2^{n-1}))$	Posibilă piesă aruncată
Aziza - Mackenzie ConnectedPieces [9]	procedură discretă	Orice	mesageri	n	$n^{n+1}$	$n^{n+1}$	Nu	${\frac {1}{3n)}$	Posibilă piesă aruncată
Brahms - Taylor	procedură discretă	Orice	Deconectat	n	Nu este limitat	Nu este limitat	Nu	1/ n
Robertson-Webb	procedură discretă	Orice	Deconectat	n	Nu este limitat	Nu este limitat	Nu	1/ n	Compartiment despărțitor ponderat fără invidie
Pikhurko [15]	procedură discretă	Orice	Deconectat	n	Nu este limitat	Nu este limitat	Nu	1/ n
Aziza - Mackenzie [9]	procedură discretă	Orice	Deconectat	n	${\displaystyle n^{n^{n^{n^{n^{n)))))))$	${\displaystyle n^{n^{n^{n^{n^{n)))))))$	Nu	1/ n
Versiunea în buclă închisă a ultimului protocol redus	procedură discretă	Segment de linie	Deconectat	n	$n^{2}/\varepsilon$	necunoscut	$\varepsilon$	1/ n
Kurokawa - Leia - Prokachi [18]	procedură discretă	Segment de linie	Deconectat	n	$n^{6}k\ln k$	necunoscut	Nu	1/ n	Doar atunci când valoarea densităților este liniară pe bucăți cu maximum k discontinuități.
Weller	Existenţă	Orice	Deconectat	n	—	$\infty$	Nu	1/ n	Pareto eficient .
2D	procedură discretă	Pătrat	Conectat și pătrat	2	2	2	Nu	1/4	Posibilă piesă aruncată
2D	Procedura de mutare a cuțitului	Pătrat	Conectat și pătrat	3	$\infty$	6	Nu	1/10	Posibilă piesă aruncată

Masa finală după numărul de participanți și tipul de piese:

numarul de agenti	Piese legate	Piese generale
2	Delhi-și-alege
3	Procedura „Moving Knife” a lui Stromkvist (timp infinit); „ Grăbește-te – fă oamenii să râdă ” (timp limitat, număr limitat de tăieturi, posibilă piesă aruncată, proporțională)	Procedura Selfridge-Conway discretă (timp limitat, nu mai mult de 5 incizii).
patru	„ Dacă te grăbești, vei face oamenii să râdă ” (timp limitat, număr limitat de tăieturi, este posibilă o piesă aruncată, proporționalitate 1/7).	Procedura Brahms-Taylor-Zwicker (timp infinit, nu mai mult de 11 tăieturi). Procedura Sabery-Wong discretă [13] (timp limitat, număr limitat de tăieturi, posibilă piesă aruncată, proporțională). Procedura discretă Aziz-Mackenzie [17] (timp limitat, număr limitat de tăieturi, proporțional).
5		Procedurile „Moving Knife” ale lui Sabury-Wong [13] (timp infinit, număr limitat de tăieturi).
n	Protocol Simmons (timp infinit) Deng-Ki-Sabury (aproximativ fără invidie, timp exponențial). „ Grăbește-te - fă oamenii să râdă ” (total liber de invidie, timp exponențial, posibil piesă de piesă, proporționalitate exponențială) ConnectedPieces Aziz - Mackenzie [9] (total liber de invidie, timp exponențial, posibil piesă de piesă, proporționalitate liniară)	Brahms & Taylor (1995) ; Robertson & Webb (1998) . Ambii algoritmi necesită un număr finit, dar nu limitat de tăieturi. Procedura Aziz-Mackenzie discretă [9] (timp limitat, număr limitat de tăieturi, împărțire proporțională).
Dificultate	Toți algoritmii pentru trebuie să fie infiniti (Stromquist, 2008). $n\geqslant 3$	Toți algoritmii trebuie să utilizeze cel puțin pași (Procaccia, 2009). $\Omega (n^{2})$
Opțiuni	Există o partiție ponderată fără invidie pentru ponderi arbitrare (Idzik, 1995), chiar și atunci când tortul și bucățile sunt simplexe (Idzik, Ichiishi, 1996), și chiar cu preferințe non-aditive (Dall'Aglio și Maccheroni, 2009).	Protocolul Robertson-Webb poate găsi o partiție ponderată fără invidie pentru greutăți arbitrare. Există o diviziune perfectă (Dubins & Spanier, 1961). Există o tăiere fără invidie și eficientă a tortului ( Teorema lui Weller ).

Vezi și

Note

↑ Adesea tradus literal din engleză ca Envy -free cake-cutting , deși invidia joacă un rol cheie în această diviziune. Articolul folosește termenul „diviziune invidioasă”, dar rezultatul acestei împărțiri trebuie să fie o distribuție fără invidie .
↑ Gamow, Stern, 1958 .
↑ Stromquist, 1980 , p. 640–644.
↑ Stromquist, 2008 .
↑ Procedura „Moving Knife” a lui Stromkvist cere agenților să-și miște cuțitele în timp ce arbitrul își mută sabia. Deoarece mișcarea sabiei este continuă, numărul de pași necesari este de nenumărat (și, prin urmare, în mod natural, infinit). Protocolul de tăiere a tortului lui Simmons converge către o partiție fără invidie, dar poate necesita un număr infinit de pași.
↑ 1 2 Deng, Qi, Saberi, 2012 , p. 1461–1476
↑ 12 Brânzei , 2015 , p. 93–95.
↑ 1 2 Segal-Halevi, Hassidim, Aumann, 2016 , p. 1–32.
↑ 1 2 3 4 5 6 Aziz, MacKenzie, 2016 .
↑ Segal-Halevi, Hassidim, Aumann, 2015 , p. 1021–1028.
↑ Brams și Taylor 1996 , p. 124–125.
↑ Brams, Taylor, Zwicker, 1997 , p. 547–555.
↑ 1 2 3 4 5 Saberi, Wang, 2009 .
↑ SJ Brams, MA Jones, C. Klamler, „Better ways to cut a cake”, Notices of the AMS, 2005. [Online]. Disponibil: http://www.ams.org/notices/200611/fea-brams.pdf Arhivat 30 septembrie 2019 la Wayback Machine
↑ 1 2 Pikhurko, 2000 , p. 736–738.
↑ Gasarch, William, Which Unbounded Protocol for Envy Free Cake Cutting is Better?, arΧiv : 1507.08497 [math.LO].
↑ 1 2 3 Aziz, MacKenzie, 2016 , p. 454.
↑ 1 2 Kurokawa, Lai, Procaccia, 2013 .
↑ Procaccia, 2009 , p. 239–244.
↑ Zeng, 2000 , p. 259–271.
↑ Idzik, 1995 .
↑ Ichiishi, Idzik, 1999 , p. 389–400.
↑ Dall'Aglio, MacCheroni, 2009 , p. 57–77.
↑ Valoarea (ca parte a întregului tort) care este garantată fiecărui agent prin estimări aditive. Când nu există invidie și întregul tort este împărțit, proporționalitatea este întotdeauna , cea mai bună posibilă. ${\tfrac {1}{n)}$

Literatură

George Gamow, Marvin Stern. Puzzle-matematică . - 1958. - ISBN 978-0670583355 .
Walter Stromquist. Cum să tăiați o prăjitură în mod corect // The American Mathematical Monthly. - 1980. - T. 87 , nr. 8 . - doi : 10.2307/2320951 . — .
Walter Stromquist. Diviziunile de tort fără invidie nu pot fi găsite prin protocoale finite // Electronic Journal of Combinatorics. - 2008. Arhivat 11 martie 2016.
Deng X., Qi Q., Saberi A. Soluții algoritmice pentru tăierea prăjiturii fără invidie // Cercetare operațională. - 2012. - T. 60 , nr. 6 . doi : 10.1287 / opre.1120.1116 .
Brânzei S. O notă despre tăierea prăjiturii fără invidie cu evaluări polinomiale // Litere de prelucrare a informațiilor. - 2015. - T. 115 , nr. 2 . - doi : 10.1016/j.ipl.2014.07.005 .
Erel Segal-Halevi, Avinatan Hassidim, Yonatan Aumann. Tăiere de prăjituri fără invidie în două dimensiuni // A 29-a Conferință AAAI privind inteligența artificială (AAAI-15). - Austin, Texas, 2015. - doi : 10.13140/RG.2.1.5047.7923 .
Erel Segal-Halevi, Avinatan Hassidim, Yonatan Aumann. Deșeurile se grăbesc // Tranzacții ACM pe algoritmi. - 2016. - T. 13 . - doi : 10.1145/2988232 . - arXiv : 1511.02599 .
Steven J. Brams, Alan D. Taylor, William S. Zwicker. O soluție de cuțit în mișcare pentru divizia de prăjituri fără invidie pentru patru persoane // Proceedings of the American Mathematical Society. - 1997. - T. 125 , nr. 2 . - doi : 10.1090/S0002-9939-97-03614-9 .
Amin Saberi, Ying Wang. Cutting a Torte for Five People // Aspecte algoritmice în informare și management. - 2009. - doi : 10.1007/978-3-642-02158-9_25 .
Pikhurko O. On Envy-Free Cake Division // The American Mathematical Monthly. - 2000. - T. 107 , nr. 8 . - doi : 10.2307/2695471 . — .
Haris Aziz, Simon MacKenzie. Un protocol discret și mărginit de tăiere a tortului fără invidie pentru patru agenți // Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing - STOC 2016. - 2016. - ISBN 9781450341325 . - doi : 10.1145/2897518.2897522 .
Haris Aziz, Simon MacKenzie. Un protocol discret și mărginit de tăiere a prăjiturii fără invidie pentru orice număr de agenți // FOCS 2016. - 2016.
David Kurokawa, John K. Lai, Ariel D. Procaccia. Cum să tai o prăjitură înainte de a se termina petrecerea // AAAI. — 2013.
Ariel Procaccia. Thou Shalt Covet Thy Neighbour's Coke // IJCAI'09 Proceedings of the 21st International Joint Conference on Artificial Intelligence. — 2009.
Dao Zhi Zeng. Proceduri aproximative fără invidie // Practica jocului: Contribuții din teoria jocurilor aplicate . - Springer, 2000. - Vol. 23. - (Biblioteca de teorie și decizie). — ISBN 9781461546276 . - doi : 10.1007/978-1-4615-4627-6_17 .
Adam Idzik. Diviziuni optime ale intervalului unității // Conferința internațională în onoarea lui Robert J. Aumann la 65 de ani de naștere. — Ierusalim, 1995.
Ichiishi T., Idzik A. Alocare echitabilă a bunurilor divizibile // Journal of Mathematical Economics. - 1999. - T. 32 , nr. 4 . - doi : 10.1016/s0304-4068(98)00053-6 .
Dall'Aglio M., MacCheroni F. Terenuri disputate // Jocuri și Comportament Economic. - 2009. - T. 66 . - doi : 10.1016/j.geb.2008.04.006 .
Steven J. Brams, Alan D. Taylor. Împărțirea echitabilă: de la tăierea prăjiturii până la soluționarea disputelor . - Cambridge University Press, 1996. - ISBN 0-521-55644-9 .

Link -uri

Calculator de diviziune echitabilă — Un applet de calcul de diviziune fără invidie pentru prăjituri, taxe, menaj și chirie.