CS 684 Algorithmic Game Theory Scribe: Yogi Sharma (ys246@)Instructor: Eva Tardos September 19, 20051 Recap of last classNotation Throughout this class, by the cost of a solution, we mean the total delay incurred bythat solution. By cost of a flow, we mean,XP ∈PfP· `P(f) =Xe∈Ef(e) · `e(f(e)).In the last class, we proved a theorem lower bounding the quality of Nash equilibrium in non-atomic games. The common way to bound the quality of Nash equilibrium is through the conceptof “Price of Anarchy” (PoA). The price of anarchy is defined to be the worst case ratio betweencost of a Nash equilibrium and cost of an optimum solution. That isPrice of Anarchy = maxN=Nash EquilibriumCost of NOPT(1)We now state the theorem we proved in the last class.Theorem 1 ([Rou 03]) Let L be a class of delay functions containing all constant functions. Forany ` ∈ L, let `(·) be non-negative, continuous, monotone, differentiable function and x · `(x) beconvex. Furthermore, assume that L contains all the constant functions.Then, the worst caseNashOptratio (with respect to total delay in the network) for any network,any set of si-tipairs, any demand between the source-sink pairs dem(i) is attained on a simplenetwork having two nodes s and t, two link from s to t and demand being equal to r. One of thelink carries the latency function `(x) ∈ L and another has a constant latency equal to `(r).The worst case ratio is obtained by type of networks shown in figure 1.s1t1`e(x) ∈ L`f(x) = constant = `(r)dem(1) = rEdge eEdge fFigure 1: The worst possible ratio between the cost of a Nash equilibrium and the cost of anoptimum solution is obtained by type of simple networks shown above with two nodes, two linksand one commodity.`(x) = ax + b`0(x) = ax`00(x) = bFigure 2: A general linear edge delay function can be simulated by the functions from class L.2 Some applications of the theoremTheorem 1 gives us a general result about how bad the quality of a Nash equilibrium can becompared to an optimum solution. In this section, we will look at some concrete examples andcalculate the worst case ratios for them. In Section 2.1, we compute the price of anarchy fornetworks with linear delay functions. In Section 2.2, we consider the case of (general) polynomialdelay functions.2.1 Price of Anarchy for linear delay functionsConsider a scenario when delay functions on edges of network are linear in the congestion of theedge. That means the delay function for an edge e can be written as `e(x) = ax+b for real numbersa ≥ 0 and b ≥ 0. We need the linear coefficient non-negative to ensure the monotonicity of thefunction (the function should be monotonically increasing), and need b non-negative to ensure thatthe function itself is non-negative. With these edge delays on the edges of an arbitrary network,we want to compute the worst case ratio between average delay of (worst) Nash equilibrium andaverage delay of an optimum solution.Instead of considering all the possible networks, we can apply Theorem 1 and consider verysimple networks with two nodes and two parallel links as shown in Figure 1. At this point, it isinstructive to check that the assumptions of Theorem 1 are satisfied by linear functions with positivecoefficients. So, we will consider only the simplest networks to calculate the price of anarchy.Switch to simpler class of functions As our next step, we will replace the class of all linearfunctions by class of very special linear function L = {f(x) = ax|a ≥ 0}S{g(x) = b|b ≥ 0}.We note that this switching is without loss of generality. Any linear edge delay function can berepresented in terms of functions from class L by introducing an extra vertex as shown in Figure 2.Calculation of Price of Anarchy As suggested by Theorem 1, there are two cases to consider.In one case, the latency function `e(x) (on the upper edge in Figure 1) is a constant function, inanother, this function is a linear function.`e(x) = b0Latency on two edges is equal in this case. Therefore, all the solutions are of equalcost, whether it is a Nash equilibrium or an optimum solution. So, in this case, the worstcase ratio is 1.`e(x)`f(x) = `e(r)(a constant)`∗e(x) = `e(x) + x · `0e(x)`∗f(x) = `e(r)⇒Figure 3: The problem of finding an optimal flow in a network can be reduced to finding a Nashwith modified delay function. The modification needed is shown in the network on the right.`e(x) = ax Let the demand be r. The delay on the lower edge (see Figure 1) is ar. A Nashsolution will send all flow on the upper edge, incurring total delay of r · ar = ar2.For determining the optimum solution, we note a theorem from a previous lecture whichstates the following.Theorem 2 Let G be a network with latency functions `e(x) on its edges. A flow in Gis optimum (minimum total delay) if and only if it is a Nash flow with respect to `∗e(x) =`e(x) + x · `e(x) delay functions on the edges.With these modified delay function, the network becomes as in Figure 3.Nash flow in the modified network splits the flow in such a way that (modified) delay on boththe links is equal. Delay on upper link is ax + x · a = 2ax and on the lower link is ar. InNash flow, let the upper edge carries flow amount ζ. We have,2aζ = ar ⇒ ζ = r/2. (2)Delay incurred by the optimum solution is ζ ·aζ +(1 − ζ)· ar =34ar2, while the delay incurredby Nash flow is ar2. (All the flow goes via upper edge.) Therefore, the worst possible ratioof cost of Nash and optimal cost ifar234ar2=43.We have proved the following theorem.Theorem 3 ([RT 02]) The worst case ratio between the cost of a Nash solution and the optimalcost in networks with linear edge delays function is less than or equal to 4/3.We note that the above worst case ratio is actually achieved by simple two node, two linkexample. Consider the network with upper edge delay function `e(x) = x and lower edge delayfunction `f(x) = 1, and demand of one unit. In this network, Nash incurs a cost of 1 while optimumsolution splits the flow evenly between the two edges and incurs a cost of 3/4. So, the ratio is 4/3.2.2 Price of Anarchy for general polynomialsIn this section, we consider networks with edge delays being arbitrary polynomials and bound thePrice of Anarchy for them. A natural question to ask is the following: if the edge delays arepolynomials of degree at most p, what can we say about the Price of Anarchy? The followingtheorem, whose (hand-wavy) proof appear later in this section answers this