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.
Zu den Herausforderungen gehört das Winner Determination Problem. Als Lösungsansatz sollen Heuristiken helfen, diesem Problem zu begegnen. Es stellt sich 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 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.
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. Im Rahmen mehrerer Versuchsdurchläufe soll das Verhalten der Heuristiken unter verschiedenen Auktionsbedingungen beobachtet werden.
Inhaltsverzeichnis
- 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
Zielsetzung und Themenschwerpunkte
Die Bachelorarbeit analysiert das Winner Determination Problem (WDP) im Kontext kombinatorischer Auktionen. Ziel ist es, den Nutzen von kombinatorischen Auktionen für die Wirtschaft zu verdeutlichen und gleichzeitig die Herausforderungen, insbesondere das WDP, zu beleuchten. Die Arbeit präsentiert verschiedene Lösungsansätze für das WDP, insbesondere Heuristiken wie den Greedy-Algorithmus, das GRASP-Verfahren und Simulated Annealing.
- Kombinatorische Auktionen und ihre Anwendungen
- Das Winner Determination Problem und seine Komplexität
- Heuristiken als Lösungsansatz für das WDP
- Die Implementierung und Evaluierung von Heuristiken
- Folgerungen und Ausblick auf zukünftige Forschung
Zusammenfassung der Kapitel
Kapitel 1 führt in die Thematik der kombinatorischen Auktionen ein und verdeutlicht deren Relevanz für die Wirtschaft. Kapitel 2 stellt die grundlegenden Auktionstheorien vor und diskutiert verschiedene Arten kombinatorischer Auktionsverfahren. Kapitel 3 fokussiert auf das Winner Determination Problem, seine Formulierung und die damit verbundenen Herausforderungen. Kapitel 4 präsentiert verschiedene Heuristiken als Lösungsansatz für das WDP, darunter der Greedy-Algorithmus, das GRASP-Verfahren und Simulated Annealing. Kapitel 5 befasst sich mit der Implementierung der Algorithmen und analysiert die Ergebnisse von Testläufen.
Schlüsselwörter
Kombinatorische Auktionen, Winner Determination Problem, Heuristiken, Greedy-Algorithmus, GRASP-Verfahren, Simulated Annealing, Auktionsumgebung, Implementierung, Testergebnisse, Wirtschaft, Ökonomie.
Häufig gestellte Fragen
Was ist das Winner Determination Problem (WDP)?
Das WDP ist die Herausforderung, in einer kombinatorischen Auktion diejenigen Gebote auszuwählen, die den Gesamterlös maximieren, ohne dass ein Gut mehrfach vergeben wird. Es gilt als hochkomplex (NP-schwer).
Warum werden Heuristiken zur Lösung des WDP eingesetzt?
Da es aufgrund der Komplexität oft keine schnelle, exakte Lösung für große Auktionsprobleme gibt, bieten Heuristiken einen effizienten Ausweg mit geringerem Rechenaufwand bei meist sehr guten Ergebnissen.
Was unterscheidet kombinatorische Auktionen von klassischen Auktionen?
In klassischen Auktionen werden Güter einzeln versteigert. Kombinatorische Auktionen erlauben es Bietern, auf ganze Güterbündel zu bieten, was ihre Präferenzen besser abbildet.
Welche spezifischen Heuristiken werden in der Arbeit untersucht?
Die Arbeit konzentriert sich auf die Suchverfahren Greedy-Algorithmus, GRASP (Greedy Randomized Adaptive Search Procedure) und Simulated Annealing.
Was sind Bidding Languages?
Bidding Languages sind formale Sprachen, mit denen Bieter ihre komplexen Gebote und Abhängigkeiten zwischen verschiedenen Gütern in einer kombinatorischen Auktion ausdrücken.
Wie wurden die theoretischen Ansätze in der Arbeit überprüft?
Es wurde ein Simulationsprogramm implementiert, um das Verhalten der verschiedenen Heuristiken unter unterschiedlichen Auktionsbedingungen experimentell zu testen.
- Citation du texte
- Alexander Rothe (Auteur), 2011, Heuristiken für das Winner Determination Problem in Kombinatorischen Auktionen, Munich, GRIN Verlag, https://www.grin.com/document/172239
