Algorithmic Mechanism Design for Dynamic Flows

• Applicant: Professor Dr. Tobias Harks
• Subject Area: Theoretical Computer Science ; Mathematics
• Term: from 2016 to 2024
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 319145075

• Final Report Year: 2025

Final Report Abstract

In this project, we investigated fundamental structures of dynamic network equilibria based on the different information structures of agents. We distinguished between full information models, prediction based models and also models, where the strategy space is restricted and may depend on the collective action of all other agents. We derived several existence results, characterization results and also results related to coordination mechanisms with tolls, where the goal is to implement dynamic equilibria having certain desiderata like minimum overall travel time.

Publications

• Dynamic Traffic Assignment for Electric Vehicles. In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022) 106, pp. 6:1–6:15.
  Lukas Graf, Tobias Harks & P Rashant Palkar
  
• Prediction Equilibrium for Dynamic Network Flows. Journal of Machine Learning Research 24 (2023), no. 310, pp. 1–33
  Lukas Graf, Tobias Harks, Kostas Kollias & Michael Markl
  
• The Price of Anarchy for Instantaneous Dynamic Equilibria. Mathematics of Operations Research.
  Graf, Lukas & Harks, Tobias
  
• Side-Constrained Dynamic Traffic Equilibria. Operations Research, 72(6), 2279-2301.
  Graf, Lukas & Harks, Tobias
  
• Tolls for Dynamic Equilibrium Flows. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2560-2606. Society for Industrial and Applied Mathematics.
  Graf, Lukas; Harks, Tobias & Schwarz, Julian