Kompetitive Exploration großer Netze

• Antragsteller: Professor Dr. Max Klimm, seit 4/2017
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2014 bis 2018
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 254845774

Ziel dieses Projektes ist die Vertiefung des Verständnisses von Algorithmen, die auf großen Netzwerken operieren, sowie die Untersuchung von Dynamiken, die durch den Wettbewerb und die Kooperation solcher Algorithmen entstehen. Dazu wollen wir Modelle und Techniken aus den Bereichen Graphenexploration und algorithmische Spieltheorie kombinieren, um neue Einsichten zu den algorithmischen und wirtschaftlichen Herausforderungen vor die uns große Datennetze (wie zum Beispiel soziale Netzwerke oder das Internet) stellen zu gewinnen.Zunächst wollen wir Agentenmodelle entwickeln, mit denen sich die Erkundung des Internets durch Softwareagenten modelieren lässt. Dabei erlauben wir den Agenten eine kleine Anzahl besuchter Knoten zu speichern, zu sie jederzeit zurück springen können. Wir wollen der Frage nachgehen, ob ein solches Modell eine effizientere Graphenexploration als bisherige Modelle erlaubt. Außerdem wollen wir untersuchen, wie auf jeder Instanz eine gute Balance zwischen der Anzahl besuchter Knoten einerseits und der Explorationszeit und dem benötigtem Speicher andererseits gefunden werden kann.Beim Einsatz mehrerer Agenten stellen Kooperation und Koordination zwischen den Agenten eine weitere Herausforderung dar. Auch hier wollen wir analysieren, wie die Fähigkeit der Agenten zu gespeicherten Knoten zurück zu springen sich auf die Mächtigkeit der Agenten auswirkt. Augrund der Größe der betrachteten Netzwerke soll vor allem die Exploration mit kleinen Teams von Agenten mit wenig Speicher untersucht werden.Als einen zentralen Beitrag dieses Projekts wollen wir die kompetitive Exploration großer Netze betrachten. Im Gegensatz zur kooperativen Exploration versuchen die Agenten hierbei jeweils ihren eigenen Nutzen zu maximieren, statt ein gemeinsames Ziel zu verfolgen. Der Wettbewerb zwischen konkurrierenden Agenten wird für gewöhnlich im Rahmen nicht-kooperativer Spiele untersucht. In der Spieltheorie geht man jedoch üblicherweise davon aus, dass die Agenten sich aller ihrer strategischen Möglichkeiten bewusst sind. Diese Annahme ist in großen Netzen unrealistisch, da das Verhalten der Agenten inhärent lokal sein muss. Diesen Gegensatz wollen wir überwinden, indem wir Methoden aus Graphenexploration und Spieltheorie kombinieren. Wir erhoffen uns dadurch eine Charakterisierung der Umstände unter denen das Verhalten der Agenten zu einem stabilen Zustand konvergiert. Außerdem wollen wir die Effizienz der erreichten Gleichgewichte und die Konvergenzgeschwindigkeit untersuchen. We planen weiterhin unsere Betrachtung auf Situationen auszudehnen, bei denen die Agenten ihren durchschnittlichen Nutzen über die Zeit maximieren wollen.Im Weiterem wollen wir die Einsichten, die wir zur kooperativen und kompetitiven Exploration gewonnen haben, kombinieren um den Wettbewerb konkurrierender Teams von Agenten zu verstehen.

• DFG-Verfahren: Schwerpunktprogramme
• Teilprojekt zu: SPP 1736: Algorithmen für große Datenmengen
• Ehemaliger Antragsteller: Professor Dr. Yann Disser, bis 3/2017