Fair resource allocation for coupled decision systems improves balance
Fair Policy Optimization in Major-Minor Weakly Coupled Markov Decision Processes
Machine Learning
Summary
This paper tackles how to share resources fairly when different decision systems are connected but usually act on their own. The authors study a model with one major system and many smaller ones linked by resource limits, which makes simple total reward goals less suitable. They introduce fairness goals that treat all smaller systems equally and create methods to find the best policies under these goals. They also test their approach on practical problems like machine maintenance and taxi management, showing it works well and scales up efficiently.
What this means in practice
- •For transportation planners: Optimize pricing and vehicle movement in urban taxi fleets with fairness across service zones using resource-coupled decision models.
- •For industrial maintenance teams: Allocate maintenance resources fairly among machines in a factory where overall capacity limits connect individual machine servicing decisions.
Authors
Xiaohui Tu, Yossiri Adulyasak, Erick Delage
Abstract
We consider fair resource allocation in sequential decision-making environments modeled as major-minor weakly coupled Markov decision processes (M2WCMDP). In this framework, resource constraints couple the action spaces of a major sub-Markov decision process (sub-MDP) and a population of minor sub-MDPs that would otherwise operate independently. Instead of using the traditional utilitarian (total-sum) objective, we optimize a general class of monotone, concave, permutation-invariant, normalized fairness functions. With homogeneous minor sub-MDPs, we prove that the problem under symmetry reduces to optimizing the platform-plus-mean-participant utilitarian objective over the class of \textit{permutation-invariant} policies, which allows us to exploit efficient algorithms that optimize the utilitarian-based objective to solve this fairness-aware problem. For more general settings, we introduce a count-proportion-based deep reinforcement learning approach with a priority-based sampler that generates feasible count actions. The generality of our framework means that the proposed algorithms and theoretical guarantees transfer to any domain with a symmetric M2WCMDP structure. We consider two applications: the machine replacement problem and the joint control of pricing and taxi relocation problem on a New York City-calibrated dataset. We validate our theoretical findings with comprehensive experiments, confirming the effectiveness of our proposed method in achieving strong fairness-aware performance while remaining scalable.