Queueing Problem with Dynamic and Heterogeneous Opportunity Costs
We study queueing problems in which agents have heterogeneous per-period waiting costs (their private information), which can vary with queue position and are thus dynamic. Our goal is to implement a Rawlsian allocation rule that minimises the maximum of individual waiting costs among all agents. Under complete information, we introduce the Just Algorithm, a simple method that always selects a Rawlsian queue. However, in settings with incomplete information where agents possess multidimensional private types i.e., the vector of their per-period waiting costs for each period, we prove that no Dominant Strategy Incentive-Compatible (DSIC) mechanism can implement the Rawlsian queueing rule over an unrestricted domain of agent types. This result underscores the challenges of implementing allocational fairness in multidimensional environments even with quasi-linear utility structure. To address this impossibility, we explore the necessary domain restrictions that allow for the existence of deterministic DSIC mechanisms. We use the Weak-Monotonicity condition from Bikhchandani et al. (2006) to do this. This condition is both necessary and sufficient for deterministic DSIC mechanisms to exist in our convex domain setting. Further, we restrict the domain to one-dimensional private information, where agents’ per-period waiting costs evolve according to publicly known agent-specific functions of their privately known first-period waiting costs. With this restriction, we construct a DSIC mechanism that implements the Just Algorithm, thereby ensuring that the allocational fairness objective is achieved. The results presented add to the growing literature on mechanism design in queueing problems by providing insights into the necessary and sufficient conditions for achieving fairness under strategic behaviour with heterogeneous waiting costs. This work highlights the complexities involved in mechanism design with multidimensional types and offers a viable solution within a significant and non-trivial restricted multidimensional domain with one-dimensional private information.
Queueing Problem with Dynamic and Heterogeneous Opportunity Costs
We study queueing problems in which agents have heterogeneous per-period waiting costs (their private information), which can vary with queue position and are thus dynamic. Our goal is to implement a Rawlsian allocation rule that minimises the maximum of individual waiting costs among all agents. Under complete information, we introduce the Just Algorithm, a simple method that always selects a Rawlsian queue. However, in settings with incomplete information where agents possess multidimensional private types i.e., the vector of their per-period waiting costs for each period, we prove that no Dominant Strategy Incentive-Compatible (DSIC) mechanism can implement the Rawlsian queueing rule over an unrestricted domain of agent types. This result underscores the challenges of implementing allocational fairness in multidimensional environments even with quasi-linear utility structure. To address this impossibility, we explore the necessary domain restrictions that allow for the existence of deterministic DSIC mechanisms. We use the Weak-Monotonicity condition from Bikhchandani et al. (2006) to do this. This condition is both necessary and sufficient for deterministic DSIC mechanisms to exist in our convex domain setting. Further, we restrict the domain to one-dimensional private information, where agents’ per-period waiting costs evolve according to publicly known agent-specific functions of their privately known first-period waiting costs. With this restriction, we construct a DSIC mechanism that implements the Just Algorithm, thereby ensuring that the allocational fairness objective is achieved. The results presented add to the growing literature on mechanism design in queueing problems by providing insights into the necessary and sufficient conditions for achieving fairness under strategic behaviour with heterogeneous waiting costs. This work highlights the complexities involved in mechanism design with multidimensional types and offers a viable solution within a significant and non-trivial restricted multidimensional domain with one-dimensional private information.