Ordinal Pareto effektivitet

Ordinal Pareto-effektivitet hänvisar till flera anpassningar av konceptet Pareto-effektivitet till inställningar där agenterna endast uttrycker ordinal nytta över objekt, men inte över buntar. Det vill säga, agenter rangordnar objekten från bäst till sämst, men de rangordnar inte undergrupperna av objekt. I synnerhet anger de inte ett numeriskt värde för varje artikel. Detta kan orsaka en oklarhet om huruvida vissa tilldelningar är Pareto-effektiva eller inte. Som ett exempel, betrakta en ekonomi med tre objekt och två agenter, med följande ranking:

  • Alice: x > y > z.
  • George: x > z > y.

Tänk på allokeringen [Alice: x, George: y,z]. Huruvida denna allokering är Pareto-effektiv eller inte beror på agenternas numeriska värderingar. Till exempel:

  • Det är möjligt att Alice föredrar {y,z} framför {x} och George föredrar {x} framför {y,z} (till exempel: Alices värderingar för x,y,z är 8,7,6 och Georges värderingar är 7 ,1,2, så nyttoprofilen är 8,3). Då är allokeringen inte Pareto-effektiv, eftersom både Alice och George skulle ha det bättre genom att byta sina paket (nyttoprofilen skulle vara 13,7).
  • Däremot är det möjligt att Alice föredrar {x} framför {y,z} och George föredrar {y,z} framför {x} (till exempel: Alices värderingar är 12,4,2 och Georges värderingar är 6,3, 4). Då är allokeringen Pareto-effektiv: i vilken annan allokering som helst, om Alice fortfarande får x, så är Georges nytta lägre; om Alice inte får x, då är Alices nytta lägre. Dessutom är allokeringen Pareto-effektiv även om objekten är delbara (det vill säga den är pareto-effektiv ): om Alice ger någon mängd r av x till George, så måste George ge henne minst 3 r av y eller 6 r av z för att hålla hennes nytta på samma nivå. Men då skulle Georges nytta ändras med 6 r -9 r eller 6 r -24 r , vilket är negativt.

Eftersom Pareto-effektiviteten för en allokering beror på rangordningen av paket, är det a-priori inte klart hur man bestämmer effektiviteten av en tilldelning när endast rankningar av objekt ges.

Definitioner

En allokering X = (X 1 ,..., X n ) Pareto-dominerar en annan allokering Y = (Y 1 ,...,Y n ), om varje agent i svagt föredrar bunten X i framför bunten Yi , och åtminstone en agent j föredrar strängt Xj framför Yj . En allokering X är Pareto-effektiv om ingen annan tilldelning Pareto-dominerar den. Ibland görs en skillnad mellan diskret-Pareto-effektivitet , vilket innebär att en allokering inte domineras av en diskret allokering, och det starkare konceptet Bråkpareto-effektivitet , vilket innebär att en allokering inte domineras ens av en bråkdelsallokering.

Ovanstående definitioner beror på agenternas rangordning av buntar (uppsättningar av artiklar). I vår inställning rapporterar agenter endast sina rankningar av objekt . En buntrankning kallas konsistent med en artikelrankning om den rangordnar singleton-buntarna i samma ordning som artiklarna de innehåller. Till exempel, om Alices rankning är w < x < y < z , måste alla konsekventa paketrankningar ha {w} < {x} < {y} < {z]. Ofta gör man ytterligare antaganden om uppsättningen av tillåtna buntrankningar, vilket medför ytterligare begränsningar för konsekvens. Exempel på antaganden är:

  • Monotonicitet: Att lägga till ett föremål i ett paket förbättrar alltid paketet. Detta motsvarar antagandet att alla artiklar är bra . Således måste Alices buntrankning ha t.ex. {y} < {y,x}.
  • Responsivitet : att ersätta ett föremål med ett bättre föremål förbättrar alltid paketet. Således måste Alices buntrankning ha t.ex. {w,x} < {w,y} < {x,y} < {x,z}. Detta är starkare än konsistens.
  • Additivitet : agenten tilldelar ett värde till varje artikel och värderar varje bunt till summan av dess innehåll. Detta antagande är starkare än lyhördhet. Till exempel, om Alice rankar {x,y}<{z} måste hon ranka {w,x,y}<{w,z}.
  • Lexikografisk : agenten rankar alltid ett paket som innehåller något objekt x ovanför varje paket som bara innehåller objekt som är lägre än x. I exemplet ovan måste Alice ranka {w,x,y} < {z}.

