Heuristiken fur das Winner Determination Problem in Kombinatorischen Auktionen

Bachelorarbeit aus dem Jahr 2011 im Fachbereich Informatik - Wirtschaftsinformatik, Note: 1,3, Helmut-Schmidt-Universitt - Universitt der Bundeswehr Hamburg, Sprache: Deutsch, Abstract: In klassischen Auktionen werden Gter einzeln und unabhngig voneinander versteigert. Die Entwicklung, Gter zu einem Gterbndel zusammen zu fassen und darauf Gebote abgeben zu knnen, fhrte zu dem Konzept der kombinatorischen Auktionen. Diese spezielle Form ermglichte Bietern neue Varianten bei der Abbildung ihrer Prferenzen. Zu den Herausforderungen gehrt das Winner Determination Problem. Als Lsungsansatz 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 hngen von der Auktionsumgebung und den Auktionsregeln ab. Bevor Lsungsanstze diskutiert werden knnen, sollten die Grnde und die Abhngigkeiten zwischen Auktion und Hrden geklrt werden. Fr die theoretische Grundlage wird in dem ersten Teil dieser Arbeit ein Einblick in die Auktionstheorien mit ihren Entwicklungen und Erkenntnissen gegeben. Anschlieend werden die verschiedenen Auktionsformen erlutert. 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 Komplexitt ist eine der bestimmenden Faktoren in diesem Problem. Dazu wird zunchst die Komplexitt in einer kombinatorischen Auktion dargestellt, um anschlieend die Fragen errtern zu knnen, die dadurch aufgeworfen werden. Durch die Komplexitt bedingt gibt es keine schnelle Lsung, die sich auf alle kombinatorischen Probleme mit der Garantie eines optimalen Ergebnisses anwenden lsst. Eine Alternative sind die in dieser Arbeit vorgestellten Heuristiken. Sie zeichnet ein im Verhltnis relativ geringer Rechenau