I

Inhaltsverzeichnis

Abbildungsverzeichnis   II

Tabellenverzeichnis II   

1.  Einleitung  1

2.  Kombinatorische Auktionen  3

2.1  Grundlegende Auktionstheorien  4

2.2  Arten der kombinatorischen Auktionsverfahren  7

2.2.1  Die geschlossene Auktion  8

2.2.2  Offene Auktionsverfahren  10

2.3  Bidding Languages  12

3.  Das Winner Determination Problem  13

3.1  Formulierung des WDPs  14

3.2  Resultierende Herausforderungen  16

4.  Lösungsansätze in Form von Heuristiken  19

4.1  Der Greedy-Algorithmus  21

4.2  Das GRASP-Verfahren  23

4.3  Simulated Annealing  25

5.  Implementierungsansatz der Algorithmen  30

5.1  Die Auktionsumgebung  30

5.2  Greedy  31

5.3  GRASP  32

5.4  Simulated Annealing  32

5.5  Testergebnisse der Implementierung  34

5.6  Folgerungen und Aussichten  38

6.  Schlussteil  39

Anhang   III

Abbildungen   III

Tabellen   II

Literaturverzeichnis   VIII

II

Abbildungsverzeichnis   

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  

Tabellenverzeichnis   

Tabelle 1:  Beispiel einer Auftragsversteigerung  

Tabelle 2:  Funktionsweise der Güterbündelüberprüfung  

Tabelle 3:  Testlauf 1  

Tabelle 4:  Testlauf 2  

1. Einleitung

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. ² 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. ³ 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. ⁴ 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

¹ Vgl. Paul Klemperer in „What Really Matters in Auction Design“, S. 184.

² Vgl. Cramton/Shoham/Steinberg, S. 2.

³ Vgl. Rassenti/Smith/Bulfin, S. 402.

⁴ Vgl. Cramton/Shoham/Steinberg, S. 3.

2

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

⁵ Vgl. Rothkopf, S. 195.

3

2. Kombinatorische Auktionen

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. ⁶ 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. ⁷ 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. ⁸ 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. ⁹ 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. ¹⁰ Dem entgegengesetzt können zwischen Gütern Substitutionseffekte auftreten. ¹¹ 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.

⁶ Vgl. Cramton/Shoham/Steinberg, S. 1.

⁷ Vgl. Nisan/Roughgarden/Tardos et al., S. 268.

⁸ Vgl. Bichler/Pikovsky/Setzer, S. 137.

⁹ Vgl. König/Schwind, S. 30.

¹⁰ Vgl. Porter/Rassenti/Roopnarine et al., S. 11153.

¹¹ Vgl. de Vries/Vohra, S. 1.

4

Bei Auktionen dieser Art, erfolgt die Versteigerung der Frequenzen gleichzeitig. ¹² 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. ¹³ 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. ¹⁴ 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.

2.1 Grundlegende Auktionstheorien

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. ¹⁵ 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. ¹⁶ 1996 wurde an Vickrey der Nobelpreis vergeben, in dem das wegweisende Schriftwerk über die Independent-Private-Value Auktion, bekannt als Auktionsmodell bei Präferenzunsicherheit ¹⁷ , 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.

¹² Vgl. Rothkopf/Pekec/Harstad, S. 1131.

¹³ Vgl. Bichler/Pikovsky/Setzer, S. 131.

¹⁴ Vgl. Porter/Rassenti/Roopnarine et al., S. 11153.

¹⁵ Vgl. Cramton/Shoham/Steinberg, S. 3.

¹⁶ Vgl. de Vries/Vohra, S. 46.

¹⁷ Vgl. Martini, S. 337.

5

Vickrey hat weiterhin das ausgeglichene Bieterverhalten bei Erst-Preis-Auktionen beobachtet. Durch Anpassung einer Preisregel könnte vertrauensvolles Bieten erreicht werden. ¹⁸ 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. ¹⁹ 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. ²⁰ 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. ²¹ 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. ²³ Dies beschrieb Milgrom erstmals 1981. Im Affiliated-Values-Model (Milgrom und Weber 1982) werden die Ansätze der zuvor erläuterten Spezialfälle verallgemeinert. ²⁴ 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

¹⁸ Vgl. Porter/Rassenti/Roopnarine et al., S. 11154.

¹⁹ Vgl. Bannier, S. 27.

²⁰ Vgl. Martini, S. 336.

²¹ Vgl. Thaler, S. 50.

²² Vgl. McAffee/McMillan, S. 721.

²³ Vgl. Cramton/Shoham/Steinberg, S. 3.

²⁴ Vgl. Li/Perrigne/Vuong, S. 2.

6

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. ²⁶ Dies gilt sowohl für Auktionen mit Private-Values und Common-Values, aber nicht beim Affiliated-Values-Theorem 27

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). ²⁸ 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

²⁵ Vgl. Cramton/Shoham/Steinberg, S. 4.

²⁶ Vgl. Bannier, S. 27.

²⁷ Vgl. Li/Perrigne/Vuong, S. 2.

²⁸ Vgl. Peters, S. 1350.

²⁹ Vgl. de Vries/Vohra, S. 46.

7

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). ³⁰ 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. ³¹ 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

2.2 Arten der kombinatorischen Auktionsverfahren

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. ³³ In geschlossenen Verfahren erfolgt die Gebotsabgabe geheim (engl. sealed-bid). ³⁴ 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

³⁰ Vgl. Cramton/Shoham/Steinberg, S. 4.

³¹ Vgl. Porter/Rassenti/Roopnarine et al., S. 11153.

³² Vgl. Cramton/Shoham/Steinberg, S. 5.

³³ Vgl. Klemperer, S. 4 ff.

³⁴ Vgl. Rothkopf, S. 191.

8

der Holländischen Auktion einen absteigenden Preis (engl. descending price). ³⁵ Im Anschluss sollen ausgewählte grundlegende Auktionsformen mit Bezug auf kombinatorische Auktionen erläutert werden.

2.2.1 Die geschlossene Auktion

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. ³⁷ Bieter in einer Vickrey-Auktion zahlen nicht den Preis, den sie geboten haben, sondern das Gebot des nächsthöheren Bieters. ³⁸ 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. ³⁹ Diese Mechanismen generalisieren die Vickrey-Auktion auf kombinatorische Auktionen. Auktionen dieser Art werden als

³⁵ Vgl. Klemperer, S. 4 ff.

³⁶ Vgl. Bichler/Pikovsky/Setzer, S. 134.

³⁷ Vgl. Cramton/Shoham/Steinberg, S. 5.

³⁸ Vgl. Rothkopf, S. 191.

³⁹ Vgl. Milgrom, S. 45 f.