Sequential Fair Resource Allocation under a Markov Decision Process Framework

Parisa Hassanzadeh, Eleonora Kreacic, Sihan Zeng, Yuchen Xiao, Sumitra Ganesh

Introduction

Resource allocation is a fundamental challenge in operations research and computer science, involving the distribution of a finite budget—such as cloud computing capacity, inventory, or humanitarian aid—among multiple competing agents. While the problem is well-understood in offline settings where all demands are known upfront, real-world scenarios are typically sequential. In these online environments, agents arrive over time, and their future needs are stochastic and uncertain.

This paper addresses the critical tension in sequential allocation: being too generous early on risks exhausting resources for later participants, while being too conservative leads to wasted resources. The authors propose a novel framework using a Markov Decision Process (MDP) and a "risk-aware" algorithm, SAFFE-D, to achieve near-optimal fairness and efficiency without the benefit of hindsight.

The Sequential Allocation Challenge

In an offline setting, fairness is often defined by maximizing the Nash Social Welfare (NSW), which is the geometric mean of the utilities assigned to agents. NSW is favored because it provides a robust compromise between total system efficiency and egalitarian fairness.

In a sequential context, however, the allocator must make irrevocable decisions at each time step $t$ based on current demands and probabilistic estimates of future needs. The authors identify a common failure mode in existing look-ahead heuristics: the "Over-Reservation Trap." When algorithms estimate future demand based solely on expected values, they often hoard resources for future agents who may not actually materialize or whose demands may be lower than predicted. This leads to poor resource utilization and suboptimal fairness.

The SAFFE and SAFFE-D Algorithms

To solve this, the authors formulate the problem as a finite-horizon MDP aimed at maximizing the expected logarithm of the Nash Social Welfare (log-NSW). They introduce two primary algorithms:

  1. SAFFE (Sequential Allocations with Fairness based on Future Estimates): This algorithm treats the sequential problem as a series of instantaneous offline problems. At each step, it uses a "water-filling" approach to allocate resources based on current demand and the expected values of future demands.
  2. SAFFE-D (SAFFE-Discounted): Recognizing that SAFFE often over-reserves due to uncertainty, SAFFE-D introduces a tunable discounting mechanism. It penalizes future demand estimates by their standard deviation. By accounting for the variance of future estimates, SAFFE-D allows the allocator to be more decisive in the present when future needs are highly uncertain, effectively preventing the hoarding of resources.

Theoretical analysis in the paper provides an upper bound on the sub-optimality gap for SAFFE-D, proving that its performance remains close to the "hindsight optimal" solution—the best possible allocation achievable if all future demands were known perfectly.

Experimental Evaluation

The researchers evaluated the proposed framework using both synthetic simulations and real-world data:

  • Synthetic Scenarios: Three distinct settings were tested to observe system behavior under symmetric conditions, non-symmetric arrival patterns (e.g., "early birds" vs. late arrivals), and non-symmetric demand sizes.
  • Real-World Application: The authors utilized a Kaggle dataset containing five years of store-item sales data across 10 different stores. In this model, each store acts as an agent requesting inventory from a central warehouse on a weekly basis.

Key Results and Insights

The experimental results demonstrate that SAFFE-D significantly outperforms standard heuristics and matches or exceeds the performance of complex Reinforcement Learning (RL) models.

  • Near-Optimal Efficiency: In synthetic tests, SAFFE-D achieved a utilization rate of nearly 99%, compared to approximately 95% for the standard SAFFE algorithm.
  • Fairness and Stability: SAFFE-D consistently minimized the maximum deviation from the hindsight optimal allocation ($\Delta A^{max}$), ensuring that no single agent was unfairly "starved" of resources.
  • Robustness to Estimation Errors: A significant finding is the algorithm's resilience to noise. Even when predicted mean demands were inaccurate by as much as 50%, the discounting mechanism allowed SAFFE-D to maintain high levels of fairness and utilization.
  • Real-World Performance: On the store sales dataset, SAFFE-D achieved 100% utilization and zero deviation from hindsight optimal fairness in daily arrival scenarios ($p=1$). Even in sparse arrival settings ($p=0.5$), it outperformed existing state-of-the-art baselines like Guarded-HOPE.

Conclusion

The SAFFE-D framework provides a computationally efficient and theoretically grounded approach to sequential resource allocation. By incorporating risk-aware discounting, it successfully navigates the trade-off between current needs and future uncertainty.

Future research directions include adapting the framework for strategic agents who might misreport demands to gain larger allocations, as well as extending the logic to infinite-horizon settings where the operational timeline is not fixed. Currently, the model serves as a powerful tool for suppliers managing inventory, cloud providers, and other entities facing stochastic, sequential demand.

Summary updated

BibTeX
@inproceedings{hassanzadeh2023sequential,
  author = {Parisa Hassanzadeh and Eleonora Kreacic and Sihan Zeng and Yuchen Xiao and Sumitra Ganesh},
  title = {{Sequential Fair Resource Allocation under a Markov Decision Process Framework}},
  booktitle = {ICAIF},
  year = {2023},
  doi = {10.1145/3604237.3626860},
}
Figure