PaperlayerView exact revision on arXiv

Source-linked AI summary

The Art of Calling the Winner by Asking Just Enough Questions: Competitive Preference Elicitation with Next-Best Queries

Nisarg Shah, Ziqi Yu

arXiv:2608.29087v1cs.GT

TL;DR

The paper asks how to determine voting winners when complete rankings are costly to elicit. It studies online next-best queries, showing sublinear guarantees for several positional rules but linear dependence on m for Condorcet-consistent rules; for Borda, MULTISCALESCORE achieves O(√m).

  • Problem

    Complete preference rankings are unrealistic when voting must choose among large pools of alternatives, motivating query-efficient winner determination.

  • Method

    The paper analyzes competitive ratios for online next-best elicitation and develops level-wise pruning and multi-scale score-thresholding algorithms for Borda.

  • Results

    O(√m): MULTISCALESCORE’s worst-case competitive-ratio guarantee for Borda, while Condorcet-consistent rules require competitive ratio linear in m.

  • Takeaways & Limitations

    Sublinear competitive ratios are achievable for many positional scoring rules, with Borda receiving a stronger guarantee from multi-scale thresholds than from level-wise pruning.

  • Takeaways & Limitations

    The multi-scale Borda bound does not extend to other concave scoring rules, and LEVELPRUNING’s lower bound is specific to that algorithm.

Abstract

from arXiv · show

We study active elicitation of agent preferences for collectively choosing among $m$ alternatives using prominent voting rules. We focus on the next-best query model, in which an agent responds to a query by revealing their next favorite alternative, and measure the competitive ratio, which is the worst-case ratio between the number of queries made by the active elicitation algorithm and the minimum number of queries needed to reveal the winning alternative(s) in hindsight. We show that sublinear competitive ratios are achievable for many positional scoring rules, whereas every Condorcet-consistent rule has competitive ratio linear in $m$. For Borda count, we develop two complementary techniques: level-wise pruning, whose analysis extends to general concave scoring rules, and multi-scale score thresholding, which gives an $O(\sqrt m)$ worst-case guarantee for Borda. We also demonstrate strong empirical performance of level-wise pruning on real data.

1 Introduction

The paper studies winner determination when complete preference rankings are unavailable and queries can be actively selected. It introduces competitive-ratio analysis for next-best elicitation and characterizes guarantees across voting-rule families.

  • Motivation: Large-scale decision settings make the assumption of fully known rankings unrealistic, motivating active elicitation from partial preference information.Examples include platforms voting over thousands of statements and systems searching astronomical spaces of statements.
  • Motivation: Competitive ratio compares an algorithm’s queries with the minimum queries needed to reveal the winners in hindsight, emphasizing performance on easy instances.This complements worst-case communication complexity, which can require the entire preference profile for many rules.
  • Framework: The paper initiates competitive-ratio analysis for winner determination under prominent voting rules in the next-best query model.The model reveals each voter’s ranking prefix one alternative at a time and stops when the winner can be certified.
  • Results: Plurality and k-approval have optimal competitive ratios of 2 and k, respectively, making k-approval sublinear when k ∈o(m).These results are obtained by eliciting the relevant top choices of every voter.
  • Results: For Borda, LEVELPRUNING gives O(m2/3), MULTISCALESCORE gives O(√m), and the analysis of LEVELPRUNING extends to concave scoring rules.The paper also establishes a universal lower bound of 3 for Borda elicitation algorithms.
  • Results: No Condorcet-consistent voting rule admits a competitive ratio sublinear in m, while experiments report better ratios for the elicitation algorithm than theoretical bounds.The empirical evaluation uses real datasets from PrefLib.

2 Model

