Bayesiansk-optimal mekanism

En Bayesian-optimal mechanism (BOM) är en mekanism där designern inte känner till värderingarna av de agenter som mekanismen är designad för, men designern vet att de är slumpvariabler och känner till sannolikhetsfördelningen för dessa variabler.

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 deras 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, men antar att de är hämtade från en viss känd sannolikhetsfördelning . Frasen "Bayesian optimal mekanismdesign" har följande betydelse:

• Bayesian betyder att vi känner till sannolikhetsfördelningen från vilken agenternas värderingar är hämtade (i motsats till prior-free mechanism design , som inte antar någon tidigare sannolikhetsfördelning).
• Optimal innebär att vi vill maximera auktionsförrättarens förväntade intäkter, där förväntningen ligger över slumpmässigheten i agenternas värderingar.
• Mekanism innebär att vi vill utforma regler som definierar en sanningsenlig mekanism , där varje agent har ett incitament att rapportera sitt verkliga värde.

Exempel

Det finns en vara till salu. Det finns två potentiella köpare. Värderingen av varje köpare hämtas iid från den enhetliga fördelningen den [0,1].

Vickrey -auktionen är en sanningsenlig mekanism och dess förväntade vinst, i det här fallet, är 1/3 ( förstaprisauktionen med förseglade bud är en icke sanningsenlig mekanism och dess förväntade vinst är densamma ).

Denna auktion är inte optimal. Det är möjligt att få en bättre vinst genom att sätta ett reservationspris . Vickrey-auktionen med ett reservationspris på 1/2 uppnår en förväntad vinst på 5/12, vilket i detta fall är optimalt.

Notation

Vi antar att agenterna har enparametersfunktioner, till exempel en auktion med enstaka föremål. Varje agent $i$ har ett värde $v_{i}$ som representerar agentens "vinnande värde" (t.ex. agentens värdering av föremålet). Vi känner inte till dessa värden, men vi vet att varje $v_{i}$ dras iid från en viss sannolikhetsfördelning. Vi betecknar med $F_{i}$ den kumulativa fördelningsfunktionen :

$F_{i}(z)=\Pr[v_{i}<z]$

och av $displaystyle f_{i}}$ \ sannolikhetsfördelningsfunktionen :

$f_{i}(z)=F_{i}'(z)$

En allokering är en vektor $x$ , så att för varje $i$ är $x_{i}$ 1 om agent $i$ vinner och 0 annars. Varje tilldelning kan ha en kostnad för auktionsförrättaren, $c(x)$ .

Överskottet av en allokering definieras som :

$S(x)=\summa _{i}x_{i}\cdot v_{i}-c(x)$

Detta är den totala vinsten för agenterna, minus kostnaden för auktionsförrättaren.

Överskottet är största möjliga vinst. Om varje vinnande agent $i$ betalar exakt sitt värde $v_{i}$ , så är auktionsförrättarens vinst exakt överskottet $S(x)$ ; detta innebär att auktionsförrättaren tar allt överskott till sig själv och lämnar ingen nytta åt agenterna.

Denna maximala vinst kan inte uppnås eftersom om auktionsförrättaren försöker debitera varje vinnande agent deras värde v $\displaystyle v_{i}},$ kommer agenterna att ljuga och rapportera ett lägre värde för att betala mindre. Myerson-mekanismen kommer att lösa detta problem.

Myerson-mekanismen

Roger Myerson designade en Bayesiansk-optimal mekanism för enparameters verktygsagenter. Nyckeltricket i Myersons mekanism är att använda virtuella värderingar . För varje agent $i$ , definiera dess virtuella värdering som:

$w_{i}(v_{i})=v_{i}-{\frac {1-F_ {i}(v_{i})}{f_{i}(v_{i})}}$

Observera att den virtuella värderingen vanligtvis är mindre än den faktiska värderingen. Det är till och med möjligt att den virtuella värderingen är negativ medan den faktiska värderingen är positiv.

Definiera det virtuella överskottet för en allokering $x$ som:

$S^{*}(x)=\summa _{i}x_{i}\cdot w_{i} (v_{i})-c(x)$

Observera att det virtuella överskottet vanligtvis är mindre än det faktiska överskottet.

