Procedura wykresu zazdrości

Procedura wykresu zazdrości (zwana także procedurą cyklu zazdrości ) jest procedurą sprawiedliwego przydziału pozycji . Może być używany przez kilka osób, które chcą podzielić między siebie kilka dyskretnych przedmiotów, takich jak pamiątki, słodycze lub miejsca w klasie.

Idealnie chcielibyśmy, aby alokacja była wolna od zazdrości (EF). tj. dać każdemu agentowi pakiet, który on/ona woli od pakietów wszystkich innych agentów. Jednak przedmioty są dyskretne i nie można ich ciąć, więc przydział bez zazdrości może być niemożliwy (na przykład rozważ jeden przedmiot i dwóch agentów). Procedura wykresu zazdrości ma na celu osiągnięcie opcji „kolejnej najlepszej” - braku zazdrości co najwyżej do jednego dobra (EF1): znajduje alokację, w której zazdrość każdej osoby wobec każdej innej osoby jest ograniczona przez maksymalną użyteczność krańcową, jaką czerpie z pojedynczego przedmiotu. Innymi słowy, na każde dwie osoby i oraz j istnieje taka pozycja, że jeśli ją usuniemy, i nie zazdrości j .

Procedura została przedstawiona przez Liptona i Markakisa oraz Mossela i Saberi, a także została opisana w .

Założenia

Procedura wykresu zazdrości zakłada, że każda osoba ma kardynalną funkcję użyteczności na wiązkach przedmiotów. Ta funkcja użyteczności musi być monotoniczna (użyteczność zbioru jest co najmniej tak duża, jak użyteczność jego podzbiorów). Nie musi to być jednak dodatek. Oznacza to, że nie zakłada się, że przedmioty są dobrami niezależnymi .

Agenci nie muszą faktycznie zgłaszać swojej użyteczności kardynalnej: wystarczy, że wiedzą, jak uszeregować pakiety.

Procedura

Zamów przedmioty dowolnie.
Podczas gdy istnieją nieprzypisane elementy:
- Upewnij się, że istnieje agent, którego nie zazdrościsz - agent, którego nie zazdrości żaden inny agent.
- Przekaż następny przedmiot niezazdrosnemu agentowi.

na grafie zazdrości występuje skierowany cykl - graf skierowany , w którym każdy agent wskazuje wszystkich agentów, których zazdrości. Cykle można usuwać poprzez cykliczną wymianę wiązek. Po usunięciu wszystkich cykli wykres zazdrości musi mieć węzeł bez przychodzących krawędzi; ten węzeł reprezentuje niezazdrosnego agenta.

Wynikowa alokacja niekoniecznie jest EF, ale jest wolna od zazdrości, z wyjątkiem jednej pozycji. Dotyczy to nie tylko ostatecznego przydziału, ale także każdego pośredniego przydziału: ponieważ przedmiot jest zawsze przekazywany agentowi, któremu nie jest zazdrosny, zazdrość wszystkich innych agentów po tym przydziale jest co najwyżej pojedynczą rzeczą.

Analiza czasu pracy

Załóżmy, że jest m elementów. Każda alokacja elementu dodaje do wykresu zazdrości co najwyżej n -1 krawędzi. $W$ związku z tym ogólnie Każdy cykl usuwania usuwa co najmniej dwie krawędzie. Dlatego musimy uruchomić etap usuwania cyklu co najwyżej ${\ Displaystyle (n-1) m/2}$ razy. Znalezienie $używając$ można wykonać w czasie w głąb . W sumie czas działania wynosi ${\ Displaystyle O (n ^ {3} m)}$ .

Przykłady

W tych przykładach preferencje wahają się od 1 do 3, gdzie im wyższa liczba, tym wyższa preferencja. Również a, b i c to ludzie, podczas gdy X, Y i Z to przedmioty.

1) Przy 3 osobach i 3 przedmiotach każda możliwa alokacja będzie miała inny wynik. Ten przypadek ma miejsce, gdy każda z trzech osób ma takie same preferencje. Istnieje sześć różnych sposobów przydzielania obiektów:

6 różnych wyników
	X	Y	Z
