Articles in journals and conference proceedings

• Simon Fischer, Petri Mähönen, Marcel Schöngens, and Berthold Vöcking: Load Balancing for Dynamic Spectrum Assignment with Local Information for Secondary Users. In: Proc. IEEE International Dynamic Access Spectrum Access Networks (DySPAN) symposium, Chicago, Illinois, USA, October 2008.
  PDF (133 kB), Postscript (293 kB), Abstract (1.4 kB), BibTeX (425 bytes)
  > show abstract

  Load Balancing for Dynamic Spectrum Assignment with Local Information for Secondary Users

  Simon Fischer, Petri Mähönen, Marcel Schöngens, Berthold Vöcking

  In this paper we study an idealized model of load balancing for dynamic spectrum allocation (DSA) for secondary users using only local information. In our model, each agent is assigned to a channel and may reassign its load in a round based fashion. We present a randomized protocol in which the actions of the agents depend purely on some cost measure (e.g., latency, inverse of the throughput, etc.) of the currently chosen channel. Since agents act concurrently, the system is prone to oscillations. We show how this can be avoided guaranteeing convergence towards a state in which every agent sustains at most a certain threshold cost (if such a state exists). We show that the system converges quickly by giving bounds on the convergence time towards approximately balanced states. Our analysis in the fluid limit (where the number of agents approaches infinity) holds for a large class of cost functions. We support our theoretical analysis by simulations to determine the dependence on the number of agents. It turns out that the number of agents affects the convergence time only in a logarithmic fashion. The work shows under quite general assumptions that even an extremely large number of users using several hundreds of (virtual) channels can work in a DSA fashion.

  < hide abstract
• Simon Fischer, Marina Petrova, Petri Mähönen, and Berthold Vöcking: Distributed Load Balancing Algorithm for Adaptive Channel Allocation for Cognitive Radios. In: Proc. 2nd Conference on Cognitive Radio Oriented Wireless Networks and Communications (CrownCom), Orlando, FL, USA, August 2007. © Copyright 2007 by ACM, Inc.
  PDF (110 kB), Postscript (222 kB), Abstract (776 bytes), BibTeX (428 bytes)
  > show abstract

  Distributed Load Balancing Algorithm for Adaptive Channel Allocation for Cognitive Radios

  Simon Fischer, Marina Petrova, Petri Mähönen, Berthold Vöcking

  The problem of channel allocation has been extensively studied in the context of cellular networks. There is a substantial amount of work in the field of dynamic frequency assignment for WLANs and mesh networks as well. The growing interest in the cognitive radio technology and its capability to offer more efficient spectrum usage brought this problem back as one of the most popular research topics nowadays. In this paper we present two quite simple to implement, distributed algorithms for selecting channels, in cognitive radio environment, so that the load is distributed (smoothed) over them.

  < hide abstract
• Simon Fischer, Lars Olbrich, and Berthold Vöcking: Approximating Wardrop Equilibria with Finitely Many Agents. In: Proc. 21st International Symposium on Distributed Computing (DISC), pages 238–252, Lemesos, Cyprus, September 2007. DOI: 10.1007/978-3-540-75142-7_20 © Copyright 2007 Springer-Verlag
  PDF (201 kB), Postscript (409 kB), Abstract (1.5 kB), BibTeX (428 bytes)
  > show abstract

  Approximating Wardrop Equilibria with Finitely Many Agents

  Simon Fischer, Lars Olbrich, Berthold Vöcking

  We study adaptive routing algorithms in a round-based model. Suppose we are given a network equipped with load-dependent latency functions on the edges and a set of commodities each of which is defined by a collection of paths (represented by a DAG) and a flow rate. Each commodity is controlled by an agent which aims at balancing its traffic among its paths such that all used paths have the same latency. Such an allocation is called a Wardrop equilibrium.

  In recent work, it was shown that an infinite population of users each of which carries an infinitesimal amount of traffic can attain approximate equilibria in a distributed and concurrent fashion quickly. Interestingly, the convergence time is independent of the underlying graph and depends only mildly on the latency functions. Unfortunately, a direct simulation of this process requires to maintain an exponential number of variables, one for each path.

  The focus of this work lies on the distributed and efficient computation of the adaptation rules by a finite number of agents. In order to guarantee a polynomial running time, every agent computes a randomised path decomposition in every communication round. Based on this decomposition, agents remove flow from paths with high latency and reassign it proportionally to all paths. This way, our algorithm can handle exponentially large path collections in polynomial time.

  < hide abstract
  The algorithm RandomizedBalancing presented in this work has been implemented in C++.
  
  ➪ Journal version:
  Simon Fischer, Lars Olbrich, and Berthold Vöcking: Approximating Wardrop Equilibria with Finitely Many Agents. In: Distributed Computing, 21 (2) July 2008. DOI: 10.1007/s00446-008-0057-1 (Special Issue DISC 2007.) © Copyright 2008 Springer-Verlag
  PDF (231 kB), Postscript (443 kB), Abstract (1.3 kB), BibTeX (361 bytes)
  > show abstract

  Approximating Wardrop Equilibria with Finitely Many Agents

  Simon Fischer, Lars Olbrich, Berthold Vöcking

  We present efficient algorithms for computing approximate Wardrop equilibria in a distributed and concurrent fashion. Our algorithms are exexuted by a finite number of agents each of which controls the flow of one commodity striving to balance the induced latency over all utilised paths. The set of allowed paths is represented by a DAG. Our algorithms are based on previous work on policies for infinite populations of agents. These policies achieve a convergence time which is independent of the underlying network and depends mildly on the latency functions.

  These policies can neither be applied to a finite set of agents nor can they be simulated directly due to the exponential number of paths. Our algorithms circumvent these problems by computing a randomised path decomposition in every communication round. Based on this decomposition, flow is shifted from overloaded to underloaded paths. This way, our algorithm can handle exponentially large path collections in polynomial time. Our algorithms are stateless, and the number of communication rounds depends polynomially on the approximation quality and is independent of the topology and size of the network.

  < hide abstract
