Online Multi-Class Selection with Group Fairness Guarantee
balance fairness and efficiencyfairness across classesfractional solutiongroup fairness guaranteesintegral algorithmlearning-augmented variantlossless rounding schememultiple classesonline multi-class selectionrandomized algorithmrelax-and-round frameworkresource reservation approachrounding stepset-aside mechanismuntrusted machine-learned predictions
We study the online multi-class selection problem with group fairness guarantees, where limited resources must be allocated to sequentially arriving agents. Our work addresses two key limitations in the existing literature. First, we introduce a novel lossless rounding scheme that ensures the integral algorithm achieves the same expected performance as any fractional solution. Second, we explicitly address the challenges introduced by agents who belong to multiple classes. To this end, we develop a randomized algorithm based on a relax-and-round framework. The algorithm first computes a fractional solution using a resource reservation approach