Feladatmegosztás

A feladatmegosztás vagy a kellemetlen, piszkos munka ( angol. Chore division , szó szerint - rutin, kötelesség) tisztességes megosztási feladat , amelyben nem kívánatos a megosztást igénylő erőforrás, így ebből mindenki minél kevesebbet szeretne kapni a megosztásban. erőforrást.

A probléma általános megvitatása

A probléma a méltányos tortavágási probléma tükörképe , amelyben az osztható forrás kívánatos, hogy a felosztásban résztvevők minél többet akarjanak kapni. Mind az első, mind a második feladat heterogén rendelkezik . Egy torta felosztásánál például a tortának lehetnek végei, sarkai és középső részei, különböző cukormáztartalommal. A munkaköri feladatok megosztása során különböző típusú felelősségek lehetnek, és az egyes munkák elvégzéséhez eltérő idő áll rendelkezésre. Mindkét feladat feltételezi, hogy az erőforrások megoszthatók. A munkatípusok korlátlanul feloszthatók, hiszen a végleges művek különböző típusokra, formátumokra bonthatók, és ezek elkészítése eltérő időbe telik. Például a mosógépbe tett töltet elosztható a ruhadarabok számával és a mosógép betöltéséhez szükséges idővel. A feladatok azonban különböznek az erőforrás kívánatosságában. A feladatmegosztási problémát Martin Gardner javasolta 1978-ban [1] .

A vámok megosztását gyakran az áruellenes termékek méltányos megosztásának nevezik, szemben az ismertebb "fair share" problémával. Egy másik név a piszkos munka problémája . Ugyanaz az erőforrás a helyzettől függően lehet jó vagy rossz. Tegyük fel például, hogy a megosztandó erőforrás egy ház hátsó udvara. Örökségmegosztás esetén ez az udvar jótékony hatású lehet, hiszen minden örökös a lehető legtöbb földhöz szeretne jutni, mint a tortaosztásnál. De a nemkívánatos munkák megosztása esetén, mint például a fűnyírás , ez az udvar már szerencsétlenségnek számít, hiszen a legtöbben a lehető legkevesebb időt szeretnének a házimunkára fordítani, így ez már a feladatmegosztás feladata. .

A méltányos tortavágási probléma egyes eredményei egyszerűen átvihetők a feladatmegosztási forgatókönyvbe. Például az oszd meg és válassz eljárás mindkét feladatnál egyformán jól működik - az egyik résztvevő véleménye szerint egyenlő részekre osztja az erőforrást, a másik pedig azt a részt választja, amely szerinte "jobb". A különbség csak a „jobb” szó jelentésében van – hogy „többet” jelent-e, mint a torta felosztásában, vagy „kevesebbet”, mint a feladatok megosztásában. Azonban nem minden eredmény átvihető ilyen könnyen. A részletesebb magyarázatok alább találhatók.

Arányos feladatmegosztás

A feladatok megosztásának definíciója a tortavágás analóg kifejezésének tükörképe – minden résztvevőnek saját nemkívánatossági függvénye szerint kell kapnia a legrosszabb esetből származó részesedést, legfeljebb a teljes értéknél (ahol egyenlő a teljes számmal résztvevők közül): $én$ $X_{i}$ ${\tfrac {1}{n))$ $n$

\forall i:V_{i}(X_{i})\leqslant V_{i}(egész)/n

Az arányos tortavágásra vonatkozó protokollok többsége könnyen átvihető a feladatmegosztásba. Például:

Az utoljára redukált protokoll használatához megkérjük az ügynököt, hogy vágjon le egy olyan darabot, amelyet pontosan értékel ki . Ha bármely más ügynök úgy érzi, hogy ez a darab túl kicsi, akkor növelheti, amíg pontosan megegyezik vele, és így tovább. Az "utolsó növelő" olyan darabot kap, ami pontosan neki és legalább másoknak is megéri. ${\tfrac {1}{n))$ ${\tfrac {1}{n))$ ${\tfrac {1}{n))$ ${\tfrac {1}{n))$
Az Even-Paz protokoll használatához kérjen meg minden ügynököt, hogy jelölje meg, hol van a középpont (feltételezve, hogy minden vágás párhuzamos). A tortát ezeknek a jeleknek a mediánjával (vagyis a közepével) felvágjuk, az ágenseket két ügynökcsoportra osztjuk, és rekurzív módon folytatjuk a felosztást mindkét felére úgy, hogy minden résztvevő elosztja azt a felét, amelyik nem tartalmazza a jegyét. . ${\tfrac {n}{2))$