The model represents voters’ rankings as initially hidden and reveals them through constrained sequential queries. An online algorithm must query only from observed responses until the complete tied winner set is certified.

  • Problem instances: An instance contains n voters, m alternatives, and a strict total-order preference ranking for each voter.The notation fixes the alternative set while allowing any finite number of voters.
  • Voting rules: A voting rule maps each instance to a set of tied winners, including positional scoring, k-approval, Borda, harmonic, Copeland, and minimax rules.Positional scoring rules sum position-dependent scores across voters; Borda uses (m −1, m −2, . . . , 0).
  • Queries: A sequential query (v, k) reveals voter v’s kth-ranked alternative, and next-best queries require all preceding k −1 positions to have been elicited.Thus each voter contributes a revealed prefix of length d(v, Q).
  • Queries: At intermediate stages, the algorithm observes only ranking prefixes and must reason about unelicited alternatives when deciding which queries can certify the winner.The remaining profile is treated as uncertain.
  • Elicitation algorithms: An elicitation algorithm must determine the winners, respect next-best queries, and choose each next query using only elicited responses.These are the winner-determination, next-best, and online-elicitation conditions.
  • Optimal queries and competitive ratio: OPT(I) is the shortest next-best query sequence that reveals the winners without the online requirement, while competitive ratio compares an online algorithm’s cost with OPT(I).All upper bounds determine the complete set of tied winners.

3 Warm Up: Plurality and k-Approval

For plurality and k-approval, eliciting every voter’s relevant top positions is optimal under next-best queries. Their competitive ratios are exactly 2 for plurality and k for k-approval.

  • Plurality: Plurality winners are the alternatives appearing as the top choice of the most voters, so eliciting every voter’s top choice determines them.This requires n queries.
  • Plurality: 2: Eliciting all voters’ top choices has competitive ratio 2 for plurality, and no online algorithm can achieve less.The proof uses OPT(I) ⩾n/2 and an adversarial construction for the lower bound.
  • k-Approval: k: Eliciting the top k choices of all voters has competitive ratio k for k ∈{2, 3, . . . , m −1}, and no online algorithm can do better.The rule selects alternatives appearing in the top k positions of the maximum number of voters.

4 Borda Count (and Concave Scoring Rules)

The Borda-count analysis develops level-wise pruning for concave scoring rules and a multi-scale thresholding algorithm with a stronger Borda guarantee. It also establishes lower bounds and leaves open whether constant-competitive Borda elicitation is possible.

  • Borda Count: Borda elicitation is substantially more complex than plurality because top-choice information alone does not identify necessary Borda winners.Even full elicitation can have competitive ratio m when O(n) queries would suffice on a unanimous profile.
  • Open Question: Whether Borda admits a constant-competitive elicitation algorithm remains open; the known universal lower bound is 3.The paper contrasts this lower bound with the O(√m) upper bound from MULTISCALESCORE.
  • Borda Count: LEVEL elicits rankings level-by-level but has competitive ratio Ω(m) for Borda.An instance with two leading alternatives makes LEVEL continue to level m−1 despite one alternative being the unique winner.
  • Borda Count: LEVELPRUNING removes voters after each level once they have revealed every alternative that can plausibly remain a winner.It uses lower and upper score bounds, retaining alternatives satisfying UB(a) ⩾ max_b LB(b).
  • Concave Scoring Rules: The analysis of LEVELPRUNING extends to concave scoring vectors whose score losses accelerate with rank.For Borda, the resulting competitive-ratio upper bound is O(m2/3).
  • Borda Count: The competitive ratio of LEVELPRUNING for Borda is Ω(√m), so its O(m2/3) analysis is not known to be tight.This lower bound applies to LEVELPRUNING rather than to all Borda elicitation algorithms.
  • Improved Borda Ratio: MULTISCALESCORE applies score-upper-bound tests at multiple thresholds and determines the complete Borda winner set.Its correctness follows when alternatives outside the threshold-certified set cannot match the maximum exact score in any consistent completion.
  • Improved Borda Ratio: O(√m) is the competitive-ratio guarantee achieved by MULTISCALESCORE for Borda.The proof bounds the ratio by 20√m in one regime and by less than 4√m in another.

5 Condorcet Methods

