Postup grafu závisti - Envy-graph procedure

The postup grafu závisti (nazývané také postup závistných cyklů) je postup pro spravedlivé rozdělení položek. Může ho použít několik lidí, kteří mezi ně chtějí rozdělit několik samostatných předmětů, jako jsou dědictví, sladkosti nebo místa ve třídě.

V ideálním případě bychom chtěli, aby to bylo alokace bez závisti (EF). tj. dát každému agentovi balíček, který upřednostňuje před balíčky všech ostatních agentů. Položky jsou však diskrétní a nelze je vyjmout, takže může být nemožné záviděníhodné přiřazení (například zvažte jednu položku a dva agenty). Procedura grafu závisti má za cíl dosáhnout možnosti „next-best“ - závistivost až nanejvýš jediné dobro (EF1): najde alokaci, ve které je závislost každé osoby vůči každé další osobě omezena maximální mezní užitečností, kterou odvozuje od jedné položky. Jinými slovy, pro každé dva lidi i a j, existuje položka taková, že pokud je tato položka odstraněna, i nezávidí j.

Postup představili Lipton a Markakis a Mossel a Saberi^[1] a je to také popsáno v.^{[2]:300–301}

Předpoklady

Postup grafu závisti předpokládá, že každá osoba má hlavní nástroj funkce na svazcích položek. Tato obslužná funkce musí být monotónní (užitečnost sady je přinejmenším stejně velká jako užitečnost jejích podmnožin). Nicméně ano ne musí být aditivní. Tj. Položky jsou ne předpokládá se nezávislé zboží.

Agenti nemusí ve skutečnosti hlásit svou hlavní užitečnost: stačí, aby věděli, jak řadit balíčky.

Postup

1. Objednávejte položky libovolně.
2. I když existují nepřiřazené položky:
   • Ujistěte se, že existuje nezáviděný agent - agent, kterému žádný jiný agent nezávidí.
   • Dejte další položku nezáviděnému agentovi.

Pokud v kroku 2 není žádný nezáviděný agent, znamená to, že existuje řízený cyklus v graf závisti - a řízený graf ve kterém každý agent ukazuje na všechny agenty, které mu závidí. Cykly lze odstranit cyklickou výměnou svazků. Po odstranění všech cyklů musí mít graf závisti uzel bez příchozích hran; tento uzel představuje nezáviděného agenta.

Výsledná alokace nemusí být nutně EF, ale kromě jedné položky je bez závisti. To platí nejen v konečné alokaci, ale také v každé mezilehlé alokaci: protože položka je vždy dána nezáviděnému agentovi, závist všech ostatních agentů po této alokaci je nanejvýš jedinou položkou.

Analýza běhu

Předpokládejme, že existují m položky. Každá alokace položky se přidává do grafu závisti n-1 hrany. Proto nanejvýš ${ displaystyle (n-1) m}$ okraje jsou přidány celkově. Každé odstranění cyklu odstraní alespoň dva okraje. Proto musíme spustit krok odstranění cyklu nanejvýš ${ displaystyle (n-1) m / 2}$ krát. Hledání cyklu lze provést včas ${ displaystyle O (n ^ {2})}$ pomocí např. hloubkové vyhledávání. Celkově vzato je doba běhu ${ displaystyle O (n ^ {3} m)}$.

Příklady

V těchto příkladech preference jdou od 1-3, kde čím vyšší číslo, tím vyšší preference. Také a, b a c jsou lidé, zatímco X, Y a Z jsou objekty.

1) Se 3 osobami a 3 objekty bude každá možná alokace jiným výsledkem. K tomuto případu dochází, když má každý ze tří lidí stejné preference. Existuje šest různých způsobů přidělení objektů:

Na začátku, protože nikdo nic nemá, jsou všichni nezávidění agenti a to je ve všech případech stejné. V případě shody rozcházíme vazby mezi nezáviděnými agenty v lexikografickém pořadí.

1. Začněme tím, že dáme objekt X a. Poté jak BA, tak nezávidění agenti. Nyní tedy dáme objekt Y b. Poté je c nezáviděný agent. Nyní tedy dáme poslední objekt Z až c. Nyní c žárlí na b a a, b žárlí na a a a na nikoho nežárlí a nyní, protože neexistuje žádný závistivý cyklus a žádné další předměty k rozdávání, postup končí a konečným výsledkem je a get X, b dostane Y a c dostane Z.
2. Začněme tím, že dáme objekt X a. Poté jak BA, tak nezávidění agenti. Nyní tedy dejme objekt Z b. Poté je c nezáviděný agent. Nyní tedy dáme poslední objekt Y c. Nyní c žárlí na a, b žárlí na aac a a na nikoho nežárlí a teď, protože neexistuje žádný závistivý cyklus a žádné další předměty, které by bylo možné rozdávat, pak procedura končí a konečným výsledkem je a get X, b dostane Z a c dostane Y.
3. Začněme tím, že dáme objekt Y a. Poté jak BA, tak nezávidění agenti. Pojďme tedy dát objekt X b. Poté je c nezáviděný agent. Nyní tedy dáme poslední objekt Z až c. Nyní c žárlí na a a b, a žárlí na b a b nežárlí na nikoho a teď, protože neexistuje žádný závistivý cyklus a žádné další předměty, které by bylo možné rozdávat, pak procedura končí a konečným výsledkem je a dostane Y, b dostane X a C dostane Z.
4. Začněme tím, že dáme objekt Y a. Poté jak BA, tak nezávidění agenti. Nyní tedy dáme objekt Z b. Poté je c nezáviděný agent. Nyní tedy dáme poslední objekt X až c. Nyní a žárlí na c, b žárlí na a ac c c na nikoho nežárlí a teď, protože neexistuje žádný závistivý cyklus a žádné další předměty, které by bylo možné rozdávat, pak procedura končí a konečným výsledkem je a dostane Y, b dostane Z a c dostane X.
5. Začněme tím, že dáme objekt Z a. Poté jak BA, tak nezávidění agenti. Pojďme tedy dát objekt X b. Poté je c nezáviděný agent. Nyní tedy dáme poslední objekt Y c. Nyní c žárlí na b, a žárlí na bac c a b na nikoho nežárlí a teď, protože neexistuje žádný závistivý cyklus a žádné další předměty, které by bylo možné rozdávat, pak procedura končí a konečným výsledkem je a get Z, b dostane X a C dostane Y.
6. Začněme tím, že dáme objekt Z a. Poté jak BA, tak nezávidění agenti. Nyní tedy dáme objekt Y b. Poté je c nezáviděný agent. Nyní tedy dáme poslední objekt X až c. Nyní b žárlí na c, a žárlí na bac c a c na nikoho nežárlí a teď, protože neexistuje žádný závistivý cyklus a žádné další předměty, které by bylo možné rozdávat, pak procedura končí a konečným výsledkem je a dostane Z, b dostane Y a c dostane X.

2) Se 3 osobami a 3 objekty bude každá možná alokace stejného výsledku. Tento případ se stane, když každý ze tří lidí má úplně jiné preference, protože každý člověk má něco jiného, ​​co dává přednost bez ohledu na to, co dostane, co chce.

Existuje šest různých způsobů přidělení objektů:

Na začátku, protože nikdo nic nemá, jsou všichni nezávidění agenti a to je ve všech případech stejné. V případě shody rozcházíme vazby mezi nezáviděnými agenty v lexikografickém pořadí.

