Slumpmässig prioritering av objekt
Slumpmässig prioritet (RP), även kallad Random Serial dictatur (RSD), är en procedur för rättvis slumpmässig tilldelning - att dela odelbara föremål rättvist mellan människor.
Anta att -partner måste dela upp (eller färre) olika objekt mellan dem. Eftersom föremålen är odelbara kommer vissa partners nödvändigtvis att få de mindre föredragna föremålen (eller inga föremål alls). RSD försöker införa rättvisa i denna situation på följande sätt. Rita en slumpmässig permutation av medlen från den enhetliga fördelningen. Låt dem sedan successivt välja ett objekt i den ordningen (så att den första agenten i beställningen får första valet och så vidare).
Egenskaper
RSD är en sanningsenlig mekanism när antalet föremål som mest är antalet agenter, eftersom du bara har en möjlighet att välja ett föremål, och den uppenbarligen dominerande strategin i denna möjlighet är att välja den bästa tillgängliga artikeln.
RSD är ex-ante avundsfri (EF), eftersom varje agent har samma chans att synas på varje position i beställningen. Uppenbarligen är det inte avundslöst i efterhand, eftersom en agent som råkar vara sist i den slumpmässiga permutationen kan avundas agenter som dyker upp tidigare.
RSD ger alltid ett i efterhand Pareto-effektivt (PE) resultat. Dessutom, i ett uppdragsproblem är varje deterministisk PE-uppdrag resultatet av SD för en viss beställning av agenterna.
RSD är dock inte ex-ante PE när agenterna har Von Neumann-Morgenstern-verktyg över slumpmässiga tilldelningar, dvs lotterier över objekt (Observera att ex-ante-avundsfrihet är svagare än ex-post-avundsfrihet, men ex-ante Pareto-effektivitet är starkare än efterhand Pareto-effektivitet). Som ett exempel, anta att det finns tre agenter, tre objekt och VNM-verktygen är:
| Artikel x | Objekt y | Artikel z | |
|---|---|---|---|
| Alice | 1 | 0,8 | 0 |
| Guppa | 1 | 0,2 | 0 |
| Carl | 1 | 0,2 | 0 |
RSD ger en 1/3 chans för varje objekt till varje agent (eftersom deras preferenser över säkra objekt sammanfaller), och en profil av förväntad nyttovektor (0,6, 0,4, 0,4). Men att tilldela objekt y till Alice för säker och objekt x,z slumpmässigt mellan Bob och Carl ger den förväntade nyttovektorn (0,8, 0,5, 0,5). Så den ursprungliga verktygsvektorn är inte Pareto-effektiv .
Dessutom, när agenter har ordinarie rankningar, misslyckas RSD även den svagare egenskapen sd-effektivitet .
När rankningarna av agenterna över objekten ritas enhetligt slumpmässigt, närmar sig sannolikheten att allokeringen som ges av RSD är ex-ante PE noll när antalet agenter växer.
En alternativ regel, den probabilistiska seriella regeln , är sd-effektiv (vilket innebär ex-post PE) och sd-EF (vilket innebär ex-ante EF), men den är inte sanningsenlig. Det är omöjligt att njuta av fördelarna med båda mekanismerna:
- Med kardinaladditiva nyttofunktioner är ingen mekanism symmetrisk, sanningsenlig och ex-ante PE.
- Med Ordinal-verktygsfunktioner är ingen mekanism SD-effektiv, strategisäker och behandlar lika.
Generaliseringar
Fler objekt än agenter
När det finns fler än objekt kan vissa agenter få mer än ett objekt. Det finns flera sätt att utöka RSD till detta fall.
- Ett sätt är att definiera en kvot för varje agent (så att summan av kvoter är lika med antalet objekt), och låta varje agent i sin tur plocka upp föremål till sin kvot. Detta förfarande förblir strategisäkert , men det är mycket orättvist.
- Ett annat sätt är att låta varje agent välja ett enstaka objekt och sedan göra en omgång till där varje agent väljer ett enda objekt, tills alla objekt är tagna; detta leder till round-robin-fördelningsförfarandet . Denna procedur är mer rättvis, men den är inte strategisäker .
- Båda procedurerna är specialfall av en plocksekvens .
Allmänt beslutsfattande
RSD kan definieras för den mer allmänna inställningen där gruppen måste välja ett enda alternativ från en uppsättning alternativ. I den här inställningen fungerar RSD enligt följande: Först, permutera slumpmässigt agenterna. Börja med uppsättningen av alla alternativ, be varje agent i permutationsordningen att välja sina favoritalternativ bland de återstående alternativen. Om mer än ett alternativ återstår efter att ha tagit hänsyn till alla agenters preferenser, randomiserar RSD enhetligt över dessa alternativ. I den tidigare nämnda artikelindelningen motsvarar alternativen tilldelningen av poster till agenter. Varje agent har stora ekvivalensklasser i sin preferens, eftersom han är likgiltig mellan alla tilldelningar där han får samma post.
I den här allmänna inställningen, om alla agenter har strikta preferenser framför alternativen, reducerar RSD till att dra en slumpmässig agent och välja det alternativ som agenten gillar bäst. Denna procedur är känd som slumpmässig diktatur (RD), och är den unika proceduren som är effektiv och strategisäker när preferenserna är strikta. När agenter kan ha svaga preferenser är det dock ingen procedur som utökar RD (som inkluderar RSD) som uppfyller både effektivitet och strategisäkerhet.
Se även
- Sidan om rättvis slumpmässig tilldelning jämför RSD med andra procedurer för att lösa samma problem, till exempel probabilistisk-seriell regel .
- Sidan om diktaturmekanismen beskriver RSD är en allmän regel för sociala val - inte nödvändigtvis för postfördelning.