Algoritm för samtidig ätning

En simultanätningsalgoritm (SE) är en algoritm för att allokera delbara objekt mellan agenter med ordinala preferenser . "Ordinala preferenser" betyder att varje agent kan rangordna objekten från bäst till sämst, men inte kan (eller vill) ange ett numeriskt värde för varje objekt. SE-allokeringen tillfredsställer SD-effektivitet - en svag ordinalvariant av Pareto-effektivitet (det betyder att allokeringen är Pareto-effektiv för minst en vektor av additiv nyttofunktioner som överensstämmer med agenternas artikelrankningar).

SE parametriseras av "äthastigheten" för varje medel. Om alla medel ges samma äthastighet, så tillfredsställer SE-tilldelningen SD-avundsfrihet - en stark ordinär variant av avundsfrihet (det betyder att tilldelningen är avundsfri för alla vektorer av additiva nyttofunktioner som överensstämmer med agenterna ' artikelrankningar). Denna speciella variant av SE kallas Probabilistic Serial rule (PS).

SE utvecklades av Hervé Moulin och Anna Bogomolnaia som en lösning på det rättvisa slumpmässiga uppdragsproblemet , där bråkdelen som varje agent får av varje föremål tolkas som en sannolikhet. Om integralen av äthastigheten för alla agenter är 1, så är summan av fraktioner som tilldelats varje agent 1, så matrisen av fraktioner kan delas upp i ett lotteri över uppdrag där varje agent får exakt ett föremål. Med samma äthastigheter är lotteriet avundslöst i förväntan ( ex-ante ) för alla vektorer av nyttofunktioner som överensstämmer med agenternas objektrankningar.

En variant av SE användes också för kakskärning , där tilldelningen är deterministisk (inte slumpmässig).

Beskrivning

Varje föremål representeras som en limpa bröd (eller annan mat). Till en början går varje agent till sitt favoritobjekt och börjar äta det. Det är möjligt att flera agenter äter samma sak samtidigt.

Närhelst ett föremål är uppätet, går var och en av agenterna som åt det till sin återstående favoritvara och börjar äta den på samma sätt, tills alla föremål är förbrukade.

För varje föremål registreras den del av föremålet som äts av varje agent. I samband med slumpmässiga tilldelningar betraktas dessa fraktioner som sannolikheter. Baserat på dessa sannolikheter görs ett lotteri. Typen av lotteri beror på problemet:

Om varje agent tillåts ta emot valfritt antal föremål, kan ett separat lotteri göras för varje föremål. Varje föremål ges till en av agenterna som åt en del av den, vald slumpmässigt enligt sannolikhetsfördelningen för det föremålet.
Om varje agent skulle få exakt ett föremål, måste det finnas ett enda lotteri som plockar en tilldelning med någon sannolikhetsfördelning på uppsättningen av deterministiska tilldelningar. För att göra detta bör n -för- n- matrisen av sannolikheter delas upp i en konvex kombination av permutationsmatriser . Detta kan göras med Birkhoff-algoritmen . Det är garanterat att hitta en kombination där antalet permutationsmatriser som mest är n ² -2 n +2.

En viktig parameter för SE är äthastigheten för varje medel. I det enklaste fallet, när alla agenter har samma rättigheter, är det vettigt att låta alla agenter äta i samma hastighet hela tiden. Men när agenter har olika rättigheter är det möjligt att ge de mer privilegierade agenterna en högre äthastighet. Dessutom är det möjligt att låta äthastigheten ändras med tiden. Det viktiga är att integralen av äthastigheten för varje agent är lika med det totala antalet artiklar som agenten ska ta emot (i uppdragsinställningen ska varje agent få exakt 1 objekt, så integralen av alla äthastighetsfunktioner bör vara 1).

Exempel

Det finns fyra agenter och fyra poster (betecknade w,x,y,z). Agenternas preferenser är:

Alice och Bob föredrar w framför x framför y till z.
Chana och Dana föredrar x framför w till z till y.

Agenterna har lika rättigheter så vi tillämpar SE med lika och enhetlig äthastighet på 1 enhet per minut.

Till en början går Alice och Bob till w och Chana och Dana går till x. Varje par äter sitt föremål samtidigt. Efter 1/2 minut har Alice och Bob vardera 1/2 av w, medan Chana och Dana har 1/2 vardera av x.

Sedan går Alice och Bob till y (deras återstående favoritobjekt) och Chana och Dana går till z (deras återstående favoritobjekt). Efter 1/2 minut har Alice och Bob vardera 1/2 av y och Chana och Dana har varsin 1/2 av z.

Bråkmatrisen är nu:

Alice: 1/2 0 1/2 0

Bob: 1/2 0 1/2 0

Chana: 0 1/2 0 1/2

Dana: 0 1/2 0 1/2

Baserat på de uppätna fraktionerna ges objekt w till antingen Alice eller Bob med lika stor sannolikhet och samma sak görs med objekt y; objekt x ges till antingen Chana eller Dana med lika stor sannolikhet och detsamma görs med objekt z. Om det krävs att ge exakt 1 objekt per agent, delas sannolikhetsmatrisen upp i följande två tilldelningsmatriser:

1 0 0 0 ||| 0 0 1 0

0 0 1 0 ||| 1 0 0 0

0 1 0 0 ||| 0 0 0 1

0 0 0 1 ||| 0 1 0 0

Ett av dessa uppdrag väljs slumpmässigt med en sannolikhet på 1/2.

Andra exempel kan genereras på MatchU.ai-webbplatsen .

Egenskaper

Beskrivningen nedan förutsätter att alla agenter har riskneutrala preferenser , det vill säga att deras nytta från ett lotteri är lika med det förväntade värdet av deras nytta från resultaten.

Effektivitet

SE med vilken vektor som helst av äthastigheter uppfyller en effektivitetsegenskap som kallas SD-effektivitet (även kallad ordningseffektivitet). Informellt betyder det att, med tanke på den resulterande sannolikhetsmatrisen, finns det ingen annan matris som alla agenter svagt-sd-föredrar och åtminstone en agent strikt-sd-föredrar.

I samband med slumpmässiga uppdrag innebär SD-effektivitet efterhandseffektivitet: varje deterministiskt uppdrag som valts av lotteriet är Pareto-effektivt .

En bråkdelstilldelning är SD-effektiv om-och-bara-om det är resultatet av SE för någon vektor av äthastighetsfunktioner.

Rättvisa

SE med lika äthastigheter (kallas PS) uppfyller en rättvisa egenskap som kallas ex-ante stokastisk dominans avundsfrihet (sd-avundsfri). Informellt betyder det att varje agent, med tanke på den resulterande sannolikhetsmatrisen, svagt föredrar sin egen rad av sannolikheter framför raden av någon annan agent. Formellt, för varannan agent i och j :

Agent i har en svagt högre sannolikhet att få sitt bästa föremål på rad i än på rad j ;
Agent i har en svagt högre sannolikhet att få en av sina två bästa objekt i rad i än i rad j ;
...
För varje k ≥ 1, har agent i en svagt högre sannolikhet att få en av sina k bästa objekt i rad i än i rad j .

Observera att sd-envy-freeness garanteras ex-ante : det är rättvist först innan lotteriet äger rum. Algoritmen är naturligtvis inte i efterhand : efter att lotteriet äger rum kan de olyckliga agenterna avundas de lyckliga. Detta är oundvikligt vid tilldelning av odelbara objekt.

PS tillfredsställer en annan rättvisa egenskap, förutom avundsfrihet. Givet eventuell bråkallokering, för varje agent i och positivt heltal k , definiera t ( i , k ) som den totala fraktion som agent i får från sina k översta indifferensklasser. Detta t är en vektor med storlek som högst n * m , där n är antalet agenter och m är antalet objekt. En ordinärt-egalitär allokering är en som maximerar vektorn t i leximinordningen. PS är den unika regeln som ger en ordinärt jämställd tilldelning.

Strategi

SE är inte en sanningsenlig mekanism : en agent som vet att hans mest föredragna föremål inte önskas av någon annan agent, kan manipulera algoritmen genom att äta hans näst mest föredragna föremål, i vetskap om att hans bästa föremål kommer att förbli intakt. Följande är känt om strategisk manipulation av PS:

PS är sanningsenlig när agenter jämför paket med den nedåtgående lexikografiska relationen.
En agent kan i polynomtid beräkna ett bästa svar i förhållande till den nedåtgående lexikografiska relationen. När det finns två agenter kan varje agent beräkna i polynomtid ett bästa svar med förväntad nytta. När antalet agenter kan variera är det NP-svårt att beräkna ett bästa svar inom EU.
Bästa svar wrt förväntat verktyg kan cykla. Det finns dock en ren Nash-jämvikt för hur många medel och föremål som helst. När det finns två agenter finns det linjära tidsalgoritmer för att beräkna en preferensprofil som är i Nash-jämvikt jämfört med de ursprungliga preferenserna. I vissa empiriska miljöer är PS mindre benägen att manipuleras. När en agent är riskvillig och inte har någon information om de andra agenternas strategier, är hans maximinstrategi att vara sanningsenlig.
Ett manipulerande medel kan öka sin användbarhet med en faktor på högst 3/2. Detta observerades först empiriskt i slumpmässiga fall och bevisades sedan formellt.

Observera att regeln om slumpmässig prioritet , som löser samma problem som PS, är sanningsenlig.

Tillägg

SE-algoritmen har utökats på många sätt.

Katta och Sethuraman presenterar Extended PS (EPS), som tillåter svaga ordinarie preferenser (rankningar med likgiltighet). Algoritmen är baserad på att upprepade gånger lösa fall av parametriskt nätverksflöde .
Bogomolnaia presenterade en enklare definition av PS-regeln för svaga preferenser, baserad på leximinordningen .
Yilmaz tillåter både likgiltighet och donationer.
Athanassoglout och Sethuraman presenterar regeln för kontrollerad konsumtion (CC) , som tillåter likgiltighet och bråkdelar av vilken kvantitet som helst.
Budish, Che, Kojima och Milgrom presenterar Generalized PS , som tillåter flera enheter per artikel, fler objekt än agenter, varje agent kan få flera enheter, övre kvoter och bi-hierarkiska begränsningar för genomförbara tilldelningar.
Ashlagi, Saberi och Shameli presenterar en annan generaliserad PS , som tillåter lägre och övre kvoter och distributionsbegränsningar (begränsningar för sannolikhetsfördelningen och inte bara den slutliga tilldelningen).
Aziz och Stursberg presenterar Egalitarian Simultaneous Reservation (ESR) , som tillåter inte bara rättvis fördelning av föremål utan också allmänna sociala valproblem , med möjliga likgiltigheter.
Aziz och Brandl presenterar Vigilant Eating (VE) , vilket tillåter ännu mer allmänna begränsningar.

Garanterar ungefärlig rättvisa i efterhand

Som förklarats ovan är den tilldelning som PS fastställt rättvis endast i förväg men inte i efterhand. Dessutom, när varje agent kan få hur många föremål som helst, kan orättvisan i efterhand vara godtyckligt dålig: teoretiskt sett är det möjligt att en agent får alla föremålen medan andra agenter inte får någon. Nyligen har flera algoritmer föreslagits som garanterar både rättvisa i förväg och ungefärlig rättvisa i efterhand.

Freeman, Shah och Vaish visar:

Recursive Probabilistic Serial (RecPS), som returnerar en sannolikhetsfördelning över tilldelningar som alla är avundsfria-utom-ett-objekt (EF1). Fördelningen är ex-ante EF, och allokeringen är ex-post EF1. En naiv version av denna algoritm ger en fördelning över ett möjligen exponentiellt antal deterministiska tilldelningar, ett stödstorlekspolynom i antalet agenter och varor är tillräckligt, och därför körs algoritmen i polynomtid. Algoritmen använder separeringsorakel .
En annan algoritm, baserad på en ex-ante max-produktallokering, som uppnår ex-ante gruppavundsfrihet (GEF; det innebär både EF och PO), och efterhand PROP1+EF ₁¹_. Detta är den enda tilldelningsregeln som uppnår alla dessa egenskaper. Det kan inte delas upp i EF1-allokeringar.
Dessa kombinationer av egenskaper är bäst möjliga: det är omöjligt att garantera samtidigt ex-ante EF (även PROP) och ex-ante PO tillsammans med ex post EF1; eller ex-ante EF (även PROP) tillsammans med ex-post EF1 och fraktionerad-PO.
RecPS kan modifieras för att uppnå liknande garantier (ex-ante EF och ex-post EF1) för dåliga.

Aziz visar:

PS -lotterialgoritmen , där tilldelningen är ex-ante sd-EF, och lotteriet görs endast bland deterministiska tilldelningar som är sd-EF1, dvs EF- och EF1-garantierna gäller för alla kardinalverktyg som överensstämmer med den ordinarie rankningen . Dessutom är resultatet sd-PO både i förväg och i efterhand. Algoritmen använder både PS-algoritmen och Birkhoff-algoritmen som subrutiner . Förhandstilldelningen är likvärdig med den som returneras av PS; detta visar att resultatet av PS kan delas upp i EF1-allokeringar.
Med binära verktyg är PS-lotterialgoritmen gruppstrategisäker , ex-ante PO, ex-ante EF och ex-post EF1.
Dessa kombinationer av egenskaper är bäst möjliga: det är omöjligt att garantera samtidigt ex-ante sd-EF, ex-post EF1 och ex-post PO; eller ex-ante PO och ex-ante sd-EF.
Att kontrollera om en given slumpmässig allokering kan implementeras genom ett lotteri över EF1 och PO allokering är NP-svårt.

Babaioff, Ezra och Feige visar:

En polynom-tidsalgoritm för beräkning av tilldelningar som är förhandsproportionella och i efterhand både PROP1 och 1/2-fraktion maximin-andel (och även 1/2-fraktion trunkerad-proportionell andel ).
Dessa egenskaper är nästan optimala - det är omöjligt att garantera mer än PROP i förväg och mer än n /(2 n -1) trunkerad proportionell andel i efterhand.

Hoefer, Schmalhofer och Varricchio utvidgar begreppet "Bästa-av-båda-världarna"-lotteri till agenter med olika rättigheter .

Se även

Sidan om rättvis slumpmässig tilldelning jämför PS med andra procedurer för att lösa samma problem, till exempel regeln om slumpmässig prioritet .