preflibtools.properties package

This package provides different modules to deal with properties of an instance.

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