singlepeakedness

This module provides procedures to deal with the potential single-peakedness of the instance.

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 (OrdinalInstance) – 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)

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 (OrdinalInstance) – 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)

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

sp_ILP_cons_ones_alt_del_cstr(model, left_of_vars, alt_vars, instance, alt_map)

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.

  • alt_map (dict[_, int]) – a mapping from alternative name to range(0, m).

sp_ILP_cons_ones_cstr(model, left_of_vars, instance, alt_map)

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.

  • alt_map (dict[_, int]) – a mapping from alternative name to range(0, m).

sp_ILP_cons_ones_vot_del_cstr(model, left_of_vars, voter_vars, instance, alt_map)

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 (OrdinalInstance) – the instance to test for single-peakedness.

  • alt_map (dict[_, int]) – a mapping from alternative name to range(0, m).

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.

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.

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.

sp_cons_ones_matrix(instance, alt_map)

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 (OrdinalInstance) – the instance to test for single-peakedness.

  • alt_map (dict[_, int]) – a mapping from alternative name to range(0, m).

Returns:

A binary matrix

Return type:

numpy array