preflibtools.properties.subdomains.ordinal

Module for testing whether ordinal instances are part of some subdomains.

Single-Peaked Subdomains

is_single_peaked(instance)

Tests whether the instance describes a profile of single-peaked preferences. It only works with strict preferences.

This function implements the algorithm of Escoffier, Lang, and Ozturk (2008). We are grateful to Thor Yung Pheng who developed this function (under the supervision of Umberto Grandi).

Parameters:: instance (OrdinalInstance) – the instance to test for single-peakedness.
Returns:: A Boolean indicating whether the instance is single-peaked, together with the axis with respect to which the instance would be single-peaked, the empty list if the instance is not single-peaked.
Return type:: Tuple(bool, list)

is_single_peaked_ILP(instance)

Tests whether the instance describes a profile of single-peaked preferences. It also works if indifference is allowed (the property would then be single-plateaued).

This function implements the algorithm proposed by Bartholdi and Trick (1986). It first constructs the corresponding binary matrix and then uses an ILP solver to check whether the matrix has the consecutive ones property.

This code is inspired by that of Zack Fitzsimmons (zfitzsim@holycross.edu) and Martin Lackner (lackner@dbai.tuwien.ac.at), available at https://github.com/zmf6921/incompletesp.

Parameters:: instance (OrdinalInstance) – the instance to test for single-peakedness.
Returns:: A triple composed of a boolean variable indicating whether the instance is single-peaked or not, the python-mip optimisation status of the ILP model, and the axis for which the instance is single-peaked (None if the instance is not single-peaked).
Return type:: Tuple(bool, str, list)

is_single_peaked_axis(instance, axis)

Tests whether the instance is single-peaked with respect to the axis provided as argument.

Parameters:

instance (OrdinalInstance) – the instance to work on.
axis (list) – a list of candidates.

Returns:

A boolean indicating if the instance is single-peaked with respect to axis.

Return type:

bool

is_single_peaked_on_tree(instance: OrdinalInstance)

Function to detect whether or not the instance is single-peaked on a tree. Returns True and the tree on the set of alternatives such that the instance is single-peaked on this tree, if one exists. Based on Trick’s 1989 algorithm.

Args:: instance (OrdinalInstance): the preference data

is_single_peaked_pq_tree(instance)

Tests whether the instance describes a profile of single-peaked preferences using PQ trees.

Parameters:: instance (OrdinalInstance) – the instance to test for single-peakedness.
Returns:: A Boolean indicating whether the instance is single-peaked or not
Return type:: bool

k_alt_partition_approx(instance)

Approximates a profiles k-alternative partition single-peakedness by continuously creating the longest possible single-peaked axis among the remaining alternatives using the algorithm of Erdélyi, Lackner, Pfandler (2017).

Parameters:: instance (OrdinalInstance) – the instance to test for k-alternative deletion single-peakedness.
Returns:: A list containing the axes that the algorithm has created.
Return type:: list(list)

k_alternative_deletion(instance)

Generates the longest incomplete axis on which the given profile does not violate single-peakedness, thereby identifying the minimum number of alternatives that should be deleted in order for it to become single-peaked.

This function utilizes the algorithm of Erdélyi, Lackner, Pfandler (2017).

Parameters:: instance (OrdinalInstance) – the instance to test for k-alternative deletion single-peakedness.
Returns:: The longest incomplete axis on which the given instance is single-peaked, as well the alternatives missing from said axis that would need to be removed from the profile.
Return type:: Tuple(list, list)

k_alternative_partition_brut_force(instance, k)

Generates the lowest amount of partitions of the alternatives in a given profile such that when restricted to each partition, the profile is single-peaked. This is done by brute-forcing all admissible partitions in a DFS fashion.

Parameters:

instance (OrdinalInstance) – the instance to test for k-alternative deletion single-peakedness.
k (int) – The maximum number of partitions

Returns:

A list containing single-peaked axes representing the optimal partitions

Return type:

list(list)

two_axes_sp(instance)

Tests whether the collection of orders of the given instance can be split into two partitions such that each partition is itself a single-peaked instance. In other words, whether the given instance is 2-axes single-peaked. This function implements an algorithm of Yang (2020).

Parameters:: instance (OrdinalInstance) – the instance to test for 2-axes single-peakedness.
Returns:: whether the instance is 2-axes single-peaked, if that is the case, also provides the partitions as two lists of orders.
Return type:: tuple(bool, list)

Single-Crossing Subdomains

This module provides procedures to check if an instance describes preferences that are single-crossing.

is_single_crossing(instance: OrdinalInstance)

Check if the given instance is single-crossing based on the “Fast Recognition by Sorting” algorithm 4 presented in the paper “Preference Restrictions in Computational Social Choice: A Survey” (p. 55).

Parameters:: instance (OrdinalInstance) – The instance to take the orders from.
Returns:: A Boolean indicating whether the instance is single-crossing, together with the ordered preferences that demonstrates that the profile is single-crossing or None if the instance is not single-crossing.
Return type:: Tuple(bool, list)

is_single_crossing_conflict_sets(instance)

Tests whether the instance describe a profile of single-crossed preferences.

Parameters:: instance (OrdinalInstance) – The instance to take the orders from.
Returns:: A boolean indicating whether the instance is single-crossed or no.
Return type:: bool

1-Euclidean Subdomain

Euclidean domain for ordinal preferences.

is_one_euclidean(instance: OrdinalInstance)

Check if the given instance is in the 1-Euclidean domain.

Args:: instance (OrdinalInstance): the preference profile
Returns:: (Boolean, dict): True and the mapping of voters to alternatives if the instance is in the 1-Euclidean domain, False and None otherwise.