Sanningsriktig resursallokering

Sanningsfull resursallokering är problemet med att fördela resurser mellan agenter med olika värderingar över resurserna, så att agenter uppmuntras att avslöja sina verkliga värderingar över resurserna.

Modell

Det finns m resurser som antas vara homogena och delbara . Exempel är:

• Material, såsom trä eller metall;
• Virtuella resurser, såsom CPU-tid eller datorminne;
• Finansiella resurser, såsom aktier i företag.

Det finns n agenter. Varje agent har en funktion som tillskriver ett numeriskt värde till varje "paket" (kombination av resurser).

Det antas ofta att agenternas värdefunktioner är linjära , så att om agenten får en bråkdel r _j av varje resurs j , så är hans/hennes värde summan av r _j * v _j .

Designmål

Målet är att utforma en sanningsenlig mekanism , som kommer att få agenterna att avslöja sina verkliga värdefunktioner, och sedan beräkna en allokering som uppfyller vissa rättvisa och effektivitetsmål. De gemensamma effektivitetsmålen är:

• Pareto-effektivitet (PE);
• Utilitär social välfärd --- definierad som summan av agenternas nyttigheter. En allokering som maximerar denna summa kallas utilitaristisk eller maxsumma ; det är alltid PE.
• Nash social välfärd --- definieras som produkten av agenternas hjälpmedel. En tilldelning som maximerar denna produkt kallas Nash-optimal eller max-product eller proportionally-fair ; det är alltid PE. När agenter har tillsatsverktyg är det likvärdigt med konkurrensjämvikten från lika inkomster .

De vanligaste rättvisemålen är:

• Likabehandling av lika (ETE) --- om två agenter har exakt samma nyttofunktion, bör de få exakt samma nytta.
• Avundsfrihet --- ingen agent ska avundas en annan agent. Det innebär ETE.

Triviala algoritmer

Två triviala sanningsenliga algoritmer är:

• Den lika uppdelade algoritmen --- som ger varje agent exakt 1/ n av varje resurs. Denna tilldelning är avundsfri (och uppenbarligen ETE), men vanligtvis är den väldigt ineffektiv.
• Seriediktaturalgoritmen --- som beordrar agenterna godtyckligt och låter varje agent i sin tur ta alla resurser som han vill, bland de återstående . Denna tilldelning är PE, men vanligtvis är den orättvis.

Det är möjligt att blanda dessa två mekanismer och få en sanningsenlig mekanism som är delvis rättvis och delvis effektiv. Men den ideala mekanismen skulle tillfredsställa alla tre egenskaperna samtidigt: sanning, effektivitet och rättvisa.

Högst ett objekt per agent

I en variant av resursallokeringsproblemet, ibland kallat ensidig matchning eller tilldelning , måste den totala mängden objekt som allokeras till varje agent vara högst 1.

När det finns 2 agenter och 2 objekt, uppfyller följande mekanism alla tre egenskaperna: om varje agent föredrar ett annat objekt, ge varje agent sitt föredragna objekt; om båda agenterna föredrar samma objekt, ge varje agent 1/2 av varje objekt (det är PE på grund av kapacitetsbegränsningarna). Men när det finns 3 eller fler medel kan det vara omöjligt att uppnå alla tre egenskaperna.

Zhou bevisade att när det finns 3 eller fler agenter måste varje agent få högst 1 objekt, och varje objekt måste ges till högst 1 agent, ingen sanningsenlig mekanism uppfyller både PE och ETE.

• När det finns flera enheter av varje objekt (men varje agent måste fortfarande få högst 1 objekt) blir det ett svagare omöjlighetsresultat: ingen PE- och ETE-mekanism uppfyller gruppens strategisäkerhet .
• Han lämnar den mer allmänna resursallokeringsinställningen öppen, där varje agent kan få mer än ett objekt.

Det finns analoga omöjlighetsresultat för agenter med ordinala verktyg :

