Computing Voting Rules with Improvement Feedback
Aggregating preferences under incomplete or constrained feedback is a fundamental problem in social choice and related domains. While prior work has established strong impossibility results for pairwise comparisons, this paper extends the inquiry to improvement feedback, where voters express incremental adjustments rather than complete preferences. We provide a complete characterization of the positional scoring rules that can be computed given improvement feedback. Interestingly, while plurality is learnable under improvement feedback--unlike with pairwise feedback--strong impossibility results persist for many other positional scoring rules. Furthermore, we show that improvement feedback, unlike pairwise feedback, does not suffice for the computation of any Condorcet-consistent rule. We complement our theoretical findings with experimental results, providing further insights into the practical implications of improvement feedback for preference aggregation.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
The Computational Impact of Partial Votes on Strategic Voting
In many real world elections, agents are not required to rank all candidates. We study three of the most common methods used to modify voting rules to deal with such partial votes. These methods modify scoring rules (lik…
Computational Aspects of Multi-Winner Approval Voting
We study computational aspects of three prominent voting rules that use approval ballots to elect multiple winners. These rules are satisfaction approval voting, proportional approval voting, and reweighted approval voti…
Obvious Manipulability of Voting Rules
The Gibbard-Satterthwaite theorem states that no unanimous and non-dictatorial voting rule is strategyproof. We revisit voting rules and consider a weaker notion of strategyproofness called not obvious manipulability tha…
Estimating the Margin of Victory of an Election using Sampling
The margin of victory of an election is a useful measure to capture the robustness of an election outcome. It also plays a crucial role in determining the sample size of various algorithms in post election audit, polling…
Computing Voting Rules with Elicited Incomplete Votes
Motivated by the difficulty of specifying complete ordinal preferences over a large set of $m$ candidates, we study voting rules that are computable by querying voters about $t < m$ candidates. Generalizing prior works t…