En nyckelsats från Myerson säger att:

Den förväntade vinsten för varje sanningsenlig mekanism är lika med dess förväntade virtuella överskott.

(förväntningen tas över slumpmässigheten i agenternas värderingar).

Denna sats föreslår följande mekanism:

• Be varje agent $i$ att rapportera sin värdering $v_{i}$
• Baserat på svaret och de kända fördelningsfunktionerna $F_{i},f_{i}$ beräkna $w_{i}$ .
• Beräkna en allokering x som maximerar det virtuella överskottet $S^{*}(x)$ .

För att komplettera beskrivningen av mekanismen bör vi specificera priset som varje vinnande agent måste betala. Ett sätt att beräkna priset är att använda VCG-mekanismen på de virtuella värderingarna $w_{i}$ . VCG-mekanismen returnerar både en allokering som maximerar det virtuella överskottet och en prisvektor. Eftersom prisvektorn motsvarar de virtuella värderingarna måste vi konvertera den tillbaka till det reala värderingsutrymmet. Så det sista steget i mekanismen är:

• Ta från varje vinnande agent $i$ priset $p_{i}=w_{i}^{-1}(p'_{i})$ , där $p'_{i}$ är priset som bestäms av VCG-mekanismen.

Sanning

Myerson-mekanismen är sanningsenlig när allokeringsregeln uppfyller den svaga monotoniska egenskapen, dvs. allokeringsfunktionen ökar svagt i agenternas värderingar. VCG-allokeringsregeln är verkligen svagt ökande i värderingarna, men vi använder den med de virtuella värderingarna snarare än de verkliga värderingarna. Därför är Myerson-mekanismen sanningsenlig om de virtuella värderingarna är svagt ökande i de verkliga värderingarna. Dvs, om för alla $i$ : $w_{i}$ är en svagt ökande funktion av $v_{i}$ .

Om $w_{i}$ inte är en svagt ökande funktion av ${\displaystyle v_{i}},$ så kan Myerson-strykning användas.

Myersons mekanism kan användas i olika inställningar. Två exempel presenteras nedan.

Ensauktion

Anta att vi vill sälja en enda vara, och vi vet att värderingarna av alla agenter kommer från samma sannolikhetsfördelning, med funktionerna $F,f$ . Sedan har alla budgivare samma virtuella värderingsfunktion, $w$ . Antag att denna funktion är svagt ökande. I det här fallet reduceras VCG-mekanismen till Vickrey-auktionen : den allokerar föremålet till agenten med den största värderingen (högsta budet). Men Myersons mekanism använder VCG med de virtuella värderingarna, som kan vara negativa. Därför reduceras Myersons mekanism i detta fall till Vickrey-auktion med reservationspris . Den allokerar objektet till agenten med den största värderingen, men bara om dess virtuella värdering är minst 0 . Detta betyder att reservationspriset för Myersons mekanism är exakt:

$w^{-1}(0)$

Så, om vi känner till sannolikhetsfördelningsfunktionerna $F,f$ , kan vi beräkna funktionen ${\displaystyle w} ,$ och utifrån den hitta det optimala reservationspriset.

Digital-varuauktion

I en digital varuauktion har vi ett obegränsat utbud av identiska föremål. Varje agent vill ha högst en vara. Värderingen av agenterna till objektet kommer från samma sannolikhetsfördelning, med funktionerna $F,f$ och virtuell värderingsfunktion $w$ . VCG-mekanismen allokerar ett föremål till varje agent med icke-negativ virtuell värdering och tar ut det lägsta vinstpriset, vilket är:

$w^{-1}(0)$

Detta är exakt lika med det optimala försäljningspriset - priset som maximerar det förväntade värdet av säljarens vinst, givet fördelningen av värderingar:

$\arg \max _{z}{z\cdot (1-F(z))}$

Alternativ

Bayesiansk-optimal mekanismdesign kräver att man känner till fördelningarna från vilka agenternas värderingar hämtas. Detta krav är inte alltid genomförbart. Det finns några andra alternativ:

• När fördelningen inte är känd kan en tidigare oberoende mekanism användas.
• När det inte ens kan antas att agenterna är hämtade från någon sannolikhetsfördelning bör en mekanism utan förutsättning användas.