The paper proves that every Condorcet-consistent voting rule has a competitive ratio linear in m. An adversarial construction forces many queries even though OPT can certify the Condorcet winner with far fewer.

  • Lower bound: Ω(m) is the competitive-ratio lower bound for every elicitation algorithm under any Condorcet-consistent voting rule.The result applies to the broad family including Copeland, Minimax, Kemeny, ranked pairs, Schulze, and Dodgson.
  • Adversarial construction: The adversarial instance uses alternatives w and c plus two sets X and Y, each containing m/2 −1 alternatives.The construction permits arbitrary internal orders within X and Y while controlling the revealed prefixes.
  • Adversarial construction: w is the Condorcet winner because three voter-type majorities establish pairwise majorities over X, Y, and c.The relevant majorities are (T1)+(T2) over X, (T1)+(T3) over Y, and (T1)+(T5) over c.
  • Lower bound: (n/2 −4) · (m −1) queries are required before the algorithm can terminate with w as the necessary winner.Before enough voters reach position m −1, the algorithm cannot exclude completions in which the unresolved group changes the pairwise outcome.
  • Comparison with OPT: OPT needs only O(n + m) queries to reveal w by selectively querying the relevant voter types.It queries T1 voters to rank 1, T2 and T3 voters as needed, and T5 voters to rank m −1.

6 Experiments

Experiments on thousands of PrefLib strict-complete preference profiles compare LEVELPRUNING with OPT and LEVEL across positional scoring and Condorcet-consistent rules. LEVELPRUNING typically has competitive ratios near 2, gains most over LEVEL on Borda, and uses a largely level-wise probing strategy.

  • Experimental setup: The experiments use PrefLib Strict Orders Complete profiles grouped by alternatives m, with voter-count distributions summarized across groups.The dataset collection varies both the number of alternatives and the number of voters.
  • Experimental setup: The evaluated rules include Borda, Harmonic, Plurality, Half-Approval, Veto, Copeland, and Minimax.The first five are positional scoring rules; Copeland and Minimax are Condorcet-consistent rules.
  • Algorithms and metrics: LEVELPRUNING queries voters level-by-level while pruning voters who have revealed all possible-winners, whereas LEVEL performs no pruning.Both methods share the same maximum queried depth dmax, but LEVELPRUNING can stop individual voters earlier.
  • Experimental setup: At least 7,000 instances per rule remained after the 60-second OPT ILP time limit excluded less than 1% of instances.Competitive ratios were computed relative to the exact OPT solver on the retained instances.
  • Competitive-ratio results: The median competitive ratio of LEVELPRUNING is typically close to 2 and shows no clear upward trend as m grows.Performance is slightly better on Borda, slightly worse on Veto, and fairly consistent across Condorcet-consistent rules.
  • Pruning comparison: Pruning is identical to LEVEL for k-Approval rules, modestly beneficial for Harmonic, Copeland, and Minimax, and noticeably more beneficial for Borda.For k-Approval, voters cannot be pruned before all top-k positions are exposed or a unanimous winner is observed.
  • Probing strategy: LEVELPRUNING has near-zero Pearson correlation between queried depth and the winner’s true rank because it largely queries voters to a common maximum depth.For k-Approval rules, the correlation is exactly 0 on every instance because no voters are pruned.
  • Probing strategy: OPT’s probing differs by rule: it avoids detractors for Condorcet rules, has peaks at 1 and 0 for large-k k-Approval, and places Borda and Harmonic between these behaviors.Plurality is largely negatively correlated, while Borda resembles larger-k k-Approval and Harmonic resembles smaller-k k-Approval.

7 Discussion

The discussion highlights complementary guarantees for Borda, open questions about optimality, and limits imposed by the next-best query model. It also situates competitive analysis as a framework that could extend beyond winner determination.

  • The optimal competitive ratio for Borda: MULTISCALESCORE improves Borda’s worst-case guarantee to O(√m), while LEVELPRUNING achieves O(m2/3) and extends to concave scoring rules.The algorithms exploit different structures and therefore provide complementary results.
  • The optimal competitive ratio for Borda: Whether Borda admits a constant-competitive elicitation algorithm remains open, because the universal lower bound is only 3 while LEVELPRUNING’s Ω(√m) construction is algorithm-specific.The existing lower bound against arbitrary Borda algorithms remains constant.
  • Alternative query models: The guarantees are specific to next-best queries, whereas approval and pairwise-comparison interfaces remain future directions for competitive-ratio analysis.These interfaces are common on platforms such as Polis and Remesh.
  • Extension to other models: Competitive analysis could replace winner determination with distortion or fairness targets, including proportional fairness and justified representation.This perspective compares queries on each instance with that instance’s optimum, rather than only using worst-case communication over all instances.

