Avundsgraf-procedur

Envy -graph-proceduren (även kallad envy-cycles-proceduren ) är en procedur för rättvis tilldelning av föremål . Den kan användas av flera personer som vill dela upp flera diskreta föremål, såsom arvegods, godis eller sittplatser i en klass.

Helst skulle vi vilja att tilldelningen var avundsfri (EF). dvs att ge varje agent en bunt som han/hon föredrar framför buntarna av alla andra agenter. Föremålen är dock diskreta och kan inte klippas, så ett uppdrag utan avundsjuka kan vara omöjligt (tänk till exempel på ett enda föremål och två agenter). Avundsgraf-proceduren syftar till att uppnå det "näst bästa" alternativet - avundsfrihet upp till högst en enskild vara (EF1): den hittar en tilldelning där varje persons avund mot varje annan person begränsas av maximal marginell nytta den härrör från en enda artikel. Med andra ord, för varannan person i och j , finns det ett objekt så att, om det objektet tas bort, i inte avundas j .

Förfarandet presenterades av Lipton och Markakis och Mossel och Saberi och det beskrivs också i .

Antaganden

Avundsgraf-proceduren förutsätter att varje person har en kardinal nyttofunktion på buntar av föremål. Denna hjälpfunktion måste vara monoton (nyttan av en mängd är minst lika stor som nyttan av dess delmängder). Det behöver dock inte vara tillsats. Dvs varorna inte vara oberoende varor .

Agenterna behöver inte faktiskt rapportera sin kardinalnytta: det räcker att de vet hur man rangordnar buntar.

Proceduren

1. Beställ föremålen godtyckligt.
2. Medan det finns objekt som inte är tilldelade:
   • Se till att det finns en agent som inte är avundsjuk - en agent som ingen annan agent avundas.
   • Ge nästa föremål till den avundsjuka agenten.

I steg 2, om det inte finns någon oavundsvärd agent, betyder det att det finns en riktad cykel i avundsgrafen - en riktad graf där varje agent pekar på alla agenter han avundas. Cyklar kan tas bort genom cykliskt utbyte av buntar. Efter att alla cykler har tagits bort måste avundsgrafen ha en nod utan inkommande kanter; denna nod representerar en icke avundsjuk agent.

Den resulterande allokeringen är inte nödvändigtvis EF, men den är fri från avundsjuka förutom ett föremål. Detta gäller inte bara i den slutliga tilldelningen utan också i varje mellantilldelning: eftersom en artikel alltid ges till en icke avundsvärd agent, är avundsjukan hos alla andra agenter efter den tilldelningen högst en enskild post.

Körtidsanalys

Anta att det finns m objekt. Varje tilldelning av ett objekt lägger till avundsgrafen högst n -1 kanter. Följaktligen läggs som mest ${\displaystyle (n-1)m} kanter till totalt.$ Varje cykelborttagning tar bort minst två kanter. Därför måste vi köra cykelborttagningssteget högst $(n-1)m/2$ gånger. Att hitta en cykel kan göras i tid $O(n^{2})$ med t.ex. djup-först-sökning . Allt som allt är körtiden $O(n^{3}m)$ .

Exempel

I dessa exempel går preferenserna från 1-3 där ju högre siffra desto högre preferens. Även a, b och c är människor medan X, Y och Z är objekt.

1) Med 3 personer och 3 objekt blir varje möjlig tilldelning ett annat resultat. Detta fall inträffar när var och en av de tre personerna har samma preferenser. Det finns sex olika sätt att allokera objekten:

6 olika resultat

	X	Y	Z
a	3	2	1
b	3	2	1
c	3	2	1

I början eftersom ingen har någonting så är alla avundsvärda agenter och det är samma sak i alla fall. I händelse av oavgjort bryter vi banden mellan icke avundade agenter i lexikografisk ordning.

