אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

Elections are a fundamental mechanism for collective decision-making. Yet in many real-world settings, the available information is often incomplete, inconsistent, or uncertain. This thesis addresses this challenge by developing computational frameworks for analyzing election outcomes under various forms of uncertainty. Our work builds upon the established paradigm of possible and necessary winners, where the goal is to determine which candidates could or must win given partially ordered voter preferences. We advance and broaden this line of inquiry by exploring novel models of incomplete information and new forms of uncertainty across different voting contexts.

First, we generalize the classic possible/necessary winner problem to the problem of computing the minimal and maximal ranks a candidate can possibly obtain. We show that these problems are fundamentally harder than the standard possible/necessary winner problem. Next, we extend the analysis to multi-winner committee selection, proposing new models for incomplete information tailored to approval-based voting. Within these models, we analyze the computational complexity of determining possible and necessary committees. In the third part, we adapt the possible/necessary winner framework to spatial voting, where uncertainty arises from partial information about the positions of voters and candidates in a multidimensional ideological space, rather than from partial preference orders. Within this model we reveal new tractability results. Finally, we move from possibilistic to probabilistic uncertainty. In this setting, voter preferences are fully known, but voter participation is stochastic. We analyze the complexity of computing and approximating the probability of a candidate’s victory.