2023/03/05 by Niclas Boehmer, Jin‐Yi Cai, Boehmer, Niclas +11 · 1 citation
Economics, Econometrics and Finance · Decision Sciences · Computer Science · #Game Theory and Voting Systems #Auction Theory and Applications #Complexity and Algorithms in Graphs
paper · pdf · doi:10.48550/arxiv.2303.02538
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.