Near Neighbor: Who is the Fairest of Them All?

Nowadays, many important decisions, such as college admissions, offering home loans, or estimating the likelihood of recidivism, rely on machine learning algorithms. There is a growing concern about the fairness of the algorithms and creating bias toward a specific population or feature [HPS16, Cho17, MSP16, KLL 17]. While algorithms are not inherently biased, nevertheless, they may amplify the already existing biases in the data. Hence, this concern has led to the design of fair algorithms for many different applications, e.g., [DOBD 18, ABD 18, PRW 17, CKLV19, EJJ 19, OA18, CKLV17, BIO 19, BCN19, KSAM19]. Bias in the data used for training machine learning algorithms is a monumental challenge in creating fair algorithms [HGB 07, TE11, ZVGRG17, Cho17]. Here, we are interested in a somewhat different problem, of handling the bias introduced by the data-structures used by such algorithms. Specifically, data-structures may introduce bias in the data stored in them, and the way they answer queries, because of the way the data is stored and how it is being accessed. Such a defect leads to selection bias by the algorithms using such data-structures.