Delvis allokeringsmekanism

Partial Allocation Mechanism (PAM) är en mekanism för sanningsenlig resursallokering . Den är baserad på maxproduktallokeringen - allokeringen som maximerar produkten av agenternas verktyg (även känd som Nash-optimal allokering eller Proportionally-Fair-lösningen; i många fall motsvarar den konkurrensjämvikten från lika inkomster). Den garanterar till varje agent minst 0,368 av hans/hennes nytta i maxproduktallokeringen. Den designades av Cole, Gkatzelis och Goel.

Miljö

Det finns m resurser som antas vara homogena och delbara .

Det finns n agenter, som var och en har en personlig funktion som tillskriver ett numeriskt värde till varje "bunt" (kombination av resurser). Värderingen antas vara homogena funktioner .

Målet är att bestämma vilket "paket" som ska ge till varje agent, där ett paket kan innehålla en bråkdel av varje resurs.

Avgörande är att vissa resurser kan behöva kasseras, dvs fritt förfogande förutsätts.

Monetära betalningar är inte tillåtna.

Algoritm

PAM fungerar på följande sätt.

  • Beräkna max-produkttilldelningen; beteckna det med z .
  • För varje agent i :
    • Beräkna maxprodukttilldelningen när i inte är närvarande .
    • Låt f i = (produkten av de andra medlen i z ) / (maxprodukten av de andra medlen när i inte är närvarande).
    • Ge till agent i en bråkdel fi av varje resurs han får i z .

Egenskaper

PAM har följande egenskaper.

  • Det är en sanningsenlig mekanism - varje agents användbarhet maximeras genom att avslöja hans/hennes verkliga värderingar.
  • För varje agent i är nyttan av i minst 1/ e ≈ 0,368 av hans /hennes nytta i maxproduktallokeringen.
  • När agenterna har additiv linjär värdering är allokeringen avundsfri .

PA vs VCG

PA-mekanismen, som inte använder betalningar, är analog med VCG-mekanismen , som använder monetära betalningar. VCG börjar med att välja max-summa allokering, och sedan för varje agent i beräknar den max-summa allokering när i inte är närvarande, och betalar i skillnaden (max-summa när i är närvarande)-(max-summa när i är närvarande) är inte närvarande). Eftersom medlen är kvasilinjära reduceras användbarheten av i av en additiv faktor.

Däremot använder PA inte monetära betalningar, och agenternas verktyg reduceras av en multiplikativ faktor, genom att ta bort en del av deras resurser.

Optimalitet

Det är inte känt om andelen 0,368 är optimal. Det finns dock bevisligen ingen sanningsenlig mekanism som kan garantera varje agent mer än 0,5 av maxproduktens användbarhet.

Tillägg

PAM har använts som en subrutin i en sanningsenlig kardinalmekanism för ensidig matchning.