Nödvändig Pareto-effektivitet

Brams, Edelman och Fishburn kallar en allokering för Pareto-säkra om den är Pareto-effektiv för alla buntrankningar som överensstämmer med agenternas artikelrankningar (de tillåter alla monotona och responsiva buntrankningar). Till exempel:

  • Om agenternas värderingar antas vara positiva är varje allokering som ger alla poster till en enskild agent Pareto-säkrande.
  • Om Alices rankning är x>y och Georges rankning är y>x, då är tilldelningen [Alice:x, George:y] Pareto-säkrande.
  • Om Alices rankning är x>y>z och Georges rankning är x>z>y och allokeringarna måste vara diskreta, då tilldelningen [Alice: x,y; George: z] är Pareto-säkra. [ förtydligande behövs ]
  • Med ovanstående rankningar är tilldelningen [Alice: x, George: y,z] inte Pareto-säkrande. Som förklarats i inledningen är det inte Pareto-effektivt t.ex. när Alices värderingar för x,y,z är 8,7,6 och Georges värderingar är 7,1,2. Observera att båda dessa värderingar överensstämmer med agenternas ranking.

Bouveret, Endriss och Lang. använda en motsvarande definition. De säger att en allokering X möjligen Pareto-dominerar en allokering Y om det finns några buntrankningar som överensstämmer med agenternas artikelrankningar, för vilka X Pareto-dominerar Y. En allokering kallas Necessarily-Pareto-efficient (NecPE) om ingen annan tilldelning möjligen-Pareto-dominerar det.

De två definitionerna är logiskt likvärdiga:

  • "X är Pareto-säkrande" motsvarar "För varje konsekvent paketrankning, för varje annan allokering Y, dominerar Y inte X".
  • "X är NecPE" är ekvivalent med "För varje annan allokering Y, för varje konsekvent buntrankning, dominerar inte Y X av Pareto". Att byta ut ordningen på "för alla" kvantifierare ändrar inte den logiska innebörden.

NecPE-villkoret förblir detsamma oavsett om vi tillåter alla additiva paketrankningar, eller om vi endast tillåter rankningar som är baserade på additiva värderingar med minskande skillnader.

Existens

NecPE är ett mycket starkt krav, som ofta inte kan uppfyllas. Anta till exempel att två agenter har samma artikelrankning. En av dem, säg Alice, får nödvändigtvis det lägst rankade föremålet. Det finns konsekventa additiv bunt-rankningar där Alices värderar detta objekt till 0 medan George värderar det till 1. Därför är det inte Pareto-effektivt att ge det till Alice.

Om vi ​​kräver att alla föremål har ett strikt positivt värde, så är att ge alla föremål till en enda agent trivialt NecPE, men det är väldigt orättvist. Om fraktionerad allokering tillåts, kan det inte finnas någon NecPE-allokering som ger båda agenterna ett positivt värde. Anta till exempel att Alice och George båda har rankningen x>y. Om båda får ett positivt värde får Alice antingen x och George lite y, eller tvärtom. I det förra fallet är det möjligt att Alices värderingar är t.ex. 4,2 och Georges värderingar är 8,1, så Alice kan byta ut ett litet belopp r av x mot ett litet belopp 3 r av y. Alice får 6 r -4 r och George får 8 r -3 r , så båda vinsterna är positiva. I det senare fallet gäller ett analogt argument.

Möjlig Pareto-effektivitet

Brams, Edelman och Fishburn kallar en allokering Pareto-möjlig om den är Pareto-effektiv för vissa buntrankningar som överensstämmer med agenternas artikelrankningar. Uppenbarligen är varje Pareto-försäkrande tilldelning Pareto-möjlig. Dessutom:

  • Om Alices rankning är x>y>z och Georges rankning är x>z>y, då är allokeringen [Alice: x, George: y,z] Pareto-möjlig. Som förklarats i inledningen är det Pareto-effektivt t.ex. när Alices värderingar för x,y,z är 12,4,2 och Georges värderingar är 6,3,4. Observera att båda dessa värderingar överensstämmer med agenternas ranking.
  • Om Alices rankning är x>y och Georges ranking är y>x, så är tilldelningen [Alice:y, George:x] inte Pareto-möjlig, eftersom den alltid är Pareto-dominerad av allokeringen [Alice:x, George: y].

Bouveret, Endriss och Lang. använda en annan definition. De säger att en allokering X nödvändigtvis Pareto-dominerar en allokering Y om för alla buntrankningar som överensstämmer med agenternas artikelrankningar, X Pareto-dominerar Y. En allokering kallas Possibly-Pareto-efficient (PosPE) om ingen annan allokering nödvändigtvis- Pareto-dominerar det.

De två definitionerna är inte logiskt likvärdiga:

  • "X är Pareto-möjligt" motsvarar "Det finns en konsekvent buntrankning för vilken Y inte dominerar X för varje annan allokering Y". Det måste vara samma paketrankning för alla andra tilldelningar Y.
  • "X är PosPE" motsvarar "För varje annan allokering Y finns det en konsekvent buntrankning, för vilken Y inte dominerar X". Det kan finnas en annan buntrankning för varannan allokering Y.

Om X är Pareto-möjligt så är det PosPE, men den andra implikationen är inte (logiskt) sann. [ förtydligande behövs ]

Det Pareto-möjliga villkoret förblir detsamma oavsett om vi tillåter alla additiva paketrankningar, eller om vi bara tillåter rankningar som är baserade på additiva värderingar med minskande skillnader .

Stokastisk dominans Pareto-effektivitet

Bogomolnaia och Moulin presenterar en effektivitetsuppfattning för fastställandet av rättvis slumpmässig tilldelning (där buntrankningen är additiv , tilldelningarna är bråkdelar och summan av bråk som ges till varje agent måste vara högst 1 ). Den bygger på föreställningen om stokastisk dominans .

För varje agent i dominerar A bunt X i svagt stokastiskt (wsd) en bunt Y i om för varje objekt z, den totala andelen artiklar bättre än z i X i är minst lika stor som i Y i (om allokeringarna X är diskreta, så betyder X i sd Y i att för varje objekt z är antalet artiklar bättre än z i i minst lika stort som i Y i ). sd-relationen har flera motsvarande definitioner; se responsiv uppsättningsförlängning . I synnerhet, X i sd Y i om-och-bara-om, för varje buntrankning som överensstämmer med artikelrankningen, är X i minst lika bra som Y i . En bunt Xi Xi dominerar strikt stokastiskt (ssd) en bunt Yi om X i wsd Yi och ≠ Yi . På motsvarande sätt, för åtminstone en post z, blir "minst lika stor som i Yi" " strikt större än i Yi" . I ssd-relationen skrivs som "X i >> Y i ".

En allokering X = (X 1 ,..., Xn ) dominerar stokastiskt en annan allokering Y = (Y 1 ,...,Y n ), om för varje agent i : Xi wsd Yi , och Y≠X ( motsvarande: för minst en agent i, X i ssd Y i ). I den stokastiska dominansrelationen mellan allokeringar skrivs också som "X >> Y". Detta motsvarar nödvändigt Pareto-dominans.

En allokering kallas sd-effektiv (även kallad: ordinärt effektiv eller O-effektiv ) om det inte finns någon allokering som stokastiskt dominerar den. Detta liknar PosPE, men betonar att buntrankningen måste baseras på additiva verktygsfunktioner, och allokeringarna kan vara bråkdelar .

Ekvivalenser

Som nämnts ovan, innebär Pareto-möjlig PosPE, men den andra riktningen är inte logiskt sann. McLennan bevisar att de är likvärdiga i rättvisa slumpmässiga tilldelningar (med strikta eller svaga objektrankningar). Särskilt bevisar han att följande är likvärdiga:

  • (a) X är sd-effektiv (det vill säga X är PosPE);
  • (b) det finns additiv bunt-rankning som överensstämmer med agenternas artikelrankningar för vilka X är fraktionellt Pareto-effektivt (det vill säga X är Pareto-möjligt);
  • (c) det finns additiv buntrankning som överensstämmer med agenternas artikelrankningar för vilka X maximerar summan av agenternas hjälpmedel.

Implikationerna (c) → (b) → (a) är lätta; den utmanande delen är att bevisa att (a) → (c). McLennan bevisar det med hjälp av polyedrisk separerande hyperplansats .

Bogomolnaia och Moulin bevisar en annan användbar karaktärisering av sd-effektivitet, för samma rättvisa slumpmässiga uppdragsinställning men med strikta objektrankningar. Definiera utbytesgrafen för en given bråkallokering som en riktad graf där noderna är objekten, och det finns en båge x→y om det finns en agent i som föredrar x och får en positiv bråkdel av y. Definiera en allokering som acyklisk om dess utbytesgraf inte har några riktade cykler. Sedan en allokering sd-effektiv om den är acyklisk.

Fishburn bevisade följande likvärdighet när det gäller dominansrelationer för diskreta paket, med responsiva paketrankningar:

  • Om X i >> Y i (det vill säga: X i ≠ Y i , och för varje objekt z, har X i minst lika många artiklar som är minst lika bra som z), så för varje responsiv bunt-rankning i enlighet med artikelrangeringen, X i >Y i .
  • Om inte Xi >> Yi , så finns det åtminstone en responsiv buntrankning som överensstämmer med artikelrangeringen, för vilken X i < Yi .

Därför gäller följande för dominansrelationer av diskreta allokeringar: X >> Y iff X nödvändigtvis Pareto-dominerar Y .

Egenskaper

Om Xi wsd Yi , då | Xi | _ ≥ |Y i | , det vill säga den totala mängden objekt (diskret eller bråkdel) i X i måste vara minst lika stor som i Y i . Detta beror på att om |X i | < |Y i | , sedan för värderingen som tilldelar nästan samma värde för alla objekt, v( X i ) < v( Y i ).

Detta betyder att om X wsd Y och både X och Y är fullständiga allokeringar (alla objekt är allokerade), så måste | X i | = |Y i | för alla agenter i . Med andra ord kan en fullständig allokering X nödvändigtvis domineras endast av en allokering Y som tilldelar varje agent samma belopp som X gör.

Detta betyder att i synnerhet, om X är sd-effektiv i uppsättningen av alla allokeringar som ger exakt 1 enhet till varje agent, så är X sd-effektiv i allmänhet.

Lexikografisk-dominans Pareto-effektivitet

Cho presenterar två andra effektivitetsuppfattningar för inställningen av rättvis slumpmässig tilldelning, baserad på lexikografisk dominans .

En allokering X = (X 1 ,...,X n ) nedåt-lexikografiskt (dl) dominerar en annan allokering Y = (Y 1 ,...,Y n ), om för varje agent i, X i svagt-dl- dominerar Yi , och för åtminstone en agent j , Xj strikt-dl-dominerar Yj . En allokering kallas dl-effektiv om det inte finns någon annan allokering som dl-dominerar den.

På liknande sätt, baserat på begreppet uppåt-lexikografisk (ul) dominans , kallas en allokering ul-effektiv om det inte finns någon annan allokering som ul-dominerar den.

Generellt sett innebär sd-domination dl-domination och ul-domination. Därför innebär dl-effektivitet och ul-effektivitet sd-effektivitet.

Ekvivalenser

Tänk på inställningen för rättvisa slumpmässiga tilldelningar (paketrankningarna är additiv , allokeringarna kan vara bråkdelar och den totala andelen som ges till varje agent måste vara 1), med strikta objektrankningar, där det kan finnas fler objekt än agenter (så vissa objekt kan förbli otilldelad). Cho och Dogan bevisar att i det här specifika fallet är dl-effektivitet och ul-effektivitet likvärdiga med sd-effektivitet. I synnerhet bevisar de att om en allokering X är sd/ld/ul effektiv, då:

  • Utbytesgrafen för X är acyklisk, och -
  • X är icke-slöseri ("slöseri" betyder att någon agent i , som får en positiv del av ett föremål x , föredrar en annan post y som inte är helt tilldelad).

Ekvivalensen gäller inte om det finns fördelningsrestriktioner: det finns allokationer som är sd-effektiva men inte dl-effektiva.

