Abolfazl Asudeh
H. V. Jagadish
ABSTRACT
Items from a database are often ranked based on a combination of criteria. The weight given to each criterion in the combination can greatly affect the fairness of the produced ranking, for example, preferring men over women. A user may have the flexibility to choose combinations that weigh these criteria differently, within limits. In this paper, we develop a system that helps users choose criterion weights that lead to greater fairness. We consider ranking functions that compute the score of each item as a weighted sum of (numeric) attribute values, and then sort items on their score. Each ranking function can be expressed as a point in a multi-dimensional space. For a broad range of fairness criteria, including proportionality, we show how to efficiently identify regions in this space that satisfy these criteria. Using this identification method, our system is able to tell users whether their proposed ranking function satisfies the desired fairness criteria and, if it does not, to suggest the smallest modification that does. Our extensive experiments on real datasets demonstrate that our methods are able to find solutions that satisfy fairness criteria effectively (usually with only small changes to proposed weight vectors) and efficiently (in interactive time, after some initial pre-processing).
- Solon Barocas and Andrew D. Selbst. Big data's disparate impact. California Law Review, 104, 2016.Google Scholar
- Batya Friedman and Helen Nissenbaum. Bias in computer systems. ACM Trans. Inf. Syst., 14(3):330--347, 1996. Google ScholarDigital Library
- Michael Feldman, Sorelle A. Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubramanian. Certifying and removing disparate impact. In SIGKDD, 2015. Google ScholarDigital Library
- Julia Stoyanovich, Ke Yang, and H.V. Jagadish. Online set selection with fairness and diversity constraints. In EDBT, 2018.Google Scholar
- Ke Yang and Julia Stoyanovich. Measuring fairness in ranked outputs. In SSDBM, 2017. Google ScholarDigital Library
- Meike Zehlike, Francesco Bonchi, Carlos Castillo, Sara Hajian, Mohamed Megahed, and Ricardo A. Baeza-Yates. FA*IR: A fair top-k ranking algorithm. In CIKM, 2017. Google ScholarDigital Library
- Indre Zliobaite. Measuring discrimination in algorithmic decision making. Data Min. Knowl. Discov., 31(4):1060--1089, 2017. Google ScholarDigital Library
- Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard S. Zemel. Fairness through awareness. In ITCS, 2012. Google ScholarDigital Library
- Sorelle A. Friedler, Carlos Scheidegger, and Suresh Venkatasubramanian. On the (im)possibility of fairness. CoRR, abs/1609.07236, 2016.Google Scholar
- L. Elisa Celis, Damian Straszak, and Nisheeth K. Vishnoi. Ranking with fairness constraints. In ICALP, 2018.Google Scholar
- The College Board. SAT percentile ranks, 2014.Google Scholar
- Peter Jacobs. Legacy admissions policies were originally created to keep jewish students out of elite colleges. Business Insider, 2013.Google Scholar
- Jerome Karabel. The Chosen: The Hidden History of Admission and Exclusion at Harvard, Yale, and Princeton. HMHCO, 2005.Google Scholar
- The New York City Council. Int. No. 1696-A: A Local Law in relation to automated decision systems used by agencies. https://laws.council.nyc.gov/legislation/int-1696--2017/, 2017. {Online; accessed on 28-September-2018}.Google Scholar
- Abolfazl Asudeh, Nan Zhang, and Gautam Das. Query reranking as a service. PVLDB, 9(11):888--899, 2016.Google ScholarDigital Library
- Abolfazl Asudeh, Azade Nazi, Nan Zhang, and Gautam Das. Efficient computation of regret-ratio minimizing set: A compact maxima representative. In SIGMOD, 2017.Google ScholarDigital Library
- Herbert Edelsbrunner. Algorithms in combinatorial geometry, volume 10. Springer Science & Business Media, 2012. Google ScholarDigital Library
- Abolfazl Asudeh, Saravanan Thirumuruganathan, Nan Zhang, and Gautam Das. Discovering the skyline of web databases. VLDB, 2016.Google ScholarDigital Library
- Akrivi Vlachou, Christos Doulkeridis, and Yannis Kotidis. Angle-based space partitioning for efficient parallel skyline computation. In SIGMOD. ACM, 2008. Google ScholarDigital Library
- M L Fredman and R E Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. JACM, 34(3), 1987.Google Scholar
- Abolfazl Asudeh, Azade Nazi, Nan Zhang, Gautam Das, and H.V. Jagadish. Rrr: Rank-regret representative. In SIGMOD, 2019.Google ScholarDigital Library
- Abolfazl Asudeh, H.V. Jagadish, Gerome Miklau, and Julia Stoyanovich. On obtaining stable rankings. PVDLB, 12(3):237--250, 2018.Google Scholar
- Mervin E Muller. A note on a method for generating points uniformly on n-dimensional spheres. Communications of the ACM, 2(4), 1959.Google Scholar
- George Marsaglia et al. Choosing a point from the surface of a sphere. The Annals of Mathematical Statistics, 43(2), 1972.Google Scholar
- Julia Angwin, Jeff Larson, Surya Mattu, and Lauren Kirchner. Machine bias: Risk assessments in criminal sentencing. ProPublica, 5/23/2016.Google Scholar
- United States Department of Transportation. Bureau of transportation statistics. https://www.transtats.bts.gov/DL_SelectFields.asp?Table_ID=236&DB_Short_Name=On-Time. {Online; accessed 12/29/2017}.Google Scholar
- I Ilyas, G Beskales, and M Soliman. A survey of top-k query processing techniques in relational database systems. CSUR, 40(4), 2008. Google ScholarDigital Library
- F Rahman, A Asudeh, N Koudas, and G Das. Efficient computation of subspace skyline over categorical domains. In CIKM. ACM, 2017.Google ScholarDigital Library
- S Borzsony, Donald Kossmann, and Konrad Stocker. The skyline operator. In ICDE, 2001. Google ScholarDigital Library
- Danupon Nanongkai, Atish Das Sarma, Ashwin Lall, Richard J Lipton, and Jun Xu. Regret-minimizing representative databases. VLDB, 2010.Google ScholarDigital Library
- Ronald Fagin, Amnon Lotem, and Moni Naor. Optimal aggregation algorithms for middleware. JCSS, 66(4), 2003. Google ScholarDigital Library
- V. Hristidis and Y. Papakonstantinou. Algorithms and applications for answering ranked queries using ranked views. VLDBJ, 2004. Google ScholarDigital Library
- Y. Chang, L. Bergman, V. Castelli, C. Li, M. Lo, and J. Smith. The onion technique: indexing for linear optimization queries. In SIGMOD, 2000. Google ScholarDigital Library
- Gisli R Hjaltason and Hanan Samet. Ranking in spatial databases. In SSTD. Springer, 1995. Google ScholarDigital Library
- S. Chaudhuri, G. Das, V. Hristidis, and G. Weikum. Probabilistic ranking of database query results. In PVLDB, 2004. Google ScholarDigital Library
- Marina Drosou, HV Jagadish, Evaggelia Pitoura, and Julia Stoyanovich. Diversity in Big Data: A review. Big Data, 5(2), 2017.Google Scholar
- Bert Boyce. Beyond topicality: A two stage view of relevance and the retrieval process. Inf Process Manag, 18(3):105--109, 1982.Google ScholarCross Ref
- Rakesh Agrawal, Sreenivas Gollapudi, Alan Halverson, and Samuel Ieong. Diversifying search results. In WSDM, pages 5--14. ACM, 2009. Google ScholarDigital Library
- Harr Chen and David R Karger. Less is more: probabilistic models for retrieving fewer relevant documents. In SIGIR. ACM, 2006. Google ScholarDigital Library
- Mark De Berg, Otfried Cheong, Marc Van Kreveld, and Mark Overmars. Computational Geometry: Introduction. Springer, 2008.Google Scholar
- Peter Orlik and Hiroaki Terao. Arrangements of hyperplanes, volume 300. Springer Science & Business Media, 2013.Google Scholar
- Branko Grünbaum. Arrangements of hyperplanes. In Convex Polytopes, pages 432--454. Springer, 2003.Google ScholarCross Ref
- Vadim V Schechtman and Alexander N Varchenko. Arrangements of hyperplanes and lie algebra homology. Inventiones math., 1991.Google Scholar
- Pankaj K Agarwal and Micha Sharir. Arrangements and their applications. Handbook of computational geometry, pages 49--119, 2000.Google Scholar
- Raphael A Finkel and Jon Louis Bentley. Quad trees a data structure for retrieval on composite keys. Acta informatica, 4(1):1--9, 1974. Google ScholarDigital Library
Index Terms
- Designing Fair Ranking Schemes
Recommendations
MithraRanking: A System for Responsible Ranking Design
SIGMOD '19: Proceedings of the 2019 International Conference on Management of DataItems from a database are often ranked based on a combination of criteria. The weight given to each criterion in the combination can greatly affect the ranking produced. Often, a user may have a general sense of the relative importance of the different ...
RRR: Rank-Regret Representative
SIGMOD '19: Proceedings of the 2019 International Conference on Management of DataSelecting the best items in a dataset is a common task in data exploration. However, the concept of "best'' lies in the eyes of the beholder: different users may consider different attributes more important, and hence arrive at different rankings. ...
Performance evaluation of a fair backoff algorithm for IEEE 802.11 DFWMAC
MobiHoc '02: Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computingDue to hidden terminals and a dynamic topology, contention among stations in an ad-hoc network is not homogeneous. Some stations are at a disadvantage in opportunity of access to the shared channel and can suffer severe throughput degradation when the ...
Comments