Daniel Freund
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Daniel Freund has a total of 28 co-authors. Here are the top co-authors by number of shared publications:
David B. Shmoys
School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14850
6 shared publications- Wentao Weng
Massachusetts Institute of Technology
6 shared publications Shane G. Henderson
Cornell University
4 shared publicationsDavid P. Williamson
School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14850
3 shared publications- Jiayu (Kamessi) Zhao
Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02142
3 shared publications - Siddhartha Banerjee
School of Operations Research and Information Engineering, Cornell University, Ithaca, NY, USA
3 shared publications
Latest Publications
- 20 October 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Manufacturing & Service Operations Management
The Dedicated Docket in U.S. Immigration Courts: An Analysis of Fairness and Efficiency Properties
Problem definition: The dedicated docket was introduced by the Biden administration to reform the immigration system. It creates a separate queue for immigration proceedings where judges are supposed to issue a decision for each case within a target timeframe. The administration announced the docket with the goals of speed, accuracy, and fairness. Though the program meets its first goal, legal advocacy groups report that this comes at the expense of the last. Referring to it as a “denial of justice” (Murphy et al. 2023), they find that cases on the dedicated docket routinely fail to access legal representation and have a much lower asylum grant rate. Against this backdrop, we aim to understand the operational implication of the dedicated docket. Methodology/results: We develop a stylized queueing model wherein a policymaker (PM) routes asylees to either the regular or the dedicated docket and sets a delay target for the dedicated one. Constrained by the target, the court allocates its limited capacity to minimize the average delay. Immigration lawyers schedule their time between dockets to maximize the rate of successful asylum cases. Compared with a single docket, we show that the dedicated-docket system can Pareto improve both the speed and accuracy. However, if the PM sets its decision poorly, the system may be dominated by a single docket. Moreover, the dedicated-docket system can satisfy three natural fairness properties only if it is dominated by the single docket. Managerial implications: Our analysis can inform both policymakers and legal advocacy groups. We prove that the lack of fairness is a fundamental design flaw of the new program. Nonetheless, through delay differentiation, the program also enables a surprising efficiency gain. Policymakers and legal advocacy groups should be aware of such trade-offs: the same delay differentiation that enables greater efficiency also creates unfairness between dockets. Funding: This work was supported through a Massachusetts Institute of Technology Social and Ethical Responsibilities of Computing seed grant. Supplemental Material: The online appendix is available at https://doi.org/10.1287/msom.2024.1023 and https://github.com/df365/Freund_ElectronicSupplements/blob/main/Docket_OnlineSupplement.pdf .
- 20 October 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Manufacturing & Service Operations Management
The Dedicated Docket in U.S. Immigration Courts: An Analysis of Fairness and Efficiency Properties
Problem definition: The dedicated docket was introduced by the Biden administration to reform the immigration system. It creates a separate queue for immigration proceedings where judges are supposed to issue a decision for each case within a target timeframe. The administration announced the docket with the goals of speed, accuracy, and fairness. Though the program meets its first goal, legal advocacy groups report that this comes at the expense of the last. Referring to it as a “denial of justice” (Murphy et al. 2023), they find that cases on the dedicated docket routinely fail to access legal representation and have a much lower asylum grant rate. Against this backdrop, we aim to understand the operational implication of the dedicated docket. Methodology/results: We develop a stylized queueing model wherein a policymaker (PM) routes asylees to either the regular or the dedicated docket and sets a delay target for the dedicated one. Constrained by the target, the court allocates its limited capacity to minimize the average delay. Immigration lawyers schedule their time between dockets to maximize the rate of successful asylum cases. Compared with a single docket, we show that the dedicated-docket system can Pareto improve both the speed and accuracy. However, if the PM sets its decision poorly, the system may be dominated by a single docket. Moreover, the dedicated-docket system can satisfy three natural fairness properties only if it is dominated by the single docket. Managerial implications: Our analysis can inform both policymakers and legal advocacy groups. We prove that the lack of fairness is a fundamental design flaw of the new program. Nonetheless, through delay differentiation, the program also enables a surprising efficiency gain. Policymakers and legal advocacy groups should be aware of such trade-offs: the same delay differentiation that enables greater efficiency also creates unfairness between dockets. Funding: This work was supported through a Massachusetts Institute of Technology Social and Ethical Responsibilities of Computing seed grant. Supplemental Material: The online appendix is available at https://doi.org/10.1287/msom.2024.1023 and https://github.com/df365/Freund_ElectronicSupplements/blob/main/Docket_OnlineSupplement.pdf .
- Top Cited Papers
- 1 March 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Manufacturing & Service Operations Management
- Vol. 28  (2) , 496-516
On the Supply of Autonomous Vehicles in Platforms
Problem definition: The ongoing large-scale deployment of autonomous vehicle (AV) technology has the potential to fundamentally change the transportation landscape. Due to the high cost of AV hardware, the most likely path to widespread AV use is via platforms that can sustain high utilization, such as ride-hailing and delivery services. Our work studies the incentives of stakeholders in such deployments, possible misalignments, and contracting solutions to overcome them. Methodology/results: We consider four potential operational models to commercialize AVs, which we model as a supply chain game between a platform, an AV supplier, and human individual contractors (ICs), including (1) an open platform in which the AV supplier and ICs bring their own vehicles to the system, (2) an AV-supplier operated platform without ICs, (3) a platform that sources AVs through leasing contracts, and (4) an integrated supply chain. We find that except for the AV-only platform, all deployment models are subject to a risk of AV underutilization due to the need to maintain the ICs’ utilization sufficiently high to ensure ICs remain engaged. As AV underutilization propagates in a nonintegrated supply chain, an open platform can become arbitrarily worse than supply chain integration, and careful usage commitments are needed to overcome the efficiency loss. Managerial implications: This paper identifies a new kind of supply chain misalignment that is likely to emerge as AVs become deployed technology, which both platform operators and AV suppliers should be mindful of. Moreover, we demonstrate the value of usage commitment in the deployment of AVs through an open platform, which makes it more efficient than AV-only/AV leasing platforms. History: This paper was selected as part of the 1RR initiative between the M&SOM Journal and the MSOM Society. This particular paper was part of the 2024 MSOM Service Operations SIG Conference. Supplemental Material: The online appendix is available at https://doi.org/10.1287/msom.2024.1175 .
- 1 March 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Manufacturing & Service Operations Management
- Vol. 28  (2) , 496-516
Top Cited PapersOn the Supply of Autonomous Vehicles in Platforms
Problem definition: The ongoing large-scale deployment of autonomous vehicle (AV) technology has the potential to fundamentally change the transportation landscape. Due to the high cost of AV hardware, the most likely path to widespread AV use is via platforms that can sustain high utilization, such as ride-hailing and delivery services. Our work studies the incentives of stakeholders in such deployments, possible misalignments, and contracting solutions to overcome them. Methodology/results: We consider four potential operational models to commercialize AVs, which we model as a supply chain game between a platform, an AV supplier, and human individual contractors (ICs), including (1) an open platform in which the AV supplier and ICs bring their own vehicles to the system, (2) an AV-supplier operated platform without ICs, (3) a platform that sources AVs through leasing contracts, and (4) an integrated supply chain. We find that except for the AV-only platform, all deployment models are subject to a risk of AV underutilization due to the need to maintain the ICs’ utilization sufficiently high to ensure ICs remain engaged. As AV underutilization propagates in a nonintegrated supply chain, an open platform can become arbitrarily worse than supply chain integration, and careful usage commitments are needed to overcome the efficiency loss. Managerial implications: This paper identifies a new kind of supply chain misalignment that is likely to emerge as AVs become deployed technology, which both platform operators and AV suppliers should be mindful of. Moreover, we demonstrate the value of usage commitment in the deployment of AVs through an open platform, which makes it more efficient than AV-only/AV leasing platforms. History: This paper was selected as part of the 1RR initiative between the M&SOM Journal and the MSOM Society. This particular paper was part of the 2024 MSOM Service Operations SIG Conference. Supplemental Material: The online appendix is available at https://doi.org/10.1287/msom.2024.1175 .
- 23 October 2025
- Published by Elsevier in Transportation Research Part C: Emerging Technologies
- Vol. 181
Pricing fast and slow: Limitations of dynamic pricing mechanisms in ride-hailing
- 23 October 2025
- Published by Elsevier in Transportation Research Part C: Emerging Technologies
- Vol. 181
Pricing fast and slow: Limitations of dynamic pricing mechanisms in ride-hailing
- Open Access
- 2 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 272
Regulating Wait-Driven Requests in Queues
- 2 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 272
Open AccessRegulating Wait-Driven Requests in Queues
- Top Cited Papers
- 1 June 2025
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Management Science
- Vol. 71  (6) , 4877-4894
Good Prophets Know When the End Is Near
We consider a class of online decision-making problems with exchangeable actions, where in each period a controller is presented an input type drawn from some stochastic arrival process. The controller must choose an action, and the final objective depends only on the aggregate type-action counts. Such a framework encapsulates many online stochastic variants of common optimization problems with knapsack, bin packing, and generalized assignment as canonical examples. In such settings, we study a natural model-predictive control algorithm. We introduce general conditions under which this algorithm obtains uniform additive loss (independent of the horizon) compared with an optimal solution with full knowledge of arrivals. Our condition builds on the recently introduced compensated coupling technique, providing a unified view of how uniform additive loss arises as a consequence of the geometry of the underlying decision-making problem. Our characterization allows us to derive uniform loss algorithms for several new settings, including the first such algorithm for online stochastic bin packing. It also lets us study the effect of other modeling assumptions, including choice of horizon, batched decisions, and limited computation. In particular, we show that our condition is fulfilled by the above-mentioned problems when the end of the time horizon is known sufficiently long before the end. In contrast, if at a late stage, there is still uncertainty about the end of the time horizon we show that such uniform loss guarantees are impossible to achieve. We use real and synthetic data to illustrate our findings. This paper was accepted by J. George Shanthikumar, data science. Funding: This work was supported by the Division of Mathematical Sciences [Grant 1839346]; the Division of Electrical, Communications and Cyber Systems [Grant 1847393]; and the Army Research Laboratory [Grant W911NF-17-1-0094]. The authors also gratefully acknowledge support from the NSF [Grants ECCS-1847393, CNS-195599, and DMS-1839346], AFOSR [Grant FA9550-23-1-0068], an ARL award [Grant W911NF-17-1-0094], and ARO MURI [Grant W911NF-19-1-0217]. Supplemental Material: The online appendix and data files are available at https://doi.org/10.1287/mnsc.2023.04307 .
- 1 June 2025
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Management Science
- Vol. 71  (6) , 4877-4894
Top Cited PapersGood Prophets Know When the End Is Near
We consider a class of online decision-making problems with exchangeable actions, where in each period a controller is presented an input type drawn from some stochastic arrival process. The controller must choose an action, and the final objective depends only on the aggregate type-action counts. Such a framework encapsulates many online stochastic variants of common optimization problems with knapsack, bin packing, and generalized assignment as canonical examples. In such settings, we study a natural model-predictive control algorithm. We introduce general conditions under which this algorithm obtains uniform additive loss (independent of the horizon) compared with an optimal solution with full knowledge of arrivals. Our condition builds on the recently introduced compensated coupling technique, providing a unified view of how uniform additive loss arises as a consequence of the geometry of the underlying decision-making problem. Our characterization allows us to derive uniform loss algorithms for several new settings, including the first such algorithm for online stochastic bin packing. It also lets us study the effect of other modeling assumptions, including choice of horizon, batched decisions, and limited computation. In particular, we show that our condition is fulfilled by the above-mentioned problems when the end of the time horizon is known sufficiently long before the end. In contrast, if at a late stage, there is still uncertainty about the end of the time horizon we show that such uniform loss guarantees are impossible to achieve. We use real and synthetic data to illustrate our findings. This paper was accepted by J. George Shanthikumar, data science. Funding: This work was supported by the Division of Mathematical Sciences [Grant 1839346]; the Division of Electrical, Communications and Cyber Systems [Grant 1847393]; and the Army Research Laboratory [Grant W911NF-17-1-0094]. The authors also gratefully acknowledge support from the NSF [Grants ECCS-1847393, CNS-195599, and DMS-1839346], AFOSR [Grant FA9550-23-1-0068], an ARL award [Grant W911NF-17-1-0094], and ARO MURI [Grant W911NF-19-1-0217]. Supplemental Material: The online appendix and data files are available at https://doi.org/10.1287/mnsc.2023.04307 .
- Open Access
- 8 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 2
On the Supply of Autonomous Vehicles in Platforms
The likely large-scale deployment of autonomous vehicle (AV) technology in the near future has the potential to fundamentally change the transportation landscape. Due to the high cost of AV hardware, the most likely path to widespread AV use is via platforms that can sustain high utilization, such as ride-hailing and delivery services. In this paper, we consider four potential operational models to commercialize AVs, which we model as a supply chain game between a platform, an AV supplier, and human drivers that join as individual contractors (ICs). Our operational models include (1) an open platform that outsources the high capital burden of AVs by allowing the AV supplier and human drivers to bring their own vehicles into the system, (2) an AV-only platform that is operated independently by the AV supplier, (3) a platform that sources AVs from the supplier through leasing contracts, and (4) an integrated supply chain in which the same entity operates the platform and supplies the AVs. We use (4) as a benchmark to measure the performances of the other models. We find that apart from operational model (2), all deployment models are subject to a risk of AV underutilization due to the need to maintain the ICs' utilization sufficiently high to ensure ICs remain engaged. In the non-integrated models, this risk can propagate backwards in the supply chain and thereby negatively affect its efficiency. In particular, as a result of AV underutilization, the supply chain profit of an open platform model can be arbitrarily smaller than the integrated benchmark. AV underutilization also arises in the presence of leasing contracts and leads to significant supply chain misalignment. The results demonstrate that the platform's optimal dispatch decision, via AV underutilization, may lead to market failures. In light of these market failures we explore potential contracting solutions through usage commitments. We find that when the platform can contractually commit to an AV utilization level under each demand realization in each scenario, the supply chain can be fully aligned. Moreover, even when demand is not fully contractible, well-designed dispatch commitments can still significantly increase the open platform efficiency. As a proof of concept, we show a guarantee of the following flavor for a simple prioritization contract: either the supply chain profit under the contract is at least half of that of an integrated supply chain or the supply chain can achieve half the profit of an integrated supply chain even without a contract. Despite the inability to fully align the supply chain, this contract demonstrates the value of supply chain contracts when compared to the potentially unbounded efficiency loss in the absence of a contract. In particular, with usage commitments, an open platform exhibits stronger theoretical guarantees and superior numerical performances compared to the other operational models considered in the paper, such as AV leasing or AV-only platforms.
- 8 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 2
Open AccessOn the Supply of Autonomous Vehicles in Platforms
The likely large-scale deployment of autonomous vehicle (AV) technology in the near future has the potential to fundamentally change the transportation landscape. Due to the high cost of AV hardware, the most likely path to widespread AV use is via platforms that can sustain high utilization, such as ride-hailing and delivery services. In this paper, we consider four potential operational models to commercialize AVs, which we model as a supply chain game between a platform, an AV supplier, and human drivers that join as individual contractors (ICs). Our operational models include (1) an open platform that outsources the high capital burden of AVs by allowing the AV supplier and human drivers to bring their own vehicles into the system, (2) an AV-only platform that is operated independently by the AV supplier, (3) a platform that sources AVs from the supplier through leasing contracts, and (4) an integrated supply chain in which the same entity operates the platform and supplies the AVs. We use (4) as a benchmark to measure the performances of the other models. We find that apart from operational model (2), all deployment models are subject to a risk of AV underutilization due to the need to maintain the ICs' utilization sufficiently high to ensure ICs remain engaged. In the non-integrated models, this risk can propagate backwards in the supply chain and thereby negatively affect its efficiency. In particular, as a result of AV underutilization, the supply chain profit of an open platform model can be arbitrarily smaller than the integrated benchmark. AV underutilization also arises in the presence of leasing contracts and leads to significant supply chain misalignment. The results demonstrate that the platform's optimal dispatch decision, via AV underutilization, may lead to market failures. In light of these market failures we explore potential contracting solutions through usage commitments. We find that when the platform can contractually commit to an AV utilization level under each demand realization in each scenario, the supply chain can be fully aligned. Moreover, even when demand is not fully contractible, well-designed dispatch commitments can still significantly increase the open platform efficiency. As a proof of concept, we show a guarantee of the following flavor for a simple prioritization contract: either the supply chain profit under the contract is at least half of that of an integrated supply chain or the supply chain can achieve half the profit of an integrated supply chain even without a contract. Despite the inability to fully align the supply chain, this contract demonstrates the value of supply chain contracts when compared to the potentially unbounded efficiency loss in the absence of a contract. In particular, with usage commitments, an open platform exhibits stronger theoretical guarantees and superior numerical performances compared to the other operational models considered in the paper, such as AV leasing or AV-only platforms.
- Open Access
- 8 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 346
The Dedicated Docket in U.S. Immigration Courts: An analysis of fairness and efficiency properties
The dedicated docket was introduced by the Biden Administration to expedite the processing of asylum claims. It creates a separate queue for immigration proceedings where judges are supposed to issue a decision for each asylum case within a target timeframe. The administration announced the docket with the goals of speed, accuracy, and fairness. Though the program meets its first goal, legal advocacy groups report that this comes at the expense of the last. Referring to it as a "Denial of justice", they find that cases on the dedicated docket routinely fail to access legal representation, and have a much lower asylum grant rate. We aim to understand the operational implication of the dedicated docket. In our stylized queueing model, a policy maker (PM) routes asylees to either the regular or the dedicated docket, and sets a delay target for the dedicated one. Constrained by the target, the court allocates its limited capacity to minimize the average delay. Immigration lawyers schedule their time between dockets to maximize the rate of successful asylum cases. Compared to a single-docket benchmark, we show that the dedicated-docket system can Pareto-improve both the speed at which cases are adjudicated and the rate of accurately decided asylum cases. Our proof is constructive: for a given sufficiently large queue length we design PM decisions (routing choices and delay target) that yield the same queue length and a higher accuracy than a single docket benchmark. The PM assigns asylees to each docket so as to ensure that (i) there are more cases on the dedicated docket than the regular one, (ii) the dedicated docket is faster than the regular one, and (iii) the workload from the regular docket is just sufficient to overload the lawyers' capacity. Our characterization of the lawyers' best response implies, under these conditions, that lawyers spend all their effort on regular docket cases and none on cases from the dedicated docket. We highlight that the resulting improvement relies on a careful operational analysis. A misspecification of the two-docket system can lead to worse performance than the single docket's. Moreover, we prove that a Pareto-improvement necessarily disadvantages cases on one of the two dockets. We propose two definitions to formalize fairness between dockets: fairness in effort and fairness in outcome. Fairness in effort requires that it is incentive compatible for lawyers to allocate their effort (time) in a way that asylees on either docket receive equal effort from lawyers on average; fairness in outcome requires that it is incentive compatible for lawyers to allocate effort such that asylees on either docket have the same probability of an asylee's application getting completely prepared. Our result shows that any two-docket system, that satisfies either notion of fairness between dockets, must be Pareto-dominated, with respect to accuracy and queue-length, by a corresponding single-docket system. Our result thus reveals that unfairness between dockets is a fundamental requirement of an efficient two-docket system. A full version of this paper can be found at https://papers.ssrn.com/sol3/papers.cfm?abstract_id=4785713.
- 8 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 346
Open AccessThe Dedicated Docket in U.S. Immigration Courts: An analysis of fairness and efficiency properties
The dedicated docket was introduced by the Biden Administration to expedite the processing of asylum claims. It creates a separate queue for immigration proceedings where judges are supposed to issue a decision for each asylum case within a target timeframe. The administration announced the docket with the goals of speed, accuracy, and fairness. Though the program meets its first goal, legal advocacy groups report that this comes at the expense of the last. Referring to it as a "Denial of justice", they find that cases on the dedicated docket routinely fail to access legal representation, and have a much lower asylum grant rate. We aim to understand the operational implication of the dedicated docket. In our stylized queueing model, a policy maker (PM) routes asylees to either the regular or the dedicated docket, and sets a delay target for the dedicated one. Constrained by the target, the court allocates its limited capacity to minimize the average delay. Immigration lawyers schedule their time between dockets to maximize the rate of successful asylum cases. Compared to a single-docket benchmark, we show that the dedicated-docket system can Pareto-improve both the speed at which cases are adjudicated and the rate of accurately decided asylum cases. Our proof is constructive: for a given sufficiently large queue length we design PM decisions (routing choices and delay target) that yield the same queue length and a higher accuracy than a single docket benchmark. The PM assigns asylees to each docket so as to ensure that (i) there are more cases on the dedicated docket than the regular one, (ii) the dedicated docket is faster than the regular one, and (iii) the workload from the regular docket is just sufficient to overload the lawyers' capacity. Our characterization of the lawyers' best response implies, under these conditions, that lawyers spend all their effort on regular docket cases and none on cases from the dedicated docket. We highlight that the resulting improvement relies on a careful operational analysis. A misspecification of the two-docket system can lead to worse performance than the single docket's. Moreover, we prove that a Pareto-improvement necessarily disadvantages cases on one of the two dockets. We propose two definitions to formalize fairness between dockets: fairness in effort and fairness in outcome. Fairness in effort requires that it is incentive compatible for lawyers to allocate their effort (time) in a way that asylees on either docket receive equal effort from lawyers on average; fairness in outcome requires that it is incentive compatible for lawyers to allocate effort such that asylees on either docket have the same probability of an asylee's application getting completely prepared. Our result shows that any two-docket system, that satisfies either notion of fairness between dockets, must be Pareto-dominated, with respect to accuracy and queue-length, by a corresponding single-docket system. Our result thus reveals that unfairness between dockets is a fundamental requirement of an efficient two-docket system. A full version of this paper can be found at https://papers.ssrn.com/sol3/papers.cfm?abstract_id=4785713.
- 1 May 2024
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 72  (3) , 1049-1070
Efficient Decentralized Multi-agent Learning in Asymmetric Bipartite Queueing Systems
New Algorithm Enables Efficient Decentralized Learning in Bipartite Queueing Systems Bipartite queueing systems, where agents with individual job queues request service from a pool of heterogeneous servers, are standard models for service applications like data networks and call centers. Traditionally, a central controller schedules agent requests with full knowledge of system parameters. However, emerging applications require decentralized operation without this central coordination or complete system information. This presents challenges as agents lack the global knowledge needed to efficiently route jobs. Recent research into efficient decentralized learning algorithms for such systems faces limitations in nonoptimal throughput, demanding computations, or degrading efficiency with exponential queue growth. In contrast, this paper introduces an algorithm that enables queues to efficiently learn decentralized scheduling policies while ensuring throughput optimality. The approach is computationally lightweight, achieving queue length bounds that scale polynomially rather than exponentially in system size. Experiments demonstrate faster convergence and robustness of our algorithm compared with prior decentralized algorithms.
- 1 May 2024
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 72  (3) , 1049-1070
Efficient Decentralized Multi-agent Learning in Asymmetric Bipartite Queueing Systems
New Algorithm Enables Efficient Decentralized Learning in Bipartite Queueing Systems Bipartite queueing systems, where agents with individual job queues request service from a pool of heterogeneous servers, are standard models for service applications like data networks and call centers. Traditionally, a central controller schedules agent requests with full knowledge of system parameters. However, emerging applications require decentralized operation without this central coordination or complete system information. This presents challenges as agents lack the global knowledge needed to efficiently route jobs. Recent research into efficient decentralized learning algorithms for such systems faces limitations in nonoptimal throughput, demanding computations, or degrading efficiency with exponential queue growth. In contrast, this paper introduces an algorithm that enables queues to efficiently learn decentralized scheduling policies while ensuring throughput optimality. The approach is computationally lightweight, achieving queue length bounds that scale polynomially rather than exponentially in system size. Experiments demonstrate faster convergence and robustness of our algorithm compared with prior decentralized algorithms.
- Open Access
Efficient decentralized multi-agent learning in asymmetric bipartite queueing systems
We study decentralized multi-agent learning in bipartite queueing systems, a standard model for service systems. In particular, N agents request service from K servers in a fully decentralized way, i.e, by running the same algorithm without communication. Previous decentralized algorithms are restricted to symmetric systems, have performance that is degrading exponentially in the number of servers, require communication through shared randomness and unique agent identities, and are computationally demanding. In contrast, we provide a simple learning algorithm that, when run decentrally by each agent, leads the queueing system to have efficient performance in general asymmetric bipartite queueing systems while also having additional robustness properties. Along the way, we provide the first provably efficient UCB-based algorithm for the centralized case of the problem.
Open AccessEfficient decentralized multi-agent learning in asymmetric bipartite queueing systems
We study decentralized multi-agent learning in bipartite queueing systems, a standard model for service systems. In particular, N agents request service from K servers in a fully decentralized way, i.e, by running the same algorithm without communication. Previous decentralized algorithms are restricted to symmetric systems, have performance that is degrading exponentially in the number of servers, require communication through shared randomness and unique agent identities, and are computationally demanding. In contrast, we provide a simple learning algorithm that, when run decentrally by each agent, leads the queueing system to have efficient performance in general asymmetric bipartite queueing systems while also having additional robustness properties. Along the way, we provide the first provably efficient UCB-based algorithm for the centralized case of the problem.
- 1 August 2023
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 48  (3) , 1344-1363
Overbooking with Bounded Loss
We study a classic problem in revenue management: quantity-based, single-resource revenue management with no-shows. In this problem, a firm observes a sequence of T customers requesting a service. Each arrival is drawn independently from a known distribution of k different types, and the firm needs to decide irrevocably whether to accept or reject requests in an online fashion. The firm has a capacity of resources B and wants to maximize its profit. Each accepted service request yields a type-dependent revenue and has a type-dependent probability of requiring a resource once all arrivals have occurred (or be a no-show). If the number of accepted arrivals that require a resource at the end of the horizon is greater than B, the firm needs to pay a fixed compensation for each service request that it cannot fulfill. With a clairvoyant that knows all arrivals ahead of time, as a benchmark, we provide an algorithm with a uniform additive loss bound, that is, its expected loss is independent of T. This improves upon prior works achieving [ ] guarantees. Funding: The authors gratefully acknowledge generous support by the Sloan School of Management at MIT. Supplemental Material: The online appendix is available at https://doi.org/10.1287/moor.2022.1293 .
- 1 August 2023
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 48  (3) , 1344-1363
Overbooking with Bounded Loss
We study a classic problem in revenue management: quantity-based, single-resource revenue management with no-shows. In this problem, a firm observes a sequence of T customers requesting a service. Each arrival is drawn independently from a known distribution of k different types, and the firm needs to decide irrevocably whether to accept or reject requests in an online fashion. The firm has a capacity of resources B and wants to maximize its profit. Each accepted service request yields a type-dependent revenue and has a type-dependent probability of requiring a resource once all arrivals have occurred (or be a no-show). If the number of accepted arrivals that require a resource at the end of the horizon is greater than B, the firm needs to pay a fixed compensation for each service request that it cannot fulfill. With a clairvoyant that knows all arrivals ahead of time, as a benchmark, we provide an algorithm with a uniform additive loss bound, that is, its expected loss is independent of T. This improves upon prior works achieving [ ] guarantees. Funding: The authors gratefully acknowledge generous support by the Sloan School of Management at MIT. Supplemental Material: The online appendix is available at https://doi.org/10.1287/moor.2022.1293 .