PaperlayerView exact revision on arXiv

Source-linked AI summary

Eliciting Single-Peaked Preferences Using Comparison Queries

Vincent Conitzer

arXiv:1401.3449v1cs.GT

TL;DR

The paper addresses the difficulty of eliciting complete preferences for voting when alternatives are numerous. It develops comparison-query methods for single-peaked preferences and shows that query complexity depends on whether ordinal or cardinal positions are known. The results establish linear or logarithmic upper bounds in structured settings, while unknown positions impose sublinear lower bounds and almost-single-peaked preferences require separate treatment.

  • Problem

    Eliciting complete preferences is impractical for many alternatives, while unrestricted preferences can require sorting-scale comparison queries.

  • Method

    The paper studies elicitation of single-peaked and cardinally single-peaked preferences using comparison queries, including settings with known or unknown alternative positions.

  • Results

    Single-peaked preferences can be elicited with O(m) queries under known ordinal positions or one known agent, and cardinally single-peaked preferences with known cardinal positions require at most 2⌈log(m)⌉ queries, whereas unknown positions require sublinear lower bounds.

  • Takeaways & Limitations

    Structural restrictions on preferences can reduce the queries needed for complete elicitation, but unknown positions substantially limit these savings even when only the aggregate ranking is required.

  • Takeaways & Limitations

    The known-cardinal-position algorithm uses midpoints and does not scale computationally to extremely large numbers of alternatives.

Abstract

from arXiv · show

Voting is a general method for aggregating the preferences of multiple agents. Each agent ranks all the possible alternatives, and based on this, an aggregate ranking of the alternatives (or at least a winning alternative) is produced. However, when there are many alternatives, it is impractical to simply ask agents to report their complete preferences. Rather, the agents preferences, or at least the relevant parts thereof, need to be elicited. This is done by asking the agents a (hopefully small) number of simple queries about their preferences, such as comparison queries, which ask an agent to compare two of the alternatives. Prior work on preference elicitation in voting has focused on the case of unrestricted preferences. It has been shown that in this setting, it is sometimes necessary to ask each agent (almost) as many queries as would be required to determine an arbitrary ranking of the alternatives. In contrast, in this paper, we focus on single-peaked preferences. We show that such preferences can be elicited using only a linear number of comparison queries, if either the order with respect to which preferences are single-peaked is known, or at least one other agents complete preferences are known. We show that using a sublinear number of queries does not suffice. We also consider the case of cardinally single-peaked preferences. For this case, we show that if the alternatives cardinal positions are known, then an agents preferences can be elicited using only a logarithmic number of queries; however, we also show that if the cardinal positions are not known, then a sublinear number of queries does not suffice. We present experimental results for all elicitation algorithms. We also consider the problem of only eliciting enough information to determine the aggregate ranking, and show that even for this more modest objective, a sublinear number of queries per agent does not suffice for known ordinal or unknown cardinal positions. Finally, we discuss whether and how these techniques can be applied when preferences are almost single-peaked.

1. Introduction

The introduction motivates preference elicitation for collective decisions and focuses on single-peaked preferences as a structured alternative to unrestricted rankings. It explains their relevance, benefits for aggregation, and challenges when preferences deviate from the model.

  • 1. Introduction: Aggregating conflicting agents’ preferences can produce either a winning alternative or a complete compromise ranking.The paper frames voting as a method for making joint decisions over plans, allocations, representatives, and other alternatives.
  • 1. Introduction: Unrestricted preferences can create Condorcet cycles, making pairwise outcomes inconsistent with any aggregate ranking.This motivates interest in preference restrictions that preserve more tractable aggregation properties.
  • 1. Introduction: Single-peaked preferences rank alternatives according to positions on a common line, with preferences declining away from an agent’s peak.The model is especially plausible when alternatives’ positions, such as political ideology or numerical values, primarily determine preferences.
  • 1. Introduction: With single-peaked preferences, pairwise majority outcomes have no Condorcet cycles, and with an odd number of agents they determine the aggregate ranking without ties.Truthful reporting is also a dominant strategy when agents simultaneously report complete preferences under this restriction.
  • 1. Introduction: Complete preference elicitation is impractical for large alternative sets because it requires substantial communication and agents must determine their full rankings.Comparison queries offer a sequential way to learn preferences, with goals including finding a winner, determining the aggregate ranking, or recovering every complete preference order.
  • 1. Introduction: The paper studies comparison-query elicitation of complete single-peaked preferences, while noting that forcing or expecting single-peakedness can be problematic when preferences are multidimensional or only approximately single-peaked.The authors distinguish complete elicitation from determining only the winner or aggregate ranking and discuss robustness to deviations from the model.

2. Related Research and the Case of Unrestricted Preferences

The paper situates its contribution within voting and preference-elicitation research, then establishes unrestricted preference elicitation as a sorting problem. This baseline requires Θ(m log m) comparisons, contrasting with the paper’s linear elicitation result for single-peaked preferences.

  • 2. Related Research and the Case of Unrestricted Preferences: Earlier voting-elicitation research primarily sought enough information to determine a winner without restricting the space of possible preferences.Prior work also examined elicitation complexity, query selection, and strategic misreporting.
  • 2. Related Research and the Case of Unrestricted Preferences: Fully eliciting arbitrary preferences over m alternatives is equivalent to sorting m elements, requiring O(m log m) comparisons and Ω(m log m) comparisons in the worst case.The lower bound follows from the m! possible rankings and the information needed to distinguish them.
  • 2. Related Research and the Case of Unrestricted Preferences: For some voting rules, even deciding whether an alternative wins requires Ω(nm log m) communicated bits when preferences are unrestricted.The cited rules include Borda, Copeland, and Ranked Pairs.
  • 2. Related Research and the Case of Unrestricted Preferences: Restricting preferences to single-peaked orders allows complete elicitation using O(m) comparison queries, after which any voting rule can be executed.The contrast shows why structural assumptions can substantially reduce elicitation burden.

3. Eliciting Ordinally Single-Peaked Preferences

Ordinally single-peaked preferences can be elicited with a linear number of comparison queries, whether alternative positions are known or one complete vote is available instead. Sublinear query complexity is impossible, while unknown positions require learning across agents.

  • 3.1 Eliciting with Knowledge of Alternatives’ Ordinal Positions: m −2 + ⌈log m⌉ comparison queries suffice to determine an agent’s preferences when alternative positions are known.The algorithm binary-searches for the peak and then adds alternatives to the ranking with at most m −2 further queries.
  • 3.1 Eliciting with Knowledge of Alternatives’ Ordinal Positions: A linear number of queries is necessary with known positions because single-peaked rankings can encode (m −1)/2 independent bits.Each comparison query communicates only one bit, yielding the lower bound.
  • 3.2 Eliciting without Knowledge of Alternatives’ Ordinal Positions: Without known positions, the first agent may require Ω(m log m) queries, so domain learning must occur while eliciting multiple agents.Any ranking is single-peaked with respect to some positions; after the first vote, some possible positionings are eliminated, but many remain.
  • 3.2 Eliciting without Knowledge of Alternatives’ Ordinal Positions: Knowing one agent’s complete preferences suffices to elicit another agent’s preferences using at most 4m −6 comparison queries without knowing alternative positions.The procedure finds the new peak, identifies alternatives between the two peaks, and integrates them into the known vote’s structure.
  • 3.2 Eliciting without Knowledge of Alternatives’ Ordinal Positions: The 4m −6 bound combines peak finding, between-peak discovery, and integration costs, each bounded linearly in the number of alternatives.The proof sums these stage-wise bounds as (m −1) + (m −2) + (m −2) + (m −1).

4. Eliciting Cardinally Single-Peaked Preferences

With known alternative cardinal positions, cardinally single-peaked preferences can be elicited efficiently by binary-searching midpoints; without those positions, linear-scale elicitation is unavoidable.

  • 4. Eliciting Cardinally Single-Peaked Preferences: Cardinally single-peaked preferences form a strict subset of ordinally single-peaked preferences.The paper gives a preference profile consistent with a common ordinal order but inconsistent with any assignment of cardinal positions.
  • 4.1 Eliciting with Knowledge of Alternatives’ Cardinal Positions: Binary search compares alternatives across midpoints to determine whether the agent’s position lies to the left or right of each midpoint.The resulting interval between adjacent midpoints is sufficient to reconstruct the complete preference ranking.
  • 4.1 Eliciting with Knowledge of Alternatives’ Cardinal Positions: 2⌈log(m)⌉ comparison queries suffice to determine one agent’s preferences when alternative cardinal positions are known.The algorithm locates the agent’s position between adjacent midpoints and sorts alternatives by distance from that position.
  • 4.1 Eliciting with Knowledge of Alternatives’ Cardinal Positions: The known-position algorithm trades low elicitation cost for computational work that does not scale to extremely large numbers of alternatives.It must store and manage all alternative midpoints, although the paper emphasizes that query cost is often more restrictive than computation.
  • 4.1 Eliciting with Knowledge of Alternatives’ Cardinal Positions: The logarithmic query bound is asymptotically tight because identifying one favorite among m alternatives requires Ω(log m) communicated bits.This lower bound holds even when the agent’s position coincides with an alternative and communication is unrestricted.
  • 4.2 Eliciting without Knowledge of Alternatives’ Cardinal Positions: Without known alternative cardinal positions, exactly eliciting all n agents’ preferences requires at least nm/2 comparison queries in the worst case.The lower bound remains even when ordinal positions are known, cardinal positions are confined to nonoverlapping intervals, and queries may be interleaved across agents.

5. Determining the Aggregate Ranking Only