1. Låt oss börja med att ge X-objektet till a. Efter det både b och c och unenviated agenter. Så låt oss nu ge Y-objektet till b. Efter det är c ​​en föga avundsjuk agent. Så låt oss nu ge det sista objektet Z till c. Nu är c ​​avundsjuk på b och a, b är avundsjuk på a och a är inte avundsjuk på någon och nu eftersom det inte finns någon avundscykel och inga fler föremål att dela ut så avslutas proceduren och slutresultatet är a får X, b får Y och c får Z.
2. Låt oss börja med att ge X-objektet till a. Efter det både b och c och unenviated agenter. Så låt oss nu ge Z-objektet till b. Efter det är c ​​en föga avundsjuk agent. Så låt oss nu ge det sista objektet Y till c. Nu är c ​​avundsjuk på a, b är avundsjuk på a och c och a är inte avundsjuk på någon och nu eftersom det inte finns någon avundscykel och inga fler föremål att dela ut så avslutas proceduren och slutresultatet är a får X, b får Z och c får Y.
3. Låt oss börja med att ge Y-objektet till a. Efter det både b och c och unenviated agenter. Så låt oss nu ge X-objektet till b. Efter det är c ​​en föga avundsjuk agent. Så låt oss nu ge det sista objektet Z till c. Nu är c ​​avundsjuk på a och b, a är avundsjuk på b och b är inte avundsjuk på någon och nu eftersom det inte finns någon avundscykel och inga fler föremål att dela ut så avslutas proceduren och slutresultatet är a får Y, b får X och c får Z.
4. Låt oss börja med att ge Y-objektet till a. Efter det både b och c och unenviated agenter. Så låt oss nu ge Z-objektet till b. Efter det är c ​​en föga avundsjuk agent. Så låt oss nu ge det sista objektet X till c. Nu är a avundsjuk på c, b är avundsjuk på a och c och c är inte avundsjuk på någon och nu eftersom det inte finns någon avundscykel och inga fler föremål att dela ut så avslutas proceduren och slutresultatet är a får Y, b får Z och c får X.
5. Låt oss börja med att ge Z-objektet till a. Efter det både b och c och unenviated agenter. Så låt oss nu ge X-objektet till b. Efter det är c ​​en föga avundsjuk agent. Så låt oss nu ge det sista objektet Y till c. Nu är c ​​avundsjuk på b, a är avundsjuk på b och c och b är inte avundsjuk på någon och nu eftersom det inte finns någon avundscykel och inga fler föremål att dela ut så avslutas proceduren och slutresultatet är a får Z, b får X och c får Y.
6. Låt oss börja med att ge Z-objektet till a. Efter det både b och c och unenviated agenter. Så låt oss nu ge Y-objektet till b. Efter det är c ​​en föga avundsjuk agent. Så låt oss nu ge det sista objektet X till c. Nu är b avundsjuk på c, a är avundsjuk på b och c och c är inte avundsjuk på någon och nu eftersom det inte finns någon avundscykel och inga fler föremål att dela ut så avslutas proceduren och slutresultatet är a får Z, b får Y och c får X.

2) Med 3 personer och 3 objekt blir varje möjlig tilldelning samma resultat. Det här fallet händer när var och en av de tre personerna har helt olika preferenser, eftersom varje person har något annat de föredrar oavsett vad de kommer att få vad de vill ha.

Samma resultat

	X	Y	Z
a	3	2	1
b	1	3	2
c	2	1	3

Det finns sex olika sätt att allokera objekten:

I början eftersom ingen har någonting så är alla avundsvärda agenter och det är samma sak i alla fall. I händelse av oavgjort bryter vi banden mellan icke avundade agenter i lexikografisk ordning.

