<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>937</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2006-10-10</completedDate>
    <publishedDate>2006-10-10</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Nash Equilibria in Online Sequential Routing Games</title>
    <abstract language="eng">In this paper, we study the efficiency of Nash equilibria for a sequence of nonatomic routing games. We assume that the games are played consecutively in time in an online fashion: by the time of playing game $i$, future games $i+1,\dots,n$ are not known, and, once players of game $i$ are in equilibrium, their corresponding strategies and costs remain fixed. Given a sequence of games, the cost for the sequence of Nash equilibria is defined as the sum of the cost of each game. We analyze the efficiency of a sequence of Nash equilibria in terms of competitive analysis arising in the online optimization field. Our main result states that the online algorithm $\sl {SeqNash}$ consisting of the sequence of Nash equilibria is $\frac{4n}{2+n}$-competitive for affine linear latency functions. For $n=1$, this result contains the bound on the price of anarchy of $\frac{4}{3}$ for affine linear latency functions of Roughgarden and Tardos [2002] as a special case. Furthermore, we analyze a problem variant with a modified cost function that reflects the total congestion cost, when all games have been played. In this case, we prove an upper bound of $\frac{4n}{2+n}$ on the competitive ratio of $\sl {SeqNash}$. We further prove a lower bound of $\frac{3n-2}{n}$ of $\sl {SeqNash}$ showing that for $n=2$ our upper bound is tight.</abstract>
    <identifier type="serial">06-43</identifier>
    <identifier type="opus3-id">937</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-9376</identifier>
    <enrichment key="SourceTitle">Appeared as: Tobias Harks and Laslo Vegh: Nonadaptive Selfish Routing with Online Demands in: CAAN 2007, Combinatorial and Algorithmic Aspects of Networking Workshop, Halifax, Canada, 2007. Jeannette C. M. Janssen and Pawel Pralat (eds.) LNCS, 4852. Springer 2007, pp. 27-45</enrichment>
    <author>Tobias Harks</author>
    <series>
      <title>ZIB-Report</title>
      <number>06-43</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Congestion Game</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Online Optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Nash equilibria</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="msc" number="91-XX">GAME THEORY, ECONOMICS, SOCIAL AND BEHAVIORAL SCIENCES</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/937/ZR-06-43.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/937/ZR_06_43.orig.Vers.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/937/ZR_06_43.orig.Vers.ps</file>
  </doc>
  <doc>
    <id>1042</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>doctoralthesis</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation>Graduiertenkolleg MAGSI</contributingCorporation>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2007-11-30</completedDate>
    <publishedDate>2007-11-30</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Multicommodity Routing Problems-Selfish Behavior and Online Aspects-</title>
    <abstract language="eng">In this thesis, we study multicommodity routing problems in networks, in which commodities have to be routed from source to destination nodes. Such problems model for instance the traffic flows in street networks, data flows in the Internet, or production flows in factories. In most of these applications, the quality of a flow depends on load dependent cost functions on the edges of the given network. The total cost of a flow is usually defined as the sum of the arc cost of the network. An optimal flow minimizes this cost. A main focus of this thesis is to investigate online multicommodity routing problems in networks, in which commodities have to be routed sequentially. Arcs are equipped with load dependent price functions defining routing costs, which have to be minimized. We discuss a greedy online algorithm that routes (fractionally) each commodity by minimizing a convex cost function that depends on the previously routed flow. We present a competitive analysis of this algorithm and prove upper bounds of (d+1)^(d+1) for polynomial price functions with nonnegative coefficients and maximum degree d. For networks with two nodes and parallel arcs, we show that this algorithm returns an optimal solution. Without restrictions on the price functions and network, no algorithm is competitive. We also investigate a variant in which the demands have to be routed unsplittably. In this case, it is NP-hard to compute the offline optimum. Furthermore, we study selfish routing problems (network games). In a network game, players route demand in a network with minimum cost. In this setting, we study the quality of Nash equilibria compared to the the system optimum (price of anarchy) in network games with nonatomic and atomic players and spittable flow. As a main result, we prove upper bounds on the price of anarchy for polynomial latency functions with nonnegative coefficients and maximum degree d, which improve upon the previous best ones.</abstract>
    <abstract language="deu">Diese Arbeit befasst sich mit Mehrgüterﬂussproblemen, in denen Güter mit einer bestimmten Rate durch ein gegebenes Netzwerk geleitet werden müssen. Mithilfe von Mehrgüterﬂussproblemen können zum Beispiel Verkehrsﬂüsse in Strassenverkehrsnetzen oder im Internet modelliert werden. In diesen Anwendungen wird die Efﬁzienz von Routenzuweisungen für Güter durch lastabhängige Kostenfunktionen auf den Kanten eines gegebenen Netzwerks deﬁniert. Die Gesamtkosten eines Mehrgüterﬂüsses sind durch die Summe der Kosten auf den Kanten deﬁniert. Ein optimaler Mehrgüterﬂuss minimiert diese Gesamtkosten. Ein wesentlicher Bestandteil dieser Arbeit ist die Untersuchung sogenannter Online Algorithmen, die Routen für bekannte Güternachfragen berechnen, ohne vollständiges Wissen über zukünftige Güternachfragen zu haben. Es konnte ein Online Algorithmus gefunden werden, dessen Gesamtkosten für polynomielle Kostenfunktionen mit endlichem Grad nicht beliebig von denen einer optimalen Lösung abweichen. Für die Berechung einer optimalen Lösung müssen alle Güternachfragen a priori vorliegen. Dieses Gütekriterium gilt unabhängig von der gewählten Netzwerktopologie oder der Eingabesequenz von Gütern. Desweiteren befasst sich diese Arbeit mit der Efﬁzienz egoistischer Routenwahl einzelner Nutzer verglichen zu einer optimalen Routenwahl. Egoistisches Verhalten von Nutzern kann mithilfe von nichtkooperativer Spieltheorie untersucht werden. Nutzer werden als strategisch agierende Spieler betrachtet, die ihren Proﬁt maximieren. Als Standardwerkzeug zur Analyse solcher Spiele hat sich das Konzept des Nash Gleichgewichts bewährt. Das Nash Gleichweicht beschreibt eine stabile Strategieverteilung der Spieler, in der kein Spieler einen höheren Proﬁt erzielen kann, wenn er einseitig seine Strategie ändert. Als Hauptergebnis dieser Arbeit konnte für polynomielle Kostenfunktionen mit endlichem Grad gezeigt werden, dass die Gesamtkosten eines Nash Gleichgewichts für sogennante atomare Spieler, die einen diskreten Anteil der gesamten Güternachfrage kontrollieren, nicht beliebig von den Gesamtkosten einer optimalen Lösung abweichen. In this thesis, we study multicommodity routing problems in networks, in which commodities have to be routed from source to destination nodes. Such problems model for instance the traffic flows in street networks, data flows in the Internet, or production flows in factories. In most of these applications, the quality of a flow depends on load dependent cost functions on the edges of the given network. The total cost of a flow is usually defined as the sum of the arc cost of the network. An optimal flow minimizes this cost. A main focus of this thesis is to investigate online multicommodity routing problems in networks, in which commodities have to be routed sequentially. Arcs are equipped with load dependent price functions defining routing costs, which have to be minimized. We discuss a greedy online algorithm that routes (fractionally) each commodity by minimizing a convex cost function that depends on the previously routed flow. We present a competitive analysis of this algorithm and prove upper bounds of (d+1)^(d+1) for polynomial price functions with nonnegative coefficients and maximum degree d. For networks with two nodes and parallel arcs, we show that this algorithm returns an optimal solution. Without restrictions on the price functions and network, no algorithm is competitive. We also investigate a variant in which the demands have to be routed unsplittably. In this case, it is NP-hard to compute the offline optimum. Furthermore, we study selfish routing problems (network games). In a network game, players route demand in a network with minimum cost. In this setting, we study the quality of Nash equilibria compared to the the system optimum (price of anarchy) in network games with nonatomic and atomic players and spittable flow. As a main result, we prove upper bounds on the price of anarchy for polynomial latency functions with nonnegative coefficients and maximum degree d, which improve upon the previous best ones.</abstract>
    <identifier type="isbn">3867273596</identifier>
    <identifier type="opus3-id">1070</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-10426</identifier>
    <enrichment key="SourceTitle">Cuvillier Verlag, Berlin, 2007 ISBN-10: 3867273596, ISBN-13: 9783867273596</enrichment>
    <author>Tobias Harks</author>
    <submitter>unknown unknown</submitter>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Mehrgueterflussprobleme</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Online Optimierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Algorithmische Spieltheorie.</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Multicommodity Flow</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Online Optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Algorithmic Game Theory</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="90Cxx">Mathematical programming [See also 49Mxx, 65Kxx]</collection>
    <collection role="msc" number="91-XX">GAME THEORY, ECONOMICS, SOCIAL AND BEHAVIORAL SCIENCES</collection>
    <collection role="collections" number="">Dissertationen</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <thesisGrantor>Technische Universität Berlin</thesisGrantor>
    <file>https://opus4.kobv.de/opus4-zib/files/1042/harks_thesis_revised.pdf</file>
  </doc>
</export-example>
