Rättvis slumpmässigt uppdrag

Rättvis slumpmässig tilldelning (även kallad probabilistisk ensidig matchning ) är ett slags rättvis divisionsproblem .

I ett uppdragsproblem (även kallat husfördelningsproblem eller ensidig matchning ) finns det m objekt och de måste fördelas på n agenter, så att varje agent får högst ett objekt. Exempel inkluderar tilldelning av jobb till arbetare, rum till huskamrater, sovsalar till studenter, tidsluckor till användare av en gemensam maskin, och så vidare.

I allmänhet kan ett rättvist uppdrag vara omöjligt att uppnå. Till exempel, om Alice och Batya båda föredrar det östra rummet framför det västra rummet, kommer bara en av dem att få det och den andra kommer att bli avundsjuk. I slumpmässiga uppdrag uppnås rättvisa med hjälp av lotteri. Så i det enkla exemplet ovan kommer Alice och Batya att kasta ett rättvist mynt och vinnaren får det östra rummet.

Historia

Slumpmässig tilldelning nämns redan i Bibeln : ett lotteri användes för att fördela Kanaans länder bland Israels stammar (4 Mosebok 26:55).

I USA användes lotterier för att tilldela offentlig mark till hemman (t.ex. Oklahoma 1901) och för att tilldela radiospektra till sändare (t.ex. FCC 1981-1993). Lotteri används fortfarande för att tilldela gröna kort .

Metoder

Det finns flera sätt att utvidga "myntkastningsmetoden" till situationer där det finns fler än två agenter, och de kan ha olika preferensrelationer på objekten:

  • Random Priority (RP, alias Random Serial Dictatorship eller RSD) är en mycket enkel mekanism som endast kräver att agenter har ordinarie rangordning på enskilda objekt. Den väljer en slumpmässig prioritetsordning på föremålen och låter varje agent i sin tur välja sin återstående favoritartikel.
  • Probabilistic Serial (PS) är en annan mekanism som bara fungerar med ordinal ranking på objekt. Agenter "äter" sina återstående favoritartiklar i konstant hastighet, och andelen varje agent lyckades äta är hans/hennes sannolikhet att få detta föremål.
  • Competitive Equilibrium from Equal Incomes (CEEI) är en marknadsbaserad mekanism: varje artikel ses som en delbar vara. Varje agent får en lika stor budget för en fiat-valuta, sedan får agenterna handla tills det finns en prisjämvikt . Detta är en mer komplex mekanism som kräver att agenterna har fullständiga kardinalfunktioner (eller alternativt ordinarie rangordning på lotterier).

Egenskaper

Effektivitet

En önskad egenskap hos en slumpmässig tilldelningsregel är Pareto-effektivitet (PE). Det finns tre varianter av PE:

  • Ex-post PE innebär att, efter att den slutliga tilldelningen har fastställts, ingen annan tilldelning är bättre för någon agent och minst lika bra för de andra. Alla tre reglerna ovan (RP, PS och CEEI) är PE i efterhand.
  • Ex-ante PE är en starkare egenskap, relevant för agenter med kardinalverktyg. Det betyder att inget annat lotteri är bättre för någon agent och minst lika bra för de andra. CEEI är ex-ante PE när agenter jämför lotterier baserat på deras förväntade nytta.
  • Eventuell PE (eller sd-PE) är en mellanliggande egenskap, relevant för agenter med ordinala verktyg . Det innebär att allokeringen är ex-ante PE för vissa värderingsfunktioner som överensstämmer med agenternas ordinarie rangordning. PS är möjligt-PE, men RP är det inte.

För PE är konsekvenserna: ex-ante → sd(möjligt) → ex-post .

Rättvisa

En annan önskad egenskap är envy-freeness (EF). Återigen finns det tre varianter av EF:

  • EF i efterhand betyder att, efter att den slutliga tilldelningen har fastställts, ingen agent föredrar tilldelningen av en annan agent. Ingen regel tillfredsställer denna starka egenskap; Det kan faktiskt vara omöjligt att hitta en EF-tilldelning i efterhand av odelbara objekt.
  • Ex-ante EF är en svagare egenskap, relevant för agenter med kardinalverktyg. Det betyder att ingen agent föredrar en annan agents lotteri . CEEI är ex-ante EF i förhållande till förväntade verktyg.
  • Nödvändig EF (eller sd-EF) är en mellanliggande egenskap, relevant för agenter med ordinala verktyg . Det betyder att allokeringen är ex-ante EF (se nedan) för alla värderingsfunktioner som överensstämmer med agenternas ordinarie rangordning. PS är nödvändigt-EF, men RP är det inte. RP är svagt ex-ante sd-EF; det är EF när agenter jämför lotterier med lexikografisk dominans (ld-EF).

För EF är implikationsriktningen motsatt till effektiviteten: ex-post → sd(necessary) → ex-ante .

Sanning

En tredje önskad egenskap är sanningsenlighet (även kallad strategisäkerhet). Återigen finns det tre varianter:

  • Ex-ante sanningsenlighet, relevant för agenter med kardinalverktyg, innebär att ingen agent kan få ett bättre lotteri genom att rapportera falska värderingar. Detta är en stark egenskap, som inte tillfredsställs av någon icke-trivial mekanism.
  • Eventuell sanningsenlighet är en svagare egenskap, relevant för agenter med ordinarie verktyg . Det betyder att en agent inte kan få ett stokastiskt dominerande lotteri genom att rapportera en falsk ranking. Denna svaga egenskap uppfylls av PS när alla rankningar är strikta, och det finns högst ett objekt per person. I den här miljön är det också sanningsenlig i förhållande till lexikografisk dominans ( ld-truthful) . Man är inte nöjd när rankingen är svag.
  • Nödvändig sanningsenlighet är en starkare egenskap, relevant för agenter med ordinarie verktyg . Det betyder att en agent som rapporterar en falsk ranking alltid får ett stokastiskt dominerat lotteri. Denna starka egenskap uppfylls av RP, och den kan på ett sanningsenligt sätt utvidgas även till det allmänna fallet när det finns fler föremål än människor.

Följande tabell jämför de olika reglernas egenskaper (RP- och PS-kolumnerna är baserade på ):

#artiklar ≤ #agenter #artiklar > #agenter
RP PS CEEI RP PS CEEI
Effektivitet: Ex-post PE Möjligt PE ex-ante PE Nej möjlig PE ex-ante PE
Rättvisa : Svag sd-EF;

ld-EF

 Nödvändig EF ex-ante EF Svag sd-EF sd-EF EF
Sanning: Nödvändig sanningsenlig Möjligt sd-sanningsfullt; ld-truthful [strikt prefs]

Inga [svaga prefs]

Nej sd-sanning* Nej Nej

Omöjliga kombinationer

Vissa kombinationer av ovanstående tre egenskaper kan inte uppfyllas samtidigt av någon mekanism:

  • För agenter med kardinalhjälpmedel bevisar Zhou att ingen mekanism uppfyller ex-ante-effektivitet , ex-ante-sanning och likabehandling av jämlikar (= agenter med identiska nyttofunktioner bör få samma nytta).
  • Bogomolnaia och Moulin bevisar att ingen mekanism uppfyller möjlig effektivitet , nödvändig sanningsenlighet och likabehandling av jämlikar för agenter med strikt ordinarie nytta .
  • För agenter med svaga ordinarie hjälpmedel bevisar Katta och Sethuraman att ingen mekanism tillfredsställer möjlig effektivitet , möjlig sanningsenlighet och nödvändig avundsfrihet .

Nedbrytning av en bråkdelsallokering

Både PS- och CEEI-reglerna beräknar en matris av förväntade tilldelningar, dvs. de marginella sannolikheter med vilka varje agent tar emot varje objekt. Men eftersom den slutliga tilldelningen måste vara en matchning, måste man hitta en nedbrytning av denna matris till ett lotteri på matchningar.

I den klassiska miljön, där m = n , kan detta göras med hjälp av Birkhoff-algoritmen . Den kan dekomponera vilken som helst n -för- n- matris av agent-objekt-sannolikheter till en konvex kombination av O( n2 ) -permutationsmatriser , som var och en representerar en matchning. Nedbrytningen är dock inte unik, och vissa nedbrytningar kan vara bättre än andra.