Vidare läsning

  • Aziz, Gaspers, Mackenzie och Walsh studerar beräkningsfrågor relaterade till ordinal rättvisa föreställningar. I avsnitt 7 studerar de kortfattat sd-Pareto-effektivitet.
  • Dogan, Dogan och Yildiz studerar en annan dominansrelation mellan allokeringar: en allokering X dominerar en allokering Y om den är Pareto-effektiv för en större uppsättning buntrankningar som överensstämmer med artikelrankningarna.
  • Abdulkadiroğlu och Sönmez undersöker sambandet mellan sd-effektivitet och efterhand Pareto-effektivitet (i samband med slumpmässig tilldelning). De introducerar ett nytt begrepp om dominans för uppsättningar av uppdrag och visar att ett lotteri är sd-effektivt om varje delmängd av stödet till lotteriet är odominerat.
  1. ^ a b c d e f g h    Brams, Steven J.; Edelman, Paul H.; Fishburn, Peter C. (2003-09-01). "Rättvis uppdelning av odelbara föremål" . Teori och beslut . 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). "Rättvis uppdelning under ordinarie preferenser: beräkna avundsfria tilldelningar av odelbara varor" . Proceedings of the 2010 Conference on ECAI 2010: 19th European Conference on Artificial Intelligence . NLD: IOS Press: 387–392. ISBN 978-1-60750-605-8 .
  3. ^ a b    Segal-Halevi, Erel; Hassidim, Avinatan; Aziz, Haris (2020-03-10). "Rättvis fördelning med minskande skillnader" . Journal of Artificial Intelligence Research . 67 : 471–507–471–507. doi : 10.1613/jair.1.11994 . ISSN 1076-9757 . S2CID 108290839 .
  4. ^ a b c   Bogomolnaia, Anna; Moulin, Hervé (2001-10-01). "En ny lösning på problemet med slumpmässig tilldelning" . Journal of Economic Theory . 100 (2): 295–328. doi : 10.1006/jeth.2000.2710 . ISSN 0022-0531 .
  5. ^ Katta, Akshay-Kumar; Sethuraman, Jay (2006). "En lösning på problemet med slumpmässig tilldelning på hela preferensdomänen". Journal of Economic Theory . 131 (1): 231. doi : 10.1016/j.jet.2005.05.001 .
  6. ^ a b   Cho, Wonki Jo; Doğan, Battal (2016-09-01). "Ekvivalens av effektivitetsbegrepp för ordinala tilldelningsproblem" . Ekonomibrev . 146 : 8–12. doi : 10.1016/j.econlet.2016.07.007 . ISSN 0165-1765 .
  7. ^ a b   McLennan, Andrew (2002-08-01). "Ordinal effektivitet och polyedrisk separerande hyperplansats" . Journal of Economic Theory . 105 (2): 435–449. doi : 10.1006/jeth.2001.2864 . ISSN 0022-0531 .
  8. ^   Fishburn, Peter C. (1996-03-01). "Ändlig linjär kvalitativ sannolikhet" . Journal of Mathematical Psychology . 40 (1): 64–77. doi : 10.1006/jmps.1996.0004 . ISSN 0022-2496 .
  9. ^    Aziz, Haris; Brandl, Florian (2022-09-01). "Den vaksamma ätningsregeln: En allmän strategi för probabilistisk ekonomisk design med begränsningar" . Spel och ekonomiskt beteende . 135 : 168–187. arXiv : 2008.08991 . doi : 10.1016/j.geb.2022.06.002 . ISSN 0899-8256 . S2CID 221186811 .
  10. ^    Aziz, Haris; Gaspers, Serge; Mackenzie, Simon; Walsh, Toby (2015-10-01). "Rättvis tilldelning av odelbara objekt under ordinalpreferenser" . Artificiell intelligens . 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). "Ett nytt förhandseffektivitetskriterium och konsekvenser för den probabilistiska seriella mekanismen" . Journal of Economic Theory . 175 : 178–200. doi : 10.1016/j.jet.2018.01.011 . hdl : 11693/48988 . ISSN 0022-0531 .
  12. ^   Abdulkadiroğlu, Atila; Sönmez, Tayfun (2003-09-01). "Ordinell effektivitet och dominerade uppsättningar av uppdrag" . Journal of Economic Theory . 112 (1): 157–172. doi : 10.1016/S0022-0531(03)00091-7 . hdl : 10161/1940 . ISSN 0022-0531 .
Hämtad från " https://en.wikipedia.org/w/index.php?title=Ordinal_Pareto_efficiency&oldid=1138948851 "