• Simon Fischer, Nils Kammenhuber, and Anja Feldmann: REPLEX — Dynamic Traffic Engineering Based on Wardrop Routing Policies. In: Proc. 2nd Conference on Future Networking Technologies (CoNext), pages 6–17, Lisboa, Portugal, December 2006. © Copyright 2006 by ACM, Inc.
  PDF (371 kB), Postscript (1.3 MB), Abstract (1.7 kB), BibTeX (366 bytes)
  > show abstract

  REPLEX --- Dynamic Traffic Engineering Based on Wardrop Routing Policies

  Simon Fischer, Nils Kammenhuber, Anja Feldmann

  Abstract. One major challenge in communication networks is the problem of dynamically distributing load in the presence of bursty and hard to predict changes in traffic demands. Current traffic engineering operates on time scales of several hours which is too slow to react to phenomena like flash crowds or BGP reroutes. One possible solution is to use load sensitive routing. Yet, interacting routing decisions at short time scales can lead to oscillations, which has prevented load sensitive routing from being deployed since the early experiences in Arpanet.

  However, recent theoretical results have devised a game theoretical re-routing policy that provably avoids such oscillation and in addition can be shown to converge quickly. In this paper we present ReplEx, a distributed dynamic traffic engineering algorithm based on this policy. Exploiting the fact that most underlying routing protocols support multiple equal-cost routes to a destination, it dynamically changes the proportion of traffic that is routed along each path. These proportions are carefully adapted utilising information from periodic measurements and, optionally, information exchanged between the routers about the traffic condition along the path.

  We evaluate the algorithm via simulations employing traffic loads that mimic actual Web traffic, i.e. bursty TCP traffic, and whose characteristics are consistent with self-similarity. The simulations quickly converge and do not exhibit significant oscillations on both artificial as well as real topologies, as can be expected from the theoretical results.

  < hide abstract
• Simon Fischer, Harald Räcke, and Berthold Vöcking: Fast Convergence to Wardrop Equilibria by Adaptive Sampling Methods. In: Proc. 38th Annual ACM Symposium on Theory of Computing (STOC), pages 653–662, Seattle, WA, USA, May 2006. ACM. DOI: 10.1145/1132516.1132608 © Copyright 2006 by ACM, Inc.
  PDF (196 kB), Postscript (356 kB), Abstract (2.6 kB), BibTeX (421 bytes)
  > show abstract

  Fast Convergence to Wardrop Equilibria by Adaptive Sampling Methods

  Simon Fischer, Harald Räcke, Berthold Vöcking

  Abstract. We study rerouting policies in a dynamic round-based variant of a well known game theoretic traffic model due to Wardrop. Previous analyses (mostly in the context of selfish routing) based on Wardrop's model focus mostly on the static analysis of equilibria. In this paper, we ask the question whether the population of agents responsible for routing the traffic can jointly compute or better learn a Wardrop equilibrium efficiently. The rerouting policies that we study are of the following kind. In each round, each agent samples an alternative routing path and compares the latency on this path with its current latency. If the agent observes that it can improve its latency then it switches with some probability depending on the possible improvement to the better path.

  We can show various positive results based on a rerouting policy using an adaptive sampling rule that implicitly amplifies paths that carry a large amount of traffic in the Wardrop equilibrium. For general asymmetric games, we show that a simple replication protocol in which agents adopt strategies of more successful agents reaches a certain kind of bicriteria equilibrium within a time bound that is independent of the size and the structure of the network but only depends on a parameter of the latency functions, that we call the relative slope. For symmetric games, this result has an intuitive interpretation: Replication approximately satisfies almost everyone very quickly.

  In order to achieve convergence to a Wardrop equilibrium besides replication one also needs an exploration component discovering possibly unused strategies. We present a sampling based replication-exploration protocol and analyze its convergence time for symmetric games. For example, if the latency functions are defined by positive polynomials in coefficient representation, the convergence time is polynomial in the representation length of the latency functions. To the best of our knowledge, all previous results on the speed of convergence towards Wardrop equilibria, even when restricted to linear latency functions, were pseudopolynomial.

  In addition to the upper bounds on the speed of convergence, we can also present a lower bound demonstrating the necessity of adaptive sampling by showing that static sampling methods result in a slowdown that is exponential in the size of the network. A further lower bound illustrates that the relative slope is, in fact, the relevant parameter that determines the speed of convergence.

  < hide abstract
• Simon Fischer and Berthold Vöcking: Adaptive Routing with Stale Information. In: Proc. 24th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 276–283, Las Vegas, NV, USA, July 2005. ACM. DOI: 10.1145/1073814.1073868 © Copyright 2005 by ACM, Inc.
  PDF (142 kB), Postscript (312 kB), Abstract (2.2 kB), BibTeX (384 bytes)
  > show abstract

  Adaptive Routing with Stale Information

  Simon Fischer and Berthold Vöcking

  Abstract. We investigate adaptive routing policies for large networks in which agents reroute traffic based on old information. It is a well known and practically relevant problem that old information can lead to undesirable oscillation effects resulting in poor performance. We investigate how adaptive routing policies should be designed such that these effects can be avoided.

  The network is represented by a general graph with latency functions on the edges. Traffic is managed by a large number of agents each of which is responsible for a negligible amount of traffic. Initially the agents' routing paths are chosen in an arbitrary fashion. From time to time each agent revises her routing strategy by sampling another path and switching with positive probability to this path if it promises smaller latencies. As the information on which the agent bases her decision might be stale, however, this does not necessarily lead to an improvement. The points of time at which agents revise their strategy are generated by a Poisson distribution. Stale information is modelled in form of a bulletin board that is updated periodically and lists the latencies on all edges.

  We analyze such a distributed routing process in the so-called fluid limit, that is, we use differential equations describing the fractions of traffic on different paths over time. In our model, we can show the following effects. Simple routing policies that always switch to the better alternative lead to oscillation, regardless at which frequency the bulletin board is updated. Oscillation effects can be avoided, however, when using smooth adaption policies that do not always switch to better alternatives but only with a probability depending on the advantage in the latency. In fact, such policies have dynamics that converge to a fixed point corresponding to a Nash equilibrium for the underlying routing game, provided the update periods are not too large.

  In addition, we also analyze the speed of convergence towards approximate equilibria of two specific variants of smooth adaptive routing policies, e.g., for a replication policy adopted from evolutionary game theory.

  < hide abstract
  ➪ Technical Report version:
  Simon Fischer and Berthold Vöcking: Adaptive Routing with Stale Information. Technical report, AIB-2005-06, RWTH Aachen, 2005.
  PDF (264 kB), Postscript (564 kB), Abstract (2.2 kB), BibTeX (220 bytes)
  This article is also available at the Aachener Informatik-Berichte (AIB) web server.
  > show abstract

  Adaptive Routing with Stale Information

  Simon Fischer and Berthold Vöcking

  Abstract. We investigate adaptive routing policies for large networks in which agents reroute traffic based on old information. It is a well known and practically relevant problem that old information can lead to undesirable oscillation effects resulting in poor performance. We investigate how adaptive routing policies should be designed such that these effects can be avoided.

  In our theoretical model, the network is represented by a general graph with latency functions on the edges. Traffic is managed by a large number of agents each of which is responsible for a negligible amount of traffic. Initially the agents' routing paths are chosen in an arbitrary fashion. From time to time each agent revises her routing strategy by sampling another path and switching with positive probability to this path if it promises smaller latencies. As the information on which the agent bases her decision might be stale, however, this does not necessarily lead to an improvement. The points of time at which agents revise their strategy are generated by a Poisson distribution. Stale information is modelled in form of a bulletin board that is updated periodically and lists the latencies on all edges.

  We analyze such a distributed routing process in the so-called fluid limit, that is, we use differential equations describing the fractions of traffic on different paths over time. In our model, we can show the following effects. Simple routing policies that always switch to the better alternative lead to oscillation, regardless at which frequency the bulletin board is updated. Oscillation effects can be avoided, however, when using smooth adaption policies that do not always switch to better alternatives but only with a probability depending on the advantage in the latency. In fact, such policies have dynamics that converge to a fixed point corresponding to a Nash equilibrium for the underlying routing game, provided the update periods are not too large.

  In addition, we also analyze the speed of convergence towards approximate equilibria of two specific variants of smooth adaptive routing policies, e.g., for a replication policy adopted from evolutionary game theory.

  < hide abstract
  ➪ Journal version:
  Simon Fischer and Berthold Vöcking: Adaptive Routing with Stale Information. In: Theoretical Computer Science, 2008. DOI: 10.1016/j.tcs.2008.01.055 (Invited paper. To appear)
  PDF (215 kB), Postscript (439 kB), Abstract (1.9 kB), BibTeX (278 bytes)
  > show abstract

  Adaptive Routing with Stale Information

  Simon Fischer, Berthold Vöcking

  Abstract. We investigate the behaviour of load-adaptive rerouting policies in the Wardrop model where decisions must be made on the basis of stale information. In this model, an infinite number of agents controls an infinitesimal amount of flow each, thus contributing to a network flow which induces latency. In our dynamic extension of this model, agents are activated in a concurrent and asynchronous fashion and may reroute their flow with the aim of reducing their sustained latency. It is a well-known problem that in settings where latency information is not always up to date such behaviour may lead to oscillation effects which seriously harm network performance. Two quantities determine the difficulty of avoiding oscillation: the steepness of the latency functions and the maximum possible age of the information $T$.

  In this work we ask for conditions that the rerouting policies must adhere to in order to converge to an equilibrium despite the information being stale. We consider simple policies which sample another path in a first step and then migrate from the current path to the new one with a probability that is a function of the anticipated latency gain. In fact we can show that our class of policies guarantees convergence if the latter migration probability function satisfies a certain smoothness condition that resembles Lipschitz continuity. It turns out that for smooth adaptation policies where the migration probability is chosen small enough relative to the inverse of the steepness of the latency functions and T, the population actually converges to an equilibrium.

  In addition, we analyse the speed of convergence towards approximate equilibria of two specific variants of smooth adaptive routing policies, e.g., for a replication policy adopted from evolutionary game theory.

  < hide abstract
• Simon Fischer and Berthold Vöcking: On the Structure and Complexity of Worst-Case Equilibria. In: Proc. 1st Workshop on Internet and Network Economics (WINE), number 3828 of Lecture Notes in Computer Science, pages 151–160, Hong Kong, China, December 2005. Springer-Verlag. DOI: 10.1007/11600930_16 © Copyright 2005 Springer-Verlag
  PDF (128 kB), Postscript (318 kB), Abstract (885 bytes), BibTeX (472 bytes)
  > show abstract

  On the Structure and Complexity of Worst-Case Equilibria

  Simon Fischer and Berthold Vöcking

  Abstract. We study an intensively studied resource allocation game introduced by Koutsoupias and Papadimitriou where $n$ weighted jobs are allocated to $m$ identical machines. It was conjectured by Gairing et al. that the fully mixed Nash equilibrium is the worst Nash equilibrium for this game w.r.t. the expected maximum load over all machines. The known algorithms for approximating the so-called "price of anarchy" rely on this conjecture. We present a counter-example to the conjecture showing that fully mixed equilibria cannot be used to approximate the price of anarchy within reasonable factors. In addition, we present an algorithm that constructs so-called concentrated equilibria that approximate the worst-case Nash equilibrium within constant factors.

  < hide abstract
  ➪ Journal version:
  Simon Fischer and Berthold Vöcking: On the Structure and Complexity of Worst-Case Equilibria. In: Theoretical Computer Science, 378 (2) pages 165-174, June 2007. DOI: 10.1016/j.tcs.2007.02.019 (Special Issue WINE 2005)
  PDF (154 kB), Postscript (314 kB), Abstract (1.2 kB), BibTeX (377 bytes)
  > show abstract

  On the Structure and Complexity of Worst-Case Equilibria

  Simon Fischer and Berthold Vöcking

  In the resource allocation game introduced by Koutsoupias and Papadimitriou, $n$ jobs of different weights are assigned to $m$ identical machines by selfish agents. For this game it has been conjectured by Gairing etal (2003, 2004, 2005) that the fully mixed Nash equilibrium (FMNE) is the worst possible w.\,r.\,t. the expected maximum load over all machines. Assuming the validity of this conjecture, computing a worst-case Nash equilibrium for a given instance was trivial and approximating the Price of Anarchy for this instance would be possible by approximating the expected social cost of the FMNE applying an FPRAS presented by Fotakis etal. (2002).

  We present a counter-example to this conjecture showing that fully mixed Nash equilibria cannot be used to approximate the Price of Anarchy. We show that the factor between the social cost of the worst Nash equilibrium and the social cost of the FMNE can be as large as the Price of Anarchy itself up to a constant factor. In addition, we present an algorithm that constructs so-called concentrated equilibria that approximate worst-case Nash equilibria within constant factors.

  < hide abstract
