AbstractThe 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 parametrized 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. Copyright 1995 by ACM, Inc.
The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.
Categories and Subject Descriptors: C.2.3 [Computer-Communication Networks]: Network Operations -- network management; D.4.8 [Operating Systems]: Performance -- qeueing theory; G.1.6 [Numerical Analysis]: Optimization
General Terms: Performance, Theory
Additional Key Words and Phrases: Fixed points, flow control, game theory, Nash equilibria