Optimizing long-term social welfare in recommender systems: a constrained matching approach
AUTHORs: 
Martin Mladenov, Elliot Creager, Omer Ben-Porat, Kevin Swersky, Richard Zemel, 
Craig BoutilierAuthors Info & Claims
Article No.: 648, Pages 6987 - 6998
Abstract
Most recommender systems (RS) research assumes that a user's utility can be maximized independently of the utility of the other agents (e.g., other users, content providers). In realistic settings, this is often not true--the dynamics of an RS ecosystem couple the long-term utility of all agents. In this work, we explore settings in which content providers cannot remain viable unless they receive a certain level of user engagement. We formulate the recommendation problem in this setting as one of equilibrium selection in the induced dynamical system, and show that it can be solved as an optimal constrained matching problem. Our model ensures the system reaches an equilibrium with maximal social welfare supported by a sufficiently diverse set of viable providers. We demonstrate that even in a simple, stylized dynamical RS model, the standard myopic approach to recommendation-- always matching a user to the best provider-- performs poorly. We develop several scalable techniques to solve the matching problem, and also draw connections to various notions of user regret and fairness, arguing that these outcomes are fairer in a utilitarian sense.
Supplementary Material
Supplemental material.
- Download
- 471.61 KB
References
[1]
An, H., Singh, M., and Svensson, O. LP-based algorithms for capacitated facility location. SIAM Journal on Computing, 46(1):272-306, 1 2017. ISSN 0097-5397.
[2]
Asudeh, A., Jagadishy, H., Stoyanovichz, J., and Das, G. Designing fair ranking schemes. ACM SIGMOD Record, 01 2019.
[3]
Barocas, S. and Selbst, A. D. Big data's disparate impact. California Law Review, 671, 2016.
[4]
Ben-Porat, O. and Tennenholtz, M. A game-theoretic approach to recommendation systems with strategic content providers. In Advances in Neural Information Processing Systems 31 (NeurIPS-18), pp. 1118-1128, Montreal, 2018.
[5]
Ben-Porat, O., Goren, G., Rosenberg, I., and Tennenholtz, M. From recommendation systems to facility location games. In Proceedings of the Thirty-third AAAI Conference on Artificial Intelligence (AAAI-19), pp. 1772-1779, Honolulu, 2019.
[6]
Beutel, A., Covington, P., Jain, S., Xu, C., Li, J., Gatto, V., and Chi, E. H. Latent cross: Making use of context in recurrent recommender systems. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining (WSDM-18), pp. 46-54, Marina Del Rey, CA, 2018.
[7]
Beutel, A., Chen, J., Doshi, T., Qian, H., Wei, L., Wu, Y., Heldt, L., Zhao, Z., Hong, L., Chi, E. H., and Goodrow, C. Fairness in recommendation ranking through pairwise comparisons. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD-19), pp. 2212-2220, Anchorage, AK, 2019.
[8]
Biega, A. J., Gummadi, K. P., and Weikum, G. Equity of attention: Amortizing individual fairness in rankings. In The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval, SIGIR '18, pp. 405-414, New York, NY, USA, 2018. Association for Computing Machinery.
[9]
Binns, R. Fairness in machine learning: Lessons from political philosophy. In Conference on Fairness, Accountability and Transparency, pp. 149-159, 2018.
[10]
Bountouridis, D., Harambam, J., Makhortykh, M., Marrero, M., Tintarev, N., and Hauff, C. SIREN: A simulation framework for understanding the effects of recommender systems in online news environments. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pp. 150-159. ACM, 2019.
[11]
Boyd, S., Parikh, N., Chu, E., Peleato, B., and Eckstein, J. Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn., 3(1):1-122, January 2011. ISSN 1935-8237.
[12]
Celis, L. E., Straszak, D., and Vishnoi, N. K. Ranking with fairness constraints. In ICALP, 2017.
[13]
Celma, Ò. The long tail in recommender systems. In Music Recommendation and Discovery, pp. 87-107. Springer, 2010.
[14]
Chaney, A. J. B., Stewart, B. M., and Engelhardt, B. E. How algorithmic confounding in recommendation systems increases homogeneity and decreases utility. In Proceedings of the 12th ACM Conference on Recommender Systems, RecSys '18, pp. 224-232, New York, NY, USA, 2018. Association for Computing Machinery.
[15]
Chen, M., Beutel, A., Covington, P., Jain, S., Belletti, F., and Chi, E. Top-k off-policy correction for a REINFORCE recommender system. In 12th ACM International Conference on Web Search and Data Mining (WSDM-19), pp. 456-464, Melbourne, Australia, 2018.
[16]
Cornuejols, G., Fisher, M. L., and Nemhauser, G. L. Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms. Management Science, 23(8):789-810, 1977. URL http://www.jstor.org/stable/2630709.
[17]
Covington, P., Adams, J., and Sargin, E. Deep neural networks for YouTube recommendations. In Proceedings of the 10th ACM Conference on Recommender Systems, pp. 191-198, Boston, 2016.
[18]
Doroudi, S., Thomas, P. S., and Brunskill, E. Importance sampling for fair policy selection. In Uncertainty in Artificial Intelligence (UAI), 2017.
[19]
Dwork, C., Hardt, M., Pitassi, T., Reingold, O., and Zemel, R. Fairness through awareness. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS '12, pp. 214-226. Association for Computing Machinery, 2012.
[20]
Ensign, D., Friedler, S. A., Neville, S., Scheidegger, C., and Venkatasubramanian, S. Runaway feedback loops in predictive policing. In Conference on Fairness, Accountability and Transparency, pp. 160-171, 2018.
[21]
Hajiaghayi, M. T., Mahdian, M., and Mirrokni, V. S. The facility location problem with general cost functions. Networks, 42(1):42-47, 2003.
[22]
Harper, F. M. and Konstan, J. A. The Movielens datasets: History and context. ACM Transactions on Interactive Intelligent Systems, 5(4):1-19, 2015.
[23]
Hashimoto, T. B., Srivastava, M., Namkoong, H., and Liang, P. Fairness without demographics in repeated loss minimization. In International Conference on Machine Learning, 2018.
[24]
He, X., Liao, L., Zhang, H., Nie, L., Hu, X., and Chua, T. Neural collaborative filtering. In Proceedings of the 26th International Conference on World Wide Web (WWW-17), pp. 173-182, Perth, Australia, 2017.
[25]
Hu, L. and Chen, Y. A short-term intervention for long-term fairness in the labor market. In Proceedings of the 2018 World Wide Web Conference, pp. 1389-1398. International World Wide Web Conferences Steering Committee, 2018.
[26]
Hu, L., Immorlica, N., and Vaughan, J. W. The disparate effects of strategic manipulation. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pp. 259-268. ACM, 2019.
[27]
Hu, Y., Koren, Y., and Volinsky, C. Collaborative filtering for implicit feedback datasets. In 2008 Eighth IEEE International Conference on Data Mining, pp. 263-272. Ieee, 2008.
[28]
Ie, E., Hsu, C.-w., Mladenov, M., Jain, V., Narvekar, S., Wang, J., Wu, R., and Boutilier, C. Recsim: A configurable simulation platform for recommender systems. arXiv preprint arXiv:1909.04847, 2019a.
[29]
Ie, E., Jain, V., Wang, J., Narvekar, S., Agarwal, R., Wu, R., Cheng, H.-T., Chandra, T., and Boutilier, C. SlateQ: A tractable decomposition for reinforcement learning with recommendation sets. In Proceedings of the Twenty-eighth International Joint Conference on Artificial Intelligence (IJCAI-19), pp. 2592-2599, Macau, 2019b.
[30]
Jabbari, S., Joseph, M., Kearns, M., Morgenstern, J., and Roth, A. Fairness in reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning-Volume 70, pp. 1617-1626. JMLR.org, 2017.
[31]
Jacobson, K., Murali, V., Newett, E., Whitman, B., and Yon, R. Music personalization at Spotify. In Proceedings of the 10th ACM Conference on Recommender Systems (RecSys16), pp. 373-373, Boston, Massachusetts, USA, 2016.
[32]
Jones, M. The maximum facility location problem. B.s. thesis, The University of Sydney, Sydney, Australia, 2015.
[33]
Joseph, M., Kearns, M., Morgenstern, J. H., and Roth, A. Fairness in learning: Classic and contextual bandits. In Advances in Neural Information Processing Systems, pp. 325-333, 2016.
[34]
Kahneman, D. and Tversky, A. Prospect theory: An analysis of decision under risk. Econometrica, 47(2):263-292, 1979.
[35]
Kannan, S., Roth, A., and Ziani, J. Downstream effects of affirmative action. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pp. 240-248. ACM, 2019.
[36]
Konstan, J. A., Miller, B. N., Maltz, D., Herlocker, J. L., Gordon, L. R., and Riedl, J. GroupLens: Applying collaborative filtering to usenet news. Communications of the ACM, 40(3):77-87, 1997.
[37]
Kwak, H., Lee, C., Park, H., and Moon, S. What is Twitter, a social network or a news media? In Proceedings of the 19th International Conference on World Wide Web, pp. 591-600, 2010.
[38]
Leben, D. Normative principles for evaluating fairness in machine learning. In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, AIES '20, pp. 86-92, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450371100.
[39]
Li, S. On facility location with general lower bounds. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '19, pp. 2279-2290, USA, 2019. Society for Industrial and Applied Mathematics.
[40]
Lum, K. and Isaac, W. To predict and serve? Significance, 13(5):14-19, 2016.
[41]
Mehta, A. Online matching and ad allocation. Foundations and Trends in Theoretical Computer Science, 8(4):265- 368, 2013.
[42]
Mirzasoleiman, B., Karbasi, A., Sarkar, R., and Krause, A. Distributed submodular maximization. Journal of Machine Learning Research, 17(235):1-44, 2016. URL http://jmlr.org/papers/v17/mirzasoleiman16a.html.
[43]
Mladenov, M., Creager, E., Ben-Porat, O., Swersky, K., Zemel, R., and Boutilier, C. Optimizing long-term social welfare in recommender systems: A constrained matching approach. Technical report, 2020. arXiv:2008.00104.
[44]
Mouzannar, H., Ohannessian, M. I., and Srebro, N. From fair decision making to social qquality. In Proceedings of the Conference on Fairness, Accountability, and Transparency, pp. 359-368. ACM, 2019.
[45]
Ribeiro, M. H., Ottoni, R., West, R., Almeida, V. A. F., and Jr., W. M. Auditing radicalization pathways on YouTube. In FAT* '20: Conference on Fairness, Accountability, and Transparency, pp. 131-141, Barcelona, 2020.
[46]
Salakhutdinov, R. and Mnih, A. Probabilistic matrix factorization. In Advances in Neural Information Processing Systems 20 (NIPS-07), pp. 1257-1264, Vancouver, 2007.
[47]
Singh, A. and Joachims, T. Fairness of exposure in rankings. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '18, pp. 2219-2228, New York, NY, USA, 2018. Association for Computing Machinery.
[48]
Yang, K. and Stoyanovich, J. Measuring fairness in ranked outputs. In SSDBM '17, 2016.
[49]
Zehlike, M., Bonchi, F., Castillo, C., Hajian, S., Megahed, M., and Baeza-Yates, R. Fa*ir: A fair top-k ranking algorithm. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, CIKM '17, pp. 1569-1578, New York, NY, USA, 2017. Association for Computing Machinery.
Recommendations
Nash Social Welfare Approximation for Strategic Agents
EC '17: Proceedings of the 2017 ACM Conference on Economics and ComputationThe fair division of resources among strategic agents is an important age-old problem that has led to a rich body of literature. At the center of this literature lies the question of whether there exist mechanisms that can implement fair outcomes, ...
Corruption in Auctions: Social Welfare Loss in Hybrid Multi-Unit Auctions
AAMAS '22: Proceedings of the 21st International Conference on Autonomous Agents and Multiagent SystemsWe initiate the study of the social welfare loss caused by corrupt auctioneers, both in single-item and multi-unit auctions. In our model, the auctioneer may collude with the winning bidders by letting them lower their bids in exchange for a (possibly ...
Platform Equilibrium: Analyzing Social Welfare in Online Market Places
EC '24: Proceedings of the 25th ACM Conference on Economics and ComputationWe introduce the theoretical study of a Platform Equilibrium in a market with unit-demand buyers and unit-supply sellers. Each seller can join a platform and transact with any buyer or remain off-platform and transact with a subset of buyers whom she ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2020.
Publisher
JMLR.org
Publication History
Published: 13 July 2020
Qualifiers
- Research-article
- Research
- Refereed limited
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 141Total Downloads
- Downloads (Last 12 months)109
- Downloads (Last 6 weeks)11
Reflects downloads up to 20 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in