Abstract
In two-sided marketplaces such as online flea markets, recommender systems for providing consumers with personalized item rankings play a key role in promoting transactions between item providers and consumers. Meanwhile, two-sided marketplaces face the problem of balancing consumer satisfaction and fairness among items to stimulate activity of item providers. Saito and Joachims (2022) devised an impact-based fair ranking method for maximizing the Nash social welfare based on fair division; however, this method, which requires solving a large-scale constrained nonlinear optimization problem, is very difficult to apply to practical-scale recommender systems. We thus propose a fast solution to the impact-based fair ranking problem. We first transform the fair ranking problem into an unconstrained optimization problem and then design a gradient ascent method that repeatedly executes the Sinkhorn algorithm. Experimental results demonstrate that our algorithm provides fair rankings of high quality and is about 1000 times faster than application of commercial optimization software.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
All these methods were implemented in Python on an Ubuntu 22.04.3 LTS computer equipped with Intel Core i9 12900k CPU 5.2 GHz (128 GB RAM) and NVIDIA GeForce RTX 3090 GPU 1.7 GHz (24 GB RAM). Our implementation is available at https://github.com/tubo213/nsw-with-optimal-transport.
References
Altschuler, J., Niles-Weed, J., Rigollet, P.: Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration. Adv. Neural Inf. Process. Syst. 30 (2017)
ApS, M.: The MOSEK optimizer API for Python manual, version 10.2 (2024). https://docs.mosek.com/latest/pythonapi/index.html
Bhatia, K., et al.: The extreme classification repository: multi-label datasets and code (2016). http://manikvarma.org/downloads/XC/XMLRepository.html
Biega, A.J., Gummadi, K.P., Weikum, G.: Equity of attention: amortizing individual fairness in rankings. In: The 41st International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 405–414 (2018)
Craswell, N., Zoeter, O., Taylor, M., Ramsey, B.: An experimental comparison of click position-bias models. In: Proceedings of the 2008 International Conference on Web Search and Data Mining, pp. 87–94 (2008)
Cuturi, M.: Sinkhorn distances: lightspeed computation of optimal transport. Adv. Neural Inf. Process. Syst. 26 (2013)
Kingma, D., Ba, J.: Adam: a method for stochastic optimization. In: International Conference on Learning Representations, San Diego (2015)
Luenberger, D.G., Ye, Y.: Linear and Nonlinear Programming. Springer (2015)
Patro, G.K., Biswas, A., Ganguly, N., Gummadi, K.P., Chakraborty, A.: FairRec: two-sided fairness for personalized recommendations in two-sided platforms. In: Proceedings of the Web Conference 2020, pp. 1194–1204 (2020)
Pitoura, E., Stefanidis, K., Koutrika, G.: Fairness in rankings and recommendations: an overview. VLDB J. 31, 431–458 (2022)
Saito, Y., Joachims, T.: Fair ranking as fair division: impact-based individual fairness in ranking. In: Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1514–1524 (2022)
Singh, A., Joachims, T.: Fairness of exposure in rankings. In: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 2219–2228 (2018)
Togashi, R., Abe, K., Saito, Y.: Scalable and provably fair exposure control for large-scale recommender systems. In: Proceedings of the ACM Web Conference 2024, pp. 3307–3318 (2024)
Acknowledgments
The authors would like to thank Yoshitsugu Yamamoto for helpful comments.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2025 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Uehara, Y. et al. (2025). Fast Solution to the Fair Ranking Problem Using the Sinkhorn Algorithm. In: Hadfi, R., Anthony, P., Sharma, A., Ito, T., Bai, Q. (eds) PRICAI 2024: Trends in Artificial Intelligence. PRICAI 2024. Lecture Notes in Computer Science(), vol 15285. Springer, Singapore. https://doi.org/10.1007/978-981-96-0128-8_18
Download citation
DOI: https://doi.org/10.1007/978-981-96-0128-8_18
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-96-0127-1
Online ISBN: 978-981-96-0128-8
eBook Packages: Computer ScienceComputer Science (R0)