Properties of Position Matrices and Their Elections

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 electi...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2023-03
Main Authors: Boehmer, Niclas, Jin-Yi, Cai, Faliszewski, Piotr, Fan, Austen Z, Janeczko, Łukasz, Kaczmarczyk, Andrzej, Wąs, Tomasz
Format: Article
Language:English
Subjects:
Algorithms
Elections
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422