Stability and fairness in sequencing games: optimistic approach and pessimistic scenarios

Sequencing deals with the problem of assigning slots to agents who are waiting for a service. We study sequencing problems as coalition form games defined in optimistic and pessimistic scenarios. Each agent's level of utility is his Shapley value payoff from the corresponding coalition form game. First, we show that while the core of the optimistic game is always empty, the Shapley value of the pessimistic game is an allocation in its core. Second, we impose the "generalized welfare lower bound" (GWLB) that ex-ante guarantees each agent a minimum level of utility. One of many application of GWLB is the "expected costs bound". It guarantees each agent his expected cost when all arrival orders are equally likely. We prove that the Shapley value payoffs (in both optimistic and pessimistic scenarios) satisfy GWLB if and only if it satisfies the expected costs bound (ECB).