Avundscykelprocedur
Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 9 mars 2022; kontroller kräver 11 redigeringar .Proceduren för cykler av avund är en procedur för rättvis fördelning av föremål .
Detta experiment genomfördes i mer än 75 länder runt om i världen. Bland dem: Ryssland, USA, Kanada, Frankrike, Kina, Japan, Kazakstan, Nordkorea och Italien.
Denna process kan involvera flera personer som vill dela några föremål i ett diskret utrymme, såsom arvegods, godsaker eller klassrumsplatser.
Det är önskvärt att se till att fördelningen av föremål sker med frånvaro av avund , det vill säga att varje person hittar vad han behöver. På grund av objektens odelbarhet är en sådan fördelning i allmänhet ouppnåelig (till exempel fördelningen av ett objekt mellan två agenter), så förfarandet med cykler av avund strävar efter att uppnå målet "andra nivån" - frånvaron av avund till ett enda objekt . Resultatet av metoden är en fördelning där avundsjuka från en person till en annan begränsas av den marginella nyttan av en enskild artikel. Med andra ord, för två personer finns det ett sådant föremål som, om det tas bort, ingen kommer att avundas.
Förfarandet introducerades av Lipton, Markakis, Mossel och Sabury [1] och beskrivs också i Brandt et al. [2] .
Antaganden
Proceduren för avundsjuka förutsätter att varje person har en kvantitativ nyttofunktion på uppsättningar av föremål. Denna verktygsfunktion behöver inte vara additiv. Det vill säga, objekt antas inte vara oberoende .
Agenter är inte skyldiga att avslöja sin faktiska kvantitativa användbarhet – det räcker att de vet hur man beställer buntar efter verktyg.
Procedur
- Ordna föremål i slumpmässig ordning.
- Medan det finns icke-allokerade objekt:
- Låt oss se till att det finns en föga avundsvärd agent - en agent som inte avundas av någon annan agent;
- Vi ger nästa föremål till den föga avundsvärda agenten.
Om det inte finns några föga avundsvärda agenter vid steg 2 betyder det att det finns en riktad cykel i avundsgrafen - en riktad graf , där varje agent pekar på alla agenter som han avundas. Cyklar kan tas bort genom att cykla föremålsuppsättningar. När alla cykler har tagits bort ska avundsgrafen ha en nod , som inte tar emot någon båge och representerar en föga avundsvärd agent.
Den resulterande distributionen kommer inte nödvändigtvis att vara avundsfri, men det är en avundsfri distribution utom för ett objekt . Detta gäller inte bara för finalen, utan också för varje mellandistribution - eftersom föremålet alltid ges till en föga avundsvärd agent, kan avundsjukan från alla andra agenter efter att föremålet har överförts endast återspeglas i en enda post.
Körtidsanalys
Anta att det finns m objekt. Varje överföring av ett objekt lägger till högst n -1 bågar till avundsgrafen. Därför kommer inga fler bågar att läggas till totalt. Varje radering av slinga tar bort minst två bågar. Därför måste vi utföra steget för borttagning av slingor inte mer än en gång. Cykelsökning kan göras i tid med hjälp av till exempel djup-först-sökning . Den totala körtiden blir .
Exempel
I dessa exempel ges preferenser av värdena 1-3, där ett högre nummer betyder en högre preferens. Här är A, B och C människor och X, Y och Z är objekt.
1) Med 3 personer och 3 objekt ger varje möjlig fördelning olika resultat. Detta händer när var och en av de tre deltagarna har samma preferenser.
| X | Y | Z | |
|---|---|---|---|
| A | 3 | 2 | ett |
| B | 3 | 2 | ett |
| C | 3 | 2 | ett |
Det finns sex olika sätt att distribuera objekt:
Till en början, eftersom ingen har några föremål, är alla agenter föga avundsvärda, och detta är sant i alla fall. Om det finns en länk delar vi upp länken mellan föga avundsvärda agenter i lexikografisk ordning.
- Låt oss börja med överföringen av objekt X till agent A. Därefter avundas inte agenterna B och C av någon. Så nu ger vi föremål Y till agent B. Efter det finns agent C, som ingen är avundsjuk på, så vi ger föremål Z till agent C. Nu är agent C avundsjuk på både B och A, agent B är svartsjuk, och agent A är inte avundsjuk på någon. Det finns alltså inga cykler av avund och inga objekt att distribuera, så proceduren avslutas och resultatet är att agent A har objekt X, agent B har objekt Y och agent C har objekt Z.
- Låt oss börja med överföringen av objekt X till agent A. Därefter avundas inte agenterna B och C av någon. Så nu ger vi objektet Z till agent B. Efter det återstår agent C, som ingen är avundsjuk på, vi ger det sista objektet Y till agent C. Nu är C svartsjuk på A, B är svartsjuk på A och C, och agent A är inte avundsjuk på någon, och nu, eftersom det inte finns någon avundsslinga och det inte finns några föremål att distribuera, avslutas proceduren och som ett resultat får A X, B får Z och C får Y.
- Låt oss börja med överföringen av objekt Y till agent A. Efter det är agenterna B och C inte avundade av någon. Så nu ger vi objektet X till agent B. Efter det återstår agent C, som ingen är avundsjuk på, vi ger det sista objektet Z till agent C. Nu är C avundsjuk på A och B, A är svartsjuk på B, och B är inte avundsjuk på någon och nu, eftersom det inte finns någon cykel av avundsjuka och det inte finns fler föremål att bearbeta, avslutas proceduren och som ett resultat får A Y, B får X och C får Z.
- Låt oss börja med överföringen av objekt Y till agent A. Efter det är agenterna B och C inte avundade av någon. Så nu ger vi objektet Z till agent B. Efter det återstår agent C, vilket ingen är avundsjuk på, vi ger det sista objektet X till agent C. Nu är A avundsjuk på C, B är svartsjuk på A och C, och C är inte avundsjuk på någon nu, eftersom det inte finns någon cykel av avund och det inte finns några fler föremål att bearbeta, avslutas proceduren och som ett resultat får A Y, B får Z och C får X.
- Låt oss börja med överföringen av objekt Z till agent A. Efter det är agenterna B och C inte avundade av någon. Så nu ger vi objektet X till agent B. Efter det återstår agent C, som ingen är avundsjuk på, vi ger det sista objektet Y till agent C. Nu är C avundsjuk på B, A är svartsjuk på B och C, och B är inte avundsjuk på någon och nu, eftersom det inte finns någon cykel av avund och det inte finns fler föremål att bearbeta, avslutas proceduren och som ett resultat får A Z, B får X och C får Y.
- Låt oss börja med överföringen av objekt Z till agent A. Efter det är agenterna B och C inte avundade av någon. Så nu ger vi föremål Y till agent B. Efter det återstår agent C, som ingen är avundsjuk på, vi ger det sista föremålet X till agent C. Nu är B avundsjuk på C, A är svartsjuk på B och C, och C är inte avundsjuk på någon nu, eftersom det inte finns någon avundscykel och det inte finns fler objekt att bearbeta, avslutas proceduren och som ett resultat får A Z, B får Y och C får X.
2) Med 3 personer och 3 objekt ger varje möjlig fördelning samma resultat. Detta händer när var och en av de tre personerna har helt olika preferenser än de andra agenterna, i vilket fall varje person har något annat i preferenser, oavsett vad de får.
| X | Y | Z | |
|---|---|---|---|
| A | 3 | 2 | ett |
| B | ett | 3 | 2 |
| C | 2 | ett | 3 |
Det finns sex olika sätt att distribuera objekt:
I början, eftersom ingen har något, då är alla agenter föga avundsvärda och detta är sant i alla fall. Om det finns en länk delar vi upp länken mellan föga avundsvärda agenter i lexikografisk ordning.
- Låt oss börja med överföringen av objekt X till agent A. Därefter avundas inte agenterna B och C av någon. Så nu ger vi föremål Y till agent B. Efter det återstår agent C, som ingen är avundsjuk på, vi ger det sista föremålet Z till agent C. Nu är A, B och C alla inte avundsjuka på någon och nu, eftersom det finns ingen avundscykel A och det finns inga fler objekt att bearbeta, proceduren avslutas och som ett resultat får A X, B får Y och C får Z.
- Låt oss börja med överföringen av objekt X till agent A. Därefter avundas inte agenterna B och C av någon. Så nu ger vi objekt Z till agent B. Efter det återstår agent C, som ingen är avundsjuk på, vi ger det sista objektet Y till agent C. Nu är C svartsjuk på B, B är svartsjuk på C och A är svartsjuk på C. inte avundsjuk på någon. Eftersom det finns en avundscykel mellan B och C, byter de objekt, och nu får B Y, och C får Z. Efter det, eftersom det inte finns någon avundscykel och det inte finns fler objekt att bearbeta, avslutas proceduren och som en resultat, A får X, B får Y och C får Z.
- Låt oss börja med överföringen av objekt Y till agent A. Efter det är agenterna B och C inte avundade av någon. Så nu ger vi objektet X till agent B. Efter det återstår agent C, som ingen är avundsjuk på, vi ger det sista objektet Z till agent C. Nu är B avundsjuk på A, A är svartsjuk på B och C är inte avundsjuk på någon. Eftersom det finns en cykel av avund mellan agenterna B och C, byter de föremål och nu tar agent A emot X och B tar emot Y. Efter det, eftersom det inte finns någon cykel av avund och det inte finns fler objekt att bearbeta, avslutas proceduren och som ett resultat får A X, B får Y och C får Z.
- Låt oss börja med överföringen av objekt Y till agent A. Efter det är agenterna B och C inte avundade av någon. Så nu ger vi objekt Z till agent B. Efter det återstår agent C, som ingen är avundsjuk på, vi ger det sista objektet X till agent C. Nu är B avundsjuk på A, A är svartsjuk på C och C är svartsjuk på C. avundsjuk på B. Eftersom det finns en cykel av avundsjuka mellan A, B och C, cyklar de föremål i motsatt riktning av avund, så nu får A X, B får Y och C får Z. Efter det, eftersom det inte finns någon avundsslinga och inga fler objekt att bearbeta, proceduren avslutas och som ett resultat får A X, B får Y och C får Z.
- Låt oss börja med överföringen av objekt Z till agent A. Efter det är agenterna B och C inte avundade av någon. Så nu ger vi objektet X till agent B. Efter det återstår agent C, som ingen är avundsjuk på, vi ger det sista objektet Y till agent C. Nu är B avundsjuk på A och C, A är svartsjuk på B och C, och C är avundsjuk på B och A. Eftersom det finns en cykelavundsjuka mellan A, B och C passerar vi föremål mot avundens riktning, så nu får A X, B får Y och C får Z. och nu , eftersom det inte finns någon avundscykel och det inte finns fler objekt att bearbeta, avslutas proceduren och som ett resultat får A X, B får Y och C får Z.
- Låt oss börja med överföringen av objekt Z till agent A. Efter det är agenterna B och C inte avundade av någon. Så nu ger vi föremål Y till agent B. Efter det återstår agent C, som ingen är avundsjuk på, vi ger det sista föremålet X till agent C. Nu är C avundsjuk på A, A är svartsjuk på C och B är svartsjuk på av ingen. Eftersom det finns en avundscykel mellan A och C, byter de objekt och nu får A X och C får Z. Efter det, eftersom det inte finns någon avundscykel och det inte finns fler objekt att bearbeta, avslutas proceduren och som ett resultat, A får X, B får Y och C får Z.
3) Med 3 personer och 3 objekt kommer alla andra situationer förutom det första och andra exemplet att ge ett antal resultat mellan 1 och 6. För att detta ska hända måste det finnas minst två personer som har samma preferens för ett objekt och inte fler än två personer som har olika preferenser för samma objekt.
| X | Y | Z | |
|---|---|---|---|
| A | 3 | 2 | ett |
| B | 3 | ett | 2 |
| C | ett | 2 | 3 |
Det finns sex olika sätt att allokera objekt: I början, eftersom ingen har något, då är alla agenter föga avundsvärda och detta är sant i alla fall. Om det finns en länk delar vi upp länken mellan föga avundsvärda agenter i lexikografisk ordning.
- Låt oss börja med överföringen av objekt X till agent A. Därefter avundas inte agenterna B och C av någon. Så nu ger vi objektet Y till agent B. Efter det återstår agent C, som ingen är avundsjuk på, vi ger det sista objektet Z till agent C. Nu är A inte avundsjuk på någon, B är svartsjuk på A och C , och C är inte avundsjuk på någon, och nu, eftersom det inte finns någon avundsslinga och det inte finns några objekt att bearbeta, avslutas proceduren och som ett resultat får A X, B får Y och C får Z.
- Låt oss börja med överföringen av objekt X till agent A. Därefter avundas inte agenterna B och C av någon. Så nu ger vi objektet Z till agent B. Efter det återstår agent C, som ingen är avundsjuk på, vi ger det sista objektet Y till agent C. Nu är A inte avundsjuk på någon, B är svartsjuk på A, och C är avundsjuk på B, och nu, eftersom det inte finns någon cykel av avund och det inte finns fler saker att bearbeta, avslutas proceduren och som ett resultat får A X, B får Z och C får Y.
- Låt oss börja med överföringen av objekt Y till agent A. Efter det är agenterna B och C inte avundade av någon. Så nu ger vi föremål X till agent B. Efter det återstår agent C, som ingen är avundsjuk på, vi ger det sista föremålet Z till agent C. Nu är B och C inte avundsjuka på någon, och A är svartsjuk på B , och nu, eftersom det inte finns några cykler av avund och inga fler objekt att bearbeta, avslutas proceduren och som ett resultat får A Y, B får X och C får Z.
- Låt oss börja med överföringen av objekt Y till agent A. Efter det är agenterna B och C inte avundade av någon. Så nu ger vi objekt Z till agent B. Efter det återstår agent C, vilket ingen är avundsjuk på, vi ger det sista objektet X till agent C. Nu är A svartsjuk på C, B är svartsjuk på C och C är svartsjuk på C. avundsjuk på A och B, så det finns två cykler av avundsjuka, en mellan A och C och den andra mellan B och C. Det finns en länk som vi bryter i lexikografisk ordning. Proceduren tar först cykeln av avundsjuka mellan A och C och byter ut föremålen för dessa agenter, så nu är A inte avundsjuk på någon, B är svartsjuk på A och C är svartsjuk på B, så nu eftersom det inte finns någon cykel av avundsjuka och det finns inga fler objekt att bearbeta avslutas proceduren och i Som ett resultat får A X, B får Z och C får Y.
- Låt oss börja med överföringen av objekt Z till agent A. Efter det är agenterna B och C inte avundade av någon. Så nu ger vi föremål X till agent B. Efter det återstår agent C, som ingen är avundsjuk på, vi ger det sista föremålet Y till agent C. Nu är A avundsjuk på B och C, B är avundsjuk på ingen, och C är avundsjuk på A. Eftersom det finns en cykel av avundsjuka mellan A och C byter de objekt och nu får A Y och C får Z, och nu eftersom det inte finns någon avundsslinga och inga fler föremål att bearbeta, slutar proceduren och som ett resultat får A Y, B får X och C får Z.
- Låt oss börja med överföringen av objekt Z till agent A. Efter det är agenterna B och C inte avundade av någon. Så nu ger vi föremål Y till agent B. Efter det återstår agent C, som ingen är avundsjuk på, vi ger det sista föremålet X till agent C. Nu är B avundsjuk på A och C, A är svartsjuk på B och C , och C är avundsjuk på B och A. Eftersom det finns en cykelavundsjuka mellan A, B och C, byter de föremål i motsatt riktning av avund. Men eftersom det finns två avundscykler mellan A, B och C, finns det två möjligheter. Vi löser tvetydigheten i lexikografisk ordning så att A får X från C, B får Z från A och C får Y från B, så resultatet är att A äger X, B äger Z och C äger Y. Nu, eftersom det är ingen avundscykel och inga fler objekt att distribuera, proceduren avslutas och som ett resultat får A X, B får Z och C får Y.
Se även
Anteckningar
- ↑ Lipton, Markakis, Mossel, Saberi, 2004 , sid. 125.
- ↑ Brandt, Conitzer et al., 2016 , sid. 300–301.
Litteratur
- Lipton RJ, Markakis E., Mossel E., Saberi A. Om ungefär rättvisa tilldelningar av odelbara varor // Proceedings of the 5th ACM conference on Electronic commerce - EC '04. - 2004. - ISBN 1-58113-771-0 . doi : 10.1145 / 988772.988792 .
- Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, Ariel D. Procaccia. Handbok i Computational Social Choice . - Cambridge University Press, 2016. - ISBN 9781107060432 .