Implementation of the consecutive-ones approach for determining if a given preference profile of incomplete votes is (possibly) single-peaked. The algorithm is described in "Incomplete Preferences in Single-Peaked Electorates" by Zack Fitzsimmons and Martin Lackner (https://arxiv.org/abs/1907.00752). The resulting consecutive ones instance is solved via a SAT solver. This is a much simpler and more reliable approach than implementing the available linear-time algorithms (such as PQ-trees, Lex-BFS, etc.) and still yields very fast runtimes.
- PreflibTools version 1.5 (https://github.com/nmattei/PrefLib-Tools)
- python-sat version 0.1.5.dev6 (https://pysathq.github.io/)
python3 weakordersp.py profile.toc N
where profile.toc is a preference profile in the tied-order complete format used by the PrefLib repository (www.preflib.org) and N is one of the following values.
- 0 to check if
profile.tocdescribes a possibly single-peaked profile. - 1 to check if
profile.tocdescribes a single-plateaued profile. - 2 to check if
profile.tocdescribes a Black single-peaked profile.
Four example preference profiles in the tied-order complete format used by PrefLib are included in the "examples" directory.
possibly-sp.tocis possibly single-peaked but not single-plateaued or Black single-peakedsingle-plateaued.tocis single-plateaued and so also possibly single-peaked.Black-sp.tocis Black single-peaked and so also single-plateaued and possibly single-peaked.none.tocis not possibly single-peaked, single-plateaued, or Black single-peaked.
For a given input profile profile.toc, the output is four comma-separated values: the input profile filename, the number of candidates in the profile, the number of voters in the profile, and True if the given restriction is satisfied (False otherwise).
For example, testing the possibly-sp.toc profile with the command
python3 weakordersp.py examples/possibly-sp.toc 0
results in the following output:
examples/possibly-sp.toc,6,4,True
This profile is possibly single-peaked.