Spatial Voting with Incomplete Voter Information


  • Aviram Imber Technion – Israel Institute of Technology
  • Jonas Israel Technische Universität Berlin
  • Markus Brill University of Warwick Technische Universität Berlin
  • Hadas Shachnai Technion – Israel Institute of Technology
  • Benny Kimelfeld Technion – Israel Institute of Technology



GTEP: Social Choice / Voting


We consider spatial voting where candidates are located in the Euclidean d-dimensional space, and each voter ranks candidates based on their distance from the voter's ideal point. We explore the case where information about the location of voters' ideal points is incomplete: for each dimension, we are given an interval of possible values. We study the computational complexity of finding the possible and necessary winners for positional scoring rules. Our results show that we retain tractable cases of the classic model where voters have partial-order preferences. Moreover, we show that there are positional scoring rules under which the possible-winner problem is intractable for partial orders, but tractable in the one-dimensional spatial setting. We also consider approval voting in this setting. We show that for up to two dimensions, the necessary-winner problem is tractable, while the possible-winner problem is hard for any number of dimensions.




How to Cite

Imber, A., Israel, J., Brill, M., Shachnai, H., & Kimelfeld, B. (2024). Spatial Voting with Incomplete Voter Information. Proceedings of the AAAI Conference on Artificial Intelligence, 38(9), 9790-9797.



AAAI Technical Track on Game Theory and Economic Paradigms