Winner Determination in Combinatorial Auctions. Dieser Artikel ist nicht verfügbar.Winner Determination in Combinatorial Auctions

Eine kombinatorische Auktion zeichnet sich dadurch aus, dass
mehrere Objekte simultan versteigert werden und die Bieter Gebote
auf Teilmengen von Objekten abgeben k önnen. Gibt es keinerlei
Beschr änkungen bei der Gebotsabgabe, so gestaltet sich die
optimale Zuordnung von Objekten zu Bietern (Gewinnerbestimmung) im
Allgemeinen als NP--schwer.
Dieses Buch besch äftigt sich vorrangig mit der
Gewinnerbestimmung; es werden Optimierungs -modelle zu
spezifischen kombinatorischen Auktionen aufgestellt und f ür
ausgew ählte Modelle Algorithmen entwickelt und getestet.
Im Zentrum der Arbeit wird untersucht, wie eine fiktive
Unternehmensleitung (Auktionator) mit Hilfe einer kombinatorischen
Auktion Zeitfenster (Objekte) einer kapazit ätsbeschr änkten
Produktionsanlage auf Profit--Center (Bieter) verteilen kann. Als
Optimierungsmodell wird das Weighted Job Interval Scheduling
Problem identifiziert; die daf ür entwickelte Lagrangeheuristik
liefert in Rechenstudien im Mittel bessere untere Schranken
als eine aus der Literatur ausgew ählte Heuristik.
In einer Verallgemeinerung werden knappe Budgets von Seiten der
Profit--Center angenommen. In Rechenstudien zeigt sich, dass eine
entwickelte Lagrange--Dekompostion bessere obere Schranken als die
durch CPLEX berechnete LP--L ösung liefert und die Heuristik im
Mittel gute untere Schranken findet.
Des weiteren wird die Anwendung von kombinatorischen Auktionen in
der Praxis analysiert; in einem Fall wird gezeigt, dass knappe
Ressourcen in einem gro{ ss}en deutschen Versicherungsunternehmen
effizienter mit einer kombinatorischen Auktion als mit einem von
dem Unternehmen vorgeschlagenen Verfahren verteilt werden
k önnen. Des weiteren wird ein Pilotprojekt von DaimlerChrysler
vorgestellt; hier wurde eine kombinatorische Ausschreibung zur
Beschaffung von Transportkapazit ät erfolgreich angewendet. [.5cm]

In a combinatorial auction many items are put up for auction
simultaneously and the bidders are allowed to place bids on
subsets of items. If no restrictions on placing bids do exist, the
assignment of items to bidders (winner determination)
is proven to be NP-hard in the general case.
This book focuses on deriving mathematical models and algorithms
for the winner determination problem. Mainly, we show how scarce
time slots (items) on a machine which is made available by the
headquarters (auctioneer) can be assigned to profit--centers
(bidders) using a combinatorial auction. The Weighted Job Interval
Scheduling Problem serves as winner determination problem; runtime
studies show that a Lagrangean heuristic outperforms a heuristic
taken from the literature.
Furthermore, we analyze the situation where the profit--centers
are assumed to be budget--restricted. To solve the winner
determination problem a Lagrangean decomposition is used; runtime
studies show that our upper bounds outperform the LP--solution
calculated by CPLEX and the proposed lower bounds seem to be tight.
Afterwards, the application of combinatorial auctions in practice
is studied. We state an allocation problem at a large German
insurance company; it is shown, that combinatorial auctions can
derive more efficient allocations than an algorithm proposed by
the company. Finally, we provide the experiences of the first use
of a combinatorial reverse auction at DaimlerChrysler where
transportation capacity was successfully procured.