A	3	2	1
B	3	2	1
C	3	2	1

Na początku, ponieważ nikt nic nie ma, wszyscy są agentami, których nie można zazdrościć i tak jest we wszystkich przypadkach. W przypadku remisu zrywamy więzi między niezazdrośnymi agentami w porządku leksykograficznym.

Zacznijmy od przekazania obiektu X do a. Potem zarówno b i c, jak i niezazdrośni agenci. Więc teraz dajmy obiekt Y b. Po tym c jest agentem, którego nie można zazdrościć. Więc teraz dajmy ostatni obiekt Z c. Teraz c jest zazdrosny o b i a, b jest zazdrosny o a i a nie jest zazdrosny o nikogo, a ponieważ nie ma już cyklu zazdrości i nie ma więcej przedmiotów do rozdania, procedura się kończy i końcowym wynikiem jest a dostaje X, b dostaje Y i c dostaje Z.
Zacznijmy od przekazania obiektu X do a. Potem zarówno b i c, jak i niezazdrośni agenci. Teraz dajmy obiekt Z b. Po tym c jest agentem, którego nie można zazdrościć. Więc teraz dajmy ostatni obiekt Y do c. Teraz c jest zazdrosny o a, b jest zazdrosny o a i c, a a nie jest zazdrosny o nikogo, a teraz, ponieważ nie ma cyklu zawiści i nie ma więcej przedmiotów do rozdania, procedura się kończy, a końcowy wynik to a dostaje X, b dostaje Z i c dostaje Y.
Zacznijmy od nadania obiektu Y a. Potem zarówno b i c, jak i niezazdrośni agenci. Więc teraz dajmy obiekt X b. Po tym c jest agentem, którego nie można zazdrościć. Więc teraz dajmy ostatni obiekt Z c. Teraz c jest zazdrosny o a i b, a jest zazdrosny o b i b nie jest zazdrosny o nikogo, a ponieważ nie ma już cyklu zazdrości i nie ma więcej przedmiotów do rozdania, procedura się kończy, a końcowym wynikiem jest a otrzymuje Y, b dostaje X i c dostaje Z.
Zacznijmy od nadania obiektu Y a. Potem zarówno b i c, jak i niezazdrośni agenci. Teraz dajmy obiekt Z b. Po tym c jest agentem, którego nie można zazdrościć. Więc teraz dajmy ostatni obiekt X na c. Teraz a jest zazdrosny o c, b jest zazdrosny o a i c oraz c nie jest zazdrosny o nikogo, a teraz, ponieważ nie ma cyklu zazdrości i nie ma więcej przedmiotów do rozdania, procedura się kończy, a końcowym wynikiem jest a otrzymuje Y, b dostaje Z i c dostaje X.
Zacznijmy od nadania obiektu Z a. Potem zarówno b i c, jak i niezazdrośni agenci. Więc teraz dajmy obiekt X b. Po tym c jest agentem, którego nie można zazdrościć. Więc teraz dajmy ostatni obiekt Y do c. Teraz c jest zazdrosny o b, a jest zazdrosny o b i c oraz b nie jest zazdrosny o nikogo, a teraz, ponieważ nie ma cyklu zawiści i nie ma więcej przedmiotów do rozdania, procedura się kończy, a końcowy wynik to a dostaje Z, b dostaje X i c dostaje Y.
Zacznijmy od nadania obiektu Z a. Potem zarówno b i c, jak i niezazdrośni agenci. Więc teraz dajmy obiekt Y b. Po tym c jest agentem, którego nie można zazdrościć. Więc teraz dajmy ostatni obiekt X na c. Teraz b jest zazdrosny o c, a jest zazdrosny o b i c oraz c nie jest zazdrosny o nikogo, a teraz, ponieważ nie ma cyklu zawiści i nie ma więcej przedmiotów do rozdania, procedura się kończy i końcowym wynikiem jest a dostaje Z, b dostaje Y, a c dostaje X.

2) Przy 3 osobach i 3 obiektach każda możliwa alokacja będzie miała taki sam wynik. Ten przypadek ma miejsce, gdy każda z trzech osób ma zupełnie inne preferencje, ponieważ każda osoba ma coś innego, co preferuje, bez względu na to, co dostanie, czego chce.

