Yannis A. Korilis
Abstract
The existence of Nash equilibria in noncooperative flow control in a general product-form network shared by K users is investigated. The performance objective of each user is to maximize its average throughput subject to an upper bound on its average time-delay. Previous attempts to study existence of equilibria for this flow control model were not successful, partly because the time-delay constraints couple the strategy spaces of the individual users in a way that does not allow the application of standard equilibrium existence theorems from the game theory literature. To overcome this difficulty, a more general approach to study the existence of Nash equilibria for decentralized control schemes is introduced. This approach is based on directly proving the existence of a fixed point of the best reply correspondence of the underlying game. For the investigated flow control model, the best reply correspondence is shown to be a function, implicitly defined by means of K interdependent linear programs. Employing an appropriate definition for continuity of the set of optimal solutions of parameterized linear programs, it is shown that, under appropriate conditions, the best reply function is continuous. Brouwer's theorem implies, then, that the best reply function has a fixed point.
- ~BAZARAA, M. S., JARVIS, J. J., AND SHERALI, H. D. 1990. Ltnear Programming and Network Flows, ~2nd ed. Wiley, New York. Google Scholar
- ~BERGE, C. 1963. Topological Spaces. Macmillan, New York.Google Scholar
- ~BORDER, K. C. 1985. Fixed-Poin,t Theorenzs with Applications to Economics and Game Theory. ~Cambridge University Press, New York.Google Scholar
- ~BOVOPOULOS, A. D., AND LAZAR, A. A. 1988. Asynchronous iterative algorithms for optimal load ~balancing. In Proceedings of tile 22nd Annual Conference on Information Sciences and Systems ~(Princeton, N.J., Mar.). Princeton Univ., Princeton, N.J., pp. 1051-1057.Google Scholar
- ~DASGUPTA, P., AND MASK/N, E. 1q86. The existence of equilibrium in discontinuous economic ~games. I: Theory. Rec. Econ. St~,d. 53, 1 26.Google Scholar
- ~DEMERS, A., KESHAV, S., AND SHENKER, S. 1989. Analysis and simulation of a fair queueing ~algorithm. In Proceedings of the ACM SIGCOM'89 (Austin, Tex., Sept. 19-22). ACM, New ~York, pp. 1 12. Google Scholar
- ~DOULIGERIS, C., AND MAZUMDAR, R. 1988. User optimal flow control in an integrated environ- ment. In Proceedings of the Indo-US Workshop on Signals and Systems (Bangalore, India, Jan.).Google Scholar
- ~DOUL1GERIS, C., AND MAZUMDAR, R. 1992. A game-theoretic approach to flow control m an ~integrated environment. J. Franklin Inst. 329, 3 (Mar.), 383-402.Google Scholar
- ~FUDENBERG, D, AND TIROLE, J. 1992. Game Theory. MIT Press, Cambridge, Mass.Google Scholar
- ~GALE, D. 1960. Tile Theory oJ Linear Economic Models. McGraw-Hill, New York.Google Scholar
- ~HSIAO, M.-T. T., AND LAZAR, A. A. 1984. Bottleneck modeling and decentralized optlmal flow ~control--I. Global objective. In Proceedings of the 18th Conference on Information Sciences and ~Systems (Princeton, N.J., Mar.). Princeton Univ., Princeton, N.J., pp. 169-173.Google Scholar
- ~HSIAO, M.-T. T., AND LAZAR, A. A. 1989. An extension to Norton's equivalent. Queueing Syst. ~Theory Appl. 5, 401-412. Google Scholar
- ~HSIAO, M.-T. T., AND LAZAR, A. A. 1991. Optimal decentralized flow control of Markovian ~Queueing networks with multiple controllers. PerJ7 Eual 13, 3, 181-204. Google Scholar
- ~K~LL~, F. P. 1979. ReuerslbihO' and Stochastic Networks. Wiley, New York.Google Scholar
- ~KORIHS, Y. A., AND LAZAR, A. A. 1992. Why is flow control hard: Optimality, fairness, partial ~and delayed reformation. CTR Technical Report 332-93-11, Center for Telecommunications ~Research, Columbia Univ., New York,Google Scholar
- ~LAZAR, A. A. 1983. Optimal control of a class of queuemg networks in equilibrium. IEEE Trans. ~Automatic Control AC-28, 11 (Nov.), 1001-1007.Google Scholar
- ~LUENBERGER, D. G. 1984. Linear and Nonlilzear Programmmg, 2nd ed. Addison-Wesley, Read- ~ing, Mass.Google Scholar
- ~M'fERSON, R. B. 1991. Game Theory: Analysts of Confltct. Harvard University Press, Cambridge, ~Mass.Google Scholar
- ~N^si4, J. 1951. Noncooperativc games. Anr~. Math. 54, 2 (Sept.), 286 295.Google Scholar
- ~ORDA, A., ROM, R., AND SH1MKiN, N. 1993. Competitive routing in multiuser commumcation ~networks. IEEE/ACM Trans. Netw. 1, 5 (Oct.), 510-521. Google Scholar
- ~PAREKH, A. K., AND GALLAGER, R. G. 1993. A generalized processor sharing approach to flow ~control in integrated services networks: The single-node case. IEEE/ACM Trans. Netw. 1, 3 ~(June), 344-357. Google Scholar
- ~ROSEN, J. B. 1965. Existence and uniqueness of equilibrium points for concave n-person games. ~Econometrtca 33, 3 (July), 520 534.Google Scholar
- ~SCHWARTZ, M. 1987. Telecommunication Networks: Protocols, Modeling and Analysts. Addison- ~Wesley, Reading, Mass. Google Scholar
- ~TAKAYAMA, A. 1985. MathematicalEconomics, 2nd ed. Cambridge University Press, New York.Google Scholar
- ~WALRAND, J. 1988. Introduction to Queueing Networks. Prentice-Hall, New York.Google Scholar
- ~ZHANG, Z., AND DOULIGERIS, C. 1992. Convergence of synchronous and asynchronous greedy ~algorithms in a multiclass telecommunications environment. IEEE Trans. Commun. 40, 8 ~(Aug.), 1277-1281.Google Scholar
Index Terms
- On the existence of equilibria in noncooperative optimal flow control
Recommendations
On the Complexity of Nash Equilibria and Other Fixed Points
We reexamine what it means to compute Nash equilibria and, more generally, what it means to compute a fixed point of a given Brouwer function, and we investigate the complexity of the associated problems. Specifically, we study the complexity of the ...
Complexity of Rational and Irrational Nash Equilibria
We introduce two new natural decision problems, denoted as RATIONAL NASH and IRRATIONAL NASH, pertinent to the rationality and irrationality, respectively, of Nash equilibria for (finite) strategic games. These problems ask, given a strategic game, ...
Games with secure equilibria
Components and objectsIn 2-player non-zero-sum games, Nash equilibria capture the options for rational behavior if each player attempts to maximize her payoff. In contrast to classical game theory, we consider lexicographic objectives: first, each player tries to maximize ...
Reviews
Jeffrey David Oldham
The authors present a new approach to proving the existence of Nash equilibria in noncooperative flow control. A fixed number of users, each noncooperatively seeking to maximize its throughput subject to an upper bound on its average time-delay, shares a set of queues in a network. Thus, the problem can be modeled using game theory. The authors prove that there exist flow strategies for the case where no user is unilaterally willing to change its flow strategy, that is, Nash equilibria exist. Most previous constrained-game research involved simpler models and relied on Rosen's theorem to prove the existence of Nash equilibria, but the more general setting prevents this theorem's use. Instead, the authors find a best reply correspondence, a mapping yielding a user's optimal strategy given all the other users' strategies, by simultaneously solving interdependent constraint optimization problems for each user. After proving that the correspondence is a continuous function mapping a convex and compact set onto itself, they invoke Brouwer's theorem, which proves that a fixed point (that is, a Nash equilibrium) exists. An appendix explores the concept of continuity in linear programming. The authors assume familiarity with queueing and game theory terminology, although they provide extensive intuition when introducing the problem. Familiarity with previous research in flow control theory may ease understanding.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments