Kao M.-Y. (ed.) Encyclopedia of Algorithms
Подождите немного. Документ загружается.
578 N Non-approximability of Bimatrix Nash Equilibria
Data Sets
Data set generators and problem families are described
in [4], and are available from http://www.avglab.com/
andrew/soft.html.
URL to Code
Thecodeusedin[4]isavailablefromhttp://www.avglab.
com/andrew/soft.html.
Cross References
All Pairs Shortest Paths in Sparse Graphs
All Pairs Shortest Paths via Matrix Multiplication
Single-Source Shortest Paths
Recommended Reading
1. Ahuja, R., Magnanti, T., Orlin, J.: Network Flows. Prentice-Hall,
Englewood Cliffs (1993)
2. Chaudhuri, S.,Zaroliagis, C.: Shortest Paths in Digraphs of Small
Treewidth. Part II: Optimal Parallel Algorithms. Theor. Comput.
Sci. 203(2), pp. 205–223 (1998)
3. Chaudhuri, S.,Zaroliagis, C.: Shortest Paths in Digraphs of Small
Treewidth. Part I: Sequential Algorithms. Algorithmca 27(3),
pp. 212–226 (2000)
4. Cherkassky, B.V., Goldberg, A.V.: Negative-Cycle Detection Al-
gorithms. Math. Program. 85, pp. 277–311 (1999)
5. Fakcharoenphol, J., Rao, S.: Planar Graphs, Negative Weight
Edges, Shortest Paths, and near Linear Time. In: Proc. 42nd IEEE
Symp. on Foundations of Computer Science – FOCS (2001),
pp. 232–241. IEEE Computer Society Press, Los Alamitos (2001)
6. Goldberg, A.V.: Scaling Algorithms for the Shortest Paths Prob-
lem. SIAM J. Comput. 24, pp. 494–504 (1995)
7. Goldberg, A.V., Radzik, T.: A Heuristic Improvement of the
BellmanFord Algorithm. Appl. Math. Lett. 6(3), pp. 3–6 (1993)
8. Kavvadias, D., Pantziou, G., Spirakis, P., Zaroliagis, C.: Efficient
Sequential and Parallel Algorithms for the Negative Cycle
Problem. In: Algorithms and Computation – ISAAC’94. Lect.
Notes Comput. Sci., vol. 834, pp.270–278. Springer, Heidelberg
(1994)
9. Klein,P.,Rao,S.,Rauch,M.,Subramanian,S.:Fastershortest-
path algorithms for planar graphs. J. Comput. Syst. Sci. 5(1),
pp. 3–23 (1997)
10. Kolliopoulos, S.G., Stein, C.: Finding Real-Valued Single-Source
Shortest Paths in o(n
3
) Expected Time. J. Algorithms 28,
pp. 125–141 (1998)
11. Mehlhorn, K., Näher, S.: LEDA: A Platform for Combinatorial
and Geometric Computing. Cambridge University Press, Cam-
bridge (1999)
12. Spirakis, P., Tsakalidis, A.: A Very Fast, Practical Algorithm for
Finding a Negative Cycle in a Digraph. In Proc. of 13th ICALP,
pp. 397–406 (1986)
13. Tarjan, R.E.: Data Structures and Network Algorithms. SIAM,
Philadelphia (1983)
14. Wong, C.H., Tam, Y.C.: Negative Cycle Detection Problem. In:
Algorithms – ESA 2005. Lecture Notes in Computer Science,
vol. 3669, pp. 652–663. Springer, Heidelberg (2005)
Non-approximability
of Bimatrix Nash Equilibria
2006; Chen, Deng, Teng
XI CHEN
1
,XIAOTIE DENG
2
1
Computer Science and Technology, Tsinghua
University, Beijing, Beijing, China
2
Department of Computer Science, City University
of Hong Kong, Hong Kong, China
Keywords and Synonyms
Approximate Nash equilibrium
Problem Definition
In this entry, the following two problems are considered:
1) the problem of finding an approximate Nash equilib-
rium in a positively normalized bimatrix (or two-player)
game; and 2) the smoothed complexity of finding an ex-
act Nash equilibrium in a bimatrix game. It turns out that
these two problems are strongly correlated [3].
Let
G =(A; B) be a bimatrix game, where A =(a
i;j
)
and B =(b
i;j
)arebothn n matrices. Game G is said
to be positively normalized, if 0 a
i;j
; b
i;j
1forall
1 i; j n.
Let P
n
denote the set of all probability vectors in R
n
,
i. e., non-negative vectors whose entries sum to 1. A Nash
equilibrium [8]of
G =(A; B) is a pair of mixed strategies
(x
2 P
n
; y
2 P
n
)suchthatforallx; y 2 P
n
,
(x
)
T
Ay
x
T
Ay
and (x
)
T
By
(x
)
T
By ;
while an -approximate Nash equilibrium is a pair
(x
2 P
n
; y
2 P
n
)thatsatisfies
(x
)
T
Ay
x
T
Ay
and
(x
)
T
By
(x
)
T
By ; for all x; y 2 P
n
:
In the smoothed analysis [11] of bimatrix games, a per-
turbation of magnitude >0 is first applied to the input
game: For a positively normalized n n game
G =(A; B),
let A and B be two matrices with
a
i;j
= a
i;j
+r
A
i;j
and b
i;j
= b
i;j
+r
B
i;j
; 81 i; j n;
while r
A
i;j
and r
B
i;j
are chosen independently and uni-
formly from interval [; ] or from Gaussian distribu-
tion with variance
2
. These two kinds of perturbations
are referred to as -uniform and -Gaussian perturba-
tions, respectively. An algorithm for bimatrix games has
polynomial smoothed complexity (under -uniform or -
Gaussian perturbations) [11], if it finds a Nash equilibrium
of game (A; B)inexpectedtimepoly(n; 1/), for all (
A; B).
Non-shared Edges N 579
Key Results
The complexity class PPAD [9] is defined in entry Bi-
matrix Nash. The following theorems are proved in [3].
Theorem 1 For any constant c > 0, the problem of com-
puting a 1/n
c
-approximate Nash equilibrium of a positively
normalized n n bimatrix game is PPAD-complete.
Theorem 2 The problem of computing a Nash equilibrium
in a bimatrix game is not in smoothed polynomial time,
under uniform or Gaussian perturbations, unless PPAD
RP.
Corollary 1 The smoothed complexity of the Lemke-
Howson algorithm is not polynomial, under uniform or
Gaussian perturbations, unless PPAD RP.
Applications
See entry Bimatrix Nash.
Open Problems
There remains a complexity gap on the approximation
of Nash equilibria in bimatrix games: The result of [7]
shows that, an -approximate Nash equilibrium can be
computed in n
O(log n/
2
)
-time, while [3] show that no al-
gorithm can find an -approximate Nash equilibrium in
poly(n; 1/)-time for of order 1/poly(n), unless PPAD is
in P. However, the hardness result of [3] does not cover
the case when is a constant between 0 and 1. Naturally,
it is unlikely that the problem of finding an -approximate
Nash equilibrium is PPAD-complete when is an absolute
constant, for otherwise, all the search problems in PPAD
wouldbesolvableinn
O(log n)
-time, due to the result of [7].
An interesting open problem is that, for every constant
>0, is there a polynomial-time algorithm for finding an
-approximate Nash equilibrium? The following conjec-
tures are proposed in [3]:
Conjecture 1 There is an O(n
k+
c
)-time algorithm for
finding an -approximate Nash equilibrium in a bimatrix
game, for some constants c and k.
Conjecture 2 There is an algorithm to find a Nash
equilibrium in a bimatrix game with smoothed complex-
ity O(n
k+
c
) under perturbations with magnitude ,for
some constants c and k.
It is also conjectured in [3] that Corollary 1 remains
true without any complexity assumption on class PPAD.
A positive answer would extend the result of [10]tothe
smoothed analysis framework.
Cross References
Complexity of Bimatrix Nash Equilibria
General Equilibrium
Leontief Economy Equilibrium
Recommended Reading
1. Chen, X., Deng, X.: 3-Nash is PPAD-complete. ECCC, TR05-134
(2005)
2. Chen, X., Deng, X.: Settling the complexity of two-player Nash
equilibrium. In: FOCS’06: Proc. of the 47th Annual IEEE Sympo-
sium on Foundations of Computer Science, 2006, pp. 261–272
3. Chen, X., Deng, X., Teng, S.H.: Computing Nash equilibria: ap-
proximation and smoothed complexity. In: FOCS’06: Proc. of
the 47th Annual IEEE Symposium on Foundations of Computer
Science, 2006, pp. 603–612
4. Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The com-
plexity of computing a Nash equilibrium.In: STOC’06: Proceed-
ings of the 38th ACM Symposium on Theory of Computing,
2006, pp. 71–78
5. Daskalakis, C., Papadimitriou, C.H.: Three-player games are
hard. ECCC, TR05-139 (2005)
6. Goldberg, P.W., Papadimitriou, C.H.: Reducibility among equi-
librium problems. In: STOC’06: Proc. of the 38th ACM Sympo-
sium on Theory of Computing, 2006, pp. 61–70
7. Lipton, R., Markakis, E., Mehta, A.: Playing large games using
simple strategies. In: Proc. of the 4th ACM conference on Elec-
tronic commerce, 2003, pp. 36–41
8. Nash, J.F.: Equilibrium point in n-person games. Proc. Natl.
Acad. Sci. USA 36(1), 48–49 (1950)
9. Papadimitriou, C.H.: On the complexity of the parity argument
and other inefficient proofs of existence. J. Comput. Syst. Sci.
48, 498–532 (1994)
10. Savani, R., von Stengel, B.: Exponentially many steps for find-
ing a Nash equilibrium in a bimatrix game. In: FOCS’04: Proc. of
the 45th Annual IEEE Symposium on Foundations of Computer
Science, 2004, pp. 258–267
11. Spielman, D.A., Teng, S.H.: Smoothed analysis of algorithms
and heuristics: progress and open questions. In: Pardo, L.M.,
Pinkus, A., Süli, E., Todd, M.J. (eds.) Foundations of Computa-
tional Mathematics, pp. 274–342. Cambridge University Press,
Cambridge, UK (2006)
Non-shared Edges
1985; Day
WING-KAI HON
Department of Computer Science, National Tsing Hua
University, Hsin Chu, Taiwan
Keywords and Synonyms
Robinson–Foulds distance; Robinson–Foulds metric
580 N Non-shared Edges
Problem Definition
Phylogenies are binary trees whose leaves are labeled
with distinct leaf labels. This problem in this article is
concerned with a well-known measurement, called non-
shared edge distance, for comparing the dissimilarity be-
tween two phylogenies. Roughly speaking, the non-shared
edge distance counts the number of edges that differentiate
one phylogeny from the other.
Let e be an edge in a phylogeny T.Removinge from
T splits T into two subtrees. The leaf labels are partitioned
into two subsets according to the subtrees. The edge e is
said to induce a partition of the set of leaf labels. Given two
phylogenies T and T
0
having the same number of leaves
with the same set of leaf labels, an edge e in T is shared if
thereexistssomeedgee
0
in T
0
such that the edges e and
e
0
induce the same partition of the set of leaf labels in their
corresponding tree. Otherwise, e is non-shared.Noticethat
T and T
0
has the same number of edges, so that the num-
ber of non-shared edges in T (with respect to T
0
)isthe
same as the number of non-shared edges in T
0
(with re-
spect to T). Such a number is called the non-shared edge
distance between T and T
0
.Twoproblemsaredefinedas
follows:
Non-shared Edge Distance Problem
I
NPUT: Two phylogenies on the same set of leaf labels
O
UTPUT: The non-shared edge distance between the two
input phylogenies
All-Pairs Non-shared Edge Distance Problem
I
NPUT: A collection of phylogenies on the same set of leaf
labels
O
UTPUT: The non-shared edge distance between each pair
of the input phylogenies
Extension
Phylogenies that are commonly used in practice have
weights associated to the edges. The notion of non-shared
edge can be easily extended for edge-weighted phyloge-
nies. In this case, an edge e will induce a partition of the
set of leaf labels as well as the multi-set of edge weights
(here, edge weights are allowed to be non-distinct). Given
two edge-weighted phylogenies R and R
0
having the same
set of leaf labels and the same multi-set of edge weights, an
edge e in R is shared ifthereexistssomeedgee
0
in R
0
such
that the edges e and e
0
induce the same partition of the
set of leaf labels and the multi-set of edge weights. Oth-
erwise, e is non-shared.Thenon-shared edge distance be-
tween R and R
0
are similarly defined, giving the following
problem:
General Non-shared Edge Distance Problem
I
NPUT: Two edge-weighted phylogenies on the same set of
leaf labels and same multi-set of edge weights
O
UTPUT: The non-shared edge distance between the two
input phylogenies
Key Results
Day [3] proposed the first linear-time algorithm for the
Non-shared Edge Distance Problem.
Theorem 1 Let T and T
0
be two input phylogenies with the
same set of leaf labels, and n be the number of leaves in each
phylogeny. The non-shared edge distance between T and T
0
can be computed in O(n) time.
Let be a collection of k phylogenies on the same set of
leaf labels, and n be the number of leaves in each phy-
logeny. The All-Pairs Non-shared Edge Distance Problem
can be solved by applying Theorem 1 on each pair of phy-
logenies, thus solving the problem in a total of O(k
2
n)
time. Pattengale and Moret [9] proposed a randomized
result based on [7] to solve the problem approximately,
whose running time is faster when n k 2
n
.
Theorem 2 Let " be a parameter with ">0.Then,there
exists a randomized algorithm such that with probability at
least 1 k
2
, the non-shared edge distance between each
pair of phylogenies in can be approximated within a fac-
tor of (1 + ") from the actual distance; the running time of
the algorithm is O(k(n
2
+ k log k)/"
2
).
For general phylogenies, let R and R
0
be two input phylo-
genies with the same set of leaf labels and the same multi-
set of edge weights, and n be the number of leaves in
each phylogeny. The General Non-shared Distance Prob-
lem can be solved easily in O(n
2
) time by applying The-
orem 1 in a straightforward manner. The running time is
improved by Hon et al. in [5].
Theorem 3 The non-shared edge distance between R and
R
0
can be computed in O(n log n) time.
Applications
Phylogeniesarecommonlyusedbybiologiststomodel
the evolutionary relationship among species. Many recon-
struction methods (such as maximum parsimony, maxi-
mum likelihood, compatibility, distance matrix) produce
different phylogenies based on the same set of species,
and it is interesting to compute the dissimilarities between
them. Also, through the comparison, information about
rare genetic events such as recombinations or gene con-
versions may be uncovered. The most common dissimi-
Nucleolus N 581
larity measure is the Robinson–Foulds metric [11], which
is exactly the same as the non-shared edge distance.
Other dissimilarity measures, such as the nearest-
neighbor interchange (NNI) distance and the subtree-
transfer (STT) distance (see [2] for details), are also pro-
posed in the literature. These measures are sometimes pre-
ferred by the biologists since they can be used to deduce
the biological events that create the dissimilarity. Never-
theless, these measures are usually difficult to compute. In
particular, computing the NNI distance and the STT dis-
tanceareshowntobeNP-hardbyDasGuptaetal.[1,2].
Approximation algorithms are devised for these problems
(NNI: [4,8], STT: [1,6]). Interestingly, all these algorithms
make use of the non-shared edge distance to bound their
approximation ratios.
Cross References
A related problem is to measure the similarity between
two input phylogenies. Maximum Agreement
Subtree for references.
Recommended Reading
1. DasGupta,B.,He,X.,Jiang,T.,Li,M.,Tromp,J.:OntheLinear-
Cost Subtree-Transfer Distance between Phylogenetic Trees.
Algorithmica 25(2–3), 176–195 (1999)
2. DasGupta,B.,He,X.,Jiang,T.,Li,M.,Tromp,J.,Zhang,L.:On
Distances between Phylogenetic Trees. In: Proceedings of the
Eighth ACM-SIAM Annual Symposium on Discrete Algorithms
(SODA), New Orleans, pp. 427–436. SIAM, Philadelphia (1997)
3. Day, W.H.E.: Optimal Algorithms for Comparing Trees with La-
beled Leaves. J. Classif. 2, 7–28 (1985)
4. Hon, W.K., Lam, T.W.: Approximating the Nearest Neighbor
Intercharge Distance for Non-Uniform-Degree Evolutionary
Trees. Int. J. Found. Comp. Sci. 12(4), 533–550 (2001)
5. Hon, W.K., Kao, M.Y., Lam, T.W., Sung, W.K., Yiu, S.M.: Non-
shared Edges and Nearest Neighbor Interchanges revisited. Inf.
Process. Lett. 91(3), 129–134 (2004)
6. Hon, W.K., Lam, T.W., Yiu, S.M., Kao, M.Y., Sung, W.K.: Sub-
tree Transfer Distance For Degree-D Phylogenies. Int. J. Found.
Comp. Sci. 15(6), 893–909 (2004)
7. Johnson, W., Lindenstrauss, J.: Extensions of Lipschitz Map-
pings into a Hilbert Space. Contemp. Math. 26, 189–206 (1984)
8. Li, M., Tromp, J., Zhang, L.: Some Notes on the Nearest Neigh-
bour Interchange Distance. J. Theor. Biol. 26(182), 463–467
(1996)
9. Pattengale, N.D., Moret, B.M.E.: A Sublinear-Time Randomized
Approximation Scheme for the Robinson–Foulds Metric. In:
Proceedings of the Tenth ACM Annual International Confer-
ence on Research in Computational Molecular Biology (RE-
COMB), pp. 221–230. Venice, Italy, April 2–5 2006
10. Robinson, D.F.: Comparison of Labeled Trees with Valency
Three. J. Comb. Theor. 11, 105–119 (1971)
11. Robinson, D.F., Foulds, L.R.: Comparison of Phylogenetic Trees.
Math. Biosci. 53, 131–147 (1981)
Nucleolus
2006; Deng, Fang, Sun
QIZHI FANG
Department of Mathematics, Ocean University of China,
Qingdao, China
Keywords and Synonyms
Nucleon; Kernel
Problem Definition
Cooperative game theory considers how to distribute the
total income generated by a set of participants in a joint
project to individuals. The Nucleolus, trying to capture the
intuition of minimizing dissatisfaction of players, is one
of the most well-known solution concepts among various
attempts to obtain a unique solution. In Deng, Fang and
Sun’s work [2], they study the Nucleolus of flow games
from the algorithmic point of view. It is shown that, for
a flow game defined on a simple network (arc capacity be-
ing all equal), computing the Nucleolus can be done in
polynomial time, and for flow games in general cases, both
the computation and the recognition of the Nucleolus are
NP-hard.
A cooperative (profit) game (N, v) consists of a player
set N = f1; 2; ; ng and a characteristic function
v :2
N
! R with v(;) = 0, where the value v(S)(S N)is
interpreted as the profit achieved by the collective action
of players in S. Any vector x 2 R
n
with
P
i2N
x
i
= v(N)
is an allocation. An allocation x is called an imputation if
x
i
v(fig)foralli 2 N.DenotebyI(v)thesetofimpu-
tations of the game.
Given an allocation x,theexcess of a coalition
S(S N)atx is defined as
e(S; x)=x(S) v(S) ;
where x(S)=
P
i2S
x
i
for S N.Thevaluee(S, x)can
be interpreted as a measure of satisfaction of coalition S
with the allocation x.Thecoreofthegame(N, v), denoted
by
C(v), is the set of allocations whose excesses are all
non-negative. For an allocation x of the game (N, v), let
(x)denotethe(2
n
2)-dimensional vector whose com-
ponents are the non-trivial excesses e(S, x), ; 6= S 6= N,ar-
ranged in a non-decreasing order. That is,
i
(x)
j
(x),
for 1 i < j 2
n
2. Denote by
l
the “lexicograph-
ically greater than” relationship between vectors of the
same dimension.
Definition 1 The Nucleolus (v)ofgame(N, v)istheset
of imputations that lexicographically maximize (x) over
582 N Nucleolus
the set of all imputations x 2 I(v). That is,
(v)=fx 2
I(v):(x)
l
(y)forally 2 I(v)g :
Even though, the Nucleolus may contain multiple points
by the definition, it was proved by Schmeidler [12]that
the Nucleolus of a game with non-empty imputation set
contains exactly one element. Kopelowitz [10]proposed
that the Nucleolus can be obtained by recursively solving
a sequential linear programs (SLP):
LP
k
:
max "
x(S)=v(S)+"
r
8S 2 J
r
r =0; 1; ; k 1
x(S) v(S)+" 8S 2 2
N
n
k1
[
r=0
J
r
x 2 I(v):
Here,
J
0
= f;; Ng and "
0
= 0 initially; the number "
r
is the optimum value of the r-th program (LP
r
), and
J
r
= fS 2 2
N
: x(S)=v(S)+"
r
for every x 2 X
r
g,where
X
r
= fx 2 I(v):(x;"
r
) is an optimal solution to LP
r
g.It
can be shown that after at most n 1 iterations, one ar-
rives at a unique optimal solution (x
;"
k
), where x
is just
the Nucleolus of the game. In addition, the set of optimal
solutions X
1
to the first program LP
1
is called the least core
of the game.
The definition of the Nucleolus entails comparisons
between vectors of exponential length, and with linear
programming approach, each linear programs in (SLP)
may possess exponential size in the number of players.
Clearly, both do not provide an efficient solution in gen-
eral.
Flow games, first studied in Kailai and Zemel [8,9],
arise from the profit distribution problem related to the
maximum flow in a network. Let D =(V ; E; !; s; t)be
a directed flow network, where V is the vertex set, E is the
arc set, ! : E ! R
+
is the arc capacity function, s and t are
the source and the sink of the network, respectively. The
network D is simple if !(e)=1foreache 2 E,whichis
denoted briefly by D =(V; E; s; t).
Definition 2 The flow game
f
=(E;) associated with
network D =(V; E; !; s; t)isdefinedby
(i) The player set is E;
(ii) 8S E, (S) is the value of a maximum flow from
s to t in the subnetwork of D consisting only of arcs
belonging to S.
Problem 1 (Computing the Nucleolus)
INSTANCE: A flow network D =(V; E; !; s; t).
QUESTION: Is there a polynomial time algorithm to com-
pute the Nucleolus of the flow game associated with D?
Problem 2 (Recognizing the Nucleolus)
INSTANCE: A flow network D =(V; E; !; s; t) and
y : E ! R
+
.
QUESTION: Is it true that y is the Nucleolus of the flow
game associated with D?
Key Results
Theorem 1 Let D =(V; E; s; t) be a simple network and
f
=(E;) be the associated flow game. Then the Nucleolus
() can be computed in polynomial time.
By making use of duality technique in linear program-
ming, Kalai and Zemel [9] gave an characterization on the
core of a flow game. They further conjectured that their
approach may serve as a practical basis for computing the
Nucleolus. In fact, the proof of Theorem 1 in the work of
Deng Fang and Sun [2] is just an elegant application of
Kalai and Zemel’s approach (especially the duality tech-
nique), and hence settling their conjecture.
Theorem 2 Given a flow game
f
=(E;) defined on net-
work D =(V; E; !; s; t), computing the Nucleolus () is
NP-hard.
Theorem 3 Given a flow game
f
=(E;) defined on
network D =(V; E; !; s; t), and an imputation y 2
I(),
checking whether y is the Nucleolus of
f
is NP-hard.
Although a flow game can be formulated as a linear pro-
duction game [1], the size of reduction may in general be
exponential in space, and consequently, their complexity
results on the Nucleolus are independent. However, in the
NP-hardness proof of Theorem 2 and 3, the flow game
constructed possesses a polynomial size formulation of
linear production game [2]. Therefore, as a direct corol-
lary, the same
NP-hardness conclusions for linear pro-
duction games are obtained. That is, both computing and
recognizing the Nucleolus of a linear production game are
NP-hard.
Applications
As an important solution concept in economics and game
theory, the Nucleolus and related solution concepts have
been applied to study insurance policies, real estate and
bankruptcy, etc. However, it is a challenging problem in
mathematical programming to decide what classes of co-
operative games permit polynomial time computation of
the Nucleolus.
Nucleolus N 583
The first polynomial time algorithm for Nucleolus in
a special tree game was proposed by Megiddo [11], in ad-
vocation of efficient algorithms for cooperative game so-
lutions. Subsequently, some efficient algorithms have been
developed for computing the Nucleolus, such as, for as-
signment games [13] and matching games [7]. On the neg-
ative side,
NP-hardness result was obtained for mini-
mum cost spanning tree games [3].
Granot, Granot and Zhu [6] observed that most of the
efficient algorithms for computing the Nucleolus are based
on the fact that the information needed to completely
characterize the Nucleolus is much less than that dictated
by its definition. Therefore, they introduced the concept
of a characterization set for the Nucleolus to embody the
notion of “minimum” relevant information needed for de-
termining the Nucleolus. Furthermore, based on the se-
quential linear programs (SLP), they established a general
relationship between the size of a characterization set and
the complexity of computing the Nucleolus. Following this
line of development, some known efficient algorithms for
computing the Nucleolus are derived directly.
Another approach to computing the Nucleolus is
taken by Faigle, Kern and Kuipers [4], which is motivated
by Schmeidler’s observation that the Nucleolus of a game
lies in the kernel [12]. In the case where the kernel of the
game contains exactly one core vector and the minimum
excess for any given allocation can be compute efficiently,
their approach derives a polynomial time algorithm for
the Nucleolus. This also generalizes some known results
on the computation of the Nucleolus. However, their algo-
rithm uses the ellipsoid method as a subroutine, it implies
that the efficiency of the algorithm is of a more theoretical
kind.
Open Problems
The field of combinatorial optimization has much to of-
fer for the study of cooperative games. It is usually the
case that the value of subgroup of players can be obtained
via a combinatorial optimization problem, where the game
is called a combinatorial optimization game. This class of
games leads to the applications of a variety of combinato-
rial optimization techniques in design and analysis of al-
gorithms, as well as establishing complexity results. One
of the most interesting result is the LP duality characteri-
zation of the core [1]. However, little work dealt with the
Nucleolus by using the duality technique so far. Hence, the
work of Deng, Fang and Sun [2] on computing the Nucle-
olus may be of independent interest.
There are still many unsolved complexity questions
concerning the Nucleolus. For the computation of the Nu-
cleolus of matching games, Kern and Paulusma [7]pro-
posed an efficient algorithm in unweighted case, and con-
jectured that it is in general
NP-hard. Since both simple
flow game and matching game fall into the class of pack-
ing/covering games, it is interesting to know the complex-
ity of computing the Nucleolus for other game models in
this class, such as, vertex covering games and minimum
coloring games.
For cooperative games arising from
NP-hard com-
binatorial optimization problems, the computation of the
Nucleolus may in general be a hard task. For example, in
a traveling salesman game, nodes of the graph are the play-
ers and an extra node 0, and the value of a subgroup S of
players is the length of a minimum Hamiltonian tour in
the subgraph induced by S [f0g [1]. It would not be sur-
prising if one shows that both the computation and the
recognition of the Nucleolus for this game model are
NP-
hard. However, this is not known yet. The same questions
are proposed for facility location games [5], though there
have been efficient algorithms for some special cases.
Moreover, when the computation of the Nucleolus is
difficult, it is also interesting to seek for meaningful ap-
proximation concepts of the Nucleolus, especially from the
political and economic background.
Cross References
Complexity of Core
Routing
Recommended Reading
1. Deng, X.: Combinatorial Optimization and Coalition Games. In:
Du, D., Pardalos, P.M. (eds.) Handbook of combinatorial opti-
mization, vol 2, pp 77–103, Kluwer, Boston (1998)
2. Deng, X., Fang, Q., Sun, X.: Finding Nucleolus of Flow Games.
Proceedings of the 17th annual ACM-SIAM symposium on Dis-
crete algorithm (SODA 2006). Lect. Notes in Comput. Sci. 3111,
124–131 (2006)
3. Faigle, U., Kern, W., Kuipers, J.: Computing the Nucleolus of
Min-cost Spanning Tree Games is
NP-hard. Int. J. Game The-
ory 27, 443–450 (1998)
4. Faigle, U., Kern, W., Kuipers, J.: On the Computation of the Nu-
cleolus of a Cooperative Game. Int. J. Game Theory 30, 79–98
(2001)
5. Goemans, M.X., Skutella, M.: Cooperative Facility Location
Games. J. Algorithms 50, 194–214 (2004)
6. Granot, D., Granot, F., Zhu, W.R.: Characterization Sets for the
Nucleolus. Int. J. Game Theory 27, 359–374 (1998)
7. Kern, W., Paulusma, D.: Matching Games: The Least Core and
the Nucleolus. Math. Oper. Res. 28, 294–308 (2003)
8. Kalai, E., Zemel, E.: Totally Balanced Games and Games of Flow.
Math. Oper. Res. 7, 476–478 (1982)
9. Kalai, E., Zemel, E.: Generalized Network Problems Yielding To-
tally Balanced Games. Oper. Res. 30, 998–1008 (1982)
584 N Nucleolus
10. Kopelowitz, A.: Computation of the Kernels of Simple Games
and the Nucleolus of n-person Games. RM-31, Math. Dept., The
Hebre University of Jerusalem (1967)
11. Megiddo, N.: Computational Complexity and the Game Theory
Approach to Cost Allocation for a Tree. Math. Oper. Res. 3, 189–
196 (1978)
12. Schmeidler, D.: The Nucleolus of a Characteristic Function
Game.SIAMJ.Appl.Math.17, 1163–1170 (1969)
13. Solymosi, T., Raghavan, T.E.S.: An Algorithm for Finding theNu-
cleolus of Assignment Games. Int. J. Game Theory 23, 119–143
(1994)
Oblivious Routing O 585
O
Oblivious Routing
2002; Räcke
NIKHIL BANSAL
IBM Research, IBM, Yorktown Heights, NY, USA
Keywords and Synonyms
Fixed path routing
Problem Definition
Consider a communication network, for example, the net-
work of cities across the country connected by commu-
nication links. There are several sender-receiver pairs on
this network that wish to communicate by sending traf-
fic across the network. The problem deals with routing all
the traffic across the network such that no link in the net-
work is overly congested. That is, no link in the network
should carry too much traffic relative to its capacity. The
obliviousness refers to the requirement that the routes in
the network must be designed without the knowledge of
the actual traffic demands that arise in the network, i. e. the
route for every sender-receiver pair stays fixed irrespective
of how much traffic any pair chooses to send. Designing
a good oblivious routing strategy is useful since it ensures
that the network is robust to changes in the traffic pattern.
Notations
Let G =(V; E) be an undirected graph with non-negative
capacities c(e)onedgese 2 E.Supposetherearek source-
destination pairs (s
i
; t
i
)fori =1;:::;k and let d
i
denote
the amount of flow (or demand) that pair i wishes to send
from s
i
to t
i
. Given a routing of these flows on G,thecon-
gestionofanedgee is defined as u(e)/c(e), the ratio of the
total flow crossing edge e divided by its capacity. The con-
gestion of the overall routing is defined as the maximum
congestion over all edges. The congestion minimization
problem is to find the routing that minimizes the maxi-
mum congestion. Observe that specifying a flow from s
i
to t
i
is equivalent to finding a probability distribution (not
necessarily unique) on a collection of paths from s
i
to t
i
.
The congestion minimization problem can be studied
in many settings. In the offline setting, the instance of the
flow problem is provided in advance and the goal is to
find the optimum routing. In the on line setting, the de-
mands arrive in an arbitrary adversarial order and a flow
must be specified for a demand immediately upon arrival;
this flow is fixed forever and cannot be rerouted later when
new demands arrive. Several distributed approaches have
also been studied where each pair routes its flow in a dis-
tributed manner based on some global information such
as the current congestion on the edges.
In this note, the oblivious setting is considered. Here
a routing scheme is specified for each pair of vertices in ad-
vance without any knowledge of which demands will actu-
ally arrive. Note that an algorithm in the oblivious setting
is severely restricted. In particular, if d
i
units of demand
arriveforpair(s
i
; t
i
), the algorithm must necessarily route
this demand according to the pre-specified paths irrespec-
tive of the other demands or any other information such as
congestion of other edges. Thus given a network graph G,
the oblivious flows need to be computed just once. Af-
ter this is done, the job of the routing algorithm is triv-
ial; whenever a demand arrives, it simply routes it along
the pre-computed path. An oblivious routing scheme is
called c-competitive if for any collection of demands D,the
maximum congestion of the oblivious routing is no more
than c times the congestion of the optimum offline solu-
tion for D. Given this stringent requirement on the quality
of oblivious routing, it is not a priori clear that any reason-
able oblivious routing scheme should exist at all.
Key Results
Oblivious routing was first studied in the context of per-
mutation routing where the demand pairs form a per-
mutation and have unit value each. It was shown that
any oblivious routing that specifies a single path (in-
stead of a flow) between every two vertices must neces-
586 O Oblivious Routing
sarily perform badly. This was first shown by Borodin and
Hopcroft [6] for hypercubes and the argument was later
extended to general graphs by Kaklamanis, Krizanc and
Tsantilas [12], who showed the following.
Theorem 1 ([6,12]) For every graph G of size n and max-
imum degree d and every oblivious routing strategy using
only a single path for every source-destination pair, there
is a permutation that causes an overlap of at least (n/d)
1/2
pathsatsomenode.ThusifeachedgeinGhasunitcapacity,
theedgecongestionisatleast(n/d)
1/2
/d.
Since there exists constant degree graphs such as the but-
terfly graphs that can route any permutation with loga-
rithmic congestion, this implies that such oblivious rout-
ing schemes must necessarily perform poorly on certain
graphs.
Fortunately, the situation is substantially better if the
single path requirement is relaxed and a probability dis-
tribution on paths (equivalently a flow) is allowed be-
tween each pair of vertices. In a seminal paper, Valiant and
Brebner [17] gave the first oblivious permutation routing
scheme with low congestion on the hypercube. It is in-
structive to consider their scheme. Consider an hypercube
with N =2
n
vertices. Represent vertex i by the binary ex-
pansion of i. For any two vertices s and t,thereisacanon-
ical path (of length at most n =logN)froms to t obtained
by starting from s and flipping the bits of s in left to right
order to match with that of t. Consider routing scheme
that for a pair s and t,itfirstchoosessomenodep uni-
formly at random, routes the flow from s to p along the
canonical path, and then routes it again from p to t along
the canonical path (or equivalently it sends 1/N units of
flow from s to each intermediate vertex p and then routes
it to t). An relatively simple analysis shows that
Theorem 2 ([17]) The above oblivious routing scheme
achieves a congestion of O(1)forhypercubes.
Subsequently, oblivious routing schemes were proposed
for few other special classes of networks. However, the
problem of designing oblivious routing schemes for gen-
eral graphs remained open until recently, when in a break-
through result Räcke showed the following.
Theorem 3 ([15]) For any undirected capacitated graph
G =(V ; E), there exist an oblivious routing scheme with
congestion O(log
3
n) wherenisthenumberofverticesinG.
The key to Räcke’s theorem is a hierarchical decompo-
sition procedure of the underlying graph (described in
further detail below). This hierarchical decomposition is
a fundamental combinatorial result about the cut struc-
ture of graphs and has found several other applications,
some of which are mentioned in Section “Applications”.
Räcke’s proof of Theorem 3 only showed the existence of
a good hierarchical decomposition and did not give an ef-
ficient polynomial time algorithm to find it. In subsequent
work, Harrelson, Hildrum and Rao [11]gaveapolyno-
mial time procedure to find the decomposition and im-
proved the competitive ratio of the oblivious routing to
O(log
2
n log log n).
Theorem 4 ([11]) There exists an O(log
2
n log log n)-
competitive oblivious routing scheme for general graphs and
moreover it can be found in polynomial time.
Interestingly, Azar et al. [4] show that the problem of find-
ing the optimum oblivious routing for a graph can be for-
mulated as a linear program. They consider a formulation
with exponentially many constraints; one for each possi-
ble demand matrix that has optimum congestion 1, that
enforces that the oblivious routing should have low con-
gestion for this demand matrix. Azar et al. [4]giveasep-
arationoracleforthisproblemandhenceitbesolved
using the ellipsoid method. A more practical polynomial
size linear program was given later by Applegate and Co-
hen [2]. Bansal et al. [5] considered a more general vari-
ant referred to as the online oblivious routing that can
also be used to find an optimum oblivious routing. How-
ever, note that without Räcke’s result, it would not be clear
whether these optimum routings were any good. More-
over these techniques do not give a hierarchical decom-
position, and hence may be less desirable in certain con-
texts. On the other hand, they may be more useful some-
times since they produce an optimum routing (while [11]
implies an O(log
2
n log log n)-competitive routing for any
graph, the best oblivious routing could have a much better
guarantee for a specific graph).
Oblivious routing has also been studied for directed
graphs, however the situation is much worse here. Azar
et al. [4] show that there exist directed graphs where any
oblivious routing is ˝(
p
n) competitive. Some positive re-
sults are also known [10]. Hajiaghayi et al. [8]showasub-
stantially improved guarantee of O(log
2
n)fordirected
graphs in the random demands model. Here each source-
sink pair has a distribution (that is known by the algo-
rithm) from which it chooses its demand independently.
A relaxation of oblivious routing known as semi-oblivious
routing has also been studied recently [9].
Techniques
This section describes the high level idea of Räcke’s result.
For a subset S V,letcap(S) denote the total capacity
of the edges that cross the cut (S; V n S)andletdem(S)
Oblivious Routing O 587
denote the total demand that must be routed across the
cut (S; V nS). Observe that q =max
SV
dem(S)/cap(S)is
a lower bound on the congestion of any solution. On the
other hand, the key result [3,13] relating multi-commodity
flows and cuts implies that there is a routing such that the
maximum congestion is at most O(q log k)wherek is the
number of distinct source sink pairs. However, note that
this by itself does not suffice to obtain good oblivious rout-
ings, since a pair (s
i
; t
i
) can have different routing for dif-
ferent demand sets. The main idea of Räcke was to impose
a tree like structure for routing on the graph to achieve
obliviousness. This is formalized by a hierarchical decom-
position described below.
Consider a hierarchical decomposition of the graph
G =(V; E) as follows. Starting from the set S = V,thesets
are partitioned successively until each set becomes single-
ton vertex. This hierarchical decomposition can be viewed
naturally as a tree T, where the root corresponds to the
set V, and leaves corresponds to the singleton sets {v}.
Let S
i
denote the subset of V corresponding to node i in
T.Foranedge(i; j) in the tree where i is the child of j,
assign it a capacity equal to cap(S
i
) (note that this is the
capacity from S
i
to the rest of G and not just capacity be-
tween S
i
and S
j
in G). The tree T is used to simulate rout-
ing in G and vice versa. Given a demand from u to v in G,
consider the corresponding (unique) route among leaves
corresponding to {u}and{v}inT. For any set of demands,
it is easily seen that the congestion in T is no more than the
congestion in G. Conversely, Räcke showed that there also
exists a tree T where the routes in T can be mapped back
to flows in G, such that for any set of demands the con-
gestion in G is at most O(log
3
n) times that in T.Inthis
mapping a flow along the (i; j)inthetreeT corresponds
to a suitably constructed flow between sets S
i
and S
j
in G.
Since route between any two vertices in T is unique, this
gives an oblivious routing in G.
Räcke uses very clever ideas to show the existence of
such a hierarchical decomposition. Describing the con-
struction is beyond the scope of this note, but it is instruc-
tive to understand the properties that must be satisfied by
such a decomposition. First, the tree T should capture the
bottlenecks in G,i.e.ifthereisasetofdemandsthatpro-
duces high congestion in G, then it should also produce
a high congestion in T. A natural approach to construct T
would be to start with V,splitV along a bottleneck (for-
mally, along a cut with low sparsity), and recurse. How-
ever, this approach is too simple to work. As discussed
below, T must also satisfy two other natural conditions,
known as the bandwidth property and the weight property
which are motivated as follows. Consider a node i con-
nected to its parent j in T.Then,i needs to route dem(S
i
)
flow out of S
i
and it incurs congestion dem(S
i
)/cap(S
i
)in
T. However, when T is mapped back to G,alltheflowgo-
ing out of S
i
must pass via S
j
. To ensure that the edges
from S
i
to S
j
are not overloaded, it must be the case that
the capacity from S
i
to S
j
is not too small compared to the
capacity from S
i
to the rest of the graph V n S
i
.Thisis
referred to as the bandwidth property. Räcke guarantees
that this is ratio is always ˝(1/ log n) for every S
i
and S
j
corresponding to edges (i; j) in the tree. The weight prop-
erty is motivated as follows. Consider a node j in T with
children i
1
;:::;i
p
, then the weight property essentially re-
quires that the sets S
i
1
;:::;S
i
p
should be well connected
among themselves even when restricted to the subgraph
S
j
. To see why this is needed, consider any communication
between, say nodes i
1
and i
2
in T. It takes the route i
1
to j
to i
2
, and hence in G; S
i
1
cannotuseedgesthatlieoutside
S
j
to communicate with S
i
2
. Räcke shows that these con-
ditions suffice and that a decomposition can be obtained
that satisfies them.
The factor O(log
3
n) in Räcke’s guarantee arises from
three sources. The first logarithmic factor is due to the
flow-cut gap [3,13]. The second is due to the logarithmic
height of the tree, and the third is due to the loss of a loga-
rithmic factor in the bandwidth and weight properties.
Applications
The problem has widespread applications to routing in
networks. In practice it is often required that the routes
must be a single path (instead of flows). This can often be
achieved by randomized rounding techniques (sometimes
under an assumption that the demands to capacity ratios
be not too large). The flow formulation provides a much
cleaner framework for studying the problems above.
Interestingly, the hierarchical decomposition also
found widespread uses in other seemingly unrelated ar-
eas such as obtaining good pre-conditioners for solving
systems of linear equations [14,16], for the all-or-nothing
multicommodity flow problem [7], online network opti-
mization [1]andsoon.
Open Problems
It is possible that any graph has an O(log n) competitive
oblivious routing scheme. Settling this is a key open ques-
tion.
Cross References
Routing
Separators in Graphs
Sparsest Cut