Budish, Che, Kojima och Milgrom generaliserar Birkhoffs algoritm till godtyckliga m och n . De tillåter också att lägga till begränsningar på tilldelningarna, under en maximal uppsättning villkor på uppsättningen av begränsningar. De presenterar också en nedbrytningsmetod som minimerar variansen i användbarheten som agenterna upplever mellan de olika matchningarna.

Demeulemeester, Goossens, Hermans och Leus presenterar en polynom-tidsupplösningsalgoritm som maximerar det värsta tänkbara antalet agenter som tar emot ett objekt. Deras algoritm garanterar att det värsta antalet agenter är lika med det förväntade antalet agenter avrundat nedåt, vilket är det bästa möjliga. De presenterar en annan sönderdelningsalgoritm som maximerar det värsta tänkbara antalet tilldelade agenter samtidigt som de garanterar att alla matchningar i sönderdelningen är ex-post PE; den andra algoritmen kan endast användas för deltilldelningar som matas ut av PS, men inte de som motsvarar RP. För RP är det endast möjligt att uppnå en 1/2-faktors approximation till det optimala värsta tänkbara antalet tilldelade medel. För generella fraktionerade tilldelningar är det NP-svårt att maximera det värsta tänkbara antalet tilldelade agenter som är föremål för efterhands-PE. De presenterar också ett kolumngenereringsramverk som kan användas för att optimera andra värsta tänkbara kriterier.

Empirisk jämförelse

Hosseini, Larson och Cohen jämför RP med PS i olika inställningar. De visar att:

  • När det finns högst 2 objekt och högst 3 agenter returnerar RP och PS samma allokering.
  • När det finns högst 2 objekt, för ett valfritt antal agenter, är PS sd-sanning och RP är sd-avundsfri, och i de flesta fall dominerar PS RP, särskilt med 4 eller fler agenter.
  • När det finns 3 eller fler objekt (och 3 eller fler agenter), kan RP och PS returnera olika allokeringar, och ingen allokering Pareto-dominerar den andra. Anta till exempel att det finns tre objekt a,b,c och tre agenter med preferensrankningar (1) a>c>b, (2) a>b>c, (3) b>a>c. Sedan, till medel (1), ger både RP och PS 1/2 a + 1/2 c; till medel (2) ger RP 1/2 a + 1/6 b + 1/3 c medan PS ger 1/2 a + 1/4 b + 1/4 c som är stokastiskt dominant ; och till medel (3) ger RP 5/6 b + 1/6 c medan PS ger 3/4 b + 1/4 c som är stokastiskt dominerad. Så (1) är likgiltig, (2) föredrar strikt PS och (3) föredrar strikt RP.
  • Andelen preferensprofiler för vilka PS sd dominerar RP är stor när antalet agenter och objekt skiljer sig åt, men närmar sig 0 när antalet är lika. Samma sak gäller för ld-herravälde.
  • När agenter är riskneutrala är den förväntade sociala välfärden för PS större än RP, men skillnaden är betydande endast när n≠m . Med RP är andelen avundsjuka medel nära noll när n ≥ m. PS är manipulerbar och vinsten från manipulation ökar när m > n .
  • När agenter är risksökande är den förväntade sociala välfärden för PS större än RP, och skillnaden växer snabbt när n≠m. Däremot, när n = m RP uppnår en högre social välfärd i de flesta fall. Med RP är andelen avundsjuka agenter nära noll när n ≥ m, men genererar avund när m>n. Avunden på RP minskar när risksökandet ökar. Vinsten av att manipulera PS minskar när agenter är mer risksökande.
  • När agenter är riskaversa blir sociala välfärdsgapet mellan RP och PS mindre (men fortfarande statistiskt signifikant). Andelen avundsjuka medel i RP ökar, men avundsjukan förblir under 0,01 när n ≥ m . Manipulerbarheten för PS går till 1 när m / n växer.

Tillägg

Tao och Cole studerar förekomsten av PE- och EF-slumpmässiga tilldelningar när verktygen är icke-linjära (kan ha komplement).

Yilmaz studerar problemet med slumpmässiga tilldelningar där agenter har pengar.

Se även

Hämtad från " https://en.wikipedia.org/w/index.php?title=Fair_random_assignment&oldid=1131424049 "