## Former Research Projects at the Chair of Informatik 1

- funded by the German-Israeli Foundation for Scientific Research and Development (GIF) (January 1, 2007 - December 31, 2010)
- funded by the DFG, Schwerpunkt 1126 (since July 2001)
- funded by the European Union, Integrated Project (since Jan 2004)
- funded by the European Science Foundation, Cost Action 293 (since Jan 2005)
- funded by the DFG (since Jan 2003)
- funded by the DFG (since Oct 2005)

**Generalized Congestion Games: Analysis, Computation, and Evolution**

funded by the German-Israeli Foundation for Scientific Research and Development (GIF) (January 1, 2007 - December 31, 2010)

The project proposes to bring together two disciplines - computer science and game theory - and by doing so to address some fundamental problems of computing in the Internet era. Combining our expertise we propose to handle several complementary issues in non-cooperative multi-agent systems. Since we can show that congestion and network games with player-specific payoff functions give us the set of all strategic games, while congestion games with player-symmetric payoff functions are the most popular type of games discussed in the computer science literature, the study of generalized congestion games is a most effective way to bridge the gap between computer science and game theory.

When referring to generalized congestion games we refer both to congestion games where agents may have different payoffs functions, as well as to congestion games with uncertainty (e.g. about the number of participants or other agents' costs). The nice graph-theoretic representation of general strategic games as player-specific congestion games enables to tackle the fundamental problem of existence of solution concepts (e.g. pure strategy equilibrium or strong equilibrium) as a function of the graph structure, as well as determine the complexity of computation and the speed of convergence to solutions as a function of the graph structure. In order to deal with congestion games with incomplete information, our aim is to tackle reasoning about uncertainty in multi-agent systems when exact probabilistic information is not available. For doing so, new equilibrium concepts are to be defined and applied to congestion settings.

This is a joint project with Dov Monderer and Moshe Tennenholtz from the Technion.**Management variabler Datenströme in Netzwerken**

funded by the DFG, Schwerpunkt 1126 (since July 2001)

This project deals with dynamic routing algorithms in large networks like the Internet. The goal is to improve our understanding of communication patterns as well as to design algorithms routing the data in such a way that the communication load is as evenly distributed over the available resources as possible. This gives us the opportunity to avoid congestion on the one hand and to guarantee a fair treatment of all participating users on the other hand. In particular, we aim at the design of algorithms for allocating streams of data on web servers as well as for performing intra-domain routing in networks. The resulting research problems will be tackled theoretically, practically, and experimentally. The project is part of the DFG research program "Algorithmik großer und komplexer Netzwerke". We closely cooperate with the networking group of the TU München headed by Anja Feldmann. Our particular focus in this cooperation is mainly on the theoretical part.**DELIS - Dynamically Evolving Large Scale Information Systems**

funded by the European Union, Integrated Project (since Jan 2004)

Most of the existing and foreseen complex networks are built, operated and used by a multitude of diverse economic interests. A prime example is the Internet, perhaps the most complex computational artifact of our times. The (possibly) selfish nature of the participating entities calls for a deeper understanding of the network dynamics in order to efficiently achieve their cooperation, by possibly considering bounded rationality aspects. In the past few years, there has been a flourishing amount of work in the border of Computer Science, Economics, Game Theory and Biology that has started to address the above issues. For example, (a) selfish network routing (and flows) were addressed in a number of recent research papers, (b) mechanism design for algorithmic cooperation of selfish users was proposed by many authors, (c) evolutionary economics addresses the dynamics of self-organization in large networks, and (d) the issues of bounded rationality of machines versus their ability for game playing were examined by several research groups, among them the Nobel-prized Economists work of 2001 and 2002.

Activities within the project can be grouped into two main classes:

*Basic Research:*basic research to understand the dynamics of the network and the effect of concepts like self-organization, selfishness and bounded rationalism as well as the structure of equilibria (and the form of dynamics) in such systems.

*Efficient Algorithms:*design of mechanisms and algorithms that efficiently achieve the cooperation between the involved selfish entities, possibly applying results from evolutionary models.**Graphs and Algorithms in Communication Networks**

funded by the European Science Foundation, Cost Action 293 (since Jan 2005)

The main objective of this Action is to create a discussion space between applied communities and theorists in the context of communication networks in which models and assumptions can be reviewed and formalized into the appropriate language.

Inside the context of communication networks, the Action focusses on, but is not restricted to the following specific fields:

*QoS networks*: Quality of Service (QoS) refers to a broad collection of networking technologies and techniques. The goal of QoS is to provide guarantees on traffic transmission. Elements of network performance within the scope of QoS include availability (uptime), bandwidth (throughput), latency (delay), delay jitter, and error rate.*Optimization in optical networks:*Optical networks using light paths in optical fibers as communication media induce a number of problems that cannot be directly resolved by using standard solutions from electronic networks, but require new approaches and techniques, instead. These problems include routing techniques, wavelength assignment on switches and cross connects, signalling, topologies design, and path recovery (backup) for protection and restoration.*Optimization in wireless networks:*Wireless networks were traditionally related with voice and telephony. Nowadays, packet networks are also supported in mobile, such as in GPRS and UMTS technologies. Trends on wireless networks include QoS for multimedia transmission and backup paths. Therefore, problems for static networks are moving to wireless, such as delay minimization, traffic engineering, frequency assignment and localization. But there are several additional challenges for wireless networks, one is for instance the coordination of the single uncontrolled agents participation in the network.**Probabilistische Analyse diskreter Optimierungsprobleme**

funded by the DFG (since Oct 2005)

Many algorithmic problems are hard from a worst-case point of view but can be solved quite well on typical inputs by heuristic approaches. Hence, worst-case complexity does not seem to be an appropriate measure for the complexity of these problems. This research project deals with the probabilistic analysis of such problems and heuristics in order to narrow the gap between the observations made in practice and the theoretical understanding of these problems.

For many problems, average-case analyses do not provide much insight either since inputs which occur in practice usually possess certain properties and a certain structure which cannot be reflected by an average-case analysis alone as it is not clear how to choose the underlying probability distribution over the set of possible inputs. In this project, we turn our attention to more general probabilistic input models like, e.g., the model of smoothed analysis. The semi-random input model used in a smoothed analysis consists of two stages. First an adversary chooses an input, then this input is randomly perturbed in the second step. In particular, the adversary can specify a worst-case input with certain properties which is only slightly perturbed in the second stage.

The focus of our research are problems which can be expressed in the form of integer linear programs. In our previous analyses we have characterized the class of integer optimization problems with polynomial smoothed complexity. The algorithms with polynomial smoothed complexity we designed, however, are clearly outperformed by common heuristics used in practice, like, e.g., Branch and Bound and Branch and Cut approaches. One of the main goals of this research project is the probabilistic analysis of these heuristics in order to understand why they perform so extraordinary well in practice. Our approach consists of two steps: First structural parameters like, e.g., the number of Pareto optimal solutions or the integrality gap, are analyzed. Then the running time of the heuristics is analyzed in terms of these parameters.**Flexible Online-Algorithmen**

funded by the DFG, Emmy-Noether-Programm (since Jan 2003)

Online algorithms studied in theory are characterized by the fact that they do not have knowledge about the whole input sequence of jobs in advance. Instead, the input sequence is generated job by job, and a new job is not issued until the previous one is handled by the online algorithm. In real applications, jobs can usually be delayed for a short amount of time, and hence the input sequence of jobs can be rearranged in a limited fashion to optimize the performance. This flexible online scenario occurs in many applications in computer science and economics, e.g., in computer graphics: A rendering system displays a sequence of primitives. The number of state changes of such a system are a significant factor for the performance. State changes occur when two consecutively rendered primitives differ in their attribute values, e.g., in their texture or shader program. With the help of a reordering buffer in which primitives can be buffered the sequence of primitives can be reordered online in such a way that the number of the state changes is reduced.