ML Anthology

Properties of Position Matrices and Their Elections

Niclas Boehmer, Jin-Yi Cai, Piotr Faliszewski, Austen Z. Fan, Lukasz Janeczko, Andrzej Kaczmarczyk, Tomasz Was
AAAI 2023 pp. 5507-5514
doi:10.1609/AAAI.V37I5.25684 /aaai/2023/boehmer2023aaai-properties/

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.

PDF AAAI Semantic Scholar

Cite

Text

Boehmer et al. "Properties of Position Matrices and Their Elections." AAAI Conference on Artificial Intelligence, 2023. doi:10.1609/AAAI.V37I5.25684

Markdown

[Boehmer et al. "Properties of Position Matrices and Their Elections." AAAI Conference on Artificial Intelligence, 2023.](https://mlanthology.org/aaai/2023/boehmer2023aaai-properties/) doi:10.1609/AAAI.V37I5.25684

BibTeX

@inproceedings{boehmer2023aaai-properties,
  title     = {{Properties of Position Matrices and Their Elections}},
  author    = {Boehmer, Niclas and Cai, Jin-Yi and Faliszewski, Piotr and Fan, Austen Z. and Janeczko, Lukasz and Kaczmarczyk, Andrzej and Was, Tomasz},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2023},
  pages     = {5507-5514},
  doi       = {10.1609/AAAI.V37I5.25684},
  url       = {https://mlanthology.org/aaai/2023/boehmer2023aaai-properties/}
}