In diesem Tandem-Projekt werden grundlegende Fragestellungen bezüglich der Existenz und Berechenbarkeit von Nashgleichgewichten in sogenannten aggregativen Spielen mit nichtkonvexen Strategieräumen untersucht, wobei die Nichtkonvexität häufig durch Ganzzahligkeitsbedingungen der Strategien auftritt. Aggregative Spiele zeichnen sich dadurch aus, dass die Nutzenfunktion eines Spielers nur von der eigenen Strategie und einem Aggregat der Strategien der anderen Spieler abhängt. Diese allgemeine Spielklasse modelliert charakteristische Eigenschaften, wie sie z.B. in der Modellierung von Energie- oder Verkehrsnetzwerken auftreten. Das Ziel des Projekts ist es, die Existenz- und Strukturtheorie von Gleichgewichten für diese Klasse von Spielen voranzutreiben. Als Hauptergebnis sollen Algorithmen zur Gleichgewichtsberechnung wie auch für eine weitergehende Bilevel-Optimierung entwickelt werden. Diese werden im Kontext der genannten Anwendungsbereiche auf realistischen Dateninstanzen empirisch getestet.

Dieses Projekt wird in Zusammenarbeit mit Prof. Dr, Martin Schmidt (Universität Trier) durchgeführt.

Um die Pariser Klimaziele einzuhalten, müssen die Treibhausgasemissionen im Verkehrssektor deutlich gesenkt werden. Neben neuen, emissionsärmeren Antriebsarten ist dabei die Verkehrswende - weg vom motorisierten Individualverkehr hin zum kollektiven öffentlichen Verkehr - unumgänglich. Das Ziel von SynphOnie ist es, eine Planungsmethode für die integrierte multikriterielle Optimierung von multimodalen Verkehrssystemen inklusive des öffentlichen Verkehrs, Ridepooling-Diensten und des Individualverkehrs zu entwickeln. Dabei werden erstmals

• verschiedene Verkehrsmodi als Gesamtsystem optimiert,
• in einem multikriteriellen Ansatz Reisezeit, Energiebedarf, Umweltbelastung und Kosten gleichzeitig betrachtet und
• das Passagierverhalten mittels Gleichgewichtsbedingungen über alle Verkehrsmodi modelliert.

Diese multikriterielle, multimodale Betrachtungsweise ermöglicht es, die Mobilität in Stadt und Land realistisch abzubilden und eine Reihe von Lösungen zu entwerfen, die verschiedenen Abwägungen zwischen Reisezeit, Energiebedarf, Umweltbelastung und Kosten darstellen.
Um solche Lösungen zu finden, wird ein zweistufiges Verfahren betrachtet. Aufbauend auf einem physikalisch-statistisch motivierten Grobmodell wird in einem zweiten Schritt in
einem Feinmodell mithilfe von diskreter Optimierung ein Verkehrsangebot aus Haltestellen, Linien, Fahrplan und Ridepoolingangebot entworfen. Mit spieltheoretischen Methoden werden dabei sowohl im Grobmodell als auch im Feinmodell
Gleichgewichte der Nachfrage zwischen den betrachteten Verkehrsmodi bestimmt. So können Effekte wie Staus und Ridepool-Kapazitäten in die Modellierung einbezogen werden.

Gemeinsames Konsortialprojekt mit Anita Schöbel (TU Kaiserslautern, Sprecherin), Philine Schiewe (TU Kaiserslautern), Karl-Heinz Küfer (ITWM Frauhofer), Markus Friedrich (U Stuttgart).

Foundational questions for dynamic flows in the context of equilibrium conditions are investigated. Several behavioral modes are considered including instantaneous dynamic equilibrium concept and classical dynamic equilibrium. Key questions range from convergence issues regarding possible discretization approaches to efficiency considerations of equilibria. We also address bilevel optimization approaches modeling mechanism design problems for dynamic equilibrium flows.

Strategic acts of sabotage and terrorism pose an increasing threat to important infrastructures and their users. This proposal aims at the design of models and algorithms for multi-level congestion and security games that allow for planning infrastructures that are robust against such attacks. In these models, we take the role of a planner, who in the first level designs the infrastructure, which is represented by a network (e.g., a public transit system or emergency exit ways in a stadium). Then, in the second level, users operate on this infrastructure according to their own selfish interests. Finally, an attacker, observing the distribution of users in the network, strategically attacks the infrastructure so as to cause as much harm as possible (e.g., affecting as many people as possible). Solving the resulting multi-level optimization problems is computationally very challenging, in particular due to non-convexities caused by the multi-level structure. We therefore propose a new concept of level-wise approximation that allows to relax optimality requirements at each level individually. Using this paradigm, we hope to devise algorithms that efficiently compute near-optimal solutions.An additional challenge arises when taking into account the interplay of congestion effects caused by the users’ selfish action and their anticipation of the attacker’s action. An important part of our project therefore is to investigate bilevel congestion games, i.e., congestion games in which users take their choices taking into account both congestion caused by other users and the actions of a lower level attacker who will strike at the most-frequented parts of the infrastructure. Combining the insights gained on approximating multi-level network problems and congestion games, we then aim to solve multi-level network security games with congestion effects using a mix of approximation algorithms, heuristics, and exact methods, which we finally investigate in a study based on realistic data sets.

Resource allocation problems play a key role for a wide range of applications including traffic networks and telecommunication networks. An intrinsic property of the above applications is that the allocation of resources cannotbe centrally enforced but is determined by independent users, each optimizing an individual objective function (e.g., selfish users evacuating a burning building, drivers choosing the fastest route, or routing protocols choosing the least delay path or least congested server). Designing mechanisms so that the resulting allocation of resources by selfish players is efficient constitutes a fundamental research challenge. From an abstract point of view, every resource incurs a cost or a utilityto its users and a mechanism defines the strategies available to players and the cost/utility shares for every player using a specific resource. Concrete examples of such mechanisms include the design of the network infrastructure in telecommunications and traffic. This proposal attempts to advance the algorithmic foundations for computingprovably optimal or approximatively optimal mechanisms in the context of network design, scheduling, and auction-based resource allocation problems.

Location routing integrates the two classical optimization problems of facility location and vehicle routing, addressing both location and tour planning decisions in a single step. There is a large number of different versions of location routing problems, incorporating different sets of constraints arising in real-world applications, such as vehicle and depot capacities or time windows.

Library of Test Instances

Die NWO Physikalische Wissenschaften vergab TOP-Stipendien an 19 Wissenschaftler aus den Bereichen Astronomie, Informatik und Mathematik oder einer Kombination dieser Disziplinen (multidisziplinär). Bei acht Wissenschaftlern handelt es sich um erfahrene Forscher mit nachgewiesener Erfolgsbilanz, bei den anderen 11 um Nachwuchsforscher, die am Anfang ihrer wissenschaftlichen Laufbahn stehen. Insgesamt erhalten die Wissenschaftler mehr als 6 Mio. EUR.

NWO-TOP Grant

In a resource allocation game, the allocation of resources is determined by a finite number of independent players, each optimizing an individual objective function. Because selfish behavior of players usually leads to inefficient resource allocation with respect to predefined performance measures, the design of protocols as a way to improve the inefficiency of selfish resource allocation is of fundamental importance.
While numerous resource allocation games and corresponding resource allocation protocols have been analyzed in the last decade with respect to various performance indicators, there has been only recently some efforts to design optimal protocols for these indicators (Chen et al.(2008), Harks and von Falkenhausen (2011)).
This project intends to make progress in the design of optimal protocols.

Marie Curie Fellowship

When so­cio­lo­gist Tho­mas Schel­ling pu­blis­hed his re­se­arch on hou­sing se­gre­ga­ti­on in ma­jor US-Ame­ri­can ci­ties in 1971, he ac­com­plis­hed more than just cont­ri­bu­ting to a no­vel type of ›so­ci­al ma­the­ma­tics‹. With Schel­lings in­te­rest in the me­cha­nisms of so­ci­al se­gre­ga­ti­on and his re­spec­tive mo­dels, the ana­ly­sis of ac­tu­al neigh­borhood dy­na­mics con­ver­ged with a ›neigh­bor­ly‹ re­se­arch me­thod. 

Teilnehmende: Tobias Harks,  Sebastian Vehlken

Neighborhood Technologies Conference

Ziele des Projektes MultiTrans (Multikriterielle Optimierung bei Transportproblemen in der Logistik) waren die mathematische Modellierung praxisrelevanter Transportprobleme, die Entwicklung und Analyse effizienter Algorithmen zur exakten und heuristischen Lösung solcher Optimierungsprobleme, sowie die Umsetzung der Lösungsansätze in einer Demonstrationssoftware. Als Ergebnisse des Forschungsvorhabens wurden eine deutliche Senkung des Modellierungsaufwandes in der Netzwerkoptimierung und eine signifikante Verbesserung des Optimierungsergebnisses durch den erhöhten Realitätsgehalt der verwendeten Modelle angestrebt.

Participants: Tobias Harks, Felix G. König, Marco E. Lübbecke, Jannik Matuschke, Britta Peis, Alexander Richter, Jens Schulz

Forschungsprojekt