direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Competitive Exploration of Large Networks

Network and Mechanism Design for Metropolitan Infrastructures
Project head:
Dr. Yann DisserDr. Max Klimm
Project assistant:
Jan Hackfeld
June 2014 - Mai 2017
DFG within SPP "Algorithms for Big Data"


The goal of this project is to deepen the understanding of algorithms that operate on very large networks and the dynamics that arise from the competition or cooperation between such algorithms. To achieve this goal, we want to combine models and techniques from the areas of graph exploration and algorithmic game theory. To date, the literature in these areas is mostly disjoint. By closing this gap, we hope to develop new insights into the important algorithmic and economic challenges faced in large networks, most prominently in those that are part of the Internet.


As a first step, we want to develop agent models tailored to software agents exploring the Internet. We consider the ability to store a small number of network nodes that the agent can jump back to. It is interesting to analyze how such a model compares to existing agent models in the field of graph exploration, and whether it allows for efficient exploration algorithms. In addition, we plan to study exploration algorithms that balance exploration coverage versus time and memory usage on an instance-by-instance basis. Second, we aim to understand the benefit of cooperation between multiple agents and the difficulty of coordinating them. Again, we want to analyze the impact of the ability to jump back on the power of the agents. Motivated by the exploration of large networks, we plan to study collaborative exploration by teams of small size and with little memory relative to the size of the network. As a main contribution of this project, we want to initiate the study of competitive exploration of large networks. Here, agents strive to maximize an individual objective function rather than pursuing a collective agenda. The competition between agents with conflicting interests is usually analyzed within the framework of non-cooperative games. A common assumption in the game theory literature is that the agents have full knowledge of all their strategic actions. This assumption is unrealistic in large data networks, where the behavior of agents is inherently local. To overcome this issue, we want to combine methodologies from graph exploration and game theory. We are interested in characterizing the circumstances under which the behavior of competing agents converges to a stable state. Other issues to be considered are the quality of the equilibria reached and the speed of convergence. We further plan to extend our analysis to settings where the payoff of an agent is received over time, and the objective the maximization of the average payoff. Going forward, we would like to combine the insights gained for cooperative and competitive exploration in order to understand the effects of competing teams of agents. In this setting, the agents of the same team cooperate on a common task and compete against other teams with conflicting interests.

Recent Activities

  • Annual Meeting September 2015 in Karlsruhe
  • PhD student meeting May 2015 in Montabaur
  • Annual Meeting September 2014 in Frankfurt




Project related publications


Hansknecht, Christoph and Klimm, Max and Skopalik, Alexander (2014). Approximate pure Nash equilibria in weighted congestion games. Proceedings of the 17th Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 242 – 257.

Harks, Tobias and Klimm, Max and Peis, Britta (2014). Resource Competition on Integral Polymatroids. Proceedings of the 10th Conference on Web and Internet Economics (WINE)

Klimm, Max and Schütz, Andreas (2014). Congestion games with higher demand dimensions. Proceedings of the 10th Conference on Web and Internet Economics (WINE), 453-459.


Disser, Yann and Feldmann, Andreas and Klimm, Max and Mihalák, Matús (2015). Improving the Hk-bound on the price of stability in undirected Shapley network design games. Theoretical Computer Science, 557–564.

Disser, Yann and Skutella, Martin (2015). The Simplex Algorithm is NP-mighty. Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 858-872.

Chalopin, Jérémie and Das, Shantanu and Disser, Yann and Mihalák, Matúš and Widmayer, Peter (2015). Mapping Simple Polygons: The Power of telling Convex from Reflex. ACM Transactions on Algorithms, 33(16).

Dereniowski, Dariusz and Disser, Yann and Kosowski, Adrian and Pająk, Dominik and Uznański, Przemysław (2015). Fast collaborative graph exploration. Information and Computation, 37–49.

Klimm, Max and Schmand, Daniel (2015). Sharing non-anonymous costs of multiple resources optimally. Proceedings of the 9th International Conference on Algorithms and Complexity (CIAC), 274-287.


Disser, Yann and Hackfeld, Jan and Klimm, Max (2016). Undirected graph exploration with Θ(log log n) pebbles. Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 25-39.


Abed, Fidaa and Chen, Lin and Disser, Yann and Groß, Martin and Megow, Nicole and Meißner, Julie and Richter, Alexander and Rischke, Roman (2017). Scheduling Maintenance Jobs in Networks. Proceedings of the International Conference on Algorithms and Complexity (CIAC)

Bjelde, Antje and Disser, Yann and Hackfeld, Jan and Hansknecht, Christoph and Lipmann, Maarten and Meißner, Julie and Schewior, Kevin and Schlöter, Miriam and Stougie, Leen (2017). Tight bounds for online TSP on the line. Proceedings of the Symposium on Discrete Algorithms (SODA) 2017. SIAM, 994–1005.

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions