Properties of Position Matrices and Their Elections
N. Boehmer, J.-Y. Cai, P. Faliszewski, A. Z. Fan, L. Janeczko, A. Kaczmarczyk, T. Wąs
AAAI 2023
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.
Experiments:
| Election type |
Culture |
Candidates |
Voters |
Instances |
Parameters |
| Ordinal |
Euclidean 1D |
{8} |
{80} |
4000 |
Uniform 1D {[0,1]} |
| Ordinal |
Euclidean 2D |
{8} |
{80} |
4000 |
Uniform 2D ($[0,1]^2$) |
| Ordinal |
Euclidean 3D-or-more |
{8} |
{80} |
4000 |
Uniform 3D ($[0,1]^3$); Uniform 5D ($[0,1]^5$); Uniform 10D ($[0,1]^10$); Uniform 20D ($[0,1]^20$); Uniform 2D Sphere ($(0, 0)$ $r=1$); Uniform 3D Sphere ($(0, 0)$ $r=1$); Uniform 5D Sphere ($(0, 0)$ $r=1$) |
| Ordinal |
Group-Separable |
{8} |
{80} |
4000 |
None |
| Ordinal |
Impartial Culture |
{8} |
{80} |
4000 |
None |
| Ordinal |
Mallows |
{8} |
{80} |
4000 |
For the 80 elections generated using the urn model and
the normalized Mallows model, we followed the protocol
of Boehmer et al. [2021b, 2022b]. Hence, for each of the
elections generated with the normalized Mallows Model,
we drew the value of rel-$\phi$ uniformly at random from the
[0, 1] interval. |
| Ordinal |
Single-Crossing |
{8} |
{80} |
4000 |
None |
| Ordinal |
Single-Peaked (Conitzer/Random Peak) |
{8} |
{80} |
4000 |
None |
| Ordinal |
Single-Peaked (Walsh/Uniform) |
{8} |
{80} |
4000 |
None |
| Ordinal |
Urn Model |
{8} |
{80} |
4000 |
The parameter for the urn model elections
was drawn according to the Gamma distribution with the
shape parameter k = 0.8 and the scale parameter $\theta =
1$. |
| Ordinal |
Euclidean 1D |
{4} |
{16} |
20 |
Uniform 1D {[0,1]} |
| Ordinal |
Euclidean 2D |
{4} |
{16} |
20 |
Uniform 2D ($[0,1]^2$) |
| Ordinal |
Euclidean 3D-or-more |
{4} |
{16} |
20 |
Uniform 3D ($[0,1]^3$); Uniform 5D ($[0,1]^5$); Uniform 10D ($[0,1]^10$); Uniform 20D ($[0,1]^20$); Uniform 2D Sphere ($(0, 0)$ $r=1$); Uniform 3D Sphere ($(0, 0)$ $r=1$); Uniform 5D Sphere ($(0, 0)$ $r=1$) |
| Ordinal |
Group-Separable |
{4} |
{16} |
20 |
None |
| Ordinal |
Impartial Culture |
{4} |
{16} |
20 |
None |
| Ordinal |
Mallows |
{4} |
{16} |
20 |
For the 80 elections generated using the urn model and
the normalized Mallows model, we followed the protocol
of Boehmer et al. [2021b, 2022b]. Hence, for each of the
elections generated with the normalized Mallows Model,
we drew the value of rel-$\phi$ uniformly at random from the
[0, 1] interval. |
| Ordinal |
Single-Crossing |
{4} |
{16} |
20 |
None |
| Ordinal |
Single-Peaked (Conitzer/Random Peak) |
{4} |
{16} |
20 |
None |
| Ordinal |
Single-Peaked (Walsh/Uniform) |
{4} |
{16} |
20 |
None |
| Ordinal |
Urn Model |
{4} |
{16} |
20 |
The parameter for the urn model elections
was drawn according to the Gamma distribution with the
shape parameter k = 0.8 and the scale parameter $\theta =
1$. |
| Ordinal |
Euclidean 1D |
{8} |
{80} |
20 |
Uniform 1D {[0,1]} |
| Ordinal |
Euclidean 2D |
{8} |
{80} |
20 |
Uniform 2D ($[0,1]^2$) |
| Ordinal |
Euclidean 3D-or-more |
{8} |
{80} |
20 |
Uniform 3D ($[0,1]^3$); Uniform 5D ($[0,1]^5$); Uniform 10D ($[0,1]^10$); Uniform 20D ($[0,1]^20$); Uniform 2D Sphere ($(0, 0)$ $r=1$); Uniform 3D Sphere ($(0, 0)$ $r=1$); Uniform 5D Sphere ($(0, 0)$ $r=1$) |
| Ordinal |
Group-Separable |
{8} |
{80} |
20 |
None |
| Ordinal |
Impartial Culture |
{8} |
{80} |
20 |
None |
| Ordinal |
Mallows |
{8} |
{80} |
20 |
For the 80 elections generated using the urn model and
the normalized Mallows model, we followed the protocol
of Boehmer et al. [2021b, 2022b]. Hence, for each of the
elections generated with the normalized Mallows Model,
we drew the value of rel-$\phi$ uniformly at random from the
[0, 1] interval. |
| Ordinal |
Single-Crossing |
{8} |
{80} |
20 |
None |
| Ordinal |
Single-Peaked (Conitzer/Random Peak) |
{8} |
{80} |
20 |
None |
| Ordinal |
Single-Peaked (Walsh/Uniform) |
{8} |
{80} |
20 |
None |
| Ordinal |
Urn Model |
{8} |
{80} |
20 |
The parameter for the urn model elections
was drawn according to the Gamma distribution with the
shape parameter k = 0.8 and the scale parameter $\theta =
1$. |