Envy Cycle eljárás

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2022. március 9-én felülvizsgált verziótól ; az ellenőrzések 11 szerkesztést igényelnek .

Az irigység ciklusainak  eljárása a tárgyak igazságos elosztásának eljárása .

Ezt a kísérletet a világ több mint 75 országában végezték el. Köztük: Oroszország, USA, Kanada, Franciaország, Kína, Japán, Kazahsztán, Észak-Korea és Olaszország.

Ebben a folyamatban több személy is részt vehet, akik meg akarnak osztani bizonyos tárgyakat egy különálló helyen, például örökségeket, finomságokat vagy osztálytermi ülőhelyeket.

Kívánatos gondoskodni arról, hogy a tárgyak elosztása irigység nélkül történjen , vagyis mindenki megtalálja, amire szüksége van. A tárgyak oszthatatlansága miatt az ilyen megoszlás általában elérhetetlen (például egy tárgy elosztása két ügynök között), ezért az irigység ciklusainak eljárása a „második szintű” cél elérésére törekszik - az irigység hiányára. egyetlen tárgyra . A módszer eredménye egy olyan elosztás, amelyben az egyik személy irigységét a másikra korlátozza egyetlen tétel határhaszna. Más szóval, bármely két ember számára van egy olyan tárgy, amelyet ha eltávolítanak, senki sem irigyel.

Az eljárást Lipton, Markakis, Mossel és Sabury vezette be [1] , és Brandt és munkatársai [2] is leírták .

Feltételezések

Az irigység ciklusa azt feltételezi, hogy minden személynek van mennyiségi hasznossági függvénye az elemek halmazán. Ennek a segédfunkciónak nem kell additívnak lennie. Vagyis az elemeket nem feltételezzük függetlennek .

Az ügynököknek nem kell nyilvánosságra hozniuk tényleges mennyiségi hasznosságukat – elegendő, ha tudják, hogyan rendelhetik meg a kötegeket közüzemenként.

Eljárás

  1. Rendezd az elemeket véletlenszerű sorrendbe.
  2. Bár vannak kiosztatlan elemek:
    • Gondoskodjunk arról, hogy legyen irigylésre méltó ügynök  – olyan ügynök, akit más ügynök nem irigyel;
    • A következő tételt az irigylésre méltó ügynöknek adjuk.

Ha a 2. lépésben nincsenek irigylésre méltó ügynökök, ez azt jelenti, hogy van egy irányított ciklus az irigységgráfban  – egy irányított gráfban , ahol minden ügynök az összes irigyelt ügynökre mutat. A ciklusok a cikkkészletek kerékpározásával eltávolíthatók. Ha az összes ciklust eltávolítjuk, az irigység gráfnak rendelkeznie kell egy csomóponttal , amely nem kap semmilyen ívet , és irigylésre méltó ügynököt képvisel.

Az így létrejövő disztribúció nem feltétlenül irigységmentes, de egy tétel kivételével irigységmentes terjesztés . Ez nem csak a végső, hanem minden közbenső elosztásra is igaz - mivel a tárgyat mindig egy irigylésre méltó ügynöknek adják, az összes többi ügynök irigysége az áru átadása után csak egyetlen tételben tükröződhet.

Futási idő elemzés

Tegyük fel, hogy m elem van. Egy elem minden egyes átvitele legfeljebb n -1 ívet ad az irigységgráfhoz. Ezért összesen nem adunk hozzá több ívet. Minden huroktörlés legalább két ívet eltávolít. Ezért a hurok eltávolítási lépést legfeljebb egyszer kell végrehajtanunk. A cikluskeresés elvégezhető időben , például a mélységi keresés segítségével . A teljes futási idő .

Példák

Ezekben a példákban a preferenciákat 1-3 értékkel adjuk meg, ahol a nagyobb szám magasabb preferenciát jelent. Itt A, B és C emberek, X, Y és Z pedig tárgyak.

1) 3 ember és 3 objektum esetén minden lehetséges elosztás más és más eredményt hoz. Ez akkor történik, ha a három résztvevő mindegyikének ugyanazok a preferenciái.

6 különböző eredmény
x Y Z
A 3 2 egy
B 3 2 egy
C 3 2 egy

Hat különböző módja van az objektumok elosztásának:

Kezdetben, mivel senkinek sincs semmi tárgya, minden ügynök irigylésre méltó, és ez minden esetben igaz. Ha van kapcsolat, akkor lexikográfiai sorrendben felosztjuk a kapcsolatot az irigylésre méltó ügynökök között.

  1. Kezdjük az X tétel A ügynöknek való átadásával. Ezt követően B és C ügynököt nem irigyeli senki. Tehát most Y tételt adunk B ügynöknek. Utána van C ügynök, akire senki nem féltékeny, ezért a Z tételt adjuk C ügynöknek. Most C ügynök féltékeny B-re és A-ra, B ügynök féltékeny, és A ügynök nem féltékeny senkire. Így nincsenek az irigység ciklusai és nincsenek kiosztandó tárgyak, így az eljárás véget ér, és az eredmény az, hogy az A ügynöknek X, B ügynöknek Y, C ügynöknek pedig Z eleme van.
  2. Kezdjük az X tétel A ügynöknek való átadásával. Ezt követően B és C ügynököt nem irigyeli senki. Tehát most a Z tárgyat adjuk B ügynöknek. Ezután marad C ügynök, akire senki sem féltékeny, az utolsó Y tárgyat adjuk C ügynöknek. Most C féltékeny A-ra, B féltékeny A-ra és C-re, és A ügynök nem féltékeny senkire, és most, mivel nincs irigységhurok, és nincsenek kiosztandó tárgyak, az eljárás véget ér, és ennek eredményeként A kap X, B Z, C pedig Y.
  3. Kezdjük az Y tétel A ügynöknek való átadásával. Ezt követően B és C ügynököt senki sem irigyeli. Tehát most az X tárgyat adjuk B ügynöknek. Utána marad C ügynök, akire senki nem féltékeny, az utolsó Z tárgyat C ügynöknek adjuk. Most C féltékeny A-ra és B-re, A féltékeny B-re, és B nem irigy senkire és most, mivel nincs irigység körforgása és nincs több feldolgozandó tárgy, az eljárás véget ér, és ennek eredményeként A kap Y-t, B X-et, C pedig Z-t.
  4. Kezdjük az Y tétel A ügynöknek való átadásával. Ezt követően B és C ügynököt senki sem irigyeli. Tehát most a Z elemet adjuk B ügynöknek. Utána C ügynök marad, amire senki nem féltékeny, az utolsó X tárgyat a C ügynöknek adjuk. Most A féltékeny C-re, B féltékeny A-ra és C-re, és C most nem irigy senkire, mivel nincs irigység körforgása, és nincs több feldolgozandó tárgy, az eljárás véget ér, és ennek eredményeként A kap Y-t, B-t Z, C pedig X-et.
  5. Kezdjük a Z tétel A ügynöknek való átadásával. Ezt követően B és C ügynököt senki sem irigyeli. Tehát most az X tárgyat adjuk B ügynöknek. Utána marad C ügynök, akire senki nem féltékeny, az utolsó Y tárgyat adjuk C ügynöknek. Most C féltékeny B-re, A féltékeny B-re és C-re, és B nem irigy senkire és most, mivel nincs irigység körforgása és nincs több feldolgozandó tárgy, az eljárás véget ér, és ennek eredményeként A kap Z-t, B X-et, C pedig Y-t.
  6. Kezdjük a Z tétel A ügynöknek való átadásával. Ezt követően B és C ügynököt senki sem irigyeli. Tehát most Y tételt adunk B ügynöknek. Ezután marad C ügynök, akire senki nem féltékeny, az utolsó X tárgyat a C ügynöknek adjuk. Most B féltékeny C-re, A féltékeny B-re és C-re, és C most nem irigy senkire, mivel nincs irigység körforgása és nincs több feldolgozandó tárgy, az eljárás véget ér, és ennek eredményeként A kap Z-t, B-t Y, C pedig X-et.

2) 3 ember és 3 objektum esetén minden lehetséges elosztás ugyanazt az eredményt adja. Ez akkor fordul elő, ha mind a három embernek teljesen más preferenciái vannak, mint a többi ágensnek, ebben az esetben minden személy mást preferál, függetlenül attól, hogy mit kap.

Ugyanaz az eredmény
x Y Z
A 3 2 egy
B egy 3 2
C 2 egy 3

Hat különböző módja van az objektumok elosztásának:

Kezdetben, mivel senkinek nincs semmije, aztán minden ügynök irigylésre méltó és ez minden esetben igaz. Ha van kapcsolat, akkor lexikográfiai sorrendben felosztjuk a kapcsolatot az irigylésre méltó ügynökök között.

  1. Kezdjük az X tétel A ügynöknek való átadásával. Ezt követően B és C ügynököt nem irigyeli senki. Tehát most Y tételt adunk B ügynöknek. Ezután marad C ügynök, akire senki nem féltékeny, az utolsó Z tárgyat C ügynöknek adjuk. Most A, B és C nem féltékeny senkire, és most, hiszen nincs A irigységciklus és nincs több feldolgozandó objektum, az eljárás véget ér, és ennek eredményeként A X-et, B-t Y, C pedig Z-t kap.
  2. Kezdjük az X tétel A ügynöknek való átadásával. Ezt követően B és C ügynököt nem irigyeli senki. Tehát most Z tárgyat adunk B ügynöknek. Ezután marad C ügynök, akire senki nem féltékeny, az utolsó Y tárgyat a C ügynöknek adjuk. Most C féltékeny B-re, B féltékeny C-re, A pedig nem féltékeny senkire. Mivel B és C között irigységciklus van, objektumokat cserélnek, és most B kap Y-t, C pedig Z-t. Ezt követően, mivel nincs irigységciklus és nincs több feldolgozandó tárgy, az eljárás véget ér, és mint egy eredmény: A X-et, B-t Y-t, C pedig Z-t kap.
  3. Kezdjük az Y tétel A ügynöknek való átadásával. Ezt követően B és C ügynököt senki sem irigyeli. Tehát most az X tárgyat adjuk B ügynöknek. Ezután marad C ügynök, akire senki nem féltékeny, az utolsó Z tárgyat adjuk C ügynöknek. Most B féltékeny A-ra, A féltékeny B-re, C pedig nem féltékeny senkire. Mivel B és C ügynök között irigység ciklus van, cserélnek tárgyakat, és most A ügynök X-et, B pedig Y-t kap. Ezt követően, mivel nincs irigység körforgása, és nincs több feldolgozandó tárgy, az eljárás véget ér és ennek eredményeként A X-et kap, B-t Y, C pedig Z-t.
  4. Kezdjük az Y tétel A ügynöknek való átadásával. Ezt követően B és C ügynököt senki sem irigyeli. Tehát most a Z tételt adjuk B ügynöknek. Ezután marad C ügynök, akire senki nem féltékeny, az utolsó X tárgyat a C ügynöknek adjuk. Most B féltékeny A-ra, A féltékeny C-re, C pedig féltékeny B-re. Mivel A, B és C között az irigység körforgása van, az irigységgel ellentétes irányba mozgatják a tárgyakat, így most A kap X-et, B-t Y-t, C pedig Z-t. Ezek után, mivel nincs irigység ciklus, és nincs több feldolgozandó objektum, az eljárás véget ér, és ennek eredményeként A X-et, B-t Y-t, C pedig Z-t kap.
  5. Kezdjük a Z tétel A ügynöknek való átadásával. Ezt követően B és C ügynököt senki sem irigyeli. Tehát most az X tárgyat adjuk B ügynöknek. Ezután marad C ügynök, akire senki nem féltékeny, az utolsó Y tárgyat adjuk C ügynöknek. Most B féltékeny A-ra és C-re, A féltékeny B-re és C és C féltékeny B-re és A-ra. Mivel A, B és C között egy ciklus irigység van, az irigység irányával ellentétesen haladunk el az objektumok mellett, így most A X-et kap, B-t Y, C pedig Z-t. , mivel nincs irigység ciklus, és nincs több feldolgozandó objektum, az eljárás véget ér, és ennek eredményeként A X-et, B-t Y, C-t pedig Z kapja.
  6. Kezdjük a Z tétel A ügynöknek való átadásával. Ezt követően B és C ügynököt senki sem irigyeli. Tehát most Y elemet adunk B ügynöknek. Ezután marad C ügynök, akire senki nem féltékeny, az utolsó X tárgyat a C ügynöknek adjuk. Most C féltékeny A-ra, A féltékeny C-re, B pedig féltékeny senkitől. Mivel A és C között irigységciklus van, objektumokat cserélnek, és most A X-et, C pedig Z-t kap. Ezt követően, mivel nincs irigységciklus, és nincs több feldolgozandó objektum, az eljárás véget ér, és ennek eredményeként A X-et, B-t Y-t, C pedig Z-t kap.

3) 3 ember és 3 objektum esetén az első és a második példától eltérő helyzetek 1 és 6 közötti számú eredményt adnak. Ahhoz, hogy ez megtörténjen, legalább két embernek azonos preferenciával kell rendelkeznie egy tárgyra, és legfeljebb két embernek van különböző preferenciája ugyanazon tárgy iránt.

3 különböző eredmény
x Y Z
A 3 2 egy
B 3 egy 2
C egy 2 3

Hat különböző módja van az objektumok kiosztásának: Kezdetben, mivel senkinek nincs semmije, aztán minden ügynök irigylésre méltó, és ez minden esetben igaz. Ha van kapcsolat, akkor lexikográfiai sorrendben felosztjuk a kapcsolatot az irigylésre méltó ügynökök között.

  1. Kezdjük az X tétel A ügynöknek való átadásával. Ezt követően B és C ügynököt nem irigyeli senki. Tehát most az Y tárgyat adjuk B ügynöknek. Ezután marad C ügynök, akire senki nem féltékeny, az utolsó Z tárgyat C ügynöknek adjuk. Most A nem féltékeny senkire, B féltékeny A-ra és C-re , és C nem féltékeny senkire, és most, mivel nincs irigységhurok és nincsenek feldolgozandó tárgyak, az eljárás véget ér, és ennek eredményeként A X-et, B-t Y-t, C pedig Z-t kap.
  2. Kezdjük az X tétel A ügynöknek való átadásával. Ezt követően B és C ügynököt nem irigyeli senki. Tehát most a Z tárgyat adjuk B ügynöknek. Ezután marad C ügynök, akire senki nem féltékeny, az utolsó Y tárgyat C ügynöknek adjuk. Most A nem féltékeny senkire, B féltékeny A-ra, és C féltékeny B-re, és most, mivel nincs irigység köre, és nincs több feldolgozandó tétel, az eljárás véget ér, és ennek eredményeként A X-et, B Z-t, C pedig Y-t kap.
  3. Kezdjük az Y tétel A ügynöknek való átadásával. Ezt követően B és C ügynököt senki sem irigyeli. Tehát most X tételt adunk B ügynöknek. Ezután marad C ügynök, akire senki nem féltékeny, az utolsó Z tárgyat a C ügynöknek adjuk. Most B és C nem féltékeny senkire, A pedig B-re. , és most, mivel nincs irigység ciklusa és nincs több feldolgozandó tétel, az eljárás véget ér, és ennek eredményeként A kap Y, B X, C pedig Z.
  4. Kezdjük az Y tétel A ügynöknek való átadásával. Ezt követően B és C ügynököt senki sem irigyeli. Tehát most a Z elemet adjuk B ügynöknek. Ezután marad C ügynök, amire senki nem irigy, az utolsó X tárgyat a C ügynöknek adjuk. Most A féltékeny C-re, B féltékeny C-re, C pedig féltékeny A-ra és B-re, ezért az irigységnek két ciklusa van, az egyik A és C, a másik pedig B és C között. Van egy kapcsolat, amelyet lexikográfiai sorrendben szakítunk meg. Az eljárás először felveszi az irigység ciklusát A és C között, és felcseréli ezen ügynökök tárgyait, így most A nem féltékeny senkire, B féltékeny A-ra és C féltékeny B-re, így most, mivel nincs irigység ciklusa. és nincs több feldolgozandó objektum, az eljárás véget ér és in Ennek eredményeként A X-et, B-t Z-t, C pedig Y-t kap.
  5. Kezdjük a Z tétel A ügynöknek való átadásával. Ezt követően B és C ügynököt senki sem irigyeli. Tehát most X tételt adunk B ügynöknek. Utána marad C ügynök, akire senki nem féltékeny, az utolsó Y tárgyat C ügynöknek adjuk. Most A féltékeny B-re és C-re, B senkire, C pedig féltékeny A-ra. Mivel A és C között irigység van, kicserélik az objektumokat, és most A kap Y-t, C pedig Z-t, és mivel nincs irigységhurok és nincs több feldolgozandó elem, az eljárás véget ér. és ennek eredményeként A kap Y-t, B-t X, C pedig Z-t.
  6. Kezdjük a Z tétel A ügynöknek való átadásával. Ezt követően B és C ügynököt senki sem irigyeli. Így most Y tételt adunk B ügynöknek. Ezután marad C ügynök, akire senki nem féltékeny, az utolsó X tárgyat a C ügynöknek adjuk. Most B féltékeny A-ra és C-re, A féltékeny B-re és C-re , C pedig féltékeny B-re és A-ra. Mivel A, B és C között ciklus irigység van, az irigységgel ellentétes irányban cserélnek tárgyakat. Mivel azonban 2 irigységi ciklus van A, B és C között, két lehetőség van. A kétértelműséget lexikográfiai sorrendben oldjuk fel úgy, hogy A X-et kap C-ből, B-t Z-t A-ból, C pedig Y-t B-ből, így az eredmény az, hogy A birtokolja X, B birtokolja Z, C pedig Y-t. Ha nincs irigységciklus és nincs több kiosztandó tárgy, az eljárás véget ér, és ennek eredményeként A X-et, B-t Z-t, C pedig Y-t kap.

Lásd még

Jegyzetek

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

Irodalom