1. Låt oss börja med att ge X-objektet till a. Efter det både b och c och unenviated agenter. Så låt oss nu ge Y-objektet till b. Efter det är c ​​en föga avundsjuk agent. Så låt oss nu ge det sista objektet Z till c. Nu är a, b och c alla inte avundsjuka på någon och nu eftersom det inte finns någon avundscykel och inga fler föremål att dela ut så avslutas proceduren och slutresultatet är a får X, b får Y och c får Z.
2. Låt oss börja med att ge X-objektet till a. Efter det både b och c och unenviated agenter. Så låt oss nu ge Z-objektet till b. Efter det är c ​​en föga avundsjuk agent. Så låt oss nu ge det sista objektet Y till c. Nu är c ​​avundsjuk på b, b är svartsjuk på c och a är inte svartsjuk på någon. Eftersom det finns en avundscykel mellan b och c kommer de att byta objekt och nu får b Y och c får Z. Och nu eftersom det inte finns någon avundscykel och inga fler objekt att dela ut så avslutas proceduren och det slutliga resultatet är en får X, b får Y och c får Z.
3. Låt oss börja med att ge Y-objektet till a. Efter det både b och c och unenviated agenter. Så låt oss nu ge X-objektet till b. Efter det är c ​​en föga avundsjuk agent. Så låt oss nu ge det sista objektet Z till c. Nu är b avundsjuk på a, a är svartsjuk på b och c är inte svartsjuk på någon. Eftersom det finns en avundscykel mellan b och c kommer de att byta objekt och nu får a X och b får Y. Och nu eftersom det inte finns någon avundscykel och inga fler objekt att dela ut så avslutas proceduren och slutresultatet är en får X, b får Y och c får Z.
4. Låt oss börja med att ge Y-objektet till a. Efter det både b och c och unenviated agenter. Så låt oss nu ge Z-objektet till b. Efter det är c ​​en föga avundsjuk agent. Så låt oss nu ge det sista objektet X till c. Nu är b avundsjuk på a, a är svartsjuk på c och c är svartsjuk på b. Eftersom det finns en avundscykel mellan a, b och c, kommer de att rotera föremål mot svartsjukans riktning och nu får a X, b får Y och c får Z. Och nu eftersom det inte finns någon avundscykel och inga fler föremål till hands ut, sedan avslutas proceduren och slutresultatet är a får X, b får Y och c får Z.
5. Låt oss börja med att ge Z-objektet till a. Efter det både b och c och unenviated agenter. Så låt oss nu ge X-objektet till b. Efter det är c ​​en föga avundsjuk agent. Så låt oss nu ge det sista objektet Y till c. Nu är b avundsjuk på a och c, a är svartsjuk på b och c och c är svartsjuk på b och a. Eftersom det finns en avundscykel mellan a, b och c kommer de att rotera föremål mot svartsjukans riktning och nu får a X och b får Y och c får Z. Och nu eftersom det inte finns någon avundscykel och inga fler föremål att dela ut sedan avslutas proceduren och slutresultatet är a får X, b får Y och c får Z.
6. Låt oss börja med att ge Z-objektet till a. Efter det både b och c och unenviated agenter. Så låt oss nu ge Y-objektet till b. Efter det är c ​​en föga avundsjuk agent. Så låt oss nu ge det sista objektet X till c. Nu är c ​​avundsjuk på a, a är svartsjuk på c och b är inte svartsjuk på någon. Eftersom det finns en avundscykel mellan a och c kommer de att byta objekt och nu får a X och c får Z. Och nu eftersom det inte finns någon avundscykel och inga fler objekt att dela ut så avslutas proceduren och slutresultatet är en får X, b får Y och c får Z.

3) Med 3 personer och 3 objekt, alla andra situationer än det första och andra exemplet kommer att ge mellan 1 och 6 resultat. Så för att det ska hända behöver du bara att minst två personer har samma preferenser på ett objekt eller som mest att två personer har olika preferenser på samma objekt.

3 olika resultat

	X	Y	Z
a	3	2	1
b	3	1	2
c	1	2	3

Det finns sex olika sätt att allokera objekten:

I början eftersom ingen har någonting så är alla avundsvärda agenter och det är samma sak i alla fall. I händelse av oavgjort bryter vi banden mellan icke avundade agenter i lexikografisk ordning.