AI Disclosure

The disclosure states that GPT-5.6-Sol helped improve proof presentation and derived the O(√m) Borda improvement from the conference-version analysis.

  • AI Disclosure: GPT-5.6-Sol improved the presentation of several proofs and derived the O(√m) Borda competitive-ratio improvement from the conference version.The conference version contained the earlier O(m2/3) bound and its analysis.

A Proofs for Section 3

The proof establishes that eliciting every voter’s top k choices is optimally k-competitive for k-approval. The upper bound uses certificate costs, while the lower bound constructs an adversary that forces complete depth-k elicitation online despite a cheaper hindsight certificate.

  • Theorem 2: The top-k elicitation algorithm makes nk queries and returns the k-approval winners.Because positions below k do not affect k-approval, certificates can be truncated after depth k.
  • Theorem 2: Every certificate has cost at least n, so the algorithm’s competitive ratio is at most nk/n = k.The proof bounds the revealed approvals of a true winner using fully queried voters and remaining queries.
  • Theorem 2: A constructed profile makes a unique winner a score n −1 alternative while every other alternative scores at most n −2.The construction excludes a from one ballot, b from two ballots, and each remaining alternative from at least two ballots.
  • Theorem 2: An adversary can force every online algorithm to query every voter through depth k, costing nk queries.Until the two exceptional ballots are revealed, a completion remains possible in which b ties or defeats a.
  • Theorem 2: In hindsight, a certificate costs at most n −1 + 2k(m −1) queries by certifying a’s lower bound and excluding every other alternative.The certificate queries first positions for voters ranking a first and depth k for two ballots excluding each rival.

B Proofs for Section 4

The proof gives a universal lower bound of 3 for online Borda elicitation using three alternatives. An adversary preserves multiple consistent profiles until nearly all second-position information is queried, while each exceptional profile has a short hindsight certificate.

  • Theorem 3: Any online Borda elicitation algorithm has competitive ratio at least 3.The lower-bound construction uses m = 3 and Borda scores (2, 1, 0).
  • Theorem 3: The base profile with n = 3t has scores (4t, 4t, t), so its winner set is {a, b}.It contains 2t voters ranking a ≻b ≻c and t voters ranking b ≻c ≻a.
  • Theorem 3: The adversary answers first-position queries with b for t voters and a for 2t voters, while delaying one second-position response.As long as a second position remains unqueried, the transcript is consistent with both the base and an exceptional profile.
  • Theorem 3: For either exceptional profile, a hindsight certificate uses at most 2t + 2 queries to certify a as the unique winner.The certificate queries the first positions of all 2t a-first voters and the exceptional information needed for the relevant profile.
  • Theorem 3: The resulting ratio satisfies CR(A) ⩾ 6t/(2t + 2) = 3t/(t + 1), which converges to 3.The online algorithm is forced to make substantially more queries than the hindsight certificate.

B.1 Full Proof for Concave Scoring Rules

