Porządkowa efektywność Pareto

Porządkowa efektywność Pareto odnosi się do kilku adaptacji koncepcji efektywności Pareto do ustawień, w których agenci wyrażają jedynie użyteczności porządkowe w odniesieniu do przedmiotów, ale nie w odniesieniu do wiązek. Oznacza to, że agenci klasyfikują pozycje od najlepszego do najgorszego, ale nie klasyfikują podzbiorów pozycji. W szczególności nie określają wartości liczbowej dla każdej pozycji. Może to powodować niejasności co do tego, czy niektóre alokacje są efektywne w sensie Pareto, czy nie. Jako przykład rozważmy gospodarkę z trzema przedmiotami i dwoma agentami, z następującymi rankingami:

  • Alicja: x > y > z.
  • Jerzy: x > z > y.

Rozważ przydział [Alicja: x, Jerzy: y, z]. To, czy ta alokacja jest efektywna w sensie Pareto, zależy od liczbowych wycen agentów. Na przykład:

  • Jest możliwe, że Alicja woli {y,z} od {x}, a George woli {x} od {y,z} (przykładowo: oceny Alicji dla x,y,z wynoszą 8,7,6, a oceny George'a to 7 ,1,2, więc profil użyteczności wynosi 8,3). Wtedy alokacja nie jest efektywna w sensie Pareto, ponieważ zarówno Alice, jak i George byliby w lepszej sytuacji, gdyby wymienili swoje pakiety (profil użyteczności wyniósłby 13,7).
  • W przeciwieństwie do tego, możliwe jest, że Alicja woli {x} od {y,z}, a George woli {y,z} od {x} (na przykład: wyceny Alicji to 12,4,2, a wyceny George'a to 6,3, 4). Wtedy alokacja jest efektywna w sensie Pareto: w każdej innej alokacji, jeśli Alicja nadal otrzymuje x, to użyteczność George'a jest niższa; jeśli Alicja nie otrzyma x, to użyteczność Alicji jest niższa. Co więcej, alokacja jest efektywna w sensie Pareto, nawet jeśli elementy są podzielne (to znaczy jest ułamkowo efektywna w sensie Pareto ): jeśli Alicja daje George'owi jakąkolwiek kwotę r od x, to George musiałby dać jej co najmniej 3 r od y lub 6 r z, aby utrzymać jej użyteczność na tym samym poziomie. Ale wtedy użyteczność George'a zmieniłaby się o 6 r -9 r lub 6 r -24 r , co jest ujemne.

Ponieważ efektywność Pareto alokacji zależy od rankingów wiązek, a priori nie jest jasne, jak określić efektywność alokacji, gdy podane są tylko rankingi pozycji.

Definicje

Alokacja X = (X 1 ,...,X n ) Pareto dominuje nad inną alokacją Y = (Y 1 ,...,Y n ), jeśli każdy agent i słabo preferuje wiązkę X i od wiązkę Y i , i co najmniej jeden agent j ściśle preferuje X j od Y j . Alokacja X jest efektywna w sensie Pareto , jeśli nie dominuje nad nią żadna inna alokacja w sensie Pareto. Czasami rozróżnia się dyskretną efektywność Pareto , co oznacza, że ​​alokacja nie jest zdominowana przez alokację dyskretną, oraz silniejsza koncepcja ułamkowej efektywności Pareto , co oznacza, że ​​alokacja nie jest zdominowana nawet przez alokację ułamkową.

pakietów (zestawów przedmiotów) agentów . W naszym ustawieniu agenci zgłaszają tylko swoje rankingi przedmiotów . Ranking wiązek jest nazywany spójnym z rankingiem przedmiotów, jeśli klasyfikuje pojedyncze pakiety w tej samej kolejności, co zawarte w nich przedmioty. Na przykład, jeśli ranking Alicji to w < x < y < z , to każdy spójny ranking pakietów musi mieć {w} < {x} < {y} < {z]. Często przyjmuje się dodatkowe założenia dotyczące zestawu dozwolonych rankingów pakietów, co nakłada dodatkowe ograniczenia na spójność. Przykładowe założenia to:

  • Monotoniczność: dodanie przedmiotu do pakietu zawsze poprawia pakiet. Odpowiada to założeniu, że wszystkie pozycje są dobre . Zatem ranking pakietów Alicji musi mieć np. {y} < {y,x}.
  • Responsywność : wymiana przedmiotu na lepszy zawsze poprawia pakiet. Zatem ranking pakietów Alicji musi mieć np. {w,x} < {w,y} < {x,y} < {x,z}. To jest silniejsze niż konsekwencja.
  • Addytywność : agent przypisuje wartość każdemu przedmiotowi i wycenia każdy pakiet jako sumę jego zawartości. To założenie jest silniejsze niż responsywność. Na przykład, jeśli Alicja ma rangę {x,y}<{z}, to musi mieć rangę {w,x,y}<{w,z}.
  • Leksykograficzny : agent zawsze klasyfikuje pakiet zawierający jakiś przedmiot x wyżej niż pakiet zawierający tylko przedmioty o rankingu niższym niż x. W powyższym przykładzie Alicja musi mieć rangę {w,x,y} < {z}.

Niezbędna efektywność Pareto

Brams, Edelman i Fishburn nazywają alokację zapewniającą Pareto, jeśli jest ona wydajna w sensie Pareto dla wszystkich rankingów pakietów, które są zgodne z rankingami pozycji agentów (dopuszczają wszystkie rankingi pakietów monotonicznych i responsywnych ). Na przykład:

  • Jeśli zakłada się, że wyceny agentów są dodatnie, to każda alokacja dająca wszystkie pozycje jednemu agentowi jest gwarancją Pareto.
  • Jeśli ranking Alicji to x>y, a ranking George'a to y>x, to alokacja [Alicja:x, George:y] jest zapewniająca Pareto.
  • Jeśli ranking Alicji to x>y>z, a ranking George'a to x>z>y i alokacje muszą być dyskretne, to alokacja [Alicja: x,y; George: z] zapewnia Pareto. [ wymagane wyjaśnienie ]
  • Przy powyższych rankingach alokacja [Alicja: x, George: y, z] nie zapewnia Pareto. Jak wyjaśniono we wstępie, nie jest ona efektywna w sensie Pareto, np. gdy wyceny Alicji dla x,y,z wynoszą 8,7,6, a wyceny George'a to 7,1,2. Należy zauważyć, że obie te wyceny są zgodne z rankingami agentów.

Bouveret, Endriss i Lang. użyj równoważnej definicji. Mówią, że alokacja X prawdopodobnie dominuje w Pareto alokacja Y, jeśli istnieją rankingi pakietów zgodne z rankingami pozycji agentów, dla których X dominuje w Pareto Y. Alokacja nazywana jest koniecznie-pareto-efektywna (NecPE), jeśli nie ma innej alokacja prawdopodobnie – Pareto – dominuje nad nią.

Te dwie definicje są logicznie równoważne:

  • „X zapewnia Pareto” jest równoważne z „Dla każdego spójnego rankingu pakietów, dla każdej innej alokacji Y, Y nie dominuje nad X w Pareto”.
  • „X to NecPE” jest równoważne z „Dla każdej innej alokacji Y, dla każdego spójnego rankingu pakietów, Y nie dominuje nad X w Pareto”. Zamiana kolejności kwantyfikatorów „dla wszystkich” nie zmienia logicznego znaczenia.

Warunek NecPE pozostaje taki sam, niezależnie od tego, czy dopuszczamy wszystkie rankingi pakietów addytywnych, czy też dopuszczamy tylko rankingi oparte na wycenach addytywnych z malejącymi różnicami.

Istnienie

NecPE to bardzo mocne wymaganie, którego często nie można spełnić. Załóżmy na przykład, że dwóch agentów ma ten sam ranking przedmiotów. Jedna z nich, powiedzmy Alicja, koniecznie otrzymuje najniżej sklasyfikowany przedmiot. Istnieją spójne addytywne rankingi pakietów, w których Alicja wycenia ten przedmiot na 0, podczas gdy George wycenia go na 1. Zatem przekazanie go Alicji nie jest efektywne w sensie Pareto.

Jeśli wymagamy, aby wszystkie przedmioty miały ściśle dodatnią wartość, to przekazanie wszystkich przedmiotów jednemu agentowi jest trywialnie NecPE, ale bardzo niesprawiedliwe. Jeśli dozwolone są alokacje ułamkowe, może nie być alokacji NecPE, która daje obu agentom wartość dodatnią. Załóżmy na przykład, że Alicja i Jerzy mają ranking x>y. Jeśli obie otrzymają wartość dodatnią, to albo Alicja otrzyma trochę x, a George trochę y, albo odwrotnie. W pierwszym przypadku możliwe jest, że wyceny Alicji wynoszą np. 4,2, a wyceny George'a 8,1, więc Alicja może wymienić niewielką kwotę r x na niewielką kwotę 3 r y. Alicja zyskuje 6 r -4 r i George zyskuje 8 r -3 r , więc oba zyski są dodatnie. W tym drugim przypadku zachodzi analogiczny argument.

Możliwa efektywność Pareto

Brams, Edelman i Fishburn nazywają alokację możliwą w sensie Pareto, jeśli jest ona efektywna w sensie Pareto dla niektórych rankingów pakietów, które są zgodne z rankingami pozycji agentów. Oczywiście każda alokacja zapewniająca Pareto jest możliwa w sensie Pareto. Ponadto:

  • Jeśli ranking Alicji to x>y>z, a ranking George'a to x>z>y, to alokacja [Alicja: x, George: y, z] jest możliwa w sensie Pareto. Jak wyjaśniono we wstępie, jest ona efektywna w sensie Pareto, np. gdy wyceny Alicji dla x,y,z wynoszą 12,4,2, a wyceny George'a to 6,3,4. Należy zauważyć, że obie te wyceny są zgodne z rankingami agentów.
  • Jeśli ranking Alicji to x>y, a ranking George'a to y>x, to alokacja [Alicja:y, George:x] nie jest możliwa w sensie Pareto, ponieważ zawsze jest zdominowana przez Pareto przez alokację [Alicja:x, George: y].

Bouveret, Endriss i Lang. użyj innej definicji. Mówią, że alokacja X z konieczności dominuje w Pareto alokacja Y, jeśli dla wszystkich rankingów wiązek zgodnych z rankingami pozycji agentów, X Pareto dominuje Y. Alokacja nazywana jest Możliwie-Pareto-efektywna (PosPE), jeśli żadna inna alokacja nie koniecznie- Dominuje w nim Pareto.

Te dwie definicje nie są logicznie równoważne:

  • „X jest możliwy w sensie Pareto” jest równoważne z „Istnieje spójny ranking pakietów, dla którego dla każdej innej alokacji Y Y nie dominuje nad X”. Musi to być ten sam ranking pakietów dla wszystkich innych alokacji Y.
  • „X to PosPE” jest równoważne z „Dla każdej innej alokacji Y istnieje spójny ranking pakietów, dla którego Y nie dominuje nad X”. Dla każdej innej alokacji Y może istnieć inny ranking pakietów.

Jeśli X jest możliwe w sensie Pareto, to jest to PosPE, ale druga implikacja nie jest (logicznie) prawdziwa. [ wymagane wyjaśnienie ]

Warunek możliwości Pareto pozostaje taki sam, niezależnie od tego, czy dopuszczamy wszystkie addytywne rankingi wiązek, czy też dopuszczamy tylko rankingi oparte na wycenach addytywnych z malejącymi różnicami .

Efektywność Pareto z dominacją stochastyczną

Bogomolnaia i Moulin przedstawiają koncepcję wydajności dla ustalania uczciwego losowego przydziału (gdzie rankingi wiązek są addytywne , przydziały są ułamkowe , a suma ułamków przydzielona każdemu agentowi musi wynosić co najwyżej 1 ). Opiera się na pojęciu dominacji stochastycznej .

Dla każdego agenta i pakiet X i dominuje słabo stochastycznie (wsd) nad pakietem Y i , jeśli dla każdego elementu z całkowity ułamek elementów lepszych niż z w X i jest co najmniej tak duży jak w Y i (jeśli alokacje są dyskretne, to X i sd Y i oznacza, że ​​dla każdego elementu z liczba elementów lepszych niż z w X i jest co najmniej tak duża jak w Y i ). Relacja sd ma kilka równoważnych definicji; zobacz responsywne rozszerzenie zestawu . W szczególności X i sd Y i wtedy i tylko wtedy, gdy dla każdego rankingu pakietów zgodnego z rankingiem przedmiotów X i jest co najmniej tak dobry jak Y i . Wiązka X i ściśle stochastycznie dominuje (ssd) wiązka Y i jeśli X i wsd Y i oraz X i ≠ Y i . Równoważnie, dla co najmniej jednego elementu z, „co najmniej tak duży jak w Y i ” staje się „ściśle większy niż w Y i ”. W ssd relacja jest zapisywana jako „X i >> Y i ”.

Alokacja X = (X 1 ,...,X n ) stochastycznie dominuje nad inną alokacją Y = (Y 1 ,...,Y n ), jeśli dla każdego agenta i : X i wsd Y i , oraz Y≠X ( równoważnie: dla co najmniej jednego agenta i, X i ssd Y i ). W stochastycznej dominacji relacja między alokacjami jest również zapisywana jako „X >> Y”. Jest to równoważne z konieczną dominacją Pareto.

Alokacja jest nazywana sd-efektywną (zwaną także: porządkowo efektywną lub O-efektywną ), jeśli nie ma alokacji, która dominuje nad nią stochastycznie. Jest to podobne do PosPE, ale podkreśla, że ​​rankingi wiązek muszą być oparte na addytywnych funkcjach użyteczności, a alokacje mogą być ułamkowe .

równoważności

Jak wspomniano powyżej, Pareto-możliwy implikuje PosPE, ale drugi kierunek nie jest logicznie prawdziwy. McLennan udowadnia, że ​​są one równoważne w sprawiedliwego losowego przydziału (ze ścisłymi lub słabymi rankingami pozycji). W szczególności dowodzi, że następujące są równoważne:

  • (a) X jest efektywny sd (to znaczy X to PosPE);
  • (b) istnieją addytywne rankingi wiązek zgodne z rankingami przedmiotów agentów, dla których X jest ułamkowo efektywny w Pareto (to znaczy, X jest możliwy w Pareto);
  • (c) istnieją addytywne rankingi wiązek zgodne z rankingami przedmiotów agentów, dla których X maksymalizuje sumę użyteczności agentów.

Implikacje (c) → (b) → (a) są łatwe; najtrudniejszą częścią jest udowodnienie, że (a) → (c). McLennan udowadnia to za pomocą twierdzenia o hiperpłaszczyznach rozdzielających wielościany .

Bogomolnaia i Moulin dowodzą kolejnej użytecznej charakterystyki efektywności SD dla tego samego uczciwego ustawienia losowego przydziału, ale ze ścisłymi rankingami pozycji. Zdefiniuj graf wymiany danej alokacji ułamkowej jako graf skierowany , w którym węzły są elementami i istnieje łuk x→y, jeśli istnieje agent i , który preferuje x i otrzymuje dodatni ułamek y. Zdefiniuj alokację jako acykliczną , jeśli jej wykres wymiany nie ma skierowanych cykli. Następnie alokacja sd-efektywna, jeśli jest acykliczna.

Fishburn udowodnił następującą równoważność relacji dominacji dyskretnych wiązek, z responsywnymi rankingami wiązek:

  • Jeśli X i >> Y i (czyli: X i ≠ Y i , a dla każdego elementu z X i ma co najmniej tyle samo elementów, które są co najmniej tak dobre jak z), to dla każdego responsywnego rankingu pakietów zgodnego z ranking przedmiotów, X i > Y i .
  • Jeśli nie X i >> Y i , to istnieje co najmniej jeden responsywny ranking pakietów zgodny z rankingiem pozycji, dla którego X i < Y i .

Dlatego dla relacji dominacji dyskretnych alokacji obowiązuje następująca zasada: X >> Y iff X koniecznie Pareto-dominuje Y .

Nieruchomości

Jeżeli X i wsd Y i , to |X i | ≥ |T i | , czyli całkowita ilość obiektów (dyskretnych lub ułamkowych) w X i musi być co najmniej tak duża jak w Y i . To dlatego, że jeśli |X i | < |Y i | , to dla wyceny, która przypisuje prawie taką samą wartość wszystkim pozycjom, v( X i ) < v( Y i ).

Oznacza to, że jeśli X wsd Y oraz zarówno X, jak i Y są pełnymi alokacjami (wszystkie obiekty są przydzielone), to koniecznie |X i | = |Y ja | dla wszystkich agentów I. Innymi słowy, pełna alokacja X może być koniecznie zdominowana tylko przez alokację Y, która przypisuje każdemu agentowi taką samą kwotę jak X.

Oznacza to, że w szczególności, jeśli X jest sd-efektywny w zbiorze wszystkich alokacji, które dają dokładnie 1 jednostkę każdemu agentowi, to X jest ogólnie sd-efektywny.

Dominacja leksykograficzna Efektywność Pareto

Cho przedstawia dwa inne pojęcia wydajności dotyczące ustalania uczciwego losowego przydziału , oparte na dominacji leksykograficznej .

Alokacja X = (X 1 ,...,X n ) leksykograficznie w dół (dl) dominuje nad inną alokacją Y = (Y 1 ,...,Y n ), jeśli dla każdego agenta i, X i słabo-dl- dominuje Y i i dla co najmniej jednego agenta j X j ściśle-dl-dominuje Yj . Alokacja nazywana jest wydajną dl, jeśli nie ma innej alokacji, która dominuje nad nią dl.

Podobnie, w oparciu o pojęcie dominacji leksykograficznej w górę (ul) , alokacja nazywana jest ul-efektywną, jeśli nie ma innej alokacji, która by nad nią dominowała.

Ogólnie rzecz biorąc, dominacja sd implikuje dominację dl i dominację ul. Dlatego wydajność dl i wydajność ul implikują wydajność sd.

równoważności

Rozważ ustawienie sprawiedliwego losowego przydziału (rankingi pakietów są addytywne , przydziały mogą być ułamkowe , a całkowity ułamek przyznany każdemu agentowi musi wynosić 1), ze ścisłymi rankingami przedmiotów, w których może być więcej przedmiotów niż agentów (więc niektóre przedmioty mogą pozostają nieprzydzielone). Cho i Dogan dowodzą, że w tym konkretnym przypadku wydajność dl i wydajność ul są równoważne wydajności sd. W szczególności dowodzą, że jeśli alokacja X jest efektywna sd/ld/ul, to:

  • Wykres wymiany X jest acykliczny i -
  • X nie jest rozrzutny („rozrzutny” oznacza, że ​​jakiś agent i , który otrzymuje dodatnią część przedmiotu x , preferuje inny przedmiot y , który nie jest całkowicie przydzielony).

Równoważność nie zachodzi, jeśli istnieją ograniczenia dystrybucyjne: istnieją alokacje, które są efektywne sd, ale nie są efektywne dl.

Dalsza lektura

  • Aziz, Gaspers, Mackenzie i Walsh badają zagadnienia obliczeniowe związane z pojęciami uczciwości porządkowej. W rozdziale 7 pokrótce badają efektywność sd-Pareto.
  • Dogan, Dogan i Yildiz badają inną relację dominacji między alokacjami: alokacja X dominuje nad alokacją Y, jeśli jest efektywna w sensie Pareto dla większego zestawu rankingów wiązek zgodnych z rankingami pozycji.
  • Abdulkadiroğlu i Sönmez badają związek między efektywnością SD a efektywnością Pareto ex post (w kontekście losowego przydziału). Wprowadzają nowe pojęcie dominacji dla zestawów przydziałów i pokazują, że loteria jest SD-efektywna, jeśli każdy podzbiór wsparcia loterii jest niezdominowany.
  1. ^ A b c d e f g h    Brams, Steven J.; Edelman, Paweł H.; Fishburn, Peter C. (2003-09-01). „Sprawiedliwy podział rzeczy niepodzielnych” . Teoria i decyzja . 55 (2): 147–180. doi : 10.1023/B:THEO.0000024421.85722.0a . ISSN 1573-7187 . S2CID 153943630 .
  2. ^ a b   Bouveret, Sylvain; Endriss, Ulle; Lang, Jérôme (2010-08-04). „Sprawiedliwy podział w ramach preferencji porządkowych: obliczanie wolnej od zazdrości alokacji dóbr niepodzielnych” . Materiały z konferencji 2010 na temat instytucji ECAI 2010: 19. europejska konferencja na temat sztucznej inteligencji . NLD: IOS Prasa: 387–392. ISBN 978-1-60750-605-8 .
  3. ^ ab Segal    -Halevi, Erel; chasydzi, Avinatan; Aziz, Haris (2020-03-10). „Sprawiedliwa alokacja przy malejących różnicach” . Dziennik badań nad sztuczną inteligencją . 67 : 471-507-471-507. doi : 10.1613/jair.1.11994 . ISSN 1076-9757 . S2CID 108290839 .
  4. ^ a b c   Bogomolnaja, Anna; Moulin, Hervé (2001-10-01). „Nowe rozwiązanie problemu losowego przypisania” . Dziennik teorii ekonomii . 100 (2): 295–328. doi : 10.1006/jeth.2000.2710 . ISSN 0022-0531 .
  5. ^ Katta, Akszaj-Kumar; Sethuraman, Jay (2006). „Rozwiązanie problemu losowego przypisania w domenie pełnej preferencji”. Dziennik teorii ekonomii . 131 (1): 231. doi : 10.1016/j.jet.2005.05.001 .
  6. ^ a b   Cho, Wonki Jo; Doğan, Battal (2016-09-01). „Równoważność pojęć wydajności dla problemów z przypisaniem porządkowym” . Listy ekonomiczne . 146 : 8–12. doi : 10.1016/j.econlet.2016.07.007 . ISSN 0165-1765 .
  7. ^ ab . McLennan, Andrew (2002-08-01)   „Wydajność porządkowa i twierdzenie o wielościennej separacji hiperpłaszczyzny” . Dziennik teorii ekonomii . 105 (2): 435–449. doi : 10.1006/jeth.2001.2864 . ISSN 0022-0531 .
  8. ^   Fishburn, Peter C. (1996-03-01). „Skończone liniowe prawdopodobieństwo jakościowe” . Journal of Psychologii Matematycznej . 40 (1): 64–77. doi : 10.1006/jmps.1996.0004 . ISSN 0022-2496 .
  9. Bibliografia    _ Brandl, Florian (2022-09-01). „Reguła czujnego jedzenia: ogólne podejście do probabilistycznego projektu ekonomicznego z ograniczeniami” . Gry i zachowania ekonomiczne . 135 : 168–187. arXiv : 2008.08991 . doi : 10.1016/j.geb.2022.06.002 . ISSN 0899-8256 . S2CID 221186811 .
  10. Bibliografia    _ Gaspers, Serge; Mackenzie, Szymon; Walsh, Toby (2015-10-01). „Sprawiedliwe przypisanie niepodzielnych przedmiotów w ramach preferencji porządkowych” . Sztuczna inteligencja . 227 : 71–92. doi : 10.1016/j.artint.2015.06.002 . ISSN 0004-3702 . S2CID 1408197 .
  11. ^   Doğan, Battal; Doğan, Serhat; Yıldız, Kemal (2018-05-01). „Nowe kryterium wydajności ex ante i implikacje dla probabilistycznego mechanizmu szeregowego” . Dziennik teorii ekonomii . 175 : 178–200. doi : 10.1016/j.jet.2018.01.011 . hdl : 11693/48988 . ISSN 0022-0531 .
  12. ^   Abdulkadiroğlu, Atila; Sonmez, Tayfun (2003-09-01). „Wydajność porządkowa i zdominowane zestawy zadań” . Dziennik teorii ekonomii . 112 (1): 157–172. doi : 10.1016/S0022-0531(03)00091-7 . hdl : 10161/1940 . ISSN 0022-0531 .
Pobrano z „ https://en.wikipedia.org/w/index.php?title=Ordinal_Pareto_efficiency&oldid=1138948851 ”