<?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>
</export-example>
