Single-Peakedness¶

Functions to analyze single-peakedness of preference profiles.

A preference profile is single-peaked with respect to an axis (linear order over the candidates) if every voter has a unique most-preferred candidate (peak) and the voter’s preferences decrease monotonically in both directions from the peak along the axis.

A profile is k-maverick single-peaked with respect to an axis if all but k voters are single-peaked with respect to that axis. The minimum k over all axes measures how far the profile is from being single-peaked.

Reference: Faliszewski, Hemaspaandra & Hemaspaandra (2014), “The complexity of manipulative attacks in nearly single-peaked electorates”, Artificial Intelligence 207, 69-99. DOI

Checking Single-Peakedness of Individual Rankings¶

pref_voting.single_peakedness.is_single_peaked(ranking, axis, num_cands=None, treat_truncated_as_maverick=False, tied_ranking_handling='maverick')[source]¶

Check if a ranking is single-peaked with respect to the given axis.

This function accepts either a list (a linear ranking, as used with Profile) or a Ranking object (as used with ProfileWithTies), and automatically handles complete, truncated, and tied rankings.

Parameters:

ranking (list or Ranking) – The voter’s ranking. If a list, it should contain candidates from most preferred to least preferred (a linear order, possibly truncated). If a Ranking object, ties and truncation are detected automatically.
axis (list or tuple) – Candidates in the left-to-right axis order.
num_cands (int or None) – Total number of candidates in the election. Required when ranking is a Ranking object, to detect whether the ranking is truncated. Ignored when ranking is a list (in which case len(axis) is used).
treat_truncated_as_maverick (bool) – If True, voters who don’t rank all candidates are counted as mavericks. If False (default), truncated rankings are checked for compatibility with single-peakedness (ranked candidates must form a contiguous segment of the axis and be single-peaked on that segment).
tied_ranking_handling (str) – How to handle rankings with ties (only relevant when ranking is a Ranking object with ties). One of 'maverick' (default), 'possibly_sp', 'single_plateaued', 'black_sp'. See module docstring for details.

Returns:

True if the ranking is single-peaked-compatible with respect to the axis.

Return type:

bool

Examples:

With a list (linear ranking from a Profile):

>>> from pref_voting.single_peakedness import is_single_peaked

>>> is_single_peaked([1, 0, 2], [0, 1, 2])
True
>>> is_single_peaked([0, 2, 1], [0, 1, 2])
False

With a Ranking object (from a ProfileWithTies):

>>> from pref_voting.rankings import Ranking
>>> from pref_voting.single_peakedness import is_single_peaked

>>> # Linear ranking: 0 > 1 > 2
>>> is_single_peaked(Ranking({0: 1, 1: 2, 2: 3}), [0, 1, 2], num_cands=3)
True
>>> # Weak order with tie: {0, 1} > 2
>>> is_single_peaked(Ranking({0: 1, 1: 1, 2: 2}), [0, 1, 2], num_cands=3,
...                  tied_ranking_handling='possibly_sp')
True

Profile-Level Analysis¶

Counting Mavericks¶

pref_voting.single_peakedness.num_mavericks(profile, axis, treat_truncated_as_maverick=False, tied_ranking_handling='maverick')[source]¶

Count the number of voters whose rankings are NOT single-peaked with respect to the given axis.

Parameters:

profile (Profile or ProfileWithTies) – The preference profile.
axis (list or tuple) – Candidates in the left-to-right axis order.
treat_truncated_as_maverick (bool) – If True, voters who don’t rank all candidates are counted as mavericks. If False (default), truncated rankings are checked for compatibility with single-peakedness (ranked candidates must form a contiguous segment of the axis and be single-peaked on that segment).
tied_ranking_handling (str) – How to handle rankings with ties. One of 'maverick' (default), 'possibly_sp', 'single_plateaued', 'black_sp'. See module docstring for details.

Returns:

The number of maverick voters.

Return type:

int

Example:

from pref_voting.profiles import Profile
from pref_voting.single_peakedness import num_mavericks

prof = Profile([[0, 1, 2], [1, 0, 2], [1, 2, 0], [2, 1, 0], [0, 2, 1]])
# 0 > 2 > 1 is not single-peaked on axis [0, 1, 2]
num_mavericks(prof, [0, 1, 2])  # returns 1

Finding the Minimum k¶

pref_voting.single_peakedness.min_k_maverick_single_peaked(profile, treat_truncated_as_maverick=False, tied_ranking_handling='maverick')[source]¶

Find the minimum k such that the profile is k-maverick single-peaked with respect to some ordering of the candidates.

This function iterates over all possible axes (permutations of candidates) and returns the axis that minimizes the number of maverick voters. An axis and its reverse are equivalent for single-peakedness, so only half of the permutations are checked.

Suitable for small numbers of candidates (up to about 8).

Parameters:

profile (Profile or ProfileWithTies) – The preference profile.
treat_truncated_as_maverick (bool) – If True, voters who don’t rank all candidates are counted as mavericks. If False (default), truncated rankings are checked for compatibility.
tied_ranking_handling (str) – How to handle rankings with ties. One of 'maverick' (default), 'possibly_sp', 'single_plateaued', 'black_sp'. See module docstring for details.

Returns:

(min_k, best_axis, sp_profile) where min_k (int) is the minimum number of mavericks, best_axis (list) is an axis achieving it, and sp_profile is the anonymized sub-profile of non-maverick voters (a Profile if the input is a Profile, a ProfileWithTies if the input is a ProfileWithTies, or None if all voters are mavericks).

Return type:

tuple

Example:

from pref_voting.profiles import Profile
from pref_voting.single_peakedness import min_k_maverick_single_peaked

prof = Profile([[0, 1, 2], [1, 0, 2], [1, 2, 0], [2, 1, 0], [0, 2, 1]])
min_k, best_axis, sp_prof = min_k_maverick_single_peaked(prof)
# min_k = 1, best_axis = [0, 1, 2], sp_prof has 4 voters

References

Faliszewski, Hemaspaandra & Hemaspaandra (2014), “The complexity of manipulative attacks in nearly single-peaked electorates”, Artificial Intelligence 207, 69-99. https://doi.org/10.1016/j.artint.2013.11.004