Balancing Fairness and High Match Rates in Reciprocal Recommender Systems: A Nash Social Welfare Approach

Yoji Tomita, Luoyi FuarXiv 2026 · DOI · arXiv

Abstract

Matching platforms, such as online dating services and job recommendations, have become increasingly prevalent. For the success of these platforms, it is crucial to design reciprocal recommender systems (RRSs) that not only increase the total number of matches but also avoid creating unfairness among users. In this paper, we investigate the fairness of RRSs on matching platforms. From the perspective of fair division, we define the users' opportunities to be recommended and establish the fairness concept of envy-freeness in the allocation of these opportunities. We first introduce the Social Welfare (SW) method, which approximately maximizes the number of matches, and show that it leads to significant unfairness in recommendation opportunities, illustrating the trade-off between fairness and match rates. To address this challenge, we propose the Nash Social Welfare (NSW) method, which alternately optimizes two NSW functions and achieves nearly envy-free recommendations. We further generalize the SW and NSW method to the $\alpha$-SW method, which balances the trade-off between fairness and high match rates. Additionally, we develop a computationally efficient approximation algorithm for the SW/NSW/$\alpha$-SW methods based on the Sinkhorn algorithm. Through extensive experiments on both synthetic datasets and two real-world datasets, we demonstrate the practical effectiveness of our approach.

Introduction

In Reciprocal Recommender Systems (RRSs), such as dating apps or professional networking sites, a successful outcome requires mutual interest from both parties. Traditional recommendation algorithms often focus on maximizing the total number of matches (Social Welfare). However, this objective frequently leads to a "rich-get-richer" phenomenon: highly popular users are recommended disproportionately often, while the majority of users receive few to no recommendations. This popularity bias results in user frustration and potential platform abandonment.

The authors address this by framing recommendation as a fair division problem. The "resource" to be divided is the opportunity to be recommended to others. By ensuring this resource is distributed fairly, platforms can maintain a more satisfied and engaged user base.

Methodology

The core of the proposed approach is the application of Nash Social Welfare (NSW) to the RRS context. While standard Social Welfare (SW) maximizes the sum of utilities, NSW maximizes the product of utilities. This shift ensures that no user is left with zero utility, effectively forcing the system to distribute recommendation opportunities more broadly.

The reciprocal matching model illustrating how recommendation matrices A and B determine matching probabilities between agents.

To formalize fairness, the authors introduce envy-freeness: a state where no user would prefer the recommendation opportunities allocated to another user over their own. They also propose a generalized $\alpha$-SW method, allowing platform operators to tune the balance between maximum matches ($\alpha=1$) and maximum fairness ($\alpha \to 0$).

Comparison of the proposed NSW approach against existing frameworks like WE-Rec and Lorenz efficiency.

To ensure scalability, the authors utilize the Sinkhorn algorithm. By treating recommendation lists as doubly stochastic matrices, they avoid the high computational costs of traditional Linear Programming, enabling the system to handle larger datasets with GPU acceleration.

Experimental Evaluation

The researchers evaluated the NSW and $\alpha$-SW methods against synthetic data and two real-world datasets: a Japanese online dating platform and a speed dating experiment dataset.

Key Findings:

  • Envy Reduction: In synthetic tests with high popularity bias, the NSW method achieved nearly zero envious pairs, whereas the standard SW method created thousands.
  • Efficiency-Fairness Trade-off: On the Japanese dating dataset, the NSW method reduced the number of envious male users from 434 to just 31. This massive gain in equity came at a relatively small cost: an 18% reduction in total expected matches.
  • Distributional Equity: The NSW method consistently yielded the lowest Gini index across all datasets, indicating a much more even distribution of matches compared to naive or product-based baselines.

Conclusion and Future Work

This research demonstrates that Nash Social Welfare provides a robust framework for balancing efficiency and fairness in reciprocal markets. By treating recommendation slots as a finite resource to be divided fairly, platforms can mitigate popularity bias without significantly compromising match rates.

Future work includes addressing the cold start problem for new users, adapting the model for dynamic preferences that evolve over time, and conducting online A/B testing to measure the long-term impact of fair recommendations on user retention and platform health.

Summary updated

Abstract

Matching platforms, such as online dating services and job recommendations, have become increasingly prevalent. For the success of these platforms, it is crucial to design reciprocal recommender systems (RRSs) that not only increase the total number of matches but also avoid creating unfairness among users. In this paper, we investigate the fairness of RRSs on matching platforms. From the perspective of fair division, we define the users' opportunities to be recommended and establish the fairness concept of envy-freeness in the allocation of these opportunities. We first introduce the Social Welfare (SW) method, which approximately maximizes the number of matches, and show that it leads to significant unfairness in recommendation opportunities, illustrating the trade-off between fairness and match rates. To address this challenge, we propose the Nash Social Welfare (NSW) method, which alternately optimizes two NSW functions and achieves nearly envy-free recommendations. We further generalize the SW and NSW method to the $α$-SW method, which balances the trade-off between fairness and high match rates. Additionally, we develop a computationally efficient approximation algorithm for the SW/NSW/$α$-SW methods based on the Sinkhorn algorithm. Through extensive experiments on both synthetic datasets and two real-world datasets, we demonstrate the practical effectiveness of our approach.
BibTeX
@misc{tomita2026balancing,
  author = {Yoji Tomita and Luoyi Fu},
  title = {{Balancing Fairness and High Match Rates in Reciprocal Recommender Systems: A Nash Social Welfare Approach}},
  year = {2026},
  eprint = {2601.13609},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2601.13609},
}
Figure