Vickrey-Auktion - Vickrey auction

Teil einer Serie über
Auktionen
Typen
All-Pay Amsterdam Englisch-Niederländisch Tausch doppelt Am besten/nicht am besten Brasilianisch Kalkutta Kerze Chinesisch Click-Box-Gebote Kombinatorisch Allgemeiner Wert Aufgeschobene Annahme Diskriminierender Preis Doppelt Niederländisch Englisch Nach vorne Französisch Generalisierter Erstpreis Generalisierter Zweitpreis japanisch Mehrfachattribute Multiunit Keine Reserve Rang Umkehren schottisch Versiegelter erster Preis Gleichzeitiges Aufsteigen Einzelpreis Ampel Einheitspreis Einmaliges Gebot Wert der Einnahmen Vickrey Vickrey–Clarke–Groves Walrasier Yankee-
Bieten
Schattierung Calor licitantis Stornierungsjagd Springen Takelwerk Scharfschützen Selbstmord Stillschweigende Absprachen
Kontexte
Algorithmen Autos Kunst Wohltätigkeit Kinder Cricket-Spieler Domain Namen Blumen Kredite Betrug Sklaven Spektrum Briefmarken Jungfräulichkeit Wein Ehefrauen
Theorie
Digitale Güter Preis der Anarchie Umsatzäquivalenz Fluch des Gewinners
Online
Ebidding Privater elektronischer Markt Software
v T e

Eine Vickrey-Auktion oder Sealed-Bid-Second-Price-Auktion ( SPSBA ) ist eine Art von Sealed-Bid- Auktion . Bieter geben schriftliche Gebote ab, ohne das Gebot der anderen Auktionsteilnehmer zu kennen. Der Höchstbietende gewinnt, aber der gezahlte Preis ist das zweithöchste Gebot. Diese Art der Auktion ähnelt strategisch einer englischen Auktion und gibt Bietern einen Anreiz, ihren wahren Wert zu bieten . Die Auktion wurde erstmals 1961 vom Columbia University- Professor William Vickrey wissenschaftlich beschrieben, wurde jedoch seit 1893 von Briefmarkensammlern genutzt. 1797 verkaufte Johann Wolfgang von Goethe ein Manuskript in einer Zweitpreisauktion mit versiegeltem Gebot.

Vickreys Originalarbeit betrachtete hauptsächlich Auktionen, bei denen nur ein einziges, unteilbares Gut verkauft wurde. Die Begriffe Vickrey-Auktion und Zweitpreis-Auktion mit geschlossenem Gebot sind in diesem Fall nur gleichwertig und werden austauschbar verwendet. Bei mehreren identischen Gütern legen die Bieter inverse Nachfragekurven vor und zahlen die Opportunitätskosten.

Vickrey-Auktionen sind in der Wirtschaftsliteratur viel untersucht, in der Praxis jedoch selten. Es gibt generalisierte Varianten der Vickrey-Auktion für Multiunit-Auktionen , wie die generalisierte Zweitpreisauktion , die in den Online-Werbeprogrammen von Google und Yahoo! verwendet wird (nicht anreizkompatibel ) und die Vickrey-Clarke-Groves-Auktion (anreizkompatibel).

Eigenschaften

Selbstoffenbarung/Anreizkompatibilität

In einer Vickrey-Auktion mit privaten Werten maximiert jeder Bieter seinen erwarteten Nutzen, indem er seine Bewertung des zum Verkauf stehenden Artikels bietet (enthüllt). Diese Art von Auktionen werden manchmal für den Handel mit bestimmten Pools auf dem Markt für hypothekenbesicherte Wertpapiere (MBS) von Agenturen verwendet.

Ex-post-Effizienz

Eine Vickrey-Auktion ist unter den allgemeinsten Umständen entscheidungseffizient (der Gewinner ist der Bieter mit der höchsten Bewertung); es liefert somit ein Basismodell, mit dem die Effizienzeigenschaften anderer Auktionstypen verglichen werden können. Es ist nur ex-post effizient (Summe der Transfers gleich Null), wenn der Verkäufer als „Spieler Null“ aufgenommen wird, dessen Transfer gleich dem Negativen der Summe der Transfers der anderen Spieler (dh der Gebote) ist.

Schwächen

• Es erlaubt keine Preisfindung , d. h. die Ermittlung des Marktpreises, wenn die Käufer sich ihrer eigenen Bewertungen nicht sicher sind, ohne sequentielle Auktionen.
• Verkäufer können Shill- Gebote verwenden, um den Gewinn zu steigern.

Der Vickrey-Clarke-Groves (VCG)-Mechanismus weist die zusätzlichen Mängel auf:

• Es ist anfällig für Absprachen mit Bietern . Wenn sich alle Bieter in der Vickrey-Auktion gegenseitig ihre Bewertungen mitteilen, können sie ihre Bewertungen teilweise oder vollständig senken, während der Gewinner der Auktion beibehalten wird.
• Es ist anfällig für eine Version von Shill Bidding, bei der ein Käufer mehrere Identitäten in der Auktion verwendet, um seinen Gewinn zu maximieren.
• Es maximiert nicht unbedingt den Verkäuferumsatz; Verkäufereinnahmen können bei VCG-Auktionen sogar Null sein. Wenn der Zweck der Durchführung der Auktion darin besteht, den Gewinn für den Verkäufer zu maximieren, anstatt nur den Käufern Ressourcen zuzuweisen, kann VCG eine schlechte Wahl sein.
• Die Umsätze des Verkäufers sind hinsichtlich der Bieter- und Angebotsmengen nicht monoton .

Die Nichtmonotonie der Verkäufererlöse in Bezug auf Gebote (ohne Einführung des am Ende dieses Artikels beschriebenen VCG-Opportunitätskostenmechanismus) kann durch das folgende Beispiel gezeigt werden. Betrachten Sie 3 Bieter A, B und C und zwei homogene Gebote, Y und Z.

• A möchte beide Artikel und bietet $2 für das Paket von Y und Z.
• B und C bieten beide jeweils 2 USD für einen einzelnen Artikel (bieten Sie 2 USD für Y oder Z), da sie wirklich einen Artikel wollen, sich aber nicht darum kümmern, ob sie den zweiten haben.

Jetzt werden Y und Z B und C zugewiesen, aber der Preis beträgt 0 $, wie durch Entfernen von B bzw. C festgestellt werden kann. Bietet C 0 $ statt 2 $, dann würde der Verkäufer 2 $ statt 0 $ machen. Da die Einnahmen des Verkäufers steigen können, wenn die Gebote entweder erhöht oder gesenkt werden, sind die Einnahmen des Verkäufers in Bezug auf die Gebote nicht monoton.

Nachweis der Dominanz wahrheitsgetreuer Gebote

Die vorherrschende Strategie in einer Vickrey-Auktion mit einem einzigen, unteilbaren Artikel besteht darin, dass jeder Bieter seinen wahren Wert des Artikels bietet.

Sei i der Wert Bieter für das Element sein. Lassen Sie Bieter i für den Artikel bieten. Die Auszahlung für Bieter i ist${\displaystyle v_{i}}$${\displaystyle b_{i}}$${\displaystyle {\begin{Fälle}v_{i}-\max _{j\neq i}b_{j}&{\text{if }}b_{i}>\max _{j\neq i}b_ {j}\\0&{\text{sonst}}\end{cases}}}$

Die Strategie des Überbietens wird durch wahrheitsgetreues Bieten dominiert. Angenommen, Bieter i bietet . ${\displaystyle b_{i}>v_{i}}$

Wenn dann der Bieter den Artikel mit einem wahrheitsgetreuen Gebot sowie einem Übergebot gewinnen würde. Der Betrag des Gebots ändert die Auszahlung nicht, daher haben die beiden Strategien in diesem Fall die gleichen Auszahlungen. ${\displaystyle \max_{j\neq i}b_{j}<v_{i}}$

Wenn dann der Bieter den Artikel so oder so verlieren würde, haben die Strategien in diesem Fall die gleichen Auszahlungen. ${\displaystyle \max_{j\neq i}b_{j}>b_{i}}$

Wenn dann nur die Strategie des Überbietens die Auktion gewinnen würde. Die Auszahlung wäre für die Strategie des Überbietens negativ, da sie mehr als ihren Wert des Artikels bezahlt haben, während die Auszahlung für ein wahrheitsgetreues Gebot null wäre. Somit wird die Strategie des Bietens über der wahren Bewertung von der Strategie des wahrheitsgetreuen Bietens dominiert. ${\displaystyle v_{i}<\max _{j\neq i}b_{j}<b_{i}}$

Die Strategie des Unterbietens wird durch wahrheitsgetreues Bieten dominiert. Angenommen, Bieter i bietet . ${\displaystyle b_{i}<v_{i}}$

Wenn dann der Bieter sowohl bei einem wahrheitsgetreuen als auch bei einem unterbotenen Gebot den Artikel verlieren würde, so haben die Strategien für diesen Fall gleiche Auszahlungen. ${\displaystyle \max_{j\neq i}b_{j}>v_{i}}$

Wenn dann der Bieter den Artikel so oder so gewinnen würde, haben die Strategien in diesem Fall die gleichen Auszahlungen. ${\displaystyle \max_{j\neq i}b_{j}<b_{i}}$