Ten sam wynik
	X	Y	Z
A	3	2	1
B	1	3	2
C	2	1	3

Istnieje sześć różnych sposobów przydzielania obiektów:

Na początku, ponieważ nikt nic nie ma, wszyscy są agentami, których nie można zazdrościć i tak jest we wszystkich przypadkach. W przypadku remisu zrywamy więzi między niezazdrośnymi agentami w porządku leksykograficznym.

Zacznijmy od przekazania obiektu X do a. Potem zarówno b i c, jak i niezazdrośni agenci. Więc teraz dajmy obiekt Y b. Po tym c jest agentem, którego nie można zazdrościć. Więc teraz dajmy ostatni obiekt Z c. Teraz a, b i c nie są o nikogo zazdrosne, a ponieważ nie ma już cyklu zazdrości i nie ma już przedmiotów do rozdania, procedura się kończy, a ostatecznym wynikiem jest to, że a dostaje X, b dostaje Y i c dostaje Z.
Zacznijmy od przekazania obiektu X do a. Potem zarówno b i c, jak i niezazdrośni agenci. Teraz dajmy obiekt Z b. Po tym c jest agentem, którego nie można zazdrościć. Więc teraz dajmy ostatni obiekt Y do c. Teraz c jest zazdrosny o b, b jest zazdrosny o c i a nie jest zazdrosny o nikogo. Ponieważ istnieje cykl zawiści między b i c, zamieniają się przedmiotami, a teraz b otrzymuje Y, a c dostaje Z. A teraz, ponieważ nie ma cyklu zawiści i nie ma więcej przedmiotów do rozdania, procedura się kończy, a końcowym rezultatem jest dostaje X, b dostaje Y i c dostaje Z.
Zacznijmy od nadania obiektu Y a. Potem zarówno b i c, jak i niezazdrośni agenci. Więc teraz dajmy obiekt X b. Po tym c jest agentem, którego nie można zazdrościć. Więc teraz dajmy ostatni obiekt Z c. Teraz b jest zazdrosny o a, a jest zazdrosny o b i c nie jest zazdrosny o nikogo. Ponieważ istnieje cykl zawiści między b i c, zamienią się przedmiotami i teraz a otrzymuje X, a b dostaje Y. A teraz, ponieważ nie ma cyklu zawiści i nie ma więcej przedmiotów do rozdania, procedura się kończy, a końcowym rezultatem jest dostaje X, b dostaje Y i c dostaje Z.
Zacznijmy od nadania obiektu Y a. Potem zarówno b i c, jak i niezazdrośni agenci. Teraz dajmy obiekt Z b. Po tym c jest agentem, którego nie można zazdrościć. Więc teraz dajmy ostatni obiekt X na c. Teraz b jest zazdrosny o a, a jest zazdrosny o c i c jest zazdrosny o b. Ponieważ istnieje cykl zawiści między a, b i c, będą obracać przedmioty w kierunku przeciwnym do zazdrości, a teraz a dostaje X, b dostaje Y i c dostaje Z. A teraz, ponieważ nie ma cyklu zazdrości i nie ma więcej przedmiotów do ręki out, procedura się kończy, a ostatecznym wynikiem jest a otrzymuje X, b otrzymuje Y, a c otrzymuje Z.
Zacznijmy od nadania obiektu Z a. Potem zarówno b i c, jak i niezazdrośni agenci. Więc teraz dajmy obiekt X b. Po tym c jest agentem, którego nie można zazdrościć. Więc teraz dajmy ostatni obiekt Y do c. Teraz b jest zazdrosny o a i c, a jest zazdrosny o b i c, a c jest zazdrosny o b i a. Ponieważ istnieje cykl zazdrości między a, b i c, będą obracać przedmioty w kierunku przeciwnym do zazdrości, a teraz a dostaje X, b dostaje Y, a c dostaje Z. A teraz, ponieważ nie ma cyklu zazdrości i nie ma więcej przedmiotów do rozdania następnie procedura się kończy, a końcowym wynikiem jest a otrzymuje X, b otrzymuje Y, a c otrzymuje Z.
Zacznijmy od nadania obiektu Z a. Potem zarówno b i c, jak i niezazdrośni agenci. Więc teraz dajmy obiekt Y b. Po tym c jest agentem, którego nie można zazdrościć. Więc teraz dajmy ostatni obiekt X na c. Teraz c jest zazdrosny o a, a jest zazdrosny o c i b nie jest zazdrosny o nikogo. Ponieważ istnieje cykl zazdrości między a i c, zamienią się obiektami, a teraz a otrzymuje X, a c otrzymuje Z. A teraz, ponieważ nie ma cyklu zazdrości i nie ma więcej przedmiotów do rozdania, procedura się kończy, a końcowym rezultatem jest dostaje X, b dostaje Y i c dostaje Z.

3) W przypadku 3 osób i 3 przedmiotów każda inna sytuacja niż w pierwszym i drugim przykładzie da od 1 do 6 wyników. Aby tak się stało, wystarczy, że co najmniej dwie osoby będą miały takie same preferencje dotyczące jednego obiektu lub co najwyżej dwie osoby będą miały różne preferencje dotyczące tego samego obiektu.

3 różne wyniki
	X	Y	Z
A	3	2	1
B	3	1	2
C	1	2	3

Istnieje sześć różnych sposobów przydzielania obiektów:

Na początku, ponieważ nikt nic nie ma, wszyscy są agentami, których nie można zazdrościć i tak jest we wszystkich przypadkach. W przypadku remisu zrywamy więzi między niezazdrośnymi agentami w porządku leksykograficznym.

Zacznijmy od przekazania obiektu X do a. Potem zarówno b i c, jak i niezazdrośni agenci. Więc teraz dajmy obiekt Y b. Po tym c jest agentem, którego nie można zazdrościć. Więc teraz dajmy ostatni obiekt Z c. Teraz a nie jest zazdrosny o nikogo, b jest zazdrosny o a i c oraz c nie jest zazdrosny o nikogo, teraz, ponieważ nie ma cyklu zazdrości i nie ma więcej przedmiotów do rozdania, procedura się kończy, a końcowym wynikiem jest X, b otrzymuje Y, a c otrzymuje Z.
Zacznijmy od przekazania obiektu X do a. Potem zarówno b i c, jak i niezazdrośni agenci. Teraz dajmy obiekt Z b. Po tym c jest agentem, którego nie można zazdrościć. Więc teraz dajmy ostatni obiekt Y do c. Teraz a nie jest zazdrosny o nikogo, b jest zazdrosny o a i c jest zazdrosny o b, teraz, ponieważ nie ma cyklu zazdrości i nie ma więcej przedmiotów do rozdania, procedura się kończy i końcowym wynikiem jest a dostaje X, b dostaje Z i c otrzymuje Y.
Zacznijmy od nadania obiektu Y a. Potem zarówno b i c, jak i niezazdrośni agenci. Teraz dajmy obiekt X b. Po tym c jest agentem, którego nie można zazdrościć. Więc teraz dajmy ostatni obiekt Z c. Teraz b i c nie są zazdrosne o nikogo, a a jest zazdrosne o b, teraz, ponieważ nie ma cyklu zawiści i nie ma już przedmiotów do rozdania, procedura się kończy, a końcowy wynik to a dostaje Y, b dostaje X i c dostaje Z .
Zacznijmy od nadania obiektu Y a. Potem zarówno b i c, jak i niezazdrośni agenci. Teraz dajmy obiekt Z b. Po tym c jest agentem, którego nie można zazdrościć. Więc teraz dajmy ostatni obiekt X na c. Teraz a jest zazdrosny o c, b jest zazdrosny o c i c jest zazdrosny o aib, więc są dwa cykle zazdrości, jeden między a i c, a drugi między b i c. Ponieważ rozstrzyganie remisów jest zgodne z porządkiem leksykograficznym, procedura najpierw wykonuje cykl zazdrości a i c, następnie zamieniają się a i c, a następnie a nie jest zazdrosny o nikogo, b jest zazdrosny o a i c jest zazdrosny o b, a teraz, ponieważ nie ma zazdrości i nie ma więcej przedmiotów do rozdania, procedura się kończy, a ostatecznym wynikiem jest to, że a otrzymuje X, b otrzymuje Z, a c otrzymuje Y.
Zacznijmy od nadania obiektu Z a. Potem zarówno b i c, jak i niezazdrośni agenci. Teraz dajmy obiekt X b. Po tym c jest agentem, którego nie można zazdrościć. Więc teraz dajmy ostatni obiekt Y do c. Teraz a jest zazdrosny o b i c, b nie jest zazdrosny o nikogo, a c jest zazdrosny o a. Ponieważ istnieje cykl zazdrości między a i c, zamienią się obiektami, a teraz a otrzymuje Y i c otrzymuje Z, teraz, ponieważ nie ma cyklu zazdrości i nie ma więcej przedmiotów do rozdania, procedura się kończy, a końcowy wynik to a otrzymuje Y , b otrzymuje X, a c otrzymuje Z.
Zacznijmy od nadania obiektu Z a. Potem zarówno b i c, jak i niezazdrośni agenci. Więc teraz dajmy obiekt Y b. Po tym c jest agentem, którego nie można zazdrościć. Więc teraz dajmy ostatni obiekt X na c. Teraz b jest zazdrosny o a i c, a jest zazdrosny o b i c, a c jest zazdrosny o b i a. Ponieważ istnieje cykl zazdrości między a, b i c, będą obracać obiekty w kierunku przeciwnym do kierunku zazdrości. Ponieważ jednak istnieją 2 cykle zazdrości między a, b i c, mogą istnieć dwie opcje. Ponieważ rozstrzyganie remisów jest zgodne z porządkiem leksykograficznym, a otrzymuje X z c, b otrzymuje Z z a, c otrzymuje Y z b, więc wynik byłby następujący: a otrzymuje X, b otrzymuje Z i c otrzymuje Y. A teraz, ponieważ nie ma zazdrości cyklu i nie ma więcej przedmiotów do rozdania, procedura się kończy, a ostatecznym wynikiem jest a otrzymuje X, b otrzymuje Z i c otrzymuje Y.

