A Framework for Stochastic Fairness in Dominant Resource Allocation with Cloud Computing Applications
Jiaqi Lei, Akhil Singla, Sanjay Mehrotra · 2025
Read A Framework for Stochastic Fairness in Dominant Resource Allocation with Cloud Computing Applications by Jiaqi Lei, Akhil Singla, Sanjay Mehrotra (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-18051.txt.
Introduction
Jiaqi Lei, Akhil Singla, and Sanjay Mehrotra share limited resources fairly when needs are uncertain. Their paper appeared in two thousand twenty-five. Cloud computing is their test case, but health systems and relief logistics face the same problem. Each user needs several resources at once. The dominant share idea judges fairness by the largest claim. Uncertainty about future needs complicates every split.
Their framework builds fairness that holds across random demand. It uses only rough estimates of each need's mean and spread. Key properties survive: no waste, no envy, and an incentive to share. A sampled version of the model provably nears the full one. A finitely convergent algorithm solves it. Tests weigh how the moment-based version performs in practice.
Catalog record
| CREATOR | Jiaqi Lei, Akhil Singla, Sanjay Mehrotra |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 106 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-18051
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Framework for Stochastic Fairness in Dominant Resource Allocation with Cloud Computing Applications Jiaqi Lei, Akhil Singla, Sanjay Mehrotra Abstract Allocation of limited resources under uncertain requirements often necessitates fairness considerations in computer systems. This paper introduces a distributionally robust (DR) stochastic fairness framework for multi-resource allocation, leveraging rough estimates of the mean and variance of resource requirement distributions. The framework employs a sampled approximation DR (SA-DR) model to develop the concept of stochastic fairness, satisfying key properties such as stochastic Pareto efficiency, stochastic sharing incentive, and stochastic envy-freeness under suitable conditions. We show the convergence of the SA-DR model to the DR model and propose a finitely convergent algorithm to solve the SA-DR model. We empirically evaluate the performance of our moment-based SA-DR model, which uses only rough estimates of the mean and variance of the resource requirement distribution, against alternative resource allocation models under varying levels of information availability. We demonstrate that our mean- and variance-based SA-DR model can achieve performance similar to the model with full information on the resource requirement distribution. Convergence of the sampled approximation model and comparisons across models are illustrated using data from cloud computing applications. 1 Introduction Fairness is often a critical consideration when allocating a limited set of resources in computer systems [ 1 , 2 , 3 , 4 ] . A central challenge arises when users’ resource requirements are unknown at decision time and only coarsely specified [ 5 , 6 ] . In cloud computing, the decision maker provides users with access to shared environments featuring virtual machines and resources such as memory, CPUs, and bandwidth [ 1 ] . The objective in such systems is to allocate resources efficiently to minimize job completion delays while maintaining fairness. However, users’ resource requirements are often uncertain at the time of job submission. For instance, a computational algorithm may have unknown memory, CPU, and bandwidth requirements at the time of job submission, and users can typically only provide rough estimates of their required resources [ 7 , 8 ] . This paper introduces the concept of stochastic fairness in resource allocation for such contexts, explores its properties, and proposes an algorithm to solve the associated stochastic fairness model. We derive insights into resource allocation decisions by comparing different models that vary in the level of information available about resource requirement uncertainty. Several concepts of fairness have been proposed for allocating a deterministic amount of resources. These include Nash Product Fairness [ 9 ] , Asset Fairness [ 10 ] , Bottleneck Fairness [ 11 ] , MaxMin Fairness [ 12 ] , Proportional Fairness [ 13 ] , (\alpha,p) -Fairness [ 14 ] , and Dominant Resource Fairness (DRF) [ 15 ] and its extension [ 6 ] . Nash Product Fairness [ 9 ] is also called Competitive Equilibrium from Equal Income (CEEI), and it is obtained by maximizing the geometric mean \prod_{i}x_{i} , where x_{i} is the resource allocated to user i . Asset Fairness aims at equalizing the resources allocated to each user [ 10 ] . Bottleneck fairness provides a resource allocation in which every user either gets all the required resources or at least a bottleneck resource [ 11 ] . MaxMin Fairness provides an allocation x , where no individual allocation x_{i} can be increased without increasing some x_{j} that is less than or equal to x_{i} [ 12 ] . An allocation x^{*} is called proportionally fair if \sum_{i}\frac{x_{i}-x_{i}^{*}}{x^{*}_{i}}\leq 0 for any other feasible x [ 13 ] . A feasible allocation x^{*} is ( \alpha,p )-fair if \sum_{i}p_{i}\frac{x_{i}-x_{i}^{*}}{\left(x_{i}^{*}\right)^{\alpha}}\leq 0 , where p=\{p_{1},p_{2},...,p_{N}\} and \alpha are positive [ 14 ] . DRF is a generalization of MaxMin-fairness to multiple resource types. The resource allocated to a user is determined by the dominant share, defined as the maximum share of any resource allocated to a user [ 15 ] . Based on DRF, [ 6 ] develops unified fairness-efficiency tradeoff functions called Fairness on Dominant Shares (FDS) and Generalized Fairness on Jobs (GFJ). The literature on cloud computing with fairness in multi-resource allocation has progressed from pricing-oriented (\alpha,p) -fair models [ 17 ] to DRF-based mechanisms tailored for practical constraints-strategy-proofness [ 18 ] , dynamic arrivals [ 19 ] , and heterogeneous servers [ 20 ] . In addition, [ 21 ] introduces fairness-utilization tradeoffs and [ 22 , 23 ] adapt bottleneck fairness and per-server dominant-share fairness to manage multi-resource bottlenecks at scale. Stochastic multi-resource allocation problems assume resource requirements are random. [ 24 ] models the stochastic allocation problem in a network as a stochastic multi-dimensional knapsack problem. [ 25 ] considers a resource allocation model for project scheduling with a chance constraint decision framework. [ 26 ] proposes a stochastic allocation mechanism for cloud computing, providing users with a selection of stochastic allocation classes to bridge the gap between reserved resources and dynamic demands in the form of shares. However, unlike our paper, the above studies only consider maximizing the profit of admitted tasks or users without considering fairness. [ 8 ] addresses the robust multi-resource allocation problem in a cloud computing context; however, their analysis is limited to worst-case scenarios, focusing on scenario demand uncertainty, box demand uncertainty, and ellipsoidal demand uncertainty. [ 27 ] proposes a resource allocation algorithm that models the long-term max-min fairness problem for users with deterministic task requirements while assuming full information on the distribution of task arrival times. In contrast, our study derives stochastic fairness properties within a distributionally robust framework for uncertain resource requirements. We further investigate the impact of key model parameters on resource allocation decisions, considering different levels of information about the resource requirement distribution. 1.1 Contributions Our paper focuses on the stochastic multi-resource allocation problem with the objective of maximizing fairness and efficiency when users’ requirements are random and only partially known. We generalize the fairness–efficiency framework from the Fairness on Dominant Shares (FDS) model of [ 6 ] to a distributionally robust (DR) setting where only bounds on the means and variances of resource requirements are available. We incorporate chance constraints to control capacity violations at a prescribed confidence level. We propose a sampled approximation of the DR model (SA-DR) as our stochastic fairness model, tailored to the moment-based ambiguity set based on the available partial information. We establish conditions under which the optimal allocations from the SA-DR model satisfy stochastic Pareto-efficiency , stochastic sharing incentive , and stochastic envy-freeness . We further show that SA-DR converges to the DR model under suitable assumptions and provide a cutting-surface algorithm with finite termination that yields an \epsilon -optimal solution. To generate insights on resource allocation, stochastic fairness and efficiency, we consider different models that either ignore randomness in resource requirements (i.e., deterministic expected-value models) or require full information on the probability distribution of the required resources while varying different model parameters. When full information on the resource requirement distribution is available, we show that a resource requirement distribution—such as a triangular distribution with lower variance compared to a uniform demand distribution—yields better fairness and efficiency in resource allocations. When only mean and variance, i.e., partial information about the resource requirements, is available, we employ the SA-DR model to obtain resource