# Learning Combinatorial Functions from Pairwise Comparisons

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

## Key facts

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

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

- [Eliciting User Preferences for Personalized Multi-Objective Decision Making through Comparative Feedback](https://mlsanity.com/paper/2302.03805/) (2023)
- [PAC learning and stabilizing Hedonic Games: towards a unifying approach](https://mlsanity.com/paper/2301.13756/) (2023)
- [What Does Preference Learning Recover from Pairwise Comparison Data?](https://mlsanity.com/paper/2602.10286/) (2026)
- [Deep Submodular Peripteral Networks](https://mlsanity.com/paper/2403.08199/) (2024)
- [Reward Learning from Best-of-N Preference Data: Targets, Tradeoffs, and Design Principles](https://mlsanity.com/paper/2605.30619/) (2026)
- [Sorting from Counterexamples](https://mlsanity.com/paper/2608.21579/) (2026)
- [Dueling Bandits with Team Comparisons](https://mlsanity.com/paper/2107.02738/) (2021)

## Abstract (arXiv)

A large body of work in machine learning has focused on the problem of learning a close approximation to an underlying combinatorial function, given a small set of labeled examples. However, for real-valued functions, cardinal labels might not be accessible, or it may be difficult for an expert to consistently assign real-valued labels over the entire set of examples. For instance, it is notoriously hard for consumers to reliably assign values to bundles of merchandise. Instead, it might be much easier for a consumer to report which of two bundles she likes better. With this motivation in mind, we consider an alternative learning model, wherein the algorithm must learn the underlying function up to pairwise comparisons, from pairwise comparisons. In this model, we present a series of novel algorithms that learn over a wide variety of combinatorial function classes. These range from graph functions to broad classes of valuation functions that are fundamentally important in microeconomic theory, the analysis of social networks, and machine learning, such as coverage, submodular, XOS, and subadditive functions, as well as functions with sparse Fourier support.