Heuristiken für das Winner Determination Problem in Kombinatorischen Auktionen

ISBN-13: 9783640920327 / Niemiecki / Miękka / 2011 / 60 str.

Alexander Rothe

Opis

Bachelorarbeit aus dem Jahr 2011 im Fachbereich Informatik - Wirtschaftsinformatik, Note: 1,3, Helmut-Schmidt-Universitat - Universitat der Bundeswehr Hamburg, Sprache: Deutsch, Abstract: In klassischen Auktionen werden Guter einzeln und unabhangig voneinander versteigert. Die Entwicklung, Guter zu einem Guterbundel zusammen zu fassen und darauf Gebote abgeben zu konnen, fuhrte zu dem Konzept der kombinatorischen Auktionen. Diese spezielle Form ermoglichte Bietern neue Varianten bei der Abbildung ihrer Praferenzen. Zu den Herausforderungen gehort das Winner Determination Problem. Als Losungsansatz 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 hangen von der Auktionsumgebung und den Auktionsregeln ab. Bevor Losungsansatze diskutiert werden konnen, sollten die Grunde und die Abhangigkeiten zwischen Auktion und Hurden geklart werden. Fur 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 erlautert. Den dritten Abschnitt, uber die Einleitung von kombinatorischen Auktionen, bilden die Bidding Languages. Mit Hilfe dieser Grundlagen kann man das Winner Determination Problem formulieren. Die Komplexitat ist eine der bestimmenden Faktoren in diesem Problem. Dazu wird zunachst die Komplexitat in einer kombinatorischen Auktion dargestellt, um anschlieend die Fragen erortern zu konnen, die dadurch aufgeworfen werden. Durch die Komplexitat bedingt gibt es keine schnelle Losung, die sich auf alle kombinatorischen Probleme mit der Garantie eines optimalen Ergebnisses anwenden lasst. Eine Alternative sind die in dieser Arbeit vorgestellten Heuristiken. Sie zeichnet ein im Verhaltnis relativ geringer Rechenau