DFG-Projekt A3G: Algorithmen zur Lösung von mathematischen Gleichgewichtsproblemen

Ein Team unter der Leitung des Mathematikers Prof. Dr. Tobias Harks von der Universität Passau erforscht in einem gemeinsamen DFG-Projekt mit Prof. Dr. Martin Schmidt von der Universität Trier das theoretische und algorithmische Verständnis von Gleichgewichtsproblemen, wie sie etwa in den Bereichen Verkehr und Elektrizität auftreten.

Das Nash-Gleichgewicht beschreibt in der Spieltheorie eine Situation, in der kein Akteur seinen Nutzen durch eine unilateral geänderte Strategie erhöhen kann. Das Konzept kann auf viele Alltagsbereiche angewandt werden, zum Beispiel auf Situationen im Verkehr. Hier hängt der Nutzen der Akteure (negative Fahrtzeit) von den Routing-Entscheidung der anderen Verkehrsteilnehmenden ab.

Ein Team der Universität Passau um Prof. Dr. Tobias Harks, Inhaber des Lehrstuhls für Mathematische Optimierung, erforscht in einem gemeinsamen DFG-Projekt mit der Universität Trier sogenannte aggregative Spiele mit Ganzzahligkeitsbedingungen, welche  sich dadurch auszeichnen, dass die Nutzenfunktion eines Spielers, in dem Fall des Autofahrers, von der eigenen Strategie und einem Aggregat der Strategien der anderen Spieler abhängt und die einzelnen Strategieräume diskret sein können. Ziel des DFG-Projekts mit dem Titel „Aggregative gemischt-ganzzahlige Gleichgewichtsprobleme: Existenz, Approximation und Algorithmus“, kurz A3G, ist es, ein theoretisches und algorithmisches Verständnis von solchen Gleichgewichtsproblemen zu entwickeln. Anwendung findet das Projekt neben dem Verkehrsbereich auch in der Elektrizität beziehungsweise bei Transport- und Kommunikationsnetzwerken.

„Wir untersuchen komplexe Gleichgewichtsprobleme, bei denen Strategieräume diskrete Aspekte aufweisen“, erklärt Prof. Dr. Harks. „Wir suchen hier nach mathematischen Strukturen, um die Existenz von Gleichgewichten zu verstehen und anschließend Algorithmen zu entwickeln, mit deren Hilfe wir Gleichgewichte berechnen können.“

Als ein Anwendungsfall beschäftigt sich das Projekt beispielsweise mit Routing und Transportprotokollen in Kommunikationsnetzwerken, bei denen Datenpakete durch ein Netz gesendet werden. Jeder Einzelanwender möchte dabei eine möglichst hohe Bandbreite erzielen, um eine möglichst gute Verbindung zu gewährleisten. Diese gute Verbindung wollen alle Nutzenden des Kommunikationsnetzwerks gleichermaßen, es gibt aber nur eine gewisse Gesamtbandbreite. Hier stellt sich das Projekt etwa die Frage, wie solche Gleichgewichte zu beschreiben sind und wie sie charakterisiert und berechnet werden können.

Das Forschungsteam geht diese Problemstellung mithilfe verschiedener mathematischer Theorien an. Unter anderem kommen die Theorien der diskreten Konvexität sowie algorithmische Optimierungsmethoden zum Einsatz.

Neben Prof. Dr. Harks forscht an der Universität Passau noch dessen wissenschaftlicher Mitarbeiter Julian Schwarz zu dem Thema. Von extern beteiligt ist Prof. Dr. Martin Schmidt, Professor für Nichtlineare Optimierung an der Universität Trier. Das Vorhaben startet im September 2024. Die Deutsche Forschungsgemeinschaft (DFG) fördert es über eine Laufzeit von drei Jahren.