Envy Cycle Procedure

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 9. marts 2022; checks kræver 11 redigeringer .

Proceduren med misundelsescyklusser  er en procedure for retfærdig fordeling af genstande .

Dette eksperiment blev udført i mere end 75 lande rundt om i verden. Blandt dem: Rusland, USA, Canada, Frankrig, Kina, Japan, Kasakhstan, Nordkorea og Italien.

Denne proces kan involvere flere personer, der ønsker at dele nogle ting i et diskret rum, såsom arvestykker, godbidder eller klasseværelsessæder.

Det er ønskeligt at sikre, at fordelingen af ​​genstande sker med fravær af misundelse , det vil sige, at hver person finder, hvad han har brug for. På grund af objekters udelelighed er en sådan fordeling generelt uopnåelig (for eksempel fordelingen af ​​et objekt mellem to agenter), så proceduren med misundelsescyklusser søger at nå målet på "andet niveau" - fraværet af misundelse op. til et enkelt objekt . Resultatet af metoden er en fordeling, hvor en persons misundelse til en anden begrænses af en enkelt genstands marginale nytte. Med andre ord, for to personer er der sådan en genstand, som ingen vil misunde, hvis den fjernes.

Proceduren blev introduceret af Lipton, Markakis, Mossel og Sabury [1] og er også beskrevet i Brandt et al. [2] .

Antagelser

Proceduren for misundelsescyklusser forudsætter, at hver person har en kvantitativ nyttefunktion på sæt af genstande. Denne hjælpefunktion behøver ikke at være additiv. Det vil sige, at genstande ikke antages at være uafhængige .

Agenter er ikke forpligtet til at oplyse deres faktiske kvantitative nytte - det er tilstrækkeligt, at de ved, hvordan man bestiller bundter efter brug.

Fremgangsmåde

  1. Arranger genstande i tilfældig rækkefølge.
  2. Mens der er ikke-allokerede varer:
    • Lad os sikre os, at der er en lidet misundelsesværdig agent  - en agent, der ikke er misundt af nogen anden agent;
    • Vi giver den næste genstand til den lidet misundelsesværdige agent.

Hvis der ikke er nogen misundelsesværdige agenter i trin 2, betyder det, at der er en rettet cyklus i misundelsesgrafen  - en rettet graf , hvor hver agent peger på alle agenter, som han misunder. Cykler kan fjernes ved at cykle emnesæt. Når alle cyklusser er fjernet, skal misundelsesgrafen have en node , som ikke modtager nogen bue og repræsenterer en ikke misundelsesværdig agent .

Den resulterende distribution vil ikke nødvendigvis være misundelsesfri, men det er en misundelsesfri distribution bortset fra én vare . Dette gælder ikke kun for den endelige, men også for hver mellemdistribution - da varen altid gives til en misundelsesværdig agent, kan misundelsen fra alle andre agenter, efter at varen er overført, kun afspejles i en enkelt vare.

Kørtidsanalyse

Antag, at der er m elementer. Hver overførsel af et element tilføjer højst n -1 buer til misundelsesgrafen. Derfor vil der ikke blive tilføjet flere buer i alt. Hver sløjfesletning fjerner mindst to buer. Derfor skal vi ikke udføre sløjfefjernelsestrinnet mere end én gang. Cyklussøgning kan udføres i tide ved hjælp af for eksempel dybde-først-søgning . Den samlede køretid vil være .

Eksempler

I disse eksempler er præferencer givet ved værdierne 1-3, hvor et højere tal betyder en højere præference. Her er A, B og C mennesker og X, Y og Z er objekter.

1) Med 3 personer og 3 objekter giver enhver mulig fordeling forskellige resultater. Dette sker, når hver af de tre deltagere har de samme præferencer.

6 forskellige resultater
x Y Z
EN 3 2 en
B 3 2 en
C 3 2 en

Der er seks forskellige måder at distribuere objekter på:

I første omgang, da ingen besidder nogen genstande, er alle agenter ikke misundelsesværdige, og det gælder i alle tilfælde. Hvis der er et link, opdeler vi linket mellem misundelsesværdige agenter i leksikografisk rækkefølge.

  1. Lad os starte med overførslen af ​​vare X til agent A. Derefter er agent B og C ikke misundt af nogen. Så nu giver vi vare Y til agent B. Efter det er der agent C, som ingen er jaloux på, så vi giver vare Z til agent C. Nu er agent C jaloux på både B og A, agent B er jaloux, og agent A er ikke jaloux på nogen. Der er således ingen cyklusser af misundelse og ingen objekter at distribuere, så proceduren afsluttes, og resultatet er, at agent A har element X, agent B har element Y, og agent C har element Z.
  2. Lad os starte med overførslen af ​​vare X til agent A. Derefter er agent B og C ikke misundt af nogen. Så nu giver vi objektet Z til agent B. Herefter er agent C tilbage, som ingen er jaloux på, vi giver det sidste objekt Y til agent C. Nu er C jaloux på A, B er jaloux på A og C, og agent A er ikke jaloux på nogen, og nu, da der ikke er nogen misundelsesløkke, og der ikke er nogen objekter at distribuere, afsluttes proceduren, og som et resultat får A X, B får Z, og C får Y.
  3. Lad os starte med overførslen af ​​vare Y til agent A. Derefter er agent B og C ikke misundt af nogen. Så nu giver vi objektet X til agent B. Herefter er agent C tilbage, som ingen er jaloux på, vi giver det sidste objekt Z til agent C. Nu er C jaloux på A og B, A er jaloux på B, og B er ikke jaloux på nogen, og nu, da der ikke er nogen cyklus af misundelse, og der ikke er flere objekter at behandle, afsluttes proceduren, og som et resultat får A Y, B får X, og C får Z.
  4. Lad os starte med overførslen af ​​vare Y til agent A. Derefter er agent B og C ikke misundt af nogen. Så nu giver vi varen Z til agent B. Derefter bliver agent C tilbage, som ingen er jaloux på, vi giver den sidste genstand X til agent C. Nu er A jaloux på C, B er jaloux på A og C, og C er ikke jaloux på nogen nu, da der ikke er nogen cyklus af misundelse, og der ikke er flere objekter at behandle, afsluttes proceduren, og som et resultat får A Y, B får Z, og C får X.
  5. Lad os starte med overførslen af ​​vare Z til agent A. Derefter er agent B og C ikke misundt af nogen. Så nu giver vi objektet X til agent B. Herefter er agent C tilbage, som ingen er jaloux på, vi giver det sidste objekt Y til agent C. Nu er C jaloux på B, A er jaloux på B og C, og B er ikke jaloux på nogen, og nu, da der ikke er nogen cyklus af misundelse, og der ikke er flere objekter at behandle, afsluttes proceduren, og som et resultat får A Z, B får X, og C får Y.
  6. Lad os starte med overførslen af ​​vare Z til agent A. Derefter er agent B og C ikke misundt af nogen. Så nu giver vi vare Y til agent B. Herefter er agent C tilbage, som ingen er jaloux på, vi giver den sidste genstand X til agent C. Nu er B jaloux på C, A er jaloux på B og C, og C er ikke jaloux på nogen nu, da der ikke er nogen misundelsescyklus, og der ikke er flere objekter at behandle, afsluttes proceduren, og som et resultat får A Z, B får Y, og C får X.

2) Med 3 personer og 3 objekter giver enhver mulig fordeling det samme resultat. Dette sker, når hver af de tre personer har helt andre præferencer end de andre agenter, i hvilket tilfælde hver person har noget forskelligt i præference, uanset hvad de får.

Samme resultat
x Y Z
EN 3 2 en
B en 3 2
C 2 en 3

Der er seks forskellige måder at distribuere objekter på:

I begyndelsen, da ingen har noget, så er alle agenter ikke misundelsesværdige, og det gælder i alle tilfælde. Hvis der er et link, opdeler vi linket mellem misundelsesværdige agenter i leksikografisk rækkefølge.

  1. Lad os starte med overførslen af ​​vare X til agent A. Derefter er agent B og C ikke misundt af nogen. Så nu giver vi vare Y til agent B. Herefter er agent C tilbage, som ingen er jaloux på, vi giver den sidste genstand Z til agent C. Nu er A, B og C alle ikke jaloux på nogen og nu, siden der er ingen misundelsescyklus A, og der er ikke flere objekter til behandling, proceduren slutter, og som et resultat får A X, B får Y, og C får Z.
  2. Lad os starte med overførslen af ​​vare X til agent A. Derefter er agent B og C ikke misundt af nogen. Så nu giver vi objekt Z til agent B. Herefter er agent C tilbage, som ingen er jaloux på, vi giver den sidste genstand Y til agent C. Nu er C jaloux på B, B er jaloux på C, og A er jaloux ikke jaloux på nogen. Da der er en misundelsescyklus mellem B og C, udveksler de objekter, og nu får B Y, og C får Z. Efter det, da der ikke er nogen misundelsescyklus, og der ikke er flere objekter at behandle, afsluttes proceduren og som en resultat, A får X, B får Y og C får Z.
  3. Lad os starte med overførslen af ​​vare Y til agent A. Derefter er agent B og C ikke misundt af nogen. Så nu giver vi objektet X til agent B. Herefter er agent C tilbage, som ingen er jaloux på, vi giver det sidste objekt Z til agent C. Nu er B jaloux på A, A er jaloux på B og C er ikke jaloux på nogen. Da der er en cyklus af misundelse mellem agent B og C, udveksler de genstande, og nu modtager agent A X og B modtager Y. Efter det, da der ikke er nogen cyklus af misundelse, og der ikke er flere objekter at behandle, afsluttes proceduren og som et resultat, modtager A X, B får Y og C får Z.
  4. Lad os starte med overførslen af ​​vare Y til agent A. Derefter er agent B og C ikke misundt af nogen. Så nu giver vi vare Z til agent B. Derefter er agent C tilbage, som ingen er jaloux på, vi giver den sidste genstand X til agent C. Nu er B jaloux på A, A er jaloux på C, og C er jaloux jaloux på B. Da der er en cyklus af misundelse mellem A, B og C, cykler de objekter i den modsatte retning af misundelse, så nu får A X, B får Y, og C får Z. Efter det, da der ikke er nogen misundelsesløkke og ikke flere objekter at behandle, afsluttes proceduren, og som et resultat får A X, B får Y, og C får Z.
  5. Lad os starte med overførslen af ​​vare Z til agent A. Derefter er agent B og C ikke misundt af nogen. Så nu giver vi objektet X til agent B. Herefter står agent C tilbage, som ingen er jaloux på, vi giver det sidste objekt Y til agent C. Nu er B jaloux på A og C, A er jaloux på B og C, og C er jaloux på B og A. Da der er en cyklusmisundelse mellem A, B og C, passerer vi objekter mod misundelsens retning, så nu får A X, B får Y, og C får Z. og nu , da der ikke er nogen misundelsescyklus, og der ikke er flere objekter at behandle, afsluttes proceduren, og som et resultat får A X, B får Y, og C får Z.
  6. Lad os starte med overførslen af ​​vare Z til agent A. Derefter er agent B og C ikke misundt af nogen. Så nu giver vi vare Y til agent B. Herefter er agent C tilbage, som ingen er jaloux på, vi giver den sidste genstand X til agent C. Nu er C jaloux på A, A er jaloux på C og B er jaloux af ingen. Da der er en misundelsescyklus mellem A og C, udveksler de objekter, og nu får A X, og C får Z. Efter det, da der ikke er nogen misundelsescyklus, og der ikke er flere objekter at behandle, afsluttes proceduren, og som et resultat, A får X, B får Y, og C får Z.

3) Med 3 personer og 3 objekter vil enhver anden situation end det første og andet eksempel give et antal resultater mellem 1 og 6. For at dette kan ske, skal der være mindst to personer, der har samme præference for et objekt og ikke mere end to personer, der har forskellige præferencer for det samme objekt.

3 forskellige resultater
x Y Z
EN 3 2 en
B 3 en 2
C en 2 3