Méltányos és pontos feladatmegosztás

A méltányos és pontos felosztási eljárások egyformán jól működnek a tortavágásnál és a feladatmegosztásnál, mert ugyanazokat az értékeket garantálják. Példa erre Austin „Moving Knife” eljárása , amely biztosítja, hogy minden résztvevő olyan darabot kapjon, amelynek értéke pontosan az erőforrás teljes becslésében szerepel. ${\tfrac {1}{n))$

Irigy feladatmegosztás

A nem irigység definíciója a feladatmegosztásban a tortamegosztás definíciójának tükörképe – minden résztvevőnek egy részt kell kapnia , amelyet saját maga becsül meg a kellemetlenség mértékére vonatkozó személyes értékelése szerint, mivel kisebb vagy egyenlő bármely más résznél: $én$ $X_{i}$

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

Két résztvevő esetében az oszd meg és válassz eljárás a feladatok irigység nélküli megosztását eredményezi. Három vagy több résztvevő esetében azonban a helyzet bonyolultabb. A fő nehézség a csonkítás – a tortán végzett művelet, hogy az értéke egyenlő legyen egy másik darabbal (ahogyan ez például a Selfridge-Conway eljárásban történik ). Ezt a műveletet nem lehet könnyen átvinni egy feladatmegosztási forgatókönyvbe.

Diszkrét Oskui eljárás három résztvevő számára

Reza Oskui volt az első, aki három résztvevő feladatmegosztási eljárását javasolta. Munkáját hivatalosan soha nem adták ki, és csak Robertson és Webb [2] munkái említik . A protokoll hasonló a Selfridge-Conway protokollhoz , de bonyolultabb – 5 bemetszés helyett 9 bemetszést igényel.

Alice, Bob és Carl részt vesz a felosztásban.

Első lépés. Alice a szemében három egyenlő részre osztja a művet (ez egyben a Selfridge-Conway protokoll első lépése is). Bob és Carl a legkisebb darabokra mutat (szerintük). Egy egyszerű eset lenne, ha különböző részesedésekre mutatnak, mert akkor minden résztvevőnek megadhatjuk a legkisebb (szerinte) részesedést, és felosztást csináltunk. A nehéz eset az, amikor ugyanarra a részesedésre mutatnak. Jelöljük a munka azon részét, amelyet Bob és Carl is X1-nek, a másik két darabot pedig X2-nek és X3-nak tekinti.

Második lépés. Kérd meg Bobot és Carlt, hogy jelöljék meg minden X2 és X3 darabon, hogy hol kell levágni őket, hogy egyenlők legyenek X1-gyel. Nézzünk meg több esetet.

1. eset. A Bob által levágott hangerő kisebb. Vagyis Bob X2-ről X2'-re, X3-ról X3-ra vág, így véleménye szerint mind az X2', mind az X3' ugyanaz, mint az X1, és Carl úgy gondolja, hogy X1 marad a legkisebb rész, legfeljebb X2' és X3'. Akkor irigységmentes a következő felosztás:

Carl X1-et kap;
Alice X2' és X3' közül a kisebbet kapja (mindkét rész kisebb, mint X1 a szemében);
Bob megkapja azt a darabot, amelyet Alice nem vett el (nála mindkét darab egyenlő X1-gyel).

Most szét kell választani az X2-ből és X3-ból levágott részeket. Minden vágott darabnál tegye a következőket:

Bob három egyenlő részre osztja őket;
A résztvevők a következő sorrendben választják ki a részeket: Carl, Alice, Bob.

Carl már nem féltékeny, mivel ő választ először. Bob nem féltékeny, mert vágott. Alice nem féltékeny, mert (negatív) előnye van Carlhoz képest – Carl az első lépésben az X1-et választotta, míg Alice egy X1-nél kisebb darabot vett, míg az utolsó lépésben Alice nem rosszabbat ( X2+X3 )/2.

2. eset. A Carl által levágott hangerő kisebb. Vagyis ha Karl úgy vág le X2-ről X2'-re és X3-ról X3'-ra, hogy X2' és X3' is olyan kicsi neki, mint X1, akkor Bob továbbra is úgy gondolja, hogy X1 a legkicsibb, nem több. mint X2' és X3'. Ezután ugyanúgy járunk el, mint az 1. esetben, megváltoztatva Bob és Carl szerepét.

3. eset. A Bob által levágott hangerő X2 esetén kisebb, és a Carl által levágott hangerő kisebb X3 esetén. Azaz, ha miután Bob levágott az X2 darabról, kiderül X2', ami az ő szemében egyenlő az X1 darabbal, és Karl az X3 darab levágása után megkapja az X3' darabot, ami az ő szemében egyenlő X1-gyel, akkor:

Carl számára: $X2'\geqslant X1=X3'$
Bob számára: $X3'\geqslant X1=X2'$

Akkor a következő részleges felosztás nem irigykedik:

Alice X2' és X3' közül a kisebbet kapja (neki mindkét rész kisebb, mint X1);
Bob vagy X2'-t kap (ha Alice nem vállalta ezt a részt), vagy X1-et (egyébként);
Carl megkapja az X3' részt (ha Alice nem vette el), vagy az X1-et (egyébként).

Az X2 és X3 levágott részek az 1. esethez hasonlóan vannak felosztva.

Oskui azt is megmutatta, hogyan lehet a következő mozgatható késes rutinokat tortavágásból feladatmegosztássá tenni:

Stromquist „Moving Knife” eljárása ;
forgókés eljárás [3] .

Peterson és Su folyamatos eljárása három és négy résztvevő számára

Peterson és Su [4] eltérő eljárást javasolt három résztvevő számára. Egyszerűbb és szimmetrikusabb, mint az Oskui eljárás, de nem diszkrét, mert a mozgó késes eljárásra támaszkodik. Ennek az eljárásnak a fő gondolata az, hogy a felelősségeket hat részre osztják, és minden résztvevőnek két darabot adnak, amelyet kevesebbnek tartanak, mint a többi résztvevő által kapott rész.

Első lépés. A munkát tetszőleges, az irigység hiányát garantáló tortavágási módszerrel 3 részre osztjuk, és minden darabot annak a játékosnak adunk, aki a legnagyobbnak tartja.

Második lépés.

Az Austin-féle „Moving Knife” eljárást használva az 1. darabot két részre osztjuk, amelyeket az 1. és 2. résztvevő azonosnak tekint. Hagyja, hogy a 3. résztvevő válassza ki a szemében kisebb részt, a többit pedig adja át a 2. résztvevőnek.
Hasonlóképpen a 2. darabot két részre osztjuk, amelyeket a 2. és 3. résztvevő egyenlőnek tekint, és hagyjuk, hogy az 1. résztvevő válassza ki a két rész közül a kisebbet, a fennmaradó részt pedig a 3. résztvevőnek adjuk.
Hasonlóképpen a 3. darabot két részre osztjuk, amelyeket a 3. és az 1. résztvevő egyenlőnek tekint, és hagyjuk, hogy a 2. résztvevő válassza ki a két rész közül a kisebbet, a fennmaradó részt pedig adjuk át az 1. résztvevőnek.

Elemzés. Az 1. résztvevőnek két darabja van, egy a 2. darabból és egy a 3. darabból. Az 1. résztvevő szemében a 2. darab része kisebb, mint a 3. résztvevőnek adott rész, a 3. darab része pedig kisebb, mint a rész. Ezen túlmenően mindkét vágott darab kisebb, mint az 1. darab darabja, mivel az 1. darab nagyobb, mint a 2. és a 3. darab (az első lépés szerint). Ezért az 1. résztvevő úgy gondolja, hogy az ő részesedése nem több, mint a másik két részesedés. Ugyanez az érvelés vonatkozik a 2. és 3. résztvevőre is. Ezért egy ilyen felosztásban nem lesz irigység.

