Opgavefordeling

Opdelingen af opgaver eller ubehageligt, snavset arbejde ( eng. Chore division , bogstaveligt talt - rutine, pligt) er en retfærdig delingsopgave , hvor den ressourcekrævende opdeling er uønsket, så alle, der deltager i divisionen, ønsker at få så lidt af dette ressource som muligt.

Generel diskussion af problemet

Problemet er et spejlbillede af fair kageskæringsproblemet , hvor den delbare ressource er ønskelig, så deltagerne i divisionen ønsker at få så meget som muligt. Både den første og anden opgave har heterogene ressourcer. Ved opdeling af en kage kan kagen eksempelvis have ende-, hjørne- og midterstykker med forskelligt glasurindhold. Ved opdeling af ansvar for et job, kan der være forskellige typer af ansvar og forskellige mængder af tid til at fuldføre hvert job. Begge opgaver forudsætter, at ressourcer kan deles. Typer af værker kan opdeles i det uendelige, da det endelige sæt af værker kan opdeles i forskellige typer, formater og tage forskellige tider at færdiggøre dem. For eksempel kan en fyldning i en vaskemaskine divideres med antallet af beklædningsgenstande og den tid, det tager at fylde maskinen. Opgaverne er dog forskellige med hensyn til ressourcens ønskelighed. Opgavefordelingsproblemet blev foreslået af Martin Gardner i 1978 [1] .

Tolddeling omtales ofte som en retfærdig deling af anti -varer i modsætning til det mere velkendte problem med "fair deling af varer". Et andet navn er beskidte arbejde problem . Den samme ressource kan være god eller dårlig afhængig af situationen. Antag for eksempel, at den ressource, der skal deles, er baghaven til et hus. I en situation med arvedeling kan denne gård være en velsignelse, da hver arving ønsker at få så meget jord som muligt, som i kagens opdeling. Men i tilfælde af at dele uønskede jobs, såsom græsslåning , kan denne have allerede betragtes som en anti-boon, da de fleste mennesker gerne vil bruge så lidt tid som muligt på husarbejde, så det er allerede en opgave at dele pligter .

Nogle af resultaterne fra fair kageskæringsproblemet kan ganske enkelt overføres til opgavefordelingsscenariet. For eksempel fungerer opdel-og-vælg- proceduren lige godt til begge opgaver - den ene af deltagerne deler ressourcen op i lige dele efter hans mening, og den anden vælger den del, der efter hans mening er "bedre". Forskellen ligger kun i betydningen af ordet "bedre" - om det betyder "mere", som i kagens opdeling, eller om det betyder "mindre", som i opgavefordelingen. Det er dog ikke alle resultater, der er så lette at overføre. Mere detaljerede forklaringer er givet nedenfor.

Forholdsmæssig opgavefordeling

Definitionen af fordeling for pligtdeling er et spejlbillede af det analoge udtryk for at skære kagen - hver deltager skal modtage en worst-case andel i henhold til deres egen uønskede funktion, ikke mere end den fulde værdi (hvor lig med det samlede antal ) af deltagere): $jeg$ $X_{i}$ ${\tfrac {1}{n))$ $n$

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

De fleste af protokollerne for proportional kageskæring kan nemt overføres til opgavefordelingen. For eksempel:

For at bruge den sidste reducerede protokol beder vi agenten om at skære et stykke af, som han vurderer til nøjagtigt . Hvis en anden agent føler, at dette stykke er for lille, så kan han øge det, indtil det er nøjagtigt det samme som ham, og så videre. Den "sidste forøger" får et stykke, der er værd præcis for ham og i hvert fald for andre. ${\tfrac {1}{n))$ ${\tfrac {1}{n))$ ${\tfrac {1}{n))$ ${\tfrac {1}{n))$
For at bruge Even-Paz-protokollen skal du bede hver agent om at markere, hvor de mener, at midten er (forudsat at alle snit er parallelle). Vi skærer kagen med medianen af disse mærker (det vil sige i midten af dem), deler agenterne i to grupper af agenter og fortsætter opdelingen rekursivt for hver halvdel, hvor hver deltager deler den halvdel, der ikke indeholder hans mærke. . ${\tfrac {n}{2))$

