21.08.2012

SR11
Währinger Straße 29
1090 Wien

Kurzfassung
Suchmaschinenanbieter beziehen einen Großteil ihrer Einnahmen aus der Versteigerung von Werbeplätzen. Jedes Mal, wenn eine Suchanfrage gestartet wird, wird ermittelt, welche Bieter am meisten für den Suchbegriff geboten haben und damit ihre Werbung in einem der dafür vorgesehenen Bereiche platzieren dürfen. Die bisher dafür verwendeten Algorithmen erlauben den Bietern nur wenige Möglichkeiten, ihre Präferenzen und Ziele auszudrücken. Daher wurde in letzter Zeit die existierende Theorie zu Allokationsproblemen erweitert und auf diese Problemstellung angewandt, um so neue Algorithmen zu entwickeln.
   Jeder Bieter hat einen bestimmten Nutzen, wenn ihm ein Werbeplatz zu einem vorher bestimmten Preis zugewiesen wird.
   In dieser Arbeit wird das Verhalten von Bietern modelliert, die ihre Kapitalrendite maximieren wollen. Dafür werden nicht-lineare Funktionen mit Budgets verwendet, um den Nutzen eines Bieters abzubilden. Es wird gezeigt, dass eine Variante der sogenannten ungarischen Methode für diese Funktionen ein für die Bieter optimales Ergebnis liefert, in dem kein Bieter einen anderen beneidet.
   Um ein möglichst einfaches Bieten zu ermöglichen, sollen die Bieter den für sie größtmöglichen Nutzen erhalten, wenn sie ihre wahren Werte preisgeben. Diese Eigenschaft kann der verwendete Algorithmus allerdings nicht für alle möglichen Eingabewerte erfüllen. Es wird analysiert, wann genau dies nicht der Fall ist, und ein mit Zufallsentscheidungen arbeitender Algorithmus formuliert, der mit diesen Fällen umgehen kann. Jeder Bieter erhält im vom sogenannten randomisierten Algorithmus berechneten Ergebnis zumindest den gleichen Nutzen wie im nicht randomisierten Fall. Es kann jedoch sein, dass er einen anderen Bieter beneidet. Ob und wie sehr sich unwahre Angaben für Bieter beim randomisierten Algorithmus auszahlen, konnte noch nicht beantwortet werden.