Essays on sequencing problems with welfare bounds

Abstract

This is a comprehensive study of sequencing problems with welfare bounds. The sequencing frame- work comprises a finite set of agents and a single facility provider that processes their jobs sequentially. Each job is characterized by its per period waiting cost and processing time. The designer has to fix the order in which agents are served and the monetary compensations to be paid/received. The sequenc- ing and queueing literature has studied the impact of imposing lower bounds on the utility function in various contexts. The most natural bound is the first come first serve protocol where there is a preexisting order in which agents arrive. From the cooperative game perspective, sequencing games with initial order was analyzed by Curiel et al. (1989) and, from the mechanism design perspective, the queueing problem was addressed by Chun et al. (2017) and by Gershkov & Schweinzer (2010). There are other fairness bounds that have been studied from the normative viewpoint. In queueing, the notion of identical costs bound (ICB), analogous to identical preferences lower bound,1 has been analyzed by Maniquet (2003), Chun (2006b), Mitra (2007) and Chun & Yengin (2017). In the se- quencing context, Mishra & Rangarajan (2007) and De (2013) study the expected cost bound where agents have identical urgency indices, implying that every possible ordering is equally likely. Chun & Yengin (2017) have introduced welfare lower bounds with the k-welfare lower bound guaranteeing each agent his utility at the kth queue position with zero transfer. In the queueing literature, Ger- shkov & Schweinzer (2010) honor an agent’s existing service rights by defining individual rationality with respect to an existing mechanism (first come first serve and random arrival schedules). They have examined whether efficient reordering is possible when individuals are rational with respect to the status quo. This thesis introduces a universal representation of all the previously studied welfare bounds in the literature. Such a generalized representation enriches the existing literature by allowing future studies to be more simplified and compact. We term this bound as the “generalized minimum welfare bound” (GMWB). It is type dependent and offers every agent a minimum guarantee on their utilities. In other words, such an assurance puts an upper limit on the maximum disutility of waiting for a service and safeguards all agents against adverse circumstances. The dissertation imposes the generalized minimum welfare bound property in the sequencing framework and studies its impact using three different approaches, viz.,the strategic approach, the egalitarian approach and the cooperative game approach. The strategic notion used in the first es- say is that of strategyproofness. We characterize the entire class of mechanisms that satisfies outcome efficiency, strategyproofness and the GMWB property. The chapter provides relevant theoretical ap- plications and also addresses issues of feasibility (or, budget balance). The second essay uses the classic Lorenz criterion that embodies the essence of egalitarianism in the distribution of the final outcome and can be used to make inequality comparisons. We find that the constrained egalitarian mechanism is the only Lorenz optimal mechanism in the class of feasible mechanisms satisfying the GMWB prop- erty. The final essay maps the sequencing problem to a characteristic form game using an optimistic and a pessimistic approach to define the worth of a coalition. Under both the approaches, the trans- fers are designed such that, every agent receives his share of Shapley value payoff as his final utility. We provide a necessary and sufficient condition for the allocation rule to satisfy GMWB. The paper also provides key insights on the existence of the core allocations in sequencing games.