Single-Peaked Models#

Single-peaked preferences capture the idea that there exists a societal axis on which the candidates can be placed in such a way that the preferences of the voters are decreasing along both sides of the axis from their most preferred candidate.

single_peaked_conitzer(num_voters: int, num_candidates: int, seed: int = None) → ndarray[source]#

Generates ordinal votes that are single-peaked following the distribution defined by Conitzer (2009). The preferences generated are single-peaked with respect to the axis 0, 1, 2, …. Votes are generated uniformly at random as follows. The most preferred candidate (the peak) is selected uniformly at random. Then, either the candidate on the left, or the one on the right of the peak comes second in the ordering. Each case occurs with probability 0.5. The method is then iterated for the next left and right candidates (only one of them being different from before).

This method ensures that the probability for a given candidate to be the peak is uniform (as opposed to the method single_peaked_walsh()). The probability for a single-peaked rank to be generated is equal to 1/m * (1/2)**dist_peak_to_end where m is the number of candidates and dist_peak_to_end is the minimum distance from to peak to an end of the axis (i.e., candidates 0 or m - 1).

A collection of num_voters vote is generated independently and identically following the process described above.

Parameters:

num_voters (int) – Number of Voters.
num_candidates (int) – Number of Candidates.
seed (int) – Seed for numpy random number generator.

Returns:

Ordinal votes.

Return type:

np.ndarray

Examples

from prefsampling.ordinal import single_peaked_conitzer

# Sample a single-peaked profile via Conitzer's method with 2 voters and 3 candidates.
single_peaked_conitzer(2, 3)

# For reproducibility, you can set the seed.
single_peaked_conitzer(2, 3, seed=1002)

Validation

Following the method proposed by Contizer, the probability of observing a given single-peaked ranking (for a fixed axis) with $m$ candidates is equal to:

$\frac{1}{m} \times \left(\frac{1}{2}\right)^{\text{dist\_peak\_to\_end}}$

where $\text{dist\_peak\_to\_end}$ is the minimum distance from the top candidate to one of the end of the axis (i.e., candidates 0 or m - 1).

Observed versus theoretical frequencies for Conitzer's single-peaked model with m=4

Observed versus theoretical frequencies for Conitzer's single-peaked model with m=5

Observed versus theoretical frequencies for Conitzer's single-peaked model with m=6

References

Eliciting single-peaked preferences using comparison queries, Vincent Conitzer, Journal of Artificial Intelligence Research, 35:161–191, 2009.

single_peaked_walsh(num_voters: int, num_candidates: int, seed: int = None) → ndarray[source]#

Generates ordinal votes that are single-peaked following the process described by Walsh (2015). The votes are generated from least preferred to most preferred candidates. A given position in the ordering is filled by selecting, with uniform probability, either the leftmost or the rightmost candidates that have not yet been positioned in the vote (left and right being defined by the axis 0, 1, 2, …).

A collection of num_voters vote is generated independently and identically following the process described above.

Parameters:

num_voters (int) – Number of Voters.
num_candidates (int) – Number of Candidates.
seed (int) – Seed for numpy random number generator.

Returns:

Ordinal votes.

Return type:

np.ndarray

Examples

from prefsampling.ordinal import single_peaked_walsh

# Sample a single-peaked profile via Walsh's method with 2 voters and 3 candidates.
single_peaked_walsh(2, 3)

# For reproducibility, you can set the seed.
single_peaked_walsh(2, 3, seed=1002)

Validation

The method proposed by Walsh ensures that for a given axis, all single-peaked rankings are equally likely to be generated.

Observed versus theoretical frequencies for Walsh's single-peaked model with m=4

Observed versus theoretical frequencies for Walsh's single-peaked model with m=5

Observed versus theoretical frequencies for Walsh's single-peaked model with m=6

References

Generating Single Peaked Votes, Toby Walsh, ArXiV preprint, 2015.

single_peaked_circle(num_voters: int, num_candidates: int, seed: int = None) → ndarray[source]#

Generates ordinal votes that are single-peaked on a circle following a distribution inspired from the one by Conitzer (2009) for single-peakedness on a line (see single_peaked_conitzer()). This method starts by determining the most preferred candidate (the peak). This is done with uniform probability over the candidates. Then, subsequent positions in the ordering are filled by taking either the next available candidate on the left or on the right, both cases occuring with probability 0.5. Left and right are defined here in terms of the circular axis: 0, 1, …, m, 1.

A collection of num_voters vote is generated independently and identically following the process described above.

Parameters:

num_voters (int) – Number of Voters.
num_candidates (int) – Number of Candidates.
seed (int) – Seed for numpy random number generator.

Returns:

Ordinal votes.

Return type:

np.ndarray

Examples

from prefsampling.ordinal import single_peaked_circle

# Sample a single-peaked on a circle profile with 2 voters and 3 candidates.
single_peaked_circle(2, 3)

# For reproducibility, you can set the seed.
single_peaked_circle(2, 3, seed=1002)

Validation

The sampler for single-peaked on a circle is such that all single-peaked on a circle rankings are equally likely to be generated.

Observed versus theoretical frequencies for single-peaked on a circle model with m=4

Observed versus theoretical frequencies for single-peaked on a circle model with m=5

Observed versus theoretical frequencies for single-peaked on a circle model with m=6

References

Preferences Single-Peaked on a Circle, Dominik Peters and Martin Lackner, Journal of Artificial Intelligence Research, 68:463–502, 2020.

Single-Peaked Models

Contents

Single-Peaked Models#