Fair Optimal Stopping Policy for Matching with Mediator

Yang LiuUAI 2017 · OpenReview

Abstract

This paper addresses the challenge of algorithmic bias in sequential matching systems, such as ride-sharing or freelance platforms, where a mediator assigns tasks to agents from diverse groups. We formulate an optimal stopping policy that maximizes system rewards while adhering to individual fairness constraints, specifically maximum expected wait times and minimum guaranteed rewards. By leveraging Lagrange relaxation and primal-dual analysis, we derive a computationally efficient, threshold-based strategy that balances social optimality with group-level fairness.

Introduction

In delegated multi-agent sequential matching environments, a mediator (e.g., a platform like Uber or Upwork) must decide whether to match an incoming task to an available agent or wait for a potentially higher-reward assignment. Traditional solutions employ "optimal stopping rules" that maximize total reward using a universal threshold. However, this approach often neglects fairness. If certain demographic groups statistically yield lower immediate rewards, standard algorithms may systematically bypass them, leading to disparate impacts like increased wait times or reduced earnings for protected groups. This research embeds fairness constraints directly into the dynamic optimal stopping framework to mitigate such biases.

Methodology

The environment is modeled as a sequential decision-making process where agent availability and rewards follow independent and identically distributed (IID) processes.

Schematic of the sequential matching process with a Decision Maker (DM) and multiple agent groups.

The author introduces two primary fairness-constrained variations:

  • Delay Fair Matching: Ensures each group has a maximum expected wait time.
  • Reward Fair Matching: Guarantees each group a minimum average reward rate.

To solve these, the paper demonstrates that these constrained rate-of-return problems can be mapped to constrained optimization problems. Using Lagrange relaxation, the complex dynamic programming task is reduced to solving a system of closed-form equations. Depending on the "tightness" of the constraints, the optimal policy is found via a linear system or a standard convex optimization problem, both solvable in polynomial time.

Key Insights and Theoretical Framework

A significant finding is that the elegant "threshold" structure of optimal stopping is preserved even with complex fairness constraints. The optimal fair policy simply necessitates group-specific thresholds.

Furthermore, the research identifies an "impossibility region" defined by a geometric mean parameter ($\nu_U$), which marks the boundary where fairness constraints can no longer be simultaneously satisfied. When constraints are tight, the matching probability for a group becomes inversely proportional to its availability and delay constraint, aligning with the principle of proportional fairness seen in network resource allocation.

Results and Discussion

The theoretical analysis provides exact, closed-form characterizations of optimal stopping rules. Computationally, group-specific thresholds can be determined in $O(1)$ time after solving the initial optimization problem.

Numerical simulations using exponential reward distributions validated these findings. In a two-group scenario, an unconstrained model achieved a reward rate of 0.6006. Introducing and tightening delay constraints successfully enforced fairness while predictably reducing the total system reward (e.g., to 0.5299 under strict constraints), illustrating the quantifiable trade-off between fairness and social optimality.

Conclusion and Future Work

This work provides a robust mathematical foundation for fair sequential matching. However, it assumes stationary (IID) agent availability and reward statistics. Future research should address dynamic feedback loops, where algorithmic decisions today influence the future state distributions of agent groups, such as their long-term availability or performance metrics.

Summary updated

BibTeX
@inproceedings{liu2017fair,
  author = {Yang Liu},
  title = {{Fair Optimal Stopping Policy for Matching with Mediator}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2017},
  url = {https://openreview.net/forum?id=SJQ-LR5gPCl},
}
Figure