Heuristiken für das Winner Determination Problem in Kombinatorischen Auktionen

Bachelorarbeit aus dem Jahr 2011 im Fachbereich Informatik - Wirtschaftsinformatik Note: 13 Helmut-Schmidt-Universität - Universität der Bundeswehr Hamburg Sprache: Deutsch Abstract: 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 Rechenau