Wenn dann nur die Strategie des wahrheitsgetreuen Bietens die Auktion gewinnen würde. Die Auszahlung für die wahrheitsgetreue Strategie wäre positiv, da sie weniger als ihren Wert des Artikels bezahlt haben, während die Auszahlung für ein unterbietendes Gebot null wäre. Somit wird die Strategie des Unterbietens von der Strategie des wahrheitsgetreuen Bietens dominiert. ${\displaystyle b_{i}<\max _{j\neq i}b_{j}<v_{i}}$

Wahres Bieten dominiert die anderen möglichen Strategien (Unterbieten und Überbieten) und ist somit eine optimale Strategie.

Äquivalenz der Einnahmen der Vickrey-Auktion und der versiegelten Erstpreisauktion

Die beiden häufigsten Auktionen sind die Sealed First Price (oder High-Bid) Auktion und die offene aufsteigende (oder englische) Auktion. Bei ersterem gibt jeder Käufer ein versiegeltes Gebot ab. Der Höchstbietende erhält den Zuschlag und zahlt sein Gebot. Bei letzterem kündigt der Auktionator sukzessive höhere Angebotspreise an und fährt fort, bis niemand mehr bereit ist, einen höheren Preis zu akzeptieren. Angenommen, die Bewertung eines Käufers ist und der aktuelle Angebotspreis ist . Wenn , dann verliert der Käufer, indem er seine Hand hebt. Wenn der Käufer nicht der aktuelle Höchstbietende ist, ist es rentabler zu bieten, als jemanden anderen als Gewinner zu überlassen. Daher ist es eine dominante Strategie für einen Käufer, aus dem Bieten auszusteigen, wenn der Angebotspreis seine Bewertung erreicht. Somit ist, wie bei der Vickrey Sealed Second Price Auction, der vom Käufer mit der höchsten Bewertung gezahlte Preis gleich dem zweithöchsten Wert. ${\displaystyle v}$${\displaystyle b}$${\displaystyle v<b}$${\displaystyle v>b}$

Betrachten Sie dann die erwartete Zahlung in der versiegelten Zweitpreisauktion. Vickrey betrachtete den Fall von zwei Käufern und ging davon aus, dass der Wert jedes Käufers eine unabhängige Ziehung aus einer einheitlichen Verteilung mit Unterstützung war . Wenn Käufer nach ihren dominanten Strategien bieten, gewinnt ein Käufer mit Bewertung, wenn der Wert seines Gegners . Angenommen, das ist der hohe Wert. Dann wird die Gewinnauszahlung gleichmäßig auf das Intervall verteilt und somit ist die erwartete Auszahlung des Gewinners ${\displaystyle [0,1]}$${\displaystyle v}$${\displaystyle x<v}$${\displaystyle v}$${\displaystyle [0,v]}$

${\displaystyle e(v)={\tfrac {1}{2}}v}$.

Wir argumentieren nun , dass in der abgedichteten ersten Preis Auktion das Gleichgewicht Gebot eines Käufers mit Bewertung ist ${\displaystyle v}$

${\displaystyle B(v)=e(v)={\tfrac {1}{2}}v}$.

Das heißt, die Auszahlung des Gewinners in der versiegelten Erstpreisauktion entspricht den erwarteten Einnahmen in der versiegelten Zweitpreisauktion.

Nachweis der Umsatzgleichheit

Angenommen, Käufer 2 bietet gemäß der Strategie , wobei das Gebot des Käufers für eine Bewertung ist . Wir müssen zeigen, dass die beste Reaktion von Käufer 1 darin besteht, dieselbe Strategie zu verwenden. ${\displaystyle B(v)=v/2}$${\displaystyle B(v)}$${\displaystyle v}$

Beachten Sie zunächst, dass, wenn Käufer 2 die Strategie anwendet, das Höchstgebot von Käufer 2 beträgt und Käufer 1 mit Wahrscheinlichkeit 1 mit einem Gebot von 1/2 oder mehr gewinnt. Betrachten Sie dann ein Gebot für das Intervall . Der Wert von Käufer 2 sei . Dann gewinnt Käufer 1 wenn , dh wenn . Unter Vickreys Annahme gleichverteilter Werte beträgt die Gewinnwahrscheinlichkeit . Die erwartete Auszahlung von Käufer 1 ist daher ${\displaystyle B(v)=v/2}$${\displaystyle B(1)=1/2}$${\displaystyle b}$${\displaystyle [0,1/2]}$${\displaystyle x}$${\displaystyle B(x)=x/2<b}$${\displaystyle x<2b}$${\displaystyle w(b)=2b}$

${\displaystyle U(b)=w(b)(vb)=2b(vb)={\tfrac {1}{2}}[{{v}^{2}}-{{(v-2b)} ^{2}}]}$

