Procedura Ciclului Invidiei

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 9 martie 2022; verificările necesită 11 modificări .

Procedura ciclurilor de invidie  este o procedură de distribuire corectă a obiectelor .

Acest experiment a fost realizat în peste 75 de țări din întreaga lume. Printre acestea: Rusia, SUA, Canada, Franța, China, Japonia, Kazahstan, Coreea de Nord și Italia.

Acest proces poate implica mai multe persoane care doresc să împartă unele articole într-un spațiu discret , cum ar fi moșteniri, tratări sau locuri în clasă.

Este de dorit să vă asigurați că distribuția obiectelor are loc cu absența invidiei , adică că fiecare persoană găsește ceea ce are nevoie. Datorită indivizibilității obiectelor, o astfel de distribuție este în general de neatins (de exemplu, distribuția unui obiect între doi agenți), astfel încât procedura ciclurilor de invidie urmărește să atingă obiectivul de „al doilea nivel” - absența invidiei. la un singur obiect . Rezultatul metodei este o distribuție în care invidia unei persoane față de alta este limitată de utilitatea marginală a unui singur articol. Cu alte cuvinte, pentru oricare doi oameni există un astfel de obiect pe care, dacă este îndepărtat, nimeni nu îl va invidia.

Procedura a fost introdusă de Lipton, Markakis, Mossel și Sabury [1] și este descrisă și în Brandt și colab. [2] .

Ipoteze

Procedura ciclurilor invidiei presupune că fiecare persoană are o funcție de utilitate cantitativă pe seturi de articole. Această funcție de utilitate nu trebuie să fie aditivă. Adică, elementele nu sunt considerate a fi independente .

Agenții nu sunt obligați să-și dezvăluie utilitatea cantitativă reală – este suficient ca ei să știe cum să comande pachetele în funcție de utilitate.

Procedura

  1. Aranjați articolele în ordine aleatorie.
  2. În timp ce există articole nealocate:
    • Să ne asigurăm că există un agent de neinvidiat  - un agent care nu este invidiat de niciun alt agent;
    • Dăm următorul articol agentului de neinvidiat.

Dacă nu există agenți de neinvidiat la pasul 2, aceasta înseamnă că există un ciclu direcționat în graficul invidiei  - un grafic direcționat , în care fiecare agent indică toți agenții pe care îi invidiază. Ciclurile pot fi eliminate prin ciclism seturi de articole. Când toate ciclurile sunt eliminate, graficul de invidie ar trebui să aibă un nod , care nu primește niciun arc și reprezintă un agent de neinvidiat.

Distribuția rezultată nu va fi neapărat fără invidie, dar este o distribuție fără invidie, cu excepția unui articol . Acest lucru este valabil nu numai pentru distribuția finală, ci și pentru fiecare distribuție intermediară - deoarece articolul este întotdeauna dat unui agent de neinvidiat, invidia tuturor celorlalți agenți după ce articolul este transferat poate fi reflectată doar într-un singur articol.

Analiza timpului de rulare

Să presupunem că există m articole. Fiecare transfer al unui element adaugă cel mult n -1 arce graficului de invidie. Prin urmare, nu se vor adăuga mai multe arcuri în total. Fiecare ștergere a buclei elimină cel puțin două arce. Prin urmare, trebuie să efectuăm etapa de eliminare a buclei nu mai mult de o dată. Căutarea ciclului poate fi efectuată în timp , utilizând, de exemplu, căutarea în profunzime . Durata totală de rulare va fi .

Exemple

În aceste exemple, preferințele sunt date de valorile 1-3, unde un număr mai mare înseamnă o preferință mai mare. Aici A, B și C sunt oameni și X, Y și Z sunt obiecte.

1) Cu 3 persoane și 3 obiecte, fiecare distribuție posibilă dă rezultate diferite. Acest lucru se întâmplă atunci când fiecare dintre cei trei participanți are aceleași preferințe.

6 rezultate diferite
X Y Z
A 3 2 unu
B 3 2 unu
C 3 2 unu

Există șase moduri diferite de a distribui obiecte:

Inițial, deoarece nimeni nu posedă niciun obiect, toți agenții sunt de neinvidiat, iar acest lucru este adevărat în toate cazurile. Dacă există o legătură, împărțim legătura dintre agenții de neinvidiat în ordine lexicografică.

  1. Să începem cu transferul articolului X către agentul A. După aceea, agenții B și C nu sunt invidiați de nimeni. Deci acum dăm elementul Y agentului B. După aceea, există agentul C, pe care nimeni nu este gelos, așa că dăm elementul Z agentului C. Acum agentul C este gelos atât pe B cât și pe A, agentul B este gelos, iar agentul A nu este gelos pe nimeni. Astfel, nu există cicluri de invidie și nici obiecte de distribuit, așa că procedura se încheie și rezultatul este că agentul A are elementul X, agentul B are elementul Y și agentul C are elementul Z.
  2. Să începem cu transferul articolului X către agentul A. După aceea, agenții B și C nu sunt invidiați de nimeni. Deci acum dăm obiectul Z agentului B. După aceea, rămâne agentul C, pe care nimeni nu este gelos, dăm ultimul obiect Y agentului C. Acum C este gelos pe A, B este gelos pe A și C, iar agentul A nu este gelos pe nimeni, iar acum, din moment ce nu există o buclă de invidie și nu există obiecte de distribuit, procedura se termină și, ca rezultat, A primește X, B primește Z și C primește Y.
  3. Să începem cu transferul articolului Y către agentul A. După aceea, agenții B și C nu sunt invidiați de nimeni. Deci acum dăm obiectul X agentului B. După aceea, rămâne agentul C, pe care nimeni nu este gelos, dăm ultimul obiect Z agentului C. Acum C este gelos pe A și B, A este gelos pe B, iar B nu este gelos pe nimeni și acum, deoarece nu există un ciclu de invidie și nu mai sunt obiecte de procesat, procedura se termină și, ca urmare, A obține Y, B primește X și C primește Z.
  4. Să începem cu transferul articolului Y către agentul A. După aceea, agenții B și C nu sunt invidiați de nimeni. Deci acum dăm elementul Z agentului B. După aceea, agentul C rămâne, pe care nimeni nu este gelos, dăm ultimul obiect X agentului C. Acum A este gelos pe C, B este gelos pe A și C, iar C nu este gelos pe nimeni acum, deoarece nu există un ciclu de invidie și nu mai sunt obiecte de procesat, procedura se termină și, ca rezultat, A primește Y, B primește Z și C primește X.
  5. Să începem cu transferul articolului Z către agentul A. După aceea, agenții B și C nu sunt invidiați de nimeni. Deci acum dăm obiectul X agentului B. După aceea, rămâne agentul C, pe care nimeni nu este gelos, dăm ultimul obiect Y agentului C. Acum C este gelos pe B, A este gelos pe B și C, iar B nu este gelos pe nimeni și acum, deoarece nu există un ciclu de invidie și nu mai sunt obiecte de procesat, procedura se termină și, ca urmare, A primește Z, B primește X și C primește Y.
  6. Să începem cu transferul articolului Z către agentul A. După aceea, agenții B și C nu sunt invidiați de nimeni. Deci acum dăm elementul Y agentului B. După aceea, rămâne agentul C, pe care nimeni nu este gelos, dăm ultimul obiect X agentului C. Acum B este gelos pe C, A este gelos pe B și C și C nu este gelos pe nimeni acum, deoarece nu există un ciclu de invidie și nu mai sunt obiecte de procesat, procedura se termină și, ca urmare, A primește Z, B primește Y și C primește X.

2) Cu 3 persoane și 3 obiecte, fiecare distribuție posibilă dă același rezultat. Acest lucru se întâmplă atunci când fiecare dintre cele trei persoane are preferințe complet diferite față de ceilalți agenți, caz în care fiecare persoană are ceva diferit în preferință, indiferent de ce primește.

Același rezultat
X Y Z
A 3 2 unu
B unu 3 2
C 2 unu 3

Există șase moduri diferite de a distribui obiecte:

