Förhandsfri mekanism

En prior-free mechanism (PFM) är en mekanism där designern inte har någon information om agenternas värderingar, inte ens att de är slumpvariabler från någon okänd sannolikhetsfördelning.

En typisk applikation är en säljare som vill sälja vissa varor till potentiella köpare. Säljaren vill prissätta föremålen på ett sätt som maximerar hans vinst. De optimala priserna beror på det belopp som varje köpare är villig att betala för varje vara. Säljaren känner inte till dessa belopp och kan inte ens anta att beloppen är hämtade från en sannolikhetsfördelning . Säljarens mål är att utforma en auktion som ger en rimlig vinst även i värsta fall.

PFM bör jämföras med två andra mekanismtyper:

• Bayesianska-optimala mekanismer (BOM) antar att agenternas värderingar är hämtade från en känd sannolikhetsfördelning. Mekanismen är skräddarsydd efter parametrarna för denna fördelning (t.ex. dess median- eller medelvärde).
• Prior-oberoende mekanismer (PIM) antar att agenternas värderingar är hämtade från en okänd sannolikhetsfördelning. De tar prov från denna fördelning för att uppskatta fördelningsparametrarna.

Ur designerns synvinkel är BOM det enklaste, sedan PIM, sedan PFM. BOM:s och PIM:s uppskattningsgarantier är i väntan, medan de för PFM är i värsta fall.

Vad kan vi göra utan föregående? Ett naivt tillvägagångssätt är att använda statistik : fråga potentiella köpare vad deras värderingar är och använd deras svar för att beräkna en empirisk fördelningsfunktion . Applicera sedan metoderna för Bayesiansk-optimal mekanismdesign på den empiriska distributionsfunktionen.

Problemet med detta naiva tillvägagångssätt är att köparna kan bete sig strategiskt. Eftersom köparnas svar påverkar de priser som de kommer att betala, kan de få incitament att rapportera falska värderingar för att pressa ner priset. Utmaningen i PFMD är att utforma sanningsenliga mekanismer . I sanningsenliga mekanismer kan ombuden inte påverka priserna de betalar, så de har inget incitament att rapportera osanning.

Flera tillvägagångssätt för att utforma sanningsenliga mekanismer utan förutsättning beskrivs nedan.

Deterministisk empirisk fördelning

För varje agent $i$ , låt $F_{-i}$ vara den empiriska fördelningsfunktionen som beräknas baserat på värderingarna av alla agenter utom $i$ . Använd den Bayesianska optimala mekanismen med $F_{-i}$ för att beräkna pris och allokering för agent $i$ .

Uppenbarligen påverkar budet från agent $i$ endast de priser som betalas av andra agenter och inte hans eget pris; därför är mekanismen sanningsenlig.

Denna "empiriska Myerson-mekanism " fungerar i vissa fall men inte i andra.

Här är ett fall där det fungerar ganska bra. Anta att vi är med i en digital varuauktion . Vi ber köparna om deras värdering av varan och får följande svar:

1. 51 köpare bjuder "1$"
2. 50 köpare bjuder "3 $".

För var och en av köparna i grupp 1 är den empiriska fördelningen 50 $1-köpare och 50 $3-köpare, så den empiriska fördelningsfunktionen är "0,5 chans för $1 och 0,5 chans för $3". För var och en av köparna i grupp 2 är den empiriska fördelningen 51 $1-köpare och 49 $3-köpare, så den empiriska fördelningsfunktionen är "0,51 chans för $1 och 0,49 chans för $3". Det Bayesianska optimala priset i båda fallen är $3. Så i det här fallet kommer priset som ges till alla köpare att vara $3. Endast de 50 köparna i grupp 2 går med på det priset, så vår vinst är $150. Detta är en optimal vinst (ett pris på $1, till exempel, skulle ge oss en vinst på endast $101).

I allmänhet fungerar den empiriska Myerson-mekanismen om följande är sant:

• Det finns inga genomförbarhetsbegränsningar (inga problem med inkompatibilitet mellan tilldelningar till olika agenter), som i en digital godsauktion ;
• Värderingen av alla agenter dras oberoende av samma okända fördelning;
• Antalet ombud är stort.

Då närmar sig vinsten av den empiriska Myerson-mekanismen det optimala.

Om några av dessa villkor inte är sanna, kan den empiriska Myerson-mekanismen ha dålig prestanda. Här är ett exempel. Anta att:

1. 10 köpare bjuder "$10";
2. 91 köpare bjuder "1 $".

För varje köpare i grupp 1 är den empiriska distributionsfunktionen "0,09 chans på $10 och 0,91 chans för $1" så det Bayesianska optimala priset är $1. För varje köpare i grupp 2 är den empiriska distributionsfunktionen "0,1 chans på $10 och 0,9 chans för $1" så det Bayesianska optimala priset är $10. Köparna i grupp 1 betalar $1 och köparna i grupp 2 vill inte betala $10, så vi slutar med en vinst på $10. Däremot skulle ett pris på $1 för alla ha gett oss en vinst på $101. Vår vinst är mindre än 10 % av det optimala. Detta exempel kan göras godtyckligt dåligt.

Dessutom kan detta exempel generaliseras för att bevisa att:

Det finns inte konstanter ${\displaystyle b,c} och en symmetrisk deterministisk sanningsenlig auktion$$OPT/bh\cdot c}$ b totalt fall där agenternas värderingar är i $[1,h]$ .

Slumpmässigt urval

Huvudartikel: Slumpmässig samplingsmekanism

I en typisk slumpmässig urvalsmekanism delas de potentiella köparna slumpmässigt upp på två delmarknader. Varje köpare går till varje delmarknad med sannolikhet 1/2, oberoende av de andra. På varje delmarknad beräknar vi en empirisk distributionsfunktion och använder den för att beräkna priserna för den andra delmarknaden. En agents bud påverkar endast priserna på den andra marknaden och inte på hans egen marknad, så mekanismen är sanningsenlig. I många scenarier ger det en bra approximation av den optimala vinsten, även i värsta scenarier; se Slumpmässig urvalsmekanism för referenser.

Konsensusuppskattningar

Huvudartikel: Konsensusuppskattning

En konsensusuppskattning är en funktion som med hög sannolikhet inte kan påverkas av en enskild agent. Om vi ​​till exempel beräknar den maximala vinsten som vi kan extrahera från en given uppsättning köpare, så kan vilken köpare som helst påverka vinsten genom att rapportera osanning. Men om vi avrundar den maximala vinsten till närmaste $1000 under den, och buden begränsas av t.ex. $10, så kommer, med stor sannolikhet, inte ett enda bud att påverka resultatet alls. Detta garanterar att mekanismen är sanningsenlig. Konsensus-uppskattningsfunktionen bör väljas noggrant för att garantera en god vinstapproximation; se konsensusuppskattning för referenser.