Nash Equilibria
in
Discrete Routing Games
Dissertation
von
Manuel Rode
Schriftliche Arbeit zur Erlangung des Grades
eines Doktors der Naturwissenschaften
Fakultät für Elektrotechnik, Informatik und Mathematik
der Universität Paderborn
Paderborn, im November 2004
Acknowledgment
I would like to thank all persons who supported my research during the past three years.
First and foremost, let me mention my advisor, Prof. Dr. Burkhard Monien, who consis-
tently gave me guidance in the process of scientific work and set a good example. It was
him to encourage me to start this PhD project. He involved me in his way of thinking and
the development of new ideas. His working group always provided a convenient research
environment to me. I also thank him for bringing to me the opportunity of a graduate
fellowship.
Prof. Dr. Marios Mavronicolas from the University of Cyprus got early into the recent re-
search on selfish routing. Mutual visits and discussions contributed to the progress in my
research as well. I thank him for giving good advice and for his great job on collaborative
publications.
I thank my secondary advisors Prof. Dr. Friedhelm Meyer auf der Heide and Prof. Dr.
Leena Suhl.
Besides Prof. Dr. Burkhard Monien and Prof. Dr. Marios Mavronicolas, Dr. Rainer Feld-
mann, Martin Gairing and Thomas Lücking are part of the "Nash team". I thank them for
several helpful discussions and for the fruitful work on joint publications.
I am indebted to Dr. Robert Elsässer, Henning Meyerhenke and Dr. Ulf-Peter Schroeder
for reading and commenting on parts of this work.
I thank all my colleagues for several discussions on scientific and non-scientific topics
and for technical and administrative support. To name those I did not mention yet: Ulrich
Ahlers, Bernard Bauer, Yvonne Bleischwitz, Dr. Torsten Fahle, Sven Grothklags, Georg
Kliewer, Dr. Michael Laska, Dr. Ulf Lorenz, Dr. Tomas Plachetka, Marion Rohloff, Ste-
fan Schamberger, Dr. Meinolf Sellmann, Dr. Norbert Sensen, Thomas Thissen, Karsten
Tiemann, Andreas Woclaw and Alexander Znamenshchykov.
This work was supported by a fellowship of the International Graduate School Dynamic
Intelligent Systems at the University of Paderborn. Thanks go to the Graduate School
team.
Paderborn,
November 2004
Manuel Rode
iv
Contents
1 Introduction 1
1.1 Selfishness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Strategic Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.3 Routing Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.4 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.5 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Preliminaries 11
2.1 Basic Mathematical Definitions . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Routing Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.1 Generic Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.2 Subclasses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 Pure Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.4 Mixed Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.5 Optimum, Nash equilibrium and Coordination Ratio . . . . . . . . . . . . 15
2.6 Summary of Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.7 Relations and Expressions . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.7.1 The Generic Routing Model . . . . . . . . . . . . . . . . . . . . 18
2.7.2 The Unrelated Routing Model . . . . . . . . . . . . . . . . . . . 20
2.7.3 The Congestion Routing Model . . . . . . . . . . . . . . . . . . 22
2.8 Remark . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3 Nashification 25
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Definitions and Terminology . . . . . . . . . . . . . . . . . . . . . . . . 25
3.3 Motivation and Context . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.4 A Fast Nashification Algorithm . . . . . . . . . . . . . . . . . . . . . . . 26
3.5 Convergence to a Nash Equilibrium . . . . . . . . . . . . . . . . . . . . 36
4 The Nash Equilibrium Verification Problem 41
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.2 A Nash Equilibrium Verification Algorithm . . . . . . . . . . . . . . . . 41
4.3 Verification of Approximate Nash Equilibria . . . . . . . . . . . . . . . . 45
4.4 A Lower Bound for the Nash Equilibrium Verification Problem . . . . . . 46
vi Contents
5 Parallel Links with Restricted Capacity 59
5.1 Parallel M/M/1-Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.1.2 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.1.3 Optimal Routing and Approximation . . . . . . . . . . . . . . . 60
5.1.4 Nash Equilibria . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.1.5 Generalization . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.2 Related Links with Weight Restriction . . . . . . . . . . . . . . . . . . . 63
5.2.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.2.2 Computation of Nash Equilibrium . . . . . . . . . . . . . . . . . 63
5.2.3 Approximation of Optimum . . . . . . . . . . . . . . . . . . . . 63
5.2.4 Nashification . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
6 Nash Equilibria of Identical Users on Parallel Links 69
6.1 Pure Nash Equilibria . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
6.1.1 Coordination Ratio for Related Links . . . . . . . . . . . . . . . 70
6.1.2 Coordination Ratio for General Latency Functions . . . . . . . . 79
6.1.3 Computation of Pure Nash Equilibrium and Optimal Assignment
for General Latency Functions . . . . . . . . . . . . . . . . . . . 86
6.2 Mixed Nash Equilibria . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
6.2.1 Uniqueness of the Fully Mixed Nash Equilibrium . . . . . . . . . 89
6.2.2 Convex versus Non-convex Latency Functions . . . . . . . . . . 91
6.2.3 Existence of Fully Mixed Nash Equilibrium . . . . . . . . . . . . 91
7 Unrelated Links 97
7.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
7.2 Pure versus Fully Mixed Nash Equilibrium . . . . . . . . . . . . . . . . 98
7.3 Mixed Nash Equilibria of Two Users . . . . . . . . . . . . . . . . . . . . 99
7.4 The Limit of the Fully Mixed Nash Equilibrium Conjecture . . . . . . . . 101
8 Conclusion and Open Questions 103
Publications 105
Bibliography 107
1
Introduction
1.1 Selfishness
If a number of (rational) persons with diverse objectives act in a common environment,
then each of them behaves as to maximize his/her own benefit.
This assumption is both, plausible and observable for a variety of scenarios like com-
munication networks, computer networks, road networks, markets, societies and games.
Independent users of an environment usually have differently directed objectives.
Since their actions interfere, they may prevent each other from reaching their goals –
unintentionally but carelessly. Typically it is not possible for all participants to entirely
achieve their target. But then, what is desirable? One possible answer is to declare the
maximization of the average benefit as the social goal. Another common idea is to aim
at maximizing the welfare of the users which are worst off, that is, the maximization of
the minimal personal benefit among the participants is the social goal. As the users do
not care about the social goal, the situation that appears may be socially undesirable. Two
questions arise immediately:
•How bad can the situation get?
•What can be done about it?
1.2 Strategic Games
From the viewpoint of game theory we may consider settings like the above as strate-
gic multi-player games. Such a game is described by a set of alternative actions (the
strategies) and a payoff function for each player. A player’s payoff may depend on the
21 Introduction
collection of all players’ choices (the outcome of the game). The players independently
try to maximize their payoff. There is no cooperation among them. A fundamental con-
cept for non-cooperative games is that of a Nash equilibrium. A Nash equilibrium is an
outcome of the game such that no player can increase its benefit by unilaterally deviating
from its current strategy. It is hence a stable state: It does not change, if the participants
are allowed to renew their decisions. The most obtruding questions in the analysis of
particular settings are:
•How, if at all, can a Nash equilibrium be computed?
•How far from optimum is the social welfare in a Nash equilibrium state?
•How can the users be forced to attain a socially desirable state, or at least to avoid
socially bad states?
The ratio by which the social benefit in a Nash equilibrium lags behind optimum in the
worst case due to lack of coordination is called coordination ratio or price of anarchy
[47].
Instead of choosing exactly one strategy deterministically, users may rate their strate-
gies by probability distributions. Such a probability distribution is hence called a mixed
strategy. Since users behave selfish, we may expect them to choose their probabilities as
to maximize their expected individual profit. The social goal is defined by the expectation
of the social benefit.
1.3 Routing Games
Selfish routing in networks constitutes a large class of strategic games that draws attention
from various domains. Many applications directly involve networks (e.g. communication
networks or traffic networks). Moreover, networks can serve to model other kinds of
resources. The main focus of this work lies on networks of parallel links. Aside from
scenarios that involve this kind of networks, they purchase their interest as a means of
modeling settings where multiple users share a set of self-contained resources (e.g. ma-
chine scheduling).
In the context of routing networks it is more intuitive to speak of cost instead of
benefit. Cost is negated payoff. To maximize payoff, the cost has to be minimized. In
networks we can think of cost in terms of latency. In correspondence to the last section,
we distinguish between a user’s individual cost, which is minimized by the user, and
social cost, which measures how desirable a routing in the network is from a social point
of view (the smaller the social cost, the more desirable). The strategies of a network user
are its feasible routing paths. In a network of parallel links the strategies correspond to the
links. Each user must send a certain amount of flow through the network. Usage of a link
involves costs for the users in terms of latency. Associated with each link is a function,
the latency function, that depends on the set of users occupying the link and gives the
latency experienced by them. Thus we make two restrictive but reasonable assumptions:
1.4 Related Work 3
•The latency on a link depends only on the set of users routing along this link.
•A link causes the same cost to all users occupying it.
The latency experienced by the user of a path is commonly defined as the sum or as the
maximum, respectively, of latencies of its links. Of course, both definitions coincide for
networks of parallel links.
A major characteristic of a routing model is whether a user’s flow is splittable or
not. We consider only unsplittable flows here which give rise to combinatorial problems,
whereas arbitrarily divisible flows allow the application of continuous mathematics. To
distinguish between both we may speak of discrete routing and continuous routing, re-
spectively.
The set of pure (i.e., deterministic) routings in a discrete routing game is finite. If users
choose mixed strategies, then the outcome of the routing game becomes randomized. We
speak of a mixed routing or a mixed assignment in that case.
1.4 Related Work
The number of publications in the area of strategic games is vast and goes back to the
beginning of the last century (and before). In this section we will only cite the work that
is most relevant for us. For a general introduction to game theory see [60, 65, 66]. An
overview of current issues and applications of game theory is given in [67].
Much of the research in game theory is based in some way on the leading concept of
Nash equilibria. The existence of a mixed Nash equilibrium for any strategic game was
proven in the seminal paper of Nash in 1951 [61]1. The work of Nash entailed a series of
other publications, many of them concerned with refinements of the equilibrium concept
to particular areas.
The research on routing games was originally motivated by the investigation of traffic
networks and transportation planning [83, 6, 7, 12, 20]. Here, the behavior of road users
interacting in a traffic network is modeled in a selfish routing game. Each user is assumed
to choose a path from its start point to its target node that minimizes its experienced
latency. As the number of road users is assumed to be very high, the contribution of a
single user to the total flow is infinitesimal. Equilibrium states of such flows are called
Wardrop equilibria. See [3, 40] for a discussion of the relation between Wardrop and Nash
equilibria. The social cost is commonly defined as the average latency per unit of flow
in this context. We refer to this setting as Wardrop model. Recent work on the Wardrop
model includes [64, 44, 71, 72, 76, 73, 74, 77, 16, 15, 17]. The infinitesimality of user
flows makes this model basically different from the one with indivisible flows which we
consider here. Nevertheless, we will apply some of the ideas of Roughgarden [74] to
discrete routing.
In [12] Braess describes a counterintuitive phenomenon that can appear in traffic net-
works: Inserting an additional link into the network can increase the individual cost of
1Already in 1838 Cournot used a restricted version of a Nash equilibrium.
41 Introduction
every user according to a Nash equilibrium flow. Thus, although an additional link should
intuitively enhance the options for the users, the situation gets worse. This phenomenon
is known as Braess paradox. It can analogously be observed in other domains like a
mechanical network of springs and strings or an electronic circuit of resistors and Zener
diodes [14]. A hydraulic and a thermal analogue is known as well. Unfortunately, it is in
general very difficult to detect such undesirable situations [71].
In 1999 Koutsoupias and Papadimitriou [47] established a field of research we are con-
cerned with in this thesis. They explore a selfish routing game on parallel links. The links
process their traffic at different speeds. Users assign their indivisible flows (determin-
istically or non-deterministically, resulting in pure or mixed assignments, respectively)
to the links. The amount of flow a user has to ship is given by the user’s weight. As
users behave selfish, they aim at minimizing their experienced latency or their expected
latency in case of mixed assignments, respectively. The latency of a link is the sum of
user weights that route along this link (the link’s congestion) over its speed. The social
cost of a pure assignment is the maximal user cost, i.e., the maximal experienced latency.
In case of mixed assignments, the social cost is the expected maximal user cost. We refer
to this model as the KP model. It is (for the deterministic case) equivalent to the clas-
sical machine scheduling problem with uniform machines. Here, machines correspond
to links, jobs to user flows, and makespan to social cost. But whereas the scheduling
problem is a global optimization problem (the goal is makespan minimization), the KP
model involves only local optimizations (each users’ goal is latency minimization). Due
to lack of coordination among the users, the routing arising from selfish user decisions
(that we expect to settle at a Nash equilibrium) can be very bad (in terms of social cost)
compared to a globally optimal one. [47] is the first work to consider this model under
this game theoretic light. Koutsoupias and Papadimitriou introduce the coordination ratio
as a measure for the loss in social quality if users are uncoordinated. More precisely,
they define it as the ratio of the worst social cost of a (mixed) Nash equilibrium over the
optimal social cost. They give tight bounds on the coordination ratio for two parallel links
and asymptotical bounds for more than two links. Their results have been generalized in
different directions.
In [54] Mavronicolas and Spirakis introduce the notion of a fully mixed Nash equi-
librium for the KP model. In such Nash equilibrium each probability is strictly positive.
That is, each user occupies every link with some non-zero probability. They characterize
the existence and non-existence of fully mixed equilibria in the KP model. Furthermore,
they prove asymptotically tight bounds on the coordination ratio of fully mixed Nash
equilibria. They were generalized by Czumaj and Vöcking in [19], who show that the
coordination ratio for the KP model with mlinks is Θ( log m
log log log m). For either identical
links or pure Nash equilibria it becomes Θ( log m
log log m).
Due to Nash it is known that for any strategic game there exists a (mixed) Nash equi-
librium. A pure Nash equilibrium does not necessarily exists. In [29] Fotakis et al. show
that every instance of the KP model possesses a pure Nash equilibrium and present a
greedy algorithm (known as LPT or Graham’s algorithm) to compute it efficiently. On
the other hand they show that computing the best or worst Nash equilibrium is NP-hard.
1.4 Related Work 5
They also give rise to the Fully Mixed Nash Equilibrium Conjecture here which is explic-
itly stated in [35]. It says that for any instance of the KP model, the fully mixed Nash
equilibrium has the worst social cost among all Nash equilibria, provided that it exists.
Fotakis et al. [29] show that the conjecture holds for instances with two users and iden-
tical links. For general instances with identical users they show that the social cost of
any Nash equilibrium is bounded by that of the generalized fully mixed Nash equilibrium
multiplied by a constant. A generalized fully mixed Nash equilibrium is the fully mixed
Nash equilibrium induced by the instance resulting from removing the smallest possible
number of slowest links such that the fully mixed Nash equilibrium exists. Another result
is a randomized FPTAS for the computation of the social cost of a Nash equilibrium on
identical links. In [46] Koutsoupias et al. give an asymptotically tight bound on the co-
ordination ratio of approximate Nash equilibria, a relaxation of ordinary Nash equilibria,
for identical links. Gairing et al. [35] show the Fully Mixed Nash Equilibrium Conjecture
for pure Nash equilibria, that is, the fully mixed Nash equilibrium, if it exits, is worse
than any pure Nash equilibrium in terms of social cost. Furthermore, they show that the
social cost of a fully mixed Nash equilibrium can be computed by a randomized PTAS,
and that it approximates the worst social cost of any Nash equilibrium up to a factor of
(6 + ), both for identical links. On the other hand it is NP-hard to approximate the worst
social cost within a factor of (2 −2
m+1 −)for any > 0.
While a Nash equilibrium is a static state that fulfills certain properties, it has to be
determined by some additional policy how the dynamic process leading to a Nash equi-
librium takes place. Even-Dar et al. [23] and Goldberg [37] investigate the convergence
to a pure Nash equilibrium in the KP model. While [23] yields bounds on the worst case
number of reassignment steps according to different policies, [37] addresses the expected
number of moves until a Nash equilibrium is reached when users are selected by a random
policy. An earlier work on this topic is that of Altman et al. [2], where the case of two
links is considered, and that of Singh et al. [78], where the dynamics of mixed strategies
for bimatrix games with two strategies are explored.
A natural direction of generalization concerns the link latency functions in the KP
model. Recall that in the original KP model the latency on link jis xj
sj, where xjis the
total flow and sjis the speed of link j. In correspondence to the machine scheduling
terminology we speak of related links in this case. Instead, we can allow for more general
latency functions. In [50] Libman and Orda explore a routing model with parallel links
where the latency is an arbitrary non-increasing function of the residual capacity, where
the latter is defined as difference of a links capacity, that is associated with every link, and
the congestion of the link. They discuss existence, uniqueness and convergence issues.
Czumaj, Krysta and Vöcking state bounds on coordination ratio and bicriteria results
for fractional and integral flows on parallel links with monotone cost functions in [18]. In
particular they explore M/M/1-queue latency functions which fit in the model of residual
capacity functions from Libman and Orda.
Gairing et al. address the KP model with restricted links [33]. Here users may only
route along a subset of the links. This set of allowed links is given explicitly for each
user. For the case of equal link speeds they show how any feasible assignment can be
61 Introduction
transformed into a Nash equilibrium without increasing the social cost2. In [79] Suri,
Tóth and Zhou explore restricted links, too. They consider related and identical links but
allow unweighted users, only. Social cost is defined as the sum of user latencies in their
model. They bound the coordination ratio for pure Nash equilibria by 2.5for related links,
and by 2.15 in case of identical links, where a lower bound of 2.001 holds.
In [10] Berenbrink et al. consider the KP model with one modification. Here, social
cost is defined as the average of individual costs. Several upper and lower bounds on
the coordination ratio of pure Nash equilibria and on the ratio of worst and best Nash
equilibrium are established.
Milchtaich explores in [56] a model which is equivalent to routing unweighted users
on parallel links, but where each user has its own latency function for every link. He shows
that for any instance of this model there exists a pure Nash equilibrium and constructs a
sequence of greedy steps with polynomial length that leads to a Nash equilibrium. For
weighted users and two links a pure Nash equilibrium can only exist in general for up to
two users.
Another extension of the KP model is to allow arbitrary network topologies with in-
dividual source-sink pairs instead of parallel links only. If we make one step further in
this direction, we come to what is called a congestion game. Here user strategies can be
arbitrary subsets of the set of resources. The cost for using a resource is a function of its
congestion. A user’s individual cost is the sum of costs of resource the user occupies. A
network congestion routing game is hence a special case of a congestion game for which
a bijective mapping of the links to the resources exists, such that the users’ source-sink
paths correspond to their strategies in the congestion game. Rosenthal showed that any
unweighted congestion game, i.e., a congestion game with unweighted users, has a pure
Nash equilibrium [70]. Libman and Orda gave an example that proves this fact invalid for
weighted users [50], even in network congestion games. Rosenthal’s proof is based on a
potential function. Such a function maps any assignment of users to their strategies on a
real number. Any change of a single user’s strategy that improves the user’s individual
cost decreases the value of the potential function. Monderer and Shapley introduced the
notion of a potential game which is a game possessing a potential function [58]. They
show that potential games have at least one pure Nash equilibrium. See [82, 81, 80] for
further characterizations of potential games. Potential functions are a powerful tool for
proving the existence of pure Nash equilibria. Recently, Fotakis et al. could show that
any weighted network congestion game with linear link latency functions has a pure Nash
equilibrium [30]. Their proof is based on a potential function. Furthermore, they show
that the coordination ratio for pure Nash equilibria of unsplittable flow in layered net-
works where the link latency equals the link congestion is Θ( log m
log log m), where mis the
number of links. Fabrikant et al. explore the complexity of pure Nash equilibria in con-
gestion games [25]. Existence and uniqueness of pure Nash equilibria for strategic games
in general are discussed in [69, 38]. A survey of methods to numerically compute mixed
Nash equilibria can be found in [55].
In markets, customers and providers interact, each as to maximize his/her profit. This
2We will refer back to this process as Nashification later.
1.5 Contribution 7
is another classical area of application for Nash equilibria. See [21, 8] for recent results.
In [24, 4], games are explored where players have to build up network connections or
to establish communication paths, respectively. An obvious motivation for such settings
is to model the evolvement of huge networks that are not centrally controlled, like the
internet.
Another issue, as a consequence of selfish behavior, is that of mechanism design.
How can environments be designed as to make users attain only desirable equilibrium
states? [62] gives a survey on this topic. In [44, 49, 26, 71, 16, 15, 13] mechanism design
for network routing games is discussed under various circumstances. In models that are
explored in this context, users are often allowed to have private information. [63] and [5]
consider the classical scheduling problem (which is basically equivalent to the KP model)
under this aspect.
In [72, 48] Stackelberg strategies for routing infinitesimal users on parallel links are
considered. In a Stackelberg strategy a certain fraction of the flow is controlled centrally
in order to induce good Nash equilibrium states for the remaining users. Both publications
define social cost as the average cost per unit of flow, i.e., as in the Wardrop model, and
give algorithms to compute Stackelberg strategies with guaranteed performance as well
as hardness results. In a similar flavor is the work of Korilis et al. [45] who explore
Stackelberg strategies for parallel M/M/1-queues.
Market equilibria, mechanism design and Stackelberg routing are not a topic of this
work. We do not intend to give an exhaustive overview on this area here but only a starting
point for the interested reader.
1.5 Contribution
Chapters 3 and 4 are concerned with the original KP model. Recall that an instance of
this model defines a set of weighted users and a set of related parallel links. Social cost
is defined as the maximal individual latency experienced by any user, here. By Nashifi-
cation we denote the process of bringing a pure assignment of users to links into a Nash
equilibrium without increasing its social cost.
In Chapter 3 we give an efficient Nashification algorithm for the KP model. It uses at
most (m+ 1)n(not necessarily improving) moves to convert any assignment into Nash
equilibrium, where mis the number of links and nis the number of users. The algorithm
runs in time O(nm). In combination with existing approximation algorithms for the well
studied classical machine scheduling problem which is equivalent, it provides a method
to compute approximate solutions for the NP hard problem of finding the best Nash equi-
librium. In particular we get a PTAS for this problem. Prior to this work, only the LPT
algorithm was known to compute a Nash equilibrium with guaranteed performance of 5
3
(see [39, 31, 29]). If the order according to which users perform moves is not determined
by some policy (like LPT), then we expect them to perform improving moves in an arbi-
trary fashion. We show that the worst case number of moves can be superpolynomial in
this case, even if always the best possible move is made and even for identical links.
The Nash Equilibrium Verification Problem asks for the correct answer to the question
81 Introduction
whether a given (pure) assignment is at Nash equilibrium or not. In Chapter 4 we consider
this problem for the KP model. We determine its exact algebraic complexity to be Θ(n+
mlog m). The upper bound is obtained from an algorithm that we introduce. A matching
lower bound is derived from the theorem of Ben-Or by a chain of Turing reductions that
involve some two-dimensional geometrical problems.
In Chapter 5 we turn our attention to two variants of the KP model with capacitated
links. First, we explore it for links having the latency characteristics of M/M/1-queues.
We prove that an existing PTAS for machine scheduling is a polynomial dual approxima-
tion scheme for routing identical M/M/1-queues. It is known that any assignment can
be turned into a Nash equilibrium with a linear number of greedy steps, if their order is
chosen appropriately. We show that there exist sequences of greedy steps with superpoly-
nomial length. Second, we address the KP model with an additional weight constraint.
That is, we allow users only to route on those links where their weight does not exceed the
weight constraint, given by a single value associated with the link. Here, we observe that
the LPT algorithm computes a Nash equilibrium. We describe how to modify the PTAS
for machine scheduling as to obtain a PTAS for best Nash equilibrium computation in
the KP model with weight constraints. At last we show that the Nashification algorithm
introduced in Chapter 3 is capable of Nashifying any pure assignment in this model as
well.
According to the KP model, the social cost is defined as the maximal individual la-
tency. Hence, the overall quality of a routing is determined by the users that are worst off
as opposed to the Wardrop model, where the social cost is computed as average latency
per infinitesimal unit of flow. The latter definition incorporates all appearing latencies
and weights them by the amount of flow subjected to them. Both concepts are commonly
used. In Chapter 6 we apply the latter definition of social cost to the congestion routing
model on parallel links with unweighted users. We prove a tight bound of 4
3for the coor-
dination ratio of pure Nash equilibria on related links. For arbitrary latency functions and
under very mild conditions, we prove a tight bound on the coordination ratio based on the
anarchy value introduced in [74]. Furthermore, we give an improved algorithm for the
computation of a Nash equilibrium with running time O(n+mlog mlog n). We show
that an optimal assignment can be computed by the same algorithm with a minor modifi-
cation. This result holds for instances with unweighted users and arbitrary non-decreasing
latency functions. Then, we turn our attention to mixed Nash equilibria for this model.
First, we show that the fully mixed Nash equilibrium is unique (for non-constant latency
functions). It is known, that the fully mixed Nash equilibrium, if it exists, yields the
largest social cost for instances with non-decreasing and convex latency functions. We
show that this is not true for non-decreasing and non-convex latency functions, even for
two identical links. Even the individual cost of a user can be larger according to a pure
Nash equilibrium than according to the fully mixed Nash equilibrium. At last we charac-
terize the instances for which the fully mixed Nash equilibrium exists or does not exist.
This allows us to extend the Fully Mixed Nash Equilibrium Conjecture to instances for
which the fully mixed Nash equilibrium does not exist according to its original definition.
In Chapter 7 we examine routing on unrelated parallel links. Here, a link’s latency is
the sum of cost values of the users occupying it. These cost values are explicitly given for
1.5 Contribution 9
every link. Each user has its own vector of cost values. We show that the individual cost
of any user, as well as the social cost, according to any pure Nash equilibrium is bounded
by the corresponding value of the fully mixed Nash equilibrium, provided it exists and
the number of users does not exceed the number of links. Furthermore, for two users,
the individual cost according to any (mixed) Nash equilibrium is bounded by that of the
fully mixed Nash equilibrium, if the latter exists. If additionally we have only two links,
then the social cost of any Nash equilibrium is bounded by that of the fully mixed one, if
it exists, that is, the Fully Mixed Nash Equilibrium Conjecture is valid. Finally, we give
a negative result, namely that the Fully Mixed Nash Equilibrium Conjecture cannot be
valid for more than two users on unrelated links.
The results of Chapters 3, 6 (except for Definition 6.10, Theorem 6.11 and Proposi-
tion 6.12) and 7 have been presented on international computer science conferences and
are published in the conference proceedings (see the list of publications on page 105).
A previous version of the results of Chapter 3 appeared in [27]. Subsection 6.1.1
appeared in [51]. Parts of Subsection 6.1.2 (Definition 6.6 to Corollary 6.9), Subsec-
tion 6.1.3 and Section 6.2 appeared in [34]. Chapter 7 appeared in [52].
10 1 Introduction
2
Preliminaries
Most of the definitions, denotations and terminologies used throughout this work are in-
troduced in this chapter. Some definitions that are specific to only few particular topics
will be stated when they are needed. We summarize all denotations given here in a table
in Section2.6.
2.1 Basic Mathematical Definitions
The set of positive natural numbers is denoted N={1,2,3,...}, while N0={0,1,2, . . . }
is the set of non-negative natural numbers (including zero). For i∈N0we denote
as [i] = {1,...,i}the set of the first ipositive natural numbers. The closed interval
[a, b] = {r∈R|a≤r≤b}is the set of reals non-smaller than aand non-larger than
b. The corresponding open interval is defined as (a, b) = {r∈R|a < r < b}. For a
set M,2Mdenotes the power set of M. For a function F,EX`Y(F(X)) is the expectation
of F(X)with random variable Xdistributed according to Y. For our purposes Xwill
be an assignment A: [n]→[m], and Ya probability matrix P= (pij)∈[0,1]n×m.
If ˜
A: [n]→[m]is a particular assignment, then the probability for Ato attain ˜
Ais
Qi∈[n]pi˜
A(i). For a matrix P∈[0,1]n×m, a vector p= (p1,...,pm),pT∈[0,1]m, and a
natural number i∈[n]we denote as P|ipthe matrix resulting from P, if the ith row of P
is replaced by p. For a natural number j∈[m],P|ijdenotes the matrix where all entries
of the ith row of Pare set to zero except for the entry in the jth column which is set to
1. For a mapping A: [n]→[m]and natural numbers i∈[n], j ∈[m],A|ijdenotes the
mapping resulting from Aif A(i)is set to j. To avoid the excessive use of brackets, we
abide with the following convention. The scope of a sum array ranges to the next addition
or subtraction operator. The scope of a product array covers only the operand following
12 2 Preliminaries
the product symbol. That is, PPA·B+Cis to be read as P(P(A·B)) + C, and
QA·Bas (QA)·B.
2.2 Routing Models
In this work we consider routing networks of parallel links. The number of links is de-
noted as m. Non-cooperative users wish to send traffic from a common source to a com-
mon destination that are connected by the links. The number of users is denoted as n.
We assume that links and users are numbered by 1,...,mand 1, . . . , n, respectively, and
identify the links and users by their indices. Hence we may denote the set of links as [m]
and the set of users as [n]. In this context 2[n]refers to the set of all subsets of the users.
All users that route their traffic along a certain link j∈[m]experience the same cost
in terms of latency which is given by the link’s latency function lj.
2.2.1 Generic Model
In the most general model the latency function is of the form lj: 2[n]→R≥0. That is,
for any subset U⊆[n]of users, lj(U)is the latency on link jif exactly the users in U
route along link j. An instance of this generic routing model is given by I= (l), where
l= (l1,...,lm)is the vector of latency functions.
2.2.2 Subclasses
We consider two different subclasses of this general model.
1. In the unrelated routing model the latency function on link j∈[m]is defined by
lj(U) = Pi∈Ucij, where C= (cij)i∈[n]
j∈[m]
is the cost matrix that defines for each user
iand link jthe contribution of user ito the latency on link jwhen user iroutes its
flow along link j. An instance of this model is denoted I= (C).
2. The second subclass is the congestion routing model. Here the latency of any link
jdepends only on the total flow on the link. The users may contribute differently
to the flow on the link they occupy which is reflected in their weights. The weight
of user i∈[n]is denoted wi. Sometimes wiis called the flow controlled by user i
or simply the traffic of user i. We combine all user weights into the vector of user
weights w= (w1,...,wn). Furthermore, we denote as W=Pi∈[n]withe total
weight. If Uis the subset of users that route along link j, then the total flow on link
jis Pi∈Uwi. The total flow on a link is also called the link’s congestion. Since
in the congestion routing model the latency of any link jonly depends on the total
flow on that link, we may define the latency function of link jas lj:R≥0→R≥0.
That is, if xis the congestion on link j, then the latency of link jis given by lj(x).
An instance of the congestion routing model is denoted as I= (w,l). Further
restricting the set of instances yields subclasses of the congestion routing model.
The following subclasses will be of interest in this work.
2.3 Pure Assignments 13
a) The congestion routing model with identical users. Here all users control the
same amount of flow. Without loss of generality we may assume this amount
to be 1. An instance of this model is given by I= (n, l). As a link’s congestion
can only attain integral values in this case, the latency functions have the form
lj:N0→R≥0.
b) The congestion routing model with related links. Here the latency function of
link j∈[m]is given by lj(x) = x
sj, where sj>0is the speed of link j. We
combine the speeds into the vector of link speeds s= (s1, . . . , sm)and denote
an instance of this model as I= (w,s). Note that this model can just as well
be seen as a subcase of the unrelated routing model by defining the entries of
the cost matrix as cij =wi
sjfor all i∈[n], j ∈[m]. This model is also known
as KP model.
We will consider two other models in Chapter 5, the routing model with parallel
M/M/1-links and the KP model with weight constraints. An instance of the former
is denoted as I= (w,c), an instance of the latter as I= (w,s,u). They will be
defined in the corresponding sections.
2.3 Pure Assignments
For an instance of any of the models, a routing is an assignment of users to links, denoted
A. That is, Ais a mapping of the form A: [n]→[m]that gives for each user i∈[n]the
link A(i)where the user’s traffic is routed. For distinction, we call this kind of assignment
pure assignment, as opposed to mixed assignments that will be introduced in the next
section.
Given a particular routing Afor an instance Iof the congestion routing model (or one
of its subcases) with user weight vector w, we can compute the link congestions. For any
link j∈[m]the congestion caused by routing Ais xj(A) = Pi∈[n]
A(i)=j
wi. The individual
cost or user cost of user iaccording to routing Afor instance I, denoted λi(A, I), is the
latency on the link to which user iis assigned by A. Thus, λi(A, I) = lA(i)(xj(A)) for the
congestion routing model. For an instance Iof the unrelated routing model the individual
cost of user iis λi(A, I) = Pk∈[n]
A(k)=A(i)cij.
For a (partial) pure assignment A:U→[m], with U⊆[n], we define view(j, A) =
{i∈U|A(i) = j}for j∈[m]. Note that Uis given implicitly by the definition of A.
Sometimes we will need to express the individual cost of a particular user iwhen all
users except for user iitself are assigned according to a given assignment Aand user
igoes to a given link j. We may denote the individual cost for user ias λi(A|ij, I)
in this case. Thus, for an instance Iof the congestion routing model λi(A|ij, I) =
lj(wi+Pk∈[n]\{i}
A(k)=j
wk), and for an instance Iof the unrelated routing model λi(A|ij, I) =
cij +Pk∈[n]\{i}
A(k)=j
ckj.
The overall quality of a routing Afor an instance Iis measured by the social cost,
denoted SC(A, I), as opposed to the individual cost.
14 2 Preliminaries
The following three definitions of social cost are common. We use superscripts to
explicitly distinguish between them.
1. SCSUM (I, A) = Pi∈[n]λi(A, I). In this case social cost is proportional (by fac-
tor n) to the average individual cost where all users contribute in equal measure
regardless of their weights.
2. SCMAX(I, A) = maxi∈[n]λi(A, I). This definition focuses on the user for which
routing is most costly.
3. SCAV G(I, A) = Pi∈[n]wiλi(A, I). This definition is used for the congestion rout-
ing model (it requires user weights). Here social cost is the weighted (by user
weights) sum of individual costs. Put in other words, it is proportional (by fac-
tor W) to the average cost per unit of flow (the average cost of one flow unit is
Pi∈[n]wiλi(A, I)/W).
The results of this work involve the last two definitions of social cost. Note that in
case of identical users the third definition coincides with the first definition.
2.4 Mixed Assignments
Under the light of non-cooperative game theory, a routing A, as introduced in the last
section, is a collection of user decisions. The set of links corresponds to the set of allowed
choices (or strategies) for any user. As long as the user decisions are deterministic, a state
of this "routing game" is completely described by A. The general definition of a strategic
game allows for non-deterministic user choices. That is, users may rate their strategies –
here the links – by a probability distribution rather than choosing exactly one of them. We
combine all those probabilities into a matrix P= (pij)which we call a mixed assignment.
That is, the flow of user iis routed via link jwith probability pij for any i∈[n], j ∈[m].
Thus, pij ∈[0,1] for all i∈[n], j ∈[m]and Pj∈[m]pij = 1 for all i∈[n].
We define link congestion, link latency, individual cost and social cost according to a
mixed assignment Pas the expectation of the respective value for pure assignment A, if A
is probability distributed according to P. That is, xj(P) = EA`P(xj(A)) is the (expected)
flow or congestion on link jaccording to Pfor j∈[m], where A`Pmeans that the
expectation is over all assignments Adistributed randomly according to P.
In the same way we get lj(P, I) = EA`P(lj(A, I)) for the link latency on link j∈
[m],λi(P) = EA`P(λj(A)) for the individual cost of user i∈[n]and SC(P, I) =
EA`P(SC(A, I)) for the social cost. Note that the last statement applies to all three defi-
nitions of social cost. That is, SCSUM (P, I) = EA`P(SCSUM (A, I)),SCMAX(P, I) =
EA`P(SCMAX (A, I)) and SCAV G(P, I) = EA`P(SCAV G(A, I)).
Similarly to the deterministic case, λi(P|ip) = EA`(P|ip)(λj(A)) is the (expected)
individual cost of user iaccording to a mixed assignment that is given by (P|ip), the
matrix where the ith row of Pis replaced by p= (p1,...,pm), a probability distribution
over mlinks, that is, pj∈[0,1] for all j∈[m]and Pj∈[m]pj= 1. Furthermore,
2.5 Optimum, Nash equilibrium and Coordination Ratio 15
λi(P|ij) = EA`(P|ij)(λj(A)) is the (expected) individual cost of user iaccording to P,
but with user igoing to link jfor sure, i.e., P|ijis the matrix resulting from Pif the
entries of the ith row are all set to zero except for the jth entry which is set to one.
For any mixed assignment Pwe define the support of user i∈[n]by support(i, P) =
{j∈[m]|pij >0}(the set of links chosen by user iwith positive probability) and the
view of link j∈[m]by view(j, P) = {i∈[n]|pij >0}(the set of users that choose link
jwith positive probability).
We call a mixed assignment Pfully mixed, if it describes a routing where each user
chooses every link with positive probability. That is, support(i, P) = [m]for all users
i∈[n]in a fully mixed assignment.
Note that a pure assignment Ais just a special case of a mixed assignment P, where
for all i∈[n], j ∈[m],pij = 1 if A(i) = j, and pij = 0 if A(i)6=j. Hence, every pure
assignment can be described by a probability matrix with entries one and zero. But it will
be more convenient to characterize a pure assignment by a mapping of users to links.
A fully mixed assignment and a pure assignment are hence two oppositional extreme
formations of a mixed assignment.
2.5 Optimum, Nash equilibrium and Coordination
Ratio
For an instance Iof a routing model, OPT(I) = minA:[n]→[m]SC(A, I)is the optimal so-
cial cost. We use OPT MAX(I)or OPT AV G(I)to explicitly refer to one of the definitions
of social cost, if the reference is not clear from the context. Note that the minimization
is over all pure assignments, since there always exists a pure assignment with minimal
social cost among all (mixed) assignments. The next definition formalizes this property.
In general, an assignment is at Nash equilibrium, if no user can decrease its individual
cost by unilaterally changing its strategy.
Definition 2.1. A mixed assignment Pfor an instance Iof a routing model is at Nash
equilibrium, if and only if for all users i∈[n]and all probability distributions p, that is
p∈[0,1]mand Pj∈[m]pj= 1,
λi(P, I)≤λi(P|ip, I).
Sometimes we simply say that Pis a Nash equilibrium to express that Pis an assign-
ment at Nash equilibrium. Note that Definition 2.1 applies to fully mixed assignments and
pure assignments as well, since both are particular mixed assignments. To explicitly refer
to a pure assignment Athat is at Nash equilibrium, we call Aa pure Nash equilibrium.
Similar, we call Fa fully mixed Nash equilibrium, to express that Fis a fully mixed
assignment at Nash equilibrium.
We denote as N(I) = {A: [n]→[m]|Ais at Nash equilibrium}the set of pure
Nash equilibrium assignments for instance I, and as M(I) = {P∈[0,1]n×m| ∀i∈
[n] : Pj∈[m]pij = 1,and Pis at Nash equilibrium}the set of (mixed) Nash equilibria
for instance I.
16 2 Preliminaries
The coordination ratio (also called price of anarchy) gives the loss in quality (in terms
of social cost) of a routing due to lack of coordination. For an instance Iof a routing
model, we define the coordination ratio CR(I)of Ias CR(I) = supP∈M(I)
SC(P,I)
OP T (I). The
coordination ratio of a routing model is the supremum of the coordination ratios of all its
instances, that is, if Sis the set of all instances of the routing model under consideration,
then supI∈SCR(I)is the coordination ratio of the routing model. Many a time we restrict
our considerations only to pure Nash equilibria. In that case coordination ratio refers to the
pure coordination ratio PCR(I) = maxA∈N(I)SC(A,I)
OP T (I)when applied to a single instance.
The pure coordination ratio of a routing model is again the supremum of PCR(I)among
all instances Iof the model.
2.6 Summary of Notations
The following list summarizes all our denotations introduced so far.
Denotation Definition Description
m∈Nnumber of links
n∈Nnumber of users
[m] = {1,...,m}set of links
[n] = {1,...,n}set of users
2[n]={U⊆[n]}set of all user subsets
wi∈R≥0weight or traffic or flow of user i
w= (w1,...,wm)vector of user flows
W=Pi∈[n]witotal weight or total flow
ljlatency function of link jin the
a) : 2[n]→R≥0a) general routing model
b) :R≥0→R≥0b) congestion routing model
c) :N≥0→R≥0c) congestion routing model with identical users
sj∈R>0speed of link j(for related links)
s= (s1,...,sm)vector of link speeds
l= (l1,...,lm)vector of link latency functions
lj(x) = x
sjlatency function j(for related links)
cij ∈R≥0cost contribution of user ion link j
C∈Rn×m
≥0cost matrix (unrelated routing model)
lj(U) = Pi∈Ucij latency function j(for unrelated links)
Iinstance of the
a) = (l)a) generic routing model
b) = (w,l)b) congestion routing model
c) = (n, l)c) congestion routing model with identical users
d) = (w,s)d) congestion routing model with related links
e) = (C)e) unrelated routing model
f) = (w,c)f) routing model with M/M/1-links
g) = (w,s,u)g) KP model with weight constraints
2.7 Relations and Expressions 17
Denotation Definition Description
pij ∈[0,1] probability for user ito go on link j
P= (pij)i,j ∈[0,1]n×mmixed assignment
A: [n]→[m]pure assignment
xj(A, I) = PA(i)=jwicongestion on link jaccording to A
xj(P, I) = EA`P(xj(A, I)) (expected) congestion on link jaccording to P
λi(A, I)individual cost of user iaccording to A
λi(P, I) = EA`P(λj(A, I)) (expected) individual cost of user i
λi(A|ij, I)individual cost of user i, if user igoes to link j
and all other users are assigned according to A
λi(P|ip, I) = EA`(P|p)(λj(A, I)) (expected) individual cost of user i, if the
probability distribution of user iis pand
that of all other users is given by P
λi(P|ij, I)(expected) individual cost of user i, if user i
goes to link j(for sure) and the probability
distributions of all other users are given by P
support(i, P) = {j∈[m]|pij >0}supported links of user i
view(j, P) = {i∈[n]|pij >0}view of link j
view(j, A) = {i∈[n]|A(i) = j}set of users that choose link j
SCSUM (A, I) = Piλi(A, I)social cost of A(1st definition)
SCMAX (A, I) = maxiλi(A, I)social cost of A(2nd definition)
SCAV G(A, I) = Piwiλi(A, I)social cost of A(3rd definition)
SCXXX(P, I) = EA`P(SCXXX(A, I)social cost of (mixed) assignment P,
where XXX ∈ {SUM, MAX, AV G}
OPT(I) = minA:[n]→[m]SC(A, I)optimal social cost according to
respective definition of social cost
N(I)set of pure Nash equilibria for I
M(I)set of mixed Nash equilibria for I
CR(I) = maxP∈M(I)SC(P,I)
OP T (I)coordination ratio of instance I
PCR(I) = maxA∈N(I)SC(A,I)
OP T (I)pure coordination ratio of instance I
2.7 Relations and Expressions
Many of the measures defined above can be expressed in several ways. It is often con-
venient to start from some particular expression in oder to simplify the calculations. We
will now have a closer look to the different routing models and concretize the respective
definitions.
18 2 Preliminaries
2.7.1 The Generic Routing Model
2.7.1.1 Individual Cost
We start with a simple but useful lemma on the individual cost in the generic routing
model.
Lemma 2.2. Let P∈Rn×mbe a mixed assignment for an instance I= (l)of the generic
routing model. Then, the individual cost of user i∈[n]according to Pis
λi(P, I) = X
j∈[m]
pijλi(P|ij, I).
Proof. It is
λi(P, I) = EA`P(λi(A, I))
=X
A:[n]→[m]Y
k∈[n]
pkA(k)λi(A, I)
=X
j∈[m]X
A:[n]\{i}→[m]
pij Y
k∈[n]\{i}
pkA(k)lj(view(j, A)∪{i})
=X
j∈[m]
pij X
A:[n]\{i}→[m]Y
k∈[n]\{i}
pkA(k)λi(A|ij, I)
=X
j∈[m]
pijEA`P|ij(λi(A, I))
=X
j∈[m]
pijλi(P|ij, I).
The following lemma gives an alternative way to express a user’s individual cost ac-
cording to a mixed assignment. We will use it in Chapter 6 for instances of the congestion
routing model.
Lemma 2.3. Let Pbe a mixed assignment for an instance I= (l)of the generic routing
model. Then the expected individual cost for user i∈[n]when going to link j∈[m]is
λi(P|ij) = X
U⊆[n]\{i}Y
k∈U
pkj Y
k∈[n]\(U∪{i})
(1 −pkj)·lj(U∪{i}).
Proof. We first prove the following.
Claim: For any V⊆[n]\{i}
λi(P|ij) = X
A:¯
V→[m]hY
k∈¯
V
pkA(k)X
U⊆VY
k∈U
pkj Y
k∈V\U)
(1 −pkj)
lj({k∈¯
V|A(k) = j}∪U∪{i})i,
2.7 Relations and Expressions 19
where ¯
V= [n]\{i}\Vis the inverse set of V.
Proof: We have
λi(P|ij) = EA`P|ij(λi(A, I))
=X
A:[n]\{i}→[m]Y
k∈[n]\{i}
pkA(k)lj({k∈[n]\{i} | A(k) = j}∪{i})
which yields the claim for V=∅. Now assume the claim is true for some V([n]\{i}.
Let r∈¯
Vbe arbitrary. Then,
λi(P|ij) = X
A:¯
V→[m]hY
k∈¯
V
pkA(k)X
U⊆VY
k∈U
pkj Y
k∈V\U
(1 −pkj)
lj({k∈¯
V|A(k) = j}∪U∪{i})i
=prj X
A:¯
V\{r}→[m]hY
k∈¯
V\{r}
pkA(k)X
U⊆VY
k∈U
pkj Y
k∈V\U
(1 −pkj)
lj({k∈¯
V\{r} | A(k) = j}∪U∪{i, r})i
+X
t∈[m]\{j}hprt X
A:¯
V\{r}→[m]Y
k∈¯
V\{r}
pkA(k)X
U⊆VY
k∈U
pkj
Y
k∈V\U
(1 −pkj)lj({k∈¯
V\{r} | A(k) = j}∪U∪{i})i
=X
A:¯
V\{r}→[m]hY
k∈¯
V\{r}
pkA(k)X
U⊆VY
k∈U
pkj Y
k∈V\U
(1 −pkj)
[prjlj({k∈¯
V\{r} | A(k) = j}∪U∪{i, r})
+ (1 −prj)lj({k∈¯
V\{r} | A(k) = j}∪U∪{i})]i
=X
A:¯
V\{r}→[m]hY
k∈¯
V\{r}
pkA(k)X
U⊆(V∪{r})Y
k∈U
pkj
Y
k∈(V∪{r})\U
(1 −pkj)lj({k∈¯
V\{r} | A(k) = j}∪U∪{i})i.
Hence the claim holds for V0=V∪ {r}. By induction the claim follows for any V⊆
[n]\{i}. This completes the proof of the claim.
Now use the claim with V= [n]\{i}. This yields the lemma.
2.7.1.2 Nash Equilibrium Condition
In a Nash equilibrium P, each user ichooses a probability distribution (the ith row of P)
which minimizes its expected individual cost. This yields the following lemma.
20 2 Preliminaries
Lemma 2.4. A mixed assignment Pfor an instance I= (l)of the generic routing model
is at Nash equilibrium, if and only if for each user iand for all links j∈support(i)
λi(P|ij, I) = min
k∈[m]λi(P|ik, I).(2.1)
Proof. Definition 2.1 yields that Pis at Nash equilibrium, exactly if for each user iand
all probability distributions p= (p1,...,pm)for user iit holds λi(P, I)≤λi(P|ip, I).
Hence, in any Nash equilibrium P, the ith row of Pmust be such that λi(P, I)is minimal.
From Lemma 2.2 we get that
λi(P, I) = X
j∈[m]
pijλi(P|ij, I).
In order to minimize λi(P, I), only those entries pij of the ith row of Pcan be positive,
for which λi(P|ij, I)is minimal. The Nash equilibrium condition is therefore equivalent
to
pij >0⇒λi(P|j, I) = min
k∈[m]λi(P|k, I)
for all users i∈[n]and links j∈[m], which yields the claim.
2.7.1.3 Social Cost
The social cost of a pure assignment Afor an instance Iof the generic routing model,
according to the definition of SCSUM and SCMAX, can be alternatively computed as
follows.
SCSUM (I, A) = X
j∈[m]
lj(view(j, A))|view(j, A)|and
SCMAX (I, A) = max
j∈[m]
view(j)6=∅
lj(view(j, A)) .
2.7.2 The Unrelated Routing Model
For an instance of the unrelated routing model we can refine the definition of individual
cost.
Lemma 2.5. Let P∈Rn×mbe a mixed assignment for an instance I= (C)of the
unrelated routing model. Then, the individual cost of user i∈[n]according to Pis
λi(P, I) = X
j∈[m]
pij
cij +X
k∈[n]
k6=i
pkjckj
.
Proof. First note that for any subset U⊆[n]of users
X
A:U→[m]Y
k∈U
pkA(k)= 1 .(2.2)
2.7 Relations and Expressions 21
It is
λi(P|ij, I) = EA`P|ij(λi(A, I))
=X
A:[n]\{i}→[m]Y
k∈[n]\{i}
pkA(k)
cij +X
k∈[n]\{i}
A(k)=j
ckj
=cij X
A:[n]\{i}→[m]Y
k∈[n]\{i}
pkA(k)
+X
A:[n]\{i}→[m]Y
k∈[n]\{i}
pkA(k)X
k∈[n]\{i}
A(k)=j
ckj
=cij +X
A:[n]\{i}→[m]Y
k∈[n]\{i}
pkA(k)X
k∈[n]\{i}
A(k)=j
ckj ,
Claim: For any subset of users U⊆[n]\{i}with inverse set ¯
U= [n]\{i}\U
λi(P|ij, I) = cij +X
k∈U
pkjckj +X
A:¯
U→[m]Y
k∈¯
U
pkA(k)X
k∈¯
U
A(k)=j
ckj .
Proof: For U=∅the claim is obvious. Now fix U⊆[n]\{i}and assume that the claim
holds for this U. We will prove that it holds for V=U∪{r} ⊆ [n]\{i}in place of U
for any r∈¯
U. The claim then follows by induction. So, let r∈¯
Ube arbitrary, and set
V=U∪{r}. Let ¯
V= [n]\{i}\Vbe the inverse set of V. We have
X
A:¯
U→[m]Y
k∈¯
U
pkA(k)X
k∈¯
U
A(k)=j
ckj
=X
t∈[m]X
A:¯
U\{r}→[m]
prt Y
k∈¯
U\{r}
pkA(k)
X
k∈¯
U\{r}
A(k)=j
ckj +(crj t=j
0t6=j
=X
A:¯
U\{r}→[m]
prj Y
k∈¯
U\{r}
pkA(k)
X
k∈¯
U\{r}
A(k)=j
ckj +crj
+X
t∈[m]\{j}X
A:¯
U\{r}→[m]
prt Y
k∈¯
U\{r}
pkA(k)X
k∈¯
U\{r}
A(k)=j
ckj
22 2 Preliminaries
=prjcrj X
A:¯
U\{r}→[m]Y
k∈¯
U\{r}
pkA(k)
+prj X
A:¯
U\{r}→[m]Y
k∈¯
U\{r}
pkA(k)X
k∈¯
U\{r}
A(k)=j
ckj
+X
t∈[m]\{j}
prt X
A:¯
U\{r}→[m]Y
k∈¯
U\{r}
pkA(k)X
k∈¯
U\{r}
A(k)=j
ckj
=prjcrj +X
A:¯
U\{r}→[m]Y
k∈¯
U\{r}
pkA(k)X
k∈¯
U\{r}
A(k)=j
ckj .
Note that the last equality is due to (2.2) and
X
t∈[m]\{j}
prt = 1 −prj .
Hence,
λi(P|i, I) = cij +X
k∈V
pkjckj +X
A:¯
V→[m]Y
k∈¯
V
pkA(k)X
k∈¯
V
A(k)=j
ckj
which completes the proof of the claim.
Applying the claim with U= [n]\{i}yields
λi(P|ij, I) = cij +X
k∈[n]\{i}
pkjckj .
Together with Lemma 2.2 this proves the lemma.
2.7.3 The Congestion Routing Model
2.7.3.1 Social Cost
We will make use of two different definitions of social cost for the congestion routing
model. In Chapters 3, 4, 7 and 5 it will be defined as SCMAX , whereas in Chapter 6 we
will define social cost as SCAV G. There is a great difference in handling the social cost
according to both definitions. In the first case, the social cost of a mixed assignment is the
expectation of the maximum of some expression. The expectation involves a summation
that must not be exchanged with the computation of the maximum. This makes the first
definition quite intractable. The congestion routing model with related links together
with this definition of social cost is also known as KP model, since it was first examined
by Koutsoupias and Papadimitriou [47] in the context of non-cooperative routing. The
second definition allows to significantly simplify the calculation of social cost, as the
following lemma shows.
2.7 Relations and Expressions 23
Lemma 2.6. Let Pbe a mixed assignment for an instance I= (w,l)of the congestion
routing model. Then,
SCAV G(P, I) = X
i∈[n]
wiλi(P, I).
Proof.
SCAV G(P, I) = EA`P(SCAV G(A, I)) = EA`P(X
i∈[n]
wiλi(A, I))
=X
i∈[n]
wiEA`P(λi(A, I)) = X
i∈[n]
wiλi(P, I).
For instances Iof the congestion routing model the social cost of a pure assignment
A, according to the definition of SCAV G, can be calculated by summing up over all links
instead of summing up the weighted user costs. That is,
SCAV G(I, A) = X
j∈[m]
xj(A)lj(xj(A)) .
We will use this relation in Chapter 6.
2.7.3.2 Related Links
In case of related links, the definitions of individual cost and social cost simplify as fol-
lows.
The individual cost of user i∈[n]according to a pure assignment Afor an instance
I= (w,s)is
λi(A, I) = Pk∈[n]
A(k)=A(i)wk
sA(i)
=xA(i)
sA(i)
.
As related links are a special case of unrelated links, we can use Lemma 2.5 with cij =wi
sj
for i∈[n], j ∈[m]to get that
λi(P, I) = X
j∈[m]
pij
wi+Pk∈[n]
k6=ipkjwi
sj
for a mixed assignment P. The social cost of P, according to the definition of SCAV G
and using Lemma 2.6 is hence
SCAV G(P, I) = X
i∈[n]X
j∈[m]
pij
w2
i+wiPk∈[n]
k6=ipkjwi
sj
.
24 2 Preliminaries
2.8 Remark
Throughout this work we will sometimes leave out arguments and super- or subscripts
when this increases readability and if it does not lead to ambiguity. For instance, λi(A)
is short for λi(A, I), and SC(A)can mean SCAV G(A, I)or SCMAX (A, I)which will be
clear from the context.
3
Nashification
3.1 Introduction
In this chapter we consider the problem of converting a given pure assignment for an
instance of the KP model into a Nash equilibrium without increasing the social cost. We
denote this kind of transformation as Nashification.
We will give a polynomial time algorithm for Nashification in Section 3.4. In Sec-
tion 3.5 we show that it may take a superpolynomial number of steps to transform an
assignment into a Nash equilibrium by successively performing best moves on the users,
if the order of moves is chosen arbitrarily.
3.2 Definitions and Terminology
The results in this chapter concern pure assignments in the original KP model. That is,
we consider weighted users on related links, and the social cost is defined as the maximal
user cost or equivalently as the maximal link latency.
Let Abe a pure assignment for an instance of the KP model. An algorithm that, given
Aand the instance as input, computes an assignment A0with SCMAX (A0)≤SCMAX (A)
and such that A0is at Nash equilibrium is said to Nashify A.
In a selfish step or selfish move one user is reassigned to a new link such that the
latency of that user decreases. A greedy step is the special case of a selfish step where
a user is reassigned to one of its best links. That is, a greedy step leads to the lowest
individual cost for that user among all selfish steps. A user is said to be satisfied if no
selfish step is possible for this user. An assignment is at Nash equilibrium, if and only if
all users are satisfied.
26 3 Nashification
3.3 Motivation and Context
Provided that the nuser flows and the mlink speeds are given in sorted order our Nashifi-
cation algorithm Nashify in Figure 3.1 computes a Nash equilibrium in time O(nm)
when started on an arbitrary pure assignment. Thus, we provide another algoritm besides
the LPT algorithm (sometimes called Graham’s algorithm) [39, 29] to compute a pure
Nash equilibrium for any instance of the KP model.
On the other hand, and more important, our algorithm can be used to compute a Nash
equilibrium of any desired quality, by starting it on a correspondingly good initial assign-
ment. Such an initial assignment can be computed using an approximation algorithm for
job scheduling on related machines which is equivalent to our model.
In [32] Friesen and Langston give such an algorithm with approximation ratio at most
1.4which runs in time O(nm). The approximation ratio of the LPT algorithm is at most
1.67 but at least 1.52 [31]. In [42] Hochbaum and Shmoys give a polynomial time approx-
imation scheme (PTAS) for the scheduling problem. Hence, combining their algorithm
with ours, we get a PTAS for the problem of computing the best Nash equilibrium. As
computing the best Nash equilibrium is known to be NP-hard in the strong sense [29],
there cannot exist a fully polynomial time approximation scheme (FPTAS) for this prob-
lem, unless P=NP.
3.4 A Fast Nashification Algorithm
Figure 3.1 shows our Nashification algorithm. A crucial observation for proving the cor-
rectness of the algorithm is stated by the following lemma.
Lemma 3.1. Let Abe any pure assignment. Assume some user iperforms a greedy move
from its current link j=A(i)to some link kwith sj≤sk, yielding a new assignment A0
with A0(i) = k. Then, λr(A) = mint∈[m]λr(A|rt)implies λr(A0) = mint∈[m]λr(A0|rt)
for any r∈[n]with wr≥wi.
Proof. Let the assumptions of the lemma hold and consider any user rwith wr≥wiand
λr(A) = mint∈[m]λr(A|rt). Let user rbe located on link s=A(r). Assume by way of
contradiction, that there exists some link twith λr(A0)> λr(A0|rt). Only the traffic on
link jand kchanges (it is decreased on link jand increased on link k) due to the move of
user i. This implies s=kor t=j.
Assume first, that s6=k(and therefore t=j). We have
xs(A)
ss
=λr(A)≤λr(A|rk) = xk(A) + wr
sk
.
User iimproves by moving to link k, thus
xk(A) + wi
sk
=λi(A0)< λi(A) = xj(A)
sj
,
3.4 A Fast Nashification Algorithm 27
and we get
λr(A0|rt) = xj(A)−wi+wr
sj
>xk(A) + wi
sk
+wr−wi
sj
≥xs(A)
ss−wr
sk
+wi
sk
+wr−wi
sj
=xs(A)
ss
+ (wr−wi)( 1
sj−1
sk
)≥xs(A)
ss
=xs(A0)
ss
=λr(A0),
a contradiction.
Now assume s=k. First note that
λr(A0|rj) = xj(A)−wi+wr
sj≥xj(A)
sj
=λi(A)> λi(A0) = xk(A) + wi
sk
=λr(A0)
implies t6=j.
Since user iperforms a greedy step, we have
xt(A) + wi
st≥xk(A) + wi
sk
,
and hence
λr(A0|rt) = xt(A) + wr
st≥xt(A) + wi
st≥xk(A) + wi
sk
=λr(A0),
a contradiction.
Put in other words, Lemma 3.1 claims that a greedy move of some user from its current
link to a non-slower link cannot cause any non-smaller user to become unsatisfied. For
the special case of identical links, every move is a move to a non-slower link. This implies
that any greedy move of some user does not unsatisfy any user with larger or equal traffic.
Thus, by successively moving each user to its best link in order of non-increasing traffic
sizes, we end up in a Nash Equilibrium. As greedy steps do not increase the social cost,
this algorithm Nashifies any pure assignment on identical links in nsteps [35, 23].
With algorithm Nashify in Figure 3.1 this idea is generalized to non-identical links.
The input to the algorithm consists of the user flows, the link speeds and a pure assignment
A. User flows and link speeds are supposed to be sorted non-increasingly.
The algorithm works in two phases. At every time, A(i)denotes the link user iis
currently assigned to. Whenever user iis moved, A(i)has to be updated which is not
explicitly mentioned in the pseudocode.
The main idea is to accumulate users with small traffic on slow links in a special
way in the first phase (without increasing the social cost) and to perform greedy steps for
unsatisfied users in the second phase.
We may assume that the overall flow on each link is computed as a first step (in time
O(n+m)) and updated whenever it changes (in constant time). Then, setting Mto the
28 3 Nashification
Nashify(I,A)
Input: instance Iof the routing model
with sorted users and links
initial assignment A
Output: equilibrium assignment Awith
non-increased social cost
// phase 1:
01 M:= SCMAX(A);
02 S:= {n};
03 mini(A(n)) := n;
04 repeat
// begin of sweep
05 i:= n;
06 j:= m;
07 while i∈Sdo
08 if j > A(i)and user ifits on link j
without exceeding latency Mthen
09 put user ion link j;
10 mini(j) := i;
11 i:= i−1;
12 else if j > A(i)then
13 j:= j−1;
14 else i:= mini(A(i)) −1;
// end of sweep
15 if i≥1then
16 put user ion link with smallest index
without exceeding latency M;
17 if A(i)≤A(i+ 1) then
18 S:= S∪{i};
19 mini(A(i)) := i;
20 else i:= 0;
21 until i < 1
// phase 2:
22 while S6=∅do
23 i:= min(S);
24 make greedy move for user i;
25 S:= S\{i};
Figure 3.1: Algorithm Nashify computes a Nash equilibrium for any instance I= (w,s)
of the KP model and assignment Awithout increasing the social cost. Users
and links must be sorted so that user flows and link speeds are ordered non-
increasingly, i.e., w1≥ ··· ≥ wnand s1≥ ··· ≥ sm.
3.4 A Fast Nashification Algorithm 29
social cost of the initial assignment which is the first step of phase 1 (line 01) takes time
O(m).
The set Sis used during the first phase to collect all those users that have already
been considered and for which certain conditions ((ii) and (iii) of Lemma 3.2) have been
established. These conditions will be explained later. For the time being, just let us remark
that they are fulfilled trivially for S={n}(line 02).
The array mini() is used during the first phase to store for each link the smallest index
of a user located on that link and contained in S. If no such user exists, then the entry of
mini() for that link is undefined. That is, for j∈[m]
mini(j) = (min(S∩view(j)) if S ∩view(j)6=∅
undefined otherwise .(3.1)
We denote a complete execution of lines 05-14 (until the while-loop is finished) a sweep.
During a sweep each user in Sis put on the link with highest possible index it fits on
without increasing the latency on that link (and hence the social cost) beyond M(the
initial social cost). The users are taken up in reverse order of there indices, always starting
with user n.
After a sweep, ipoints to the user with highest index among all users which are not
contained in S. If i= 0 at this point, then all users are in Swhich causes the algorithm
to leave the first phase (line 21). Otherwise the current user is reassigned to the link with
smallest index it fits on without increasing the social cost beyond M(line 16). This can
possibly mean that the user is not moved at all. If it is now located on a link with non-
higher index than user i+1, then it is added to Sand phase 1 goes on with the next sweep
(line 17-19). Otherwise the first phase is quitted by setting ito zero (line 20).
So, after each sweep, either a new user is added to Sor the first phase is terminated.
For the latter case we will prove (Lemma 3.2) that all unsatisfied users are in Sand that
they are arranged in a special way.
In the second phase we successively perform greedy steps for all unsatisfied users in
Sin order of increasing indices, i.e., in order of non-increasing traffic sizes. Because of
the special conditions that have been established by phase 1, and by Lemma 3.1, these
greedy moves do not cause other users with larger traffic to become unsatisfied.
To prove correctness we will proceed in two steps. First we prove that phase 1 estab-
lishes four postconditions (Lemma 3.2). Then we show that the same conditions remain
valid throughout the execution of the second phase (Lemma 3.3). It is then a simple mat-
ter to conclude that the assignment is at Nash equilibrium at the end of phase 2 and that
the social cost has not increased (Theorem 3.4).
Lemma 3.2. After phase 1 the following holds:
(i) All unsatisfied users are in S.
(ii) S={n, (n−1),...,(n+ 1 −|S|)}, that is, Scontains the |S|users with highest
indices.
(iii) i, i + 1 ∈S⇒A(i)≤A(i+ 1).
30 3 Nashification
(iv) Every user i∈Scan only improve (if at all) by moving to a link with smaller index.
Proof. Throughout the first phase mini() is kept valid (except for the transitions from
line 02 to 03, from line 09 to 10 and from line 18 to 19). Let us state this as the fifth
property:
(v) Array mini() is valid according to (3.1) throughout phase 1.
Actually, all we need is that (v) is valid at line 14, the only time when mini() is read. We
first prove properties (ii),(iii) and (v), which are strongly interrelated, to be invariants that
hold at any time throughout phase 1. Obviously, all three hold before the first run of the
repeat-until-loop. Now consider the first time when (ii),(iii) or (v) becomes invalid.
Assume that (ii) is the first property to become invalid. Note that a user which is in-
cluded in S, will never be removed from Sduring the first phase. Hence (ii) can only
become invalid when a new user is added to Safter a sweep in line 18. After a sweep, i
(if it is not zero) points to the user with the largest index that is not contained in Sso far.
This is because a sweep is finished if i /∈Sand iis either decremented by one (line 11)
during an iteration of the sweep or, as (v) is valid and mini(A(i)) is (particularly) a user
contained in S, set (in line 14) to an index which is at most by one lower than that of some
user in S. Thus, Sis always a consecutive set of the users with the |S|largest indices as
stated by (ii).
Now assume that (iii) becomes invalid first. There are two points in the algorithm
where (iii) could possibly become invalid. The first is in line 09, where a user i∈Sis
moved during a sweep. The second is in line 18, where a new user is added to S.
If a user i∈Sis moved during a sweep in line 09 to a link j, then this could invalidate
(iii) in two ways: First, if i > 1, then j < A(i−1) would cause (iii) to be invalid after the
reassignment. But as j > A(i)(because of line 08) this would imply A(i)< A(i−1),
and hence (iii) would have been invalid before, contradicting our assumption. Second, if
i < n, then j > A(i+ 1) would invalidate (iii). But consider the last run of the while-
loop where the value of iwas greater than it is now. Either it was i+ 1 and has been
decremented to iin line 11. But then user i+ 1 has been assigned to link jin line 09,
and as jis never increased during a sweep, we must now have j≤A(i+ 1). Or iwas
decreased by line 14 to its current value. Let i0be the former value of i(before the
decreasement). Then mini(A(i0)) = i+ 1 (because of line 14). In particular, this implies
A(i+ 1) = A(i0)due to the definition of mini(). As line 14 has been executed, we know
that the if-condition in line 12 was false, and hence, j≤A(i0) = A(i+ 1) at that point
of time. As jis never increased during a sweep, j≤A(i+ 1) is still true.
Line 18 is only executed if this does not invalidate (iii) which is explicitly inquired in
line 17. Note that i−1/∈Sbecause of (ii) and the fact that i /∈S(before the execution
of line 18).
At last assume that (v) becomes invalid first. This could only happen due to the execu-
tion of line 09 or line 18. If line 09 is executed, then user ihas the smallest index among
3.4 A Fast Nashification Algorithm 31
all users on link jcontained in S, because (iii) implies (by induction) that A(r)≤A(i)
for all r∈Swith r < i, and, due to line 08,A(i)< j. Thus mini() is properly up-
dated in line 10. When a new user is added to Sin line 18, then it must have the smallest
index among all users in S(due to (ii)), hence the updating of mini() in line 19 is correct.
To show (iv), we first prove that (iv) holds directly after any sweep and then argue that
the assignment is not changed (in line 16) after the last sweep. (Actually we will prove
a much stronger claim than (iv), namely that any user i∈Scannot be moved to any link
j > A(i)without exceeding the initial social cost M, that is, xj(A) + wi> Msjfor all
j∈[m]with j > A(i).)
Assume by way of contradiction that after some sweep there is some user rwhich fits
on some link s > A(r)without exceeding latency M. Without loss of generality, let this
be the first sweep for which such user exists, and let rbe the largest index of such user.
Hence, we know that user r+ 1 does not fit on any link j > A(r+ 1). As wr≥wr+1,
user rdoes not fit on any link j > A(r+ 1). If A(r) = A(r+ 1), then we are done.
Otherwise, let i0be the last value of variable igreater than r. When iis decreased from i0
to rin line 11 or 14, we know that user i0does not fit on any link j0> A(i0). This implies,
as wr≥wi0, that user rcannot fit on any link j0> A(i0), too, and therefore s≤A(i0).
If user ris located on the same link as user i0, i.e., A(r) = A(i0), then we are done.
Otherwise, A(r)< A(i0)(due to (iii)). During the following iterations of the while-loop, j
is successively set to A(i0), A(i0)−1,...,A(r)+1. As s∈ {A(i0), A(i0)−1, . . . , A(r)+1},
user rwould have been moved to link sby line 08 in the iteration of the while-loop with
j=sif it would fit on link s, a contradiction.
It remains to show that after the last sweep the assignment is not changed. This could
only happen if user iis moved to some link j > A(i+1) in line 16, because if it is moved
to some link j≤A(i+ 1), then the repeat-until-loop proceeds with a new sweep. But if
user iis moved to some link j > A(i+ 1), then, as wi≥wi+1, user i+ 1 had fit on link j
before user iis moved. This contradicts the above proof for (iv) to hold after any sweep.
At last we prove (i). The repeat-until-loop in phase 1 can only be terminated if i
becomes zero. This can happen in two different ways. Either ibecomes zero at the end
of the last sweep, or it is set to zero in line 20. In the first case all users are in S, which
implies (i). In the second case we know that A(i)> A(i+ 1) (because of line 17), that
user idoes not fit on any link j < A(i)(because of line 16) and that user i+ 1 cannot be
moved to any link j > A(i+ 1) (due to (iv)). Due to (ii), each user r /∈Scontrols at least
the same amount of traffic as users iand i+ 1, i.e., wr≥wi≥wi+1. Hence, none of the
users r /∈Scan fit on any link on which widoes not fit or on which wi+1 does not fit, that
is, on any link in {j∈[m]|j < A(i)}∪{j∈[m]|j > A(i+ 1)}= [m].
Our next step is to show that properties (i),(ii),(iii) and (iv), stated in Lemma 3.2 as
postconditions of phase 1, remain true during (and after) phase 2 as well.
Lemma 3.3. After any run of the while-loop in phase 2 the four properties from Lemma 3.2
remain valid, provided that they had been valid before.
32 3 Nashification
Proof. Consider any run of the while-loop and assume the conditions of Lemma 3.2 to
hold beforehand. Let ibe the user with smallest index in S, and suppose it is moved from
link j=A(i)to its best link k. Because of (ii), we have i=n+ 1 − |S|.(iv) implies
k≤A(i)and therefore sk≥sj.
Now let r /∈Sbe any user on some link s=A(r). Due to Lemma 3.1 and since wr≥wi,
rcannot be unsatisfied after ihas been moved. Thus, (i) still holds after moving i. As iis
removed from S(in line 25) and i=n+ 1 −|S|,(ii) and (iii) still hold after the iteration.
(iii) and the fact that iwas moved to a link j≤A(i)imply that (iv) remains true after the
iteration.
Having Lemmas 3.2 and 3.3 available, we can now conclude that algorithm Nashify
is correct and bound its running time.
Theorem 3.4. Given any pure assignment, algorithm Nashify computes a Nash equi-
librium with non-increased social cost, performing at most (m+ 1)nmoves. Provided
that user flows and link speeds are sorted, its running time is O(nm).
Proof.
Correctness
After execution of phase 1 properties (i)-(iv) from Lemma 3.2 hold. Applying Lemma 3.3
inductively shows that properties (i)-(iv) remain valid beyond the end of the algorithm.
Combining property (i) with the fact that set Sis empty at the end of the algorithm (due to
line 22) proves that the assignment is at Nash equilibrium when the algorithm terminates.
As the latency of any link is never increased beyond the initial value of the social cost
throughout the algorithm, the social cost of the computed Nash equilibrium will be no
more than that of the initial assignment.
Running time
We now analyze the running time of the first phase. Lines 01,02 and 03 are executed
once. Lines 04,05,06,15 and 21 are executed once for each iteration of the repeat-until-
loop. Denote the number of iterations of the repeat-until-loop as r. Lines 16,17,18 and
19 are executed at most rtimes. Line 20 is executed once. Denote the overall number of
iterations of the while-loop in lines 07-14 as w. Then, lines 08-14 are executed at most
wtimes. The while-statement in line 08 itself is executed w+ 1 times.
We assume that the flow on each link is computed in advance by adding all user flows
assigned to the respective link, which takes time O(m+n). Whenever the assignment is
changed during the algorithm, the link flows have to be updated which takes only constant
time. With these precomputations it takes time O(m)to execute lines 01 and 16, and all
other lines of phase 1 take constant time. Hence, the running time of phase 1 is O(rm+w).
The repeat-until-loop is iterated a most ntimes, because in each iteration, except for the
last maybe, one user (more precisely its index) is added to S. Once in Sa user is never
removed from Sagain during the first phase. Starting with S={n}, at most n−1users
can be added to S. Thus, r≤n. During one iteration of the while-loop (lines 07-14)
either lines 09-11 or line 13 or line 14 are executed. By lines 09-11 a user from S
3.4 A Fast Nashification Algorithm 33
located on some link A(i)is moved to some link with higher index j > A(i). This user
is never moved back again (to a link with lower index) during the first phase. As there
are mlinks, this can happen at most m−1times for each user. Hence, there are at most
n(m−1) iterations of the while-loop that execute lines 09-11 throughout the first phase.
In line 13 jis decremented if j−1> A(i). This can happen at most m−2times
during one iteration of the repeat-until-loop, because jis started at m, is never increased
during the while-loop and A(i)≥1. It follows that there are at most r(m−2) runs
of the while-loop that execute line 13 altogether. In line 14,iis set to a user which is
either not in Sor which is located on a link with smaller index than the user to which iis
currently pointing. In the first case the while-loop is not continued which happens once
per iteration of the repeat-until-loop. The second case can appear at most m−1times
during one iteration of the repeat-until-loop. Hence, line 14 is executed at most rm times
throughout phase 1. The amortized number wof iterations of the while-loop is therefore
at most n(m−1) + r(m−2) + rm =O(nm). Thus, the running time of phase 1 is
O(nm).
The while-loop in phase 2 is iterated at most |S| ≤ ntimes. During each iteration one
user has to be put on its best link, which takes time O(m). Hence, the running time of
phase 2 is O(nm).
Number of Moves
Now we bound the total number of reassignment steps. In phase 1 each user is shifted at
most once to a link with smaller index (in line 16). Afterwards it is contained in Sand
hence line 16 can never be executed again for that user. Once in S, a user can be shifted
only to a link with higher index than its current link (in line 09). This can happen at most
m−1times. In phase 2 each of the users in Sis reassigned at most once. Thus, the total
number of moves is bounded by n(m+ 1).
Apart from the routing model with related links as considered here, the algorithm can
also cope with slightly more general models. All we need is that users and links can be
ordered in a certain way so that the properties stated by the following proposition hold.
Proposition 3.5. Let I= (l)be an instance of the generic routing model, and let Abe any
pure assignment for I. If the following three properties hold, then algorithm Nashify,
started on input (I, A), Nashifies A.
(i) Let A0be any assignment that is attained during the execution of Nashify on
input (I, A). Let jbe any link, and set U=view(j, A0) = {r∈[n]|A0(r) = j}.
Then, ∀i, r ∈[n]\U, r < i :lj(U∪{r})≥lj(U∪{i}).
(ii) Let A0and A00 be any two consecutive assignments that are attained during the ex-
ecution of algorithm Nashify on input (I, A). Since, A0and A00 differ only in the
assignment of one user, say user i, we have A0(i) = j,A00(i) = k6=jand A0(r) =
A00(r)for all r∈[n]\{i}. Set U=view(j, A0)\{i}={r∈[n]\{i}|A0(r) = j}
and V=view(k, A0) = {r∈[n]|A0(r) = k}. If j > k, then ∀r∈[n]\U, r < i :
lj(U∪{r})−lk(V∪{r})≥lj(U∪{i})−lk(V∪{i}).
34 3 Nashification
(iii) Let A0be any assignment that is attained during the execution of Nashify on
input (I, A). Let jbe any link, and set U=view(j, A0) = {r∈[n]|A0(r) = j}.
Then, ∀i∈[n]:lj(U∪{i})≥lj(U).
Proof. In other words, property (i) claims that adding a user to some link causes the same
or higher latency than adding any user with larger index to the link instead. This ensures
that the first phase of the algorithm works correctly, because all we need for the first
phase (see proof of Lemma 3.2) is that if some user fits on some link without increasing
the social cost, then any user with larger index does as well.
Properties (ii) and (iii) are used for proving Lemma 3.6 which is a generalized version
of Lemma 3.1 and assures that the second phase works properly (by the same arguments
as in the proof of Lemma 3.3). Put in words, (ii) states that moving a user from some
link to any link with smaller index decreases its experienced latency by at least the same
amount as for a user with larger index being moved between the same links. Property
(iii) simply states that the latency cannot decrease if additional flow is routed through a
link.
Lemma 3.6. Let properties (i), (ii) and (iii) of Proposition 3.5 hold for an execution of
Nashify on input (I, A), where I= (l)is an instance of the generic routing model and
Ais any pure assignment for I. Consider any step of the second phase of the algorithm.
Let A0and A00 be the assignments before and after this step, respectively. Assume some
user iis greedy-moved from its current link j=A0(i)to some link kwith k < j, yielding
an assignment A00 with A00(i) = k. Then, λr(A) = mint∈[m]λr(A|rt)implies λr(A00) =
mint∈[m]λr(A00 |rt)for any r∈[n]with r < i.
Proof. Let the assumptions of the lemma hold and consider any user rwith r < i and
λr(A0) = mint∈[m]λr(A0|rt). Let user rbe located on link s=A0(r). Assume by way
of contradiction, that there exists some link twith
λr(A00)> λr(A00 |rt).(3.2)
Since only the traffic on link jand kchanges (it is decreased on link jand increased on
link k) due to the move of user i, and because of property (iii) (which excludes t=k),
we have s=kor t=j.
Assume first, that s6=k(and therefore t=j). Let us write view(p)for the view of link
paccording to assignment A0, i.e., view(p) = view(p, A0)for any link p∈[m]. Then we
have
ls(view(s)) = λr(A0)≤λr(A0|rk) = lk(view(k)∪{r}).(3.3)
User iimproves by moving to link k, thus
lk(view(k)∪{i}) = λi(A00)< λi(A0) = lj(view(j)) ,(3.4)
3.4 A Fast Nashification Algorithm 35
and we get
λr(A00 |rt) = lj(view(j)\{i}∪{r})
(3.4)
> lj(view(j)\{i}∪{r}) + lk(view(k)∪{i})−lj(view(j))
=lj(V∪{r}) + lk(U∪{i})−lj(V∪{i})
with U=view(k)and V=view(j)\{i}
(ii)
≥lk(U∪{r})
=lk(view(k)∪{r})(3.3)
≥ls(view(s)) = λr(A00),
contradicting (3.2).
Now assume s=k. First note that
λr(A00 |rj) = lj(view(j)\{i}∪{r}) = lj(U∪{r})with U=view(j)\{i}
(i)
≥lj(U∪{i}) = lj(view(j)) = λi(A0)> λi(A00) = λr(A00)
implies t6=j.
Since user ihas performed a greedy step, we have
lt(view(t)∪{i})≥lk(view(k)∪{i}),(3.5)
and hence
λr(A00 |rt) = lt(view(t)∪{r})(i)
≥lt(view(t)∪{i})(3.5)
≥lk(view(k)∪{i}) = λr(A00),
a contradiction to (3.2) .
If the properties of Proposition 3.5 hold for all assignments, then, in particular, they
hold for those assignments that are attained during the execution of Nashify. In this
way we can simplify the properties, as stated by the following corollary. Nevertheless,
the exact properties of Proposition 3.5 will be useful in Chapter 5.
Corollary 3.7. Let I= (l)be an instance of the generic routing model, where users and
links are numbered such that
(i)’ ∀j∈[m], i ∈[n−1], U ⊆[n]\{i, i + 1}:lj(U∪{i})≥lj(U∪{i+ 1})and
(ii)’ ∀j∈[m−1], i ∈[n−1], U, V ⊆[n]\{i, i + 1}:
lj+1(U∪{i})−lj(V∪{i})≥lj+1(U∪{i+ 1})−lj(V∪{i+ 1}and
(iii)’ ∀j∈[m], i ∈[n], U ⊆[n]\{i}:lj(U∪{i})≥lj(U).
Then algorithm Nashify Nashifies any pure assignment.
36 3 Nashification
Proof. We claim that properties (i)’,(ii)’ and (iii)’ imply properties (i),(ii) and (iii) of
Proposition 3.5. Property (i) follows by induction on ifrom property (i)’.(ii) follows
by induction on iand jfrom (ii)’.(iii) and (iii)’ are essentially the same. Note that
Proposition 3.5 requires the properties only to hold for the assignments that are actually
attained by algorithm Nashify, whereas (i)’,(ii)’ and (iii)’ yield more general versions
that hold for all assignments.
For the KP model the latency on a link jis defined as lj(U) = Pi∈U
wi
sj, where
U=view(j). So, any instance of this model possesses the properties stated in Corol-
lary 3.7. E.g., lj(U) = f(Pi∈U
wi
sj)with any non-decreasing and convex function fis
another appropriate definition obeying the properties of Corollary 3.7 and therefore also
those of Proposition 3.5.
We are not aware of any other efficient algorithm for approximating best Nash equi-
libria in the KP model up to a given quality. Hence, our approach is the first to yield a
Nash equilibrium of arbitrary constant approximation ratio in polynomial time. The work
which bears the closest similarity to ours, is that of Hurkens and Vredeveld [43]. They
explore so called jump optimal assignments. An assignment is said to be jump optimal,
if no user on a link with maximal latency can improve by a selfish step. They give an
algorithm for computing jump optimal assignments in at most n(m−1) steps. As the
Nash equilibrium property particularly implies jump optimality, our algorithm computes
a jump optimal assignment in about the same number of steps. However, our algorithm
achieves asymptotically better worst case running time.
3.5 Convergence to a Nash Equilibrium
In the previous section we addressed the question of how to compute a Nash equilibrium
assignment of guaranteed quality in the KP model by a central algorithm. In this section
we will explore the process of finding a Nash equilibrium if the users are being left to
their own decisions.
During this process we allow only one user at a time to change its link. This user is
chosen randomly. All users are provided with complete information, that is, they know
the speed and the current flow of each link. We assume that the user which is allowed to
move goes to its best link, i.e., that it makes a greedy step.
First of all this process always comes to a Nash equilibrium after a finite number of
moves. The validity of this claim does not require the assumption of greedy steps. That
is, the number of general selfish steps is finite as well. This can be proven by exploring
the vector of non-increasingly ordered link latencies [23]. With every selfish step its
lexicographic order decreases. The number of different vectors is bounded by the number
of different pure assignments, which is mn. Hence, there cannot be more than mnselfish
steps. This argument has also been used in [29] to prove the existence of a pure Nash
equilibrium in the KP model.
3.5 Convergence to a Nash Equilibrium 37
We now show that the process of finding a Nash equilibrium can take a superpolyno-
mial number of steps if the users are unguided, even on identical links, and even if we
allow greedy steps only.
We give an instance with nusers for which there exists a sequence of greedy steps of
length at least 23
2√n−6.
Definition 3.8. Define instance I(m, a)of the KP model with midentical links, a, m ∈
N≥2, as follows:
There are m−1classes of users U1,...,Um−1. The number of users in class i∈[m−1]
is ui=a+ 1 + (m−i)a. Each user rof class m−1has traffic size wr= 1, and each
user rin class i∈[m−2] has traffic size wr= 1 + Pm−1
j=i+1 Pk∈Ujwk.
For instance I=I(m, a)let A(I)be the assignment where all users go to link 1. We
consider the process where users successively perform greedy steps until a Nash equi-
librium is reached and hence no more selfish steps are possible. Often many users can
improve by switching their link. In this case we have to choose which user is allowed to
move next. We do so by always choosing a user of smallest traffic size and refer to this as
Smallest-Traffic-First (STF) selection rule. Ties are broken arbitrarily. We show that the
STF selection rule, and hence random selection in the worst case, leads to a superpolyno-
mial number of steps.
Theorem 3.9. Consider instance I(m, a)of the KP model for a, m ∈N≥2. Starting with
initial assignment A(I(m, a)) and letting the users successively perform greedy steps
according to the STF selection rule it takes at least am−1≥a√2
an−2steps to reach a
Nash equilibrium.
Proof. Let t(m, a)denote the number of steps for instance I=I(m, a)until a Nash
equilibrium is reached starting from initial assignment A(I)where all users go to link 1
and selecting users according to the STF rule.
For m= 2 we initially have u1= 2a+ 1 users of size 1on link 1while link 2is
empty. Hence, aof the users will move from link 1to link 2which takes asteps. This
proves t(2, a) = a.
Let m≥3, and let the claim be valid for m−1. That is t(m−1, a)≥am−2. Consider
instance I=I(m, a)with initial assignment A(I). There are am + 1 users in class U1.
Initially, their flows are assigned to link 1(as for all other users). As each of them is
larger than the total flow of all users in U2,...,Um−1, in a Nash equilibrium they must
be distributed among the mlinks such that one link carries a+ 1 of them and all other
links have exactly a. This implies that a(m−1) of them will move away from link 1
during the process. Let t2be the point in time when the first m−1users of class U1have
been moved away from link 1. Note that they must go to different links. Let t1be the
time just before the last of these users is moved. At time t1no user from U2, . . . , Um−1
can improve, because otherwise the user of class U1would not be allowed to move since
we always choose the smallest traffic first. Hence, at time t1we have am + 1 −(m−2)
users of class U1on link 1, we have m−2other links which carry one user from class
U1and no other users, and we have one link which contains all other users. The latter
38 3 Nashification
w2
1 2 3 m
w1w1
w1
wm−1
w1
w1
Figure 3.2: Link 1contains (a−1)m+ 3 users of class U1. Links 3, . . . , m contain
one user of class U1each. Link 2contains all remaining users of classes
U2,...,Um−1.wiis the traffic size of any user from class i.
3.5 Convergence to a Nash Equilibrium 39
has minimal latency among all links, and without loss of generality we may assume that
it is link 2(we may renumber the links appropriately). Thus the next user from link 1
will go to link 2. Figure 3.2 illustrates this step. After that, links 2, . . . , m induce an
instance I0=I(m−1, a)of m−1links with initial assignment A0=A(I0)and we can
apply the induction hypothesis and get that it takes t(m−1, a)≥am−2steps until a Nash
equilibrium is reached for those links. Note that each link of I0contains one additional
traffic (from class U1). This raises the latency on each link by the same amount but has
no influence on the moves that are carried out for I0. When all steps for I0are done we
can repeat our argumentation. After the next m−1users have moved from link 1we
again have an initial assignment for I0where all users from U2,...,Um−1are assigned to
the first link of I0(which is link 2for instance I). Hence, again t(m−1, a)moves are
necessary until the next user from link 1is allowed to move.
Initially there are am + 1 users of class U1on link 1. Hence it happens atimes that
m−1of them are moved from link 1yielding an initial assignment A0for instance I0. Each
time it takes t(m−1, a)steps to Nashify the sub instance I0. This is at(m−1, a)≥am−1
steps altogether, which proves that t(m, a)≥am−1.
The total number of users for instance I(m, a)is
n=X
i∈[m−1]
ui=X
i∈[m−1]
[a+ 1 + (m−i)a] = (m−1)(a+ 1 + am
2)<a
2(m+ 1)2,
which implies q2
an−1≤m. Thus we can bound the total number of moves from below
by t(m, a)≥am−1≥a√2
an−2.
The term a√2
a, with a∈N≥2, is maximized for a= 7. Hence for instance I(m, 7)
we obtain at least 7√2
7n−2≥2.829√n−4steps. So, on one hand, the worst case number of
greedy steps for unguided users on identical links is at least 2.829√n−4>23
2(√n−4). On
the other hand, it is shown in [27] that the number of greedy steps is bounded by 2n−1
for identical links.
Theorem 3.10. ([27]) For any instance with nusers on identical links, the length of any
sequence of greedy steps is at most 2n−1.
Similarly, but independently, Even-Dar et al. [23] show that the number of greedy
steps for nusers with k≤ndifferent flow sizes on identical links is bounded from above
by O((n
k+ 1)k).
40 3 Nashification
4
The Nash Equilibrium Verification
Problem
4.1 Introduction
In this chapter we deal with the question of how to decide whether a given pure assign-
ment for the KP model is at Nash equilibrium or not. We will refer to this as the Nash
Equilibrium Verification problem. We reveal an interesting equivalence to a geometric
problem in two dimensional space. On this basis we can then give a fast algorithm for
Nash Equilibrium Verification in Section 4.2. The algorithm runs in time O(n+mlog m).
Section 4.3 describes how the algorithm can be extended to verify whether an assignment
is at approximate Nash equilibrium.
In Section 4.4 we reduce the Open Halfspace Emptiness problem to the Nash Equilib-
rium Verification problem. With help of Ben-Or’s theorem [9] the former can be shown
to take at least O(mlog m)steps in the worst case of any computation that is describable
by an algebraic computation tree. This yields a lower bound of O(n+mlog m)for the
Nash Equilibrium Verification problem matching the upper bound of our algorithm.
4.2 A Nash Equilibrium Verification Algorithm
In this section we present an algorithm IsNash(I,A)(Figure 4.2), which outputs true,
if the pure assignment Ais at Nash equilibrium for the instance I= (w, bfs)of the KP
Model with link speeds s= (s1,...,sm)and user flows w= (w1, . . . , wn), and false
otherwise.
42 4 The Nash Equilibrium Verification Problem
The simplest approach to test whether Ais at Nash equilibrium, is to check for each
user i∈[n], whether it can improve by changing to another link k, i.e., whether
xk+wi
sk
<xA(i)
sA(i)
=λi(A)(4.1)
for some k∈[m]\{A(i)}. If such user exists, Ais not a Nash equilibrium. To verify that
no such user exists, we have to check m−1links for each of nusers. This takes time
Θ(mn)in the worst case.
To get better, we make use of the fact that it suffices to verify for each link the user
with the smallest traffic. This is due to the following lemma.
Lemma 4.1. If there is some user iassigned to link jwhich can improve by moving to
some link k, then any user ron link jwith wr≤wican improve by moving to link k.
Proof. Assume user iis assigned to link jand can improve by moving to link k. Then
wr≤wi⇒xk+wr
sk≤xk+wi
sk
<xj
sj
,
which proves the claim.
Hence, if we initially compute for each link jits congestion xjand the smallest user
flow assigned to link j, which takes time O(n+m), then we only have to check (4.1) for
musers. This takes time O(n+m2)altogether.
For the special case of identical link, we only have to check whether a user can im-
prove by changing to the least loaded link, which yields an O(n+m)-time algorithm.
For the special case of identical users (say of identical traffic size w) but related links,
we just have to check for each link whether a user can improve by changing to the link
jfor which xj+w
sjis minimal. This can be done in time O(m)if the assignment is given
by the link flows x1,...,xm. If the assignment is given by Aand the flow values must be
computed by the algorithm itself, then it takes nsteps to go through all users. Hence, the
algorithm takes time O(n+m)in this case.
For the same reason we will never get rid of the additive O(n)term in the upper bound
on the complexity of the general problem. But we will now see how to bring down the
running time below O(n+m2)in the general case. First note that we only have to check
the smallest user on each link (due to Lemma 4.1). Henceforth, let ¯wjbe the smallest
traffic on link j, and let lj=xj
sjbe the latency on link j. All users on link jare satisfied,
if and only if there exists no other link with speed sand flow x, such that
x+ ¯wj
s< lj
⇔x < ljs−¯wj.(4.2)
Inequality (4.2) describes a closed halfplane in the two-dimensional sx-coordinate plane
with boundary line x=ljs−¯wj. If we draw for each link jthe corresponding line into
4.2 A Nash Equilibrium Verification Algorithm 43
x
s
Figure 4.1: Set of lines and points in the plane corresponding to an assignment in the KP
model. The dashed course marks the boundary of the intersection of the upper
halfplanes of all lines. In a Nash equilibrium all points must lie on or above
this course.
the plane, we get a passel of lines like in Figure 4.1. Furthermore, for each link k,(sk, xk)
can be interpreted as a point in the same plane.
Then a link kwith speed skand flow xkfulfilling (4.2) for some j∈[m]and x=xk,
s=sk, corresponds to a point (sk, xk)lying below line x=ljs−¯wj. Hence, Ais at
Nash equilibrium, exactly if none of the points (sk, xk), k = 1,...,m, lies below any of
the lines x=ljs−¯wj, j = 1,...,m. That is, for Ato be a Nash equilibrium, all points
must lie in the intersection of the closed upper halfplanes determined by the lines.
It takes time O(n+m)to compute xj,¯wjand ljfor each j∈[m]. The intersection of
mhalfplanes is a convex polygonal region which can be computed in time O(mlog m)
(see e.g. [68]). Checking whether a single point is included in a convex polygonal re-
gion with mcorners can be done in time O(log m)with preprocessing time O(m)[68].
For a set of mpoints, as the preprocessing must be carried out only once, the question
whether all points are contained in a convex polygonal region can be answered after time
O(mlog m). Thus we have the following O(n+mlog m)time algorithm for the Nash
Equilibrium Verification problem:
1. compute xj,¯wj, ljfor all j∈[m]
2. compute the intersection Qof the mhalfplanes
determined by {(s, x)∈R2|x≥ljs−¯wj}, j ∈[m]
3. check whether all mpoints (sj, xj), j ∈[m], lie in Q
Figure 4.2 states the pseudocode of a more dedicated algorithm. All we need in order
to decide whether a point lies in the closed upper halfspace of all lines (see Figure 4.1),
44 4 The Nash Equilibrium Verification Problem
IsNash(I,A)
Input: instance I= (w,s)of the KP model,
assignment A
Output: true if Ais Nash equilibrium, false otherwise
1. for all j∈[m]set xj:= 0; and ¯wj:= ∞;
for i= 1,...,n
xA(i):= xA(i)+wi;
¯wA(i):= min{¯wA(i), wi};
for j= 1,...,m
lj:= xj/sj;
2. sort ((xj,¯wj, lj))j∈[m]non-decreasingly according to lj;
a1:= 0;b1:= −¯w1;i1:= 1;p:= 1;
for j= 2,...,m
while ljap−¯wj≥lipap−¯wipand p > 0
p:= p−1;
if p= 0 then
a1:= 0;b1:= −¯wj;i1:= j;p:= 1;
else if lj> lipthen
q:= ¯wj−¯wip
lj−lip;
p:= p+ 1;
ap:= q;bp:= ljq−¯wj;ip:= j;
3. sort ((xj, sj))j∈[p]non-decreasingly according to sj;
k:= 1;
for j= 1,...,m
while k < p and ak+1 ≤sj
k:= k+ 1;
if xj< liksj−¯wikthen return false;
return true;
Figure 4.2: Algorithm IsNash(I,A)verifies whether a pure assignment Afor an in-
stance Iof the congestion routing model with related links (KP model) is at
Nash equilibrium or not.
4.3 Verification of Approximate Nash Equilibria 45
is the course of the lower border of the intersection of all halfplanes. The algorithm com-
putes the corners (a0, b0),...,(ar, br)of this course. After the precomputations in step 1,
in step 2 we first sort the links according to non-decreasing latencies lj, i.e., according
to the slopes of the lines. Then, we successively add lines according to that order in the
for-loop. Variable pstores the number of corner points the course produced so far consists
of. i1, i2,... are the corresponding line indices, i.e., (ak, bk)is the intersection point of
line ik−1with line ikfor k∈[p]\{1}. Assume, (ap, bp)is the last corner so far. When a
new line is added, we have to check whether its value at position apis lower than bpor
not (this is done by the while-condition). In the first case we get a new corner (ap+1, bp+1)
(the intersection point of the new line and the last line) which is constructed in the else-
statement (the inner if-statement accounts for the special case where the new line and the
last line have the same slope). In the second case, as any point below the last line also lies
below the new line or some other line processed so far, we may delete the last line and the
corresponding corner and repeat the step with (ai−1, bi−1),(ai−2, bi−2), . . . until the first
case applies or all corners have been deleted.
Once we have computed all corners (a0, b0),...,(ar, br), we have to check for the
points (s1, x1),...,(sm, xm)whether they lie below the course given by the corners. This
is done in the third step. First we sort the points non-decreasingly according to their
abscissa sj. Then we take up all points one after the other. For each point (sj, xj)we
advance in the list of corners (starting with corner point k= 1) until we find the cor-
responding line segment, i.e., until ak< sj≤ak+1 or k=p. If (sj, xj)lies below
the line segment, then Ais not at Nash equilibrium. If all points lie above or on their
corresponding line segment, Ais at Nash equilibrium.
Running Time
The running time for the precomputation step is O(n+m). The second step is dominated
by the sorting. The rest of this step takes time O(m), because each corner is added to and
deleted from the list at most once. Similarly, the running time of O(mlog m)for the third
phase is due to the sorting, whereas the remainder of this phase takes only linear time.
Thus, altogether the algorithm runs in time O(n+mlog m).
Theorem 4.2. The Nash Equilibrium Verification Problem can be decided in time O(n+
mlog m)for any instance of the KP model with nusers and mlinks..
4.3 Verification of Approximate Nash Equilibria
There are two established ways to define an approximate Nash equilibrium.
Definition 4.3. Let Abe an assignment for an instance of the KP model with nusers and
mlinks. Then Ais at -Nash equilibrium for > 0, if ∀i∈[n], j ∈[m]:li(A|j) + ≥
li(A).
Definition 4.4. Let Abe an assignment for an instance of the KP model with nusers and
mlinks. Then Ais at (1 + )-approximate Nash equilibrium for > 0, if ∀i∈[n], j ∈
[m] : (1 + )li(A|j)≥li(A).
46 4 The Nash Equilibrium Verification Problem
According to Definition 4.3 an assignment is at -approximate Nash equilibrium if
no user can decrease its cost by more than by changing to another link. According to
Definition 4.4 an assignment is at (1 + )-approximate Nash equilibrium if no user can
decrease its cost by a factor of 1
1+or below. Both kinds of approximate Nash equilibria
give way to exact Nash equilibria if is zero.
Our algorithm for the Nash Equilibrium Verification problem can be used to check
whether an assignment is at approximate Nash equilibrium as well, if slight modifications
are being undertaken.
First note that Lemma 4.1 is transferable to the approximate case. That is, if a user,
assigned to some link, can decrease its experienced latency by at least , or, respectively,
by at least a factor of 1
1+, when switching to another link, then the same holds for any
user with smaller or equal flow that is currently assigned to the same link. Hence, as in
the original algorithm, we have to check the Nash equilibrium condition only once per
link, namely for the smallest flow.
According to Definition 4.3 the -approximate Nash equilibrium condition for link j
is not fulfilled if there exists another link with speed sand flow xso that
x+ ¯wj
s+ < lj
⇔x < (lj−)s−¯wj.(4.3)
Again we can interpret this inequality geometrically. This yields for each link a line and
a point in the sx-plane. The only difference to the verification problem for exact Nash
equilibria is that the line for link jhas slope (lj−)now instead of lj. Similarly, on
the basis of Definition 4.4, the slope is 1
1+lj. With these modifications we can adopt
our argumentation from the last section. So, we only have to change the last line in the
first step of the algorithm in Figure 4.2. We compute ljas lj:= xj
sj−or lj:= xj
(1+)sj
to obtain an algorithm for the -approximate Nash Equilibrium Verification Problem or
for the (1 + )-approximate Nash Equilibrium Verification Problem, respectively. Note
that in the first case the slopes of some lines might be negative. Those lines can never
cause the instance to be not at Nash equilibrium, but processing them does not derange
the algorithm nor does it affect its worst case running time.
Theorem 4.5. The -approximate Nash Equilibrium Verification Problem and the (1 +
)-approximate Nash Equilibrium Verification Problem can be decided in time O(n+
mlog m)for any instance of the KP model with nusers and mlinks..
4.4 A Lower Bound for the Nash Equilibrium Verifi-
cation Problem
In this section we prove a lower bound of Ω(n+mlog m)for the problem to decide
whether a given assignment of nusers to mlinks in the KP model is at Nash equilibrium
or not. This lower bound holds for any algorithm whose computation can be described by
an algebraic computation tree [9].
4.4 A Lower Bound for the Nash Equilibrium Verification Problem 47
Algebraic Computation Trees
An algebraic computation tree Tis a binary tree with three kinds of nodes: computation
nodes,branch nodes and output nodes. Computation nodes have exactly one child node,
branch nodes have two child nodes and the output nodes are exactly the leaves of the tree.
An input for the algebraic computation tree is given by a vector x∈Rnof real numbers.
A function is associated with the tree that assigns
•to each computation node van instruction fv=fu◦fw,fv=c◦fuor fv=√fu
which assigns the value fvto vwhere ◦is one of the operations +,−,·, / and
fu, fw∈Rare input values or values associated with computation nodes u, w that
are ancestors of vand c∈Ris a constant,
•to each branch node va test instruction fu>0,fu≥0or fu= 0, where fu∈Ris
an input value or the value associated with an ancestor uof v,
•to each output node Y es or No
An algebraic computation tree assigns either Y es or No to each of its inputs x∈Rnby
traversing a path in the tree. At each computation node the associated operation is per-
formed. At each branch node the path branches either to the left or right child according
to the associated test. At a leaf node either Y es or No is reported. An algebraic com-
putation tree Tis said to decide the membership for a set W⊆Rn, if Wis the set of
Y es-instances of T.
The following theorem of Ben-Or is the basis for our lower bound proof by counting
the number of connected components in the subspace of Y es-instances.
Theorem 4.6. ([9]) Let W⊆Rnbe any set, and let Tbe an algebraic computation
tree that solves the membership problem for W. If Nis the number of disjoint connected
components of Wand his the height of T, then 2h3n+h≥N.
Algorithms that can be described by algebraic computation trees correspond to pro-
grams that can be carried out by a realRAM (see [68]), which is a widely used model of
computation, particularly in the area of computational geometry. A realRAM is similar
to an ordinary RAM [1] but can operate on real numbers (i.e., with infinite precision) in
constant time.
To achieve a lower bound on the Nash Equilibrium Verification Problem we will
bound the complexity of another algebraic problem from below and then reduce it in a
chain of reductions to the Nash Equilibrium Verification Problem. The proof involves the
following five problems:
P1Given n∈Nand 3nnumbers a1,...,an, b1,...,bn, c1,...,cn∈R, is for all
i, j ∈[n] : (ci/∈(aj, bj)∧aj< bj)?
P2Given n∈Nclosed halfplanes and npoints in the plane, do all points lie in the
intersection of all halfplanes?
48 4 The Nash Equilibrium Verification Problem
P3Given n∈Nlines in the xy-plane with positive slopes intersecting the negative
y-axis and npoints in the open first quadrant (i.e., with positive coordinates), does
no point lie below any line?
P4Given n∈Nlines in the xy-plane with positive slopes a1, . . . , an∈R>0and neg-
ative y-axis intercepts b1,...,bn∈R<0(i.e., (0, bi)is the intersection point of line
iwith the y-axis), does none of the points (−b1
a1,−b1),...,(−bn
an,−bn)∈R2
>0lie
below any line?
P5Given n∈Nlinks with speeds s1,...,sn∈R>0, congestions x1, . . . , xn∈R>0
and smallest flows ¯w1,..., ¯wn∈R>0, is this situation at Nash equilibrium?
Note that, different from our former convention, ndenotes the number of links in the
description of problem P5. We will prove that
P1≤O(n)
const−TP2≤O(n)
const−TP3≤O(n)
const−TP4≤O(n)
const−TP5,
where A≤O(n)
const−TBmeans that problem Ais Turing-reducible to problem Bvia some
deterministic linear time function that makes at most a constant number of queries to B.
We will give then a lower bound for the computational complexity of P1in the algebraic
computation tree model, which therefore applies to P5, which is essentially the Nash
Equilibrium Verification Problem, as well.
Let us start with the last step of the reduction chain.
Lemma 4.7. P4≤O(n)
const−TP5.
Proof. Let a1,...,an∈R>0, b1,...,bn∈R<0be an input to Problem P4. Then set the
input of the P5problem to an instance of the KP model with nlinks of speeds s1, . . . , sn,
congestions x1,...,xnand smallest traffic sizes ¯w1,..., ¯wn. We obtain the link speeds
by si=−bi
aiand the congestions and smallest flows by xi= ¯wi=−bifor all i∈[n]. This
corresponds to an assignment of nusers with weights w1=−b1, . . . , wn=−bn, where
user iis assigned to link isolely for all i∈[n]. Then, for any i, j ∈[n],
−bi<−bi
ai
aj+bj⇔wi+wj
si
<wj
sj
.
Note that −biis positive. The left inequality formalizes the fact that the ith point (which
has coordinates (−bi
ai,−bi)) lies below the jth line (with slope ajand intersection with
the y-axis at bj) referring to the input of P4. The second inequality stands for the fact
that, referring to the P5-input, the only user on link jcan improve by switching to link i,
and hence the situation is not at Nash equilibrium. Due to the above equivalence, the P4
instance is positive, exactly if the P5instance we obtained from it is positive.
4.4 A Lower Bound for the Nash Equilibrium Verification Problem 49
Remark 4.8. Note that in the proof of Lemma 4.7 problem P4is transformed to a special
case of P5where each link carries exactly one user’s flow. One can formulate a more gen-
eral version P0
4of P4such that there is a bijective transformation between the instances
of P0
4and P5.
P0
4Given n∈Nlines with positive slopes a1,...,an∈R>0and y-axis intercepts
b1,...,bn∈R<0and nabscissas z1,...,zn∈R>0with zi=−bi
aior zi≥2−bi
aifor
all i∈[n], does none of the points (z1, a1z1),...,(zn, anzn)lie below any line?
The constraints on z1,...,znare due to the fact that in the P5instance the smallest traffic
size of a link can either be equal to the link’s congestion (if there is at most one user on
that link) or must be lower than or equal to half the congestion (if there are at least two
users on that link).
Showing P3≤O(n)
const−TP4is the main step of the reduction chain. We first give a
description of the transformation and the main idea. Then a formal proof follows.
Let the input to P3be given by a1,...,an∈R>0, the slopes of the nlines, b1, . . . , bn∈
R<0, their y-axis intercepts (i.e., (0, bi)is the intersection point of line iwith the y-axis)
and (x1, y1),...,(xn, yn)∈R2
>0, the npoints.
Problem P3is similar to P4in that both problems question whether any of npoints
lies below any of nlines. But for problem P3both, lines and points, are part of the input.
The lines may have arbitrary positive slope and negative y-axis intercept. The points may
have arbitrary positive coordinates. Hence we have 4ndegrees of freedom. For P4only
the lines are part of the input, yielding only 2ndegrees of freedom. Thus, in order to cope
with this non-conformity, we map the instance of P3to an instance of P4with 2nlines
instead of only nlines. Lines 1,...,nwill be the same as the nlines of the P3-instance.
Lines n+1,...,2nwill be determined so that their corresponding points match the points
of the P3-instance. Denote the slopes of the lines of the P4instance as ˆa1, . . . , ˆa2nand
their y-axis intercepts by ˆ
b1,...,ˆ
b2n. Hence we set
ˆai=(aifor i∈[n]
yi−n/xi−nfor i∈[2n]\[n]and ˆ
bi=(bifor i∈[n]
−yi−nfor i∈[2n]\[n].(4.4)
Let (ˆx1,ˆy1),...,(ˆx2n,ˆy2n)be the points yielded by the lines we just defined, i.e., ˆxi=
−ˆ
bi/ˆaiand ˆyi=−ˆ
bifor i∈[2n]. Note that lines 1,...,nof the P4instance and points
(ˆxn+1,ˆyn+1),...,(ˆx2n,ˆy2n)correspond to the lines and points of the P3instance. Let us
call these lines and points deliberate lines and deliberate points, respectively.
If one of the points lies below one of the lines for the P3instance, then the same is
true for the corresponding deliberate line and point of the P4instance. But, unfortunately,
one of the points (ˆx1,ˆy1),...,(ˆxn,ˆyn)or one of the lines n+ 1,...,2nof the P4instance
could also cause the instance to be negative. Let us call these points and lines artefactual
points and artefactual lines, respectively. Thus, we cannot guarantee that the P4instance
is positive if the P3instance is positive.
50 4 The Nash Equilibrium Verification Problem
To overcome this problem, we shift all lines and points of the original P3instance
by an appropriate number δ∈Rof units in the direction of the positive x-axis. Denote
the modified input to P3by a0
1,...,a0
n∈R>0(the slopes of the lines), b0
1, . . . , b0
n∈R<0
(their y-axis intercepts) and (x0
1, y0
1),...,(x0
n, y0
n)∈R2
>0(the points). Shifting a line does
not change its slope but only its intersection point with the y-axis. Shifting a point only
increases its x-coordinate. That is, we have a0
i=ai, b0
i=bi−δai, x0
i=xi+δand y0
i=yi
for all i∈[n]. The P4-instance is now defined according to the shifted P3-instance. That
is,
ˆai=(a0
ifor i∈[n]
y0
i−n/x0
i−nfor i∈[2n]\[n]and ˆ
bi=(b0
ifor i∈[n]
−y0
i−nfor i∈[2n]\[n].(4.5)
Shifting all lines and points of the P3instance by the same amount does not affect
the question whether the instance is positive or not since it does not change the relative
position of lines and points. But, as we will see, it changes the artefactual lines and points
of the corresponding P4instance that we get by the transformation as described above. If
the amount of movement is sufficiently large, then the artefactual lines and points cannot
cause the instance to be negative.
Let us assume the P4instance that we obtained by transforming the modified (after
shifting) P3instance is negative. Then there exist i, j ∈[2n]such that point ilies below
line j, i.e.,
ˆyi<ˆajˆxi+ˆ
bj
⇔ −ˆ
bi<−ˆajˆ
bi
ˆai
+ˆ
bj.(4.6)
Subject to iand jwe can distinguish four cases.
artefactual point ilies below deliberate line jif i, j ∈[n]
artefactual point ilies below artefactual line jif i∈[n], j ∈[2n]\[n]
deliberate point ilies below deliberate line jif i∈[2n]\[n], j ∈[n]
deliberate point ilies below artefactual line jif i, j ∈[2n]\[n]
We get the corresponding inequalities, if we apply the definition of ˆaiand ˆ
biin (4.5) to
4.4 A Lower Bound for the Nash Equilibrium Verification Problem 51
(4.6).
−ˆ
bi<−ˆajˆ
bi
ˆai
+ˆ
bj.
⇔
−b0
i<−a0
jb0
i
a0
i+b0
jif i, j ∈[n]
−b0
i<−y0
j−nb0
i
x0
j−na0
i−y0
j−nif i∈[n], j ∈[2n]\[n]
y0
i−n<a0
jy0
i−nx0
i−n
y0
i−n+b0
jif i∈[2n]\[n], j ∈[n]
y0
i−n<y0
j−ny0
i−nx0
i−n
x0
j−ny0
i−n−y0
j−nif i, j ∈[2n]\[n]
⇔
−(bi−δai)<−aj(bi−δai)
ai+ (bj−δaj)if i, j ∈[n]
−(bi−δai)<−yj−n(bi−δai)
(xj−n+δ)ai−yj−nif i∈[n], j ∈[2n]\[n]
yi−n< aj(xi−n+δ) + (bj−δaj)if i∈[2n]\[n], j ∈[n]
yi−n<yj−n(xi−n+δ)
xj−n+δ−yj−nif i, j ∈[2n]\[n]
⇔
δai−bi<−aj
aibi+bjif i, j ∈[n]
(δai−bi)(xj−n+δ)<−yj−n(bi
ai+xj−n)if i∈[n], j ∈[2n]\[n]
yi−n< ajxi−n+bjif i∈[2n]\[n], j ∈[n]
xj−n+δ < yj−n
yi−n(xi−n−xj−n)if i, j ∈[2n]\[n]
Note that the third case is equivalent to the fact that point i−nlies below line jin the
original P3instance (before shifting). Furthermore, the other three cases cannot appear
if we choose δsufficiently large, as in all cases the left hand side of the inequality is in-
creasing with δand the right hand side does not depend on δ. If δ≥1
ai−ajbi
ai+bj+bi
for i, j ∈[n], then the first case cannot appear. We may estimate more roughly and will
choose δsuch that δ≥ −ajbi
a2
i
for i, j ∈[n]. Similarly, we can avoid the second and fourth
case. If we ensure that δ≥1, then δai−bi≥ −yj−nbi
ai−yj−nxj−nfor i∈[n], j ∈[2n]\[n]
would suffice to make the second case impossible. Recall that −biis positive. Conse-
quently, if we set δ≥max{1,−yj−nbi
a2
i}for i∈[n], j ∈[2n]\[n], then the second case
cannot appear. If δ≥yj−nxi−n
yi−nfor i, j ∈[2n]\[n], then the fourth case cannot appear.
Hence, if we set δsuch that δ≥max{−ajbi
a2
i,1,−yjbi
a2
i,yjxi
yi}for all i, j ∈[n], then we
avoid all cases that involve artefactual lines or points.
Figure 4.3 exemplifies the fourth case. On the left we see two deliberate points p1=
(x1, y1)and p2= (x2, y2)of the P4instance that has been obtained from the P3instance
without shifting. l1and l2are the corresponding lines with slopes a1=y1
x1,a2=y2
x2
and vertical axis intercepts b1=−y1,b2=−y2. As p2lies below l1, the P4instance is
negative although the P3instance may be positive. If all points and lines of the P3instance
are shifted by δto the right before transforming it to the P4instance, then we obtain points
p0
1= (x1+δ, y1)and p0
2= (x2+δ, y2)and lines l0
1and l0
2with slopes a0
1=y1
x1+δand
52 4 The Nash Equilibrium Verification Problem
a0
2=y2
x2+δin place of points p1,p2and lines l1,l2. The axis intercepts do not change. This
is illustrated at the right side of Figure 4.3. Now p0
2lies above l0
1, as desired.
p1
p2
l1
l2
x
y
p’
1p’
2
l’1
l’2x
y
Figure 4.3: Left: Deliberate point p2lies below artefactual line l1. Right: After shifting
p0
2lies above l0
1.
To determine δin linear time we estimate the terms and set
δ= max{−amaxbmin
a2
min
,1,−ymaxbmin
a2
min
,ymaxxmax
ymin }(4.7)
where
amax = max
i∈[n]ai, amin = min
i∈[n]ai,
ymax = max
i∈[n]yi, ymin = min
i∈[n]yi,(4.8)
bmin = min
i∈[n]bi, xmax = max
i∈[n]xi.
Let us state all the above in the following lemma.
Lemma 4.9. P3≤O(n)
const−TP4.
Proof. Let I= (a1,...,an, b1,...,bn, x1,...,xn, y1,...,yn)be an instance of problem
P3. Set δaccording to (4.7) and (4.8). For i∈[2n]set
ˆai=(aii∈[n]
yi−n/(xi−n+δ)i∈[2n]\[n]and ˆ
bi=(bi−δaii∈[n]
−yi−ni∈[2n]\[n].
Then ˆ
I= (ˆa1,...,ˆa2n,ˆ
b1,...,ˆ
b2n)is an instance of problem P4.
We will show that ˆ
Iis positive for P4, if and only if Iis positive for P3.
Assume first that Iis negative. Then there exist i, j ∈[n]such that the ith point lies below
4.4 A Lower Bound for the Nash Equilibrium Verification Problem 53
the jth line of I. That is,
yi< ajxi+bj
⇔yi<ajyi(xi+δ)
yi
+ (bj−δaj)
⇔ −ˆ
bi+n<−ˆaj
ˆ
bi+n
ˆai+n
+ˆ
bj
⇔ˆyi+n<ˆajˆxi+n+ˆ
bj
The last inequality implies that point (−ˆ
bi+n
ˆai+n,−ˆ
bi+n)lies below the jth line, and hence ˆ
I
must be negative, too.
Now assume that ˆ
Iis negative. Then there exist i, j ∈[2n]such that the point (−ˆ
bi
ˆai,−ˆ
bi)
lies below the jth line of ˆ
I. That is,
ˆ
bi<ˆaj −ˆ
bi
ˆai!+ˆ
bj
⇔
−(bi−δai)<−aj(bi−δai)
ai+ (bj−δaj)if i, j ∈[n]
−(bi−δai)<−yj−n(bi−δai)
(xj−n+δ)ai−yj−nif i∈[n], j ∈[2n]\[n]
yi−n< aj(xi−n+δ) + (bj−δaj)if i∈[2n]\[n], j ∈[n]
yi−n<yj−n(xi−n+δ)
xj−n+δ−yj−nif i, j ∈[2n]\[n]
⇔
δa2
i<−ajbi+aibj+aibiif i, j ∈[n]
(δai−bi)(xj−n+δ)ai<−yj−nbi−aixj−nyj−nif i∈[n], j ∈[2n]\[n]
yi−n< ajxi−n+bjif i∈[2n]\[n], j ∈[n]
yi−n(xj−n+δ)< yj−nxi−n−xj−nyj−nif i, j ∈[2n]\[n]
⇒
δ < −aj
a2
ibiif i, j ∈[n]
δ2<−yj−nbi
a2
i
if i∈[n], j ∈[2n]\[n]
yi−n< ajxi−n+bjif i∈[2n]\[n], j ∈[n]
δ < yj−nxi−n
yi−nif i, j ∈[2n]\[n]
⇒
δ < −amaxbmin
a2
min
if i, j ∈[n]
δ < 1∨δ < −ymaxbmin
a2
min
if i∈[n], j ∈[2n]\[n]
I is negative for P3if i∈[2n]\[n], j ∈[n]
δ < ymaxxmax
ymin if i, j ∈[2n]\[n]
.
As the first, second and fourth case contradict (4.7), this implies that Iis negative.
We continue with the next step of the reduction chain. On first sight problem P2seems
to be more general than P3, as the constraints on the input for P3are more restrictive. But,
54 4 The Nash Equilibrium Verification Problem
as we will see in the proof of the next lemma, we can decide P2by deciding four instances
of P3.
Lemma 4.10. P2≤O(n)
const−TP3.
Proof. Let Ibe an input instance for P2. Assume the nhalfplanes are given by base
points q1,...,qn∈R2and normal vectors n1,...,nn∈R2\{(0,0)}, where qilies on the
boundary of halfplane iand niis directed into the interior of halfplane i. That is, halfplane
iis defined by the set of points {p∈R2|(p−qi)•ni≥0}, where ’•’ denotes the inner
product. Let the input points be given by (x1, y1),...,(xn, yn)∈R2. First, process all
halfplanes with axis parallel boundary line (or, equivalently, with axis parallel normal
vector). Therefor, sweep over the halfplanes once and determine the intersection area of
all halfplanes with horizontal or vertical boundary line and, at the same time, remove all
those halfplanes. Note that the intersection area is an axis parallel rectangle. Now check
for each point whether it lies in this rectangle. If not, then we may report that the given
P2instance is negative. Otherwise, partition the remaining halfplanes into four groups
according to their normal vector. For j∈ {1,2,3,4}group jcontains all halfplanes with
normal vectors lying in the jth quadrant of the coordinate plane. A vector v= (x, y)lies
in the
•1st quadrant, if 0< x, y,
•2nd quadrant, if x < 0< y,
•3rd quadrant, if x, y < 0,
•4th quadrant, if x > 0> y.
Note that x, y 6= 0 applies to all normal vectors, as halfplanes with axis parallel normal
vectors have been removed. Hence the quadrant of each remaining normal vector is well
defined.
For j∈[4] we define the function fj:R2→R2by
fj((x, y)) =
(−y, x)for j= 1
(x, y)for j= 2
(y, −x)for j= 3
(−y, −y)for j= 4
.
For each group jof halfplanes, we now construct a new instance I0
jconsisting of npoints
and mjhalfplanes, where mjis the number of halfplanes in group j. For I0
jwe obtain
the npoints by applying fjto each input point of the P2instance. The mjhalfplanes are
obtained by applying fjto both, the base point and the normal vector of each halfplane in
group j. Note that all normal vectors of I0
1, I0
2, I0
3, I0
4lie in the 2nd quadrant. Furthermore,
we did not change the relative position of the points and the halfplanes that belong to the
same instance I0
j, as the transformation affects all coordinates similarly. Thus, the original
4.4 A Lower Bound for the Nash Equilibrium Verification Problem 55
instance Iis positive exactly if I0
jis positive for all j∈ {1,2,3,4}.
For each j∈ {1,2,3,4}we now obtain from I0
jan instance I00
j. For each halfplane of
I0
j, given by its base point and its normal vector, we compute the slope and vertical axis
intercept of its boundary line. As all normal vectors lie in the 2nd quadrant we obtain
positive slopes only. Now we shift all lines and points in positive x-axis direction such
that afterwards all of the npoints have a positive x-coordinate. The amount by which
we have to shift can be computed by seeking the minimal x-coordinate of any point and
adding an arbitrary positive constant. After that we compute the minimal y-coordinate
ymin of a point and the maximal y-axis interception ymax of a line in the modified (by the
shift in positive x-axis direction) instance we obtained from I0
j. If ymax ≥ymin, then some
point lies below some line and we may report that the instance is negative immediately.
Otherwise, we shift all lines and points by (ymax +ymin)/2in negative y-axis direction.
Both steps do not affect the relative position of the lines and points, but now all lines have
negative y-axis intercepts and all points have positive coordinates.
As the number of lines in I0
j,mj, might be lower than the number of points, n, the last
step is to copy one of the lines n−mjtimes. Let us denote the instance we obtained from
I0
jin this way by I00
j. Then, for j∈ {1,2,3,4},I00
jis an instance for P3, and I, the original
instance for P2, is positive, exactly if for all j∈ {1,2,3,4}I00
jis positive for P3.
Problem P2is very similar to the Halfspace Emptiness Problem for the two dimen-
sional case, which is well known in the area of computational geometry (see e.g. [22]).
In both cases a set of points and a set of halfplanes is given. P2asks whether every point
lies in every halfplane. The halfspace emptiness problem asks whether all halfplanes are
empty, which is exactly the case if every point lies in the complement of every halfplane.
But as the halfplanes are closed, their complements are open halfplanes, that is, they do
not contain their boundaries. In order to get closed halfplanes, open halfplanes are re-
quired as input. Hence, one could consider P2as the two dimensional Open Halfspace
Emptiness Problem which asks whether, given a set of open halfplanes and a set of points,
all halfplanes are empty. The following lemma shows that we can reduce P1, a combina-
torial problem, to P2.
Lemma 4.11. P1≤O(n)
const−TP2.
Proof. Let a1,...,an, b1,...,bn, c1,...,cn∈Rbe an input to P1. If for some i∈[n]
ai≥bi, then the instance is negative. Otherwise, define x:R→Rand y:R→Rby
x(r) = 1−r2
1+r2and y(r) = 2r
1+r2, and set gi= (x(ai), y(ai)),hi= (x(bi), y(bi)) and pi=
(x(ci), y(ci)) for all i∈[n]. We now construct an input to P2.p1,...,pnare the points of
the input to P2. The halfplanes of the P2input are given by their base points q1= (g1+
h1)/2,...,qn= (gn+hn)/2and normal vectors n1=−q1,...,nn=−qn. Figure 4.4
shows a plot of the two functions used to map a real number of the P1instance to the
horizontal and vertical coordinate of a point in the plane. As (x(r))2+ (y(r))2= 1 for
any r∈R, the set of real numbers is mapped to the unit circle in the plane with its center
at the origin. Figure 4.5 (left) illustrates this mapping, where the set of real numbers is
shown as the vertical line ((1, r))r∈R. A number cjof the P1instance translates to a point
56 4 The Nash Equilibrium Verification Problem
−10 −5 0 5 10
r
−1
−0.5
0
0.5
1
x/y
x(r)
y(r)
Figure 4.4: x(r) = 1−r2
1+r2and y(r) = 2r
1+r2
of the P2instance that lies on the unit circle and an interval of the P1instance translates
to a halfplane of the P2instance whose boundary line is a secant of the unit circle (see
Figure 4.5 (right)). If a number ci, i ∈[n], is contained in an interval (aj, bj), j ∈[n], in
the P1-instance, then point pilies out of halfplane jin the P2-instance, and vice versa.
That is, the P2-instance is positive, exactly if the P1instance is positive.
Finally, we bound the complexity of problem P1from below using Ben-Or’s theorem.
Lemma 4.12. Every algebraic computation tree that decides P1-instances with input size
n, has depth at least Ω(nlog n).
Proof. Let W={I= (a1,...,an, b1,...,bn, c1,...,cn)∈R3n|Iis positive for P1}be
the set of positive P1instances.
The instance with ai=i+ 0.25, bi=i+ 0.75 and ci=σ(i)for i∈[n]is positive
for any permutation σon [n]. There are n!permutations which yield n!distinct inputs to
P1. All of them lie in different connected components of W, because there is no way to
get from one to the other by continuously mutating the input vector without obtaining a
negative instance. Thus, the number of disjoint connected components of Wis at least n!.
The theorem of Ben-Or (see Theorem 4.6) implies that for the height hof any algebraic
4.4 A Lower Bound for the Nash Equilibrium Verification Problem 57
x
y
pj
pk
hi
gi
niqi
interior of
halfplane i
exterior of
halfplane i
x
y
Figure 4.5: Left: Mapping the real numbers to the unit circle. Right: An interval is trans-
formed to a halfplane.
computation tree deciding P1we have
2h3n+h≥n!
⇒hlog 2 + (n+h) log 3 ≥log n!
⇒h≥log n!−nlog 3
log 2 + log 3 = Ω(log n!−n) = Ω(nlog n).
Theorem 4.13. Every algebraic computation for the Nash Equilibrium Verification Prob-
lem takes at least Ω(n+mlog m)steps in the worst case, where nis the number of users
and mis the number of links.
Proof. The claim follows from Lemma 4.9-4.12 and the fact that processing the input
takes Ω(n+m)steps.
58 4 The Nash Equilibrium Verification Problem
5
Parallel Links with Restricted
Capacity
In this chapter we explore non-cooperative routing on parallel links which cannot process
an arbitrary amount of flow.
In Section 5.1 we assume that the links behave like M/M/1queues. The congestion
on a link is bounded by its capacity. The latency function for link j∈[m]is lj(x) = 1
cj−x
where cjis the capacity of link j.
In Section 5.2 we extend the KP model by an additional constraint. Each link has an
associated capacity which gives the size of the maximal user traffic that may be routed
along that link.
5.1 Parallel M/M/1-Queues
5.1.1 Motivation
Assume we have nusers that wish to send streams of packets at different rates r1, . . . , rn.
That is, riis the average number of packets per unit of time that have to be delivered for
user i. The arrivals are randomly spaced in time and the interarrival times are distributed
exponentially. Each user can choose one of mparallel links to route its stream. Each
link represents a queue with exponentially distributed service times. This setting can be
modeled by parallel M/M/1-queues (according to Kendall’s notation, see e.g. [11]). It is
well known that the expected delay of such a queue is 1
c−x, where cis the service rate and
xis the expected arrival rate for that queue [11]. The arrival rate must be smaller than the
service rate, otherwise the expected delay is unbounded.
60 5 Parallel Links with Restricted Capacity
5.1.2 Definition
In accordance with our notation in previous chapters, we speak of user weights or user
flows, denoted w1,...,wn, instead of rates. We define the latency function of link j∈[m]
as lj(x) = 1
cj−xfor x < cj, where cjis the capacity of link j(corresponding to the service
rate) and xis the link flow (corresponding to the arrival rate). We assume that the latency
becomes infinitely large as the flow on a link attains or goes beyond its capacity. The
social cost of an assignment Ais defined as SC(A) = SCMAX(A), as in the KP model.
We denote an instance of the routing model with parallel M/M/1-queues as I= (w,c).
5.1.3 Optimal Routing and Approximation
Assume the flows w1,...,wn∈Nof n= 3musers are given. Set all capacities to
cj=W/m +1
2for j∈[m], where Wis the total flow. An assignment Afor the resulting
instance can only have bounded social cost, if all flows are distributed equally among the
links, that is, if xj(A) = W/m for all j∈[m]. Obviously, this yields a reduction from
the 3-PARTITION Problem which is known to be NP -complete in the strong sense [36]
on the problem to decide whether there exists a routing with bounded social cost for a
given instance of the routing model with parallel M/M/1-queues. Hence, this problem
is NP-complete even for identical links. Furthermore, the computation of an optimal
assignment or any constant factor approximation is NP-complete as well.
Hence, there does not exist a polynomial -approximation algorithm for identical links
for any > 0, unless P=NP. Henceforth, we investigate the dual approximation. Let an
instance I= (w,c)with identical links be given by the vector of user weights w∈Rn
>0
and the link capacity vector c= (c, . . . , c)∈Rm
>0. That is, cis the common capacity
of all links. An -primal approximation for the routing problem on Iis an assignment
Awith social cost SC(A, I)≤(1 + )OPT(I)where SC(A, I) = maxj∈[m]1
cj−xj(A).
A dual approximation achieves optimal social cost but at the price of capacity dilation.
That is, if Ais an -dual approximation, then SC(A, I)≤OPT(I)where SC(A, I) =
maxj∈[m]1
(1+)cj−xj(A). Note that we define any assignment to be optimal, if the optimal
social cost is unbounded.
Hochbaum and Shmoys [41] have developed an -approximation scheme for the Min-
imal Makespan Problem on identical machines, or, equivalently, for the routing problem
in the KP model with identical links (see Section 3.3). We will now show that every -
primal approximation for the routing problem in the KP model with identical links is an
-dual approximation for the routing problem on identical parallel M/M/1-queues.
Lemma 5.1. For an instance I= (w,s)of the KP model with identical links and > 0let
assignment Abe an -approximation for the routing problem on I. Then, Ais an -dual
approximation for the routing problem on an instance ˜
I= (w,c)of the routing model
with identical parallel M/M/1-queues and c=s.
Proof. From the assumption of the lemma we get that
SC(A, I) = max
j∈[m]
xj(A)
sj≤(1 + )OPT(I).
5.1 Parallel M/M/1-Queues 61
This implies xj(A)≤(1 + )sjOPT(I)for all j∈[m]. If OPT(˜
I) = ∞, then any
assignment is an -dual approximation and nothing is to show. Otherwise we know that
there exists an assignment A∗(the optimal assignment for ˜
I) with xj(A∗)< cj=sjfor
all j∈[m]. Hence, OPT(I)≤SC(A∗, I)<1, which implies SC(A, I)<(1 + )or,
equivalently, xj(A)<(1 + )sj= (1 + )cjfor all j∈[m]. Let c0
j,j∈[m], be the
extended link capacities for the M/M/1-links. That is, c0
j= (1 + )cj. Then
1
c0
j−xj(A)≤1
(1 + )cj−(1 + )cjOPT(I)=1
1 + ·1
cj·1
1−OPT(I)
for all j∈[m]. Note that all denominators are positive. We claim that
1
1 + ·1
cj·1
1−OPT(I)≤OPT(˜
I)
for all j∈[m]which would conclude the proof, since then
1
c0
j−xj(A)≤OPT(˜
I)
for all j∈[m].
Assume, by way of contradiction, that this is not true. Then, for an optimal assignment
A∗according to ˜
I, we have
1
1 + ·1
cj·1
1−OPT(I)> OPT(˜
I)≥1
cj−xj(A∗)
for all j∈[m](recall that the link capacities cj, j ∈[m], are all the same). This implies
that cj−xj(A∗)> cj(1 −OPT(I)), or equivalently,
xj(A∗)
cj
=xj(A∗)
sj
< OPT(I)
for all j∈[m], a contradiction, since there cannot exist an assignment for Iwith social
cost less than OPT(I).
With Lemma 5.1 and the approximation scheme from Hochbaum and Shmoys we
obtain a polynomial -dual approximation scheme for the routing problem on identical
parallel M/M/1-links.
5.1.4 Nash Equilibria
According to our definition, the latency on a link becomes infinitely large when the con-
gestion attains or exceeds the link capacity. That is, lj(x) = ∞for x≥cj. We do not
distinguish to which extent the congestion exceeds the capacity.
The coordination ratio for routing on parallel M/M/1-links is unbounded, even for
identical links. To see this, consider four users with weights w1=w2= 2 and w3=w4=
62 5 Parallel Links with Restricted Capacity
1on two links with capacity c1=c2= 4. If both of the large users go to the first and both
of the small users go to the second link, then no user can decrease its cost by switching to
the opposite link. The latency experienced by the large users, and hence the social cost of
this Nash equilibrium assignment, is infinitely large. The optimal assignment has social
cost 1(one small and one large user on each link).
Any assignment on not necessarily identical parallel M/M/1-links can be transformed
into a Nash equilibrium by performing greedy steps for the users in order of non-increasing
weights. After one sweep over all users a Nash equilibrium is reached. This approach was
described in [50]. Note, that the same approach works for Nashification in the KP model
with identical links (see the discussion after Lemma 3.1 in Section 3.4). In both cases a
greedy step of some user cannot cause a smaller or equally sized user to become unsat-
isfied. A greedy step places an unsatisfied user to the minimal latency link. If the links
are kept in a priority queue this can be done in time O(log m)with precomputation time
O(mlog m). Hence, it takes time O(nlog n+ (m+n) log m)to Nashify an assignment.
On the other hand, if the user to perform a greedy step is chosen randomly, then the
number of steps until a Nash equilibrium is reached can be superpolynomial in the worst
case, as stated by the following lemma.
Lemma 5.2. For any k∈Nthere exists an instance I= (w,c)of the routing model
with identical parallel M/M/1-links and n≥kusers, such that the worst case number
of greedy steps is at least 2.829√n−4.
Proof. For k∈Nlet I0=I(m, 7) = (w,s)be an instance of the KP model according to
Definition 3.8 with n≥kusers. Let I= (w,c)be an instance of the routing model with
identical parallel M/M/1-links having common link capacity c= 1 + Pi∈[n]wi. Then,
starting with an initial assignment where all users go to the first link and successively
performing greedy steps for the respective smallest unsatisfied user (STF selection rule)
yields a sequence of at least 2.829√n−4steps. The proof for this follows from the proof of
Theorem 3.9 and the discussion after, since the same steps are carried out here as for the
KP instance I0under the STF policy.
5.1.5 Generalization
The results of this section hold for a more general model with link capacities as well.
Assume the latency on link j∈[m]is defined as lj(x) = f(cj−x), where f:R→R≥0
is a common non-increasing function for all links. That is, in this model the latency of
a link (or, put in a more general context, the cost of a resource) depends on its unused
capacity. The closer it is filled up to its capacity, the more costly it becomes to route
additional flow along the link. In [50] such a system is called residual capacity atomic
non-cooperative network. The model with M/M/1-links is a special case where fis de-
fined by f(y) = 1
y. Another reasonable choice for fis f(y) = 1
ey. In this case the latency
can equivalently be defined as lj(x) = ajex. Libman and Orda explore the model with
arbitrary non-increasing function fin [50]. They show that Nashification can be done in
nsteps. Concerning the problem to compute an optimal assignment for an instance with
5.2 Related Links with Weight Restriction 63
identical links, one can show that an -dual approximation scheme exists for any choice
of f. We omit the proof, because it is quite the same as that of Lemma 5.1.
5.2 Related Links with Weight Restriction
In this section we turn our attention to a model similar to the KP model but with additional
restrictions for the maximal user traffic on a link. Let us name this model the KP model
with weight constraints.
5.2.1 Definition
An instance of this model is a tuple I= (w,s,u)consisting of the vector of user weights
w= (w1,...,wn), the vector of link speeds s= (s1,...,sm)and the vector of maximal
traffic sizes u= (u1,...,um). That is, link jcan handle only user flows of size at most
uj. A routing Ais feasible, if it obeys this additional weight constraint, i.e., if
wi≤uA(i)for all i∈[n].(5.1)
5.2.2 Computation of Nash Equilibrium
For any instance of this model, the LPT-algorithm, which assigns the users one by one to
their respective best feasible link, computes a Nash equilibrium. This follows from the
fact that according to the LPT-algorithm the users are taken up in order of non-increasing
traffic size. Hence, when a user is placed, its set of feasible links contains all links that
are feasible for any user that has already been assigned. This ensures that the arguments
in the proof (see [29]) of the fact that LPT yields a Nash equilibrium in the KP model
without constraints still work for the KP model with weight constraints.
Let us make an additional assumption. It is reasonable that, comparing two different
links, a more powerful link can handle larger pieces of user flow and has higher speed as
well. We hence constitute that the larger the maximal traffic size a link can handle is, the
greater its speed must be. That is,
ui> uj⇒si> sjfor all i, j ∈[m].(5.2)
The remainder of this section refers to the model with this presumption. Note that nothing
is implied for the speeds of two links iand j, if ui=uj. Thus, if we set uj= maxi∈[n]wi
for all j∈[m], then we obtain an instance that conforms to the original KP model. The
KP model is hence a special case of the KP model with weight constraints and with 5.2.
5.2.3 Approximation of Optimum
The Computation of an optimal routing remains of course NP- complete in the con-
strained model. But we can apply the approximation scheme for makespan minimization
64 5 Parallel Links with Restricted Capacity
on related machines from Hochbaum and Shmoys [42] with some modifications to com-
pute an -approximation, i.e., an assignment with social cost at most (1 + )times the
optimal social cost, for any > 0in polynomial time.
We give here a description of the modifications on the algorithm from Hochbaum
and Shmoys in [42]. We will use their terminology and definitions without explicitly
mentioning. So, the next few paragraphs are not self contained and it is advisable to read
[42] first.
The algorithm is based on an -relaxed decision procedure for Bin Packing. In this
context, the link speeds s1,...,smare called bin sizes and the user weights w1, . . . , wnare
termed piece sizes. Without loss of generality, we assume s1≥ ··· ≥ sm. Given B > 0,
the decision procedure either computes a packing of the pieces for bin sizes (1+)Bsjor
reports that no packing with bin sizes Bsjexists. This decision procedure is executed re-
peatedly in a binary search loop. Bis the binary search variable. We only have to modify
the decision procedure which is based on dynamic programming. It builds up a layered
graph, where each vertex corresponds to a state vector describing the distribution of un-
packed pieces, i.e., an entry of the vector gives the number of pieces whose rounded size
attains some certain value associated with that entry (see [42] for details on the rounding
procedure). Each edge between two subsequent layers corresponds to packing one bin by
large and medium pieces. Additionally, there are update layers which care for pieces that
are packed as small pieces (see [42] for the definition of large, medium and small pieces).
The layers are ordered according to the bin sizes. That is, the vertices in layer j∈[m]
represent the possible state vectors before packing bin j, and layer j+1 contains one ver-
tex for each possible state vector after packing bin j. Consider layer jof the graph. Each
vertex of this layer is labeled with a vector (L;M;V1, V2, V ), where vectors Land M
describe the distribution of unpacked large and medium pieces, and V1, V2and Vstore the
unused slack in enormous,huge and large bins (see [42] for the definition of enormous,
huge and large bins).
After building up the graph, a path from the initial vertex (representing the state where
all pieces are unpacked) to the success vertex (corresponding to the state where all pieces
are packed) has to be found by depth first search. If no such path exists, then we may
return from the decision procedure and report failure. Otherwise, the path found corre-
sponds to an -relaxed packing.
Our modifications in order to adapt the decision procedure to the case where the max-
imal piece size for a bin j∈[m]is bounded by ujconcern the depth first search. We
have to take care that these additional constraints are not violated during the evolvement
of the depth first search path. Assume the path has reached some vertex in layer j. Ac-
cording to the depth first search algorithm we have to examine all outgoing edges of that
vertex. In the modified algorithm we will not follow up edges that represent a packing
of bin jwhich involves pieces that violate the weight constraint for this bin. Let us call
those edges infeasible edges. To determine wether the weight constraint is violated, we
have to compare the real piece sizes to the capacity ujof bin j. Note that an edge does
not describe exactly which pieces are packed into the bin, but only how many pieces of
each subinterval in the interval of large and medium pieces have to be assigned to the bin.
During building up the path, we mark each piece that is assigned to some bin with the
5.2 Related Links with Weight Restriction 65
index of that bin. Unpacked pieces remain unmarked. If the packing represented by an
edge puts ppieces of some subinterval into bin j, then we mark the plargest unpacked
pieces of this subinterval that do not violate the weight constraint of bin j. If not enough
such pieces are available, then the edge is infeasible.
The second modification concerns the packing of small pieces. After all bins whose
sizes lie in the same interval (k+1, k]are packed, the remaining large pieces are packed as
small pieces in enormous bins. Therefor the unused slack of the enormous bins is stored
in an entry V1of the state vector. In the modified algorithm we again have to care for the
weight constraints not to be violated in this step. Assume the depth first search procedure
is examining an edge that represents the packing of pieces as small pieces. Since we have
marked all pieces packed so far with the index of their bin, we can compute the unused
slack of any eligible bin. We grep up the small pieces to be packed in non-increasing order
and pack each in the bin with the largest capacity that has unused slack. If we come across
a piece that cannot be packed without violating the weight constraint, then the examined
edge is infeasible. Note that we do not constrict the possibilities to pack small pieces in
further stages in any way, as all small pieces packed later are smaller than the small pieces
considered here.
By the two modifications on the PTAS for machine scheduling described above, we
get a PTAS for the KP routing model with weight constraints obeying (5.2). We omit a
formal proof here and refer the reader to [42].
5.2.4 Nashification
In Chapter 3 we presented an algorithm Nashify (see Figure 3.1) to convert any pure
assignment for an instance of the KP model into a pure Nash equilibrium without increas-
ing its social cost. Algorithm Nashify works for the KP model with weight constraints
(and with (5.2)) as well, if it is modified such that users can only be put on those links
where the weight constraint is not violated.
We make use of Proposition 3.5 to prove this fact. Instead of modifying the algorithm,
we define the link latency functions such that no user will be placed on a link where it
would violate the weight constraint (5.1). Let I= (w,s,u)be an instance of the KP
model with weight constraints. Define lj: 2[n]→R≥0, the latency function for link
j∈[m], by
lj(U) = (Pi∈Uwi
sjif ∀i∈U:uj≥wi
M+Pi∈Uwi
sjif ∃i∈U:uj< wi
,(5.3)
where M=Wmaxk∈[m]sk
mink∈[m]sk+ 1. Starting algorithm Nashify on I0= (l)and any assign-
ment Athat is feasible for I, it will at no time produce an unfeasible assignment. We state
this as a lemma.
Lemma 5.3. Let I= (w,s,u)be an instance of the KP model with weight constraints,
and let Abe a feasible assignment for I. Furthermore, let I0= (l)be an instance of
the generic routing model obtained from Iaccording to (5.3). Let A0be any assignment
66 5 Parallel Links with Restricted Capacity
generated during the execution of Nashify on input (I0, A). Then, no user violates the
maximal weight constraint (5.1) in A0.
Proof. Assume the opposite, i.e., there is a user i∈[n]assigned to link j=A0(i)such
that uj< wi. As the social cost of A0for instance I0is at least the latency on link j, we
get
SC(A0, I0)≥lj({k∈[n]:A(k) = A(i)}) = M+Pk∈[n]:A(k)=A(i)wk
sj
≥M
sj
=Wmaxk∈[m]sk
mink∈[m]sk
+ 11
sj
>W
mink∈[m]sk
≥SC(A, I0).
This contradicts the fact that algorithm Nashify does not increase the social cost through-
out its execution.
The following lemma is the last step until we are ready to state the main result of this
section in Theorem 5.5.
Lemma 5.4. Let I= (w,s,u)be an instance of the KP model with weight constraints
obeying (5.2). Let Abe any feasible assignment for I. Let the users and links be numbered
such that wand sare sorted non-increasingly, i.e., wi≥wi+1 and sj≥sj+1 for all
i∈[n−1], j ∈[m−1]. Define a corresponding instance I0= (l)of the generic routing
model with nusers and latency functions l= (l1,...,lm)according to (5.3). Then,
properties (i), (ii) and (iii) of Proposition 3.5 are fulfilled for I0and A.
Proof. Note that the non-increasing order of the entries of simplies that uis sorted non-
increasingly, too, because of (5.2). We first prove that property (i) of Proposition 3.5
holds. Let j∈[m], i ∈[n−1] and U⊆[n]−{i, i + 1}be arbitrary. Then
lj(U∪{i}) = wi+Pk∈Uwk
sj
+(0if ∀k∈U∪{i}:uj≥wk
M
sjif ∃k∈U∪{i}:uj< wk
,
and
lj(U∪{i+ 1}) = wi+1 +Pk∈Uwk
sj
+(0if ∀k∈U∪{i+ 1}:uj≥wk
M
sjif ∃k∈U∪{i+ 1}:uj< wk
.
Since wi+1 ≤wi,(∃k∈U∪{i+ 1}:uj< wk)implies (∃k∈U∪{i}:uj< wk). It
follows that lj(U∪{i})≥lj(U∪{i+ 1}).
To prove (ii), set Mj(U) = Mif ∃i∈U:uj< wi, and set Mj(U) = 0 otherwise
for all j∈[m], U ⊆[n]. Let A0and A00 be any two consecutive assignments that are
attained during the execution of algorithm Nashify on input (I, A). Let user ibe the
unique user whose link is changed during the transition from A0to A00. Denote j=
A0(i)and k=A00(i). Set U=view(j, A0)\{i}={r∈[n]\{i}|A0(r) = j}and
5.2 Related Links with Weight Restriction 67
V=view(k, A0) = {r∈[n]|A0(r) = k}. Define xj=Pr∈Uwrand xk=Pr∈Vwr.
Assume j > k, and let r∈[n]\Uwith r < i be arbitrary. Then,
lj(U∪{r})−lk(V∪{r})−(lj(U∪{i})−lk(V∪{i}))
=xj+wr+Mj(U∪{r})
sj−xk+wr+Mk(V∪{r})
sk
−xj+wi+Mj(U∪{i})
sj−xk+wi+Mk(V∪{i})
sk
= (wr−wi)1
sj−1
skMj(U∪{r})−Mj(U∪{i}
sj−Mk(V∪{r})−Mk(V∪{i})
sk
≥Mj(U∪{r})−Mj(U∪{i})
sj−Mk(V∪{r})−Mk(V∪{i})
sk
.
The last estimation makes use of the fact that wr≥wiand that sk≥sj. Note that
Mj(U∪{i}) = Mimplies uj< wiand hence that A0is infeasible for I, contradicting
Lemma 5.3. Similarly, Mk(U∪{i}) = Mimplies uk< wiand hence that A00 is infeasible
for I. Again, this contradicts Lemma 5.3. So, we have Mj(U∪{i}) = 0 and Mk(U∪
{i}) = 0. If Mk(V∪{r}) = M, then there is some user v∈V∪{r}with uk< wv. If
v6=r, then A0is infeasible for I, since A0(v) = k. But v=rimplies wr> uk≥uj, and
consequently Mj(U∪{r}) = M. Thus,
lj(U∪{r})−lk(V∪{r})−(lj(U∪{i})−lk(V∪{i}))
≥Mj(U∪{r})−Mj(U∪{i})
sj−Mk(V∪{r})−Mk(V∪{i})
sk
≥0,
which implies (ii) of Proposition 3.5.
To show (iii) consider any assignment A0and any link j. Set U=view(j, A0)\{i}.
Then, for any user i,
lj(U∪{i}) = wi+Pk∈Uwk
sj
+(0if ∀k∈U∪{i}:uj≥wk
M
sjif ∃k∈U∪{i}:uj< wk
≥Pk∈Uwk
sj
+(0if ∀k∈U:uj≥wk
M
sjif ∃k∈U:uj< wk
=lj(U).
It is now simple to prove that Nashify works for the model considered here.
Theorem 5.5. Let I= (w,s,u)be an instance of the KP model with weight constraints,
and let Abe any feasible assignment for I. Then, algorithm Nashify can be used to
Nashify A.
68 5 Parallel Links with Restricted Capacity
Proof. Renumber the users and links such that wand sare sorted non-increasingly, that
is, wi≥wi+1 and sj≥sj+1 for all i∈[n−1], j ∈[m−1]. Define an instance I0= (l)of
the generic routing model with nusers and latency functions l= (l1, . . . , lm)according
to (5.3). Due to Lemma 5.4 and Proposition 3.5 Nashify Nashifies Aaccording to
I0. Due to Lemma 5.3 A0is feasible for I. Hence, A0is also a Nash equilibrium with
non-increased social cost according to I.
6
Nash Equilibria of Identical Users
on Parallel Links
In this chapter we explore Nash equilibria of identical users on parallel links with quite
general latency functions. We measure the social cost as the weighted (by the users’ traffic
sizes) average user cost, that is, SC(A, I) = SCAV G(A, I), or, equivalently, SC(A, I) =
SCMAX (A, I), since both definitions coincide in case of identical users. We hence adopt
the social cost definition of the Wardrop model. But in contrast to the Wardrop model
we deal with atomic flows which may not be split. Thus, in this aspect we follow the KP
model.
Section 6.1 is concerned with pure Nash equilibria. Here, we first prove that the
coordination ratio is exactly 4
3if we restrict to related links (i.e., with latency functions
lj(x) = x
sj). Furthermore, we give bounds on the coordination ratio for almost arbitrary
latency functions that depend on the growth of the functions. Finally, we state a fast and
simple algorithm to compute a Nash equilibrium and an optimal assignment.
Section 6.2 addresses general (mixed) Nash equilibria on links with arbitrary con-
vex, non-decreasing and non-constant latency functions. In this setting the so called fully
mixed Nash equilibrium has the worst social cost, if it exists. It is a special mixed Nash
equilibrium where each user selects every link with strictly positive probability. We point
out the important role of convex latency functions in this setting. Furthermore, we show
that the fully mixed Nash equilibrium is unique if it exists and characterize the set of
instances for which it does not exist. At last we show that the social cost of any Nash
equilibrium for a given instance is bounded by that of the fully mixed Nash equilibrium
for the instance induced by the links that are "sufficiently fast" when processing one user.
70 6 Nash Equilibria of Identical Users on Parallel Links
6.1 Pure Nash Equilibria
6.1.1 Coordination Ratio for Related Links
We will now prove the following theorem which states that the coordination ratio for pure
Nash equilibria of identical users on related links is exactly 4
3. The proof also reveals the
very special structure of a worst case Nash equilibrium.
Theorem 6.1. Consider any instance Iof the congestion routing model with identical
users and related links. Then,
max
A∈N(I)
SC(A, I)
OPT(I)=4
3.
To prepare the proof of Theorem 6.1, we first show an optimality criterion for our
model (Lemma 6.2) and make some claims about the structure of a worst case Nash
equilibrium (Lemma 6.3, 6.4 and 6.5). The proof will then derive a contradiction from
the existence of an instance with coordination ratio larger than 4
3. Note that the model
under consideration is a special case of the congestion routing model with related links.
We may hence denote an instance of this model as I= (w,s). Our first lemma shows
that an assignment has optimal social cost exactly if it is locally optimal, i.e., if the social
cost cannot be decreased by reassigning a single user.
Lemma 6.2. Let Abe any pure assignment for an instance I= (w,s)of the congestion
routing model with identical users and related links, and let w= (w, . . . , w). Then, Ais
an optimal assignment, i.e., SC(A, I) = OPT(I), if and only if for every pair of links
i, j ∈[m]
(xi(A) + w)2
si
+(xj(A)−w)2
sj≥(xi(A))2
si
+(xj(A))2
sj
.
Proof. 1. ’⇒’: Let Abe an optimal assignment. If we create a new assignment A0by
shifting one user from link jto link ifor some i, j ∈[m], we get
SC(A0) = SC(A) + (xi(A) + w)2
si
+(xj(A)−w)2
sj−(xi(A))2
si−(xj(A))2
sj
for the social cost of A0. Now, SC(A0)≥SC(A)yields the above inequality.
2. ’⇐’: Let A∗be an optimal assignment, and let Abe any assignment, for which the
above inequality holds. Let xj=xj(A)and x∗
j=xj(A∗)be the traffic of link j∈[m]
according to Aand A∗, respectively. According to the first part of this proof we have
(x∗
j+w)2
sj
+(x∗
i−w)2
si≥(x∗
i)2
si
+(x∗
j)2
sj
⇔2x∗
jw+w2
sj≥2x∗
iw−w2
si
for all i, j ∈[m](6.1)
6.1 Pure Nash Equilibria 71
By assumption,
(xi+w)2
si
+(xj−w)2
sj≥x2
i
si
+x2
j
sj
⇔2xiw+w2
si≥2xjw−w2
sj
for all i, j ∈[m].(6.2)
If xj=x∗
jfor all j∈[m], then SC(A) = SC(A∗)and nothing is to show. Hence, we
may assume that there exist links i, j ∈[m]with x∗
i−xi>0and xj−x∗
j>0. I.e.,
link ihas more traffic according to A∗than according to A, and link jhas more traffic
according to Athan to A∗. As the traffic on any link is a multiple of w, we have
x∗
i−xi≥wand (6.3)
xj−x∗
j≥wfor all i, j ∈[m](6.4)
But this yields
2x∗
jw+w2
sj
(6.1)
≥2x∗
iw−w2
si
(6.3)
≥2xiw+w2
si
(6.2)
≥2xjw−w2
sj
(6.4)
≥2x∗
jw+w2
sj
for all i, j ∈[m]
Notice, that the left and right side of the inequality chain are identical and therefore all
terms must be equal. On the one hand this implies xj=x∗
j+wand x∗
i=xi+w. That
is, for each link, the traffics according to Aand A∗can differ by at most one user. This
implies that the number of links with x∗
i−xi>0and of those with xj−x∗
j>0are equal.
On the other hand we can follow
2x∗
jw+w2
sj
=2xiw+w2
si
⇔x2
i
si
+(x∗
j+w)2
sj
=(xi+w)2
si
+(x∗
j)2
sj
⇔x2
i
si
+x2
j
sj
=(x∗
i)2
si
+(x∗
j)2
sj
for all i, j ∈[m].(6.5)
(6.5) tells us that the contribution of links iand jto the social cost is the same for Aand
A∗. As for every link jthat has a greater traffic according to Athan to A∗there exists some
link ithat has a lower traffic according to Athan to A∗, we have SC(A) = SC(A∗).
The next lemma claims that in an optimal assignment any link carries at most one user
more than according to any Nash equilibrium assignment.
Lemma 6.3. Let I= (w,s)be an instance of the congestion routing model with identical
users and related links, and let A∗and Abe an optimal and a Nash equilibrium assign-
ment, respectively. Without loss of generality, let w= (1,...,1). Then, xj(A∗, I)−
xj(A, I)≤1for all j∈[m].
72 6 Nash Equilibria of Identical Users on Parallel Links
Proof. Denote xj=xj(A)and x∗
j=xj(A∗). Assume the claim is violated for some link
k, i.e.,
xk≤x∗
k−2.(6.6)
Due to Lemma 6.2, optimality of A∗implies for all j∈[m]
(x∗
j+ 1)2
sj
+(x∗
k−1)2
sk≥(x∗
j)2
sj
+(x∗
k)2
sk
⇔2x∗
j+ 1
sj≥2x∗
k−1
sk
⇔x∗
j
sj≥2x∗
k−1
2sk−1
2sj
.(6.7)
Since Ais at Nash equilibrium,
xj
sj≤xk+ 1
sk
for all j∈[m].(6.8)
Now, let jbe some link with
xj≥x∗
j+ 1 .
Such link exists, because Pi∈[m]x∗
i=Pi∈[m]xi=n. Then,
2x∗
k−1
2sk−1
2sj
+1
sj
(6.7)
≤x∗
j+ 1
sj≤xj
sj
(6.8)
≤xk+ 1
sk
(6.6)
≤x∗
k−1
sk
⇒1
2sk
+1
2sj≤0,
a contradiction.
The following lemma reveals the very special structure of any minimal example of an
instance with coordination ratio greater than a given constant.
Lemma 6.4. Let I= (w,s)be a minimal (in the number of links) instance of the con-
gestion routing model with identical users and related links for which a Nash equilibrium
assignment Aexists, such that SC(A,I)
OP T (I)> ρ for a given ρ∈R≥1. Without loss of gener-
ality, let w= (1,...,1). Then, xk(A, I) = xk(A∗, I) + m−1for some k∈[m], and
xj(A, I) = xj(A∗, I)−1for all j∈[m]\{k}, where A∗is an optimal assignment for I.
Proof. Let A∗be an optimal assignment for I, and let Abe a Nash equilibrium with
SC(A)
SC(A∗)> ρ. First, let us assume that there exists some link kwith xk(A) = xk(A∗).
Then, removing that link and all associated users yields a new instance with coordination
ratio
ρ0=SC(A)−(xk(A∗))2/sk
SC(A∗)−(xk(A∗))2/sk
.
6.1 Pure Nash Equilibria 73
ρ0<SC(A)
SC(A∗)would imply
(SC(A)−(xk(A∗))2/sk)SC(A∗)< SC(A)(SC(A∗)−(xk(A∗))2/sk)
⇔SC(A∗)> SC(A),
a contradiction, since A∗has minimal social cost. Hence, the new instance has at least
the same coordination ratio but fewer links, which contradicts our assumption that Iis a
minimal instance with coordination ratio greater than ρ.
Now, assume more than one link have xj(A)≥xj(A∗) + 1, and let link kbe one of them.
By Lemma 6.3 and the first part of this proof, all links with xj(A)xj(A∗) + 1 have
xj(A) = xj(A∗)−1. Note that there must exist at least (xk(A)−xk(A∗)) such links and
let Sbe a set of exactly (xk(A)−xk(A∗)) such links. Setting
C=X
j∈[m]\({k}∪S)
(xj(A))2
sj
,
D=X
j∈[m]\({k}∪S)
(xj(A∗))2
sj
,
E=X
j∈S∪{k}
(xj(A))2
sj
and
F=X
j∈S∪{k}
(xj(A∗))2
sj
,
we can write the coordination ratio of Aas
SC(A)
SC(A∗)=Pj∈[m]
(xj(A))2
sj
Pj∈[m]
(xj(A∗))2
sj
=C+E
D+F.
Either C
D>E
F, or C
D≤E
F. In the first case we can remove the links in S∪{k}together
with the users assigned to them, obtaining an instance I1with fewer links. Let A1be the
subassignment of Ainduced by I1. Of course A1remains a Nash equilibrium for I1. Also
the subassignment of A∗induced by I1remains optimal for I1. Hence I1has coordination
ratio at least C
D>C+E
D+F> ρ. Similarly, in the second case, we can remove all links in
[m]\(S∪{k})and their associated users, obtaining an instance I2with fewer links and
at least the same coordination ratio at least E
F≥C+E
D+F> ρ. Both cases contradict the
assumption, that Ihas minimal number of links among all instances with coordination
ratio greater than ρ.
Lemma 6.5. Let I= (w,s)be a minimal (in the number of links) instance of the con-
gestion routing model with identical users and related links, with a worst case Nash
equilibrium assignment Aand an optimal assignment A∗, such that SC(A,I)
SC(A∗,I)> ρ for
a given ρ∈R≥1. Without loss of generality, let w= (1,...,1). Then, there exists
74 6 Nash Equilibria of Identical Users on Parallel Links
an instance ˜
I= (˜w,˜s)that has the same number mof links as I, with optimal assign-
ment ˜
A∗and Nash equilibrium assignment ˜
A, such that xk(˜
A, ˜
I) = xk(˜
A∗,˜
I) + m−1
for some link k∈[m],xi(˜
A∗,˜
I) = xj(˜
A∗,˜
I)and ˜si= ˜sjfor all i, j ∈[m]\{k}and
SC(˜
A,˜
I)
SC(˜
A∗,˜
I)≥SC(A,I)
SC(A∗,I).
Proof. Let k∈[m]be the link with xk(A) = xk(A∗) + m−1due to Lemma 6.4. Let
S⊂[m]\{k}be a maximal set of links, such that xi(A∗) = xj(A∗)and si=sjfor all
i, j ∈S, and let s=|S|be the cardinality of S. If s=m−1, then the claim holds. Other-
wise let i∈[m]\(S∪{k})be arbitrary. Note that xi(A) = xi(A∗)−1for all i∈[m]\{k}
due to Lemma 6.4. We now obtain two new instances I1= (w0,s0)and I2= (w00,s00)
from I= (w,s)and corresponding pairs of assignments A1, A∗
1and A2, A∗
2by
a) setting the traffic of link iaccording to A1and A∗
1to the traffic of the links in S
according to Aand A∗, respectively (this yields A1and A∗
1); and setting the speed
of link ito the speed of the links in S(this yields I1),
that is s0
j:= st,xj(A1) := xt(A)and xj(A∗
1) := xt(A∗)for all j∈S∪ {i}and
t∈Sarbitrary, and s0
j:= sj,xj(A1) := xj(A)and xj(A∗
1) := xj(A∗)for all
j∈[m]\(S∪{i}).
b) setting the traffic of the links in Saccording to A2and A∗
2to the traffic of link i
according to Aand A∗, respectively (this yields A2and A∗
2); and setting the speed
of the links in Sto the speed of link i(this yields I2)
that is s00
j:= si,xj(A2) := xi(A)and xj(A∗
2) := xi(A∗)for all j∈S∪{i}, and
s00
j:= sj,xj(A2) := xj(A)and xj(A∗
2) := xj(A∗)for all j∈[m]\(S∪{i}).
We will now show that either
SC(A1, I1)
SC(A∗
1, I1)≥SC(A, I)
SC(A∗, I)or SC(A2, I2)
SC(A∗
2, I2)≥SC(A, I)
SC(A∗, I).
Set
C=X
j∈[m]\(S∪{i})
(xj(A))2
sj
,
D=X
j∈[m]\(S∪{i})
(xj(A∗))2
sj
,
e=(xi(A∗)−1)2
si
,
f=(xi(A∗))2
si
,
g=(xj(A∗)−1)2
sj∀j∈Sand
h=(xj(A∗))2
sj∀j∈S .
6.1 Pure Nash Equilibria 75
Then,
SC(A, I)
SC(A∗, I)=C+e+sg
D+f+sh
SC(A1, I1)
SC(A∗
1, I1)=C+ (s+ 1)g
D+ (s+ 1)h
SC(A2, I2)
SC(A∗
2, I2)=C+ (s+ 1)e
D+ (s+ 1)f.
Assume,
SC(A1, I1)
SC(A∗
1, I1)<SC(A, I)
SC(A∗, I)and SC(A2, I2)
SC(A∗
2, I2)<SC(A, I)
SC(A∗, I).
This yields
(C+ (s+ 1)g)(D+f+sh)<(C+e+sg)(D+ (s+ 1)h)
∧(C+ (s+ 1)e)(D+f+sh)<(C+e+sg)(D+ (s+ 1)f)
⇔Cf +Dg + (s+ 1)fg < Ch +De + (s+ 1)eh
∧sCh +sDe +s(s+ 1)eh < sCf +sDg +s(s+ 1)fg
⇒Cf +Dg + (s+ 1)fg < Cf +Dg + (s+ 1)fg ,
a contradiction. A1is a Nash equilibrium for I1, because the Nash equilibrium condition
holds for the links in S(no user can improve by moving from or to one of those links) and
therefore is also valid for link iwhich is a copy of the links in Sin the modified instance.
Similarly, A2is a Nash equilibrium for I2, because the Nash equilibrium condition holds
for link i(no user can improve by moving from or to link i) and hence also for the links
in Swhich are copies of link iin the modified instance. As OPT(I1)≤SC(A∗
1, I1)and
OPT(I2)≤SC(A∗
2, I2), we have either
SC(A1, I1)
OPT(I1)≥SC(A1, I1)
SC(A∗
1, I1)≥SC(A, I)
OPT(I)or SC(A2, I2)
OPT(I2)≥SC(A2, I2)
SC(A∗
2, I2)≥SC(A, I)
OPT(I).
Thus, either I1or I2is an instance with at least the same coordination ratio as instance I.
In both modified instances, the number of equal links (the links in S) has increased
to s+ 1. Thus, by applying this step repeatedly, we eventually equalize all links except
for link kand obtain an instance ˜
Iand assignments ˜
Aand ˜
A∗as stated in the lemma.
Note, that the number mof links remains the same, while the number of users might
change, but that the latter is bounded by mtimes the maximal link congestion according
to assignment Afor the original instance.
Using Lemma 6.5 and 6.2, we are now ready to prove the theorem.
Proof of Theorem 6.1:
We first prove, by way of contradiction, that the coordination ratio is at most 4
3. Hence,
assume that (A, I)is a minimal counterexample. That is, I= (w,s)is a minimal (in
the number of links) instance of the congestion routing model with identical users and
76 6 Nash Equilibria of Identical Users on Parallel Links
related links with a worst case Nash equilibrium A, such that SC(A)
OP T (I)>4
3. Let A∗be an
optimal assignment for I, and, without loss of generality, let w= (1,...,1). Note, that
xj(A), xj(A∗)∈N0for all j∈[m], and that m≥2.
Due to Lemma 6.5 we may assume that for some link kthe traffic according to A
exceeds the traffic according to A∗by m−1, whereas the traffic of any other link according
to Ais by one lower than according to A∗, and that all the latter links have equal speed,
say s, and equal traffic according to A∗, say x(A∗). Without loss of generality, we may
assume k= 1 and s= 1. Thus,
x1(A) = x1(A∗) + m−1,and
xj(A) = xj(A∗)−1 = x(A∗)−1, sj= 1 for 2≤j≤m .
For the social costs of Aand A∗we have
SC(A) = (x1(A∗) + m−1)2
s1
+ (m−1)(x(A∗)−1)2and
OPT(I) = SC(A∗) = (x1(A∗))2
s1
+ (m−1)(x(A∗))2.
Hence, SC(A)
OP T (I)is bounded from above by the result of the following optimization problem
with three unknowns x1, x and s1:
maximize
x1∈N0, x∈N, s1∈R>0
(x1+m−1)2
s1+ (m−1)(x−1)2
(x1)2
s1+ (m−1)x2subject to (6.9)
(a) (x1+1)2
s1+ (x−1)2≥(x1)2
s1+x2
(b) (x1−1)2
s1+ (x+ 1)2≥(x1)2
s1+x2
(c) x1+m−1
s1≤x
(d) x1+m
s1≥x−1
x1and xcorrespond to x1(A∗)and x(A∗), respectively. Because of 0≤xj(A) = x(A∗)−
1for j≥2,x(A∗)cannot be zero.
Because of Lemma 6.2, (a) and (b) are necessary and sufficient for the optimality of
A∗. (c) and (d) express the fact that Ais at Nash equilibrium.
Note that we may rewrite (a) as
2x1+ 1
s1≥2x−1or x1+1
2
s1≥x−1
2
and (b) as
2x+ 1 ≥2x1−1
s1
or x+1
2≥x1−1
2
s1
.
Hence (a) implies (d) and (c) implies (b) and we may immediately drop (d) and (b).
6.1 Pure Nash Equilibria 77
Setting C= (x1+m−1)2, D = (x1)2, E = (m−1)(x−1)2and F= (m−1)x2, we can
rewrite the fraction to be maximized as C+s1E
D+s1F. Since, C
D>1>E
F, we have to minimize
s1(subject to the constraints imposed by x1and x) in order to maximize the fraction.
(c) imposes a lower bound of x1+m−1
xon s1(while (a) only yields an upper bound).
Thus we have to set s1=x1+m−1
xin order to maximize the fraction which becomes
now
(x1+m−1)2x+ (m−1)(x−1)2(x1+m−1)
(x1)2x+ (m−1)x2(x1+m−1)
=1 + (m−1)2x+ 2x1(m−1)x+ (m−1)(−2x+ 1)(x1+m−1)
(x1)2x+ (m−1)x2(x1+m−1)
=1 + −(m−1)2x+ (m−1)(x1+m−1)
(x1)2x+ (m−1)x2(x1+m−1) .
The only remaining constraint (a) becomes
2x1+ 1
x1+m−1x≥2x−1
or
x1+m−1≥(2m−3)x .
This simplifies the optimization problem as follows.
maximize
x1∈N0, x∈N1 + (m−1) −(m−1)x+ (x1+m−1)
(x1)2x+ (m−1)(x1+m−1)x2
subject to
(a) x1≥x(2m−3) −(m−1) .
The denominator of the fraction is positive and increasing in x. (a) implies that the
numerator of the fraction is non-negative for all m≥2. As the numerator is decreasing
in x,xhas to be minimized in order to maximize the fraction. The lowest possible value
for x(because of x∈N) is x= 1. This yields
maximize
x1∈N01 + f(x1)
subject to
(a) x1≥m−2,
where
f(x1) = (m−1)x1
(x1)2+ (m−1)(x1+m−1) .
To maximize f(x1)over N0we first compute an upper bound on the maximum by
maximizing f(x1)over R≥0.
78 6 Nash Equilibria of Identical Users on Parallel Links
The first order derivative of f1(x1)is
∂f(x1)
∂x1
= (m−1)((x1)2+ (m−1)(x1+m−1)) −x1(2x1+m−1)
[(x1)2+ (m−1)(x1+m−1)]2
= (m−1) (m−1)2−(x1)2
[(x1)2+ (m−1)(x1+m−1)]2.
∂f(x1)
∂x1= 0 implies (x1)2= (m−1)2. Hence f(x1)attains its only local extremum over
R≥0at x1=m−1. As f(x1)is continuous over R≥0,f(0) = 0,limx1→∞ f(x1) = 0
and f(m−1) = 1
3>0, this local extremum is the global maximum of f(x1)on R≥0.
As m−1, the position where f(x1)attains its maximum over R≥0, is integral and lies in
the feasible range of our optimization problem, f(m−1) = 1
3is the exact solution to the
optimization problem rather than only an upper bound on it.
Hence, SC(A)
OP T (I)≤1 + f(m−1) = 4
3, contradicting the existence of an instance with
SC(A)
OP T (I)>4
3.
Finally, we give an example that proves the bound tight. Let m≥2be arbitrary.
Define an instance I= (w,s)of the congestion routing model with mrelated links and
identical users. Set s1= 2(m−2), s2=···=sm= 1, and let A∗and Abe assignments
with
x1(A∗) = m−1, x2(A∗) = ···=xm(A∗) = 1,
x1(A) = 2(m−1), x2(A) = ···=xm(A) = 0 .
Ais at Nash equilibrium, because
xj(A) + 1
sj
= 1 ≥2(m−1)
2(m−2) =x1(A)
s1
for 2≤j≤m .
For the (pure) coordination ration of Iwe get
PCR(I)≥SC(A)
SC(A∗)=
(2(m−1))2
2(m−1)
(m−1)2
2(m−1) + (m−1) =4
3.
The lower bound example given in the proof of Theorem 6.1 works for any number
m≥2of links. Hence, the coordination ratio is the same for 2links and an arbitrary large
number of links.
If we allowed that flow is split arbitrarily, then every Nash equilibrium has optimal so-
cial cost, as users would distribute their flow uniformly (weighted by link speeds) among
the links. If flow is splittable but the link latencies are given by arbitrary linear functions
lj(x) = ajx+bj,aj, bj≥0, then the coordination ratio is also 4
3[76].
6.1 Pure Nash Equilibria 79
6.1.2 Coordination Ratio for General Latency Functions
In this section, we carry over two upper bounds from Roughgarden and Tardos on the
coordination ratio for splittable flows in arbitrary routing networks to our model with unit
sized unsplittable flows on parallel links. The first [76, Corollary 2.10] can be adapted
directly to our discrete setting. The second [74, Theorem 3.8] is a genuine bound on the
coordination ratio, denoted anarchy value, for splittable flows. We will prove an analog
bound with help of the discrete version of the anarchy value that will be introduced in
Definition 6.10.
Recall that an instance of the congestion routing model with identical users is given
by I= (n, l). The latency on a link jwith congestion xis given by lj(x). We say that
xlj(x)is the cost function of link j. That is, xlj(x)is the contribution of link jto the
social cost. Indeed, the social cost of a routing Ais the sum of the cost contributions of
all links.
If all cost functions are convex, then a splittable flow is globally optimal, exactly if
it is locally optimal, i.e., if any reassignment of an infinitesimal amount of flow does not
decrease the social cost [6, 20].
An analog property holds for unsplittable flows. Here, we have discrete latency func-
tions of the form l: [n]→R, and hence discrete cost functions. The notion of convexity
refers to what is known as discrete convexity in this case. Let us define this formally.
Definition 6.6. We call a discrete function f: [n]→Rconvex, if
f(x+ 1) −f(x)≤f(y+ 1) −f(y)
for all x, y ∈[n−1] with x < y.
Our notion of a convex function corresponds to the particular case of a discretely con-
vex function as defined by Murota and Shioura in [59] for one dimension. Their definition
is basically due to a corresponding definition of Miller [57].
The following lemma implies that for an instance of the congestion routing model
with convex cost functions an unsplittable flow of unit sized users is globally optimal,
exactly if it is locally optimal. We will use it in the proof of Lemma 6.8 and Lemma 6.14.
Lemma 6.7. Let fj: [n]∪ {0} → Rbe a convex function for j∈[m]. Set X={x=
(x1,...,xm)∈Nm
0|Pj∈[m]xj=n}and let x∈X. Then, Pj∈[m]fj(xj)is minimal
among all y∈X, i.e., Pj∈[m]fj(xj)≤Pj∈[m]fj(yj)for all y= (y1, . . . , ym)∈X, if
and only if
fj(xj+ 1) + fk(xk−1) ≥fj(xj) + fk(xk)for all j, k ∈[m], xk≥1.(6.10)
Proof. Define f:X→Rby f(x) = Pj∈[m]fj(xj). Assume Pj∈[m]fj(xj)is minimal,
but fj(xj+ 1) + fk(xk−1) < fj(xj) + fk(xk)for some j, k ∈[m]. Determine y=
(y1,...,ym)∈Xby yj=xj+ 1,yk=xk−1and yt=xtfor all t∈[m]\{j, k}. Then,
X
t∈[m]
ft(yt) = f(xj+ 1) + f(xk−1) + X
t∈[m]\{j,k}
ft(xt)<X
j∈[m]
fj(xj),
80 6 Nash Equilibria of Identical Users on Parallel Links
a contradiction.
Assume now that (6.10) holds, but that there exists y= (y1, . . . , ym)∈Xwith
f(x)> f(y). Set J+(x,y) = {j∈[m]|yj> xj},J−(x,y) = {j∈[m]|yj< xj}
and t=Pj∈J+(yj−xj). Consider the sequence of vectors x=x(0), ..., x(t) = y,
where x(i)is obtained from x(i−1) for i∈[t]by setting r= min J+(x(i−1),y),
s= min J−(x(i−1),y),xr(i) = xr(i−1)+1,xs(i) = xs(i−1)−1and xj(i) = xj(i−1)
for j∈[m]\{r, s}.
Claim: For any i∈[t],f(x(i−1)) ≤f(x(i)).
If the claim is valid, then f(x)≤f(x(1)) ≤ ··· ≤ f(x(t−1)) ≤f(y), a contradiction
with our assumption. This would complete the proof.
Proof of claim: Let i∈[t]be arbitrary. Set r= min J+(x(i−1),y)and s= min J−(x(i−
1),y). Then,
f(x(i−1)) = X
j∈[m]
fj(xj(i−1))
=fr(xr(i−1)) + fs(xs(i−1)) + X
j∈[m]\{r,s}
fj(xj(i−1))
Note that xj(i)≥xjfor all j∈J+and i∈[t], and that xj(i)≤xjfor all j∈J−and
i∈[t]. Hence, xr(i−1) ≥xrand xs(i−1) ≤xs. (6.10) implies
fr(xr+ 1) + fs(xs−1) ≥fr(xr) + fs(xs)
or equivalently,
fr(xr+ 1) −fr(xr)≥fs(xs)−fs(xs−1) .
Since frand fsare convex, we obtain
fr(xr(i−1) + 1) −fr(xr(i−1)) ≥fr(xr+ 1) −fr(xr)and
fs(xs(i−1)) −fs(xs(i−1) −1) ≤fs(xs)−fs(xs−1) .
Thus,
fr(xr(i)) −fr(xr(i−1)) = fr(xr(i−1) + 1) −fr(xr(i−1))
≥fs(xs(i−1)) −fs(xs(i−1) −1)
=fs(xs(i−1)) −fs(xs(i))
which yields
fr(xr(i)) + fs(xs(i)) ≥fr(xr(i−1)) + fs(xs(i−1)) .
It follows that
f(x(i−1)) ≤fr(xr(i))+fs(xs(i))+ X
j∈[m]\{r,s}
fj(xj(i−1)) = X
j∈[m]
fj(xj(i)) = f(x(i)) ,
as desired.
6.1 Pure Nash Equilibria 81
The next lemma states the first upper bound on the coordination ratio in our model.
This bound is not tight, but the proof is simple.
Lemma 6.8. Consider any instance Iof the congestion routing model with identical users
and non-decreasing latency functions. If xlj(x)≤αPx
t=1 lj(t)for all j∈[m], x ∈[n],
then
SC(A, I)≤αOPT(I)
for any pure Nash equilibrium A.
Proof. Let x∗= (x∗
1,...,x∗
m)be the vector of link congestions in an optimal assignment.
Set fj(x) = Px
t=1 lj(t)for all j∈[m]. In a pure Nash equilibrium Athat assigns
xj=xj(A)users to link j, we have lj(xj+ 1) ≥lk(xk)which implies fj(xj+ 1) +
fk(xk−1) ≥fj(xj) + fk(xk)for all j, k ∈[m]. As ljis non-decreasing, fjis convex
for all j∈[m]. Hence we can apply Lemma 6.7 and obtain that Pj∈[m]fj(xj)is minimal
among all assignments with Pj∈[m]xj=n. Thus,
SC(A) =
m
X
j=1
xjlj(xj)≤α
m
X
j=1
xj
X
t=1
lj(t) = α
m
X
j=1
fj(xj)≤α
m
X
j=1
fj(x∗
j)
=α
m
X
j=1
x∗
j
X
t=1
lj(t)≤α
m
X
j=1
x∗
jlj(x∗
j) = α·OPT(I)
The following corollary is an example for the application of the upper bound.
Corollary 6.9. For the congestion routing model with identical users and where link
latencies are polynomial functions with non-negative coefficients and maximal degree d,
the coordination ratio for pure Nash equilibria is bounded by d+ 1.
Proof. Let l(x) = Pd
k=0 akxk,ad>0. Then, for x∈[n],
xl(x)
Px
t=1 l(t)=Pd
k=0 akxk+1
Pd
k=0 akPx
t=1 tk≤Pk=0 akxk+1
Pd
k=0 akRx
t=0 tddt =Pd
k=0 akxk+1
Pd
k=0
akxk+1
k+1 ≤d+ 1
The claim now follows from Lemma 6.8.
We now establish another bound on the coordination ratio, following the ideas of
Roughgarden [74, Lemma 3.5, 3.6, 3.7, Theorem 3.8]. He bounds the coordination ratio
for splittable flows in general networks (i.e. in the Wardrop model) by the anarchy value,
a value that depends on the latency functions only (and not on the structure of the network
graph). Let us first define a corresponding value for our model. We will denote it as the
discrete anarchy value.
82 6 Nash Equilibria of Identical Users on Parallel Links
Definition 6.10. Let l: [n]→R≥0be a non-decreasing latency function. Define the
marginal cost function l∗: [n]→R≥0corresponding to lby
l∗(1) = l(1),
and l∗(x) = xl(x)−(x−1)l(x−1) for x∈[n]\{1}.
Furthermore, define the discrete anarchy value of lby
α(l) = max
r∈[n]k(r)l(k(r))
rl(r)+ 1 −k(r)
r−1
,
where
k(r) = max{k∈[r]|l∗(k)≤l(r)}for r∈[n].
Finally, define the discrete anarchy value of an instance I= (n, l)of the congestion
routing model with identical users by
α(I) = max
j∈[m]α(lj).
Note that in the above definition k(r)is well defined, because l∗(1) = l(1) ≤l(r).
We are now ready to state the theorem which bounds the coordination ratio by the
discrete anarchy value.
Theorem 6.11. Let I= (n, l)be an instance of the congestion routing model with iden-
tical users and non-decreasing latency functions l1,...,lmsuch that xlj(x)is convex for
all j∈[m]. Let Abe an assignment at Nash equilibrium, and let A∗be any assignment
for I. Then,
SC(A, I)≤α(I)SC(A∗, I)
Proof. Let jbe any link with latency function ljand marginal cost function l∗
j, and let
kj(r) = max{k∈ {1,...,r} | l∗
j(k)≤lj(r)}for r∈[n]. Let xjand x∗
jbe the flow on
link jaccording to Aand A∗, respectively, that is, xj=xj(A)and x∗
j=xj(A∗). Denote
kj=kj(xj).
Then, as l∗
jis non-decreasing (because xlj(x)is convex) and non-negative (because
6.1 Pure Nash Equilibria 83
xlj(x)is non-decreasing),
lj(x∗
j)x∗
j=lj(kj)kj+
Px∗
j
t=kj+1 l∗
j(t)x∗
j> xj
Px∗
j
t=kj+1 l∗
j(t)xj≥x∗
j> kj
−Pkj
t=x∗
j+1 l∗
j(t)x∗
j≤kj
≥lj(kj)kj+
(x∗
j−xj)l∗
j(xj+ 1) + (xj−kj)l∗
j(kj+ 1) x∗
j> xj
(x∗
j−kj)l∗
j(kj+ 1) xj≥x∗
j> kj
−(kj−x∗
j)l∗
j(kj)x∗
j≤kj
≥lj(kj)kj+
(x∗
j−xj)lj(xj+ 1) + (xj−kj)lj(xj)x∗
j> xj
(x∗
j−kj)lj(xj)xj≥x∗
j> kj
(x∗
j−kj)lj(xj)x∗
j≤kj
=lj(kj)kj+ (x∗
j−kj)lj(xj) + ((x∗
j−xj)(lj(xj+ 1) −lj(xj)) x∗
j> xj
0xj≥x∗
j
The last estimation makes use of the fact that, by definition of kj,l∗
j(kj)≤lj(xj), and
that lj(xj)≤l∗
j(kj+ 1) if kj< n. Let L= maxj∈[m]lj(xj). Then, as Ais at Nash
equilibrium,
lj(xj+ 1) ≥Lfor all j∈[m].
Furthermore, note that
X
j∈[m]
x∗
j=X
j∈[m]
xj=n .
Thus we can bound the social cost of A∗from below by
SC(A∗) = X
j∈[m]
x∗
jlj(x∗
j)
≥X
j∈[m]lj(kj)kj+ (x∗
j−kj)lj(xj)+X
j∈[m]
x∗
j>xj
(x∗
j−xj)(lj(xj+ 1) −lj(xj))
=X
j∈[m]lj(kj)
lj(xj)kj+ (xj−kj)lj(xj) + X
j∈[m]x∗
j−xjlj(xj)
+X
j∈[m]
x∗
j>xj
(x∗
j−xj)(lj(xj+ 1) −lj(xj))
84 6 Nash Equilibria of Identical Users on Parallel Links
=X
j∈[m]kjlj(kj)
xjlj(xj)+ 1 −kj
xjxjlj(xj) + X
j∈[m]
x∗
j<xj
(x∗
j−xj)lj(xj)
+X
j∈[m]
x∗
j>xj
(x∗
j−xj)lj(xj+ 1)
≥X
j∈[m]
1
α(lj)xjlj(xj) + X
j∈[m]
x∗
j<xj
(x∗
j−xj)L+X
j∈[m]
x∗
j>xj
(x∗
j−xj)L
≥1
α(I)X
j∈[m]
xjlj(xj) + LX
j∈[m]
(x∗
j−xj)
| {z }
=0
=1
α(I)SC(A).
To give an example we will now bound the discrete anarchy value for linear latency
functions. Let the latency function of link jbe lj(x) = ajx+bjwith aj, bj∈R≥0. Then,
l∗
j(x) = ajx2+bjx−aj(x−1)2−bj(x−1) = 2ajx+bj−aj.
To compute kj(r) = max{k∈ {1,...,r} | l∗
j(k)≤lj(r)}for r∈[n], we have to
maximize ksubject to
l∗
j(k)≤lj(r)⇔2ajk+bj−aj≤ajr+bj⇔k≤r+ 1
2.
Hence, kj(r) = br+1
2c. Now we can bound α(lj)by
α(lj) = max
r∈[n]
1
br+1
2c1
r
ajbr+1
2c+bj
ajr+bj+ 1 −br+1
2c1
r
(6.11)
≤max
r∈[n]
1
br+1
2c1
r
ajbr+1
2c
ajr+ 1 −br+1
2c1
r
= max
r∈[n]
1
(br+1
2c1
r−1
2)2+3
4
≤4
3.
It follows from Theorem 6.11 that for any network of parallel links with linear latency
functions, the coordination ratio of pure Nash equilibria is bounded by 4
3. Because of
Theorem 6.1 and as related links are a special case of linear links, we know that this
bound is tight. In general, Theorem 6.11 yields only an upper bound on the coordination
ratio. However, the following proposition shows that, given an instance I, one can always
construct an instance I0, consisting of one constant latency link and one link from I, with
α(I0) = α(I)and coordination ratio α(I).
6.1 Pure Nash Equilibria 85
Proposition 6.12. Let I= (n, l)be an instance of the congestion routing model with n
identical users and discrete anarchy value α(I). Then there exists an instance I0with at
most nusers and two links and the same discrete anarchy value α(I0) = α(I)that has
coordination ratio exactly α(I0).
Proof. Let j∈[m]be a link of Iwith α(lj) = α(I). Let kj(r) = max{k∈[r]|l∗
j(k)≤
lj(r)}for r∈[n]. Let n0∈[n]be such that
k(n0)lj(k(n0))
n0lj(n0)+ 1 −k(n0)
n0−1
=α(lj).
Now construct a new instance I0with n0users and two links with latency functions l0
1(x) =
lj(n0)and l0
2(x) = lj(x)for all x∈[n0]. That is, link 1has constant latency and link 2has
the same latency function as link jof instance I.
Note that α(I0) = max{α(l0
1), α(l0
2)}= max{1, α(lj)}=α(lj) = α(I). Theorem 6.11
implies that the coordination ratio for I0is bounded by α(I0).
Consider an assignment Afor I0where all n0users go to link 2, i.e., x1(A) = 0 and
x2(A) = n0. Then l0
1(x1(A)) = lj(n0) = l0
2(x2(A)) and hence Ais at Nash equilibrium.
Now consider an assignment A∗with x1(A∗) = n0−k(n0)users on the first link and
x2(A∗) = k(n0)users on the second. Then, comparing the social cost of Aand A∗yields
SC(A)
SC(A∗)=n0lj(n0)
(n0−k(n0))lj(n0) + k(n0)lj(k(n0))
=k(n0)lj(k(n0)
n0lj(n0)+ 1 −k(n0)
n0−1
=α(I0).
Hence, the coordination ratio of I0is exactly α(I0).
Proposition 6.12 shows that coordination ratio is not a matter of the number of links
but only of the links’ latency characteristics. Note that the construction of an instance I0
with coordination ratio α(I0)in the proof of Proposition 6.12 involves a constant latency
link and hence is only feasible if links of arbitrary constant latency are allowed. For
example it does not yield a lower bound on the coordination ratio for related links (see
Theorem 6.1).
The definition of the discrete anarchy value α(I)of an instance Idepends on the
number nof its users. If we increase n, then also α(I)can increase. It cannot decrease
because it is maximized over all possible numbers 1,...,n of users. If we let ngo to
infinity, then either α(I)is unbounded, or it reaches its maximum for some value of n, or
it remains below (but gets arbitrarily close to) some supremum. In the first case we can
construct an instance with arbitrary coordination ratio as in the proof of Proposition 6.12.
The second case is covered by Theorem 6.11 and Proposition 6.12 for the corresponding
value of n. In the last case the coordination ratio is bounded by the supremum and we can
construct an instance with coordination ratio arbitrarily close to it.
86 6 Nash Equilibria of Identical Users on Parallel Links
6.1.3 Computation of Pure Nash Equilibrium and Optimal
Assignment for General Latency Functions
We complete this section by giving a fast algorithm to compute a pure Nash equilibrium
in the congestion routing model with identical users and arbitrary non-decreasing latency
functions. By the same algorithm we can also compute a globally optimal assignment, as
we will see.
A simple approach to compute a Nash equilibrium is to assign the users one by one to
their respective best link. This greedy algorithm can be implemented with running time
O((n+m) log m)if the links are kept in a priority queue according to their latency after
the assignment of the next user. Our algorithm, computeNash() (Figure 6.1), takes
time O(mlog mlog n)to compute the link congestions of a Nash equilibrium which is
better if the number of users is large compared to the number of links or, more precisely,
if m=o(n
log n). Note that additional time O(n+m)is needed to generate a corresponding
assignment.
The algorithm gets as input an arbitrary initial assignment of users to links given by
the link congestions x1,...,xm, i.e., xjis the number of users on link j. It transforms this
assignment into a Nash equilibrium by moving chunks of users at a time. The first chunk
contains all users. In each phase the chunk size is cut in half until a chunk consists of one
user only.
Proposition 6.13. Consider the congestion routing model with identical users and arbi-
trary non-decreasing latency functions. Then algorithm computeNash() computes a
pure Nash equilibrium in time O(mlog mlog n).
Proof. Obviously, algorithm computeNash() has computed a Nash equilibrium after
it terminates, because after the last iteration of the for-loop (with δ= 1), it holds lk(xk)≤
lj(xj+ 1) for all j, k ∈[m].
We now consider the running time. We show that each iteration of the for-loop takes
time O(mlog m), if implemented properly. Therefore, during each iteration of the for-
loop, the links are kept in two priority queues. In one queue the priorities are according to
lj(xj), in the other according to lj(xj+δ). For each iteration of the for-loop we prove that
a link’s congestion is either increased once or decreased an arbitrary number of times.
(a) Assume first, the congestion of some link is increased and then decreased. Con-
sider the first time that this happens on any link, and let tbe the corresponding link.
Let x1...,xmbe the link congestions just before the increment. Then lt(xt+δ)is
minimal among all lj(xj+δ)before xtis increased, and lt(xt+δ)> lu(x0
u+δ)for
some u∈[m]before it is decreased, where x0
uis the congestion of link ujust before
the decrement. As lt(xt+δ)was minimal before the increment of xt(which implies
lt(xt+δ)≤lu(xu+δ)), the congestion on link umust have been decreased after xtwas
increased (i.e., x0
u< xu). Before the last decrement of link u’s congestion the congestion
on link uwas x0
u+δand lu(x0
u+δ)was maximal among all links at that time. But this
implies lu(x0
u+δ)≥lt(xt+δ), a contradiction.
(b) Now assume, the congestion of some link is decreased and then increased. Consider
the first time that this happens on any link, and let sbe the corresponding link. Let
6.1 Pure Nash Equilibria 87
x1...,xmbe the link congestions just before the decrement. Then ls(xs)is maximal
among all lj(xj)before xsis decreased, and ls(xs)< lu(x0
u)for some u∈[m]before it is
increased, where x0
uis the congestion of link ujust before the increment. As ls(xs)was
maximal before the decrement of xs, the congestion on link umust have been increased
after xswas decreased. Before the last increment of link u’s congestion the congestion on
link uwas x0
u−δand lu(x0
u)was minimal at that time. But this implies lu(x0
u)≤ls(xs),
a contradiction.
(c) At last assume that there is a link twhose congestion is increased twice during one
iteration of the for-loop. Let x1...,xmbe the link congestions at the beginning of that
iteration. Then, ls(x0
s)> lt(xt+ 2δ)for some s, where x0
sis the congestion on link sjust
before the second increment of xt. As the congestion on link sis going to be decreased,
it cannot have been increased during this iteration due to (a). Hence, x0
s≤xs. The post-
condition of the last iteration of the for-loop implies ls(xs)≤lt(xt+δ0), where δ0is the
value of the for-variable in the last iteration. As dye ≤ 2dy
2efor every y≥0, we have
δ0≤2δwhich implies lt(xt+δ0)≤lt(xt+ 2δ)and hence ls(xs)≤lt(xt+ 2δ). But this
implies ls(xs)≤lt(xt+ 2δ)< ls(x0
s)≤ls(xs), a contradiction.
In each iteration of the inner while-loop the congestion of some link is increased.
We have just shown ((a),(b) and (c)) that this can happen only once per link. So, we
have at most miterations of the while-loop during each iteration of the for-loop. As the
links are kept sorted, the links with minimal lt(xt+δ)and maximal ls(xs), respectively,
can be determined in constant time. Updating of the data structures can be done in time
O(log m). Building up the data structures at the beginning of each iteration of the for-loop
takes time O(mlog m). Thus, each iteration of the for-loop takes time O(mlog m). The
for-loop is iterated O(log n)times. The total running time is hence O(mlog mlog n).
The following lemma shows that we can compute a globally optimal pure assignment
in the same way as a Nash equilibrium, but according to other latency functions, if the
cost function xlj(x)is convex for every link j∈[m]. A corresponding result holds for
continuous latency functions and splittable flows, too (see e.g. [75]).
Lemma 6.14. Consider an instance of the congestion routing routing model with identical
users and mlinks with latency function lj(x)on link j, such that xlj(x)is convex and
non-decreasing for all j∈[m]. Set l∗
j(x) = xlj(x)−(x−1)lj(x−1) for all j∈
[m], and let Abe any pure assignment. Then, Ais globally optimal with respect to
latency functions l1,...,lm, if and only if Ais at Nash equilibrium with respect to latency
functions l∗
1,...,l∗
m.
Proof. Let x= (x1,...,xm)be the vector of link flows according to A, i.e., xj=xj(A).
Ais at Nash equilibrium according to latency functions l∗
1,...,l∗
m, exactly if l∗
j(xj)≤
l∗
k(xk+ 1) for all j, k ∈[m], or, equivalently, if for all j, k ∈[m]
xjlj(xj)−(xj−1)lj(xj−1) ≤(xk+ 1)lk(xk+ 1) −xklk(xk).
This is true, if and only if for all j, k ∈[m]
fj(xj) + fk(xk)≤fj(xj−1) + fk(xk+ 1) ,
88 6 Nash Equilibria of Identical Users on Parallel Links
computeNash(I,x)
Input: instance I= (n, l)of the congestion routing
model with identical users
link congestions x1,...,xm
Output: Nash equilibrium x1,...,xm
for δ=n, dn
2e,dn
4e,...,1do
while ∃s, t ∈[n]with xs≥δand ls(xs)> lt(xt+δ)do
let tbe such that lt(xt+δ)is minimal;
let s∈[m]be such that ls(xs)is maximal
w.r.t. xs≥δ
xs=xs−δ;xt=xt+δ;
Figure 6.1: An algorithm to compute a Nash equilibrium from any assignment for an in-
stance of the congestion routing model with identical users.
where fj(x) = xlj(x). Due to Lemma 6.7 this is necessary and sufficient for SC(A) =
Pj∈[m]fj(xj)to be minimal.
Thus, algorithm computeNash() can be used to compute a globally optimal pure
assignment by applying it to the instance with latency function l∗
j(x) = xlj(x)−(x−
1)lj(x−1) on link j∈[m].
6.2 Mixed Nash Equilibria
In this section we turn our attention to general (mixed) Nash equilibria in the model of
identical users and almost arbitrary link latency functions. Recall that a mixed assignment
Pdetermines for each user i∈[n]and each link j∈[m]the probability pij for user ito
use link j.Pis at Nash equilibrium if no user can decrease its expected individual cost by
changing its vector of probabilities (the ith row of P) solely. A pure assignment is hence
a special case of a mixed assignment where each probability is either zero or one. On the
other hand we can identify the opposite extremal case of a mixed assignment where no
probability is zero or one, that is, pij ∈(0,1) for all i∈[n], j ∈[m]. The latter is called
afully mixed assignment. If a fully mixed assignment is at Nash equilibrium, then it is
called a fully mixed Nash equilibrium. This special Nash equilibrium plays an important
role, because the social cost achieves its maximum among all Nash equilibria for a given
instance with the fully mixed Nash equilibrium, if latency functions are convex, and pro-
vided that the fully mixed Nash equilibrium exists (see Theorem 6.19).
There is strong indication that also for the KP model (i.e., the congestion routing model
with related links and social cost defined as SCMAX ) the fully mixed Nash equilibrium
has maximal social cost, but, unfortunately, this claim remains unproven yet. However, it
could be proven for several special cases of the KP model [29, 35, 52, 27] and is conjec-
6.2 Mixed Nash Equilibria 89
tured to hold in general [35].
In the first subsection we show that for any instance of our model, the fully mixed
Nash equilibrium, if it exists, is unique.
In the next subsection we provide an example that shows that the Fully Mixed Nash
Equilibrium Conjecture can only hold for instances with convex latency functions. In fact
we show that even pure Nash equilibria may have larger social cost than the fully mixed
Nash equilibrium, if the latency functions are not required to be convex.
The last subsection characterizes the instances for which it exists or does not exist. Finally
we show that, by removing a subset of the links, one can always obtain an instance for
which the fully mixed Nash equilibrium exists and has non-smaller social cost than any
other equilibrium in the original instance.
6.2.1 Uniqueness of the Fully Mixed Nash Equilibrium
A fully mixed Nash equilibrium does not necessarily exist for a given instance. But if it
exists, then it is unique, and we may hence speak of the fully mixed Nash equilibrium. To
prove uniqueness we make use of the next two lemmas.
Definition 6.15. For r∈N,p= (p1,...,pr)∈Rrand a function g:N0→Rdefine
H(p, r, g) = X
A⊆[r]Y
k∈A
pkY
k∈[r]\A
(1 −pk)·g(|A|).
Lemma 6.16. [34] For every vector of rprobabilities p= (p1, . . . , pr)∈[0,1]rand
every non-decreasing function g:N0→R,H(p, r, g)is non-decreasing in each prob-
ability pi,i∈[n]. If, additionally, gis non-constant on {0,...,Pi∈[r]dpie} (i.e., g(0) <
g(Pi∈[r]dpie)), then H(p, r, g)is strictly increasing in each probability pi,i∈[n].
Proof. We prove that H(p, r, g)is non-decreasing (strictly increasing, respectively) in pr.
The claim then follows by symmetry of H(p, r, g)in all probabilities pi, i ∈[r]. It is
H(p, r, g) = X
A⊆[r]Y
k∈A
pkY
k∈[r]\/∈A
(1 −pk)·g(|A|)
=X
A⊆[r−1] Y
k∈A
pkY
k/∈A∪{r}
(1 −pk)·[g(|A|) + pr·(g(|A|+ 1) −g(|A|))]
As g(|A|+ 1) −g(|A|)≥0for all A⊆[r−1] (gis non-decreasing), H(p, r, g)is non-
decreasing in pr. Furthermore, if gis non-constant on the interval {0, . . . , Pi∈[r]dpie},
then there is some A⊂[r−1] with pi>0for all i∈A, such that g(|A|+1)−g(|A|)>0,
and hence H(p, r, g)is strictly increasing in pr.
Lemma 6.17. Consider an instance I= (n, l)of the congestion routing model with n
identical users and mlinks with non-decreasing and non-constant (on [n]) latency func-
tions. If a fully mixed Nash equilibrium Fexists, then every user is assigned to link
j∈[m]with the same probability in F. That is fij =fhj for all i, h ∈[n], j ∈[m].
90 6 Nash Equilibria of Identical Users on Parallel Links
Proof. For m= 1 the claim is trivial. So let m > 1. Let iand hbe any two users. The
expected individual cost of user ion link jis
λi(F|j) = X
A⊆[n]\{i,h}
[(1 −fhj)lj(|A|+ 1) + fhjlj(|A|+ 2)] r(F, A, {i, h}, j)
with
r(F, A, {i, h}, j) = Y
k∈A
fkj Y
k∈[n]\(A∪{i,h})
(1 −fkj).
In a fully mixed Nash equilibrium a user experiences the same expected individual latency
on all links, i.e., λi(F|j) = λiand λh(F|j) = λhfor all j∈[m]for some λiand λh. Thus,
for all j∈[m],
λi−λh= (fhj −fij)X
A⊆[n]\{i,h}
(lj(|A|+ 2) −lj(|A|+ 1))r(F, A, {i, h}, j).
As Fis fully mixed, fkj ∈(0,1) for all k∈[n], j ∈[m]. Thus r(F, A, {i, h}, j)>0for
all A⊆[n], i, h ∈[n], j ∈[m]. As ljis non-constant on [n], we have lj(|A|+2)−lj(|A|+
1) >0for some A⊆[n]\{i, h}. Thus the sum is positive for all j∈[m]. Hence, λi> λh
(λi< λh, respectively) implies fhj > fij (fhj < fij, respectively) for all j∈[m], which
contradicts the fact that Pj∈[m]fhj = 1 = Pj∈[m]fij. Thus, λi=λh, which implies
fhj =fij for all j∈[m].
Theorem 6.18. Consider an instance I= (n, l)of the congestion routing model with
identical users and non-decreasing and non-constant (on [n]) latency functions. If a fully
mixed Nash equilibrium Fexists, then it is unique.
Proof. Lemma 6.17 yields that a certain link is used by every user with the same proba-
bility in any fully mixed Nash equilibrium F, i.e., fhj =fij for all i, h ∈[n]and j∈[m].
We will use this fact to establish uniqueness of the fully mixed Nash equilibrium.
Assume there are two fully mixed Nash equilibria F0and F00 with f0
ij =f0
jand f00
ij =f00
j
for all i∈[n], j ∈[m]. The expected individual cost of any user ion link jaccording to
F0is
λi(F0|j) = X
A⊆[n]\{i}Y
k∈A
f0
kY
k∈[n]\A∪{i}
(1 −f0
k)·lj(|A|+ 1)
=H((f0
j,...,f0
j)
|{z }
∈Rn−1
, n −1, gj),
where gj: [n]∪{0} → Ris defined by gj(x) = lj(x+ 1).
Due to Lemma 6.16, λi(F0|j) = H((f0
j,...,f0
j), n −1, gj)is strictly increasing in f0
j
for all i∈[n]. Similarly, λi(F00|j) = H((f00
j,...,f00
j), n −1, gj)is strictly increasing in
f00
jfor any i∈[n]. If F0and F00 are different, then there exist two links j, k ∈[m]with
f0
j> f00
jand f0
k< f00
k. But this implies λi(F0|j)> λi(F00|j) = λi(F00|k)> λi(F0|k)for
any i∈[n], and hence contradicts the Nash equilibrium condition for F0. This completes
the proof.
6.2 Mixed Nash Equilibria 91
6.2.2 Convex versus Non-convex Latency Functions
For instances of the routing model under consideration where all latency functions are
convex the following theorem applies.
Theorem 6.19. [34] Consider an instance Iof the congestion routing model with identi-
cal users and parallel links with non-decreasing and convex latency functions. If the fully
mixed Nash equilibrium Fexists, then for every mixed Nash equilibrium P,SC(P, I)≤
SC(F, I).
Thus, for instances with convex latency functions, the fully mixed Nash equilibrium,
provided that it exists, has the worst social cost among all equilibria. Now we show that
it is necessary to require convex latency functions, as the claim might not hold otherwise,
even for identical links.
Proposition 6.20. There exists an instance I= (n, l)of the congestion routing model with
identical users and identical links with a non-decreasing, non-convex latency function for
which a pure Nash equilibrium Aand a fully mixed Nash equilibrium Fexist, such that
λi(A, I)> λi(F, I)for all i∈[n].
Proof. Consider an instance with m= 2 links and n= 4 (unit sized) users. Define l, the
common latency function of both links, as follows: l(1) = 1, l(2) = 2, l(3) = 2+, l(4) =
2 + 2, where > 0. Then, any pure Nash equilibrium Aassigns exactly 2users to each
link, and hence λi(A) = 2 for all i∈[n]. Now, consider the fully mixed Nash equilibrium
F. Here fij =1
2for all i∈[n], j ∈[m]. It follows that
λi(F) = 1
8(l(1) + 3l(2) + 3l(3) + l(4)) = 15
8+5
8for all i∈[n].
For < 1
5we have λi(A)> λi(F)for all i∈[n].
Note that because of Lemma 2.6, for the example given in Proposition 6.20 the social
cost of the pure Nash equilibrium exceeds that of the fully mixed Nash equilibrium.
6.2.3 Existence of Fully Mixed Nash Equilibrium
For instances with identical links, that is, where all links j∈[m]have the same latency
function lj=l, a fully mixed Nash equilibrium Falways exists and has probabilities
fij =1
mfor all i∈[n], j ∈[m]. In general, the existence of the fully mixed Nash
equilibrium is not granted, but depends on the latency functions l1, . . . , lm. We will now
shed light on this dependence.
Without loss of generality, we assume the links to be ordered non-decreasingly ac-
cording to lj(1). Furthermore, we assume ljto be non-constant on [n], i.e., lj(n)> lj(1).
Definition 6.21. For an instance I= (n, l)of the congestion routing model with identical
users and ordered (non-decreasingly according to lj(1)) and non-constant (on [n]) latency
functions, that is, l1(1) ≤ ··· ≤ lm(1) and lj(1) < lj(n)for all j∈[m], let gj:
92 6 Nash Equilibria of Identical Users on Parallel Links
[n−1] ∪ {0} → Rbe defined by gj(x) = lj(x+ 1) for all j∈[m]. For k∈[m],
j∈[k−1], define pj(k)∈R, such that
H((pj(k),...,pj(k))
|{z }
∈Rn−1
, n −1, gj) = min{lk(1), lj(n)}.
Due to Lemma 6.16, H((pj(k),...,pj(k)), n −1, gj)is strictly increasing in pj(k)
for pj(k)∈(0,1). Furthermore, it is H((0,...,0), n −1, gj) = lj(1) ≤lk(1) and
H((1,...,1), n−1, gj) = lj(n)for j∈[k−1]. Hence, for every j∈[k−1],pj(k)∈[0,1]
is uniquely determined by the above definition. Note that H((pj(k), . . . , pj(k)), n−1, gj)
is the expected individual latency of any user on link j∈[m], if pij =pj(k)for all i∈[n].
Definition 6.22. Let I= (n, l)be an instance of the congestion routing model with
identical users and non-constant (on [n]) latency functions. Without loss of general-
ity let the links be ordered non-decreasingly according to lj(1). Links k∈[m]with
Pj∈[k−1] pj(k)>1or ∃j∈[k−1] : lj(n)< lk(1) are called dead links. Links k∈[m]
with Pj∈[k−1] pj(k) = 1 and ∀j∈[k−1] : lj(n)< lk(1) are called special links.
Lemma 6.23. [34] Let g:N0→Rbe a convex function, and let p= (p1, . . . , pr)∈
[0,1]rbe a vector of probabilities. Set ˜p=Pi∈[r]pi
r. Then,
H(p, r, g)≤H((˜p, . . . , ˜p)
|{z }
∈Rr
, r, g).
Lemma 6.24. Let I= (n, l)be an instance of the congestion routing model with identical
users and non-decreasing, non-constant latency functions. If j∈[m]is a dead link, then
in any Nash equilibrium Pfor I,pij = 0 for all i∈[n].
Proof. Let Pbe a Nash equilibrium. Denote Θij = Θij(P) = Pt∈[n]\{i}ptj for i∈
[n], j ∈[m], and define gj: [n−1] ∪ {0} → Rby gj(x) = lj(x+ 1) for all j∈[m].
Note, that Pm
j=1
Θij
n−1= 1 for all i∈[n].
Assume pik >0for some user i∈[n]and some dead link k. Then, for all j∈[m]
lk(1) ≤λi(P|k)≤λi(P|j)(6.12)
=H(p(j), n −1, gj)Lemma 6.23
≤H(( Θij
n−1,..., Θij
n−1), n −1, gj),(6.13)
where p(j) = (p1,j,...,pi−1,j, pi+1,j,...,pn,j). Since kis a dead link, we have
X
j∈[k−1]
pj(k)>1or ∃j∈[k−1] : lj(n)< lk(1) .
In the latter case we get that λi(P|j)≤lj(n)< lk(1) for some j∈[k−1], a contradiction
with (6.12). In the first case,
k−1
X
j=1
Θij
n−1≤1<
k−1
X
j=1
pj(k).
6.2 Mixed Nash Equilibria 93
Hence there must exist some j∈[k−1], such that pj(k)>Θij
n−1. This implies
H(( Θij
n−1,..., Θij
n−1), n −1, gj)Lemma 6.16
< H((pj(k),...,pj(k)), n −1, gj) = lk(1) ,
a contradiction with (6.13).
Lemma 6.25. Consider an instance I= (n, l)of the congestion routing model with
identical users and non-decreasing, non-constant latency functions. Let Sbe the set of
special links. In any Nash equilibrium P, there exists at most one user iwith pij >0for
some j∈S.
Proof. Let Pbe a Nash equilibrium. Denote Θij = Θij(P) = Pt∈[n]\{i}ptj for i∈
[n], j ∈[m], and define gj: [n−1] ∪{0} → Rby gj(x) = lj(x+ 1) for all j∈[m].
Assume pik >0and phr >0for two users i, h ∈[n], i 6=h, and special links k, r ∈S(k
may be equal to r). Hence, Θir ≥phr
n−1>0. Without loss of generality, k≤r. Then for
all j∈[m]
lk(1) ≤λi(P|k)≤λi(P|j)
=H(p(j), n −1, gj)Lemma 6.23
≤H(( Θij
n−1,..., Θij
n−1), n −1, gj),(6.14)
where p(j) = (p1,j,...,pi−1,j, pi+1,j,...,pn,j). Since Θir >0,
k−1
X
j=1
Θij
n−1<
m
X
j=1
Θij
n−1= 1 =
k−1
X
j=1
pj(k).
Hence, there exists some link j∈[k−1], such that pj(k)>Θij
n−1. This implies
H(( Θij
n−1,..., Θij
n−1), n −1, gj)Lemma 6.16
< H((pj(k),...,pj(k)), n −1, gj) = lk(1) ,
a contradiction with (6.14).
Theorem 6.26. Consider an instance I= (n, l)of the congestion routing model with (at
least two) identical users and non-decreasing, non-constant latency functions. Then there
exists a fully mixed Nash equilibrium, if and only if the instance contains no special and
no dead links.
Proof. In a fully mixed Nash equilibrium, every user chooses each link with non-zero
probability. Therefore, as a direct consequence of Lemma 6.24 and Lemma 6.25, a fully
mixed Nash equilibrium cannot exist, if n≥2and the instance possesses dead or special
links.
Now, assume there are no dead or special links. We will show that there exists a fully
mixed Nash equilibrium Fwith probabilities fij =fjfor i∈[n], j ∈[m].
Define gj: [n−1] ∪ {0} → Rby gj(x) = lj(x+ 1) for all j∈[m]. Let
ˆxj=H((1,...,1), n −1, gj)−lm(1) for j∈[m−1]. For x∈[0,ˆxj]determine fj(x)by
94 6 Nash Equilibria of Identical Users on Parallel Links
H((fj(x),...,fj(x)), n−1, gj) = lm(1)+xfor j∈[m−1], and for x∈[0,minj∈[m−1] ˆxj]
set fm(x) = 1−Pm−1
j=1 fj(x). Note, that fj(x)is strictly increasing in xfor all x∈[0,ˆxj],
j∈[m−1] because of Lemma 6.16, and therefore fm(x)is strictly decreasing in xfor
x∈[0,minj∈[m−1] ˆxj].
Define ˆxby ˆx= max{x∈[0,minj∈[m−1] ˆxj]|fm(x)≥0}. Then, the function
H((fm(x),...,fm(x)), n −1, gm)is strictly decreasing in xfor x∈[0,ˆx].
As link mis neither a special nor a dead link, it holds that fm(0) = 1−Pj∈[m−1] pj(m)>
0. This yields H((fm(0),...,fm(0)), n −1, gm)> lm(1) (because H((0,...,0), n −
1, gm) = lm(1) and H((p, . . . , p), n −1, gm)is strictly increasing in pfor p∈(0,1)). On
the other hand, as fm(ˆx) = 0,H((fm(ˆx),...,fm(ˆx)), n −1, gm) = lm(1) < lm(1) + ˆx.
Since H((fm(x),...,fm(x)), n −1, gm)is a continuous function in x, we can follow
from the intermediate value theorem that there must exist some x0∈(0,ˆx), such that
H((fm(x0),...,fm(x0)), n −1, gm) = lm(1) + x0. Setting fij =fj(x0)for all i∈
[n], j ∈[m]yields the desired fully mixed Nash equilibrium.
Theorem 6.26 implies that if the fully mixed Nash equilibrium does not exist, then
the instance contains dead or special links. But dead links are never used in any Nash
equilibrium and may be removed from the instance. Special links can only be used by
a single user. We now broaden the result from Theorem 6.19 by giving an upper bound
on the social cost of any Nash equilibrium for any instance, including those that do not
possess a fully mixed Nash equilibrium.
Theorem 6.27. Consider an instance I= (n, l)of the congestion routing model with
identical users and non-decreasing, non-constant and convex latency functions. Then the
social cost of any Nash equilibrium Pis bounded by the social cost of the fully mixed
Nash equilibrium Ffor the instance induced by the non-special and non-dead links.
Proof. Consider any Nash equilibrium P. Let Fbe the fully mixed Nash equilibrium for
the instance where the links are restricted to the links which are not special and not dead.
Due to Lemma 6.24 no user chooses a dead link with non-zero probability according to P.
If no user chooses a special link with non-zero probability, then the claim follows directly
from Theorem 6.19. So assume that there exists a user that is assigned to a special link
with non-zero probability. Lemma 6.25 shows that there is at most one such user.
Without loss of generality, let [r]be the set of non-special and non-dead links. Let
i∈[n]be any user. Denote Θij(P) = Pk∈[n]\{i}pkj and Θij(F) = Pk∈[n]\{i}fkj for all
j∈[m]. Note that Θij(F) = (n−1)fkj for all k∈[n]because of Lemma 6.17. It is
Pj∈[r]Θij(P)≤n−1 = Pj∈[r]Θij(F). This implies that there exists a link j∈[r]
where Θij(P)≤Θij(F). Let gj:N∪{0} → Rbe defined by gj(x) = lj(x+ 1) for all
6.2 Mixed Nash Equilibria 95
j∈[m]. Then,
λi(P)≤λi(P|j) = H((p1j,...,pi−1,j, pi+1,j,...,pnj), n −1, gj)
Lemma 6.23
≤H((Θij(P)
n−1,...,Θij(P)
n−1), n −1, gj)
Lemma 6.16
≤H((Θij(F)
n−1,...,Θij(F)
n−1), n −1, gj)
Lemma 6.17
=H((f1j,...,fi−1,j, fi+1,j,...,fnj), n −1, gj)
=λi(F|j) = λi(F).
Thus, SC(P) = Pi∈[n]λi(P)≤Pi∈[n]λi(F) = SC(F).
96 6 Nash Equilibria of Identical Users on Parallel Links
7
Unrelated Links
In this chapter we address non-cooperative routing on unrelated parallel links. In contrast
to the KP model with related links, here links may process different user flows at different
speeds. Related links are a special case of unrelated links. Hence, the unrelated routing
model is a generalization of the KP model.
We will explore the scope of the Fully Mixed Nash Equilibrium Conjecture (which
is originally stated for the KP model [35]) for unrelated links. We prove that it holds for
certain special cases of the unrelated routing model. On the other hand we give a minimal
instance for which it does not hold.
7.1 Definition
For unrelated links it is not possible anymore to assign one speed to each link which holds
for all users. In fact we must specify one vector of link speeds for each user. If sij is the
speed at which link jprocesses the traffic of user i, then the latency on link jaccording
to some pure assignment Ais lj(A) = PA(i)=j
wi
sij . For convenience we incorporate the
user weights and respective link speeds into one value and define cij =wi
sij to be the
contribution of user ito the latency on link j. So, an instance of the unrelated routing
model is given by I= (C), where C= (cij)∈Rn×m
≥0is the cost matrix. Note that we
have cij =wi
sjfor the special case of related links. The definition of social cost remains as
for the KP model. That is, SC(P) = SCMAX(P).
98 7 Unrelated Links
7.2 Pure versus Fully Mixed Nash Equilibrium
Our first result is that the social cost of a pure Nash equilibrium can never exceed that of
a fully mixed Nash equilibrium, if the number of users is not larger than the number of
links. This is a consequence of the corresponding claim for the individual cost that we
prove first.
Proposition 7.1. Consider an instance I= (C)of the unrelated routing model where
n≤mand for which a fully mixed Nash equilibrium Fexists. Let Pbe any pure Nash
equilibrium. Then, for any user i,λi(P)≤λi(F).
Proof. Let Abe the assignment corresponding to P, i.e., (A(i) = j⇔pij = 1) for all
i∈[n], j ∈[m].
1. Assume first that each user is assigned to a different link, that is, A(i)6=A(k)for all
i, k ∈[n]with i6=k. By definition of individual cost, this implies that λi(P) = cij,
where j=A(i)is the link to which player iis assigned by P. However, λi(F) =
cij +Pk∈[n],k6=ifkjckj, and hence λi(P)≤λi(F).
2. Assume now that not all players are assigned to different links by P. Since n≤m,
this implies that there is some empty link j∈[m], that is, no player is assigned
to link jby P. By definition of individual cost and the Nash equilibrium property,
λi(P)≤λi(P|j) = cij, while λi(F) = cij +Pk∈[n],k6=ifkjckj, and hence λi(P)≤
λi(F).
Theorem 7.2. Consider an instance I= (C)of the unrelated routing model where n≤
m, and for which a fully mixed Nash equilibrium Fexists. Let Pbe any pure Nash
equilibrium. Then, SC(P)≤SC(F).
Proof. Let kbe a user with maximal individual cost according to pure Nash equilibrium
P. Then the social cost of Pcan be written as SC(P) = maxi∈[n]λi(P) = λk(P).
Proposition 7.1 yields λk(P)≤λk(F). The individual cost of user kaccording to Fcan
be expressed by λk(F) = PA:[n]→[m]Qi∈[n]fi,A(i)λk(A). Hence,
λk(F)≤X
A:[n]→[m]Y
i∈[n]
fi,A(i)max
r∈[n]λr(A)
=X
A:[n]→[m]Y
i∈[n]
fi,A(i)SC(A)
=SC(F),
and the claim follows.
In Section 7.4 we will see that neither of Proposition 7.1 and Theorem 7.2 remains
true, if we drop the assumption that the number of users does not exceed the number of
links. So, we cannot expect to get a stronger result in this direction.
7.3 Mixed Nash Equilibria of Two Users 99
7.3 Mixed Nash Equilibria of Two Users
We now investigate mixed Nash equilibria that involve only two users. The first result is
the correspondent of Proposition 7.1 for this case. The second shows validity of the Fully
Mixed Nash Equilibrium Conjecture for two users on two links.
Proposition 7.3. Consider an instance I= (C)of the unrelated routing model with
n= 2 users for which the fully mixed Nash equilibrium Fexists. Let Pbe any Nash
equilibrium. Then, for any user i∈[2],λi(P)≤λi(F).
Proof. We proceed by case analysis on the relation between support(1) and support(2).
1. Assume first that support(1) = support(2). There are two subcases to consider.
a) If support(1) = support(2) = [m], then pij =fij for all i∈[2], j ∈[m]with
cij >0which follows from the Nash equilibrium conditions for Pand Fand
the definition of individual cost. Note that the probabilities pij and fij for iand
jwith cij = 0 vanish in the computation of individual cost (see Lemma 2.5)
according to Pand F, respectively. Hence, λi(P) = λi(F)for i∈[2].
b) If support(1) = support(2) 6= [m], then there exists some link k∈[m]such
that both, k6∈ support(1) and k6∈ support(2). Note that λ1(P)≤λ1(P|k) =
c1k, while λ1(F) = λ1(F|k) = c1k+f2kc2k. Since f2k>0and c2k≥0, it
follows that λ1(P)≤λ1(F), as needed. Corresponding arguments for user 2
establish that λ2(P)≤λ2(F), as well.
2. Assume now that support(1) 6=support(2). Then, either we have support(1) \
support(2) 6=∅or support(2) \support(1) 6=∅.
a) Consider first the subcase where support(1) \support(2) 6=∅. Then, there
exists some link k∈[m]such that k∈support(1) while k /∈support(2).
Note that λ1(P) = λ1(P|k) = c1kwhile λ1(F) = λ1(F|k) = c1k+f2kc2k.
Since f2k>0while c2k≥0, it follows that λ1(P)≤λ1(F). We pro-
ceed to consider user 2. To show that λ2(P)≤λ2(F), assume, by way of
contradiction, that λ2(P)> λ2(F). For all links j∈support(2) we have
λ2(P) = λ2(P|j) = c2j+p1jc1jand λ2(F) = λ2(F|j) = c2j+f1jc1j.
Since λ2(P)> λ2(F), it follows that p1j> f1jfor all j∈support(2).
Since, however, Pm
j=1 p1j= 1 = Pm
j=1 f1j, this implies that there exists
some link k /∈support(2) such that p1k< f1k. Thus, λ2(P)≤λ2(P|k) =
c2k+p1kc1k≤c2k+f1kc1k=λ2(F|k) = λ2(F), a contradiction. It follows
that λ2(P)≤λ2(F).
b) Corresponding arguments suffice to establish that both, λ1(P)≤λ1(F)and
λ2(P)≤λ2(F)in the subcase where support(2) \support(1) 6=∅as well.
Proposition 7.3 is tight in the sense that the claim is not valid for instances with more
than two users (see Theorem 7.5).
100 7 Unrelated Links
Theorem 7.4. For the set of instances of the unrelated routing model where m=n= 2
the Fully Mixed Nash Equilibrium Conjecture is valid.
Proof. Let I= (C)be an instance of the model with n=m= 2 for which the
fully mixed Nash equilibrium Fexists. We will show that for any Nash equilibrium
P,SC(P)≤SC(F). We proceed by case analysis on the supports of P.
1. Assume first that Pis pure. Since m=n, Theorem 7.2 implies that SC(P)≤
SC(F), as needed.
2. Assume now that one user is pure and the other one is mixed in P. Without loss
of generality, assume that user 1is pure and that it is assigned to link 1, while user
2is mixed. We calculate the individual cost of user 2in P. Clearly, λ2(P|1) =
c21 +c11 and λ2(P|2) = c22. Since Pis at Nash equilibrium, λ2(P|1) = λ2(P|2)
or c21 +c11 =c22. The social cost of Pis
SC(P) = p21(c11 +c21) + p22 max{c11, c22}
=p21c22 +p22c22 (since c22 =c11 +c21 ≥c11)
=c22 .
Thus,
SC(F) = X
A:[2]→[2] Y
i∈[2]
fi,A(i)max
k∈[2] λk(A)
≥X
A:[2]→[2] Y
i∈[2]
fi,A(i)λ2(A)
=λ2(F)
=λ2(F|2) (since Fis fully mixed)
≥c22 (since λ2(F|2) = c22 +f12c12) (7.1)
=SC(P),
as needed.
3. Now assume that both users are not pure in P, i.e., support(1) = support(2) =
{1,2}. We distinguish two subcases:
a) Let C > 0, i.e., cij >0for all i, j ∈[2]. This implies that the fully mixed
Nash equilibrium is unique. Hence, as Pis fully mixed, P=Fand nothing
is to show.
b) Now assume that C > 0does not hold, i.e., cij = 0 for some i, j ∈[2].
Without loss of generality let c12 = 0 (all other cases are symmetric). Then the
Nash equilibrium condition for Pyields λ1(P|1) = λ1(P|2) and λ2(P|1) =
λ2(P|2), or equivalently
c11 +p21c21 =c12 +p22c22 and
c21 +p11c11 =c22 +p12c12 .
7.4 The Limit of the Fully Mixed Nash Equilibrium Conjecture 101
Applying p22 = 1 −p21,p12 = 1 −p11 and c12 = 0 yields
p21(c21 +c22) = c22 −c11 and
p11c11 =c22 −c21 .
The social cost of Pis
SC(P) = p21[p11(c21 +c11) + (1 −p11) max{c21, c12}]
+ (1 −p21)[p11 max{c22, c11}+ (1 −p11)(c22 +c12)] .
Since c12 = 0, and as p21 ≥0implies c22 ≥c11, we have
SC(P) = p21[p11(c21 +c11) + (1 −p11)c21]
+ (1 −p21)[p11c22 + (1 −p11)(c22 +c12)]
=p21[p11c11 +c21] + (1 −p21)c22
=p21[c22 −c21 +c21] + (1 −p21)c22
=c22 .
As SC(F)≥c22 (see (7.1)), the claim follows.
Thus, in all cases SC(P)≤SC(F), as needed.
7.4 The Limit of the Fully Mixed Nash Equilibrium
Conjecture
We finally show that the Fully Mixed Nash Equilibrium Conjecture does not hold for
unrelated links in general. Moreover, even a pure Nash equilibrium can have greater
social cost than a fully mixed Nash equilibrium.
Theorem 7.5. There exists an instance Iof the unrelated routing model with n= 3
users and a fully mixed Nash equilibrium Fand a pure Nash equilibrium P, such that
SC(P)> SC(F).
Proof. We simply define an instance I= (C)with n= 3 users and m= 2 links and
show that it has a fully mixed Nash equilibrium Fand a pure Nash equilibrium Pwith
SC(P)> SC(F).
•Set c11 =c21 = 2,c31 = 0 and c12 =c22 =3
2and c32 = 3.
Consider first the pure assignment Passigning users 1and 2to link 1, and user 3to link
2. We verify that Pis at Nash equilibrium:
•λ1(P|1) = c11 +c21 = 4 <9
2=c12 +c32 =λ1(P|2).
•λ2(P|1) = c21 +c11 = 4 <9
2=c22 +c32 =λ2(P|2).
102 7 Unrelated Links
•λ3(P|2) = c32 = 3 <4 = c31 +c11 +c21 =λ3(P|1).
It follows that no user can improve by switching to the opposite link, and hence, Pis at
Nash equilibrium. The social cost of Pis SC(P) = max{c11 +c21, c32}= 4.
Consider now the fully mixed assignment Fwith f11 =f21 =6
7,f31 =1
3,f12 =
f22 =1
7and f32 =2
3. We verify that Fis a (fully mixed) Nash equilibrium:
•λ1(F|1) = c11 +f21c21 +f31c31 =26
7=c12 +f22c22 +f32c32 =λ1(F|2).
•λ2(F|1) = c21 +f11c11 +f31c31 =26
7=c22 +f12c12 +f32c32 =λ2(F|2).
•λ3(F|1) = c31 +f11c11 +f21c21 =24
7=c32 +f12c12 +f22c22 =λ3(F|2).
It follows that Fis at Nash equilibrium. The social cost of Fis
SC(F) = f11f21f31(c11 +c21 +c31) + f11f21f32 max{c11 +c21, c32}
+f11f22f31 max{c11 +c31, c22}+f11f22f32 max{c11, c22 +c32}
+f12f21f31 max{c12, c21 +c31}+f12f21f32 max{c12 +c32, c21}
+f12f22f31 max{c12 +c22, c31}+f12f22f32(c12 +c22 +c32)
=1
7·7·3·(144 + 288 + 12 + 54 + 12 + 54 + 3 + 12)
=193
49 .
Thus, SC(F) = 193
49 <4 = SC(P), as needed.
Theorem 7.5 shows that the Fully Mixed Nash Equilibrium Conjecture is not valid for
the unrelated routing model, even for instances with n= 3 and m= 2. On the other
hand, Theorem 7.4 shows that it holds for instances with two users and two links. It is an
open problem whether it holds for instances with two users in general.
8
Conclusion and Open Questions
Selfish routing and other settings that involve selfish behavior form an important and on-
going field of research. This is not only shown by the multitude of recent publications.
Circumstances like the growth of economic freedom in divers spheres (e.g. telecommu-
nication and energy market) or the immense evolvement of the internet make it a non-
surprising fact.
To get a deep insight into the rather complicated real world applications of selfish be-
havior, it is necessary to establish a comprehensive theoretical background. The purpose
of this work is to expand the collection of results and to get a better understanding of
selfish behavior in some concrete and well defined settings.
By introducing the KP model [47], Koutsoupias and Papadimitriou initiated a recent
surge of research in the intersection of economics and computer science. We have pre-
sented several results on the KP model. Most notably, we gave an efficient Nashification
algorithm which yields a PTAS for the problem to compute the best Nash equilibrium.
Even though our algorithm does not increase the social cost, it involves reassignments
of users that do not necessarily improve the users’ individual costs. An open question
is whether one can carry out Nashification in polynomial time with improving steps or
greedy steps only. Furthermore, we have introduced the Nash Equilibrium Verification
Problem and analyzed its algebraic complexity. Thereby we revealed an interesting re-
lationship to a geometric problem which in turn helped us to give an optimal algorithm
for the problem. The Nash Equilibrium Verification Problem can be considered for other
settings as well. We leave this issue as a topic of future work.
For the KP model with identical links we have constructed an instance which takes
a number of 23
2√n−6greedy steps to reach a Nash equilibrium in the worst case. On the
other hand, the number of greedy steps is bounded by 2n−1. It remains an open problem
to close the gap between these bounds.
104 8 Conclusion and Open Questions
We followed up divers extensions of the KP model, like links with M/M/1-queue
characteristics or links with weight constraints. Furthermore, we made a step toward the
Wardrop model by adapting its definition of social cost and allowing very general latency
functions, whereas we retained the indivisibility of flow and the restricted topology of
the KP model. The challenge here is to surmount also the limitation to parallel links.
Other relevant topologies can be the first step. E.g., one can show that the LPT algorithm
computes a Nash equilibrium for unweighted users in series-parallel networks with non-
decreasing link latency functions. What is the performance of the resulting routing? For
weighted users it is not even clear whether a pure Nash equilibrium always exists for
series-parallel networks.
Concerning our results on the coordination ratio for pure Nash equilibria of identical
users on parallel links, the generalization to weighted users is still open. Another con-
crete question is whether the analysis of the algorithm in Figure 6.1 can improved as to
obtain a better bound on its running time or if the given bound of O(mlog mlog n)is
asymptotically tight.
For unweighted users and the definition of social cost as average cost per unit of
flow, we have proved a coordination ratio of 4
3for related links. For the reciprocal case
of weighted users on related links, the pure coordination ratio is 9
8([51]). What is the
coordination ratio for weighted users on related links?
The Fully Mixed Nash Equilibrium Conjecture was originally stated for the KP model
[35]. Nevertheless, there is hope that it holds for other settings as well. It is known that it
remains valid for the congestion routing game of unweighted users on parallel links with
non-decreasing convex latency functions and the social cost being defined as sum of user
costs. Hence, if the fully mixed Nash equilibrium exists for an instance of this model, then
its social cost bounds the social cost of any Nash equilibrium. If an instance possesses
some very fast and some very slow links at the same time, then the fully mixed Nash
equilibrium, which requires that every link is used by each user with positive probability,
may not exist. We have shown that if (some of) the slow links are removed as to get an
instance that possesses a fully mixed Nash equilibrium, then the social cost of the fully
mixed Nash equilibrium still is an upper bound on the social cost for any Nash equilibrium
in the original instance. A further issue here is to generalize these results to the case of
weighted users.
We have addressed the Fully Mixed Nash Equilibrium Conjecture also for the case of
unrelated links (and everything else being defined as in the KP model). We could assert it
for instances with two users and two links. On the other hand we gave an example to show
that it does not hold for three users and two links. To fill the remaining gap is the next
issue for this model. That is, we state the following open question: Is the Fully Mixed
Nash Equilibrium Conjecture true for two users on unrelated links in general? Although
there exists a pure Nash equilibrium for any instance of the model with unrelated links, it
is an open problem to efficiently compute one (except for the two links case).
For the original KP model (with related links) the Fully Mixed Nash Equilibrium
Conjecture was proved for a variety of restricted cases. Its general validity remains an
open problem as well.
Publications
Many of the results presented in this thesis have been presented on international con-
ferences or were submitted to journals. Here is a list of publications with the author’s
participation that have appeared by the printing time of the thesis.
[34] M. Gairing, T. Lücking, M. Mavronicolas, B. Monien, and M. Rode. Nash equi-
libria in discrete routing games with convex latency functions. In Proceedings
of the 31st International Colloquium on Automata, Languages and Programming
(ICALP), volume 3142 of LNCS, pages 645–657, 2004.
[51] T. Lücking, M. Mavronicolas, B. Monien, and M. Rode. A new model for selfish
routing. In Proceedings of the 21st Annual Symposium on Theoretical Aspects of
Computer Science (STACS), volume 2996 of LNCS, pages 547–558, 2004.
[27] R. Feldmann, M. Gairing, T. Lücking, B. Monien, and M. Rode. Nashification
and the coordination ratio for a selfish routing game. In Proceedings of the 30th
International Colloquium on Automata, Languages, and Programming (ICALP),
volume 2719 of LNCS, pages 514–526, 2003.
[28] R. Feldmann, M. Gairing, T. Lücking, B. Monien, and M. Rode. Selfish routing
in non-cooperative networks: A survey. In Proceedings of the 28th International
Symposium on Mathematical Foundations of Computer Science (MFCS), volume
2747 of LNCS, pages 21–45, 2003.
[52] T. Lücking, M. Mavronicolas, B. Monien, M. Rode, P. Spirakis, and I. Vrto. Which
is the worst-case nash equilibrium? In Proceedings of the 28th International Sym-
posium on Mathematical Foundations of Computer Science (MFCS), volume 2747
of LNCS, pages 551–561, 2003.
[53] T. Lücking, B. Monien, and M. Rode. On the problem of scheduling flows on dis-
tributed networks. In Proceedings of the 27th International Symposium on Math-
ematical Foundations of Computer Science (MFCS), volume 2402 of LNCS, pages
495–505, 2002.
Bibliography
[1] A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer
Algorithms. Addison-Wesley, 1974.
[2] E. Altman, T. Ba¸sar, T. Jiménez, and Nahum Shimkin. Routing into two parallel
links: Game-theoretic distributed algorithms. Journal of Parallel and Distributed
Computing, 61(9):1367–1381, 2001.
[3] E. Altman and L. Wynter. Equilibrium, games, and pricing in transportation and
telecommunications networks. Special Issue of Networks and Spatial Economics on
"Crossovers between Transportation Planning and Telecommunications", 4(1):7–
21, 2004.
[4] E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler, and T. Roughgar-
den. The price of stability for network design with fair cost allocation. In Proceed-
ings of the 45th IEEE Symposium on Foundations of Computer Science (FOCS),
2004.
[5] A. Archer and E. Tardos. Frugal path mechanisms. In Proceedings of the 13th
Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 991–999,
2002.
[6] M. Beckmann, C. B. McGuire, and C. B. Winsten. Studies in the Economics of
Transportation. Yale University Press, 1956.
[7] M. J. Beckmann. On the theory of traffic flow in networks. Traffic Quart, 21:109–
116, 1967.
[8] R. Beier, A. Czumaj, P. Krysta, and B. Vöcking. Computing equilibria for con-
gestion games with (im)perfect information. In Proceedings of the 15th Annual
ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 746–755, 2004.
[9] M. Ben-Or. Lower bounds for algebraic computation trees. In Proceedings of the
15th Annual ACM Symposium on Theory of Computing (STOC), pages 80–86, 1983.
[10] P. Berenbrink, L. A. Goldberg, P. Goldberg, and R. Martin. Utilitarian resource
assignment. The Computing Research Repository (CoRR), 2004. cs.GT/0410018.
[11] S. K. Bose. An Introduction to Queueing Systems. Kluwer Academic Publishers,
2001.
108 Bibliography
[12] D. Braess. über ein paradoxon der verkehrsplanung. Unternehmensforschung,
12:258–268, 1968.
[13] G. Christodoulou, E. Koutsoupias, and A. Nanavati. Coordination mechanisms. In
Proceedings of the 31st International Colloquium on Automata, Languages, and
Programming (ICALP), pages 345–357, 2004.
[14] J. E. Cohen and P. Horowitz. Paradoxical behaviour of mechanical and electrical
networks. Nature, 352:699–701, 1991.
[15] R. Cole, Y. Dodis, and T. Roughgarden. How much can taxes help selfish routing?
In Proceedings of the 4th ACM Conference on Electronic Commerce (EC), pages
98–107, 2003.
[16] R. Cole, Y. Dodis, and T. Roughgarden. Pricing network edges for heterogeneous
selfish users. In Proceedings of the 35th Annual ACM Symposium on Theory of
Computing (STOC), pages 521–530, 2003.
[17] J. R. Correa, A. S. Schulz, and N. E. Stier Moses. Computational complexity, fair-
ness, and the price of anarchy of the maximum latency problem. Working Paper
4447-03, Massachusetts Institute of Technology (MIT), Sloan School of Manage-
ment, 2004. Available at http://ideas.repec.org/p/mit/sloanp/5051.html.
[18] A. Czumaj, P. Krysta, and B. Vöcking. Selfish traffic allocation for server farms. In
Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC),
pages 287–296. ACM Press, 2002.
[19] A. Czumaj and B. Vöcking. Tight bounds for worst-case equilibria. In Proceedings
of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages
413–420, 2002.
[20] S.C. Dafermos and F.T. Sparrow. The traffic assignment problem for a general net-
work. Journal of Research of the National Bureau of Standards - B. Mathematical
Sciences, 73B(2):91–118, 1969.
[21] X. Deng, C. Papadimitriou, and S. Safra. On the complexity of equilibria. In Pro-
ceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC),
pages 67–71, 2002.
[22] J. Erickson. New lower bounds for halfspace emptiness. In Proceedings of the 37th
Annual Symposium on Foundations of Computer Science (FOCS), pages 472–481,
1996.
[23] E. Even-Dar, A. Kesselmann, and Y. Mansour. Convergence time to Nash equilibria.
In Proceedings of the 30th International Colloquium on Automata, Languages, and
Programming (ICALP), pages 502–513, 2003.
Bibliography 109
[24] A. Fabrikant, A. Luthra, E. Maneva, C. H. Papadimitriou, and S. Shenker. On a
network creation game. In Proceedings of the 22nd Annual Symposium on Principles
of Distributed Computing (PODC), pages 347–351, 2003.
[25] A. Fabrikant, C. Papadimitriou, and K. Talwar. The complexity of pure Nash equi-
libria. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing
(STOC), pages 604–612, 2004.
[26] J. Feigenbaum, C. Papdimitriou, and S. Shenker. Sharing the cost of multicast trans-
missions. In Proceedings of the 32nd Annual ACM Symposium on Theory of Com-
puting (STOC), pages 218–227, 2000.
[27] R. Feldmann, M. Gairing, T. Lücking, B. Monien, and M. Rode. Nashification and
the coordination ratio for a selfish routing game. In Proceedings of the 30th Inter-
national Colloquium on Automata, Languages, and Programming (ICALP), pages
514–526, 2003.
[28] R. Feldmann, M. Gairing, T. Lücking, B. Monien, and M. Rode. Selfish routing
in non-cooperative networks: A survey. In Proceedings of the 28th International
Symposium on Mathematical Foundations of Computer Science (MFCS), pages 21–
45, 2003.
[29] D. Fotakis, S. Kontogiannis, E. Koutsoupias, M. Mavronicolas, and P. Spirakis. The
structure and complexity of Nash equilibria for a selfish routing game. In Proceed-
ings of the 29th International Colloquium on Automata, Languages, and Program-
ming (ICALP), pages 510–519. ACM Press, 2002.
[30] D. Fotakis, S. C. Kontogiannis, and P. G. Spirakis. Selfish unsplittable flows. In
Proceedings of the 31st International Colloquium on Automata, Languages, and
Programming (ICALP), pages 593–605, 2004.
[31] D. K. Friesen. Tighter bounds for lpt scheduling on uniform processors. SIAM
Journal on Computing, 16(3):554–560, 1987.
[32] D. K. Friesen and M. A. Langston. Bounds for multifit scheduling on uniform pro-
cessors. SIAM Journal on Computing, 12(1):60–70, 1983.
[33] M. Gairing, T. Lücking, M. Mavronicolas, and B. Monien. Computing Nash equi-
libria for scheduling on restricted parallel links. In Proceedings of the 36th Annual
ACM Symposium on Theory of Computing (STOC), pages 613–622, 2004.
[34] M. Gairing, T. Lücking, M. Mavronicolas, B. Monien, and M. Rode. Nash equi-
libria in discrete routing games with convex latency functions. In Proceedings
of the 31st International Colloquium on Automata, Languages and Programming
(ICALP), pages 645–657, 2004.
110 Bibliography
[35] M. Gairing, T. Lücking, M. Mavronicolas, B. Monien, and P. Spirakis. Extreme
Nash equilibria. In Proceedings of the 8th Italian Conference on Theoretical Com-
puter Science (ICTCS), pages 1–20, 2003.
[36] M. R. Garey and D. S. Johnson. Computers And Intractability – A Guide to the
Theory of NP-Completeness. W. H. Freeman and Company, 1979.
[37] P. W. Goldberg. Bounds for the convergence rate of randomized local search in a
multiplayer load-balancing game. In Proceedings of the 23rd Annual ACM Sympo-
sium on Principles of Distributed Computing (PODC), pages 131–140, 2004.
[38] G. Gottlob, G. Greco, and F. Scarcello. Pure Nash equilibria: hard and easy games.
In Proceedings of the 9th conference on Theoretical Aspects of Rationality and
Knowledge (TARK), pages 215–230, 2003.
[39] R. L. Graham. Bounds on multiprocessing timing anomalies. SIAM Journal on
Applied Mathematics, 17(2):416–429, 1969.
[40] A. Haurie and P. Marcotte. On the relationship between Nash-Cournot and Wardrop
equilibria. Networks, 15:295–308, 1985.
[41] D. S. Hochbaum and D. B. Shmoys. Using dual approximation algorithms for
scheduling problems: Theoretical and practical results. Journal of the ACM,
34(1):144–162, 1987.
[42] D. S. Hochbaum and D. B. Shmoys. A polynomial approximation scheme for
scheduling on uniform processors: Using the dual approximation approach. SIAM
Journal on Computing, 17(3):539–551, 1988.
[43] C. Hurkens and T. Vredeveld. Local search for multiprocessor scheduling: how
many moves does it take to a local optimum? Operations Research Letters, 31:137–
141, 2003.
[44] Y. A. Korilis, A. A. Lazar, and A. Orda. Architecting noncooperative networks.
IEEE Journal on Selected Areas in Communications, 13(7):1241–1251, 1995.
[45] Y. A. Korilis, A. A. Lazar, and A. Orda. The role of the manager in a noncooperative
network. In Proceedings of the 15th Annual Joint Conference of the IEEE Computer
and Communications Societies (INFOCOM), pages 1285–1293, 1996.
[46] E. Koutsoupias, M. Mavronicolas, and P. Spirakis. Approximate equilibria and ball
fusion. Theory of Computing Systems, 36(6):683–693, 2003.
[47] E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. In Proceedings of
the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS),
pages 404–413, 1999.
Bibliography 111
[48] V. S. A. Kumar and M. V. Marathe. Improved results for Stackelberg scheduling
strategies. In Proceedings of the 29th International Colloquium on Automata, Lan-
guages, and Programming (ICALP), pages 776–787, 2002.
[49] L. Libman and A. Orda. The designer’s perspective to atomic noncooperative net-
works. IEEE/ACM Transactions on Networking, 7(6):875–884, 1999.
[50] L. Libman and A. Orda. Atomic resource sharing in noncooperative networks.
Telecommunication Systems, 17(4):385–409, 2001.
[51] T. Lücking, M. Mavronicolas, B. Monien, and M. Rode. A new model for selfish
routing. In Proceedings of the 21st Annual Symposium on Theoretical Aspects of
Computer Science (STACS), pages 547–558, 2004.
[52] T. Lücking, M. Mavronicolas, B. Monien, M. Rode, P. Spirakis, and I. Vrto. Which
is the worst-case Nash equilibrium? In Proceedings of the 28th International Sympo-
sium on Mathematical Foundations of Computer Science (MFCS), pages 551–561,
2003.
[53] T. Lücking, B. Monien, and M. Rode. On the problem of scheduling flows on dis-
tributed networks. In Proceedings of the 27th International Symposium on Mathe-
matical Foundations of Computer Science (MFCS), pages 495–505, 2002.
[54] M. Mavronicolas and P. Spirakis. The price of selfish routing. In Proceedings of the
33rd Annual ACM Symposium on Theory of Computing (STOC), pages 123–134,
2001.
[55] R. D. McKelvey and A. McLennan. Computation of Equilibria in Finite Games.
Elsevier, 1996.
[56] I. Milchtaich. Congestion games with player-specific payoff functions. Games and
Economic Behavior, 13:111–124, 1996.
[57] B. L. Miller. On minimizing nonseparable functions defined on the integers with
an inventory application. SIAM Journal on Applied Mathematics, 21(1):166–185,
1971.
[58] D. Monderer and L. S. Shapley. Potential games. Games and Economic Behavior,
14:124–143, 1996.
[59] K. Murota and A. Shioura. Relationship of m-/l-convex functions with discrete con-
vex functions by miller and favati-tardella. Discrete Applied Mathematics, 115(1–
3):151–176, 2001.
[60] R. B. Myerson. Game Theory: Analysis of Conflict. Harvard University Press, 1991.
[61] J. Nash. Non-cooperative games. Annals of Mathematics, 54(2):286–295, 1951.
112 Bibliography
[62] N. Nisan. Algorithms for selfish agents. In Proceedings of the 16th International
Symposium on Theoretical Aspects of Computer Science (STACS), pages 1–15, 1999.
[63] N. Nisan and A. Ronen. Algorithmic mechanism design. In Proceedings of the 31st
Annual ACM Symposium on Theory of Computing (STOC), pages 129–140, 1999.
[64] A. Orda and N. Shimkin. Competitive routing in multiuser communication net-
works. IEEE/ACM Transactions on Networking, 1(5):510–521, 1993.
[65] M. J. Osborne and A. Rubinstein. A Course in Game Theory. The MIT Press, 1994.
[66] G. Owen. Game Theory. Academic Press, 1995.
[67] C.H. Papadimitriou. Algorithms, games, and the internet. In Proceedings of the 33rd
Annual ACM Symposium on Theory of Computing (STOC), pages 749–753, 2001.
[68] F. P. Preparata and M. I. Shamos. Computational Geometry - An Introduction.
Springer-Verlag, 1985.
[69] J. B. Rosen. Existence and uniqueness of equilibrium points for concave n-person
games. Econometrica, 33(3):520–534, 1965.
[70] R. W. Rosenthal. A class of games possessing pure-strategy Nash equilibria. Inter-
national Journal of Game Theory, 2:65–67, 1973.
[71] T. Roughgarden. Designing networks for selfish users is hard. In Proceedings of
the 42nd Annual Symposium on Foundations of Computer Science (FOCS), pages
472–481, 2001.
[72] T. Roughgarden. Stackelberg scheduling strategies. In Proceedings of the 33rd
Annual ACM Symposium on Theory of Computing (STOC), pages 104–113, 2001.
[73] T. Roughgarden. Selfish Routing. PhD thesis, Cornell University, 2002.
[74] T. Roughgarden. The price of anarchy is independent of the network topology.
Journal of Computer and System Sciences, 67(2):341–364, 2003.
[75] T. Roughgarden and E. Tardos. How bad is selfish routing? In Proceedings of
the 41st Annual Symposium on Foundations of Computer Science (FOCS), pages
93–102, 2000.
[76] T. Roughgarden and E. Tardos. How bad is selfish routing? Journal of the ACM,
49(2):236–259, 2002.
[77] A. S. Schulz and N. Stier Moses. On the performance of user equilibria in traffic
networks. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA), pages 86–87, 2003.
Bibliography 113
[78] S. Singh, M. Kearns, and Y. Mansour. Nash convergence of gradient dynamics
in general-sum games. In Proceedings of the 16th Conference in Uncertainty in
Artificial Intelligence (UAI), pages 541–548, 2000.
[79] S. Suri, C. D. Tóth, and Y. Zhou. Selfish load balancing and atomic congestion
games. In Proceedings of the 16th Annual ACM Symposium on Parallelism in Algo-
rithms and Architectures (SPAA), pages 188–195, 2004.
[80] T. Ui. Discrete concavity for potential games. Working paper, Yoko-
hama National University, Faculty of Economics, 2004. Available at
http://www2.igss.ynu.ac.jp/ oui/d-potential.pdf.
[81] M. Voorneveld, P. Borm, F. van Megen, and S. Tijs. Congestion games and poten-
tials reconsidered. Discussion Paper 98, Tilburg University, Center for Economic
Research, 1999. Available at http://ideas.repec.org/p/dgr/kubcen/199998.html.
[82] M. Voorneveld and H. Norde. A characterization of ordinal potential games. Games
and Economic Behavior, 19:235–242, 1997.
[83] J. G. Wardrop. Some theoretical aspects of road traffic research. In Proceedings of
the Institute of Civil Engineers (ICE), Part II, volume 1, pages 325–378, 1956.
