Document Open Access Logo

Ranking with Fairness Constraints

Authors L. Elisa Celis, Damian Straszak, Nisheeth K. Vishnoi

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.28.pdf
  • Filesize: 0.5 MB
  • 15 pages

Document Identifiers

Author Details

L. Elisa Celis
  • École Polytechnique Fédérale de Lausanne (EPFL), Switzerland
Damian Straszak
  • École Polytechnique Fédérale de Lausanne (EPFL), Switzerland
Nisheeth K. Vishnoi
  • École Polytechnique Fédérale de Lausanne (EPFL), Switzerland

Cite AsGet BibTex

L. Elisa Celis, Damian Straszak, and Nisheeth K. Vishnoi. Ranking with Fairness Constraints. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.28

Abstract

Ranking algorithms are deployed widely to order a set of items in applications such as search engines, news feeds, and recommendation systems. Recent studies, however, have shown that, left unchecked, the output of ranking algorithms can result in decreased diversity in the type of content presented, promote stereotypes, and polarize opinions. In order to address such issues, we study the following variant of the traditional ranking problem when, in addition, there are fairness or diversity constraints. Given a collection of items along with 1) the value of placing an item in a particular position in the ranking, 2) the collection of sensitive attributes (such as gender, race, political opinion) of each item and 3) a collection of fairness constraints that, for each k, bound the number of items with each attribute that are allowed to appear in the top k positions of the ranking, the goal is to output a ranking that maximizes the value with respect to the original rank quality metric while respecting the constraints. This problem encapsulates various well-studied problems related to bipartite and hypergraph matching as special cases and turns out to be hard to approximate even with simple constraints. Our main technical contributions are fast exact and approximation algorithms along with complementary hardness results that, together, come close to settling the approximability of this constrained ranking maximization problem. Unlike prior work on the approximability of constrained matching problems, our algorithm runs in linear time, even when the number of constraints is (polynomially) large, its approximation ratio does not depend on the number of constraints, and it produces solutions with small constraint violations. Our results rely on insights about the constrained matching problem when the objective function satisfies certain properties that appear in common ranking metrics such as discounted cumulative gain (DCG), Spearman's rho or Bradley-Terry, along with the nested structure of fairness constraints.

Subject Classification

