Împărțirea sarcinilor

Împărțirea sarcinilor sau munca neplăcută, murdară ( ing. Divizarea treburilor , literalmente - rutină, datorie) este o sarcină de împărțire corectă , în care resursa care necesită împărțire este nedorită, astfel încât toată lumea care participă la divizie dorește să obțină cât mai puțin din aceasta. resursă posibilă.

Discuție generală a problemei

Problema este o imagine în oglindă a problemei de tăiere a prăjiturii corecte , în care resursa divizibilă este de dorit, astfel încât participanții la divizie să vrea să obțină cât mai mult posibil. Atât prima cât și a doua sarcină au resurse eterogene . La împărțirea unui tort, de exemplu, tortul poate avea bucăți de capăt, colț și mijloc cu conținut diferit de glazură. Atunci când împarte responsabilitățile unui loc de muncă, pot exista diferite tipuri de responsabilități și diferite cantități de timp pentru a finaliza fiecare job. Ambele sarcini presupun că resursele pot fi partajate. Tipurile de lucrări pot fi împărțite pe termen nelimitat, deoarece setul final de lucrări poate fi împărțit în diferite tipuri, formate și poate dura diferiți pentru a le finaliza. De exemplu, o încărcătură într-o mașină de spălat poate fi împărțită la numărul de articole de îmbrăcăminte și timpul necesar pentru încărcarea mașinii. Sarcinile, însă, diferă în ceea ce privește dezirabilitatea resursei. Problema împărțirii sarcinilor a fost propusă de Martin Gardner în 1978 [1] .

Împărțirea îndatoririlor este adesea menționată ca o împărțire echitabilă a bunurilor anti -bunuri , spre deosebire de problema mai cunoscută a „partajării echitabile a mărfurilor”. Un alt nume este problema muncii murdare . Aceeași resursă poate fi bună sau rea în funcție de situație. De exemplu, să presupunem că resursa care trebuie partajată este curtea din spate a unei case. Într-o situație de împărțire a moștenirii, această curte poate fi o binefacere, întrucât fiecare moștenitor dorește să obțină cât mai mult teren, ca la împărțirea turtei. Dar în cazul împărțirii locurilor de muncă nedorite, cum ar fi tunderea gazonului , această curte poate fi deja considerată un anti-favoare, deoarece majoritatea oamenilor ar dori să petreacă cât mai puțin timp posibil cu treburile casnice, așa că aceasta este deja o sarcină de împărțire a sarcinilor. .

Unele dintre rezultatele din problema tăierii torturilor pot fi pur și simplu transferate în scenariul împărțirii sarcinilor. De exemplu, procedura de împărțire și alegere funcționează la fel de bine pentru ambele sarcini - unul dintre participanți împarte resursa în părți egale, în opinia sa, iar celălalt alege partea care, în opinia sa, este „mai bună”. Diferența este doar în sensul cuvântului „mai bine” – dacă înseamnă „mai mult”, ca în împărțirea tortului, sau dacă înseamnă „mai puțin”, ca în împărțirea sarcinilor. Cu toate acestea, nu toate rezultatele sunt atât de ușor de transferat. Mai jos sunt oferite explicații mai detaliate.

Împărțirea proporțională a sarcinilor

Definiția repartizării pentru împărțirea sarcinilor este o imagine în oglindă a termenului analog pentru tăierea prăjiturii - fiecare participant trebuie să primească o cotă în cel mai rău caz în funcție de propria funcție de indezirabilitate, nu mai mult decât valoarea totală (unde este egală cu numărul total ). de participanți): $i$ $X_{i}$ ${\tfrac {1}{n)}$ $n$

\forall i:V_{i}(X_{i})\leqslant V_{i}(Întreg)/n

Majoritatea protocoalelor pentru tăierea proporțională a torturilor pot fi ușor transferate în împărțirea sarcinilor. De exemplu:

Pentru a utiliza ultimul protocol redus , îi cerem agentului să taie o bucată pe care o evaluează exact . Dacă orice alt agent consideră că această piesă este prea mică, atunci o poate crește până când este exact egală cu el și așa mai departe. „Ultimul crescător” primește o piesă care merită exact pentru el și cel puțin pentru alții. ${\tfrac {1}{n)}$ ${\tfrac {1}{n)}$ ${\tfrac {1}{n)}$ ${\tfrac {1}{n)}$
Pentru a utiliza protocolul Even-Paz, cereți fiecărui agent să marcheze unde crede că este mijlocul (presupunând că toate tăieturile sunt paralele). Tăiem tortul după mediana acestor semne (adică la mijlocul acestora), împărțim agenții în două grupuri de agenți și continuăm împărțirea recursiv pentru fiecare jumătate, fiecare participant împărțind jumătatea care nu conține marca sa. . ${\tfrac {n}{2))$

Împărțirea echitabilă și precisă a sarcinilor

Procedurile de împărțire corectă și exactă funcționează la fel de bine pentru tăierea prăjiturii și împărțirea sarcinilor, deoarece garantează aceleași valori. Un exemplu este procedura „Moving Knife” a lui Austin , care asigură că fiecare participant primește o piesă care este evaluată exact în estimarea completă a resursei. ${\tfrac {1}{n)}$

Distribuirea invidioasă a taxelor

Definiția lipsei de invidie în împărțirea sarcinilor este o imagine în oglindă a definiției pentru împărțirea tortului - fiecare participant trebuie să primească o parte , care este estimată de el, conform propriei evaluări personale a nivelului de neplăcut, ca mai mic sau egal cu orice altă parte: $i$ $X_{i}$

\forall i,j:V_{i}(X_{i})\leqslant V_{i}(X_{j})

Pentru doi participanți, procedura de împărțire și alegere are ca rezultat o împărțire a sarcinilor fără invidie. Cu toate acestea, pentru trei sau mai mulți participanți, situația este mai complicată. Principala dificultate este trunchierea - acțiunea asupra unei bucăți de tort pentru a o face egală ca valoare cu o altă bucată (cum se face, de exemplu, în procedura Selfridge-Conway ). Această acțiune nu poate fi ușor transferată într-un scenariu de împărțire a sarcinilor.

Procedura Oskui discretă pentru trei participanți

Reza Oskui a fost primul care a propus o procedură de împărțire a sarcinilor pentru trei participanți. Lucrarea sa nu a fost niciodată publicată oficial și este menționată doar în lucrarea lui Robertson și Webb [2] . Protocolul este similar cu protocolul Selfridge-Conway, dar este mai complex - necesită 9 incizii în loc de 5 incizii.

Mai jos, Alice, Bob și Carl iau parte la divizie.

Primul pas. Alice împarte lucrarea în trei părți egale în ochii ei (acesta este și primul pas în protocolul Selfridge-Conway). Bob și Carl indică cele mai mici piese (în opinia lor). Un caz simplu ar fi atunci când ei indică acțiuni diferite, pentru că atunci putem oferi fiecărui participant cea mai mică cotă (după părerea lui) și am făcut o împărțire. Cazul dificil este atunci când indică aceeași cotă. Să notăm partea de lucru pe care atât Bob, cât și Carl o consideră cea mai mică ca X1, iar celelalte două piese ca X2 și X3.

Al doilea pas. Cereți-i lui Bob și Carl să marcheze pe fiecare piesă X2 și X3 unde să le decupeze pentru a le face egale cu X1. Să luăm în considerare mai multe cazuri.

Cazul 1. Volumul pe care Bob îl taie este mai mic. Adică, Bob taie de la X2 la X2' și de la X3 la X3', astfel încât atât X2' cât și X3', după părerea lui, sunt la fel cu X1, iar Carl crede că X1 rămâne cea mai mică parte, nu mai mult de X2’ și X3’. Atunci următoarea diviziune este fără invidie:

Carl primește X1;
Alice devine cel mai mic dintre X2’ și X3’ (ambele părți sunt mai mici decât X1 în ochii ei);
Bob primește piesa pe care Alice nu a luat-o (ambele piese sunt egale cu X1 pentru el).

Acum trebuie să separăm părțile tăiate de X2 și X3. Pentru fiecare bucată tăiată, procedați după cum urmează:

Bob le împarte în trei părți egale;
Participanții aleg părțile în această ordine: Carl, Alice, Bob.

Carl nu mai este gelos așa cum alege el primul. Bob nu este gelos pentru că a tăiat. Alice nu este geloasă pentru că are un avantaj (negativ) față de Carl - la primul pas Carl a ales X1 în timp ce Alice a luat o piesă care este mai mică decât X1, în timp ce în ultimul pas Alice a luat o piesă care nu este mai rea ( X2+X3 )/2.

Cazul 2. Volumul pe care Carl îl taie este mai mic. Adică, dacă Karl oprește de la X2 la X2' și de la X3 la X3' în așa fel încât atât X2' cât și X3' să fie la fel de mici pentru el ca X1, atunci Bob încă crede că X1 este cel mai mic, nu mai mult. decât X2' şi X3'. Apoi procedăm în același mod ca în cazul 1, schimbând rolurile lui Bob și Carl.

Cazul 3. Volumul pe care Bob îl taie este mai mic pentru X2, iar volumul pe care Carl îl taie este mai mic pentru X3. Adică, dacă după ce Bob taie din bucata X2, rezultă X2', care în ochii lui este egal cu piesa X1, iar Karl primește după tăierea piesei X3, bucata X3', care în ochii lui este egală cu X1, atunci:

pentru Carl: $X2'\geqslant X1=X3'$
pentru Bob: $X3'\geqslant X1=X2'$

Atunci următoarea diviziune parțială nu are invidie:

Alice devine cel mai mic dintre X2' și X3' (pentru ea ambele părți sunt mai mici decât X1);
Bob primește fie X2’ (dacă Alice nu a luat această parte) fie X1 (în caz contrar);
Carl primește fie partea X3’ (dacă Alice nu a luat-o), fie X1 (altfel).

Părțile tăiate X2 și X3 sunt împărțite în mod similar cu cazul 1.

Oskui a arătat, de asemenea, cum să transforme următoarele rutine de cuțit în mișcare de la tăierea prăjiturii într-o împărțire a sarcinilor:

Procedura „Moving Knife” a lui Stromquist ;
procedura cuțitului rotativ [3] .

Procedura continuă a lui Peterson și Su pentru trei și patru participanți

Peterson și Su [4] au propus o procedură diferită pentru trei participanți. Este mai simplu și mai simetric decât procedura Oskui, dar nu este discretă deoarece se bazează pe procedura cuțitului în mișcare. Ideea principală a acestei proceduri este de a împărți responsabilitățile în șase părți și de a oferi fiecărui participant două piese, pe care le consideră a fi mai puține decât părțile primite de ceilalți participanți.

Primul pas. Împărțim munca în 3 părți folosind orice metodă de tăiere a tortului care garantează absența invidiei și dăm fiecare piesă jucătorului care o consideră cea mai mare.

Al doilea pas.

Folosind procedura „Moving Knife” a lui Austin, împărțim piesa 1 în două părți, pe care participanții 1 și 2 le consideră la fel. Lăsați participantul 3 să aleagă partea care este mai mică în ochii lui și dă restul participantului 2.
În mod similar, împărțim piesa 2 în două părți, pe care participanții 2 și 3 le consideră egale, și lăsăm participantul 1 să aleagă cea mai mică dintre cele două părți și să dăm partea rămasă participantului 3.
În mod similar, împărțim piesa 3 în două părți, pe care participanții 3 și 1 le consideră egale, și lăsăm participantul 2 să aleagă cea mai mică dintre cele două părți și să dăm partea rămasă participantului 1.

Analiză. Participantul 1 are două bucăți tăiate, una din piesa 2 și una din piesa 3. În ochii participantului 1, partea piesei 2 este mai mică decât partea dată participantului 3, iar partea piesei 3 este mai mică decât partea dat participantului 2. Mai mult, ambele aceste piese tăiate sunt mai mici decât bucățile piesei 1, deoarece piesa 1 este mai mare decât piesa 2 și piesa 3 (conform primului pas). Prin urmare, participantul 1 consideră că cota sa nu este mai mult decât fiecare dintre celelalte două părți. Același raționament se aplică participanților 2 și 3. Prin urmare, într-o astfel de diviziune nu va exista invidie.

Peterson și Su și-au extins procedura continuă la patru participanți [4] .

Procedura discretă a lui Peterson și Su pentru orice număr de participanți

Existența unei proceduri discrete pentru cinci sau mai mulți participanți a rămas o întrebare deschisă până în 2009, când Peterson și Su au publicat o procedură pentru n participanți [5] . Procedura este similară cu procedura Brahms-Taylor și folosește aceeași idee de avantaj inerent . În loc să întrerupă, au folosit un adaos din rezervă .

Procedura discretă și restrânsă Dehghani cu co-autori pentru orice număr de participanți

Peterson și Su au introdus o procedură de „cuțit în mișcare” pentru împărțirea sarcinilor pentru 4 persoane. Dehghani și colaboratorii [6] au dat primul protocol restrâns discret pentru împărțirea sarcinilor fără invidie între un număr mare de agenți.

Proceduri pentru piesele conectate

Următoarele proceduri pot fi transferate pentru a împărți tortul prost (adică, responsabilitățile) cu bucățile deconectate:

Procedura „Moving Knife” a lui Robertson-Webb [7] ;
Procedura Stromquist's Moving Knife [8] ;
Protocoale Simmons-Su . Simmons a dezvoltat inițial un protocol pentru distribuirea aproximativă a prăjiturii fără invidie cu piese conectate, bazat pe Lema lui Sperner . Su a arătat, folosind lema duală, că un protocol similar ar putea fi folosit pentru o împărțire aproximativă a sarcinilor fără invidie. În special, el a arătat că există întotdeauna o împărțire a sarcinilor fără invidie cu bucăți coerente.

Prețul justiției

Heydrich și Stee [9] au calculat costul echității în împărțirea sarcinilor în cazul în care părțile trebuie conectate.

Aplicații

Împărțirea sarcinilor poate fi folosită pentru a împărți munca și costurile țărilor pentru atenuarea schimbărilor climatice . Problemele sunt legate de aspecte morale și de nevoia de cooperare a națiunilor. Cu toate acestea, utilizarea unei proceduri de împărțire a sarcinilor reduce necesitatea unei autorități supranaționale de a diviza și de a supraveghea munca acestor națiuni [10] .

O altă utilizare a procedurii de împărțire a sarcinilor poate fi problema împărțirii unui apartament .

Vezi și

Tăierea geloasă a tortului

Note

↑ Gardner, 1978 .
↑ Robertson, Webb, 1998 , p. 73–75.
↑ Robertson, Webb, 1998 , p. 77–78.
↑ 12 Peterson , Su, 2002 , p. 117–122.
^ Peterson, Su, 2009 .
↑ Dehghani, Farhadi, Hajiaghayi, Yami, 2018 , p. 2564–2583.
↑ Robertson, Webb, 1998 , p. exercițiul 5.10.
↑ Robertson, Webb, 1998 , p. exercițiul 5.11.
↑ Heydrich, Van Stee, 2015 , p. 51–61.
↑ Traxler, 2002 , p. 101–134.

Literatură

Martin Gardner. Aha! perspicacitate . - New York: WF Freeman and Co., 1978. - ISBN 978-0-7167-1017-2 .
Jack Robertson, William Webb. Algoritmi de tăiere a prăjiturii: fiți corect dacă puteți. - Natick, Massachusetts: A.K. Peters, 1998. - ISBN 978-1-56881-076-8 .
Elisha Peterson, Francis Edward Su. Divizia de treburi fără invidie pentru patru persoane // Revista de matematică. - 2002. - T. 75 , nr. 2 . - doi : 10.2307/3219145 . — .
Elisha Peterson, Francis Edward Su. Diviziune de corvoadă fără invidie pentru N persoane . — 2009.
Sina Dehghani, Alireza Farhadi, Mohammad Taghi Hajiaghayi, Hadi Yami. Divizia de treburi fără invidie pentru un număr arbitrar de agenți. - Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018. - doi : 10.1137/1.9781611975031.164 .
Sandy Heydrich, Rob Van Stee. Împărțirea corectă a treburilor conectate (engleză) // Informatică teoretică. - 2015. - Vol. 593 . - doi : 10.1016/j.tcs.2015.05.041 .
Martin Traxler. Fair Chore Division pentru schimbări climatice // Teorie și practică socială. - 2002. - T. 28 , nr. 1 . - doi : 10.5840/soctheorpract20022814 . — .