1. Låt oss börja med att ge X-objektet till a. Efter det både b och c och unenviated agenter. Så låt oss nu ge Y-objektet till b. Efter det är c ​​en föga avundsjuk agent. Så låt oss nu ge det sista objektet Z till c. Nu är a inte avundsjuk på någon, b är avundsjuk på a och c och c är inte avundsjuk på någon, nu eftersom det inte finns någon avundscykel och inga fler föremål att dela ut så avslutas proceduren och slutresultatet är att a får X, b får Y och c får Z.
2. Låt oss börja med att ge X-objektet till a. Efter det både b och c och unenviated agenter. Så låt oss nu ge Z-objektet till b. Efter det är c ​​en föga avundsjuk agent. Så låt oss nu ge det sista objektet Y till c. Nu är a inte avundsjuk på någon, b är avundsjuk på a och c är avundsjuk på b, nu eftersom det inte finns någon avundscykel och inga fler föremål att dela ut så avslutas proceduren och slutresultatet är a får X, b får Z och c får Y.
3. Låt oss börja med att ge Y-objektet till a. Efter det både b och c och unenviated agenter. Så låt oss nu ge X-objektet till b. Efter det är c ​​en föga avundsjuk agent. Så låt oss nu ge det sista objektet Z till c. Nu är b och c inte avundsjuka på någon och a är avundsjuka på b, nu eftersom det inte finns någon avundscykel och inga fler föremål att dela ut så avslutas proceduren och slutresultatet är a får Y, b får X och c får Z .
4. Låt oss börja med att ge Y-objektet till a. Efter det både b och c och unenviated agenter. Så låt oss nu ge Z-objektet till b. Efter det är c ​​en föga avundsjuk agent. Så låt oss nu ge det sista objektet X till c. Nu är a avundsjuk på c, b är svartsjuk på c och c är svartsjuk på a och b, så det finns två avundsjuka cykler, en mellan a och c och en annan mellan b och c. Eftersom oavgjort är av lexikografisk ordning, gör proceduren avundscykeln a och c först, sedan byter a och c sedan a är inte avundsjuk på någon, b är avundsjuk på a och c är avundsjuk på b och nu eftersom det inte finns någon avundscykel och inga fler föremål att dela ut, sedan avslutas proceduren och slutresultatet är a får X, b får Z och c får Y.
5. Låt oss börja med att ge Z-objektet till a. Efter det både b och c och unenviated agenter. Så låt oss nu ge X-objektet till b. Efter det är c ​​en föga avundsjuk agent. Så låt oss nu ge det sista objektet Y till c. Nu är a avundsjuk på b och c, b är inte svartsjuk på någon och c är svartsjuk på a. Eftersom det finns en avundscykel mellan a och c kommer de att byta objekt och nu får a Y och c får Z, nu eftersom det inte finns någon avundscykel och inga fler objekt att dela ut så avslutas proceduren och slutresultatet är ett får Y , b får X och c får Z.
6. Låt oss börja med att ge Z-objektet till a. Efter det både b och c och unenviated agenter. Så låt oss nu ge Y-objektet till b. Efter det är c ​​en föga avundsjuk agent. Så låt oss nu ge det sista objektet X till c. Nu är b avundsjuk på a och c, a är svartsjuk på b och c och c är svartsjuk på b och a. Eftersom det finns en avundscykel mellan a, b och c kommer de att rotera föremål mot svartsjukans riktning. Men eftersom det finns två avundscykler mellan a, b och c kan det finnas två alternativ. Eftersom oavgjort är efter lexikografisk ordning, a får X från c, b får Z från a och c får Y från b så resultatet skulle bli a får X, b får Z och c får Y. Och nu eftersom det inte finns någon avundsjuka cykla och inga fler föremål att dela ut så avslutas proceduren och slutresultatet är a får X, b får Z och c får Y.

Tillägg

Envy-graph-algoritmen garanterar EF1 när föremålen är varor (- marginalvärdet för varje artikel är positivt för alla agenter). Men när det finns både varor och sysslor garanterar det inte EF1. En anpassning som kallas generalized envy-graph garanterar EF1 även med en blandning av varor och sysslor. Det fungerar närhelst värderingarna är dubbelt monotona , det vill säga: varje agent kan dela upp föremålen i två delmängder: en delmängd innehåller varor (- objekt vars marginalnytta alltid är positiv) och den andra innehåller sysslor (- objekt vars marginalnytta alltid är negativ).

När agenter har kardinalitetsbegränsningar (dvs. för varje kategori av objekt finns det en övre gräns för antalet objekt som varje agent får från denna kategori), kan avundsgrafalgoritmen misslyckas. Men att kombinera det med round-robin-protokollet ger en algoritm som hittar tilldelningar som både är EF1 och som uppfyller kardinalitetsbegränsningarna.

När agenterna har uppdragsvärderingar (alias OXS-värderingar), finns det en utökning av avundsgrafalgoritmen som kallas "Algorithm H", där nästa allokering till en icke avundsvärd agent väljs så att agent-objektets nytta maximeras. Det finns inga formellt bevis för egenskaperna hos denna algoritm, men den klarar sig bra på realistiska data.

Se även

• Avundsfri varufördelning
• Girig nummeruppdelning - kan ses som ett specialfall av avundsgrafalgoritmen för fallet när alla agenter har identiska värderingar.
• Procedur för minskande efterfrågan och underbudsprocedur - två ytterligare procedurer baserade på ordinarie rangordning av buntar.