La început, din moment ce nimeni nu are nimic, atunci toți agenții sunt de neinvidiat și acest lucru este adevărat în toate cazurile. Dacă există o legătură, împărțim legătura dintre agenții de neinvidiat în ordine lexicografică.

  1. Să începem cu transferul articolului X către agentul A. După aceea, agenții B și C nu sunt invidiați de nimeni. Deci acum dăm elementul Y agentului B. După aceea, rămâne agentul C, pe care nimeni nu este gelos, dăm ultimul obiect Z agentului C. Acum A, B și C nu sunt cu toții gelosi pe nimeni și acum, din moment ce nu există ciclul de invidie A și nu mai sunt obiecte de prelucrat, procedura se termină și, ca urmare, A primește X, B primește Y și C primește Z.
  2. Să începem cu transferul articolului X către agentul A. După aceea, agenții B și C nu sunt invidiați de nimeni. Deci acum dăm obiectul Z agentului B. După aceea, rămâne agentul C, pe care nimeni nu este gelos, dăm ultimul obiect Y agentului C. Acum C este gelos pe B, B este gelos pe C și A este nu gelos pe nimeni. Întrucât există un ciclu de invidie între B și C, ei fac schimb de obiecte, iar acum B primește Y, iar C primește Z. După aceea, deoarece nu există niciun ciclu de invidie și nu mai sunt obiecte de procesat, procedura se încheie și ca un rezultat, A obține X, B primește Y și C primește Z.
  3. Să începem cu transferul articolului Y către agentul A. După aceea, agenții B și C nu sunt invidiați de nimeni. Deci acum dăm obiectul X agentului B. După aceea, rămâne agentul C, pe care nimeni nu este gelos, dăm ultimul obiect Z agentului C. Acum B este gelos pe A, A este gelos pe B și C. nu este gelos pe nimeni. Întrucât există un ciclu de invidie între agenții B și C, aceștia fac schimb de articole și acum agentul A primește X și B primește Y. După aceea, deoarece nu există un ciclu de invidie și nu mai sunt obiecte de procesat, procedura se încheie și ca urmare, A primește X, B primește Y și C primește Z.
  4. Să începem cu transferul articolului Y către agentul A. După aceea, agenții B și C nu sunt invidiați de nimeni. Deci acum dăm elementul Z agentului B. După aceea, rămâne agentul C, pe care nimeni nu este gelos, dăm ultimul obiect X agentului C. Acum B este gelos pe A, A este gelos pe C și C este gelos pe B. Deoarece există un ciclu de invidie între A, B și C, ele ciclează obiectele în direcția opusă invidiei, așa că acum A primește X, B primește Y și C primește Z. După aceea, deoarece nu există buclă de invidie și nu mai există obiecte de procesat, procedura se termină și, ca rezultat, A primește X, B primește Y și C primește Z.
  5. Să începem cu transferul articolului Z către agentul A. După aceea, agenții B și C nu sunt invidiați de nimeni. Deci acum dăm obiectul X agentului B. După aceea, rămâne agentul C, pe care nimeni nu este gelos, dăm ultimul obiect Y agentului C. Acum B este gelos pe A și C, A este gelos pe B și C, iar C este gelos pe B și A. Deoarece există un ciclu de invidie între A, B și C, trecem obiectele în direcția invidiei, așa că acum A primește X, B primește Y și C primește Z. și acum , deoarece nu există un ciclu de invidie și nu mai sunt obiecte de procesat, procedura se termină și, ca rezultat, A obține X, B primește Y și C primește Z.
  6. Să începem cu transferul articolului Z către agentul A. După aceea, agenții B și C nu sunt invidiați de nimeni. Deci acum dăm elementul Y agentului B. După aceea, rămâne agentul C, pe care nimeni nu este gelos, dăm ultimul obiect X agentului C. Acum C este gelos pe A, A este gelos pe C și B este gelos de nimeni. Întrucât există un ciclu de invidie între A și C, ei fac schimb de obiecte și acum A primește X și C primește Z. După aceea, deoarece nu există un ciclu de invidie și nu mai sunt obiecte de procesat, procedura se termină și, ca urmare, A primește X, B primește Y și C primește Z.

3) Cu 3 persoane și 3 obiecte, orice alte situații, altele decât primul și al doilea exemplu, vor da un număr de rezultate între 1 și 6. Pentru ca acest lucru să se întâmple, trebuie să existe cel puțin două persoane care au aceeași preferință pentru un obiect și nu mai mult de două persoane care au preferințe diferite pentru același obiect.

3 rezultate diferite
X Y Z
A 3 2 unu
B 3 unu 2
C unu 2 3