Der er seks forskellige måder at allokere objekter på: I begyndelsen, da ingen har noget, så er alle agenter ikke misundelsesværdige, og det gælder i alle tilfælde. Hvis der er et link, opdeler vi linket mellem misundelsesværdige agenter i leksikografisk rækkefølge.

  1. Lad os starte med overførslen af ​​vare X til agent A. Derefter er agent B og C ikke misundt af nogen. Så nu giver vi objektet Y til agent B. Herefter er agent C tilbage, som ingen er jaloux på, vi giver den sidste genstand Z til agent C. Nu er A ikke jaloux på nogen, B er jaloux på A og C , og C er ikke jaloux på nogen, og nu, da der ikke er nogen misundelsesløkke, og der ikke er nogen objekter at behandle, afsluttes proceduren, og som et resultat får A X, B får Y, og C får Z.
  2. Lad os starte med overførslen af ​​vare X til agent A. Derefter er agent B og C ikke misundt af nogen. Så nu giver vi objektet Z til agent B. Herefter er agent C tilbage, som ingen er jaloux på, vi giver det sidste objekt Y til agent C. Nu er A ikke jaloux på nogen, B er jaloux på A, og C er jaloux på B, og nu, da der ikke er nogen cyklus af misundelse, og der ikke er flere ting at behandle, afsluttes proceduren, og som et resultat får A X, B får Z, og C får Y.
  3. Lad os starte med overførslen af ​​vare Y til agent A. Derefter er agent B og C ikke misundt af nogen. Så nu giver vi vare X til agent B. Herefter er agent C tilbage, som ingen er jaloux på, vi giver den sidste genstand Z til agent C. Nu er B og C ikke jaloux på nogen, og A er jaloux på B , og nu, da der ikke er nogen cyklusser af misundelse og ikke flere elementer at behandle, afsluttes proceduren, og som et resultat får A Y, B får X, og C får Z.
  4. Lad os starte med overførslen af ​​vare Y til agent A. Derefter er agent B og C ikke misundt af nogen. Så nu giver vi punkt Z til agent B. Derefter forbliver agent C, som ingen er jaloux på, vi giver den sidste genstand X til agent C. Nu er A jaloux på C, B er jaloux på C, og C er jaloux jaloux på A og B, så der er to cyklusser af misundelse, den ene mellem A og C og den anden mellem B og C. Der er et link, som vi bryder i leksikografisk rækkefølge. Proceduren tager først cyklussen af ​​misundelse mellem A og C og udveksler objekterne fra disse agenter, så nu er A ikke jaloux på nogen, B er jaloux på A og C er jaloux på B, så nu, da der ikke er nogen cyklus af misundelse og der ikke er flere objekter at behandle, afsluttes proceduren og i Som et resultat får A X, B får Z, og C får Y.
  5. Lad os starte med overførslen af ​​vare Z til agent A. Derefter er agent B og C ikke misundt af nogen. Så nu giver vi vare X til agent B. Herefter er agent C tilbage, som ingen er jaloux på, vi giver den sidste genstand Y til agent C. Nu er A jaloux på B og C, B er jaloux på ingen, og C er jaloux på A. Da der er en cyklus af misundelse mellem A og C, udveksler de objekter, og nu får A Y og C får Z, og nu, da der ikke er nogen misundelsesløkke og ikke flere emner at behandle, slutter proceduren og som et resultat får A Y, B får X, og C får Z.
  6. Lad os starte med overførslen af ​​vare Z til agent A. Derefter er agent B og C ikke misundt af nogen. Så nu giver vi vare Y til agent B. Herefter er agent C tilbage, som ingen er jaloux på, vi giver den sidste genstand X til agent C. Nu er B jaloux på A og C, A er jaloux på B og C , og C er jaloux på B og A. Da der er en cyklusmisundelse mellem A, B og C, udveksler de objekter i den modsatte retning af misundelse. Men da der er 2 misundelsescyklusser mellem A, B og C, er der to muligheder. Vi løser tvetydigheden i leksikografisk rækkefølge, så A får X fra C, B får Z fra A, og C får Y fra B, så resultatet er, A ejer X, B ejer Z og C ejer Y. Nu, da der er der ingen misundelsescyklus og ikke flere objekter at distribuere, afsluttes proceduren, og som et resultat får A X, B får Z, og C får Y.

Se også

Noter

  1. ↑ Lipton, Markakis, Mossel, Saberi, 2004 , s. 125.
  2. ↑ Brandt, Conitzer et al., 2016 , s. 300-301.

Litteratur