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_pq_tree(instance)
- 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)
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