1. Začněme tím, že dáme objekt X a. Poté jak BA, tak nezávidění agenti. Nyní tedy dáme objekt Y b. Poté je c nezáviděný agent. Nyní tedy dáme poslední objekt Z až c. Nyní a, b a c na nikoho nežárlí a nyní, protože neexistuje žádný závistivý cyklus a žádné další předměty, které by bylo možné rozdávat, pak procedura končí a konečným výsledkem je a dostane X, b dostane Y a c dostane Z.
2. Začněme tím, že dáme objekt X a. Poté jak BA, tak nezávidění agenti. Nyní tedy dáme objekt Z b. Poté je c nezáviděný agent. Nyní tedy dáme poslední objekt Y c. Nyní c žárlí na b, b žárlí na c a a nežárlí na nikoho. Protože mezi bac je cyklus závisti, budou přepínat objekty a nyní b dostane Yac dostane Z. A teď, protože neexistuje žádný cyklus závisti a žádné další objekty, které by bylo možné rozdávat, pak procedura končí a konečným výsledkem je a dostane X, b dostane Y a c dostane Z.
3. Začněme tím, že dáme objekt Y a. Poté jak BA, tak nezávidění agenti. Pojďme tedy dát objekt X b. Poté je c nezáviděný agent. Nyní tedy dáme poslední objekt Z až c. Nyní b žárlí na, a žárlí na b a c nežárlí na nikoho. Protože mezi bac je cyklus závisti, budou přepínat objekty a nyní a dostane X a b dostane Y. A teď, protože neexistuje žádný cyklus závisti a žádné další objekty k rozdávání, postup končí a konečným výsledkem je a dostane X, b dostane Y a c dostane Z.
4. Začněme tím, že dáme objekt Y a. Poté jak BA, tak nezávidění agenti. Nyní tedy dáme objekt Z b. Poté je c nezáviděný agent. Nyní tedy dáme poslední objekt X až c. Nyní b žárlí na, a žárlí na c a c žárlí na b. Protože mezi a, b a c existuje cyklus závisti, budou otáčet objekty proti směru žárlivosti a nyní a dostane X, b dostane Y a c dostane Z. A teď, protože neexistuje žádný závistivý cyklus a žádné další objekty po ruce poté procedura končí a konečným výsledkem je a dostane X, b dostane Y a c dostane Z.
5. Začněme tím, že dáme objekt Z a. Poté jak BA, tak nezávidění agenti. Pojďme tedy dát objekt X b. Poté je c nezáviděný agent. Nyní tedy dáme poslední objekt Y c. Nyní b žárlí na a a c, a žárlí na b a c a c žárlí na b a a. Vzhledem k tomu, že mezi a, b a c existuje cyklus závisti, budou otáčet objekty proti směru žárlivosti a nyní a dostane X a b dostane Y a c dostane Z. A teď, protože neexistuje žádný závistivý cyklus a žádné další předměty k rozdávání pak postup končí a konečným výsledkem je a dostane X, b dostane Y a c dostane Z.
6. Začněme tím, že dáme objekt Z a. Poté jak BA, tak nezávidění agenti. Nyní tedy dáme objekt Y b. Poté je c nezáviděný agent. Nyní tedy dáme poslední objekt X až c. Nyní c žárlí na, a žárlí na c a b nežárlí na nikoho. Protože existuje cyklus závisti mezi a a c, budou přepínat objekty a nyní a dostane X a c dostane Z. A teď, protože neexistuje žádný cyklus závisti a žádné další objekty k rozdání, postup končí a konečným výsledkem je a dostane X, b dostane Y a c dostane Z.

3) Se 3 osobami a 3 objekty bude jakákoli jiná situace, než první a druhý příklad, obsahovat 1 až 6 výsledků. Aby k tomu došlo, potřebujete, aby alespoň dva lidé měli stejné preference na jeden objekt, nebo nanejvýš pro dva lidi, aby měli různé preference pro stejný objekt.

Existuje šest různých způsobů přidělení objektů:

Na začátku, protože nikdo nic nemá, jsou všichni nezávidění agenti a to je ve všech případech stejné. V případě shody rozcházíme vazby mezi nezáviděnými agenty v lexikografickém pořadí.

