Abbildungsverzeichnis
Tabellenverzeichnis
1. Einleitung
2. Kombinatorische Auktionen
2.1 Grundlegende Auktionstheorien
2.2 Arten der kombinatorischen Auktionsverfahren
2.2.1 Die geschlossene Auktion
2.2.2 Offene Auktionsverfahren
2.3 Bidding Languages
3. Das Winner Determination Problem
3.1 Formulierung des WDPs
3.2 Resultierende Herausforderungen
4. Lösungsansätze in Form von Heuristiken
4.1 Der Greedy-Algorithmus
4.2 Das GRASP-Verfahren
4.3 Simulated Annealing
5. Implementierungsansatz der Algorithmen
5.1 Die Auktionsumgebung
5.2 Greedy
5.3 GRASP
5.4 Simulated Annealing
5.5 Testergebnisse der Implementierung
5.6 Folgerungen und Aussichten
6. Schlussteil
Anhang
Abbildungen
Tabellen
Literaturverzeichnis
Abb. 1: Greedy-Pseudocode
Abb. 2: GRASP-Pseudocode
Abb. 3: Pseudocode für das Simulated Annealing
Abb. 4: Auszug 1 aus der Methode Greedy der Klasse Auction
Abb. 5: Auszug 2 aus der Methode Greedy der Klasse Auction
Abb. 6: Auszug aus der Methode GRASP der Klasse Auction
Abb. 7: Auszug aus der Methode Simulated_Annealing der Klasse Auction
Abb. 8: 5 Bieter, 10 Güter, Greedy und SA im Vergleich
Abb. 9: 5 Bieter, 10 Güter, GRASP 10, sRCL = 3, lRCL = 6
Abb. 10: 5 Bieter, 10 Güter, GRASP 100, sRCL = 3, lRCL = 6
Abb. 11: Rechenaufwandverteilung bei 8 Bietern, 21 Gütern
Abb. 12: 8 Bieter, 21 Güter, RCL = 6
Abb. 13: Kombinatorische Auktion mit vier Gütern
Abb. 14: Eingabemaske für die Auktionsparameter
Tabelle 1: Beispiel einer Auftragsversteigerung
Tabelle 2: Funktionsweise der Güterbündelüberprüfung
Tabelle 3: Testlauf 1
Tabelle 4: Testlauf 2
„Good auction design is not one size fits all“1
In der Wirtschaftslehre gehört die Auktionstheorie zu den am weitesten studierten und einflussreichsten Themen. Es werden die zwei grundlegendsten Fragen der Wirtschaft nach dem Preis und dem Zuschlag gestellt. Bei der Beantwortung der Fragen stellen Auktionen das kleine Fundament des Marktes. Viele moderne Märkte sind als Auktionen organisiert.2 In klassischen Auktionen werden Güter einzeln und unabhängig voneinander versteigert. Die Entwicklung, Güter zu einem Güterbündel zusammen zu fassen und darauf Gebote abgeben zu können, führte zu dem Konzept der kombinatorischen Auktionen. Diese spezielle Form ermöglichte Bietern neue Varianten bei der Abbildung ihrer Präferenzen. Ein bekanntes Beispiel ist die Einführung einer Verteilungsregel von knappen Zeitfenstern für Starts und Landungen auf großen Flughäfen im Jahre 1968. Wenn Fluggesellschaften ein Zeitfenster am Startflughafen anfordern, besteht eine Abhängigkeit zu dem Zeitfenster der Landung an einem Zielflughafen. Diesem Umstand sollte Aufmerksamkeit verliehen werden. Aus ökonomischer Sicht ist eine Reservierung der Zeitspannen nach dem Aspekt interessant, welche Fluggesellschaft bereit ist am meisten dafür zu zahlen. Die Güter können bei diesen Ansprüchen nicht mehr unabhängig voneinander betrachtet werden. Es wurden Verfahren entwickelt, um die Vergabe der Zeitfenster über kombinatorische Auktionen abzuwickeln.3 Neben den positiven Aspekten ergeben sich gleichzeitig Herausforderungen, die nicht vollständig bewältigt wurden. Diese verhindern in einigen Feldern die Nutzung von kombinatorischen Auktionen. Zu den Hauptgründen gehört das Winner Determination Problem. Als Lösungsansatz sollen Heuristiken helfen, diesem Problem zu begegnen. Der Einsatz einer Heuristik bringt Vor- und Nachteile mit sich. Es stellt sich zusätzlich die Frage, welche Heuristik die besten Ergebnisse erzielt. In dieser Arbeit liegt die Konzentration auf den Suchverfahren Greedy, GRASP und Simulated Annealing.
Viele Probleme in der Auktionstheorie hängen von der Auktionsumgebung und den Auktionsregeln ab.4 Bevor Lösungsansätze diskutiert werden können, sollten die Gründe und die Abhängigkeiten zwischen Auktion und Hürden geklärt werden. Für die theoretische Grundlage wird in dem ersten Teil dieser Arbeit ein Einblick in die Auktionstheorien mit ihren Entwicklungen und Erkenntnissen gegeben. Anschließend werden die verschiedenen Auktionsformen erläutert. Den dritten Abschnitt, über die Einleitung von kombinatorischen Auktionen, bilden die Bidding Languages. Mit Hilfe dieser Grundlagen kann man das Winner Determination Problem formulieren. Die Komplexität ist eine der bestimmenden Faktoren in diesem Problem. Dazu wird zunächst die Komplexität in einer kombinatorischen Auktion dargestellt, um anschließend die Fragen erörtern zu können, die dadurch aufgeworfen werden. Den Schwerpunkt dieser Arbeit bilden Lösungsansätze, die teilweise auf sehr unterschiedlichen Konzepten basieren. Es gibt aktuell viele Algorithmen, Verfahrensweisen und Theorien, die sich mit der Problematik auseinandersetzen. Durch die Komplexität bedingt gibt es keine schnelle Lösung, die sich auf alle kombinatorischen Probleme mit der Garantie eines optimalen Ergebnisses anwenden lässt. Eine Alternative sind die in dieser Arbeit vorgestellten Heuristiken. Sie zeichnet ein im Verhältnis relativ geringer Rechenaufwand aus. Zur Klärung der Funktionsweise wird vor den einzelnen Verfahren die Idee hinter den Heuristiken vorgestellt. Danach folgt die Erläuterung der grundlegenden Funktionsweise, auf welchen die Algorithmen beruhen. Weiterhin werden die Eigenschaften und experimentellen Ergebnisse dargestellt, wie sie in der Literatur zu finden sind.
Um die theoretischen Überlegungen zu überprüfen, wurde im Rahmen dieser Bachelorarbeit ein Programm zur Simulation einer kombinatorischen Auktion implementiert. Dieses Programm ist in der Programmiersprache C# 4.0 geschrieben. Im Rahmen mehrerer Versuchsdurchläufe soll das Verhalten der Heuristiken unter verschiedenen Auktionsbedingungen beobachtet werden. Aufgrund der Abhängigkeit von den Ergebnissen zu den in der Arbeit implementierten Heuristiken ist eine Vorstellung der implementierten Algorithmen vor den Testdurchläufen nötig. Nach der Analyse der Testergebnisse schließen sich Folgerungen aus den Experimenten und mögliche Varianten für weitere Implementierungen an.
Das Ziel der vorliegenden Bachelorarbeit ist es, den wesentlichen Nutzen von kombinatorischen Auktionen in der Wirtschaft zu verdeutlichen trotz der Komplikationen, die sie mit sich bringen. Eine Herausforderung in Form des Winner Determination Problems soll erläutert und der Lösungsansatz der Nutzung von Heuristiken vorgestellt werden. Die genutzten Lösungsvarianten können nur ein Schema darstellen, das spezifiziert werden muss. Die Details der Auktion im Kontext sind entscheidend für den Erfolg. Sollen gute Auktionsmodelle entworfen werden, gibt es keine Lösung die überall anwendbar ist.5
Eine kombinatorische Auktion ist eine spezielle Form der Auktion. Zu den geläufigen Auktionen in Standardform gehört die Englische Auktion, charakterisiert durch aufsteigende Gebote. Diese kann Konsumenten von Onlineplattformen bekannt sein. In vielen öffentlichen Institutionen wird die Bestpreis-Auktion durchgeführt. Hierbei werden alle Gebote für ein Gut entgegengenommen und das höchste gewinnt. Bei dieser Form der Auktion können im Normalfall Gebote für einzelne Güter abgegeben werden. Das Interesse an mehreren Gütern in Kombination kann nicht abgebildet werden. Hat der Bieter die Möglichkeit, auf Güterbündel Gebote abzugeben, wird die Auktion kombinatorisch.6
Die Auktion kann in zwei Optimalitätskriterien eingeteilt werden. Damit ist die Frage gemeint, aus welcher Sicht optimiert werden soll. Ein Kriterium ist die allokative Effizienz. Hier ist mit optimal eine Lösung gemeint, welche den Gesamtnutzen aller Teilnehmer maximiert. Das andere Kriterium ist die Ertragsmaximierung in einer Auktion. Die Allokation soll dahingehend optimiert werden, dass der Ertrag eines Teilnehmers maximiert wird. Im Regelfall ist es der Ertrag des Auktionators.7 Aus dem Bestreben einen maximalen Erlös für den Auktionator zu erzielen, lässt sich das Winner Determination Problem ableiten, für das im Verlauf der Arbeit Lösungsansätze erläutert werden sollen. Diese Form der Optimierung strebt die in dieser Arbeit implementierte Auktion an. Das Optimum kann aus anderer Sicht in einem Minimum liegen. Zum Beispiel wird in der betrieblichen Beschaffung versucht, die Kosten zu minimieren.8 In der Literatur zu den relevanten Heuristiken dieser Arbeit findet man beide Formen der Optimierung.
Eine kombinatorische Auktion erlaubt dem Bieter eine detailreichere Abbildung seiner Präferenzen.9 Dies ist wichtig, wenn es sich bei versteigerten Gütern um Komplementäre handelt. Komplementäre Güter ergänzen sich gegenseitig und ergeben zusammen einen größeren Wert, als wenn sie einzeln veräußert werden würden.10 Dem entgegengesetzt können zwischen Gütern Substitutionseffekte auftreten.11 Ein bekanntes Beispiel ist die seit einigen Jahren erfolgende Vergabe von Frequenzlizenzen durch die US-amerikanische FCC (Federal Communications Commission). Die FCC hat die Lizenzen auf geographische Regionen aufgeteilt. Diese werden derzeit durch simultane aufsteigende Auktionen vergeben.
Bei Auktionen dieser Art, erfolgt die Versteigerung der Frequenzen gleichzeitig.12 Zu beachten sind zum Beispiel bei Mobilfunkanbietern die starken Präferenzen über ein geographisches Gebiet hinaus. Bieter am Frequenzmarkt haben Interesse an den umliegenden Regionen. Bei simultanen Auktionen riskieren sie, lediglich eine Frequenz zu erhalten und für diese noch einen hohen Preis zu bezahlen.13 Schnell könnte man folgern, dass der Einsatz von kombinatorischen Auktionen sinnvoller für die Frequenzvergabe ist. Bei der Aussage muss beachtet werden, dass es Probleme mit dieser Versteigerungsart gibt, welche die FCC nicht als hinreichend gelöst sieht.14 Bevor die Rolle der kombinatorischen Auktionen näher vertieft wird, muss zunächst die Basis der Auktionstheorie geschaffen werden. Sie ist das Fundament für die weiteren Verfahrensmodelle und daraus resultierenden Herausforderungen.
In der Auktionstheorie werden Auktionen nicht ausschließlich durch ihre Regeln bestimmt, wie zum Beispiel aufsteigende oder erstabgegebene Gebote. Die Auktionsumgebung spielt eine wesentliche Rolle bei der Betrachtung. Zu dieser Umgebung gehören die Anzahl der Verkäufer und Käufer, die Anzahl der zu versteigernden Güter, die Präferenzen der Teilnehmer und die Informationen, die es über die Präferenzen der Teilnehmer gibt.15 Als Bezugsumgebung wird das Private-Value-Model nach Vickrey (1961) genommen. Nach diesem hat jeder Bieter eine eigene private Werteinschätzung für jedes Bündel von Gütern. Jedem Bieter sind seine Präferenzen über den Wert des Gutes und seine Vermögensausstattung bekannt. Diese hängen nicht von Informationen über die Präferenzen der anderen Bieter ab.16 1996 wurde an Vickrey der Nobelpreis vergeben, in dem das wegweisende Schriftwerk über die Independent-Private-Value Auktion, bekannt als Auktionsmodell bei Präferenzunsicherheit17, erwähnt wurde. Zentrale Annahmen des Modells sind symmetrische Verhaltens- und Informationsstrukturen. Bezüglich des symmetrischen Verhaltens haben zwei Bieter mit dem gleichen Maximalgebot, das gleiche Bieterverhalten und die gleiche Risikoneigung. Die symmetrische Information setzt die Annahme von den Bietern voraus, dass die Maximalgebote nach einer einheitlichen Wahrscheinlichkeitsverteilung vergeben werden.
Vickrey hat weiterhin das ausgeglichene Bieterverhalten bei Erst-Preis-Auktionen beobachtet. Durch Anpassung einer Preisregel könnte vertrauensvolles Bieten erreicht werden.18 Diese Regel lautet: Jeder Bieter zahlt eher die sozialen Opportunitätskosten seines Gewinnes, als die des Gebotes. Letztendlich hat Vickrey den später bewiesenen Satz über die Erlösäquivalenz dargestellt.19 Verschiedene Auktionsmechanismen, deren Allokationen sich im Gleichgewicht nicht unterscheiden, erzielen den gleichen Verkaufserlös. Ein Beispiel für die Independent- Private-Value Auktion ist die Versteigerung von Kunstvermögen, die später nicht weiterverkauft werden sollen.
1969 hat Wilson mit dem Common-Value-Model, eine neue Betrachtung eingeführt. Dieses wird als Auktionsmodell bei Qualitätsunsicherheit bezeichnet.20 Im Gegensatz zum Private- Value-Model haben die Güter einen einheitlichen Wert für die Bieter. Der Wert ist während der Versteigerung nicht allgemein bekannt und hängt von den privaten Informationen von jedem Bieter ab. Aus der Sicht eines Bieters ist der wahre Wert von der Zahlungsbereitschaft der anderen abhängig. Wilsons Analyse ausgeglichener Auktionen bei gleichen Gutwerten zeigte das Problem des Winner’s Curse auf.21 Gewinner der Common-Value Auktion ist derjenige, der zufällig die optimistischsten Informationen und damit höchste Werteinschätzung des Gutes hat. Der Durchschnitt der Erwartungen bezüglich des wahren Wertes kann unter der Werteinschätzung des Siegers liegen. Nach Bekanntgabe, dass alle anderen Bieter das Gut weniger wertig eingeschätzt haben als der Sieger, könnte dieser das Gut nachträglich wertminderer beurteilen. Die Konsequenz ist ein Vermögensschaden. Durch Gebote, die tatsächlich niedriger sind als der eigene eingeschätzte Wert, soll das Problem des Winner’s Curse minimiert werden.22
Das Private-Value- und Common-Value-Model beschreiben extreme Fälle und sind für die theoretische Erläuterung hilfreich. In der Praxis werden Auktionsumgebungen mit Elementen aus beiden Modellformen genutzt.23 Dies beschrieb Milgrom erstmals 1981. Im Affiliated- Values-Model (Milgrom und Weber 1982) werden die Ansätze der zuvor erläuterten Spezialfälle verallgemeinert.24 Die Kombination von Präferenz- und Qualitätsunsicherheit soll gleichzeitig berücksichtigt werden. Ausgehend von der privaten Werteinschätzung eines Bieters für ein Gut, kommen für alle Bieter auf die Schätzung Einfluss nehmende unbekannte Bestimmungsfaktoren hinzu. Diese können für das zu versteigernde Gut eingeholte Expertisen oder Informationen von Experten sein. Die Werteinschätzung des Bieters hängt direkt von den privaten Informationen aller Bieter ab.25
Während sich die vorangegangenen Analysen an Auktionen im Standardformat orientierten, schaffte Meyerson mit seiner Entwicklung der Mechanismus-Design-Theorie die Möglichkeit für Forscher, optimierte Mechanismen für ein ausgeglichenes Resultat herzuleiten. Ziel der Mechanismen sollte die Maximierung einer bestimmten Zielfunktion sein, zum Beispiel der Gewinn des Verkäufers. 1981 legte Myerson eine erlösmaximierende Auktion mit risikoneutralen Bietern und unabhängigen privaten Informationen fest. Zusätzlich bewies er, dass in ursprünglicher Form von Vickrey hergeleitete Revenue-Equivalence-Theorem. In der Grundform wird zu Myersons Annahmen eine gemeinsame Wahrscheinlichkeitsverteilung der Informationen hinzugefügt. Dann gilt: Alle Auktionsmechanismen, in denen der Bieter mit höchsten Informationen gewinnt und Bieter mit den niedrigsten Informationen kein Gewinn erwartet, führen zum selben erwarteten Gewinn. Als Folgerung gilt eine von den privaten Informationen abhängige Übereinstimmung der Bietergebote zwischen den Auktionsmechanismen.26 Dies gilt sowohl für Auktionen mit Private-Values und Common- Values, aber nicht beim Affiliated-Values-Theorem27
Meyer erkannte, dass jede Auktion als direkter Mechanismus wiedergegeben werden kann. Der Mechanismus bestimmt die Zuweisungen und Zahlungen auf Basis des Vektors mit den Geboten. Für jedes Gleichgewicht in jedem Auktionstyp gibt es einen äquivalenten direkten Mechanismus, durch den die Bieter der Teilnahme zustimmen und vertrauensvoll berichten. Ohne Einschränkung der Allgemeingültigkeit kann sich auf kompatible Anreize und individuell rationale Mechanismen konzentriert werden, um die Eigenschaften aller Auktionen zu verstehen. Kompatible Anreize berücksichtigen die privaten Informationen, die Bieter bei ihrer Wertbeurteilung haben. Die individuelle Rationalität bezieht die freiwillige Beteiligungsentscheidung der Bieter mit ein. Dieses Konzept ist bekannt als Revelation Principle (Offenbarungsprinzip).28 Es besagt, dass jeder nicht zur Wahrheitsbekanntgabe anregende indirekte Mechanismus (bzw. Vertragssituation) in einen direkten Mechanismus übersetzt werden kann, der zur Offenbarung der Wahrheit und bevorzugten Verhaltensweise des Bieters führt.29
Diese Idee wurde von Meyerson und Satterthwaite (1983) genutzt. Sie beweisen eine generelle Unmöglichkeit von effizienten Verhandlungen, wenn die Existenz eines Gewinnes vor der Verhandlung unbekannt ist. Die Vorteilhaftigkeit der Vereinbarungen für alle Vertragspartner ist in dem Fall nicht sicher. Dieselbe Unmöglichkeit lässt sich auf Auktionen erweitern, in denen Käufer und Verkäufer private Informationen haben. Effizienz ist realisierbar, wenn die Händler zusammenwirkend die Verhandlungen durchführen (Crampton, Gibbon und Klemperer 1987). Ebenso können effiziente Mechanismen existieren, wenn die Positionen von Käufer und Verkäufer nicht ex ante (vorher) festgelegt sind und die Händler beide Positionen in Abhängigkeit vom Preis einnehmen können (Wilson 1993).30
Die vorgestellten Veröffentlichungen sind ein kleiner Auszug aus der Entwicklung der Auktionstheorie. Ergänzt wurden diese um zahlreiche empirische und experimentelle Untersuchungen. Sie gehören zu den Grundbausteinen für den aktuellen Fortschritt auf dem Gebiet. Vernachlässigt wurde, dass Bieter in vielen Auktionsumgebungen sich sehr komplex für die Güterbündel interessieren. Diesen Umstand versucht man in kombinatorischen Auktionen zu begegnen.31 Ein Beispiel liefert ein paar Schuhe. Dieses ist für einige Bieter im Ganzen mehr wert als der Wert eines linken und eines rechten Schuhs im Einzelnen. Gleichermaßen kann der Wert eines Güterbündels entgegengesetzt niedriger ausfallen.32
Auktionsverfahren legen die Regeln in Form von Bietprotokollen bei Auktionen fest. Die grundlegenden klassischen Auktionen können in vier Formen eingeteilt werden, die teilweise bei kombinatorischen Auktionen wieder auffindbar sind. Nachfolgend wird die Unterteilung kurz erläutert, um dann anschließend genauer auf die Verfahren eingehen zu können. Unterschieden wird grundsätzlich zwischen geschlossenen und offenen Auktionsverfahren.33 In geschlossenen Verfahren erfolgt die Gebotsabgabe geheim (engl. sealed-bid ).34 Weiterhin können geschlossene Auktionsverfahren in Erstpreis- und Zweitpreisauktionen unterteilt werden. Zu den Erstpreisauktionen (engl. first price ) gehört das Bestpreisverfahren. Den Zweitpreisverfahren (engl. second price ) gehört die Vickrey-Auktion an.
In einer offenen Auktion (engl. open-cry ), kann jeder Bieter die Gebote der anderen Bieter sehen. In der Englischen Auktion gibt es einen aufsteigenden Preis (engl. ascending price ), in der Holländischen Auktion einen absteigenden Preis (engl. descending price ).35 Im Anschluss sollen ausgewählte grundlegende Auktionsformen mit Bezug auf kombinatorische Auktionen erläutert werden.
Das Bestpreis- oder Erstpreisverfahren wurde in der Einleitung zu kombinatorischen Auktionen erwähnt. Die Abgabe der Gebote für Güter erfolgt verschlossen bis zu einem festterminierten Zeitpunkt. Aus diesen wird dann die kostenminimierende oder erlösmaximierende Kombination ausgewählt. Der Gewinner zahlt jeweils sein Gebot. Eigenschaften einfacher Bestpreisauktionen kann man bei den kombinatorischen Verfahrensweisen beobachten. Sie sind stabil gegen Absprachen zwischen den Bietern. Im Vergleich zu anderen Auktionsverfahren erfordert die Bestpreisauktion eine komplexe Strategie. Beispielsweise ein Bieter Lowcost , der die niedrigsten Kosten für ein Gut oder über mehrere Güter hinweg hat. Dieser Bieter kann vermuten, dass die anderen Bieter höhere Kosten haben. Sie bieten über den privaten Kosten von Lowcost. Bei Bietern wie Lowcost, welche die niedrigsten Produktionskosten haben, besteht die Gefahr, dass sie die Auktion mit einer spekulativen Strategie verlieren. Die Herausforderung bei der Strategie liegt in der Festlegung eines optimalen Gebotes. Erstpreisauktionen kommen zum Beispiel bei öffentlichen Bauvorhaben zum Einsatz.36
Die Arbeiten von Vickrey wurden bei den Auktionstheorien aufgegriffen. Obwohl die Vickrey-Auktion ansprechende theoretische Eigenschaften für die betriebliche Beschaffung aufweist, kommt sie in der Praxis eher selten vor.37 Bieter in einer Vickrey-Auktion zahlen nicht den Preis, den sie geboten haben, sondern das Gebot des nächsthöheren Bieters.38 Dieses Auktionsverfahren ist der Zweitpreisform zuzuordnen. Das Ziel ist die Motivation der Auktionsteilnehmer, an ihrer wahren Zahlungsbereitschaft angelehnt, die Gebote zu verteilen. Es gibt keinen Anreiz, mehr oder weniger anzuzeigen. Die Vickrey-Clarke-Groves- Mechanismen bezeichnen eine Klasse strategiebeständiger Mechanismen, welche die Eigenschaften der geschlossenen Auktion aufweisen.39 Diese Mechanismen generalisieren die Vickrey-Auktion auf kombinatorische Auktionen. Auktionen dieser Art werden als verallgemeinerte Vickrey-Auktion (engl. generalized Vickrey-Auction , GVA ) bezeichnet.40 In einer Vickrey-Clark-Grove Auktion können Bieter für alle Güterbündel nach ihren Präferenzen Gebote abgeben. Im Folgenden ein Beispiel einer Auftragsversteigerung für zwei Güter a und b . Die Angebote der Lieferanten werden verschlossen, mit in Tabelle 1 ersichtlichen Werten, an den Auktionator übermittelt. Der Abnehmer hat Interesse daran, die Gesamtkosten zu minimieren. Dementsprechend wählt der Auktionator die kostenminimalste Allokation {a} von Lieferant 2 und {b} von Lieferant 1 im Wert von 30€.
Tabelle 1: Beispiel einer Auftragsversteigerung41
Abbildung in dieser Leseprobe nicht enthalten
Angelehnt an der konventionellen Vickrey-Auktion zahlen die Gewinner nicht den Preis in Höhe ihres Angebotes. Ihnen wird stattdessen ihr Beitrag zur Senkung der Kosten angerechnet. Dieser setzt sich aus der Differenz zum Wert zusammen, der durch eine Verteilung auf den nächsthöheren Bieter erzielt worden wäre.42 Ohne Lieferant 1 wären Gesamtkosten von 32€ entstanden, weil dies der nächstminimalen Allokation von {a, b} entspricht. Resultierend erhält er eine Vickrey-Zahlung von 32 - 30 = 2€. Lieferant 1 zahlt für {b} 13€. Die Nettozahlung an Lieferant 1 beträgt 13 + 2 = 15€. Gleiche Verteilung bei Lieferant 2. Ohne ihn beliefen sich die Gesamtkosten auf 35€ für {a, b}. Dies ergibt eine Vickrey-Zahlung von 35 - 30 = 5€. Da Lieferant 2 für {a} ein Angebot von 17€ abgegeben hat, bekommt er vom Käufer 17 + 5 = 22€ ausgezahlt.43
In diesem Fallbeispiel kann durch die eingesetzten Mechanismen eine Nutzung von überwiegend vertrauensvollen Strategien erzielt werden.44 Die Vickrey-Zahlung erwirkt die dominante Strategie, die Güter privat zu bewerten oder die Gebote an den privaten Herstellungskosten zu orientieren. Es sind Einschränkungen zu beachten.45 Primär sollten die Bieter ihre Werteinschätzung unabhängig von zusätzlichen Informationen über den Preis vollziehen. Bei zu hoher Komplementarität kann der Erlös für den Verkäufer zu gering ausfallen. Die Erhöhung des Preises eines Gutes erwirkt hier ein Fallen des Preises für das komplementäre Gut. Zusätzliche Bieter oder eine wachsende Werteinschätzungsfunktion der Bieter kann den Verkäufererlös weiter vermindern.
In seinen Arbeiten lobt Rothkopf die theoretischen Eigenschaften der Vickrey-Clarke-Groves Mechanismen. In der Praxis sieht er diese als nicht funktionierend. Sie arbeiten nicht, wie sie es der Theorie nach tun sollten. Rothkopf differenziert in seiner Veröffentlichung nach mehreren Problemfeldern bei der Anwendung, die von der Auktionsumgebung abhängig sind.46 Milgrom und Bichler teilen in gewissen Punkten die Ansicht von Rothkopf. Beide sehen auch Auktionsverfahren als nicht praktikabel. Sie führen den hohen Komplexitätsaufwand als Ursache auf. Bei der Komplexität spielt das Winner Determination Problem eine wesentliche Rolle.47 Komplexität in Auktionen und das Winner Determination Problem bilden einen Kernpunkt dieser Arbeit und werden später noch erläutert.
Bei offenen Auktionen können Bieter die Gebote der anderen Wettbewerber einsehen. Das erlaubt Rückschlüsse über die privaten Präferenzen aller Bieter. Die Informationen darüber können zu einer Anpassung der eigenen Bewertung führen. Was sich zunächst negativ anhören kann, gehört zu den Hauptmotivationsfaktoren bei offenen Auktionen. Die Informationen helfen dem Bieter bei seiner ersten vorläufigen Preisbildung, Güterzusammenstellung und Fokussierung seines Schwerpunktes vor der Auktion.48 Offene Auktionen werden im Großteil iterativ (in mehreren Runden), durchgeführt. In kombinatorischen Auktionen müssen potentiell sehr viele Gebote abgegeben werden. Dieser Sachverhalt wird bei den Herausforderungen von kombinatorischen Auktionen noch näher diskutiert. Bei den iterativen Auktionsverfahren sind, durch die Aufteilung auf Runden, weniger Gebote abzugeben. Bei der betrieblichen Beschaffung haben iterative Verfahren Vorteile, die ebenfalls bei kombinatorischen Auktionen gelten.49
Eines davon ist die Möglichkeit, dass Bieter auch in späteren Runden Gebote für Bündel abgeben können, die sie vorher nicht in Betracht gezogen haben.50 Wissenschaftler haben verschiedene iterative kombinatorische Verfahren entworfen und nach Mechanismen geforscht, die wichtige ökonomische Eigenschaften wie Budgetausgeglichenheit, individuelle Rationalität, Strategiebeständigkeit und allokative Effizienz erhalten. Die aus Auktionen resultierende Komplexität für Bieter und Auktionator sollen minimal gehalten werden. Eine Schwierigkeit bei iterativen Mechanismen ist das Schwellwertproblem (engl. threshold problem ).51 Es beinhaltet die Erschwernis, gegen große Bündelgebote anzukommen. In einer Beispielauktion sind drei Bieter bereit, ihre Güter für 7€ aufgrund ihrer privaten Bewertung zu verkaufen. In der aktuellen Runde haben sie jeweils 8€ Geboten. Ein vierter Bieter hat in der selbigen Runde 22€ für das ganze Güterbündel geboten. Alleine kann keiner der drei Bieter das Gebot von Bieter 4 unterbieten, da ein einzelner Bieter mit 6€ unter seinen Kosten liegen würde. Eine Abstimmung unterhalb der Bieter wäre erforderlich, um den Gewinn von Bieter 4 zu vermeiden. In der Praxis ist das diffizil realisierbar. Die Suche nach der effizienten Allokation ist schwer umzusetzen.
In klassischen nichtkombinatorischen Auktionen gewinnt bei gleicher Höhe das Gebot, was zuerst abgegeben wurde. Die Eigenschaft mehrere Gebote zu beinhalten, die zu verschiedenen Zeiten eingehen, macht es bei gleichwertigen Allokationen kompliziert, den Gewinner zu ermitteln. In einer Auktionsrunde können zusätzlich Allokationen mit mehreren Geboten gleiche Gesamtwerte erzielen. Der Gebrauch von Zeitstempeln ist eine potentielle Lösung. Es gewinnt die Allokation, die den im Durchschnitt kleinsten Zeitstempel hat oder die als erstes eine reelle Zusammenstellung repräsentiert.52
Als dritte Schwierigkeit in offenen kombinatorischen Auktionen ist das Bloßstellungsproblem (engl. exposure problem ) zu benennen. Zur Veranschaulichung sollen zwei komplementäre Güter x und y gekauft werden. Möchte ein Bieter eines der Güter verkaufen, kann es zu einem für den Käufer nicht befriedigenden Ergebnis kommen.53 Für Lieferanten wäre es wünschenswert, dass wenn sie in einer neuen Runde Gebote abgeben, die Gebote für komplementäre Güter aus der letzten Runde noch gelten. Durch die Runden ist dieses Problem auf die iterative Verfahrensweise zurückzuführen. Ein Lösungsansatz hierfür ist die logische Verknüpfung von Geboten. Hierzu kommen sogenannte Biet-Sprachen (engl. bidding languages ) zum Einsatz. Die Biet-Sprachen sollen die Gebote einfach und aussagekräftig darstellen.54 Vor der Diskussion des Winner Determination Problem muss zuerst diese Darstellung von Geboten erläutert werden.55
[...]
1 Vgl. Paul Klemperer in „What Really Matters in Auction Design“, S. 184.
2 Vgl. Cramton/Shoham/Steinberg, S. 2.
3 Vgl. Rassenti/Smith/Bulfin, S. 402.
4 Vgl. Cramton/Shoham/Steinberg, S. 3.
5 Vgl. Rothkopf, S. 195.
6 Vgl. Cramton/Shoham/Steinberg, S. 1.
7 Vgl. Nisan/Roughgarden/Tardos et al., S. 268.
8 Vgl. Bichler/Pikovsky/Setzer, S. 137.
9 Vgl. König/Schwind, S. 30.
10 Vgl. Porter/Rassenti/Roopnarine et al., S. 11153.
11 Vgl. de Vries/Vohra, S. 1.
12 Vgl. Rothkopf/Pekec/Harstad, S. 1131.
13 Vgl. Bichler/Pikovsky/Setzer, S. 131.
14 Vgl. Porter/Rassenti/Roopnarine et al., S. 11153.
15 Vgl. Cramton/Shoham/Steinberg, S. 3.
16 Vgl. de Vries/Vohra, S. 46.
17 Vgl. Martini, S. 337.
18 Vgl. Porter/Rassenti/Roopnarine et al., S. 11154.
19 Vgl. Bannier, S. 27.
20 Vgl. Martini, S. 336.
21 Vgl. Thaler, S. 50.
22 Vgl. McAffee/McMillan, S. 721.
23 Vgl. Cramton/Shoham/Steinberg, S. 3.
24 Vgl. Li/Perrigne/Vuong, S. 2.
25 Vgl. Cramton/Shoham/Steinberg, S. 4.
26 Vgl. Bannier, S. 27.
27 Vgl. Li/Perrigne/Vuong, S. 2.
28 Vgl. Peters, S. 1350.
29 Vgl. de Vries/Vohra, S. 46.
30 Vgl. Cramton/Shoham/Steinberg, S. 4.
31 Vgl. Porter/Rassenti/Roopnarine et al., S. 11153.
32 Vgl. Cramton/Shoham/Steinberg, S. 5.
33 Vgl. Klemperer, S. 4 ff.
34 Vgl. Rothkopf, S. 191.
35 Vgl. Klemperer, S. 4 ff.
36 Vgl. Bichler/Pikovsky/Setzer, S. 134.
37 Vgl. Cramton/Shoham/Steinberg, S. 5.
38 Vgl. Rothkopf, S. 191.
39 Vgl. Milgrom, S. 45 f.
40 Vgl. Klemperer, S. 232.
41 Vgl. Bichler/Pikovsky/Setzer, S. 134.
42 Vgl. Milgrom, S. 48 f.
43 Vgl. de Vries/Vohra, S. 49.
44 Vgl. Nisan/Roughgarden/Tardos et al., S. 222.
45 Vgl. Cramton/Shoham/Steinberg, S. 5.
46 Vgl. Rothkopf, S. 192 ff.
47 Vgl. Milgrom, S. 298 f.
48 Vgl. Cramton/Shoham/Steinberg, S. 5.
49 Vgl. Bichler/Pikovsky/Setzer, S. 131.
50 Vgl. Porter/Rassenti/Roopnarine et al., S. 11153.
51 Vgl. Rothkopf/Pekec/Harstad, S. 1132.
52 Vgl. Bichler/Pikovsky/Setzer, S. 131.
53 Vgl. Porter/Rassenti/Roopnarine et al., S. 11153.
54 Vgl. Nisan/Roughgarden/Tardos et al., S. 279.
55 Vgl. Lehmann/Müller/Sandholm, S. 5.
