Oszacowanie konsensusu

Oszacowanie konsensusu to technika projektowania zgodnych z prawdą mechanizmów w ustawieniach projektowania mechanizmów wolnych od uprzednich . Technika ta została wprowadzona na aukcjach towarów cyfrowych , a później rozszerzona na bardziej ogólne ustawienia.

Załóżmy, że istnieje dobro cyfrowe, które chcemy sprzedać grupie kupujących o nieznanych wycenach. Chcemy ustalić cenę, która przyniesie nam maksymalny zysk. Załóżmy, że mamy funkcję, która, biorąc pod uwagę wyceny kupujących, mówi nam maksymalny zysk, jaki możemy osiągnąć. Możemy go wykorzystać w następujący sposób:

1. Poproś kupujących, aby przedstawili swoje wyceny.
2. Oblicz maksymalny możliwy zysk, biorąc pod uwagę wyceny. ${\ displaystyle R_ {max}}$
3. Oblicz cenę, która gwarantuje, że uzyskamy zysk ${\ displaystyle R_ {max}}$ .

Krok 3 można osiągnąć za pomocą mechanizmu pozyskiwania zysków , który jest mechanizmem zgodnym z prawdą . Jednak generalnie mechanizm nie jest zgodny z prawdą, ponieważ kupujący mogą $licytując$ strategicznie Aby rozwiązać ten problem, możemy zastąpić dokładny $\ Displaystyle R_$ - na które z dużym prawdopodobieństwem nie ma wpływu $aplikacja}$ pojedynczy agent.

Jako przykład załóżmy, że wiemy, że wycena każdego pojedynczego agenta wynosi co najwyżej 0,1. Jako pierwszą próbę oszacowania konsensusu, niech ${\ Displaystyle R_ {aplikacja} = \ lfloor R_ {max} \ rfloor}$ = wartość ${\ Displaystyle R_{max}}$ zaokrąglone do najbliższej liczby całkowitej poniżej. Intuicyjnie, w $}$ p { $}}$$aplikacja$ , wtedy pojedynczy agent może zmienić go tylko na między ${\ Displaystyle R_ {max} = 56,6}$ a ${\ Displaystyle R_ {max} = 56,8}$ , ale we wszystkich przypadkach ${\ Displaystyle R_ {aplikacja} = 56}$ ).

Aby pojęcie „większości przypadków” było dokładniejsze, zdefiniuj: ${\ Displaystyle R_ {aplikacja} = \ lfloor R_ {max} + U \ rfloor}$ , gdzie ${ \displaystyle U}$ jest zmienną losową wylosowaną równomiernie z ${\ displaystyle [0,1]}$ . To sprawia, że ${\ displaystyle R_ {aplikacja}}$ jest również zmienną losową. Z prawdopodobieństwem co najmniej 90% $mieć$$nie$ wpływu na żaden pojedynczy agent, więc mechanizm wykorzystujący z prawdą z dużym

Taka zmienna losowa nazywana jest oszacowaniem konsensusu : ${\ displaystyle R_ {aplikacja}}$

• „Konsensus” oznacza, że ​​z dużym prawdopodobieństwem pojedynczy agent nie może wpłynąć na wynik, tak więc istnieje zgodność między wynikami z agentem lub bez niego.
• „Oszacowanie” oznacza, że ​​zmienna losowa jest zbliżona do zmiennej rzeczywistej, którą jesteśmy zainteresowani - zmiennej ${\ displaystyle R_ {max}}$ .

Wady stosowania szacunków konsensusu to:

• Nie daje nam to zysku optymalnego - ale daje nam zysk w przybliżeniu optymalny.
• Nie jest to do końca zgodne z prawdą – jest jedynie „prawdziwe z dużym prawdopodobieństwem” (prawdopodobieństwo, że agent może zyskać na odstępstwie, spada do 0, gdy rośnie liczba wygrywających agentów).

W praktyce zamiast zaokrąglania w dół do najbliższej liczby całkowitej, lepiej zastosować zaokrąglanie wykładnicze - zaokrąglanie w dół do najbliższej potęgi jakiejś stałej. W przypadku towarów cyfrowych wykorzystanie tego konsensusu pozwala nam osiągnąć co najmniej 1/3,39 optymalnego zysku, nawet w najgorszych scenariuszach.

Zobacz też

• Mechanizm losowego próbkowania - alternatywne podejście do projektowania mechanizmu bez uprzedniego .