Există șase moduri diferite de a aloca obiecte: La început, deoarece nimeni nu are nimic, atunci toți agenții sunt de neinvidiat și acest lucru este adevărat în toate cazurile. Dacă există o legătură, împărțim legătura dintre agenții de neinvidiat în ordine lexicografică.

  1. Să începem cu transferul articolului X către agentul A. După aceea, agenții B și C nu sunt invidiați de nimeni. Deci acum dăm obiectul Y agentului B. După aceea, rămâne agentul C, pe care nimeni nu este gelos, dăm ultimul obiect Z agentului C. Acum A nu este gelos pe nimeni, B este gelos pe A și C. , iar C nu este gelos pe nimeni, iar acum, din moment ce nu există o buclă de invidie și nu există obiecte de procesat, procedura se termină și, ca rezultat, A obține X, B primește Y și C primește Z.
  2. Să începem cu transferul articolului X către agentul A. După aceea, agenții B și C nu sunt invidiați de nimeni. Deci acum dăm obiectul Z agentului B. După aceea, rămâne agentul C, pe care nimeni nu este gelos, dăm ultimul obiect Y agentului C. Acum A nu este gelos pe nimeni, B este gelos pe A și C este gelos pe B și acum, deoarece nu există un ciclu de invidie și nu mai sunt elemente de procesat, procedura se termină și, ca rezultat, A primește X, B primește Z și C primește Y.
  3. Să începem cu transferul articolului Y către agentul A. După aceea, agenții B și C nu sunt invidiați de nimeni. Deci acum dăm elementul X agentului B. După aceea, rămâne agentul C, pe care nimeni nu este gelos, dăm ultimul obiect Z agentului C. Acum B și C nu sunt gelosi pe nimeni, iar A este gelos pe B. , iar acum, deoarece nu există cicluri de invidie și nu mai există elemente de procesat, procedura se termină și, ca rezultat, A obține Y, B primește X și C primește Z.
  4. Să începem cu transferul articolului Y către agentul A. După aceea, agenții B și C nu sunt invidiați de nimeni. Deci acum dăm elementul Z agentului B. După aceea, agentul C rămâne, pe care nimeni nu este gelos, dăm ultimul obiect X agentului C. Acum A este gelos pe C, B este gelos pe C și C este gelos pe A și B, deci sunt două cicluri de invidie, unul între A și C și celălalt între B și C. Există o legătură pe care o rupem în ordine lexicografică. Procedura ia mai întâi ciclul invidiei dintre A și C și schimbă obiectele acestor agenți, așa că acum A nu este gelos pe nimeni, B este gelos pe A și C este gelos pe B, deci acum, din moment ce nu există un ciclu de invidie și nu mai sunt obiecte de procesat, procedura se termină și în rezultat, A obține X, B primește Z și C primește Y.
  5. Să începem cu transferul articolului Z către agentul A. După aceea, agenții B și C nu sunt invidiați de nimeni. Deci acum dăm elementul X agentului B. După aceea, rămâne agentul C, pe care nimeni nu este gelos, dăm ultimul obiect Y agentului C. Acum A este gelos pe B și C, B nu este gelos pe nimeni, iar C este gelos pe A. Deoarece există un ciclu de invidie între A și C, ei schimbă obiecte și acum A primește Y și C primește Z, iar acum, deoarece nu există nicio buclă de invidie și nu mai există elemente de procesat, procedura se încheie și ca rezultat A obține Y, B devine X și C primește Z.
  6. Să începem cu transferul articolului Z către agentul A. După aceea, agenții B și C nu sunt invidiați de nimeni. Deci acum dăm elementul Y agentului B. După aceea, rămâne agentul C, pe care nimeni nu este gelos, dăm ultimul obiect X agentului C. Acum B este gelos pe A și C, A este gelos pe B și C , iar C este gelos pe B și A. Întrucât există o invidie de ciclu între A, B și C, ei schimbă obiecte în direcția opusă invidiei. Cu toate acestea, deoarece există 2 cicluri de invidie între A, B și C, există două posibilități. Rezolvăm ambiguitatea în ordine lexicografică, astfel încât A să obțină X de la C, B să primească Z de la A și C să obțină Y de la B, deci rezultatul este, A deține X, B deține Z și C deține Y. Acum, deoarece există Nu există un ciclu de invidie și nu mai există obiecte de distribuit, procedura se termină și, ca rezultat, A primește X, B primește Z și C primește Y.

Vezi și

Note

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

Literatură