Determining only the aggregate ranking remains query-intensive when cardinal positions are unknown, despite requiring less information than eliciting every individual preference.

  • 5. Determining the Aggregate Ranking Only: Thus, determining the aggregate ranking still requires Ω(nm) queries rather than a sublinear number in the unknown-cardinal-positions setting.The same lower-bound phenomenon persists even when ordinal positions are known and agent queries can be interleaved.
  • 5. Determining the Aggregate Ranking Only: (n + 1)m/4 comparison queries are necessary in the worst case to determine the aggregate ranking with unknown alternative cardinal positions.The lower bound applies when n is odd and m is even, even though the agents’ preferences are known to be cardinally single-peaked.
  • 5. Determining the Aggregate Ranking Only: Determining only the winner is easier because the winning alternative is the median of the agents’ peaks.When ordinal positions are known, each peak can be found using logarithmically many queries.

6. Robustness to Slight Deviations from Single-Peakedness

The paper studies elicitation when some agents deviate from single-peakedness, distinguishing rare non-single-peaked agents from individually near-single-peaked preferences. Verification-based algorithms retain efficiency for the first interpretation, whereas the second remains difficult.

  • Aggregation consequences: Almost single-peaked preferences can restore Condorcet cycles, leaving aggregation unclear and potentially making aggregation rules manipulable.The paper distinguishes these consequences from the elicitation results for rare deviations.
  • Few non-single-peaked agents: O(m + αm log m) queries suffice on average when a fraction α of agents are not single-peaked and alternative positions are known.The algorithm first elicits under the single-peaked assumption, verifies adjacent pairs, and falls back to O(m log m) sorting when verification fails.
  • Limitations: With unknown positions, cardinal single-peakedness loses its query advantage under verification because the verification step requires m −1 queries.This contrasts with the O(log m) bound available when cardinal positions are known and the assumption is certain.
  • Individual deviations: The verification approach addresses a minority of exceptional agents, but individually near-single-peaked preferences can make roughly half of verification queries disagree with expectations.The paper illustrates this with a ranking whose peak is far left while the reported order begins near the middle.
  • Unknown positions: O(m + (2α −α2)m log m) queries suffice on average when positions are unknown and non-single-peakedness is independently distributed across agents.The verification step fails when either the current or previous agent is not single-peaked.

7. Conclusions

The paper concludes that single-peaked structure supports efficient preference elicitation and strategy-proof aggregation, while broader settings require attention to cycles and strategic effects. It identifies higher-dimensional and near-single-peaked domains as directions for further study.

  • Conclusions: Single-peaked preferences are useful because they avoid Condorcet cycles and permit strategy-proof aggregation.When all agents share the same positions and their number is odd, pairwise election outcomes define the aggregate ranking without ties.
  • Future directions: Higher-dimensional alternatives and almost single-peaked preferences may reintroduce Condorcet cycles, although efficient elicitation algorithms may still exist.The paper identifies both settings as relevant subjects for future research.
  • Strategic effects: Without strategy-proof aggregation, elicitation queries can reveal earlier agents’ answers and affect later agents’ strategic responses.The paper connects this issue to strategic effects studied in prior work.

Appendix A. Experimental Results for Ordinally Single-Peaked Preferences

The appendix compares two single-peaked elicitation algorithms with MergeSort under ordinal positions and known prior votes. FindRankingGivenPositions performs best, followed by FindRankingGivenOtherVote, while MergeSort is the general-preference baseline.

  • Setup: The experiment compares position-aware, other-vote-based, and unrestricted sorting approaches for eliciting a second single-peaked vote.FindRankingGivenPositions receives the positions, FindRankingGivenOtherVote receives a first vote, and MergeSort receives neither.
  • Baseline: MergeSort is an appropriate unrestricted-preference baseline because any comparison-query algorithm for arbitrary rankings solves sorting and requires Ω(m log m) comparisons.The appendix notes that alternative sorting algorithms may differ slightly in practice but share this asymptotic requirement.
  • Implementation: FindRankingGivenOtherVote sometimes repeats queries, whereas FindRankingGivenPositions and MergeSort never repeat them.Storing previous answers can reduce query counts but imposes computational overhead.
  • Results: FindRankingGivenPositions outperforms FindRankingGivenOtherVote, which clearly outperforms MergeSort in the ordinal experiment.Figure 1 uses a logarithmic x-axis and averages each data point over five runs.

Appendix B. Experimental Results for Cardinally Single-Peaked Preferences

The appendix compares FindRankingGivenCardinalPositions with FindRankingGivenPositions using preferences generated from random cardinal positions. Both algorithms were verified to produce the correct ranking, with results averaged over five runs on a logarithmic scale.

  • Results: Both cardinally generated-preference algorithms produced the correct ranking in every experimental run.Alternatives and the agent received uniformly random positions in [0, 1], and rankings followed proximity to the agent’s position.
  • Setup: The cardinal-position algorithm is evaluated on preferences constructed by drawing a cardinal position for every alternative and for the agent.The agent ranks alternatives by their distance from its own cardinal position.
  • Comparison: Figure 2 compares FindRankingGivenPositions and FindRankingGivenCardinalPositions on a logarithmic x-axis, averaging each data point over five runs.The caption identifies the two algorithms but does not state a numerical winner.
Loading 1401.3449v1…