The analysis develops structural properties of concave scoring rules, certificate-based lower bounds, and the level-wise pruning algorithm. These ingredients yield query-cost guarantees in terms of the winner’s deficit and the rule’s top gap.

  • Normalization: Affine transformations preserve winner sets, certificates, OPT, LEVELPRUNING, concavity, the top gap, and deficits, so scores are normalized to s1 = 1 and sm = 0.Under this normalization, a winner of deficit δ has score n(1 −δ).
  • Structural properties: Concavity makes every consecutive score difference at least γ and bounds γ ≤ 1/(m −1), with equality exactly for Borda.The same lemma also bounds score decay across levels, providing the inequalities used in the cost analysis.
  • Certificates: A certificate requires LB(w) ≥ UB(a) for every challenger a, because otherwise one completion can minimize w’s score while maximizing a’s score.The completion argument assigns the alternatives to compatible open positions voter by voter.
  • Lower bounds: Every certificate for a concave-rule winner of deficit δ costs at least max{n(m −1)δ, n/2} queries.The first term follows from bounded average score reduction per query, while the second follows because fewer than half the voters queried cannot certify a winner.
  • LEVELPRUNING: LEVELPRUNING queries profiles level by level, retaining alternatives whose upper bounds reach the largest current lower bound and pruning voters once all retained alternatives are exact.Its analysis splits execution at depth d∗ into an initial phase and a subsequent phase, without requiring knowledge of δ.

B.2 Proof of the LevelPruning Lower Bound

The lower-bound construction shows that LEVELPRUNING can spend many queries before pruning, even when a short offline certificate exists. The section also develops score-bound and threshold-testing machinery for a multi-scale Borda algorithm that remains correct for complete winner sets.

  • Lower-bound construction: LEVELPRUNING has competitive ratio Ω(√m) for Borda count.The construction uses r = ⌊√m/2⌋ challengers and separates voters into two groups with cyclic challenger placements.
  • Lower-bound construction: The construction makes w the unique Borda winner while keeping all r challengers possible through depth d.Challengers retain identical bounds through the relevant levels, preventing voter pruning before the costly level.
  • Lower-bound construction: An offline certificate costs at most 2n queries, whereas LEVELPRUNING continues querying every voter at the critical level.The offline certificate queries one voter group to depth 1 and the other to depth 4r.
  • Score bounds: For Borda, a next-best query either leaves a candidate’s upper bound unchanged when that candidate is revealed or decreases it by 1/(m −1) otherwise.Upper bounds are monotone nonincreasing and become exact when the candidate is exact at every voter.
  • Multi-scale thresholding: At dyadic scale g, at most 2g −1 candidates survive, and a successful scale determines the complete Borda winner set.The algorithm freezes the surviving set, score-tests every member, and falls back to full elicitation if no scale succeeds.

C.3.3 Lower Bounds on the Profile-Aware Optimum

This section characterizes when a partial transcript certifies a winner in every consistent completion and derives lower bounds on the profile-aware optimum from Borda score bounds.

  • Certificate characterization: A candidate w is a winner in every completion of Q exactly when LBQ(w) ≥ UBQ(a) for every challenger a.If the inequality fails, a completion can simultaneously minimize w’s contribution and maximize a’s contribution.
  • Optimum lower bounds: The score-bound argument lower-bounds each challenger’s upper score using unrevealed ballot prefixes, while the winner’s lower score is positive on at most the queried voters.Combining these bounds yields both certificate-cost inequalities and therefore applies to the profile-aware optimum.

C.3.4 Query Cost

The multi-scale Borda algorithm bounds its cumulative query cost by scale and compares that cost with certificate lower bounds. It is correct for tied winners, but its implementation and guarantees rely on explicit certification choices and modeling assumptions.

  • Query-cost upper bound: Through dyadic scale g, MULTISCALESCORE makes at most 5ng^2 queries.This combines uniform prefix extension with score-testing costs across all candidates surviving each scale.
  • Case analysis: If the winner’s deficit scale satisfies ρ ≤ G, the algorithm terminates at the first scale g ≥ ρ containing the winner.For g ∈ {1, 2}, the competitive ratio is at most 25.
  • Case analysis: If ρ > G, fallback full elicitation together with the optimum lower bound gives a competitive ratio less than 4√m.Here G is the largest power of two not exceeding √m.
  • Correctness and ties: Processing every candidate in the frozen set Cg is necessary because another candidate may have a larger score or tie the first certified winner.This is what converts one-sided score tests into a certificate for the complete winner set.
  • Experimental optimum: The experiments’ ILPs may certify any one tied true winner, rather than necessarily certifying the entire tied winner set.The selected target is constrained to dominate challengers under worst-case score bounds.
Loading 2608.29087v1…