1. Začněme tím, že dáme objekt X a. Poté jak BA, tak nezávidění agenti. Nyní tedy dáme objekt Y b. Poté je c nezáviděný agent. Nyní tedy dáme poslední objekt Z až c. Nyní a na nikoho nežárlí, b na nikoho žárlí a c a c na nikoho nežárlí, nyní, protože neexistuje žádný závistivý cyklus a žádné další předměty, které by bylo možné rozdávat, pak procedura končí a konečným výsledkem je get X, b dostane Y a c dostane Z.
2. Začněme tím, že dáme objekt X a. Poté jak BA, tak nezávidění agenti. Nyní tedy dáme objekt Z b. Poté je c nezáviděný agent. Nyní tedy dáme poslední objekt Y c. Nyní a nežárlí na nikoho, b žárlí na a a c žárlí na b, nyní, protože neexistuje žádný závistivý cyklus a žádné další předměty k rozdání, pak procedura končí a konečným výsledkem je a dostane X, b dostane Z ac dostane Y.
3. Začněme tím, že dáme objekt Y a. Poté jak BA, tak nezávidění agenti. Pojďme tedy dát objekt X b. Poté je c nezáviděný agent. Nyní tedy dáme poslední objekt Z až c. Nyní b a c na nikoho nežárlí a a žárlí na b, nyní, protože neexistuje žádný závistivý cyklus a žádné další předměty k rozdávání, procedura končí a konečným výsledkem je a dostane Y, b dostane X a c dostane Z .
4. Začněme tím, že dáme objekt Y a. Poté jak BA, tak nezávidění agenti. Nyní tedy dáme objekt Z b. Poté je c nezáviděný agent. Nyní tedy dáme poslední objekt X až c. Nyní a žárlí na c, b žárlí na c a c žárlí na a a b, takže existují dva závistivé cykly, jeden mezi a a c a druhý mezi b a c. Protože dělení tie je podle lexikografického pořadí, postup nejdříve přepne cyklus závisti a a c, potom se přepne a a c, pak a na nikoho nežárlí, b žárlí na a a c žárlí na b a nyní, protože neexistuje cyklus závisti a žádné další předměty k rozdání, pak procedura končí a konečným výsledkem je a dostane X, b dostane Z a c dostane Y.
5. Začněme tím, že dáme objekt Z a. Poté jak BA, tak nezávidění agenti. Pojďme tedy dát objekt X b. Poté je c nezáviděný agent. Nyní tedy dáme poslední objekt Y c. Nyní a žárlí na b a c, b nežárlí na nikoho a c žárlí na a. Vzhledem k tomu, že mezi aac existuje cyklus závisti, budou přepínat objekty a nyní dostane Y a C dostane Z, nyní, protože neexistuje žádný cyklus závisti a žádné další objekty, které by bylo možné rozdávat, pak procedura končí a konečným výsledkem je a dostane Y , b dostane X a c dostane Z.
6. Začněme tím, že dáme objekt Z a. Poté jak BA, tak nezávidění agenti. Nyní tedy dáme objekt Y b. Poté je c nezáviděný agent. Nyní tedy dáme poslední objekt X až c. Nyní b žárlí na a a c, a žárlí na b a c a c žárlí na b a a. Protože mezi a, b a c existuje cyklus závisti, budou otáčet objekty proti směru žárlivosti. Protože však mezi a, bac existují dva závistivé cykly, mohou existovat dvě možnosti. Protože rozdělovač tie je podle lexikografického pořadí, a dostane X z c, b dostane Z z a c dostane Y z b, takže výsledkem bude a dostane X, b dostane Z a c dostane Y. A teď, protože neexistuje žádná závist cyklus a žádné další objekty k rozdání, pak procedura končí a konečným výsledkem je a dostane X, b dostane Z a c dostane Y.

Rozšíření

Algoritmus grafu závisti zaručuje EF1, když jsou položky zboží (- mezní hodnota každé položky je pro všechny agenty kladná). Pokud však existuje zboží i práce, nezaručuje to EF1. Volala adaptace zobecněný graf závisti zaručuje EF1 i při kombinaci zboží a práce. Funguje to, kdykoli jsou ocenění dvojnásobně monotónní, to znamená: každý agent může rozdělit položky do dvou podmnožin: jedna podmnožina obsahuje zboží (- položky, jejichž mezní užitek je vždy pozitivní) a druhá obsahuje domácí práce (- položky, jejichž mezní užitnost je vždy záporná).^[3]

Pokud mají agenti omezení mohutnosti (tj. Pro každou kategorii položek existuje horní hranice počtu položek, které každý agent získá z této kategorie), algoritmus závidění grafu může selhat. Kombinace však s protokol každý s každým dává algoritmus, který najde přidělení, která jsou EF1 a splňují omezení mohutnosti.^[4]

Viz také

• Přidělení položek bez závisti
• Chamtivé dělení čísel - lze zobrazit speciální případ algoritmu grafu závisti pro případ, kdy mají všichni agenti shodná ocenění.

Reference