We consider a basic resource allocation game, where the players' strategy spaces are subsets of @math and cost utility functions are parameterized by some common vector @math and, otherwise, only depend on the own strategy choice. A strategy of a player can be interpreted as a vector of resource consumption and a joint strategy profile naturally leads to an aggregate consumption vector. We assume that resources can be priced, that is, the game is augmented by a price vector @math and players have quasi-linear overall costs utilities meaning that in addition to the original costs utilities, a player needs to pay the corresponding price per consumed unit. We investigate the following question: for which aggregated consumption vectors @math can we find prices @math that induce an equilibrium realizing the targeted consumption profile? For answering this question, we develop a duality-based framework and derive a characterization of the existence of such @math and @math . We show that our characterization can help to unify parts of three largely independent streams in the literature -- tolls in transportation systems, Walrasian market equilibria and congestion control in communication networks. Besides reproving existing results we establish novel existence results by drawing connections to polyhedral combinatorics and discrete convexity.
Our first main result (Theorem ) relies on a decomposition property of the Lagrangian (for separable problems) and the use of Lagrange multipliers for pricing the resources. This approach is not new and has been developed before, see for instance Bertsekas and Ghallager @cite_16 and Palomar and Chiang @cite_44 . In particular, motivated by the dual-decomposition of the convex programming formulation of the bandwidth allocation problem of @cite_56 , Palomar and Chiang @cite_44 described how the Lagrangian of a general separable optimization problem [ i N U_i( x_i) x_i X_i, i N, ; i N h_i( x_i) u ] can be decomposed into @math independent problems. The difference of this model to ours is the parameterization of the cost utility functions @math with respect to the capacity vector @math . This degree of freedom is a strict generalization and allows to model dependencies of targeted capacity vectors with respect to the intrinsic cost utilities - a prime example appears in nonatomic congestion games, where the cost function of an agent depends on the aggregated load vector. Moreover, this dependency allows to model with respect to allocations which are not possible in the model of Palomar and Chiang @cite_44 .
@cite_44 @cite_16 @cite_56
2162986857 2159715570
A systematic understanding of the decomposability structures in network utility maximization is key to both resource allocation and functionality allocation. It helps us obtain the most appropriate distributed algorithm for a given network resource allocation problem, and quantifies the comparison across architectural alternatives of modularized network design. Decomposition theory naturally provides the mathematical language to build an analytic foundation for the design of modularized and distributed control of networks. In this tutorial paper, we first review the basics of convexity, Lagrange duality, distributed subgradient method, Jacobi and Gauss-Seidel iterations, and implication of different time scales of variable updates. Then, we introduce primal, dual, indirect, partial, and hierarchical decompositions, focusing on network utility maximization problem formulations and the meanings of primal and dual decompositions in terms of network architectures. Finally, we present recent examples on: systematic search for alternative decompositions; decoupling techniques for coupled objective functions; and decoupling techniques for coupled constraint sets that are not readily decomposable This paper analyses the stability and fairness of two classes of rate control algorithm for communication networks. The algorithms provide natural generalisations to large-scale networks of simple additive increase multiplicative decrease schemes, and are shown to be stable about a system optimum characterised by a proportional fairness criterion. Stability is established by showing that, with an appropriate formulation of the overall optimisation problem, the network's implicit objective function provides a Lyapunov function for the dynamical system defined by the rate control algorithm. The network's optimisation problem may be cast in primal or dual form: this leads naturally to two classes of algorithm, which may be interpreted in terms of either congestion indication feedback signals or explicit rates based on shadow prices. Both classes of algorithm may be generalised to include routing control, and provide natural implementations of proportionally fair pricing.