Properties of Position Matrices and Their Elections
Niclas Boehmer, Jin-Yi Cai, Piotr Faliszewski, Austen Z. Fan, Łukasz Janeczko, Andrzej Kaczmarczyk, Tomasz Wąs
Abstract
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.
BibTeX
@article{Boehmer_Cai_Faliszewski_Fan_Janeczko_Kaczmarczyk_Wąs_2023, title={Properties of Position Matrices and Their Elections}, volume={37}, url={https://ojs.aaai.org/index.php/AAAI/article/view/25684}, DOI={10.1609/aaai.v37i5.25684}, abstractNote={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.}, number={5}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Boehmer, Niclas and Cai, Jin-Yi and Faliszewski, Piotr and Fan, Austen Z. and Janeczko, Łukasz and Kaczmarczyk, Andrzej and Wąs, Tomasz}, year={2023}, month={Jun.}, pages={5507-5514} }