Retfærdig og præcis opgavefordeling

De retfærdige og nøjagtige opdelingsprocedurer fungerer lige godt til kageskæring og opgavefordeling, fordi de garanterer de samme værdier. Et eksempel er Austins "Moving Knife"-procedure , som sikrer, at hver deltager får en brik, der er værdsat nøjagtigt i ressourcens fulde estimat. ${\tfrac {1}{n))$

Misundelig fordeling af pligter

Definitionen af ingen misundelse i opgavefordelingen er et spejlbillede af definitionen for kagens opdeling - hver deltager skal modtage en del , som vurderes af ham, i henhold til hans egen personlige vurdering af niveauet af ubehageligheder, som mindre end eller lig med enhver anden del: $jeg$ $X_{i}$

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

For to deltagere resulterer del -og-vælg- proceduren i en opgavefordeling uden misundelse. For tre eller flere deltagere er situationen dog mere kompliceret. Den største vanskelighed er trunkering - handlingen på et stykke kage for at gøre det lige i værdi med et andet stykke (som det f.eks. gøres i Selfridge-Conway-proceduren ). Denne handling kan ikke uden videre overføres til en opgavefordeling.

Diskret Oskui-procedure for tre deltagere

Reza Oskui var den første til at foreslå en procedure for opgavefordelingen for tre deltagere. Hans arbejde er aldrig blevet formelt offentliggjort og er kun nævnt i Robertsons og Webbs arbejde [2] . Protokollen ligner Selfridge-Conway-protokollen, men er mere kompleks - den kræver 9 snit i stedet for 5 snit.

Herunder deltager Alice, Bob og Carl i divisionen.

Første skridt. Alice deler værket i tre lige store dele i hendes øjne (dette er også det første trin i Selfridge-Conway-protokollen). Bob og Carl peger på de mindste stykker (efter deres mening). Et simpelt tilfælde ville være, når de peger på forskellige andele, for så kan vi give hver deltager den mindste (efter hans mening) andel, og vi lavede en opdeling. Den svære sag er, når de peger på den samme andel. Lad os betegne den del af værket, som både Bob og Carl betragter som den mindste som X1, og de to andre stykker som X2 og X3.

Andet trin. Bed Bob og Carl om at markere på hvert stykke X2 og X3, hvor de skal afskæres fra dem for at gøre dem lig med X1. Lad os overveje flere tilfælde.

Tilfælde 1. Den lydstyrke, som Bob afskærer, er mindre. Det vil sige, at Bob skærer fra X2 til X2', og fra X3 til X3', så både X2' og X3' efter hans mening er det samme som X1, og Carl mener, at X1 forbliver den mindste del, ikke mere end X2' og X3'. Så er følgende opdeling misundelsesfri:

Carl modtager X1;
Alice får den mindste af X2' og X3' (begge dele er mindre end X1 i hendes øjne);
Bob får den brik, som Alice ikke tog (begge brikker er lig med X1 for ham).

Nu skal vi adskille de afskårne dele fra X2 og X3. For hvert skåret stykke skal du gøre følgende:

Bob deler dem i tre lige store dele;
Deltagerne vælger dele i denne rækkefølge: Carl, Alice, Bob.

Carl er ikke længere jaloux, som han vælger først. Bob er ikke jaloux, fordi han skar. Alice er ikke jaloux, fordi hun har en (negativ) fordel i forhold til Carl - i første trin valgte Carl X1, mens Alice tog en brik, der er mindre end X1, mens Alice i sidste trin tog en brik, der ikke er værre ( X2+X3 )/2.

