FAST: A Fairness Assured Service Recommendation Strategy Considering Service Capacity Constraint

Yao Wu, Jian Cao, Guandong Xu

Introduction

In real-world service industries such as dining, healthcare, and beauty, recommendation systems face a hard constraint often ignored in digital-only domains: physical capacity. Recommending a popular restaurant to thousands of users simultaneously leads to overcrowding, service degradation, or user rejection. However, simply limiting traffic to popular services to manage load can lead to systemic unfairness. If two users share identical preferences, but one is consistently denied their top choice due to capacity limits, the system is biased. This paper introduces FAST, a strategy designed to balance capacity constraints, recommendation quality, and individual fairness over time.

The Challenge of Capacity and Fairness

Previous solutions to capacity-constrained recommendations often penalized popular services to reduce traffic or ignored the issue entirely. The authors argue that these approaches fail to address the three-way trade-off necessary for a sustainable service ecosystem:

  1. Capacity Constraints: Ensuring services are never recommended to more users than they can handle.
  2. Recommendation Quality: Maintaining high utility so users receive items they actually desire.
  3. Individual Fairness: Ensuring that, over multiple rounds, no single user is consistently deprived of their top choices more than others.

The FAST Strategy

The authors propose a new metric called Top-N Fairness. This metric recognizes that users primarily care about the top items in a recommendation list. It measures the "fairness degree" by comparing how often a service appears in a specific user's top-N list versus its appearance for the general population.

Based on this metric, the FAST (Fairness Assured service recommendation STrategy) was developed in two variants:

  • F-FAST (Fixed User Set): Designed for stable environments like subscription services. It uses a greedy heuristic to sort users by their current fairness score in each round. The most "unfairly treated" users (those who have missed out on top choices in the past) get priority for their preferred services until capacity is reached.
  • D-FAST (Dynamic User Set): Designed for scenarios where users join or leave the system. It includes a baseline adjustment step to ensure new users can quickly reach a fair state without being penalized by the system's historical data.

Crucially, the authors provide a theoretical proof that under the FAST strategy, the variance of fairness among users converges to zero over time, eventually reaching a state of "Individual Level Fair Status."

Experimental Evaluation

The researchers evaluated FAST using the Yelp Dataset (focusing on Phoenix and Toronto) and Synthetic Datasets designed to simulate different levels of "capacity conflict," ranging from high-demand scenarios to those where demand is lower than capacity.

Key Results

  • Superior Fairness: In Yelp dataset experiments, F-FAST reached a stable, fair state significantly faster than random selection strategies.
  • Efficiency and Quality: Compared to an Integer Linear Programming (ILP) baseline—which maximizes quality but ignores fairness—F-FAST only lost approximately 7% in recommendation quality while providing much higher fairness.
  • Performance vs. Random: F-FAST provided 20% higher recommendation quality than a "Random Strategy" that also attempts to maintain fairness.
  • Dynamic Resilience: D-FAST successfully integrated new users, bringing them to a "fair" state within approximately 30 rounds of recommendations.

Insights and Future Work

A core insight of this research is that perfect fairness is impossible in a single round due to hard capacity limits; fairness must be viewed as a long-term, multi-round accumulation. By focusing on the Top-N items, the system minimizes the "price of fairness"—the small drop in quality required to ensure all users are treated equitably over time.

While FAST focuses on individual fairness (treating similar individuals similarly), the authors suggest that future research should extend these strategies to group fairness. This would ensure that protected attributes, such as gender or race, do not result in systemic recommendation biases under capacity constraints. Additionally, further optimization may be required to scale the $O(n^2 \log n)$ heuristic for systems with millions of concurrent users.

Summary updated

BibTeX
@inproceedings{wu2020fast,
  author = {Yao Wu and Jian Cao and Guandong Xu},
  title = {{FAST: A Fairness Assured Service Recommendation Strategy Considering Service Capacity Constraint}},
  booktitle = {ICSOC},
  year = {2020},
  doi = {10.1007/978-3-030-65310-1\_21},
}
Figure