Rozszerzenia

Algorytm wykresu zazdrości gwarantuje EF1, gdy pozycje są dobrami (- wartość krańcowa każdej pozycji jest dodatnia dla wszystkich agentów). Jednak gdy występują zarówno towary, jak i obowiązki, nie gwarantuje to EF1. Adaptacja zwana uogólnionym wykresem zazdrości gwarantuje EF1 nawet przy mieszance dóbr i obowiązków. Działa zawsze wtedy, gdy wyceny są podwójnie monotoniczne , to znaczy: każdy agent może podzielić pozycje na dwa podzbiory: jeden podzbiór zawiera dobra (- przedmioty, których użyteczność krańcowa jest zawsze dodatnia), a drugi zawiera obowiązki domowe (- przedmioty, których użyteczność krańcowa jest zawsze dodatnia). negatywny).

Gdy agenci mają ograniczenia liczności (tj. dla każdej kategorii pozycji istnieje górna granica liczby pozycji, które każdy agent otrzymuje z tej kategorii), algorytm wykresu zazdrości może zawieść. Jednak połączenie tego z protokołem okrężnym daje algorytm, który znajduje alokacje, które są zarówno EF1, jak i spełniają ograniczenia liczności.

Kiedy agenci mają wyceny przydziału (inaczej wyceny OXS), istnieje rozszerzenie algorytmu wykresu zazdrości o nazwie „Algorytm H”, w którym następna alokacja do agenta, którego nie zazdrości, jest wybierana w taki sposób, aby zmaksymalizować użyteczność agenta-przedmiotu. Nie ma formalnego dowodu na właściwości tego algorytmu, ale dobrze sobie radzi z realistycznymi danymi.

Zobacz też

Alokacja przedmiotów bez zazdrości
Zachłanne partycjonowanie liczb - można zobaczyć specjalny przypadek algorytmu grafu zazdrości dla przypadku, gdy wszyscy agenci mają identyczne wyceny.
Procedura Malejącego Popytu i procedura podcięcia - dwie dodatkowe procedury oparte na porządku porządkowym pakietów.