Tilfælde 2. Det volumen Carl skærer af er mindre. Det vil sige, at hvis Karl afskærer fra X2 til X2' og fra X3 til X3' på en sådan måde, at både X2' og X3' er lige så små for ham som X1, så synes Bob stadig, at X1 er den mindste, ikke mere end X2' og X3'. Derefter fortsætter vi på samme måde som i case 1, og skifter rollerne som Bob og Carl.

Tilfælde 3. Den lydstyrke, som Bob afskærer, er mindre for X2, og den lydstyrke, som Carl afskærer, er mindre for X3. Det vil sige, hvis det efter Bob har klippet stykke X2 af, viser sig X2', som i hans øjne er lig med stykke X1, og Karl modtager efter at have klippet stykke X3 af, stykke X3', som i hans øjne er lig med X1, derefter:

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

Så er den følgende delvise opdeling ingen misundelse:

Alice får den mindste af X2' og X3' (for hende er begge dele mindre end X1);
Bob modtager enten X2' (hvis Alice ikke tog denne del) eller X1 (ellers);
Carl får enten del X3' (hvis Alice ikke tog den) eller X1 (ellers).

De afskårne dele X2 og X3 er opdelt på samme måde som tilfælde 1.

Oskui viste også, hvordan man forvandler følgende flyttekniv-rutiner fra kageskæring til en opdeling af opgaver:

Stromquists "Moving Knife" procedure ;
roterende kniv procedure [3] .

Kontinuerlig procedure for Peterson og Su for tre og fire deltagere

Peterson og Su [4] foreslog en anden procedure for tre deltagere. Den er enklere og mere symmetrisk end Oskui-proceduren, men den er ikke diskret, fordi den er afhængig af den bevægelige kniv-procedure. Hovedideen med denne procedure er at opdele ansvaret i seks dele og give hver deltager to stykker, som de anser for at være mindre end de dele, som andre deltagere har modtaget.

Første skridt. Vi opdeler arbejdet i 3 dele ved at bruge en hvilken som helst metode til at skære kagen på, der garanterer fraværet af misundelse, og giver hver brik til den spiller, der anser den for den største.

Andet trin.

Ved at bruge Austins "Moving Knife"-procedure deler vi stykke 1 i to dele, som deltager 1 og 2 betragter som ens. Lad deltager 3 vælge den del, der er mindre i hans øjne, og giv resten til deltager 2.
På samme måde deler vi stykke 2 op i to dele, som deltager 2 og 3 betragter som lige, og lader deltager 1 vælge den mindste af de to dele, og giver den resterende del til deltager 3.
På samme måde deler vi stykke 3 i to dele, som deltager 3 og 1 anser for lige, og lader deltager 2 vælge den mindste af de to dele, og giver den resterende del til deltager 1.

Analyse. Deltager 1 har to udskårne stykker, en fra brik 2 og en fra brik 3. I deltager 1's øjne er delen af brik 2 mindre end delen givet til deltager 3, og delen af brik 3 er mindre end delen givet til deltager 2. Desuden er begge disse afskårne stykker mindre end stykkerne i stykke 1, da stykke 1 er større end både stykke 2 og stykke 3 (ifølge det første trin). Derfor mener deltager 1, at hans andel ikke er mere end hver af de to andre andele. Det samme ræsonnement gælder for deltager 2 og 3. Derfor vil der i en sådan opdeling ikke være misundelse.

Peterson og Su udvidede deres kontinuerlige procedure til fire deltagere [4] .

Diskret procedure for Peterson og Su for et hvilket som helst antal deltagere

Eksistensen af en diskret procedure for fem eller flere deltagere forblev et åbent spørgsmål indtil 2009, hvor Peterson og Su offentliggjorde en procedure for n deltagere [5] . Proceduren ligner Brahms-Taylor-proceduren og bruger den samme idé om iboende fordel . I stedet for at afskære brugte de en tilføjelse fra reserven .

Diskret og begrænset procedure Dehghani med medforfattere for et vilkårligt antal deltagere

Peterson og Su indførte en "bevægelig kniv"-procedure for at opdele opgaver for 4 personer. Dehghani et al . [6] gav den første diskrete begrænsede protokol til opdeling af opgaver uden misundelse blandt et vilkårligt antal agenter.

Procedurer for tilsluttede stykker

Følgende procedurer kan overføres for at dele den dårlige kage (dvs. ansvar) med afbrudte stykker:

Robertson-Webbs "Moving Knife"-procedure [7] ;
Stromquists Moving Knife procedure [8] ;
Simmons-Su protokoller . Simmons udviklede oprindeligt en protokol til omtrentlig misundelsesfri kagedeling med forbundne stykker baseret på Sperners Lemma . Su viste ved hjælp af det dobbelte lemma, at en lignende protokol kunne bruges til en omtrentlig fordeling af opgaver uden misundelse. Især viste han, at der altid er en opgavefordeling uden misundelse med sammenhængende bidder.

Prisen på retfærdighed

Heydrich og Stee [9] beregnede omkostningerne ved retfærdighed i opgavefordelingen, hvis delene skal forbindes.

Ansøgninger

Deling af pligter kan bruges til at dele landes arbejde og omkostninger for at afbøde klimaændringer . Problemerne er relateret til moralske aspekter og behovet for samarbejde mellem nationer. Brugen af en pligtdelingsprocedure reducerer imidlertid behovet for en overnational myndighed til at opdele og føre tilsyn med disse nationers arbejde [10] .

En anden anvendelse af arbejdsdelingsproceduren kan være problemet med at dele en lejlighed .

Se også

Jaloux udskæring af kagen

Noter

↑ Gardner, 1978 .
↑ Robertson, Webb, 1998 , s. 73-75.
↑ Robertson, Webb, 1998 , s. 77-78.
↑ 12 Peterson , Su, 2002 , s. 117-122.
↑ Peterson, Su, 2009 .
↑ Dehghani, Farhadi, Hajiaghayi, Yami, 2018 , s. 2564-2583.
↑ Robertson, Webb, 1998 , s. øvelse 5.10.
↑ Robertson, Webb, 1998 , s. øvelse 5.11.
↑ Heydrich, Van Stee, 2015 , s. 51-61.
↑ Traxler, 2002 , s. 101-134.

Litteratur

Martin Gardner. aha! indsigt . - New York: WF Freeman og Co., 1978. - ISBN 978-0-7167-1017-2 .
Jack Robertson, William Webb. Kage-skæringsalgoritmer: Vær fair, hvis du kan. - Natick, Massachusetts: A.K. Peters, 1998. - ISBN 978-1-56881-076-8 .
Elisha Peterson, Francis Edward Su. Fire-personers misundelsesfri opgaveafdeling // Mathematics Magazine. - 2002. - T. 75 , no. 2 . - doi : 10.2307/3219145 . — .
Elisha Peterson, Francis Edward Su. N-person misundelsesfri pligtopdeling . – 2009.
Sina Dehghani, Alireza Farhadi, Mohammad Taghi Hajiaghayi, Hadi Yami. Misundelsesfri opgaveafdeling for et vilkårligt antal agenter. - Proceedings of the Twenty-nith Annual ACM-SIAM Symposium on Discrete Algorithms, 2018. - doi : 10.1137/1.9781611975031.164 .
Sandy Heydrich, Rob Van Stee. Opdele forbundne gøremål retfærdigt (engelsk) // Teoretisk datalogi. - 2015. - Bd. 593 . - doi : 10.1016/j.tcs.2015.05.041 .
Martin Traxler. Fair Chore Division for Climate Change // Social teori og praksis. - 2002. - T. 28 , no. 1 . - doi : 10.5840/soctheorpract20022814 . — .