Incremental Fairness in Two-Sided Market Platforms: On Updating Recommendations Fairly

Gourab K. Patro, Abhijnan Chakraborty, Niloy Ganguly, Krishna P. Gummadi

Abstract

In two-sided market platforms like Amazon or Uber, updating recommendation algorithms is essential for improving customer experience. However, immediate "flips" to new models often cause "update shock"—sudden, massive shifts in exposure that can jeopardize the livelihoods of producers (sellers, drivers, etc.). This paper proposes an incremental update framework that uses Integer Linear Programming (ILP) to transition between algorithms smoothly. By enforcing minimum utility thresholds for customers while minimizing exposure volatility for producers, the framework ensures a fair transition for all stakeholders.

Introduction: The Cost of "Moving Fast"

In the competitive landscape of online platforms, recommendation engines are frequently updated to incorporate new data or better features. While these updates aim to enhance customer satisfaction, they often ignore the impact on the supply side of the market. An overnight update can cause a producer's traffic to plummet instantly. Analysis of Amazon and Google Local data reveals that immediate updates can cause over 69% of items to experience more than a 100% change in exposure.

The challenge lies in balancing three competing interests:

  1. Producers require "Egocentric Fairness," meaning they need stable, predictable exposure to manage their businesses.
  2. Customers expect high-quality recommendations that reflect the latest algorithmic improvements.
  3. Platforms need to deploy updates efficiently without alienating their producer base.

The Incremental Update Framework

To address "update shock," the authors propose transitioning from an old model ($V^{old}$) to a new model ($V^{new}$) over $\eta$ discrete steps. This process is managed through an online optimization framework.

The incremental update framework timeline, showing the transition from an old model to a new model over discrete periods.

As shown in the timeline above, the system solves an Integer Linear Programming (ILP) problem for each customer login instance. The objective is to minimize the difference between the current exposure distribution and a target distribution, ensuring a smooth path toward the new model's steady state. A critical component is the Hard Constraint: every customer is guaranteed a minimum utility threshold ($\theta_i$) that gradually increases over the transition period.

To maintain computational efficiency, the framework employs a Prefiltering step, focusing the ILP solver on a subset of items that are both highly relevant to the user and effective at correcting current exposure imbalances.

Experimental Evaluation

The framework was tested using real-world datasets from Amazon Reviews (Grocery) and Google Local (NYC), simulating various update scenarios such as model switches, data refreshes, and feature additions.

Key Results: Smoothness and Efficiency

The researchers compared their ILP-based methods against standard baselines, including "Immediate Updates" and "Canary Deployments" (CanD).

Comparison of exposure change (EC) across steps for different update strategies. The proposed ILP methods (c-f) show smoother transitions compared to baselines (a-b).

As illustrated in the bar charts, the proposed ILP methods (such as ILP-EL and ILP-EG) distribute the exposure change more evenly across the transition steps. In contrast, the IRF (Immediate) baseline shows a massive spike at the first step, while Canary Deployments (CanD) fail to manage the exposure path effectively.

Key metrics confirmed these visual findings:

  • Smoothness: The ILP-EL (Estimated Linear) method achieved the best stability scores, providing the most predictable experience for producers.
  • Path Efficiency: The transition path length for the proposed methods was nearly optimal (~1.0), indicating that the system moves directly toward the new state without unnecessary fluctuations.
  • Customer Utility: By adjusting the $\theta_i$ constraint, platforms can control the speed at which customers receive the benefits of the new algorithm.

Conclusion and Future Directions

This research shifts the focus of algorithmic fairness from static snapshots to dynamic transitions. By treating algorithm updates as a phased negotiation between stakeholders, platforms can foster more sustainable ecosystems.

Future work may address limitations such as the "Closed Market Assumption" (accounting for producers joining or leaving during an update) and "Position Bias" (recognizing that higher ranks in a recommendation list carry significantly more value). Ultimately, this framework provides a robust toolkit for platforms to "move fast" without "breaking" the livelihoods of those who power them.

Summary updated

BibTeX
@inproceedings{patro2020incremental,
  author = {Gourab K. Patro and Abhijnan Chakraborty and Niloy Ganguly and Krishna P. Gummadi},
  title = {{Incremental Fairness in Two-Sided Market Platforms: On Updating Recommendations Fairly}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i01.5349},
}
Figure