On the Dual Gradient Descent Method for the Resource Allocation Problem in Multiagent Systems

We consider a sequence of block-separable convex programming problems describing theresource allocation in multiagent systems. We construct several iterative algorithms for setting theresource prices. Under various assumptions about the utility functions and resource constraints,we obtain estimates for the average deviation (regret) of the objective function from the optimalvalue and the constraint residuals. Here the average is understood as the expectation forindependent identically distributed data and as the time average in the online optimizationproblem. The analysis of the problem is carried out by online optimization methods and dualitytheory. The algorithms considered use the information concerning the difference between the totaldemand and supply that is generated by agents’ reactions to prices and corresponds to theconstraint residuals.