Properties of Position Matrices and Their Elections


  • Niclas Boehmer Algorithmics and Computational Complexity, Technische Universität Berlin
  • Jin-Yi Cai University of Wisconsin-Madison
  • Piotr Faliszewski AGH University
  • Austen Z. Fan University of Wisconsin-Madison
  • Łukasz Janeczko AGH University
  • Andrzej Kaczmarczyk AGH University
  • Tomasz Wąs AGH University Pennsylvania State University



GTEP: Social Choice / Voting


We study the properties of elections that have a given position matrix (in such elections each candidate is ranked on each position by a number of voters specified in the matrix). We show that counting elections that generate a given position matrix is #P-complete. Consequently, sampling such elections uniformly at random seems challenging and we propose a simpler algorithm, without hard guarantees. Next, we consider the problem of testing if a given matrix can be implemented by an election with a certain structure (such as single-peakedness or group-separability). Finally, we consider the problem of checking if a given position matrix can be implemented by an election with a Condorcet winner. We complement our theoretical findings with experiments.




How to Cite

Boehmer, N., Cai, J.-Y., Faliszewski, P., Fan, A. Z., Janeczko, Łukasz, Kaczmarczyk, A., & Wąs, T. (2023). Properties of Position Matrices and Their Elections. Proceedings of the AAAI Conference on Artificial Intelligence, 37(5), 5507-5514.



AAAI Technical Track on Game Theory and Economic Paradigms