Nov. 28 (10:00-11:00) room C.714
Sreoshi Banerjee (BME QSMS)
On the (non-) coincidence of the Serial and Shapley solutions in multi-server waiting line problems
Existing literature on single-server waiting line problems (sequencing, queueing, and scheduling) has traditionally designed equitable compensations by associating a transferable utility (TU) game to a problem and assign agents their respective Shapley shares. We study two widely acceptable cost sharing rules the Shapley value and the serial rule. We identify the domains in which these two rules coincide and, for those in which they differ, provide a rationale for why the serial rule is a preferable approach to cost-sharing over the Shapley value. We show that the optimistic Shapley agrees with the serial rule in the following domains: (1) multi-server queueing with divisible or non-divisible jobs; and (2) multi-server scheduling with non-divisible jobs. This coincidence fails for multi-server scheduling with divisible jobs. The pessimistic Shapley agrees with the reverse serial rule in: (1) multi-server queueing with divisible or non-divisible jobs. This coincidence fails in multi-server scheduling with divisible or non-divisible jobs. From a fairness viewpoint, the pessimistic Shapley value satisfies an undesirable property called “order reversal”, in contrast to the reverse serial rule, which satisfies “order preservation”. We characterize the serial and reverse serial rules for all the above domains.
The talk is based on joint work with Christian Trudeau.