View PDF HTML (experimental)

Abstract:Online selection problems arise in applications such as crowdsourcing and recruitment, where decision makers may seek representation across multiple, potentially overlapping demographic or skill dimensions. We study diversity-fair online selection under adversarial arrivals. A recruiter must immediately and irrevocably decide whether to accept each candidate while selecting at most \(K\) candidates. Before arrivals begin, the recruiter observes aggregate marginal information: the total number of candidates contributing to each of the \(d\) diversity dimensions. When the candidate pool is large, this information may be estimated from demographic statistics of the applicant population. We evaluate the expected utilities across dimensions using the generalized mean \(M_p=(d^{-1}\sum_{k=1}^d U_k^p)^{1/p}, -\infty\le p\le 1,\) where \(U_k\) denotes the expected utility of dimension \(k\). We first study max-min fairness, corresponding to \(p=-\infty\). We prove that no online policy can achieve a competitive ratio better than \(O(1/\sqrt d)\) and develop a policy with a competitive ratio \(1/[4(2+\sqrt2)\sqrt d]\), establishing the optimal dependence on \(d\) up to a constant factor. Without exact marginal information, the optimal worst-case rate falls to \(\Theta(1/d)\), demonstrating the value of this information. We also extend the max-min analysis to nonbinary attributes and characterize the optimal dependence on their value range. Finally, we study generalized-mean objectives. For \(0\le p\le1\), we establish an optimal competitive ratio of \(\Theta(1/\log d)\). For each fixed finite negative mean \(p=-q\), where \(q>0\), our policy achieves \(d^{-q/(2q+1)}\) up to polylogarithmic factors, matching the exponent of the corresponding impossibility bound.

Submission history

From: Tongwen Wu [view email]
[v1] Mon, 14 Apr 2025 16:35:20 UTC (632 KB)
[v2] Tue, 15 Apr 2025 02:49:31 UTC (632 KB)
[v3] Sun, 30 Aug 2026 06:57:20 UTC (91 KB)