Lagrange Relaxation und Column Generation für Kombinatorische Auktionen

Inhaltsverzeichnis

Abkürzungsverzeichnis

1 Einleitung

2 Kombinatorische Auktionen
2.1 Synergieeffekte
2.1.1 Komplementarität / Superadditivität
2.1.2 Substituierbarkeit / Subadditivität
2.2 Grundlegende Fragen
2.3 Formale Darstellung des CAP
2.3.1 Allgemeine Formulierung des CAP
2.3.2 CAP für superadditive Wertfunktionen
2.4 Das Set-Packing Problem (SPP)
2.5 Komplexität des SPP

3 Dezentrale Lösungsverfahren
3.1 Duales SPP
3.2 Lagrange Relaxation
3.2.1 Formale Beschreibung
3.2.2 Interpretation für Auktionen
3.2.3 Heuristik zur Bestimmung des Lagrange-Multiplikators
3.3 RSB-Allokationsprozedur für airport time slots
3.4 Column Generation
3.4.1 Vorgehen zur Lösung von Kombinatorischen Auktionen

Literaturverzeichnis

Abkürzungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

1 Einleitung

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.

2 Kombinatorische Auktionen

In Kombinatorischen Auktionen ist es den Bietern erlaubt sowohl auf einzelne Güter, als auch auf Güterbündel zu bieten. Dies ist dann sinnvoll, wenn sich Synergien für den Bieter ergeben. In diesem Fall ist die Wertfunktion für ein Güterbündel nicht additiv, d.h. sie ergibt sich nicht als Summe der Werte der einzelnen Güter. Beispiele hierfür sind u.a. Bandbreiten-Auktionen (FCC-spectrum auctions), Start- und Landezeiten auf Flughäfen oder zusammenhängende Grundstücke.

2.1 Synergieeffekte

2.1.1 Komplementarität / Superadditivität

Der Wert eines Güterbündels ist im Falle von Komplementarität mindestens so hoch, wie die in dem Güterbündel enthalten Güter bzw. Güterbündel. Sei Vi die Wertfunktion von Bieter i. A und B seien zwei beliebige disjunkte Teilmengen der angebotenen Gütermenge M. Gilt für alle A, B Ì M:

Vi(A) + Vi(B) £ Vi(AÈB),

so ist die Wertfunktion von Bieter i komplementär bzw. superadditiv. Im Extremfall können Güter nur zusammen einen Wert haben und die Teilmengen alleine wertlos sein. Die Güter ergänzen sich dann gegenseitig.

2.1.2 Substituierbarkeit / Subadditivität

Es ist allerdings auch möglich, dass Güterbündel einen geringeren Wert haben, als die Summe der darin enthaltenen Güter bzw. Güterbündel. Dies kann z.B. der Fall sein wenn die Güter für den Bieter einen ähnlichen Zweck erfüllen, sich also gegenseitig (teilweise) überflüssig machen. Formal gilt also: Vi(A) + Vi(B) ³ Vi(AÈB).

2.2 Grundlegende Fragen

Beschäftigt man sich mit Kombinatorischen Auktionen und deren Design, so sind vier grundlegende Fragestellungen^[1] zu beachten:

- Gebotsabgabe: Jedem Bieter muss es möglich sein, Gebote auf Güterbündel abgeben zu können. In einem Protokoll muss festgelegt werden wie die Kommunikation zwischen dem Bieter und dem Auktionator ablaufen soll. Bei der Wahl der Gebotssprache ist die richtige Balance zwischen Ausdrucksstärke und Einfachheit zu bestimmen.
- Allokation: Sind alle Gebote abgegeben, müssen die Gebote bestimmt werden, die den Zuschlag erhalten. Dies entspricht einer Optimierung der Zielfunktion, z.B. die Erlösmaximierung des Auktionators.
- Zahlung: Wie hoch ist der Betrag, den der Gewinner für die Güterbündel zahlen muss. Er muss nicht der Höhe des Gebotes entsprechen. Die Zahlungsbedingungen beeinflussen die Strategie des Bieters und somit auch die Einkünfte des Auktionators.
- Strategie: Jeder Bieter kann, abhängig von den festgelegten Regeln, eine Strategie wählen mit der er seine Ziele verfolgt. Eine gut konstruierte Auktion schafft es trotz der eigenen Interessen der Bieter, die Ziele des Auktionators zu optimieren.

Diese Arbeit beschäftigt sich im wesentlichen mit der Problemstellung der Allokation. Es wird angenommen, dass die Gebotsabgabe vollzogen ist. Die Gebote repräsentieren die Wertfunktionen der Bieter und die Zahlung entspricht der Höhe des Gebots. Zudem wird unterstellt, dass die Bieter nicht strategisch handeln und ihre Interessen preisgeben. Für eine spieltheoretische Betrachtung sei auf den VCG-Mechanismus^[2] von Vickrey, Clarke und Groves verwiesen, dessen Ziel es ist eine Auktion anreizkompatibel zu gestalten.

2.3 Formale Darstellung des CAP

Die Bestimmung der Gebote, die den Zuschlag erhalten, ist in der englischsprachigen Literatur als "winner determination problem" bekannt. Die genaue formale Darstellung hängt von den Zielen des Auktionators ab. Hier wird in Anlehnung an de Vries^[3] angenommen der Auktionator ist der Verkäufer, dessen Ziel es ist seinen Erlös zu maximieren. Die Bieter sind die Käufer, deren Gebote ihre wirkliche Wertvorstellung repräsentieren.

2.3.1 Allgemeine Formulierung des CAP

Dieses Problem wird im folgenden CAP (combinatorial auction problem) genannt. Das CAP kann als Integer Problem / Programm (IP) formuliert werden.

Sei N die Menge der Bieter und M die Menge (unterschiedlicher) Güter. Ein Gebot S bezieht sich auf eine Teilmenge (Gut bzw. Güterbündel) von M, SÍM. bj(S) ist die Höhe des Gebots S (bid), des Bieters jÎN. Ein Gebot mit bj(S) < 0 wird niemals gewählt, so dass ohne Einschränkung der Allgemeinheit gilt bj(S) ³ 0. Die Entscheidungsvariable y(S, j) ist gelich 1, wenn das Gebot S des Bieters j den Zuschlag erhält, und ansonsten 0.

Abbildung in dieser Leseprobe nicht enthalten

Die erste Nebenbedingung garantiert die Disjunktheit der Gebote bezüglich der Güter, d.h. dass ein bestimmtes Gut in höchstens einem Gebot vorhanden ist, welches den Zuschlag erhält. Die zweite garantiert, dass pro Bieter höchstens ein Gebot berücksichtigt wird.

2.3.2 CAP für superadditive Wertfunktionen

Sind die Wertfunktionen aller Bieter superadditiv (komplementär), d.h. der Wert eines Güterbündels ist mindestens so hoch wie die Summe der enthaltenen Güter(bündel), dann lässt sich das CAP wie folgt reduzieren. Sei b(S) = maxjÎN bj(S) das höchste Gebot eines Bieters auf das Güterbündel S, und xS = 1 falls b(S) den Zuschlag erhält und 0 ansonsten.

Abbildung in dieser Leseprobe nicht enthalten

2.4 Das Set-Packing Problem (SPP)

Das SPP ist ein wohlbekanntes und gut untersuchtes IP. Gegeben sind eine Menge M von Elementen und eine Menge V mit Teilmengen von M, welche mit nichtnegativen Gewichten bewertet sind. Gesucht ist eine paarweise disjunkte Menge von Teilmengen, die das höchste Gewicht hat. Die Entscheidungsvariable xj ist gleich 1 falls die j-te Teilmenge aus V mit dem Gewicht cj gewählt wird und ansonsten 0. Sei aij =1 falls die j-te Teilmenge aus V das Element iÎM enthält und 0 ansonsten. Nun lässt sich das SPP wie folgt formalisieren:

Abbildung in dieser Leseprobe nicht enthalten

Wie von Rothkopf^[4] und Sandholm^[5] gezeigt wurde, ist das CAP eine Instanz des SPP. M entspricht der Menge der Güter und V der Menge der möglichen Gebote, also der Menge aller möglichen Teilmengen von M (Potenzmenge von M).

2.5 Komplexität des SPP

Mit einer vollständigen Enumeration aller möglichen 0-1-Kombinationen kann in endlicher Zeit eine optimale Lösung gefunden werden. Allerdings ergeben sich für |V| Variablen 2|V| potentielle Lösungen, was nur für kleinste Instanzen berechenbar ist. Für die Instanzen des SPP die im CAP entstehen entspricht die Kardinalität von V der Anzahl der Gebote, was allerdings eine große Zahl sein kann.

Es ist kein polynomialer Algorithmus für das SPP bekannt und solange nicht NP = P gilt, auch nicht existent, da das Problem NP-vollständig ist.

Für das CAP ergibt sich zudem die Schwierigkeit, dass ein polynomialer Algorithmus bezüglich der Gebote (des Input) immer noch exponentiell bezüglich der Menge der Güter ist.

Für eine effektive Lösung des CAP bedarf es daher zweier Dinge. Erstens darf die Anzahl der unterschiedlichen Gebote ist nicht zu groß sein und sollte in computerberechenbarer Form strukturiert sein. Zum zweiten sollte das zugrunde liegende SPP in einer angemessenen Zeit berechenbar sein.

[...]

^[1] vgl. [8] Nisan 2000

^[2] siehe z.B. [13] Vickrey 1961

^[3] vgl. [4] de Vries 2003

^[4] vgl. [11]Rothkopf 1998

^[5] vgl. [12] Sandholm 1999