There is growing awareness and concern about fairness in machine learning and algorithm design. This is particularly true in online selection problems where decisions are often biased. This paper tackles the challenge of fairness and bias in sequential decision-making by introducing "multi-color" variants of the classic secretary and prophet problems. The authors design optimal, fair online algorithms that guarantee candidates from different demographic groups are selected at target rates without sacrificing too much efficiency.
The Problem: Bias in Sequential Decisions
Machine learning algorithms are increasingly used to make sequential decisions, such as hiring staff, approving loans, or allocating organs for transplant. These scenarios are classic examples of "online selection" problems, where candidates arrive one by one, and a decision-maker must irrevocably decide whether to select the current candidate or wait for a potentially better one.
However, standard algorithms for these problems (like the classic $1/e$ secretary algorithm) ignore social norms like fairness and can be highly biased. For instance, candidates from different demographic groups might be incomparable due to systemic biases, or a decision-maker might be legally required to select from different groups at specific target rates. The authors address this gap by formalizing two new problems:
- The Multi-Color Secretary Problem: Candidates belong to different groups (colors) and arrive in a random order. You can rank candidates within the same group, but you cannot compare them across groups.
- The Multi-Color Prophet Problem: Candidates have observable values drawn from known distributions. The goal is to maximize the expected value of the chosen candidate while ensuring the probability of selecting from each group matches a predefined target distribution.
Fair and Optimal Methods
The authors develop novel algorithms tailored to these multi-color settings:
- Group-Specific Thresholds (Secretary): Instead of using a single global time threshold (like skipping the first 37% of candidates), the proposed algorithm uses a specific time threshold $t_j$ for each group $j$. If a candidate from group $j$ arrives after $t_j$ and is the best seen in their group so far, they are selected. The authors mathematically derive the optimal thresholds to maximize the chance of picking the best overall candidate.
- Marginal Probability Scaling (Prophet): For the prophet problem, the authors design algorithms that mimic the optimal offline fair algorithm (which can see all candidates at once). For general distributions, they calculate the probability $q_i$ that the offline optimal algorithm would pick candidate $i$, and set online thresholds to accept that candidate with probability $q_i/2$. For independent and identically distributed (IID) candidates, they scale this acceptance probability to $2/(3n)$.
Datasets and Empirical Results
The authors evaluate their algorithms on synthetic datasets (testing theoretical bounds) and two real-world datasets:
- Feedback Maximization: A telemarketing dataset where the goal is to select a client for feedback, grouped into 5 colors by age, ensuring age-diverse feedback.
- Influence Maximization: A social network dataset where the goal is to select an influencer, grouped into 5 colors by Body Mass Index (BMI) to ensure fair representation.
The empirical results highlight that classic optimal algorithms are wildly unfair, often picking almost exclusively from the very end of a stream or entirely ignoring certain groups. Standard unfair baselines heavily skewed their selections, picking up to 80% of candidates from a single group.
Conversely, on the real-world Feedback and Influence datasets, the proposed fair secretary algorithm picked the maximum element of a color ~76% more often than a naive fair baseline (which just randomly picks a color first, then runs the standard secretary algorithm).
Key Insights
- Fairness as a byproduct of optimality: In the multi-color secretary problem, the optimal online algorithm naturally approaches perfect fairness exponentially fast as group sizes increase. You don't have to artificially force the algorithm to be fair; simply optimizing for the best candidate under the constraint of cross-group incomparability inherently leads to fair outcomes.
- Incomparability elegantly models bias: The assumption in the secretary model that candidates cannot be compared across groups perfectly encapsulates real-world scenarios where different backgrounds, education types, or systemic biases make direct comparisons "apples-to-oranges."
- Tight Theoretical Bounds: The proposed algorithms achieve strong theoretical guarantees, including a competitive ratio of $k^{\frac{1}{k-1}}$ for $k$ groups with equal probabilities in the secretary problem, and tight approximations for the prophet problem.
Limitations and Future Work
The paper strictly focuses on single-item selection models. In many real-world scenarios (like hiring a team or admitting a class of students), decision-makers need to select multiple candidates. Extending this framework to combinatorial settings—such as bipartite matching for ride-sharing or organ donation, allocation problems with matroid structures, and general combinatorial auctions—remains a highly promising direction for future work.
Summary updated