Preference Elicitation for Single Crossing Domain

Palash Dey, Neeldhara MisraIJCAI 2016

Introduction

In multiagent systems and social choice theory, eliciting the preferences of $n$ voters over $m$ candidates is a fundamental but computationally expensive task. Without structural assumptions, each voter has $m!$ possible rankings, and eliciting these preferences through pairwise comparisons typically requires $\Omega(m \log m)$ queries per voter. For large populations, the total cost of $\Omega(nm \log m)$ queries becomes prohibitively high.

However, real-world preferences often exhibit specific structures. This paper focuses on the single crossing domain, where voters can be arranged in an order such that for any two candidates $x$ and $y$, the voters who prefer $x$ over $y$ appear consecutively. This research provides the first comprehensive set of algorithms and complexity bounds for reconstructing preference profiles within this domain.

Methodology

The authors investigate the problem across two primary dimensions: the level of prior knowledge regarding the voter ordering and the method of accessing voter data.

Access Models and Knowledge

  1. Knowledge of Voter Order: The algorithms distinguish between cases where the specific ordering that makes the profile single crossing is known versus unknown.
  2. Access Model: The research considers Random Access (querying any voter at any time) and Sequential Access (processing voters as they arrive one by one).

Algorithmic Techniques

  • Binary Search over Voters: If the voter order is known, the "crossing point" where preferences flip between two candidates can be found efficiently using binary search across the sequence of voters.
  • Amortized Insertion Sort: A specialized insertion sort (Algorithm 1) leverages the fact that preferences change gradually in a single crossing profile. By using a "nearby" preference as a starting point, the cost of positioning a candidate is amortized across the profile.
  • Search-and-Verify: For unknown orders, the algorithm (Algorithm 4) maintains a set of unique preferences. Since a single crossing profile contains at most $\binom{m}{2} + 1$ distinct rankings (Lemma 3), new voters can often be matched to existing rankings before resorting to full elicitation.

Key Results

The paper establishes tight upper and lower bounds for query complexity, demonstrating that the single crossing property allows for elicitation with complexity often close to $O(mn)$. This is a significant improvement over the naive $O(nm \log m)$ required for unrestricted preferences.

Summary of query complexity bounds for preference elicitation in single crossing domains.

A crucial structural insight (Lemma 3) is that in a single crossing profile, there are at most $O(m^2)$ distinct preferences, regardless of the number of voters $n$. This massive reduction from $m!$ is what enables such efficient elicitation. Furthermore, the authors proved lower bounds showing that for most settings, it is mathematically impossible to significantly outperform their proposed algorithms.

Conclusion and Future Work

This work provides a robust theoretical foundation for preference elicitation in structured domains. While the results are near-optimal, several avenues for future research remain:

  • Closing the Gap: In the "Known Order, Random Access" case, a factor of $m$ gap remains between the upper and lower bounds ($m^2$ vs $m$).
  • Robustness: Real-world data is often "noisy." Developing algorithms that can handle profiles that are only "nearly" single crossing is a vital next step.
  • Communication Complexity: Beyond query counts, exploring the total bits of information exchanged could provide further insights into the efficiency of these mechanisms.

Summary updated

BibTeX
@inproceedings{dey2016preference,
  author = {Palash Dey and Neeldhara Misra},
  title = {{Preference Elicitation for Single Crossing Domain}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure