A robust protocol should perform well for a variety of mixtures of users. We quantify this idea of robustness by examining the equilibrium efficiency loss exhibited by a protocol under a worst-case choice of user preferences. We apply this idea to the design of queueing disciplines with heterogeneous users, in particular compare the worst-case equilibrium efficiency loss of a FIFO queue to one employing Shenker's Fair Share discipline. Joint work with Damon Mosk-Aoyama.
Copyright. All Rights Reserved.