• För agenter med strikta ordinarie verktyg, Bogomolnaia och Moulin bevisar att ingen mekanism uppfyller möjlig-PE, nödvändig-sanning och ETE.
• För agenter med svaga ordinarie hjälpmedel bevisar Katta och Sethuraman att ingen mekanism uppfyller möjlig-PE, möjlig-sanning och nödvändig-avundsfrihet.

Se även: Sanningsriktig ensidig matchning.

Approximationsalgoritmer

Det finns flera sanningsenliga algoritmer som hittar en konstant-faktor approximation av maximal utilitaristisk eller Nash välfärd.

Guo och Conitzer studerade det speciella fallet med n = 2 agenter. För fallet med m = 2 resurser visade de en sanningsenlig mekanism som uppnådde 0,828 av den maximala utilitaristiska välfärden och visade en övre gräns på 0,841. När det gäller många resurser visade de att alla sanningsenliga mekanismer av samma slag närmar sig 0,5 av den maximala utilitaristiska välfärden. Deras mekanismer är kompletta - de allokerar alla resurser.

Cole, Gkatzelis och Goel studerade mekanismer av ett annat slag - baserat på maxproduktallokeringen. För många agenter , med värderingar som är homogena funktioner , visar de en sanningsenlig mekanism som kallas partiell allokering som garanterar varje agent minst 1/ e ≈ 0,368 av hans/hennes nytta i maxproduktallokeringen. Deras mekanism är avundsfri när värderingarna är additiv linjära funktioner. De visar att ingen sanningsenlig mekanism kan garantera alla agenter mer än 0,5 av deras maximala produktnytta.

För det speciella fallet med n=2 agenter visar de en sanningsenlig mekanism som uppnår minst 0,622 av den utilitaristiska välfärden. De visar också att mekanismen som driver lika-delningsmekanismen och partiell tilldelningsmekanismen , och att välja utfallet med högsta sociala välfärd, fortfarande är sanningsenlig, eftersom båda aktörerna alltid föredrar samma resultat . Dessutom uppnår den minst 2/3 av den optimala välfärden. De visar också en ${\displaystyle O(m\log m)}-$ algoritm för att beräkna maxproduktallokeringen, och visar att den Nash-optimala allokeringen i sig uppnår minst 0,933 av den utilitaristiska välfärden.

De visar också en mekanism som kallas Strong Demand Matching, som är skräddarsydd för en miljö med många agenter och få resurser (som privatiseringsauktionen i Tjeckien ) . Mekanismen garanterar till varje agent minst p /( p +1) av maxproduktsnyttan, när p är det minsta jämviktspriset för en resurs när varje agent har en enhetsbudget. När det finns många fler agenter än resurser är priset för varje resurs vanligtvis högt, så approximationsfaktorn närmar sig 1. I synnerhet när det finns två resurser är denna bråkdel minst n /( n +1 ) . Denna mekanism tilldelar varje agent en bråkdel av en enskild resurs.

Cheung förbättrade konkurrensförhållandena för tidigare verk:

• Förhållandet för två agenter och två resurser förbättrades från 0,828 till 5/6 ≈ 0,833 med en fullständig allokeringsmekanism, och strikt mer än 5/6 med en partiell allokeringsmekanism. Den övre gränsen förbättrades från 0,841 till 5/6+epsilon för en fullständig allokeringsmekanism och till 0,8644 för en partiell mekanism.
• Förhållandet för två agenter och många resurser förbättrades från 2/3 till 0,67776, genom att använda ett vägt medelvärde av två mekanismer: partiell allokering och max (partiell allokering, lika-fördelning).

Relaterade problem

• Sanningsriktig kakskärning - en variant av problemet där det finns en enda heterogen resurs ("kaka"), och varje agent har ett personligt värdemått över resursen.
• Strategisk rättvis division - studiet av jämvikter i spel för rättvis division när agenterna agerar strategiskt snarare än uppriktigt.
• Sanningsfull fördelning av två typer av resurser - riklig och knapp.
• Sanningsenlig rättvis uppdelning av odelbara föremål.