Multiwinner Elections under Minimax Chamberlin-Courant Rule in Euclidean Space
Description: We consider a fair and diverse committee selection problem. Here, the goal is to select a fixed number of candidates (a committee) based on the voters’ preferences. The problem encapsulates several application scenarios ranging from choosing representatives in democracies to staff hiring and procurement decisions. An interesting application scenario also includes selecting a fixed number of diverse search results for a query to a search engine. We study the problem when candidates and voters are embedded in a Euclidean space, and voters’ preferences are derived from their distance to the candidates. We give several efficient algorithms with appealing approximate fairness guarantees.
Anonymity Preserving Space Partitions
Description: Given a dataset partitioned according to predefined attributes, we consider the problem of removing the minimum number of attributes (equivalently, merging a minimum number of parts) so that each non-empty part contains at least t-data points (i.e., t-anonymous dataset). We give an efficient algorithm to compute almost optimal solution and an exponential algorithm to compute an exact solution.
Equitable Division of a Path
Description: We investigate the problem of fairly dividing a set of items placed on a line (path). We make sure that each participating agent gets a contiguous set of items (on the line). This setting is relevant in many real-life scenarios. For example, land division among different departments in a university or a company, as each department would prefer a contiguous piece of land. We design an efficient algorithm to compute an equitable division of items. For specific restricted settings, we also give stronger fairness guarantees such as Pareto optimality.
Fair Covering of Points by Balls
Description: We study the variant of the clustering problem with fairness constraints. The motivation for this project stems from the following scenario – Our goal is to place a fixed number of facilities (For example, hospitals) in a city. The population of the city includes different communities, and each house belongs to one of these communities. A household is served by a facility if it lies within a certain distance from the facility. We want to find the locations to build the new facilities to maximize the number of households served while ensuring that each community is served proportionally. For example, suppose the city has two communities, A, B consisting of 60, 40 percent of the city houses, respectively, then in the final solution. In that case, the ratio of the number of households served for communities A, B should be 60 to 40, respectively. We give an algorithm that trades time seamlessly with the quality of the solution (i.e., computing a more accurate solution takes more time).
On the Complexity of Winner Verification and Candidate Winner for Multiwinner Voting Rules
Description: We investigate two variants of the diverse committee selection problem. In general, the goal here is to select a fixed number of candidates (a committee) based on the voters’ preferences. We refer to the committees optimizing the objective function (committees in the solution set) as the winning committees. The problem encapsulates several application scenarios, ranging from choosing representatives in democracies to staff hiring and procurement decisions. An interesting application scenario also includes selecting a fixed number of diverse search results for a query to a search engine. We consider the following two related variants of the problem: i) Given a committee, checking if it is a winning committee. ii) Given a candidate, checking if it belongs to some winning committee. We show that, in general, the problem is hard, and the straightforward brute-force algorithm is the best one can do. But when the voters’ preferences are structured, we give efficient algorithms to solve both the problems.