Winner Determination in Combinatorial Auctions

Eine kombinatorische Auktion zeichnet sich dadurch aus, dassmehrere Objekte simultan versteigert werden und die Bieter Geboteauf Teilmengen von Objekten abgeben k onnen. Gibt es keinerleiBeschr ankungen bei der Gebotsabgabe, so gestaltet sich dieoptimale Zuordnung von Objekten zu Bietern (Gewinnerbestimmung) imAllgemeinen als NP--schwer. Dieses Buch besch aftigt sich vorrangig mit derGewinnerbestimmung; es werden Optimierungs -modelle zuspezifischen kombinatorischen Auktionen aufgestellt und f urausgew ahlte Modelle Algorithmen entwickelt und getestet. Im Zentrum der Arbeit wird untersucht, wie eine fiktiveUnternehmensleitung (Auktionator) mit Hilfe einer kombinatorischenAuktion Zeitfenster (Objekte) einer kapazit atsbeschr anktenProduktionsanlage auf Profit--Center (Bieter) verteilen kann. AlsOptimierungsmodell wird das Weighted Job Interval SchedulingProblem identifiziert; die daf ur entwickelte Lagrangeheuristikliefert in Rechenstudien im Mittel bessere untere Schrankenals eine aus der Literatur ausgew ahlte Heuristik. In einer Verallgemeinerung werden knappe Budgets von Seiten derProfit--Center angenommen. In Rechenstudien zeigt sich, dass eineentwickelte Lagrange--Dekompostion bessere obere Schranken als diedurch CPLEX berechnete LP--L osung liefert und die Heuristik imMittel gute untere Schranken findet. Des weiteren wird die Anwendung von kombinatorischen Auktionen inder Praxis analysiert; in einem Fall wird gezeigt, dass knappeRessourcen in einem grossen deutschen Versicherungsunternehmeneffizienter mit einer kombinatorischen Auktion als mit einem vondem Unternehmen vorgeschlagenen Verfahren verteilt werdenk onnen. Des weiteren wird ein Pilotprojekt von DaimlerChryslervorgestellt; hier wurde eine kombinatorische Ausschreibung zurBeschaffung von Transportkapazit at erfolgreich angewendet. [.5cm]In a combinatorial auction many items are put up for auctionsimultaneously and the bidders are allowed to place bids onsubsets of items. If no restrictions on placing bids do exist, theassignment of items to bidders (winner determination)is proven to be NP-hard in the general case. This book focuses on deriving mathematical models and algorithmsfor the winner determination problem. Mainly, we show how scarcetime slots (items) on a machine which is made available by theheadquarters (auctioneer) can be assigned to profit--centers(bidders) using a combinatorial auction. The Weighted Job IntervalScheduling Problem serves as winner determination problem; runtimestudies show that a Lagrangean heuristic outperforms a heuristictaken from the literature. Furthermore, we analyze the situation where the profit--centersare assumed to be budget--restricted. To solve the winnerdetermination problem a Lagrangean decomposition is used; runtimestudies show that our upper bounds outperform the LP--solutioncalculated by CPLEX and the proposed lower bounds seem to be tight. Afterwards, the application of combinatorial auctions in practiceis studied. We state an allocation problem at a large Germaninsurance company; it is shown, that combinatorial auctions canderive more efficient allocations than an algorithm proposed bythe company. Finally, we provide the experiences of the first useof a combinatorial reverse auction at DaimlerChrysler wheretransportation capacity was successfully procured.