|
Article Excerpt
In this paper we characterize the "price of anarchy," i.e., the inefficiency between user and system optimal solutions, when costs are nonseparable, asymmetric and nonlinear, generalizing earlier work that has addressed "the price of anarchy" under separable costs. The results in this paper apply primarily to nonatomic games such as the traffic equilibrium problem, but also in competitive multiperiod pricing and competitive supply chain settings. The bounds established in this paper are tight and explicitly account for the degree of asymmetry and nonlinearity of the cost function. We first provide a proof method for problems with a positive definite Jacobian matrix. Subsequently, we use ideas from semidefinite optimization in order to account for problems with a positive semidefinite Jacobian matrix (where the first approach does not apply). This latter connection also provides a different application of semidefinite optimization.
Key words: price of anarchy; system and user-optimization; variational inequalities; traffic equilibrium
1. Introduction. There has been an increasing literature in recent years trying to quantify the inefficiency of Nash equilibrium problems (user optimization) in noncooperative games. The fact that there is not full efficiency in the system is well known, both in the economics literature and in the transportation literature (see Braess [3], Dubey [12]). This inefficiency of user optimization was first quantified by Koutsoupias and Papadimitriou [20] in the context of a load-balancing game. They coined the term "the price of anarchy" for characterizing the degree of efficiency loss. The type of setting they consider is an atomic game. Subsequently, Roughgarden and Tardos [32, 33] and Roughgarden [31, 30] applied this idea to nonatomic games, with a particular focus on the classical network equilibrium problem in transportation with arc cost functions that are separable in terms of the arc flows. They established worst-case bounds for measuring this inefficiency for affine separable cost functions and subsequently for special classes of separable nonlinear ones (such as polynomials). It should be noted that Marcotte [21] presented results on the price of anarchy for a bilevel network design model. Johari and Tsitsiklis [19] also studied this problem in the context of resource allocation between users sharing a common resource. In their case, the problem also reduces to one where each player has a separable payoff function. Correa et al. [7] have also studied the price of anarchy in the context of transportation for capacitated networks. They further consider other cost (also referred to as latency) structures such as maximum latency (see Correa et al. [6]). The cost functions they consider are also separable. The paper by Chau and Sim [4] has recently considered the case of nonseparable, symmetric cost functions giving rise to the same bound as Roughgarden and Tardos [33].
Wardrop [36] was perhaps the first to state the equilibrium principles in the context of transportation. Dafermos and Sparrow [11] coined the terms "user-optimized" and "system-optimized" to distinguish between the Nash equilibrium where users act unilaterally in their own self-interest versus when users are forced to select the routes that optimize the total network efficiency. Smith [34] and Dafermos [8] recognized that this problem could be cast as a variational inequality. In Dafermos [9], and more recently from Hearn and coauthors [17, 18], Cole et al. [5] considered how the user-optimized problem can become a centralized system optimization problem through the imposition of tolls. The monograph by Patriksson [27] and the review paper by Florian and Hearn [13], and the references therein, summarize the relevant literature in traffic equilibrium problems. Traffic equilibrium problems are typically modeled through variational inequalities (see [section] 4 for details). The books by Pang and Facchinei [26] summarize the developments in the general area of variational inequalities.
In this paper we establish a bound on the ratio of the overall profit of the system between the user and the system-optimized setting. Although the primary application is transportation, as we discuss at the end of the paper, the results apply to other application settings as well. This work is the first to consider nonseparable, asymmetric cost functions and is important because it allows modeling of more realistic situations. Furthermore, it allows a unifying framework that naturally extends results in the current literature. In particular, our contributions versus the existing literature are the following.
(i) We consider nonseparable, asymmetric, nonlinear functions in the sense that cost functions also depend on the strategies of the competitors. For such cost functions, we cannot construct a convex optimization reformulation as in the separable case (see Beckmann et al. [2]). Furthermore, cost functions can be asymmetric in the sense that different competitors' strategies affect their cost functions differently. This generalization is important because the strategies of one's competitors will influence his/her own cost in an asymmetric way. In particular, we introduce a measure of asymmetry (denoted by [c.sup.2] in [section]2) that quantifies the degree of asymmetry of the competitors' cost functions. We introduce a measure that quantifies the degree of nonlinearity of the problem function (denoted by A in [section]2). We establish that the ratio of the total cost in the system operating in a user-optimized setting versus the total cost in a system-optimized setting is bounded by
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].
For affine problems, the bound becomes
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].
We illustrate how our results are a natural generalization of the bound established by Roughgarden [31] and Roughgarden and Tardos [33] because when the problem functions are separable and affine the bound becomes 4/3. Furthermore, the work by Chau and Sim [4] (where the functions are nonseparable but symmetric) becomes a special case because the bound is still 4/3 because [c.sup.2] = 1. The results in the affine case do not depend on the structure of the feasible region and, as a result, allow it to be a nonconvex set. Nevertheless, existence of solution issues could arise in such settings (see Cole et al. [5]).
(ii) When the cost function has no constant term, the bound becomes [c.sup.2][A.sup.2] - 2(A - 1). If in addition the problem function is affine, then the bound becomes [c.sup.2]. Therefore, although for affine symmetric costs with no constant terms the price of anarchy is one, if the costs are very asymmetric (despite being affine and with no constant terms) the price of anarchy can still be very large. (iii) We establish that the bounds above are tight.
(iv) The previous analysis and bounds rely on the assumption that the Jacobian matrix of the problem function F is a positive definite matrix. If the Jacobian matrix is positive semidefinite, then the asymmetry constant [c.sup.2] is not well defined. As a result, we consider a more general approach, based on a semidefinite optimization formulation, that applies to the positive semidefinite case. We illustrate that this approach gives rise to the same bound when the Jacobian matrix is positive definite, and hence is a direct generalization.
The remainder of this paper is structured as follows. In [section]2, we establish a bound for nonlinear asymmetric problems where the Jacobian matrix of the problem function is positive definite, and establish that this bound is tight. In [section]3, we generalize the bound to problems with a positive semidefinite Jacobian, and hence nonunique solutions. In this case, we introduce a way to determine bounds using a semidefinite programming (SDP) formulation. We illustrate that the SDP approach yields the same bound in the case of a positive definite Jacobian matrix. Finally, in [section]4 we discuss the application of the results to traffic equilibrium as well as other application areas.
2. A bound for nonlinear asymmetric cost functions with a positive definite Jacobian matrix. In this paper, we establish a bound between the user and the system optimization problems in the context of minimizing cost. For the system-optimized (SO) centralized problem we will consider the minimization problem [min.sub.x[member of]K] F[(x).sup.t] x. For the user-optimized (UO) decentralized problem we will consider the variational inequality problem of finding [x.sub.u] [member of] K satisfying
F[([x.sub.u]).sub.t](x - [x.sub.u]) [greater than or equal to] 0, for all x [member of] K. (1)
Throughout this paper, [x.sub.u] and [x.sub.s] denote solutions of the user and system optimization problems, respectively. Then, [Z.sub.u] = F[([x.sub.u]).sup.t][x.sub.u] is the total cost for the UO problem and [Z.sub.s] = F[([x.sub.s]).sup.t][x.sub.s] = [min.sub.x[member of]K] F[(x).sup.t]x the total cost for the SO problem.
One of the major application areas of these results is transportation. The user optimization problem is in this case traditionally formulated as a variational inequality problem (see, for example, Florian and Hearn [13] and Patriksson [27]) with problem function F representing the vector of the arc costs per unit of flow and the vector of variables x representing the arc flows. The system optimization problem...
|