ACM Subject Classification
  • Information systems → Retrieval models and ranking
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Discrete optimization
Keywords
  • Ranking
  • Fairness
  • Optimization
  • Matching
  • Approximation Algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Sanjeev Arora, Alan M. Frieze, and Haim Kaplan. A new rounding procedure for the assignment problem with applications to dense graph arrangement problems. In 37th Annual Symposium on Foundations of Computer Science, FOCS '96, Burlington, Vermont, USA, 14-16 October, 1996, pages 21-30, 1996. URL: http://dx.doi.org/10.1109/SFCS.1996.548460.
  2. Drake Baer. The `Filter Bubble' Explains Why Trump Won and You Didn't See It Coming, November 2016. NY Mag. Google Scholar
  3. Eytan Bakshy, Solomon Messing, and Lada A Adamic. Exposure to ideologically diverse news and opinion on facebook. Science, 348(6239):1130-1132, 2015. Google Scholar
  4. S. Barocas and A.D. Selbst. Big Data’s Disparate Impact. SSRN eLibrary, 2015. Google Scholar
  5. Tolga Bolukbasi, Kai-Wei Chang, James Y Zou, Venkatesh Saligrama, and Adam T Kalai. Man is to computer programmer as woman is to homemaker? Debiasing word embeddings. In Advances in Neural Information Processing Systems, pages 4349-4357, 2016. Google Scholar
  6. Ralph Allan Bradley and Milton E Terry. Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324-345, 1952. Google Scholar
  7. Jaime Carbonell and Jade Goldstein. The use of MMR, diversity-based reranking for reordering documents and producing summaries. In Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, pages 335-336. ACM, 1998. Google Scholar
  8. L. Elisa Celis, Amit Deshpande, Tarun Kathuria, Damian Straszak, and Nisheeth K. Vishnoi. On the complexity of constrained determinantal point processes. In APPROX/RANDOM 2017, pages 36:1-36:22, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.36.
  9. L. Elisa Celis, Amit Deshpande, Tarun Kathuria, and Nisheeth K Vishnoi. How to be fair and diverse? Fairness, Accountability and Transparency in Machine Learning, 2016. Google Scholar
  10. L. Elisa Celis, Lingxiao Huang, and Nisheeth K. Vishnoi. Multiwinner voting with fairness constraints. In IJCAI-ECAI, 2018. Google Scholar
  11. L. Elisa Celis, Vijay Keswani, Damian Straszak, Amit Deshpande, Tarun Kathuria, and Nisheeth K. Vishnoi. Fair and diverse DPP-based data summarization. CoRR, abs/1802.04023, 2018. URL: http://arxiv.org/abs/1802.04023.
  12. L. Elisa Celis, Peter M. Krafft, and Nathan Kobe. Sequential voting promotes collective discovery in social recommendation systems. In Proceedings of the Tenth International Conference on Web and Social Media, Cologne, Germany, May 17-20, 2016., pages 42-51, 2016. URL: http://www.aaai.org/ocs/index.php/ICWSM/ICWSM16/paper/view/13160.
  13. L. Elisa Celis, Damian Straszak, and Nisheeth K. Vishnoi. Ranking with fairness constraints. CoRR, abs/1704.06840, 2017. URL: http://arxiv.org/abs/1704.06840.
  14. L. Elisa Celis and Siddartha Tekriwal. What Do Users Want in Q&A Sites: Quality or Diversity? In International Conference on Computational Social Science (IC2S2), 2017. Google Scholar
  15. L. Elisa Celis and Nisheeth K. Vishnoi. Fair Personalization. Fairness, Accountability, and Transparency in Machine Learning, 2017. Google Scholar
  16. Chandra Chekuri and Sanjeev Khanna. A polynomial time approximation scheme for the multiple knapsack problem. SIAM J. Comput., 35(3):713-728, 2005. URL: http://dx.doi.org/10.1137/S0097539700382820.
  17. Charles LA Clarke, Maheedhar Kolla, Gordon V Cormack, Olga Vechtomova, Azin Ashkan, Stefan Büttcher, and Ian MacKinnon. Novelty and diversity in information retrieval evaluation. In Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, pages 659-666. ACM, 2008. Google Scholar
  18. Matthew Costello, James Hawdon, Thomas Ratliff, and Tyler Grantham. Who views online extremism? Individual attributes leading to exposure. Computers in Human Behavior, 63:311-320, 2016. Google Scholar
  19. Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. In ITCS, New York, NY, USA, 2012. ACM. URL: http://dx.doi.org/10.1145/2090236.2090255.
  20. Cynthia Dwork, Ravi Kumar, Moni Naor, and Dandapani Sivakumar. Rank aggregation methods for the web. In Proceedings of the 10th international conference on World Wide Web, pages 613-622. ACM, 2001. Google Scholar
  21. Robert Epstein and Ronald E. Robertson. The search engine manipulation effect (SEME) and its possible impact on the outcomes of elections. Proceedings of the National Academy of Sciences, 112(33):E4512-E4521, 2015. URL: http://dx.doi.org/10.1073/pnas.1419828112.
  22. Uriel Feige and Shlomo Jozeph. Universal factor graphs. In Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I, pages 339-350, 2012. URL: http://dx.doi.org/10.1007/978-3-642-31594-7_29.
  23. Sreenivas Gollapudi and Aneesh Sharma. An axiomatic approach for result diversification. In Proceedings of the 18th international conference on World wide web, pages 381-390. ACM, 2009. Google Scholar
  24. Fabrizio Grandoni, R Ravi, Mohit Singh, and Rico Zenklusen. New approaches to multi-objective optimization. Mathematical Programming, 146(1-2):525-554, 2014. Google Scholar
  25. J. Hastad. Clique is Hard to Approximate Within n^1-ε. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science, FOCS '96. IEEE Computer Society, 1996. Google Scholar
  26. Kalervo Järvelin and Jaana Kekäläinen. Cumulated gain-based evaluation of IR techniques. ACM Transactions on Information Systems (TOIS), 20(4):422-446, 2002. Google Scholar
  27. T.A. Jenkyns. The Efficacy of the 'greedy' Algorithm. In Proc. of 7th S-E. Conf. on Combinatorics, Graph Theory and Computing, pages 341-350, 1976. Google Scholar
  28. Matthew Kay, Cynthia Matuszek, and Sean A Munson. Unequal representation and gender stereotypes in image search results for occupations. In Proceedings of the 33rd Annual ACM Conference on Human Factors in Computing Systems, pages 3819-3828. ACM, 2015. Google Scholar
  29. Keith Kirkpatrick. Battling algorithmic bias: how do we ensure algorithms treat us fairly? Communications of the ACM, 59(10):16-17, 2016. Google Scholar
  30. Jon Kleinberg, Sendhil Mullainathan, and Manish Raghavan. Inherent trade-offs in the fair determination of risk scores. Innovations in Theoretical Computer Science, 2017. Google Scholar
  31. Christopher D Manning, Prabhakar Raghavan, Hinrich Schütze, et al. Introduction to information retrieval. Cambridge university press Cambridge, 2008. Google Scholar
  32. Melvin Earl Maron and John L Kuhns. On relevance, probabilistic indexing and information retrieval. Journal of the ACM (JACM), 7(3):216-244, 1960. Google Scholar
  33. Julián Mestre. Greedy in approximation algorithms. In Algorithms - ESA 2006, 14th Annual European Symposium, Zurich, Switzerland, September 11-13, 2006, Proceedings, pages 528-539, 2006. URL: http://dx.doi.org/10.1007/11841036_48.
  34. Burt L Monroe. Fully proportional representation. American Political Science Review, 89(4):925-940, 1995. Google Scholar
  35. Debmalya Panigrahi, Atish Das Sarma, Gagan Aggarwal, and Andrew Tomkins. Online selection of diverse results. In Proceedings of the fifth ACM international conference on Web search and data mining, pages 263-272. ACM, 2012. Google Scholar
  36. Filip Radlinski, Paul N Bennett, Ben Carterette, and Thorsten Joachims. Redundancy, diversity and interdependent document relevance. In ACM SIGIR Forum, volume 43, pages 46-52. ACM, 2009. Google Scholar
  37. Filip Radlinski, Robert Kleinberg, and Thorsten Joachims. Learning diverse rankings with multi-armed bandits. In Proceedings of the 25th International conference on Machine learning, pages 784-791. ACM, 2008. Google Scholar
  38. Stephen E Robertson. The probability ranking principle in ir. Journal of documentation, 33(4):294-304, 1977. Google Scholar
  39. Gerard Salton and Christopher Buckley. Term-weighting approaches in automatic text retrieval. Information Processing &Management, 24(5):513-523, 1988. URL: http://dx.doi.org/10.1016/0306-4573(88)90021-0.
  40. Aleksandrs Slivkins, Filip Radlinski, and Sreenivas Gollapudi. Ranked bandits in metric spaces: learning diverse rankings over large document collections. Journal of Machine Learning Research, 14(Feb):399-436, 2013. Google Scholar
  41. Charles Spearman. The proof and measurement of association between two things. The American journal of psychology, 15(1):72-101, 1904. Google Scholar
  42. Aravind Srinivasan. Improved approximations of packing and covering problems. In Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 29 May-1 June 1995, Las Vegas, Nevada, USA, pages 268-276, 1995. URL: http://dx.doi.org/10.1145/225058.225138.
  43. Ke Yang and Julia Stoyanovich. Measuring fairness in ranked outputs. In Proceedings of the 29th International Conference on Scientific and Statistical Database Management, Chicago, IL, USA, June 27-29, 2017, pages 22:1-22:6, 2017. URL: http://dx.doi.org/10.1145/3085504.3085526.
  44. Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna Gummadi. Fairness Constraints: A Mechanism for Fair Classification. In Fairness, Accountability, and Transparency in Machine Learning, 2015. URL: http://www.fatml.org/cfp.html.
  45. Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork. Learning fair representations. In Proceedings of The 30th International Conference on Machine Learning, pages 325-333, 2013. Google Scholar
  46. Cheng Xiang Zhai, William W Cohen, and John Lafferty. Beyond independent relevance: methods and evaluation metrics for subtopic retrieval. In Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, pages 10-17. ACM, 2003. Google Scholar
  47. Mi Zhang and Neil Hurley. Avoiding monotony: improving the diversity of recommendation lists. In Proceedings of the 2008 ACM conference on Recommender systems, pages 123-130. ACM, 2008. Google Scholar
  48. Cai-Nicolas Ziegler, Sean M McNee, Joseph A Konstan, and Georg Lausen. Improving recommendation lists through topic diversification. In Proceedings of the 14th international conference on World Wide Web, pages 22-32. ACM, 2005. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact