Verteilte Systeme wie das Internet sind mit klassischen Methoden der Informatik aus verschiedenen Gründen nur schwer zu organisieren. Aufgrund der Größe und Dynamik dieser Systeme muss beim Entwurf von Protokollen und algorithmischen Verfahren großer Wert auf Skalierbarkeit, verteilte Ausführbarkeit und Adaptivität gelegt werden. Dort, wo autonome Teilsysteme im Wettbewerb um vorhandene Ressourcen stehen, müssen darüber hinaus nach spieltheoretischen Prinzipien entwickelte Mechanismen den beteiligten Akteuren Anreize zur Kooperation liefern.
Facility-Location in dynamischen Netzwerken
Das Facility-Location-Problem stellt eine bedeutende Fragstellung in der theoretischen Informatik dar. Es wird oft als Benchmarkproblem für die Entwicklung von sowohl sequentiellen, als auch verteilt ausgeführten Approximationsalgorithmen für diverse Problemstellungen verwendet. Ein Grund dafür stellt die Lokalität dar, welche dem Facility-Location-Problem inhärent ist. Die Fragestellung bei Facility-Location besteht darin eine kosteneffiziente Verteilung von Diensten oder Ressourcen auf Rechenknoten eines Netzwerks festzulegen. Bei dieser Ressourcenverteilung möchte man einerseits möglichst wenige Rechenknoten nutzen (da dieses mit sehr hohen Kosten verbunden ist), andererseits möchte man aber auch garantieren, dass sich alle Kunden möglichst in der „Nähe“ von den Ressourcen oder Diensten bereitstellenden Rechenknoten befinden. Dabei wird Nähe durch die Qualität der Latenzen, welche auf den Verbindungen zwischen Kunden und Rechenknoten bestehen, definiert.
Besondere Schwierigkeiten bei der von uns untersuchten Variante von Facility-Location bestehen in der riesigen Größe der betrachteten Netzwerke und der fortwährenden Dynamik, der diese Netzwerke unterworfen sind. Durch die ständigen Veränderungen der Netzwerke ist es notwendig Algorithmen zu nutzen, welche ihre Lösung fortwährend an die derzeitige Situation anpassen, um zu jedem Zeitpunkt eine Lösung ausreichender Qualität bereitstellen zu können. Dies ist nur durch den Einsatz von verteilten, insbesondere lokalen Algorithmen möglich, welche nur Informationen aus ihrer unmittelbaren Umgebung für ihre Entscheidungsfindung nutzen und dadurch mit beliebig skalierenden Netzwerken umgehen können. Außerdem ermöglicht diese lokale Herangehensweise auch einen direkten und schnellen Umgang mit der in den Netzwerken auftretenden Dynamik: Knoten können selbst deutlich schneller Entscheidungen treffen und neue Lösung berechnen, als das eine das Netzwerk zentral steuernde Instanz machen könnte.
Ein probabilistisches Konsumentenmodell für Internet-Werbung
Platzierung von Werbeanzeigen
Ein zentrales Problem bei der Bewerbung von Angeboten im Internet ist die Auswahl der Webseiten, die mit hoher Wahrscheinlichkeit von potentiellen Kunden besucht werden. Wir nehmen an, dass mit jeder betrachteten Werbefläche der Kaufreiz des Kundens wächst. Es gilt also die Platzierung dahingehend zu optimeren, dass der erwartete Verkaufserlös maximiert wird, die Werbekosten aber gering ausfallen.
Dieses Problem lässt sich auf zweierlei Arten betrachten. Geht man von nur einem Anbieter aus, gilt es zu bewerten, wie gut eine Auswahl von Webseiten tatsächlich ist. Dabei interessieren wir uns dafür, wie lange es erwartungsgemäß dauert, bis der Kunde eine bestimmte Anzahl von ihnen besucht haben wird. Erweiternd stellen wir aber auch die Frage, wie sich eine möglichst gute Lösung auf algorithmischem Wege bestimmen lässt.
Betrachtet man den tatsächlichen Internetmarkt, in dem zahlreiche Anbieter ähnliche Produkte anbieten, so erhält unsere Fragestellung einen spieltheoretischen Aspekt. Mehrere Anbieter werben um gleiche Kunden und beeinflussen sich gegenseitig. So verfolgen sie etwa Strategien wie eigene Werbeanzeigen nicht neben einem Konkurenzprodukt zu platzieren oder nur in bestimmten Teilen des Internets aufzutreten. Wir analysieren solche Spielstrategien mit dem Ziel, optimale Verhaltensregeln für Systeme mit mehreren egoistischen Akteuren zu finden. Diese Stategien finden insbesondere Anwendung in großen dynamischen Märkten, wie sie beispielsweise im Sonderforschungsbereich On-The-Fly Computing erforscht werden.
Kontakt:
Dipl.-Inform. Peter Pietrzyk
E-Mail: Peter.Pietrzyk@hni.upb.de
Telefon: +49 (0) 5251/60 64 69
Dipl.-Math. Andreas Cord-Landwehr
E-Mail: Andreas.Cord-Landwehr@hni.upb.de
Telefon: +49 (0) 5251/60 64 27
Jun.-Prof. Dr. rer.nat. Patrick Briest
E-Mail: Patrick.Briest@hni.upb.de
Telefon: +49 (0) 5251/60 64 57
Maximilian Drees, M.Sc.
E-Mail: Maximilian.Drees@hni.upb.de
Telefon: +49 (0) 5251/60 64 34
