preflibtools.properties package
This package provides different modules to deal with properties of an instance.
preflibtools.properties.basic defines methods to check basic properties of instances.
preflibtools.properties.singlepeakedness provides different ways to investigate different single-peakedness properties of an instance.
preflibtools.properties.singlecrossing presents ways of testing if and instance is single-crossing.
preflibtools.properties.distances offers different distances that can be computed between instances.
preflibtools.properties.basic
This module describes several procedures to check for basic procedures of PrefLib instances.
- preflibtools.properties.basic.borda_scores(instance)
Computes the total Borda scores of all the alternatives of the instance. Within an indifference class, all alternatives are assigned the smallest score one alternative from the class would have gotten, had the order been strict. For instance, for the order ({a1}, {a2, a3}, {a4}), a1 gets score 3, a2 and a3 score 1 and a4 score 0.
- Parameters
instance (preflibtools.instance.preflibinstance.PreflibInstance) – The instance.
- Returns
A dictionary mapping every instance to their Borda score.
- Return type
dict
- preflibtools.properties.basic.has_condorcet(instance)
Checks whether the instance has a Condorcet winner, using different procedures depending on the data type of the instance. An alternative is a Condorcet winner if it strictly beats every other alternative in a pairwise majority contest.
- Parameters
instance (preflibtools.instance.preflibinstance.PreflibInstance) – The instance.
- Returns
A boolean indicating whether the instance has a Condorcet winner or not.
- Return type
bool
- preflibtools.properties.basic.is_approval(instance)
Checks whether the instance describes an approval profile. A profile is considered to represent approval ballots in two cases: All the orders are complete and consist of only two indifference classes; The orders are incomplete and consists of a single indifference class.
- Parameters
instance (preflibtools.instance.preflibinstance.PreflibInstance) – The instance.
- Returns
A boolean indicating whether the instance describes an approval profile.
- Return type
bool
- preflibtools.properties.basic.is_complete(instance)
Checks whether the instance describes a profile of complete preferences.
- Parameters
instance (preflibtools.instance.preflibinstance.PreflibInstance) – The instance.
- Returns
A boolean indicating whether the instance describes a profile of complete preferences.
- Return type
bool
- preflibtools.properties.basic.is_strict(instance)
Checks whether the instance describes a profile of strict preferences.
- Parameters
instance (preflibtools.instance.preflibinstance.PreflibInstance) – The instance.
- Returns
A boolean indicating whether the instance describes a profile of strict preferences.
- Return type
bool
- preflibtools.properties.basic.largest_ballot(instance)
Returns the size of the largest ballot of the instance, i.e., the maximum number of alternatives appearing in an order.
- Parameters
instance (preflibtools.instance.preflibinstance.PreflibInstance) – The instance.
- Returns
The size of the largest ballot of the instance.
- Return type
int
- preflibtools.properties.basic.largest_indif(instance)
Returns the size of the largest indifference class of any voter of the instance.
- Parameters
instance (preflibtools.instance.preflibinstance.PreflibInstance) – The instance.
- Returns
The size of the largest indifference class of the instance.
- Return type
int
- preflibtools.properties.basic.max_nb_indif(instance)
Returns the maximum number of indifference classes over the orders of the instance.
- Parameters
instance (preflibtools.instance.preflibinstance.PreflibInstance) – The instance.
- Returns
The maximum number of indifference classes of the instance.
- Return type
int
- preflibtools.properties.basic.min_nb_indif(instance)
Returns the minimum number of indifference classes over the orders of the instance.
- Parameters
instance (preflibtools.instance.preflibinstance.PreflibInstance) – The instance.
- Returns
The minimum number of indifference classes of the instance.
- Return type
int
- preflibtools.properties.basic.nb_alternatives(instance)
Returns the number of alternatives of the instance.
- Parameters
instance (preflibtools.instance.preflibinstance.PreflibInstance) – The instance.
- Returns
The number of alternatives of the instance.
- Return type
int
- preflibtools.properties.basic.nb_different_orders(instance)
Returns the number of different orders of the instance.
- Parameters
instance (preflibtools.instance.preflibinstance.PreflibInstance) – The instance.
- Returns
The number of different orders of the instance.
- Return type
int
- preflibtools.properties.basic.nb_voters(instance)
Returns the number of voters .
- Parameters
instance (preflibtools.instance.preflibinstance.PreflibInstance) – The instance.
- Returns
The number of voters of the instance.
- Return type
int
- preflibtools.properties.basic.smallest_ballot(instance)
Returns the size of the smallest ballot of the instance, i.e., the smallest number of alternatives appearing in an order.
- Parameters
instance (preflibtools.instance.preflibinstance.PreflibInstance) – The instance.
- Returns
The size of the smallest ballot of the instance.
- Return type
int
- preflibtools.properties.basic.smallest_indif(instance)
Returns the size of the smallest indifference class of any voter of the instance.
- Parameters
instance (preflibtools.instance.preflibinstance.PreflibInstance) – The instance.
- Returns
The size of the smallest indifference class of the instance.
- Return type
int
- preflibtools.properties.basic.sum_vote_count(instance)
Returns the sum of the vote count of the instance.
- Parameters
instance (preflibtools.instance.preflibinstance.PreflibInstance) – The instance.
- Returns
The sum of vote count of the instance.
- Return type
int
preflibtools.properties.singlepeakedness
This module provides procedures to deal with the potential single-peakedness of the instance.
- preflibtools.properties.singlepeakedness.approx_SP_alternative_deletion_ILP(instance)
Uses an ILP solver to compute how close to single-peakedness an instance, where closeness is measured as the smallest number of alternatives to remove for the instance to be single-peaked.
- Parameters
instance (preflibtools.instance.preflibinstance.PreflibInstance) – the instance to work on.
- Returns
A quadruple composed of the number of alternatives that have been removed for the instance to be single-peaked, the python-mip optimisation status of the ILP model, the axis for which the instance is single-peaked, and the list of alternatives that have been removed.
- Return type
Tuple(bool, str, list, list)
- preflibtools.properties.singlepeakedness.approx_SP_voter_deletion_ILP(instance, weighted=False)
Uses an ILP solver to compute how close to single-peakedness an instance, where closeness is measured as the smallest number of voter to remove for the instance to be single-peaked.
- Parameters
instance (preflibtools.instance.preflibinstance.PreflibInstance) – the instance to work on.
weighted – a boolean indicating if orders in the instance should have a weight of 1 in the ILP optimization (the default case), or if the weight should be the number of voters having submitted the order.
- Returns
A quadruple composed of the number of voters that have been removed for the instance to be single-peaked, the python-mip optimisation status of the ILP model, the axis for which the instance is single-peaked, and the list of voters that have been removed.
- Return type
Tuple(bool, str, list, list)
- preflibtools.properties.singlepeakedness.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 (preflibtools.instance.preflibinstance.PreflibInstance) – the instance to test for single-peakedness.
- Returns
The axis with respect to which the instance would be single-peaked, the empty list if the instance is not single-peaked.
- Return type
list
- preflibtools.properties.singlepeakedness.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 (preflibtools.instance.preflibinstance.PreflibInstance) – 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)
- preflibtools.properties.singlepeakedness.is_single_peaked_axis(instance, axis)
Tests whether the instance is single-peaked with respect to the axis provided as argument.
- Parameters
instance (preflibtools.instance.preflibinstance.PreflibInstance) – 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
- preflibtools.properties.singlepeakedness.sp_ILP_cons_ones_alt_del_cstr(model, left_of_vars, alt_vars, instance)
A helper function for computing the closeness to single-peakedness of and instance with an ILP solver. Adds the single-peakedness constraints to the ILP model given as parameter, allowing to ignore some alternatives if needed. These constraints enforce that the instance is indeed single-peaked with respect to the axis constructed for the non-ignored alternatives. They actually implement the consecutive ones property of the binary matrix corresponding to the instance.
- Parameters
model – The ILP model, should be an instance of the python-mip Model class.
left_of_vars – A list of list of python-mip variables where leftOfVars[a1][a2] is set to 1 if and only if a1 is to the left of a2 in the axis.
alt_vars – A list of list of python-mip variables where altVars[a] is set to 1 if and only if alternative a is removed from consideration.
instance – the instance to test for single-peakedness.
- preflibtools.properties.singlepeakedness.sp_ILP_cons_ones_cstr(model, left_of_vars, instance)
A helper function for testing single-peakedness with an ILP solver. Adds the single-peakedness constraints to the ILP model given as parameter. These constraints enforce that the instance is indeed single-peaked with respect to the axis constructed. They actually implement the consecutive ones property of the binary matrix corresponding to the instance.
- Parameters
model – The ILP model, should be an instance of the python-mip Model class.
left_of_vars – A list of list of python-mip variables where leftOfVars[a1][a2] is set to 1 if and only if a1 is to the left of a2 in the axis.
instance – the instance to test for single-peakedness.
- preflibtools.properties.singlepeakedness.sp_ILP_cons_ones_vot_del_cstr(model, left_of_vars, voter_vars, instance)
A helper function for computing the closeness to single-peakedness of and instance with an ILP solver. Adds the single-peakedness constraints to the ILP model given as parameter, allowing to ignore some voters if needed. These constraints enforce that the instance is indeed single-peaked with respect to the axis constructed for the non-ignored voters. They actually implement the consecutive ones property of the binary matrix corresponding to the instance.
- Parameters
model – The ILP model, should be an instance of the python-mip Model class.
left_of_vars – A list of list of python-mip variables where leftOfVars[a1][a2] is set to 1 if and only if a1 is to the left of a2 in the axis.
voter_vars – A list of list of python-mip variables where votersVars[v] is set to 1 if and only if voter v is removed from consideration.
instance (preflibtools.instance.preflibinstance.PreflibInstance) – the instance to test for single-peakedness.
- preflibtools.properties.singlepeakedness.sp_ILP_pos_cstr(model, left_of_vars, pos_vars, instance)
A helper function for testing single-peakedness with an ILP solver. Adds the position constraints to the ILP model given as parameter. These constraints enforce the position variables to follow the order defined by the left-of variables.
- Parameters
model – The ILP model, should be an instance of the python-mip Model class.
left_of_vars – A list of list of python-mip variables where leftOfVars[a1][a2] is set to 1 if and only if alternative a1 is to the left of alternative a2 in the axis.
pos_vars – A list of list of python-mip variables where posVar[a1] indicates the position of alternative a1 in the axis.
instance – the instance to test for single-peakedness.
- preflibtools.properties.singlepeakedness.sp_ILP_total_cstr(model, left_of_vars, instance)
A helper function for testing single-peakedness with an ILP solver. Adds the totality constraints to the ILP model given as parameter. These constraints encode that the axis constructed is total.
- Parameters
model – The ILP model, should be an instance of the python-mip Model class.
left_of_vars – A list of list of python-mip variables where leftOfVars[a1][a2] is set to 1 if and only if a1 is to the left of a2 in the axis.
instance – the instance to test for single-peakedness.
- preflibtools.properties.singlepeakedness.sp_ILP_trans_cstr(model, left_of_vars, instance)
A helper function for testing single-peakedness with an ILP solver. Adds the transitivity constraints to the ILP model given as parameter. These constraints encode that the axis constructed is transitive.
- Parameters
model – The ILP model, should be an instance of the python-mip Model class.
left_of_vars – A list of list of python-mip variables where leftOfVars[a1][a2] is set to 1 if and only if a1 is to the left of a2 in the axis.
instance – the instance to test for single-peakedness.
- preflibtools.properties.singlepeakedness.sp_cons_ones_matrix(instance)
Returns a binary matrix such that the instance is single-peaked if and only if the matrix has the consecutive ones property. This is an helper function to implement the algorithm proposed by Bartholdi and Trick (1986) to deal with single-peakedness.
- Parameters
instance (preflibtools.instance.preflibinstance.PreflibInstance) – the instance to test for single-peakedness.
- Returns
A binary matrix
- Return type
numpy array
preflibtools.properties.singlecrossing
This module provides procedures to check if an instance describes preferences that are single-crossing.
- preflibtools.properties.singlecrossing.is_single_crossing(instance)
Tests whether the instance describe a profile of single-crossed preferences.
- Parameters
instance (preflibtools.instance.preflibinstance.PreflibInstance) – The instance to take the orders from.
- Returns
A boolean indicating whether the instance is single-crossed or no.
- Return type
bool
preflibtools.properties.distances
This module provides functions to compute distances between orders.
- preflibtools.properties.distances.distance_matrix(instance, distance_function)
Returns a matrix of the pairwise distance between all orders of the instance.
- Parameters
instance (preflibtools.instance.preflibinstance.PreflibInstance) – The instance to take the orders from.
distance_function (function) – The distance function to use. It should take two orders as input.
- Returns
A Numpy array of the pairwise distances, coordinates being the index of the orders in the order list of the instance.
- Return type
numpy array
- preflibtools.properties.distances.kendall_tau_distance(order1, order2)
Returns the Kendall’s tau distance between two orders.
- Parameters
order1 (tuple) – The first order.
order2 (tuple) – The second order.
- Returns
The Kendall’s tau distance between the two orders.
- Return type
int
- preflibtools.properties.distances.sertel_distance(order1, order2)
Returns the Sertel’s distance between two orders.
- Parameters
order1 (tuple) – The first order.
order2 (tuple) – The second order.
- Returns
The Sertel’s distance between the two orders.
- Return type
float
- preflibtools.properties.distances.spearman_footrule_distance(order1, order2)
Returns the Spearman’s footrule distance between two orders.
- Parameters
order1 (tuple) – The first order.
order2 (tuple) – The second order.
- Returns
The Spearman’s footrule distance between the two orders.
- Return type
float