The Taub Faculty of Computer Science Events and Talks

A central task in social choice is that of aggregating voter preferences to decide who wins. For this task, a voting rule maps a collection of voter preferences over the candidates to a set of winning candidates. Relevant scenarios may be political elections, document rankings in search engines, hiring dynamics in the job market, and so on. We study situations in which voter preferences are incomplete. These scenarios arise naturally in a variety of practical settings: voters may be undecided about some candidates, new candidates can be introduced, and the information can be retrieved from indirect sources such as social media.

We analyze the complexity of some fundamental computational problems in such settings. In our first work, we study the task of computing the minimal and maximal ranks that a candidate can obtain, given partial voting preferences. In our second work, we study the problem of computing the probability of winning in an election where voter attendance is random. In our third work, we introduce several models of incomplete votes for approval-based committee (ABC) voting. We study the problems of determining whether a given set of candidates is a possible or necessary winning committee. In our fourth work, we consider spatial voting, where candidates and voters are located in the Euclidean space, and each voter ranks candidates based on their distance from the voter's position. We study the problems of finding the possible and necessary winners given incomplete information about the voter's position.