Prof. Dr. Max Klimm

Prof. Klimm erforscht Algorithmen auf großen Netzwerken und deren Verhalten unter Wettbewerb und Kooperation, kombiniert dabei Graphentheorie mit algorithmischer Spieltheorie. Ein aktueller Schwerpunkt liegt auf der Optimierung von Verkehrsflüssen unter unsicherer Nachfrage — ein Problem, das für Logistik, städtische Mobilität und Infrastrukturplanung relevant ist. Die Arbeiten liefern theoretische Grundlagen und algorithmische Methoden, um dezentrale Systeme effizienter zu gestalten, in denen mehrere Akteure oder Algorithmen gleichzeitig agieren.

🔒 Das System hat 276 mögliche Industrie-Partner gefunden — Firmen, Scores und Begründungen sind nur für eingeloggte Nutzer:innen sichtbar. Anmelden

• Netzwerk und Mechanism Design für Infrastrukturnetzwerke in Metropolregionen

  Quelle ↗

• SPP 1736: Kompetitive Exploration großer Netze (Klimm)

  Quelle ↗

  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.

• Impartial Selection and the Power of Up to Two Choices

  2017

  ACM Transactions on Economics and Computation · DOI

  We study mechanisms that select members of a set of agents based on nominations by other members and that are impartial in the sense that agents cannot influence their own chance of selection. Prior work has shown that deterministic mechanisms for selecting any fixed number k of agents are severely limited and cannot extract a constant fraction of the nominations of the k most highly nominated agents. We prove here that this impossibility result can be circumvented by allowing the mechanism to sometimes but not always select fewer than k agents. This added flexibility also improves the performance of randomized mechanisms, for which we show a separation between mechanisms that make exactly two or up to two choices and give upper and lower bounds for mechanisms allowed more than two choices.

• Sensitivity Analysis for Convex Separable Optimization Over Integral Polymatroids

  2018

  SIAM Journal on Optimization · DOI

  We study the sensitivity of optimal solutions of convex separable optimization problems over an integral polymatroid base polytope with respect to parameters determining both the cost of each element and the polytope. Under convexity and a regularity assumption on the functional dependency of the cost function with respect to the parameters, we show that reoptimization after a change in parameters can be done by elementary local operations. Applying this result, we derive that starting from any optimal solution, there is a new optimal solution to new parameters such that the $L_1$-norm of the difference of the two solutions is at most two times the $L_1$-norm of the difference of the parameters. We apply these sensitivity results to a class of noncooperative games with a finite set of players where a strategy of a player is to choose a vector in a player-specific integral polymatroid base polytope defined on a common set of elements. The players' private cost functions are regular, convex-separable, and the cost of each element is a nondecreasing function of the own usage of that element and the overall usage of the other players. Under these assumptions, we establish the existence of a pure Nash equilibrium. The existence is proven by an algorithm computing a pure Nash equilibrium that runs in polynomial time whenever the rank of the polymatroid base polytope is polynomially bounded. Both the existence result and the algorithm generalize and unify previous results appearing in the literature. We finally complement our results by showing that polymatroids are the maximal combinatorial structure enabling these results. For any nonpolymatroid region, there is a corresponding optimization problem for which the sensitivity results do not hold. In addition, there is a game where the players' strategies are isomorphic to the nonpolymatroid region and that does not admit a pure Nash equilibrium.