## Max-Weight Scheduling

We define a discrete-time queueing network where there are restrictions on which queues can be served simultaneously. We give a policy for serving queues which is stable whenever it is possible to stabilize the queueing network.

## Blackwell Approachability

Sequentially a player decides to play $\{p_t\}_{t=1}^\infty$ and his adversary decides $\{q_t\}_{t=1}^\infty$. At time $t$, a decision $(p_t,q_t)$ results in a vector payoff $A(p_t,q_t)\in {\mathbb R}^k$. Given $a_t$ is the average vector payoff at time $t$, Blackwell’s Approachability Theorem is a necessary and sufficient condition so that, regardless of the adversary’s decisions, the player makes the sequence of vectors $\{a_t\}_{t=1}^\infty$ approach a convex set ${\mathcal A}$.

## Power-of-k Choices

We consider a model of a large number of single server queues. When a job arrives, we assume it chooses between $k$ queues. The job then chooses to join the shortest of these queues. We show that such choice can dramatically reduce queue sizes.

## Little’s Law Here $\bar{N}$ is the long run queue length; $\bar{W}$ is the expected waiting time; $\lambda$ is the arrival rate at the queue.