Executive Summary : | Voting, networks, and fairness each has a proven-track-record of successfully modeling many real-world problems. Voting serves as a fundamental tool to aggregate different preferences over a set of candidates. And, a network is a mathematical structure to encode ``relationship'' among multiple entities. In many applications of voting, there exists a network structure on the voters. For example, let us consider a participatory budgeting scenario where the people in a city needs to collectively decide on which projects to fund. Here, there exists the city network on the set of voters and the utility derived by some voter from a project also depends on the vicinity of the project-location from the voter's location. One can also think of other applications where there exists a network on the candidates. For example, let us consider a meta-recommender system to choose k items (items correspond to the candidates) which aggregates the output of many other recommender systems (which corresponds to the voters). In such applications, one often likes to choose the final k items as diversely as possible. Suppose we have a network on the items where we have an edge between two items if they are similar. Hence, the goal of the meta-recommender system is to choose k items which ``reflects'' the output of individual recommender systems as closely as possible and the induced graph on those k items contains as few edges as possible. It is plausible to think of other important applications where the final output needs to satisfy some other graph property, say connectedness, independence, etc., of the underlying network on the candidates. On top of this, the system designer may need to satisfy additional fairness criteria with respect to some other features of the candidates, say gender, race, etc. or the network structure available on the voters or candidates. For example, one may like to ensure that the utility derived from the output by different voters does not vary too much between neighbors of the underlying network on the voters. Although there have been plenty of research activity going on in each of the three themes, namely voting, networks, and fairness, surprisingly there are only a few works in the intersection of voting and networks, and voting and fairness. We propose to comprehensively study the interplay and price of various fairness notions in the context of voting when we have a network on the voters or on the candidates or both. More specifically, we will focus on the key computational challenges arising at this crucial juncture of voting, networks, and fairness. |