Procedura „ultima redusă”

Ultima procedură de scădere este procedura corectă de tăiere a tortului . Procedura este concepută pentru a aloca o resursă divizibilă eterogenă, cum ar fi un tort de ziua de naștere, și implică n participanți la diviziune cu preferințe diferite pentru diferite părți ale tortului. Procedura permite ca n persoane să obțină o împărțire proporțională , adică să împartă tortul între ei, astfel încât fiecare participant să primească cel puțin valoarea totală conform propriei evaluări (subiective). De exemplu, dacă estimarea lui Alice a întregului tort este de 100 USD și sunt 5 participanți, atunci Alice poate obține o bucată pe care o evaluează cel puțin 20 USD, indiferent de ceea ce cred sau fac ceilalți participanți. ${\tfrac {1}{n)}$

Istorie

În timpul celui de-al Doilea Război Mondial, matematicianul evreu polonez Hugo Steinhaus , ascuns de naziști, a devenit interesat de întrebarea cum să împărțim echitabil resursele. Inspirat de procedura Delhi-and-Choose de împărțire a unui tort între doi frați, el le-a rugat pe studenții săi, Stefan Banach și Bronisław Knaster , să găsească o procedură care ar putea funcționa pentru mai mulți oameni și a publicat soluția lor [1] .

Această publicație a inițiat o nouă ramură de cercetare care este acum realizată de mulți cercetători din multe discipline. Vezi articolul Împărțirea târgului .

Descriere

Mai jos este descrierea autorului a protocolului de partajare:

„Sunt participanți A, B, C, .. N. Participantul A taie o bucată arbitrară din tort. Membrul B are acum dreptul, dar nu și obligația, de a reduce piesa prin tăierea unei piese. După ce a făcut acest lucru, C are dreptul (dar nu și obligația) de a reduce piesa deja redusă (sau neredusă) și așa mai departe participantului N. Regula îl obligă pe ultimul care a redus (tăiat) să-și ia parte. Acest participant părăsește divizia și restul de n - 1 participanți încep același joc cu restul tortului. După ce numărul de participanți este redus la doi, aceștia aplică regula clasică de înjumătățire.

Fiecare membru are o metodă care asigură că primește o bucată cu o valoare mai mare sau egală cu . Metoda este următoarea: tăiați întotdeauna piesa curentă, astfel încât valoarea rămasă să fie pentru dvs. Există două opțiuni - fie obțineți piesa pe care ați tăiat-o, fie cealaltă persoană primește o bucată mai mică, pe care o prețuiți mai puțin de . În acest din urmă caz, există n - 1 participanți rămași și estimarea turtei rămase este mai mare decât . Prin inducție, putem demonstra că valoarea rezultată va fi de cel puțin . ${\tfrac {1}{n)}$ ${\tfrac {1}{n)}$ ${\tfrac {1}{n)}$ ${\tfrac {n-1}{n)}$ ${\tfrac {1}{n)}$

Un caz degenerat al unei funcții de preferință generală

Algoritmul este simplificat în cazul degenerat când toți participanții au aceleași funcții de preferință, deoarece participantul care a făcut prima tăietură optimă devine ultimul care a redus. În mod echivalent, fiecare participant 1, 2, ..., n − 1 taie la rândul său o bucată din tortul rămas. Apoi, în ordine inversă, fiecare participant n , n − 1, ..., 1 alege o piesă care nu a fost încă revendicată.

Analiză

Protocolul Last Diminisher este discret și se poate face în runde. În cel mai rău caz, veți avea nevoie de acțiuni - o acțiune pe rundă. ${\tfrac {n\times (n-1)}{2}}=O(n^{2})$

Cu toate acestea, majoritatea acestor acțiuni nu sunt tăieturi reale, adică Alice poate marca piesa dorită pe hârtie, iar celălalt participant o reduce pe aceeași bucată de hârtie și așa mai departe. Numai „ultimul tăietor” ar trebui să taie prajitura. Astfel, sunt necesare doar n − 1 tăieturi. $O(n^{2})$

Procedura este foarte liberală în ceea ce privește inciziile. Inciziile făcute de participanți pot fi de orice formă. Ele pot fi chiar incoerente. Pe de altă parte, tăieturile pot fi limitate pentru a se asigura că piesele au o formă acceptabilă. În special:

Dacă tortul original este conectat, atunci se poate garanta că fiecare bucată este conectată (continuă).
Dacă prăjitura originală este un set convex , atunci fiecare bucată poate fi garantată a fi convexă.
Dacă tortul original este un dreptunghi , atunci fiecare bucată poate fi garantată a fi dreptunghi.
Dacă tortul original este un triunghi , atunci fiecare bucată poate fi garantată a fi un triunghi.

Versiune continuă

O versiune în timp continuă a protocolului poate fi executată folosind procedura Moving Knife a lui Dubins-Spanier [2] . Acesta a fost primul exemplu de procedură de împărțire echitabilă continuă. Cuțitul se mișcă peste tort de la stânga la dreapta. Orice participant poate spune „stop” dacă crede că valoarea piesei din stânga cuțitului este de . Tortul este tăiat și participantul care a spus „stop” primește această bucată. Repetați cu tortul rămas și cu participanții. Ultimul participant primește restul tortului. Similar cu ultima procedură de reducere, această procedură poate fi utilizată pentru a obține bucăți contigue pentru fiecare participant. $1/n$

Versiune aproximativă fără invidie

Dacă există 3 sau mai mulți participanți, partiția obținută folosind protocolul ultimul care trebuie redus nu este întotdeauna lipsită de invidie . De exemplu, să presupunem că primul jucător Alice primește o piesă (pe care o evaluează la 1/3). Apoi ceilalți doi, Bob și Charlie, împart restul în mod corect, în opinia lor, dar în opinia Alicei, cota lui Bob valorează 2/3, în timp ce cota lui Charlie valorează 0. Se dovedește că Alice este geloasă pe Bob.

O soluție simplă [3] este de a permite returnarea . Adică, participantul care a câștigat piesa conform protocolului „ultimul care a redus” nu părăsește jocul, dar poate rămâne în joc și poate participa la pașii următori. Dacă câștigă din nou, trebuie să-și returneze piesa actuală la tort. Pentru a ne asigura că protocolul se termină, alegem o constantă și adăugăm o regulă conform căreia fiecare participant poate reveni la joc nu mai mult de o dată. $\varepsilon$ ${\tfrac {1}{\varepsilon }}$

În versiunea returnată, fiecare membru are o metodă pentru a se asigura că primește o bucată a cărei valoare este cel puțin la fel de mare ca cea mai mare bucată minus . Metoda este următoarea: tăiați întotdeauna piesa curentă, astfel încât partea rămasă să aibă o valoare plus piesa curentă. Acest lucru asigură că valoarea piesei tale crește de fiecare dată când câștigi, iar atunci când nu câștigi, valoarea câștigătorului nu depășește propria ta valoare. Astfel, nivelul invidiei nu depășește . $\varepsilon$ $\varepsilon$ $\varepsilon$ $\varepsilon$

Timpul de rulare al algoritmului nu depășește , deoarece există cel mult pași, iar la fiecare pas interogăm participanții. ${\tfrac {n^{2}}{\varepsilon }}$ ${\tfrac {n}{\varepsilon })$ $n$

Dezavantajul aproximării fără invidie este că piesele nu vor fi neapărat conectate, deoarece piesele merg constant înapoi în tort și sunt redistribuite. Consultați Jealous Cake Cutting#Connected Pieces pentru alte soluții la această problemă.

Îmbunătățiri

Procedura Last Reducer a fost îmbunătățită ulterior în diferite moduri. Consultați articolul Diviziunea proporțională pentru detalii .

Note

↑ Steinhaus, 1948 , p. 101–4.
↑ Dubins și Spanier, 1961 , p. unu.
↑ Brams și Taylor 1996 , p. 130–131.

Literatură

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 .
Lester Eli Dubins, Edwin Henry Spanier. Cum să tăiați o prăjitură în mod corect // The American Mathematical Monthly. - 1961. - T. 68 , nr. 1 . - doi : 10.2307/2311357 . — .
Hugo Steinhaus. Problema împărțirii echitabile // Econometrica. - 1948. - T. 16 , nr. 1 . — .