Beachten Sie, dass das Maximum bei . ${\displaystyle U(b)}$${\displaystyle b=v/2=B(v)}$

Verwendung im Netzwerkrouting

Beim Netzwerk-Routing sind VCG-Mechanismen eine Familie von Zahlungssystemen , die auf dem Mehrwertkonzept basieren . Die Grundidee eines VCG-Mechanismus beim Netzwerk-Routing besteht darin, dem Eigentümer jedes Links oder Knotens (je nach Netzwerkmodell), der Teil der Lösung ist, seine deklarierten Kosten plus seinen Mehrwert zu bezahlen . Bei vielen Routingproblemen ist dieser Mechanismus nicht nur strategiesicher , sondern auch das Minimum unter allen strategiesicheren Mechanismen.

Im Fall von Netzwerkflüssen, Unicast oder Multicast , wird ein Mindestkostenfluss (MCF) in Grafik G basierend auf den angegebenen Kosten d _k jeder der Verbindungen berechnet und die Zahlung wird wie folgt berechnet:

Jeder Link (oder Knoten) im MCF wird bezahlt ${\displaystyle \scriptstyle e_{k}}$

${\displaystyle p_{k}=d_{k}+MCF(G-e_{k})-MCF(G)}$,

wobei MCF( G ) die Kosten des minimalen Kostenflusses in Graph G angibt und G  −  e _k Graph G ohne den Link e _{k bezeichnet} . Links, die nicht im MCF sind, werden nichts bezahlt. Dieses Routingproblem ist einer der Fälle, für die VCG strategiesicher und minimal ist.

Im Jahr 2004 wurde gezeigt , dass die erwartete VCG Überbezahlung eines Erdős-Rényi Zufallsgraphen mit n Knoten und Kanten Wahrscheinlichkeit p , nähert ${\displaystyle \scriptstyle G\in G(n,p)}$

${\displaystyle {\frac {p}{2-p}}}$

als n nähert sich z . Vor diesem Ergebnis war bekannt, dass die VCG-Überzahlung in G ( n ,  p ) ist ${\displaystyle \scriptstyle \infty}$${\displaystyle np=\omega ({\sqrt {n\log n}})}$

${\displaystyle \Omega \left({\frac {1}{np}}\right)}$

und

${\displaystyle O(1)\,}$

mit hoher Wahrscheinlichkeit gegeben

${\displaystyle np=\omega (\log n).\,}$

Verallgemeinerungen

Die offensichtlichste Verallgemeinerung auf mehrere oder teilbare Güter besteht darin, dass alle erfolgreichen Bieter den Betrag des höchsten nicht erfolgreichen Gebots zahlen. Dies wird als Einheitspreisauktion bezeichnet . Die Einheitspreisauktion führt jedoch nicht dazu, dass Bieter wie bei einer Zweitpreisauktion ihre wahren Bewertungen bieten, es sei denn, jeder Bieter hat nur eine Nachfrage nach einer einzigen Einheit. Eine Verallgemeinerung der Vickrey-Auktion, die den Anreiz aufrechterhält, wahrheitsgetreu zu bieten, ist als Vickrey-Clarke-Groves (VCG)-Mechanismus bekannt. Die Idee in VCG besteht darin, dass Elemente zugewiesen werden, um die Summe der Nutzen zu maximieren; dann zahlt jeder Bieter die "Opportunitätskosten", die seine Anwesenheit allen anderen Spielern einbringt. Diese Opportunitätskosten für einen Bieter sind definiert als die Gesamtgebote aller anderen Bieter, die gewonnen hätten, wenn der erste Bieter nicht geboten hätte, abzüglich der Gesamtgebote aller anderen tatsächlich gewonnenen Bieter.

Eine andere Art der Verallgemeinerung besteht darin, einen Reservierungspreis festzulegen – einen Mindestpreis, unter dem der Artikel überhaupt nicht verkauft wird. In einigen Fällen kann die Festlegung eines Reservierungspreises die Einnahmen des Auktionators erheblich steigern. Dies ist ein Beispiel für ein Bayesian-optimales Mechanismusdesign .

Siehe auch

• Auktionstheorie
• Erstpreis-Auktion mit geschlossenem Gebot
• VCG-Auktion

Verweise

• Vijay Krishna, Auktionstheorie , Academic Press, 2002.
• Peter Cramton, Yoav Shoham, Richard Steinberg (Hrsg.), Combinatorial Auctions , MIT Press, 2006, Kapitel 1. ISBN  0-262-03342-9 .
• Paul Milgrom, Putting Auction Theory to Work , Cambridge University Press, 2004.
• Teck Ho, "Verbrauch und Produktion" UC Berkeley, Haas-Klasse von 2010.

Anmerkungen