Szczegóły publikacji
Opis bibliograficzny
Properties of position matrices and their elections / Niclas Boehmer, Jin-Yi Cai, Piotr FALISZEWSKI, Austen Z. Fan, Łukasz JANECZKO, Andrzej KACZMARCZYK, Tomasz WĄS // W: AAAI-23 [Dokument elektroniczny] : thirty-seventh AAAI conference on Artificial intelligence ; thirty-fifth conference on Innovative applications of artificial intelligence ; thirteenth symposium on Educational advances in artificial intelligence : February 7-14, 2023, Washington DC, USA / ed. by Brian Williams, Yiling Chen, Jennifer Neville. — Wersja do Windows. — Dane tekstowe. — Washington : Association for the Advancement of Artificial Intelligence, cop. 2023. — (Proceedings of the ... AAAI Conference on Artificial Intelligence ; ISSN 2159-5399 ; Vol. 37). — e-ISBN: 978-1-57735-880-0. — S. 5507–5514. — Wymagania systemowe: Adobe Reader. — Tryb dostępu: https://ojs.aaai.org/index.php/AAAI/article/view/25684/25456 [2023-07-04]. — Bibliogr. s. 5514, Abstr. — Publikacja dostępna online od: 2023-06-26. --- Opublikowane w części: AAAI-23 Technical Tracks 5. — T. Wąs – dod. afiliacja: Pennsylvania State University
Autorzy (7)
- Boehmer Niclas
- Cai Jin-Yi
- AGHFaliszewski Piotr
- Fan Austen Z.
- AGHJaneczko Łukasz
- AGHKaczmarczyk Andrzej
- AGHWąs Tomasz
Słowa kluczowe
Dane bibliometryczne
ID BaDAP | 147596 |
---|---|
Data dodania do BaDAP | 2023-07-26 |
DOI | 10.1609/aaai.v37i5.25684 |
Rok publikacji | 2023 |
Typ publikacji | materiały konferencyjne (aut.) |
Otwarty dostęp | |
Konferencje | Thirty-Seventh AAAI Conference on Artificial Intelligence, Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence |
Czasopismo/seria | Proceedings of the ... AAAI Conference on Artificial Intelligence |
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.