Auktionen sind ein wichtiger Marktmechanismus für Güter deren Preis nicht eindeutig vorgegeben ist. Die Preisbildung und Allokation erfolgt auf Basis von Geboten. Kombinatorische Auktionen erlauben es, Gebote nicht nur für einzelne Güter, sondern
auch für Kombinationen von Gütern, sog. Güterbündel, abzugeben. Dies kann sinnvoll sein, da der Preis, den ein Bieter für ein bestimmtes Gut bereit ist zu zahlen, oftmals auf komplexe Weise von anderen Gütern und deren Preis abhängt. Eine Berücksichtigung dieser Synergien kann zu einer besseren Allokation und einer Erhöhung der Erlöse des Auktionators führen. Das grundlegende Problem von Kombinatorischen Auktionen mit dem sich diese Arbeit beschäftigt, ist die Allokation der Güter, also die Bestimmung der Gebote, die den Zuschlag erhalten. Im allgemeinen Fall wächst die Anzahl der möglichen Gebote exponentiell mit der Anzahl der angebotenen Güter. Die Bestimmung der optimalen Lösung ist im allgemeinen Fall NP-vollständig. In Kapitel 2 wird die Problematik detailliert beschrieben und es wird auf dieser Grundlage eine formale Darstellung erarbeitet. Kapitel 3 beschäftigt sich damit, wie mit Hilfe der Lagrange Relaxation und des Column Generation Verfahren eine Lösung des Problems erfolgen kann.
Inhaltsverzeichnis
- Einleitung
- Kombinatorische Auktionen
- Synergieeffekte
- Komplementarität / Superadditivität
- Substituierbarkeit / Subadditivität
- Grundlegende Fragen
- Formale Darstellung des CAP
- Allgemeine Formulierung des CAP
- CAP für superadditive Wertfunktionen
- Das Set-Packing Problem (SPP)
- Komplexität des SPP
- Dezentrale Lösungsverfahren
- Duales SPP
- Lagrange Relaxation
- Formale Beschreibung
- Interpretation für Auktionen
- Heuristik zur Bestimmung des Lagrange-Multiplikators
- RSB-Allokationsprozedur für airport time slots
- Column Generation
- Vorgehen zur Lösung von Kombinatorischen Auktionen
Zielsetzung und Themenschwerpunkte
Diese Arbeit befasst sich mit der Problematik von Kombinatorischen Auktionen, insbesondere der Allokation von Gütern in einem Szenario, bei dem Bieter Gebote für Kombinationen von Gütern, sog. Güterbündel, abgeben können. Dabei wird die Herausforderung der komplexen Preisbildung und Allokation von Gütern in Situationen betrachtet, wo der Preis, den ein Bieter für ein Gut zu zahlen bereit ist, von anderen Gütern und deren Preis abhängt. Die Arbeit untersucht, wie mit Hilfe der Lagrange Relaxation und des Column Generation Verfahrens eine Lösung des Problems gefunden werden kann.
- Synergieeffekte und komplexe Wertfunktionen in Kombinatorischen Auktionen
- Formale Modellierung des Kombinatorischen Auktions-Problems (CAP)
- Einsatz der Lagrange Relaxation zur Lösung des CAP
- Anwendungen der Column Generation Methode für Kombinatorische Auktionen
- Dezentrale Lösungsansätze für komplexe Allokationsprobleme
Zusammenfassung der Kapitel
Kapitel 2 beschäftigt sich mit der detaillierten Beschreibung der Problematik von Kombinatorischen Auktionen. Es werden verschiedene Arten von Synergieeffekten, wie Komplementarität und Substituierbarkeit, erläutert. Die Kapitel behandelt die Formale Darstellung des CAP, inklusive der allgemeinen Formulierung und der spezifischen Formulierung für superadditive Wertfunktionen. Es werden außerdem die grundlegenden Fragen im Kontext von Kombinatorischen Auktionen besprochen und das Set-Packing Problem (SPP) als ein wichtiges Beispiel vorgestellt. Die Komplexität des SPP wird ebenfalls diskutiert.
Kapitel 3 behandelt dezentrale Lösungsverfahren für das CAP, insbesondere die Lagrange Relaxation und die Column Generation Methode. Es werden die Anwendung der Lagrange Relaxation im Kontext von Auktionen erläutert und eine Heuristik zur Bestimmung des Lagrange-Multiplikators vorgestellt. Darüber hinaus wird die RSB-Allokationsprozedur für Flughafenzeitfenster als Beispiel für eine Anwendung der Lagrange Relaxation beschrieben. Der Abschnitt über Column Generation behandelt das Vorgehen zur Lösung von Kombinatorischen Auktionen mit dieser Methode.
Schlüsselwörter
Kombinatorische Auktionen, Lagrange Relaxation, Column Generation, CAP, SPP, Synergieeffekte, Komplementarität, Substituierbarkeit, Wertfunktion, Güterbündel, dezentrale Lösungsverfahren, Allokation, Preisbildung.
- Arbeit zitieren
- Stefan Gretschel (Autor:in), 2003, Lagrange Relaxation und Column Generation für Kombinatorische Auktionen, München, GRIN Verlag, https://www.hausarbeiten.de/document/39340
