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

i

. The good can be produced in any amount, but producing

$X = \sum_{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) = \sum_{i=1}^n U_i(x_i) - C(X)$

, where

$X = \sum_{i=1}^n x_i$

, since this is a simple convex optimization problem.