Procedura AL

O procedură AL este o procedură de distribuire corectă a obiectelor între două persoane. Procedura găsește o distribuție a unui subset de obiecte care va fi lipsită de invidie . Mai mult, distribuția rezultată este Pareto eficientă în următorul sens: nu există o distribuție fără invidie care să fie mai bună pentru o persoană și nici mai rea pentru oricare alta.

Procedura AL a fost publicată pentru prima dată de Brahms și Klamler [1] . Mai târziu a fost generalizată de Aziz pentru cazul în care agenții nu pot distinge anumite obiecte după semnificația lor [2] .

Ipoteze

Procedura AL pentru îndeplinirea următoarelor condiții:

• Fiecare persoană poate clasifica articolele de la cel mai bun la cel mai rău (adică fiecare persoană poate oferi o relație strictă de preferințe [3] asupra articolelor).
• Fiecare persoană are o relație de preferință pe seturi de articole care este compatibilă cu extensia adaptivă a comenzii articolelor.

Cerințe

NU este intenționat ca o persoană să-și poată indica preferințele cu privire la seturile de articole. Există multe seturi disponibile și poate fi dificil să compilați o listă completă de preferințe pentru seturile de articole.

Prin urmare, procedura ar trebui să ofere o distribuție fără invidie pentru orice relație de preferință care este în concordanță cu ordinea articolelor și aditivitatea slabă . Cu alte cuvinte, procedura trebuie să returneze o distribuție în care cu siguranță nu va exista invidie (neapărat fără invidie, OBZ-distribution, engleză  neapărat envy-free , NEF) [4] .

Să fie cele două fețe Alice și George. O distribuție este o distribuție OBZ pentru Alice dacă injectarea lui f din articolele lui George în articolele lui Alice este astfel încât pentru fiecare articol x primit de George, Alice preferă elementul f ( x ) în locul articolului x . Distribuția este o distribuție OBZ pentru George dacă proprietatea simetrică este valabilă. O distribuție de articole este o distribuție OBZ dacă este o distribuție OBZ pentru ambii parteneri. Rețineți că în distribuția OBZ, Alice și George primesc același număr de articole.

Alocarea goală este evident o alocare OBZ, dar este foarte ineficientă. Prin urmare, căutăm cea mai „cea mai bună” distribuție dintre toate distribuțiile OBZ. O distribuție OBZ se numește Pareto eficientă dacă nu există o altă distribuție OBZ care să fie mai bună pentru un articol și mai proastă pentru altul.

Procedura BT

Ca o introducere, introducem următoarea procedură simplă de împărțire:

• Pune toate obiectele pe masă.
• În timp ce există elemente pe masă, procedați în felul următor:
  • Participanții sunt rugați să aleagă articolul cel mai preferat dintre articolele de pe masă.
  • Dacă sunt selectate elemente diferite, atunci dăm fiecărui participant articolul selectat și continuăm.
  • Dacă există o potrivire, plasați elementul selectat în „Tema contestată”. Acest articol nu este distribuit.

Această procedură returnează distribuția OBZ. Procedura este foarte simplă, dar nu foarte eficientă, deoarece un număr mare de articole vor fi aruncate în „Mola de concurs”. Procedura AL este puțin mai complicată, dar asigură că Heap-ul contestat nu este niciodată mai mare decât heap-ul rezultat în procedura BT, dar poate fi mai mic.

procedura AL

Procedura AL funcționează asemănător cu procedura BT, dar înainte de a fi trimisă la „Gata contestată”, procedura încearcă să dea articolul unui participant, ca compensație , pentru a-i oferi celuilalt participant un alt articol. Numai în cazul în care o astfel de compensație eșuează, articolul este trimis în „Gata contestată”.

De exemplu, să presupunem că există patru subiecte (1, 2, 3, 4) și preferințele participanților sunt după cum urmează:

• Alice: 1 > 2 > 3 > 4
• George: 2 > 3 > 4 > 1

Procedura BT dă elementul 1 lui Alice și elementul 2 lui George pentru că sunt cele mai de dorit și sunt diferite. Acum, atât Alice, cât și George aleg elementul 3, așa că este aruncat. Acum aleg amândoi elementul 4 și este, de asemenea, aruncat. Distribuție finală: Alice George . Distribuția este o distribuție OBZ, dar nu este eficientă Pareto.

Procedura AL începe, de asemenea, prin a da elementul 1 lui Alice și elementul 2 lui George. Acum, în loc să renunțe la elementul 3, procedura îi dă lui Alice, iar lui George i se dă pentru compensare elementul 4. Distribuție finală: Alice George Distribuția este o distribuție OBZ și este eficientă Pareto.

Ambele proceduri sunt disponibile pentru manipulare - participantul poate câștiga profit suplimentar indicând preferințele greșite. Cu toate acestea, o astfel de manipulare necesită cunoașterea preferințelor partenerilor, deci este dificil de utilizat în practică.

Procedura AL cu obiect nediferențiat

Procedura AL inițială se bazează în mod fundamental pe presupunerea că ordonarea articolelor este strictă (fără indistincte). Aziz [5] a generalizat această procedură la ordonări generale cu posibilitatea de a avea obiecte care nu se pot distinge.

Note

1. ↑ Brams, Kilgour, Klamler, 2014 , p. 130.
2. ↑ Aziz, 2015 , p. 307–324.
3. ↑ Aici, strict înseamnă că pentru un participant nu pot exista două obiecte pe care să nu le distingă ca importanță.
4. ↑ Brandt, Conitzer et al., 2016 , p. 303.
5. ↑ Aziz, 2015 , p. 307-324.

Literatură

• Steven J. Brams, D. Marc Kilgour, Christian Klamler. Divizia echitabilă pentru două persoane a articolelor indivizibile: un algoritm eficient, fără invidie  // Notices of the American Mathematical Society. - 2014. - Februarie ( vol. 61 , numărul 2 ). - doi : 10.1090/noti1075 .
• Haris Aziz. O generalizare a metodei AL pentru alocarea corectă a obiectelor indivizibile // Buletin de Teorie Economică. - 2015. - Vol. 4 , nr. 2 . - doi : 10.1007/s40505-015-0089-1 . - arXiv : 1409,6765 .
• Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, Ariel D. Procaccia. Manual de alegere socială computațională . - Cambridge University Press, 2016. - ISBN 9781107060432 . ( versiune online )