What is it about?
Consider the problem of forming a representative committee. In essence, the task amounts to finding a group of people among a given set of candidates to represent the will of a (usually) larger body of constituents. In computational terms, this task can be modeled mathematically as a clustering problem, where each cluster center is a chosen candidate, and the points in the corresponding cluster are the constituents it best represents. In certain scenarios, it may be essential to consider additional requirements. For instance, it may be necessary that a minimum number of the chosen committee members belong to a certain minority-ethnic background, to ensure that all groups in a society are represented in the decision-making process. Introducing minimum-representation constraints makes the clustering problem nearly impossible to solve, and we present theoretical results showing that it is mostly unlikely that an efficient algorithm exists to solve this problem. Even though we present efficient heuristic solutions which can solve most instances of the problem in practice, it is mostly unlikely to design efficient algorithmic solutions that has a theoretical bound on the quality of the solution returned.
Featured Image
Photo by Miles Peacock on Unsplash
Why is it important?
The idea of using algorithmic computational tools for assisted decision making has gained significant negative attention in recent years, since these systems behave in a way that a human observer will deem it as unfair or biased, often especially towards certain minority-ethnic groups. A plethora of fairness notions have been introduced in recent times to avoid bias in algorithmic decision making systems. However, majority of the existing literature assume that the minority groups are disjoint, which is not always true. For example, a potential candidate can be an ethnically-black non-binary person who also has a physical disability, and choosing such a candidate satisfy representation constraint of more than one minority group due to the intersectionality of groups. In our work, we study clustering problems where a certain minimum number of candidates must be chosen from each minority-ethnic group to ensure diversity, where the potential candidates may belong to more than one group.
Perspectives
A fundamental philosophical question is what is fair? The answer will be highly subjective and perspective, which depends on who is answering and the notion of fairness under consideration. We leave it to sociologists to define what is fair in a society. As computer scientists, we abstract a notion of fairness that adhere to societal norms as mathematical constraints and try to obtain solutions that satisfy these constraints. Sometimes the mathematical constraints introduced to ensure a fairness notion makes the problem computationally very hard to solve. In our work, we show that ensuring all minority groups are given a fair chance to be part of a representative committee is nearly impossible to achieve, unless there is a breakthrough in the computing technology. Studying the computational complexity of different fairness notions help us to distinguish between fairness notions that are theoretically possible to achieve and not possible to achieve.
Suhas Thejaswi
Read the Original
This page is a summary of: Clustering with Fair-Center Representation, August 2022, ACM (Association for Computing Machinery),
DOI: 10.1145/3534678.3539487.
You can read the full text:
Resources
Contributors
The following have contributed to this page