• Simon Fischer: A Polynomial Upper Bound for a Mutation-Based Algorithm on the Two-Dimensional Ising Model. In: Proc. Genetic and Evolutionary Computation Conference (GECCO), number 3102 of Lecture Notes in Computer Science, pages 1100–1112, June 2004. Springer-Verlag. © Copyright 2004 Springer-Verlag
  PDF (143 kB), Postscript (342 kB), Abstract (798 bytes), BibTeX (403 bytes)
  This article is also available as a technical report at the web server of the Collaborative Research Center "Computational Intelligence".
  > show abstract

  A Polynomial Upper Bound for a Mutation-Based Algorithm on the Two-Dimensional Ising Model

  Simon Fischer

  Abstract. Fitness functions based on the Ising model are suited excellently for studying the adaption capabilities of randomised search heuristics. The one-dimensional Ising model was considered a hard problem for mutation-based algorithms, and the two-dimensional Ising model was even thought to amplify the difficulties. While in one dimension the Ising model does not have any local optima, in two dimensions it does. Here we prove that a simple search heuristics, the Metropolis algorithm, optimises on average the two-dimensional Ising model in polynomial time.\medskip

  Keywords: Ising model, expected optimisation time, adaption

  < hide abstract
• Simon Fischer and Ingo Wegener: The Ising Model on the Ring: Mutation versus Recombination. In: Proc. Genetic and Evolutionary Computation Conference (GECCO), number 3102(1) of Lecture Notes in Computer Science, pages 1113–1124, June 2004. Springer-Verlag. © Copyright 2004 Springer-Verlag
  PDF (126 kB), Postscript (578 kB), Abstract (1009 bytes), BibTeX (401 bytes)
  An extended version of this article is available as a technical report at the web server of the Collaborative Research Center "Computational Intelligence".
  > show abstract

  The Ising Model on the Ring: Mutation versus Recombination

  Simon Fischer and Ingo Wegener

  Abstract. The investigation of genetic and evolutionary algorithms on Ising model problems gives much insight how these algorithms work as adaptation schemes.

  The Ising model on the ring has been considered as a typical example with a clear building block structure suited well for two-point crossover. It has been claimed that GAs based on recombination and appropriate diversity-preserving methods outperform by far EAs based only on mutation.

  Here, a rigorous analysis of the expected optimization time proves that mutation-based EAs are surprisingly effective. The (1+lambda)EA with an appropriate lambda-value is almost as efficient as usual GAs. Moreover, it is proved that specialized GAs do even better and this holds for two-point crossover as well as for one-point crossover.

  Keywords: Ising model, mutation vs. recombination, expected optimization time, fitness sharing

  < hide abstract
  ➪ Journal version:
  Simon Fischer and Ingo Wegener: The One-dimensional Ising Model: Mutation versus Recombination. In: Theoretical Computer Science, 344 (2–3) pages 208–225, November 2005. DOI: 10.1016/j.tcs.2005.04.002
  PDF (179 kB), Postscript (396 kB), Abstract (1 kB), BibTeX (341 bytes)
  > show abstract

  The One-Dimensional Ising Model: Mutation versus Recombination

  Simon Fischer and Ingo Wegener

  Abstract. The investigation of genetic and evolutionary algorithms on Ising model problems gives much insight into how these algorithms work as adaptation schemes. The one-dimensional Ising model with periodic boundary conditions has been considered as a typical example with a clear building block structure suited well for two-point crossover. It has been claimed that GAs based on recombination and appropriate diversity-preserving methods by far outperform EAs based on mutation only. Here, a rigorous analysis of the expected optimization time proves that mutation-based EAs are surprisingly effective. The (1+lambda)EA with an appropriate lambda-value is almost as efficient as typical GAs. Moreover, it is proved that specialized GAs do even better and this holds for two-point crossover as well as for one-point crossover.

  Keywords: Ising model, evolutionary algorithms, randomized local search, expected optimization time

  < hide abstract
