When modeling human preferences, our first instinct is often to design fine-grained, multi-point scales. We ask users to rate movies from 1 to 5 stars, or we ask agents in economic models to strictly rank their choices from most to least preferred. Intuitively, more data should yield better outcomes.
However, this granularity comes at a steep mathematical and computational cost. In multi-agent systems—such as matching markets, coalition formation, and group recommendation—complex ordinal rankings frequently lead to computational intractability (NP-hardness) or, worse, mathematical impossibility, where no stable or optimal solution exists at all.
A powerful alternative is dichotomous preference modeling. By collapsing an agent's utility into a binary choice—approval or disapproval, accept or reject, like or dislike—we radically transform the underlying mathematical landscape. This simplification eliminates preference cycles, guarantees the existence of stable outcomes, and drastically reduces the computational complexity of finding them, all while retaining enough informational signal to make high-quality decisions.
Guaranteeing Stability in Coalition Formation
To understand why binary preferences are so powerful, consider hedonic games, where agents split themselves into coalitions (groups) based on who else is in their group. In a standard hedonic game with ranked preferences, a "core-stable" partition—a grouping where no sub-group has an incentive to defect and form their own coalition—is not guaranteed to exist. The complex interplay of rankings can create cyclic dependencies reminiscent of the Condorcet paradox in voting theory.
When we restrict preferences to a binary format, this barrier vanishes. In Boolean Hedonic Games, Haris Aziz et al. demonstrate that when agents have dichotomous preferences—meaning they are either fully satisfied or unsatisfied based on whether their propositional goals are met—a core-stable partition is mathematically guaranteed to exist. Because preferences are binary, the search for an optimal partition can be framed as a maximum satisfiability (MaxSAT) problem, allowing standard propositional logic tools to resolve group configurations efficiently.
Dominik Peters expanded on this in Complexity of Hedonic Games with Dichotomous Preferences, proving that this restriction fundamentally tames the preference space. By reducing choices to simple "Yes/No" responses over potential coalitions, finding stable partitions shifts from an intractable combinatorial nightmare into a problem space solvable via polynomial-time combinatorial optimization techniques.
This stability guarantee extends to assigning agents to specific tasks. In the Group Activity Selection Problem (GASP), introduced by Andreas Darmann et al., agents choose activities based on the activity type and the size of the resulting group. While the general problem with weak order preferences is highly complex, the authors show that an approval-based variant (a-GASP) simplifies the problem by letting agents simply accept or reject specific (activity, group size) pairs. Building on this framework, Vittorio Bilò et al. showed that when preferences are restricted to binary or unitary weights, the socially optimal outcome is guaranteed to be Nash stable, and agents can efficiently reach this assignment through iterative, individual improvements.
Taming Complexity in Matching and Diversity
The computational benefits of dichotomous preferences become even more pronounced when agents care about complex group compositions or external relationships.
Consider the problem of forming teams based on diversity ratios (e.g., balancing junior and senior project members). In Stable Roommate Problem with Diversity Preferences, Niclas Boehmer et al. analyze scenarios where agents care about the ratio of agent types in their room. While finding stable allocations for multi-person rooms is generally NP-hard under ranked preferences, modeling utility as binary approval or disapproval of specific ratios ensures that core-stable outcomes always exist and can be computed in polynomial time. Furthermore, in Individual-Based Stability in Hedonic Diversity Games, the authors prove that for any two-class game based on group ratios, an individually stable outcome is guaranteed to exist and can be found using a straightforward polynomial-time algorithm, even when preferences are not single-peaked.
Ranked Preferences (Ordinal) Dichotomous Preferences (Binary)
[Agent A: Group 1 > 2 > 3] [Agent A: Group 1 & 2 (OK), 3 (No)]
[Agent B: Group 2 > 3 > 1] [Agent B: Group 2 & 3 (OK), 1 (No)]
[Agent C: Group 3 > 1 > 2] [Agent C: Group 3 & 1 (OK), 2 (No)]
│ │
▼ ▼
Potential Cyclic Traps Guaranteed Core Stability
(No Stable Partition) (Overlap = Group 2 is OK)
Binary preferences also resolve the challenges of externalities—situations where an agent's happiness depends on the outcomes of others. In The Dichotomous Affiliate Stable Matching Problem, Marina Knittel et al. study matching markets where organizations care about where their affiliates end up. While externalities usually break traditional matching algorithms, the authors show that substituting complex ordinal rankings with a binary system of mutual interest allows stable solutions to be recovered in polynomial time.
The Informational Sufficiency of Binary Signals
If dichotomous preferences make algorithms run faster and guarantee stability, do they sacrifice too much accuracy? Evidence from recommendation and dialogue systems suggests they do not.
In collaborative filtering, we often assume that fine-grained ratings (like a 1-to-5 star scale) are necessary to capture user tastes. However, in Boolean Matrix Factorization and Noisy Completion via Message Passing, Siamak Ravanbakhsh et al. demonstrate that simple binary representations of user preferences capture nearly as much information for recommendation tasks as full ordinal scales. The underlying structure of collaborative filtering is effectively driven by basic logical relationships rather than fine-grained numerical values.
This principle is highly practical in real-world applications where user attention is scarce:
- Reducing Interaction Friction: In Cinemappy: a Context-aware Mobile App for Movie Recommendations boosted by DBpedia, Vito Claudio Ostuni et al. observe that mobile users naturally default to binary behavior—either giving the highest possible rating or leaving no feedback at all. A binary mechanism aligns with actual user behavior and minimizes cognitive load.
- Leveraging Semantic Data: In a companion paper on content-based recommender systems, Vito Claudio Ostuni et al. show that a simple binary "like/dislike" rating system is entirely sufficient for mapping user preferences to semantic graphs (such as DBpedia), achieving competitive recommendation quality without complex data modeling.
- Streamlining Conversational AI: In Modeling Spoken Decision Making Dialogue and Optimization of its Dialogue Strategy, Hideki Kashioka et al. simplify user preference models into binary parameters representing only interest or lack thereof. This allows a reinforcement learning agent to optimize its dialogue strategy efficiently, guiding users through complex decisions without needing to track continuous utility functions.
By shifting from continuous or ranked utilities to dichotomous preferences, researchers across algorithmic game theory and machine learning exploit a shared truth: collapsing preferences into a binary signal eliminates mathematical friction, unlocks strong stability guarantees, and drastically reduces computational complexity, all while preserving the core information needed to make optimal decisions.
Key Foundational Work
Group Activity Selection Problem (2012) — contributed 2 concept elements to this direction.
Linked open data to support content-based recommender systems (2012) — contributed 2 concept elements to this direction.
Cinemappy: a Context-aware Mobile App for Movie Recommendations boosted by DBpedia (2012) — contributed 1 concept elements to this direction.