Worst-Case Efficiency Analysis of Queueing Disciplines

摘要

Consider n users vying for shares of a divisible good. Every user i wants as much of the good as possible but has diminishing returns, meaning that its utility U_i(x_i) for x_i ≥ 0 units of the good is a nonnegative, nondecreasing, continuously differentiable concave function of .x,;. The good can be produced in any amount, but producing X = ∑_(i=1)~n x_i units of it incurs a cost C(X) for a given nondecreasing and convex function C that satisfies C(0) = 0. Cost might represent monetary cost, but other interesting interpretations are also possible. For example, x_i could represent the amount of traffic (measured in packets, say) that user i injects into a queue in a given time window, and C(X) could denote aggregate delay (X·c(X), where c(X) is the average per-unit delay). An altruistic designer who knows the utility functions of the users and who can dictate the allocation x = (x_1,..., x_n) can easily choose the allocation that maximizes the welfare W(x) = ∑_(i=1)~n U_i(x_i) - C(X), where X = ∑_(i=1)~n x_i, this is a simple convex optimization problem.