• Simon Fischer and Berthold Vöcking: On the Evolution of Selfish Routing. In: Proc. 12th Annual European Symposium on Algorithms (ESA), number 3221 of Lecture Notes in Computer Science, pages 323–334, Bergen, Norway, September 2004. Springer-Verlag. DOI: 10.1007/b100428 © Copyright 2004 Springer-Verlag
  PDF (135 kB), Postscript (329 kB), Abstract (1.2 kB), BibTeX (434 bytes)
  An extended version of this article is available as a technical report at the DELIS web server.
  > show abstract

  On the Evolution of Selfish Routing

  Simon Fischer and Berthold Vöcking

  Abstract. We introduce a model to study the temporal behaviour of selfish agents in networks. So far, most of the analysis of selfish routing is concerned with static properties of equilibria which is one of the most fundamental paradigms in classical Game Theory. By adopting a generalised approach of Evolutionary Game Theory we extend the model of selfish routing to study the dynamical behaviour of agents.

  For symmetric games corresponding to singlecommodity flow, we show that the game converges to a Nash equilibrium in a restricted strategy space. In particular we prove that the time for the agents to reach an $\epsilon$-approximate equilibrium is polynomial in $\epsilon$ and only logarithmic in the ratio between maximal and optimal latency. In addition, we present an almost matching lower bound in the same parameters.

  Furthermore, we extend the model to asymmetric games corresponding to multicommodity flow. Here we also prove convergence to restricted Nash equilibria, and we derive upper bounds for the convergence time that are linear instead of logarithmic.

  < hide abstract

Technical reports and non-refereed articles

• Heiner Ackermann, Petra Berenbrink, Simon Fischer, and Martin Hoefer: Concurrent Imitation Dynamics in Congestion Games. Technical report, arXiv:0808.2081v1, arXiv.org, 2008.
  PDF (257 kB), Postscript (413 kB), Abstract (1.8 kB), BibTeX (273 bytes)
  > show abstract

  Concurrent Imitation Dynamics in Congestion Games

  Heiner Ackermann, Petra Berenbrink, Simon Fischer, and Martin Hoefer

  Imitating successful behavior is a natural and frequently applied approach to trust in when facing scenarios for which we have little or no experience upon which we can base our decision. In this paper, we consider such behavior in atomic congestion games. We propose to study concurrent imitation dynamics that emerge when each player samples another player and possibly imitates this agents' strategy if the anticipated latency gain is sufficiently large. Our main focus is on convergence properties. Using a potential function argument, we show that our dynamics converge in a monotonic fashion to stable states. In such a state none of the players can improve its latency by imitating somebody else.

  As our main result, we show rapid convergence to approximate equilibria. At an approximate equilibrium only a small fraction of agents sustains a latency significantly above or below average. In particular, imitation dynamics behave like fully polynomial time approximation schemes (FPTAS). Fixing all other parameters, the convergence time depends only in a logarithmic fashion on the number of agents.

  Since imitation processes are not innovative they cannot discover unused strategies. Furthermore, strategies may become extinct with non-zero probability. For the case of singleton games, we show that the probability of this event occurring is negligible. Additionally, we prove that the social cost of a stable state reached by our dynamics is not much worse than an optimal state in singleton congestion games with linear latency function. Finally, we discuss how the protocol can be extended such that, in the long run, the dynamics converges to a Nash equilibrium.

  < hide abstract
• Simon Fischer and Berthold Vöcking: A Counterexample to the Fully Mixed Nash Equilibrium Conjecture. Technical report, AIB-2005-11, RWTH Aachen, 2005.
  PDF (180 kB), Postscript (399 kB), Abstract (615 bytes), BibTeX (242 bytes)
  This article is also available at the Aachener Informatik-Berichte (AIB) web server.
  > show abstract

  A Counterexample to the Fully Mixed Nash Equilibrium Conjecture

  Simon Fischer and Berthold Vöcking

  Abstract. We study a well-known resource allocation game introduced by Koutsoupias and Papadimitriou. It was conjectured by Gairing et al. that the fully mixed Nash equilibrium is the worst Nash equilibrium for this game. The known algorithms for approximating the so-called "price of anarchy" w.r.t. mixed equilibria rely on this conjecture. We present a counterexample to the conjecture showing that fully mixed equilibria cannot be used to approximate the price of anarchy within reasonable factors.

  < hide abstract
• Simon Fischer and Berthold Vöcking: Evolutionary Game Theory with Applications to Adaptive Routing. In: Proc. European Conference on Complex Systems (ECCS), pages 104, Paris, France, November 2005.
  PDF (111 kB), Postscript (251 kB), Abstract (950 bytes), BibTeX (320 bytes)
  This article surveys the results from "On the Evolution of Selfish Routing" (ESA'04) and "Adaptive Routing with Stale Information" (PODC'05) below.
  > show abstract

  Evolutionary Game Theory with Applications to Adaptive Routing

  Simon Fischer and Berthold Vöcking

  Abstract. One of the most important problems in large communication networks like the Internet is the problem of routing traffic through the network. Current Internet technology based on the TCP protocol does not route traffic adaptively to the injection rates but uses fixed end-to-end routes and adjusts only the injection rates in order to avoid congestion. A more flexible approach uses load-adaptive rerouting policies that reconsider their routing strategies from time to time depending on the current network traffic. In this manuscript, we survey recent results from [FV04] and [FV05] about the application of methods from evolutionary game theory to such an adaptive traffic management.

  Key words: Evolutionary game theory, Wardrop model, adaptive routing, stale information, analysis and dynamics of complex networks

  < hide abstract
• Ingo Mierswa, Ralf Klinkberg, Simon Fischer, and Oliver Ritthoff: A Flexible Platform for Knowledge Discovery Experiments: YALE – Yet Another Learning Environment. In: LLWA 03 - Tagungsband der GI-Workshop-Woche Lernen - Lehren - Wissen - Adaptivität, 2003.
  PDF (59.6 kB), BibTeX (364 bytes)
• Oliver Ritthoff, Ralf Klinkenberg, Simon Fischer, and Ingo Mierswa: A Hybrid Approach to Feature Selection and Generation Using an Evolutionary Algorithm. In: Proceedings of the 2002 U.K. Workshop on Computational Intelligence (UKCI-02), pages 147–154, Birmingham, UK, September 2002. University of Birmingham. (ISBN 0704423685)
  Postscript (138 kB), BibTeX (488 bytes)
• Simon Fischer, Ralf Klinkenberg, Ingo Mierswa, and Oliver Ritthoff: Yale: Yet Another Learning Environment – Tutorial. Technical report, CI-136/02, Collaborative Research Center 531, Dortmund University, Dortmund, Germany, June 2002. http://yale.sourceforge.net.
  PDF (819 kB), Postscript (176 kB), BibTeX (410 bytes)
• Oliver Ritthoff, Ralf Klinkenberg, Simon Fischer, Ingo Mierswa, and Sven Felske: Yale: Yet Another Learning Environment. In: LLWA 01 – Tagungsband der GI-Workshop-Woche Lernen – Lehren – Wissen – Adaptivität, number 763 of Forschungsberichte des Fachbereichs Informatik, Universität Dortmund, pages 84–92, Dortmund, Germany, October 2001. (ISSN 0933-6192)
  PDF (2.5 MB), Postscript (881 kB), BibTeX (539 bytes)

Theses

• Simon Fischer: Dynamic Selfish Routing. PhD Thesis, Lehrstuhl für Algorithmen und Komplexität, RWTH Aachen, June 2007.
  PDF (1.9 MB), Postscript (4.9 MB), Abstract (5.1 kB), BibTeX (219 bytes)
  > show abstract

  Dynamic Selfish Routing

  Simon Fischer

  This thesis deals with dynamic, load-adaptive rerouting policies in game theoretic settings. In the Wardrop model, which forms the basis of our dynamic population model, each of an infinite number of agents injects an infinitesimal amount of flow into a network, which in turn induces latency on the edges. Each agent may choose from a set of paths and strives to minimise its sustained latency selfishly. Population states which are stable in that no agent can improve its latency by switching to another path are referred to as Wardrop equilibria.

  A variety of results in this model have been obtained recently. Most of these revolve around the price of anarchy, which measures the degradation of performance due to the selfish behaviour of the agents as compared to a centrally optimised solution. Most of these analyses consider the notion of Wardrop equilibria as a solution concept of selfish routing games, but disregard the question of how such an equilibrium can be attained in the first place. In fact, common game theoretic assumptions needed for the motivation of equilibria in general strategic games are not satisfied for routing games in large networks, the Internet being the prime example. These assumptions comprise accurate knowledge of the network and its latency functions as well as unbounded rationality and reasoning capabilities. The question of how Wardrop equilibria can be attained by a population of selfish agents is the central topic of this thesis.

  Our first approach is inspired by evolutionary game theory. We show that Wardrop equilibria actually satisfy a stronger stability criterion, called evolutionary stability, which can be motivated by milder assumptions. We model a population of agents following some very simple randomised selfish rules allowing them to exchange their path for a better one from time to time. An agent samples another path according to some probability distribution and possibly exchanges its current path for the new one with a probability that increases with the latency gain. The behaviour of such a population over time can be described in terms of a system of differential equations. For a concrete choice of probability distributions involved in the above rules, these differential equations take the form of the so-called replicator dynamics. As a first result, we show that a population following this dynamics converges towards the set of Wardrop equilibria.

  This convergence result implicitly assumes perfect information in that rerouting decisions made by other agents are observable by other agents immediately. In communication networks, however, such rerouting decisions may be observed only with a delay. In both theory and practise, it is known that rerouting decisions based on stale information may lead to undesirable oscillation effects which seriously harm performance. We consider an extension of our dynamic population model in which information is updated only at intervals of a given length. We show that, despite of this, convergence to Wardrop equilibria is still possible. For any class of latency functions with bounded slope and any finite update period length, policies from a large class converge towards Wardrop equilibria provided that they satisfy a certain smoothness condition. This condition requires the migration rate to be reduced by a factor that is reciprocal to the maximum slope and the update period length.

  Finally, we show that Wardrop equilibria can be approached quickly. This is an issue of particular importance if the network or the flow demands themselves may change over time. To measure the speed of convergence, we consider the time to reach approximate Wardrop equilibria. We show that by applying a clever sampling technique it is possible to reach an approximate Wardrop equilibrium in time polynomial in the approximation quality and the representation length of the network, e.g., for positive polynomial latency functions in coefficient representation. In particular, our bounds depend on the maximum slope of the latency functions only logarithmically, which improves over earlier results in similar models which depend linearly on this parameter. We show that the crucial parameter that limits the speed of convergence is not the slope, but rather the elasticity of the latency functions. This parameter is closely related to the degree of polynomials.

  Based on these positive theoretical results, we design a dynamic traffic engineering protocol which we evaluate by simulations. Our protocol splits traffic bound for the same destination among alternative next-hop routers and continuously adjusts the splitting ratios. The simulation framework involves significantly more details than the Wardrop model does. For example, our simulations feature a full TCP implementation at packet level and include realistic HTTP workload generated on the basis of realistic statistical properties of Web users. The simulation results are in good correspondence with theory. We see that our protocol in fact converges quickly and significantly improves the throughput of an autonomous system.

  < hide abstract
• Simon Fischer: Evolutionäre Algorithmen für verallgemeinerte Ising-Modelle. Master's Thesis, Lehrstuhl für effiziente Algorithmen und Komplexitätstheorie, Universität Dortmund, September 2003.
  PDF (811 kB), Postscript (3.9 MB), ps.gz (1.1 MB), BibTeX (301 bytes)
  German only. Includes gimmick.
  

Other publications

• Simon Fischer: Dynamisches eigennütziges Routing. In: Dorothea Wagner (editors): Ausgezeichnete Informatik Dissertationen, 2008. (To appear)
  BibTeX (228 bytes)
• Simon Fischer and Berthold Vöcking: Dynamic Selfish Routing and Traffic Optimization. In: Friedhelm Meyer auf der Heide (editors): The European Integrated Project ``Dynamically Evolving, Large Scale Information Systems (DELIS)'', Proceedings of the Final Workshop, pages 147–164, 2008. HNI Verlagsschriftenreihe.
  PDF (150 kB), Postscript (225 kB), Abstract (1.6 kB), BibTeX (421 bytes)
  > show abstract

  Dynamic Selfish Routing and Traffic Optimisation

  Simon Fischer, Berthold Vöcking

  Abstract. This work surveys results from the PhD thesis of Simon Fischer as well as from Fischer, Olbrich, Vöcking 2006.

  Recently, the Wardrop model has attracted a lot of attention as a model of selfish behaviour in routing scenarios. In this model, an infinite number of users controls an infinite amount of flow each. The overall flow induces latencies on the edges, and agents strive to minimise their sustained latency selfishly. Most of the studies on this model focus on static properties of equilibria like bounds on the degradation of performance due to the selfishness of the agents and the absence of central coordination, and ways to reduce this degradation.

  In order to motivate the study of equilibria, one typically uses strong assumptions on the knowledge and rationality of the agents. In this work, we take a different approach by modelling the agents as a dynamic population of agents exchanging their routing path from time to time in order to improve their sustained latency.

  Our motivation is twofold. First, our results show that it is possible for a population of agents to attain an equilibrium without relying on the abovementioned assumptions, merely by following some simple selfish improvement rules. Second, we use these results to obtain fast distributed algorithms for computing approximate Wardrop equilibria.

  Our analysis are mainly theoretical, but we also present simulations of dynamic traffic engineering protocols based on our population dynamics.

  < hide abstract