Ordinal Distances

agg_voterlikeness_distance(election_1: ~mapof.elections.objects.OrdinalElection.OrdinalElection, election_2: ~mapof.elections.objects.OrdinalElection.OrdinalElection, inner_distance: callable) -> (<class 'float'>, <class 'list'>)

Compute Aggregated-Voterlikeness distance between ordinal elections

blank_distance(election_1: ~mapof.elections.objects.OrdinalElection.OrdinalElection, election_2: ~mapof.elections.objects.OrdinalElection.OrdinalElection) -> (<class 'int'>, <class 'list'>)

Computes blank distance for testing purposes.

bordawise_distance(election_1: ~mapof.elections.objects.OrdinalElection.OrdinalElection, election_2: ~mapof.elections.objects.OrdinalElection.OrdinalElection, inner_distance: callable) -> (<class 'float'>, None)

Computes Bordawise distance between ordinal elections.

Parameters:

• election_1 (OrdinalElection) – First election to compare.

• election_2 (OrdinalElection.) – Second election to compare.

• inner_distance (callable) – Inner distance to use.

Returns:

Bordawise distance between the two elections.

Return type:

(float, list | None)

discrete_distance(election_1: ~mapof.elections.objects.OrdinalElection.OrdinalElection, election_2: ~mapof.elections.objects.OrdinalElection.OrdinalElection) -> (<class 'int'>, <class 'list'>)

Computes Discrete distance between elections

get_matching_cost_pos_swap(election_1: OrdinalElection, election_2: OrdinalElection, matching) → list[list]

Return: Cost table

get_matching_cost_positionwise(election_1: OrdinalElection, election_2: OrdinalElection, inner_distance: callable) → list[list]

Return: Cost table

get_matching_cost_swap_bf(election_1: OrdinalElection, election_2: OrdinalElection, mapping)

Return: Cost table

get_matching_cost_truncated_swap_bf(election_1: OrdinalElection, election_2: OrdinalElection, mapping)

Return: Cost table

pairwise_distance(election_1: ~mapof.elections.objects.OrdinalElection.OrdinalElection, election_2: ~mapof.elections.objects.OrdinalElection.OrdinalElection, inner_distance: callable) -> (<class 'float'>, None)

Compute Pairwise distance between ordinal elections.

Parameters:

• election_1 (OrdinalElection) – First election to compare.

• election_2 (OrdinalElection.) – Second election to compare.

• inner_distance (callable) – Inner distance to use.

Returns:

Pairwise distance between the two elections.

Return type:

(float, None)

pos_swap_distance(election_1: ~mapof.elections.objects.OrdinalElection.OrdinalElection, election_2: ~mapof.elections.objects.OrdinalElection.OrdinalElection, inner_distance: callable) -> (<class 'float'>, <class 'list'>)

Compute Positionwise-Swap distance between ordinal elections

positionwise_distance(election_1, election_2, inner_distance: callable) -> (<class 'float'>, <class 'list'>)

Compute Positionwise distance between ordinal elections.

Parameters:

• election_1 (OrdinalElection) – First election to compare.

• election_2 (OrdinalElection) – Second election to compare.

• inner_distance (callable) – Inner distance to use.

Returns:

Positionwise distance between the two elections and the optimal matching.

Return type:

(float, list)

spearman_distance(election_1: ~mapof.elections.objects.OrdinalElection.OrdinalElection, election_2: ~mapof.elections.objects.OrdinalElection.OrdinalElection) -> (<class 'int'>, <class 'list'>)

Compute Spearman distance between elections (using the C++ extension)

spearman_distance_fastmap(election_1: OrdinalElection, election_2: OrdinalElection, method: str = 'aa') → tuple[int, list | None]

Computes Isomorphic Spearman distance between elections using fastmap library.

Args:

election_1: First ordinal election. election_2: Second ordinal election. method: Method used to compute the distance. Should be one of the

“bf” - uses brute-force to solve the equivalent Bilinear Assignment Problem (BAP).

Generates all permutations σ of the set {0,..,min(nv-1,nc-1)} using Heap’s algorithm and for each generated permutation σ solves the Linear Assignment Problem (LAP) to obtain the optimal permutation v of {0,..,max(nv-1,nc-1)}. Time complexity of this method is O(min(nv,nc)! * max(nv,nc)**3)

NOTE: This method returns exact value but if one of the nv, nc is greater than 10 it is extremely slow.

“aa” - implements Alternating Algorithm heuristic described in arXiv:1707.07057

which solves the equivalent Bilinear Assignment Problem (BAP). The algorithm first generates a feasible solution to the BAP by sampling from a uniform distribution two permutations σ, v and then performs a coordinate-descent-like refinment by interchangeably fixing one of the permutations, solving the corresponding Linear Assignment Problem (LAP) and updating the other permutation with the matching found in LAP, doing so until convergence. Time complexity of this method is O(N * (nv**3 + nc**3)) where N is the number of iterations it takes for the algorithm to converge.

NOTE: This method is much faster in practice than “bf” but there are no theoretical guarantees on the approximation ratio for the used heuristic.

“bb” - implements Branch-and-Bound algorithm to solve exactly the equivalent

Bilinear Assigmnent Problem (BAP).

NOTE: Performance of this method highly depends on the cultures from which the elections were sampled. In the worst case scenario it may be significantly slower than “bf”. Also due to the implemented bounding function this method is not suited for instances with more than few dozen voters.

Raises:

ImportError: Raises exception if fastmap module is not found.

Returns:

Tuple of Isomorphic Spearman distance value and None.

spearman_distance_ilp_py(election_1: ~mapof.elections.objects.OrdinalElection.OrdinalElection, election_2: ~mapof.elections.objects.OrdinalElection.OrdinalElection) -> (<class 'int'>, <class 'list'>)

Computes Spearman distance between elections

swap_distance(election_1: ~mapof.elections.objects.OrdinalElection.OrdinalElection, election_2: ~mapof.elections.objects.OrdinalElection.OrdinalElection) -> (<class 'int'>, <class 'list'>)

Compute swap distance between elections (using the C++ extension)

swap_distance_bf(election_1: ~mapof.elections.objects.OrdinalElection.OrdinalElection, election_2: ~mapof.elections.objects.OrdinalElection.OrdinalElection) -> (<class 'int'>, <class 'list'>)

Compute swap distance between elections via brute force, in Python. This is mostly as a fallback to the C++ implementation, which might ocassionally be unavailable for some due to envorinoment issues (lack of proper tools under MS Windows, old compilers, etc.)

truncated_swap_distance(election_1: ~mapof.elections.objects.OrdinalElection.OrdinalElection, election_2: ~mapof.elections.objects.OrdinalElection.OrdinalElection) -> (<class 'int'>, <class 'list'>)

Compute truncated swap distance between elections

voterlikeness_distance(election_1: ~mapof.elections.objects.OrdinalElection.OrdinalElection, election_2: ~mapof.elections.objects.OrdinalElection.OrdinalElection, inner_distance: callable) -> (<class 'float'>, <class 'list'>)

Compute Voterlikeness distance between elections.

Parameters:

• election_1 (OrdinalElection) – First election to compare.

• election_2 (OrdinalElection.) – Second election to compare.

• inner_distance (callable) – Inner distance to use.

Returns:

Voterlikeness distance between the two elections.

Return type:

(float, None)