Introduction
Reciprocal Recommender Systems (RRSs) are essential for two-sided matching markets such as online dating, job recruitment, and freelance platforms. Unlike traditional recommendation tasks where only the user's preference matters, RRSs must ensure mutual interest: a recommendation is only successful if both parties find each other attractive. Furthermore, these systems must manage "congestion"—the tendency for recommendations to cluster around a few highly popular users, leading to a suboptimal distribution of matches and overwhelming "superstar" participants.
The Challenge of Social Welfare Maximization
Recent advancements in RRS have focused on Social Welfare (SW) maximization, which aims to optimize the total expected number of matches across the entire platform. While theoretically sound, SW methods face two significant hurdles:
- Computational Complexity: These methods typically exhibit quadratic complexity, making them difficult to scale to large-scale real-world datasets.
- Dependence on Examination Functions: SW models rely on a "position-based model," assuming the system knows the exact probability of a user examining an item at a specific rank (the examination function). In practice, this function is difficult to estimate and varies significantly across different user interfaces and behaviors.
Methodology: Transferable Utility Matching
To overcome these limitations, researchers from CyberAgent propose a novel approach based on Transferable Utility (TU) matching theory. Instead of treating recommendation as a pure optimization problem, they model it as an economic market equilibrium.
Core Concepts
The TU model introduces "virtual transfers"—mathematical shadow prices—that occur between users. These transfers act as a balancing mechanism: if a user is excessively popular, their "price" increases, signaling the system to distribute recommendations toward other compatible users. This naturally mitigates congestion without requiring explicit constraints.
The authors utilize the Choo-Siow model, assuming that preference errors follow a Gumbel distribution. This formulation allows the matching problem to be solved efficiently using the Iterative Proportional Fitting Procedure (IPFP). Crucially, the TU method maintains a dot-product structure, ensuring compatibility with modern high-speed vector search engines like FAISS or Milvus for real-time retrieval.
Experimental Evaluation
The proposed TU method was evaluated against standard baselines ("Naive" and "Reciprocal") and the state-of-the-art Social Welfare (SW) method using both synthetic and real-world dating platform data.
Scalability and Market Size
Synthetic experiments demonstrated that the TU method matches the performance of SW in smaller markets while offering superior scalability. As shown in Figure 1, the SW method becomes computationally infeasible as the market size $n$ increases to 500, whereas the TU method continues to provide high-quality matching results.
Robustness and Examination-Agnosticism
A key advantage of the TU approach is its "examination-agnostic" nature. Because the model does not explicitly incorporate the examination function into its core mathematical framework, it remains robust even when user browsing behavior is unknown or misspecified.
Experiments with different browsing models—logarithmic, inverse, and exponential decay—showed that while SW performance can degrade significantly if the assumed examination function is incorrect, the TU method consistently achieves near-optimal results.
Key Insights
- Market Equilibrium as a Solution: Modeling recommendation as a stable market equilibrium effectively solves the popularity concentration problem.
- Fairness: The TU method significantly reduces the Gini index of matches, ensuring a more equitable distribution of matches across the user base compared to Naive or Reciprocal baselines.
- Real-World Application: On a large-scale Japanese dating platform dataset ($1,000 \times 1,000$), the TU method was the only advanced approach capable of producing results within reasonable time and memory constraints, outperforming simpler baselines.
Conclusion
The Transferable Utility matching approach represents a significant step forward for reciprocal recommendation. By combining economic theory with efficient iterative algorithms, it provides a scalable, fair, and robust solution that operates effectively without the need for precise behavioral modeling. Future work will explore stochastic optimizations for even larger datasets and live A/B testing in production environments.
Summary updated