Peterson és Su négy résztvevőre bővítette folyamatos eljárását [4] .

Peterson és Su diszkrét eljárása tetszőleges számú résztvevőre

Az öt vagy több résztvevőre vonatkozó diszkrét eljárás megléte nyitott kérdés maradt 2009-ig, amikor Peterson és Su közzétett egy eljárást n résztvevőre [5] . Az eljárás hasonló a Brahms-Taylor eljáráshoz , és ugyanazt az eredendő előnyt használja . Levágás helyett a tartalékból kiegészítést használtak .

Diszkrét és korlátozott eljárás Dehghani társszerzőkkel tetszőleges számú résztvevő számára

Peterson és Su egy „mozgó késes” eljárást vezetett be a feladatok 4 főre való felosztására. Dehghani és munkatársai [6] adták meg az első diszkrét korlátozott protokollt a feladatok megosztására, tetszőleges számú ügynök közötti irigység nélkül.

Eljárások az összekapcsolt darabokhoz

A következő eljárások átvihetők a rossz torta (azaz a felelősség) megosztására a szétválasztott darabokkal:

Robertson-Webb „Moving Knife” eljárása [7] ;
Stromquist Moving Knife eljárása [8] ;
Simmons-Su protokollok . Simmons eredetileg Sperner lemmája alapján dolgozott ki egy protokollt a hozzávetőlegesen irigységmentes tortamegosztáshoz az összekapcsolt darabokkal . Su a kettős lemmával megmutatta, hogy egy hasonló protokoll használható a feladatok hozzávetőleges megosztására irigység nélkül. Különösen azt mutatta meg, hogy a feladatok mindig irigység nélkül, koherens darabokra oszthatók.

Az igazságosság ára

Heydrich és Stee [9] kiszámította a méltányosság költségét a feladatmegosztásban, ha az alkatrészeket össze kell kötni.

Alkalmazások

A feladatok megosztása felhasználható arra, hogy megosszák az országok munkáját és költségeit az éghajlatváltozás mérséklése érdekében . A problémák az erkölcsi szempontokhoz és a nemzetek együttműködésének szükségességéhez kapcsolódnak. A feladatmegosztási eljárás alkalmazása azonban csökkenti annak szükségességét, hogy egy nemzetek feletti hatóság felosztja és felügyelje e nemzetek munkáját [10] .

A feladatmegosztási eljárás másik felhasználási módja lehet a lakásmegosztás problémája .

Lásd még

Féltékeny tortavágás

Jegyzetek

↑ 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. gyakorlat 5.10.
↑ Robertson, Webb, 1998 , p. gyakorlat 5.11.
↑ Heydrich, Van Stee, 2015 , p. 51–61.
↑ Traxler, 2002 , p. 101–134.

Irodalom

Martin Gardner. aha! belátás . - New York: WF Freeman and Co., 1978. - ISBN 978-0-7167-1017-2 .
Jack Robertson, William Webb. Tortavágási algoritmusok: Legyen igazságos, ha tud. - Natick, Massachusetts: A.K. Peters, 1998. - ISBN 978-1-56881-076-8 .
Elisha Peterson, Francis Edward Su. Négyfős irigységmentes házimunkák osztály // Mathematics Magazine. - 2002. - T. 75 , sz. 2 . - doi : 10.2307/3219145 . — .
Elisha Peterson, Francis Edward Su. N-személyes irigységmentes házimunkák felosztása . – 2009.
Sina Dehghani, Alireza Farhadi, Mohammad Taghi Hajiaghayi, Hadi Yami. Irigységmentes házimunkák osztály tetszőleges számú ügynök számára. - Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018. - doi : 10.1137/1.9781611975031.164 .
Sandy Heydrich, Rob Van Stee. A kapcsolódó házimunkák igazságos felosztása (angol) // Theoretical Computer Science. - 2015. - Kt. 593 . - doi : 10.1016/j.tcs.2015.05.041 .
Martin Traxler. Fair Chore Division for Climate Change // Társadalomelmélet és gyakorlat. - 2002. - T. 28 , sz. 1 . - doi : 10.5840/soctheorpract20022814 . — .