# Structure in Dichotomous Preferences

arXiv: https://arxiv.org/abs/1505.00341 · HTML: https://mlsanity.com/paper/1505.00341/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 May 2015.

## Built on by (most cited first, 7 of 7)

- [Temporal Fairness in Multiwinner Voting](https://mlsanity.com/paper/2312.04417/) (2023)
- [DiRe Committee : Diversity and Representation Constraints in Multiwinner Elections](https://mlsanity.com/paper/2107.07356/) (2021)
- [Core-Stable Committees under Restricted Domains](https://mlsanity.com/paper/2108.01987/) (2021)
- [Polynomial-Time Algorithm for Thiele Voting Rules with Voter Interval Preferences](https://mlsanity.com/paper/2604.05953/) (2026)
- [Computing Thiele Rules on Interval Elections and their Generalizations](https://mlsanity.com/paper/2605.03067/) (2026)
- [Bandits with Single-Peaked Preferences and Limited Resources](https://mlsanity.com/paper/2510.09425/) (2025)
- [Algorithms for Structured Elections under Thiele Voting Rules](https://mlsanity.com/paper/2607.28575/) (2026)

## Abstract (arXiv)

Many hard computational social choice problems are known to become tractable when voters' preferences belong to a restricted domain, such as those of single-peaked or single-crossing preferences. However, to date, all algorithmic results of this type have been obtained for the setting where each voter's preference list is a total order of candidates. The goal of this paper is to extend this line of research to the setting where voters' preferences are dichotomous, i.e., each voter approves a subset of candidates and disapproves the remaining candidates. We propose several analogues of the notions of single-peaked and single-crossing preferences for dichotomous profiles and investigate the relationships among them. We then demonstrate that for some of these notions the respective restricted domains admit efficient algorithms for computationally hard approval-based multi-winner rules.