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
6. Schlussteil
Zielsetzung & Themen
Die Arbeit untersucht die Herausforderungen des Winner Determination Problems (WDP) bei kombinatorischen Auktionen und bewertet verschiedene heuristische Lösungsansätze hinsichtlich ihrer Effizienz und Ergebnisqualität durch eine praktische Implementierung in C#.
- Grundlagen und Klassifizierung kombinatorischer Auktionsverfahren
- Formale Analyse und Komplexität des Winner Determination Problems
- Vergleichende Untersuchung der Heuristiken Greedy, GRASP und Simulated Annealing
- Implementierung einer Simulationsumgebung zur Performance-Evaluierung
- Analyse der Rechenzeit und Lösungsqualität in unterschiedlichen Auktionsszenarien
Auszug aus dem Buch
4.1 Der Greedy-Algorithmus
Der Greedy-Algorithmus lässt sich wortwörtlich mit gieriger oder gefräßiger Algorithmus übersetzen. Der Grundgedanke ist die Konstruktion einer Teillösung und das Schrittweise hinzufügen einer neuen Komponente. Der Grund für die Beliebtheit des Algorithmus liegt in seiner Einfachheit. Es ist die „einfache“ Eigenschaft, die hinter der Idee von Greedy steckt.
Das generelle Verfahren lautet: Bestimme einzeln die Werte aller Variablen in einer Entscheidung und übernehme den besten Wert. Die Wahl der im Einzelschritt besten Alternative gibt dem Algorithmus den Namen „Greedy“. Aufgrund der Funktionsweise kann das Verfahren als kurzsichtig bezeichnet werden. Die Auswahl des Optimums bei jeder Einzelentscheidung muss nicht dem Optimum aller Lösungen entsprechen.
Ein einfaches Beispiel für das Greedy-Verfahren ist das Kassierer-Problem. Die meisten Kassierer sind dazu angehalten, dem Kunden beim Wechselgeld in Abhängigkeit der vorhandenen Münzen, so wenige Münzen wie möglich heraus zu geben. Nahezu intuitiv beginnen die Kassierer schrittweise die nächsthöhere Münze auszuzahlen, ohne den Restbetrag zu überschreiten. Sollten dem Kassierer zum Beispiel Cent-Stücke in Höhe von 50, 20, 10, 5 und 1 zur Verfügung stehen, würde er bei einem Rückzahlungsbetrag von 94 Cent zuerst 50, dann zweimal 20 und viermal 1 Cent-Stück herausgeben.
Die Einzelschritte besitzen die drei Eigenschaften Gültigkeit, lokales Optimum und Unumkehrbarkeit. Sie müssen gültig sein mit Bezug auf die Bedingungen der Problemstellung. Bei jedem Schritt wird zum Zeitpunkt der Wahl von allen gültigen Optionen die beste lokale Wahl getroffen. Die Schritte können ein einziges Mal durchgeführt und nicht mehr abgeändert werden. Das ergibt die Unumkehrbarkeit.
Zusammenfassung der Kapitel
1. Einleitung: Einführung in die Auktionstheorie, Definition der kombinatorischen Auktionen und Hinführung zur Problematik des Winner Determination Problems sowie zur Zielsetzung der Arbeit.
2. Kombinatorische Auktionen: Detaillierte Betrachtung verschiedener Auktionsformen, Biet-Sprachen und der theoretischen Grundlagen für kombinatorische Auktionen.
3. Das Winner Determination Problem: Mathematische Definition des WDPs, Analyse der Komplexität und Aufzeigen der Herausforderungen, insbesondere im Vergleich zum Rucksackproblem.
4. Lösungsansätze in Form von Heuristiken: Vorstellung der theoretischen Ansätze von Greedy-Verfahren, GRASP und Simulated Annealing zur Lösung NP-schwerer Optimierungsprobleme.
5. Implementierungsansatz der Algorithmen: Dokumentation der Simulationsumgebung in C# 4.0, der Implementierungsdetails der Algorithmen und Analyse der Testergebnisse.
6. Schlussteil: Zusammenfassung der Erkenntnisse aus der Simulation und Ausblick auf Optimierungspotenziale sowie die Bedeutung der Arbeit für die Wirtschaftsinformatik.
Schlüsselwörter
Kombinatorische Auktionen, Winner Determination Problem, WDP, Heuristiken, Greedy-Algorithmus, GRASP, Simulated Annealing, Auktionsdesign, Allokationseffizienz, Komplexitätstheorie, Metaheuristiken, Bidding Languages, Optimierung, Simulationsumgebung, Wirtschaftsinformatik.
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit behandelt die Herausforderungen bei der Bestimmung von Auktionsgewinnern in komplexen kombinatorischen Auktionen, bei denen Bieter Gebote für Bündel von Gütern abgeben können.
Was sind die zentralen Themenfelder?
Die zentralen Felder sind die Auktionstheorie, die mathematische Formulierung von Optimierungsproblemen (Winner Determination Problem) sowie die Implementierung und der Vergleich effizienter Such-Algorithmen (Heuristiken).
Was ist das primäre Ziel der Bachelorarbeit?
Ziel ist es, den Nutzen kombinatorischer Auktionen in der Wirtschaft aufzuzeigen, das damit verbundene Winner Determination Problem zu erläutern und verschiedene heuristische Lösungsansätze auf ihre praktische Anwendbarkeit hin zu evaluieren.
Welche wissenschaftlichen Methoden werden verwendet?
Neben der theoretischen Herleitung der Komplexität werden die Methoden Greedy, GRASP und Simulated Annealing implementiert und durch simulierte Auktionsdurchläufe empirisch auf ihre Performance und Lösungsqualität geprüft.
Was wird im Hauptteil der Arbeit behandelt?
Der Hauptteil gliedert sich in die theoretische Fundierung der Auktionsmodelle, die mathematische Problemformulierung, die Erläuterung der gewählten Heuristiken und die detaillierte Darstellung der C#-basierten Implementierung und Testergebnisse.
Welche Schlüsselbegriffe charakterisieren die Arbeit?
Die Arbeit lässt sich durch Begriffe wie Kombinatorische Auktionen, Winner Determination Problem, Metaheuristiken, Allokationseffizienz und Rechenkomplexität charakterisieren.
Warum ist das Winner Determination Problem für die Praxis so relevant?
Da es für das WDP bei großen Auktionsumgebungen keine zeitlich effizienten Algorithmen für ein exaktes Optimum gibt, behindert die Komplexität die praktische Anwendung; Heuristiken sollen hier einen praktikablen Kompromiss zwischen Rechenzeit und Lösungsqualität bieten.
Wie unterscheidet sich GRASP in der Implementierung von einem einfachen Greedy-Ansatz?
GRASP erweitert den deterministischen Greedy-Algorithmus um eine Randomisierungskomponente durch eine sogenannte Kandidatenliste (RCL) und ein adaptives Suchverfahren, wodurch die Chancen steigen, nicht in einem lokalen Optimum stecken zu bleiben.
Welche Rolle spielt die Temperatur beim Simulated Annealing im Kontext dieser Simulation?
Die Temperatur fungiert als Kontrollparameter, der im Zeitverlauf abnimmt und entscheidet, mit welcher Wahrscheinlichkeit der Algorithmus auch "schlechtere" Lösungen akzeptiert, um Suchbarrieren zu überwinden und globale Optima besser anzunähern.
- Citar trabajo
- Alexander Rothe (Autor), 2011, Heuristiken für das Winner Determination Problem in Kombinatorischen Auktionen, Múnich, GRIN Verlag, https://www.grin.com/document/172239
