Preflibtools

Welcome to the documentation for the Preflibtools package, a set of tools to work with preference data from the PrefLib.org website.

Overview

This package provides input and output operations on PrefLib instances, together with some additional functionalities on the instances: Testing whether a Condorcet winner exists, whether the instance is single-peaked, etc…

We developed this package in the hope of making the use of PrefLib instances easy. This has been done in the same spirit as PrefLib: Providing tools for the community with the help of the community. The code for this package is hosted in the PrefLib-Tools GitHub repository. If you want to contribute, feel free to create pull requests. If you have a question, a remark, or encounter a problem, please open an issue in the GitHub repository.

The full documentation of the package can be found at the following URL: http://www.docs.preflib.org.

Ordinal Preferences Example

In the following, we present the typical use of the package when dealing with preferences submitted as orders.

We start by initializing a PrefLib instance. It can be populated either by reading a file, or by using one of the sampling method we provide.

from preflibtools.instances.preflibinstance import PreflibInstance

# Either the instance is populated by reading a file from PrefLib
instance = PreflibInstance()
instance.parse("ED-00001-00000001.toc")

# Or by sampling preferences from one of the statistical culture we provide
instance = PreflibInstance()
instance.populateMallowsMixture(5, 10, 5)

Once the instance has been initialised, we can perform operations on it. Let’s start simply with accessing the information of the instance.

# The type of the instance
instance.dataType
# The number of alternatives and their names
instance.nbAlternatives
for alt, altName in instance.alternativesName.items():
        alternative = alt
        name = altName
# The number of voters
instance.nbVoters
# The sum of vote count
instance.sumVoteCount
# The number of different orders that have been submitted
instance.nbDifferentOrders
# The orders together with their multiplicity
for o in instance.orders:
        order = o
        multiplicity = instance.nbEachOrder(order)

We represent orders as tuples of tuples (we need them to be hashable), i.e., it is a vector of sets of alternatives where each set represents an indifference class for the voter. Here are some examples of orders.

# The strict and complete order 1 > 2 > 0
strictOrder = ((1,), (2,), (0,))
# The weak and complete order (1, 2) > 0 > (3, 4)
weakOrder = ((1, 2), (0,), (3, 4))
# The incomplete an weak order (1, 2) > 4
incompleteOrder = ((1, 2), (4,))

Now that we know how orders are represented, we can see some example of how to handle orders within the instance.

# Adding preferences to the instance, using different formats
# Simply a list of orders
extraOrders = [((0,), (1,), (2,)), ((2,), (0,), (1,))]
instance.appendOrderList(orders)
# A vote map, i.e., a dictionary mapping orders to their multiplicity
extraVoteMap = {((0,), (1,), (2,)): 3, ((2,), (0,), (1,)): 2}
instance.appendVoteMap(voteMap)

# We can access the full profile, i.e., with orders appearing several times
# (according to their multiplicity)
instance.fullProfile()

# If we are dealing with strict orders, we can flatten the orders so that ((0,), (1,), (2,))
# is rewritten as (0, 1, 2). This return a list of tuple(order, multiplicity).
instance.flattenStrictOrders()

# We can access the profile as a vote map
instance.voteMap()

We have now played around with the orders in the instance, maybe we feel like saving it into a file.

# Writing the instance into a file, the file type is automatically added
instance.write("myNewInstance")

To finish, we may want to test some properties of the instance. Let’s start with some basic ones.

from preflibtools.properties.basic import bordaScores, hasCondorcet

# Let's check the Borda scores of the alternatives
bordaScores(instance)
# We can also check if the instance has a Condorcet winner
hasCondorcet(instance)

The are plenty of methods to check for the potential single-peakedness of the instance.

from preflibtools.properties.singlepeakedness import isAxisSinglePeaked, isSinglePeaked
from preflibtools.properties.singlepeakedness import isSinglePeakedILP
from preflibtools.properties.singlepeakedness import approxSPVoterDeletionILP
from preflibtools.properties.singlepeakedness import approxSPAlternativeDeletionILP

# We can first check if the instance is single-peaked with respect to a given
# axis. This only works for complete orders, they can be weak though.
isSP = isAxisSinglePeaked(instance, [0, 1, 2])
# In general we can test for the single-peakedness of the instance:
# In the case of strict and complete orders;
(isSP, axis) = isSinglePeaked(instance)
# And in the case of weak and complete order (using an ILP solver).
(isSP, optimalityStatus axis) = isSinglePeakedILP(instance)

# Maybe the instance is not single-peaked, but approximately. We can check how close to
# single-peaked it is in terms of voter deletion and alternative deletion.
(nbVoterDeleted, optStatus, axis, deletedVoters) = approxSPVoterDeletionILP(instance)
(nbAltDeleted, optStatus, axis, deletedAlts) = approxSPAlternativeDeletionILP(instance)

We can also look into single-crossing.

from preflibtools.properties.singlecrossing import isSingleCrossing

# Testing if the instance is single-crossing
isSingleCrossing(instance)

Finally, we can talk about distances between the orders of the instance.

from preflibtools.properties.distances import distanceMatrix, spearmanFootruleDistance
from preflibtools.properties.distances import kendallTauDistance,  sertelDistance

# We can create the distance matrix between any two orders of the instance
distanceMatrix(instance, kendallTauDistance)
distanceMatrix(instance, spearmanFootruleDistance)
distanceMatrix(instance, sertelDistance)

Requirements

This package requires some other packages to function properly:

  • numpy: to deal with array and math-related functions (random generator, factorial, etc…)

  • mip: to deal with optimisation problems (for instance closeness to single-peakedness).

  • matplotlib: to create images of the instances.

  • networkx: to draw images of instances representing graphs.

Modules

The package provides different modules. The first set of them deal with PrefLib instances.

  • preflibtools.instances.preflibinstance: provides the main class used to represent PrefLib instances together with a very basic graph class.

  • preflibtools.instances.sampling: provides all kinds of methods to sample preferences using different kinds of Mallows’ models and urn model’s.

  • preflibtools.instances.drawing: provides the function to create images from PrefLib instances. These are used to illustrate the instances in PrefLib.org.

See the documentation of the corresponding preflibtools.instances package.

A second set of modules introduces functions to test properties of PrefLib instances.

  • preflibtools.properties.basic: provides a lot of small functions testing very basic properties (number of agents, size of the largest ballot…) that are mainly used for sanity checks.

  • preflibtools.properties.singlepeakedness: provides a set of function to test whether instances represent single-peaked preferences, and related properties (closeness to single-peakedness etc…).

  • preflibtools.properties.distances: provides a set of distances that can be computed between instances.

See the documentation of the corresponding preflibtools.properties package.

Index

The general index can be found here.