Computing Voting Rules with Improvement Feedback
Authors: Evi Micha
Vasilis Varsamis
Venue: ICML 2025 poster (2025)
Keywords: Preference Aggregation
Incomplete Preferences
Improvement Feedback
Positional Scoring Rules
Condorcet-Consistent Rules
Computational Social Choice
Primary area: theory->game_theory
TL;DR: This paper studies the limits of learning social choice functions using t-improvement feedback.

Abstract: 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.

Computing Voting Rules with Improvement Feedback
Evi Micha Vasilis Varsamis
Abstract
queries between pairs of outputs (Ouyang et al., 2022; Chris- tiano et al., 2017).
Aggregating preferences under incomplete con- strained feedback is 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 vot- ers express incremental adjustments rather than complete preferences. We provide complete characterization of the positional scoring rules that can be computed given improvement feed- back. Interestingly, while plurality is learnable un- der improvement feedback-und unlike with pairwise feedback strong impossibility results persist for many other positional scoring rules. Furthermore, show that improvement feedback, unlike pair- wise feedback, does not suffice for the computa- tion of any Condorcet-consisten rule. We comple- ment our theoretical findings with experimental results, providing further insights into the prac- tical implications of improvement feedback for preference aggregation.
Despite their widespread use, pairwise or t-wise compar- isons-rankings of t candidates face fundamental limita- tions. Recent work by Halpern et al. (2024) shows that, even under ideal conditions where the preferences of the popula- tion over every t-wise query are fully known (i.e., for every ranking of t candidates, the proportion of the population that agrees with is known), the winner under common vot- ing rules cannot be determined. For example, the plurality winner cannot be reliably identified, and even randomized algorithms fail to perform better than random guessing.
Motivated by these limitations, we explore an alternative type of feedback known as improvement feedback. Unlike clicitation methods based on rankings or pairwise compar- isons, improvement feedback enables agents to iteratively refine initial suggestion. For instance, in RLHF applica- tions, improvement feedback could involve user modifying draft generated by an LLM to better align with their pref- erences (Schick et al., 2023; Jin et al., 2023). Similarly, in robotics, users might iteratively adjust a robot's trajectory or behavior to achieve their desired outcome (Bajesy et al., 2018; 8; Yang et al., 2024).
1. Introduction
This form of feedback aligns naturally with the framework of preference- reinforcement learning (PbRL), which infers preferences from relative judgments rather than ex- plicit reward signals. While PbRL typically relies on pair- wise comparisons (e.g., preferring trajectory A over B), improvement feedback can be interpreted as the case where the preferred option an improved version of the original. This connection is particularly salient in coactive learning frameworks (Shivaswamy & Joachims, 2015; Tucker et al., 2024), where users typically refine queried options through targeted adjustments rather than identifying the optimal can- didate outright-oftee because they may not even know what the optimal choice is.
Classical social choice theory assumes that voters provide complete rankings of all candidates, which are then aggre- gated by voting rule to select a winner (Brandt et al., 2016). However, this assumption becomes impractical in many real- world scenarios involving a large number of candidates, as voters may be unable or unwilling to rank all of them. For example, deliberation platforms like Polis (Small al., 2021), users provide pairwise comparisons over a limited subset of opinions rather than full rankings. Similarly, in Re- inforcement Learning from Human Feedback (RLHF)-a methodology widely used to fine-tune large language mod- els (LL.M))eeedbaa often takes the form of comparison
A simple observation that improvement feedback offers promising pathway to address some challenges posed by t-wise comparisons. For example, unlike pairwise feedback-whicl struggles to compute the plurality win- ner- per-improvement feedback enables users to iteratively re- fine a suggested candidate. As users provide targeted adjust- ments, they gradually reveal their top preferences, ultimately
'Thomas Lord Department of Computer Science University of Southern California, Los Angeles, California, USA. Correspon- dence to: Evi Micha Cevi.micha @ ceeuusceede edu., Vasilis Varsamis <varsamis @usc.duu>.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Computing Voting Rules with Improvement Feedback
enabling the identification of the plurality winner through this iterative process. This raises the following questions:
in this case. As discussed in the introduction, in practical settings t < m. thus making these findings particularly relevant. We also extend these negative results for every t E [m - 1] under the uniform t-improvement distribution, where when a candidate a is queried, a candidate from its t-above neighborhood is returned uniformly at random.
Can other voting rules be computed using im- provement feedback? For which voting rules is improvement feedback more effective than pair- wise comparisons, and vice versa?
In Section 5, we turn our attention to Condorcet-consisten rules, which select the Condorcet winner whenever one exists. While pairwise comparisons suffice to identify the Condorcet winner, we surprisingly show that under t- improvement feedback, no (randomized) algorithm can de- termine the Condorcet winner with probability greater than 1/m. This result applies under the uniform t-improvement feedback model for all values of t and extends to all S m/2 - 2 for almost every t-improvement feedback distribution. We also diseuss the one specific exception to this result in detail.
1.1. Our Contribution
We model improvement feedback as a process in which, when a user or agent is queried with a candidate ranked at position i in their preference order or ranking, they re- turn, with some probability, a candidate ranked at position j. where j < i. The likelihood of returning the candidate at position j decreases as the distance i i-j increases, reflecting the agent's tendency to provide localized improvements. To formalize this, we introduce the concept of l-improvement feedback, where user refines a queried option by selecting better candidate from the t-above neighborhood of the queried candidate in their preference ranking fiekinggie.,..ae a candi- date within the I positions above the queried candidate. The t- t-improvement feedback distribution specifies the probabili- ties of selecting a candidate from this neighborhood. The parameter defines the size of this neighborhood. capturing how much better the returned candidate can be relative to the queried one. In practice, t is typically much smaller than the total number of candidates, m, reflecting the limited cognitive and practical effort users are willing to expend.
These theoretical results indicate that while t-improvement feedback is particularly effective for identifying the plu- rality winner, it is insufficient for computing many other widely studied rules in social choice theory, such as Kemeny, Copeland, Borda, which, by contrast, can be identified using pairwise comparison feedback.
Lastly, in Section 6, we compare the two types of feedback through simulations. Interestingly, contrary to the theo- retical results, t-improvement feedback queries turn to be more efficient in some cases for implementing rules-such as Copeland or Borda that are learnable from pairwise comparison feedback but are not implementable by t- improvement feedback in the theoretical worst case.
Our goal is to investigate whether winners under various voting rules can be identified using t-improvement feedback queries over the underlying preferences of the agents, which are unknown to the algorithm. We consider an idealized setting, similar to (Halpern et al., 2024), where the algorithm has access to the full statistical distribution of feedback responses. Specifically, with a sufficiently large number of t- t-improvement feedback queries, the algorithm knows the exact probability of receiving candidate h as feedhack when querying candidate a, given the population's 's preferences and the underlying t-improvement feedback distribution. This idealized assumption strengthens our impossibility results and models scenarios where such statistical information is available or can be effectively estimated.
1.2. Related Work
Our work contributes to the growing body of research on decision decision-making with partial access votes. Filmus & Oren (2014) and Oren et al. (2013) studied t-top queries, where each agent reports their top t-candidates, and inves- tigated how large f must be to reliably identify the correct winner under various voting rules. Similarly, Bentert & Skowron (2020) examined t-wise comparison queries, an- alyzing which voting rules can be implemented with this feedback. More recently, Halpern et al. (2024) provided complete characterization of positional scoring rules that can be computed using t-wise comparison feedback.
In Section 4, we study the well-known family of positional scoring rules and provide a complete characterization of the rules that are learnable under t-improvement feedback queries, for all practical values t. We show that beyond plurality and specific positional scoring rule uniquely de- termined by the t-improvement feedback distribution, as well as any linear combination of the two, no other posi- tional scoring rule is learnable using t-improvement feed- back queries for any value of t < m//2 - 2. In fact, we show that even randomized algorithms cannot reliably iden- tify the correct winner with a probability greater than 1/m
These works build on foundational results regarding pair- wise comparisons, which are often represented as (weighted) tournament graphs. Tournament graphs serve as the pri- mary input for many well-known voting rules, including Borda count and several Condorcet-consistent rules, such as Copeland, Kemeny, and Minimax (Brandt et al., 201 6). Our work builds on and extends the results of Halpern et al. (2024), which we discuss in greater detail later. To the best
2

---

Computing Voting Rules with Improvement Feedback
of our knowledge, no prior work has studied improvement feedback queries for identifying the correct winner under different voting rules.
Voting Rules. A voting rule is function / ((C(M) - M that takes as input a preference profile and outputs a candidate the winner. We call the winner of f the f-winner. In this work, we focus on two main families of voting rules.
The query complexity of identifying the correct candidate has also been studied over different queries. For example, the query complexity of tournament graphs has been studied in the context of identifying Condorcet winners (Procaccia, 2008). Other works have explored the query complexity of complete rankings, focusing either identifying the winner (Dey & Bhattacharyya, 2015) or recovering the full ranking (Micha& & Shah, 2020) of different voting rules. In impos- sibilities, assuming perfect access to the feedback model under consideration, and does not analyze the sample com- plexity of learning voting rules.
The first family is the family of positional scoring rules, which are defined using scoring vector ş (51, $2...., E 1 with s; 2 8/+1 for all E [m - 1] and $1 > 8m- Without loss of generality, we usually assume 8m = 0. The score of a candidate a E M under positional scoring rule fa. parametrized by scoring vector s, given a preference profile D E (CC(M), is defined as follows:
contrast, our work focuses on information-theore
sca(a, D)
Pr lo (a) = -1]
Our work is also related to frameworks like coactive ing (Shivaswamy & Joachims, 2015) and interactive prefer- ence learning (Tucker et al., 2024), which focus on scenar- ios where users provide incremental improvements rather than global rankings. However, these frameworks aim to minimize regret and learn a good candidate for a single user through iterative interaction. In contrast, we investi- gate whether improvement feedback is sufficient to identify the correct candidate when preferences are heterogeneous across a population.
learn-
The rule fo then returns the candidate with the highest score as the winner, breaking ties arbitrarily. Some well- known positional scoring rules are plurality, parametrized by Splu (1, ..... 0): veto, parametrized by Sueto (1 (1...., 1, 1,0); and Borda count, parametrized by Bordd = (m 1,-1, 2, O).
The second family is the family of condorcet-consistennn rules. A candidate a E A is called the Condorcet win- ner if they beat every other candidate in pairwise ma- jority comparisons, i.e., Pra-nla >o b] 0.5 for all b E M Haj. A Condorcet-consistent voting rule f se- lects the Condorcet winner whenever one exists. Famous examples of Condorcet-consisten rules include Copeland's Rule, Kemeny's Rule, the Minimax Rule, Ranked pairs, and many others (Brandt et al., 2016).
2. Model
For N. let =1. k}.
We consider set M {a1,-.-, am) of m candidates. A ranking or preference a
over the candidates is bijection o [m] + M, where or (i) returns the candidate that is the i-th most preferred candidate in a and o -a) returns the position of candidate in a. We denote by L(M) the set of all m! possible rankings over M. We use a >a to denote that candidate a is ranked above candidate b under ranking a.
Improvement Feedback Distribution. In the improve- ment feedback setting, when an agent is queried with a candidate a ranked at position i in the agent's preference ranking a, the agent returns an improved candidate ranked at position j. where j < i. The candidates ranked in posi- tions j E [max(i - t, i), - 1] are referred to as the t-above neighborhood of (i)) representing the set of candidates that are strictly preferred but within / positions above the queried candidate. The only exception occurs when a is the agent's s first choice (i.e., i = 1), in which case no improvement is provided, and the agent returns a.
Let A(C(M)) be the set of probability distributions over L(M). A preference profile corresponds to distribution De E ((C())) which represents the proportion of users in the population that have each ranking. For example, if Pro~Dla= = 41 >.. > am = 1/3 this means that 1/3 of the population holds the ranking a1 >...> > Om-
Given a permutation over the candidates
M + M,
we define π a the ranking obtained by permuting the candidates in a according to π. The special case aas swaps only candidates and b, such that (a) = b, (b) = a, and Tas (c) e for all + a, b. For preference profiles, we denote by π o D the preference profile induced by sampling D and outputting æ a. Lastly, for swapping a and b, Dat>b ab o D.
More formally, for a fixed parameter S m - 1, the t- improvement feedback distribution defines the probability of returning a candidate o(j) when querying (i), denoted as pl.- The distribution satisfies the following properties:
př. > 0 only if < i, ensuring that the returned can- didates are strictly preferred to the queried candidate. The only exception is pt, = 1, reflecting that no im- provement is possible when querying the top-ranked
3

---

Computing Voting Rules with Improvement Feedback
candidate.
the preference profile. Therefore, discussed in the in- troduction, when this information is available, the plurality winner can be directly determined.
The probabilities sum to over the candidates in the t-above neighborhood:
Having direct access to this distribution provides strictly more information than an approximation based on random or adjusted queries (where, upon querying a, the algorithm observes b with some probability). Since our impossibility results hold even under this idealized setting, they provide fundamental limits that also apply to real-world scenarios with finite queries.
Pig 11, vi 1.
-=ma
We pay special attention to the uniform L-improvement feed- buck distribution, where the agent selects an improved can- didate uniformly at random from the t-above neighborhood:
t- f-Lndistinguishable Preference Profiles. Two prefer- ence profiles D1. D2 E ((((M) are said to be t- indistinguishable if, for every pair of candidates a, b M, the probability of receiving is the same under both profiles. Formally,
my 0,
0 <iijjs otherwise.
feedback when querying b
We also denote Pf the cumulative probability that can- didate ranked at position is returned as an improvement when querying candidate ranked at any position below i, ie.,
Pr ld a] = Pr lot = a]. on
a~
Thus, no algorithm with access only to t-improvement feed- back can distinguish between Dj and D2.
min min(m.i+e) Σ
P
In our results, we will focus on the I-indistinguishabiiiy between a preference profile D and its swapped version Dattb In this case, when the feedback probabilities satisfy
Intuitively, Pf. represents the overall likelihood that can- didate at position is selected through the improvement feedback process, summing over the probabilities of be- ing reached from any candidate ranked below it. Notably, Ph since there no candidate ranked below the last position m that could return it as an improvement.
(1 (x) y] = Pr Is (I) = y] onD
Pr
Dacs
= Pr lot (Tab(I)) = (v)l.)).
anD
for all y, E M, then the profiles are t-indistinguishable.
Improvement Feedback Queries. We consider algo- rithms that make t-improvement feedback queries over the preference profile D.. For x E M and a E L(M), we denote by of (x) the candidate returned when querying x in a under 1-improvement feedback. Specificallyy we as- sume that algorithm has access to the exact probability of observing a E M when querying b E M,, denoted by Pra-D la's (b) = a), and given by:
3. Main t t Indittiguuiiie Preference Profiles
We begin by constructing family of preference profiles, denoted D.j.,, which will serve as the foundation for our impossibility results.
Definition 3.1. Let Di be a preference profile defined with respect two candidates and as follows:
Pr (6 = a) onD
With probability p. candidate a is fixed at position i (where i 1), and candidate b is fixed at position j (where j t).
m- iin(m.i+()
Σ
ph. Pr lo R
loloo'(0) (a)= i 5].
2. With probability 1 - p. candidate is fixed at position m, and candidate b fixed at position é, where 1 <
This expression considers all possible positions of and b in the ranking, weighting the feedback probability p by the likelihood that a and b occupy these positions un- der the population distribution D. Additionally, we denote
f < m-
3. Select a uniformly random ranking S of all re- maining candidates (excluding a and b). This ranking determines their relative order, and they are then as- signed to the unoccupied positions.
by Pro-Dig' (a) = a] the probability of not returning any improvement, as a is already ranked first. This probability reflects the likelihood that a is the tap-ranked candidate in

---

Computing Voting Rules with Improvement Feedback
The proof of the following lemma can be found in Ap- pendix A
which a family of t-indistinguishable profiles, as described in Lemma 3.3, can be constructed. This lemma closely re- sembles Lemma 4.1 of Halpern et al. (2024) and its proof can be found in Appendix B
Lemma 3.2. For any m 2 and any t E [m- 1). the preference profiles Di and Dij.t are t-indistinguishable when p- - 7. 1
P
Lemma 4.1. Fix a scoring vector 5. Let D and Daesh be two t-indistinguishabbe preference profiles and let a.b E M be two candidates such that scg(a, D) o scy(b, D). Then, there exists a family of preference profiles (ee such that all profiles are t-indistinguishable from one another, but each candidate c M uniquely maximizes sca(c, D.).
We will also rely on the following technical lemma to es- tablish our impossibility results. Intuitively, this lemma suggests that if there exist m distinct preference profiles that are t-indistinguishabl from one another, and each has a different f-winner under some voting rule ʃ. then no ran- domized algorithm can identify the correct winner with a probability greater than l/m. This result corresponds to Lemma 4.2 of (Halpern et al., 2024), but we restate and prove here for completeness.
4.1. General t- Improvement Feedback Distribution
Here, we consider general l-improvement feedback distri- butions. To provide a complete characterization of the scor- ing rules that are learnable under t-improvement feedback queries, we first prove the following lemma.
Lemma 3.3. Fix any voting rule f and suppose there is a family of m preference profiles that are all t- indistinguishable from one another, but each has a distinct singleton f-winner. Then, for all (possibly randomized) algorithmss A that have access to t-improvement feedback, there is preference profile with a unique s-winning can- didate a, such that A outputs a with probability at most 1 1/m.
Lemma 4.2. For any m 2 6, any S m/2- 2. any pair of candidates a.b E M and any scoring vector z & span Bppie 3)), there exists preference profile D such that sca(a, D) & sca(b, D), and D and Daesh are t-indistinguishable.
Proof. Consider the preference profile D Dim,,+1 as defined in Definition 3.1. From Lemma 3.2, we have that for all E {2.... m t - 2]. Ds,m,i+1 and D imm,t11 are t- indistinguishable for every t I m 4, when
Proof. We denote with )CEM the set of m preference profiles that are all t- t-indistinguisaable and e is the unique winner in De under f. When the algorithm is applied to any of these preference profiles, it will receive the exact same feedback, and therefore the output should be the same across them. Due to the pigconhole principle, there must be a candidate a that is returned as the winner with probability at
Pr
P Pt + P
p P. P
P
If holds that sez(a, Di.m.i+1) # scz(b, Di.ma+1) for some E (2...., m t 2}. then setting D Dimatt1 satisfies the lemma.
most 1/m, and hence D satisfies the desired property. D
4. Positional Scoring Rules
Now, suppose that for every i E (,...., 1 2), we have
In this section, we consider the family of positional scoring rules and provide a complete characterization of the rules that are learnable under t-improvement feedback queries. For general t-improvement feedback distributions, this char- acterization applies for all S m//2- 2, while for the uni- form t-improvement feedback distribution, it extends to all t e im 1m-11 1].
scz(a, D Dim,,41) = scy(b, D iim.
This implies that
p. = --3; p)) 8i+1
8i41
8, + 81+1
In Section 4.1, we show that for any value of < m/2- - 2, the only learnable scoring vectors are linear combinations of ह and 6ptu, where ,7 = .P...... ). In fact, we prove that even randomized algorithms cannot identify the correct winner for any scoring vector ş outside the span( (57 Sptu) with a probability greater than 1/m. In Section 4.2, we extend these negative results to cover all values of i under the uniform t-improvement feedback distribution.
Thus, we have
P
8i+1
8:+1
8;
X
p + P(t1
81 8i+1
pt.
p!
(1)
for all i E (2....mm-1- 1-2
Assuming s/p; = x for all i E {2...., m - 1}, we next consider the preference profile D2,5,2 as defined in Definition 3.1. From Lemma 3.2, we have that for
For showing our negative results, we start with the fol- lowing lemma, which establishes the conditions under
5

---

Computing Voting Rules with Improvement Feedback
all i {m ,,...,"h m 1), 22. and Datth are
Proof. The first part of the lemma immediately follows from Lemma 4.3.
indistinguishable for every - 7/2 2, when
For the second part, since in Lemma 4.2 we show the existence of a preference profile D that is indistinguish- able from D and has the desired properties, we can apply Lemma 4.1 for constructing a family of preference profiles that are t-indistinguishable and each of them has a different candidate span(s, Sptu). Then, by applying Lemma 3.3, the theorem follows.
P2
p =
2P' P.
If it holds that scz(a, 22,1.2) # scy(b, D2.,2) for some i {m - l....,m m 1}, then setting 22,12 satisfies the lemma.
winner under a scoring rule not in
Now, suppose that for every i {m t, .....,.. m 1}, we have
scs(a, D2,122 = sCy(b, D2,1.).
An interesting observation arises when t 1. In this case, P = for all i [m 11, since each candidate ranked at position i can only be returned as improvement of candidate ranked at position i + 1, and when a candidate at position + 1 is queried, the agent always returns the candidate at position with probability 1. As a result, the scoring vector & = (1...., 1,0), which corresponds the veto scoring rule. Therefore, when 1, we can learn all rules within the span of plurality and veto. However, for larger values of t, the veto scoring rule is no longer learnable under t-improvement feedback queries.
This implics
p 82 (1 p1-p) + 8: 7
282
Thus, we obtain
P p 2P P.
82
282 St
From Equation (1), we know that o. X. Then by com- bining Equation (1) and the above equality, we get that P.. > for all {2, (2,..., 1}. This means that, less & = A for all i E f2....,m m - l}. which implies that E span( 57), there exists preference profile D satisfying the conditions of the lemma and the lemma follows.
4.2. Uniform t Improveeennt Feedback Distribution
Here, we turn our attention the uniform f-improvement feedback distribution. In this setting, we extend Lemma 4.2 to cover all values of t. To derive this result, we intro- duce an additional set preference profiles, distinct from those in Definition 3.1, and carefully analyze the resulting cases. The proof of the following lemma can be found in Appendix D
Next, we show that if 3 3 then the scores of all the candidates under ş can be computed with access to 1-improvement feedback queries. The proof of the following lemma can be found in Appendix C
Lemma 4.5. Under uniform t-improvement feedback distri- bution, for any E [m-11, any pair of candidates a, E M and any scoring vector & span( 31), there exists preference profile D) such that sca(a, D) & scy(b, D), and D and D are t-indistinguishable
Lemma 4.3. For any t E [m - 1] and any 5 E spon(5pla 5t), given a E M and E (CC(M)), it is pos- sible to calculate scy(a, D) with t-improvement feedback queries.
From the above lemma, we immediately derive the follow- ing theorem in manner similar to Theorem 4.4.
Now, we are ready to prove the following theorem.
Theorem 4.6. Under uniform t-improvement feedback feedbbbcc dis- tribution, for any m 2 6, any E [m 11, and any scoring vector 8:
Theorem 4.4. For any m 2 6, any t S m//2- 2, and any scoring vector 8:
1. I span(s), Sptu), then using t-improvement feed- back queries, the candidate that maximizes the score under 5 for any input profile D can be found.
1. If E span( Fpph), then using l-improvement feed- back queries, the candidate that maximizes the score under forr any input profile D can be found.
2. f $ span(5), Sppta) then no randomized algorithm with access to t-improvement feedback queries can output the candidate with the maximum score under for any input profile D with probability greater than 1 1/m.
2. I & span(s), Fptu). then randomized algorithm with access to t-improvement feedback queries can output the candidate with the maximum score under ž for any input profile D with probability greater than 1 m.
6

---

Computing Voting Rules with Improvement Feedback
5. Condorcet Consistent Rules
such that
In the previous section, we showed that t-improvement feed- back queries do not help us overcome the impossibility results associated with positional scoring rules and pair- wise comparison queries, except for plurality and specific positional scoring rule determined by the L-improvement feedback distribution. In this section, we extend these nega- tive results to the family of Condorcet-consistent rules.
Pr Pa E aEM((a
E
br x), onD
Pr
(EM(())
and D and Dae+b are t-indistinguishuble under the uniform L-improvement feedbbuck distribution.
Since in Lemma 5.2 we show the existence of preference profile D that is indistinguishable from Da and has the desired properties, we can apply Lemma 5. for constructing a family of preference profiles that are t-indistinguishable from one another and each of them has different candidate as the Condorcet winner. Then, by applying Lemma 3.3 we get the following theorem.
In Section 1, we demonstrate that for every/ & E [m-1], 11, no algorithm can reliably identify the Condorcet winner using uniform t-improvement feedback queries. In fact, even randomized algorithms cannot identify the correct candidate with a probability greater than 1/m. In Section 5.2, we extend this negative result to any t-improvement feedback distributions for L S "1/2- - 2, with only one exception, which we discuss in detail. These results contrast sharply with pairwise comparison queries, which are sufficient for identifying the Condorcet winner whenever one exists.
Theorem 5.3. For m 2 13 and any t E [m- 1}, no random- ized algorithm that has access to uniform t- t-improvement feedback queries outputs the unique Condorcet winner with probability more than 1/m.
As in the case of positional scoring rules, to establish these negative results, we start with the following lemma, which establishes the conditions under which a set of m t-indistinguishable profiles, as described in Lemma 3.3, can be constructed. Again, this lemma builds upon Lemma 4.1 of Halpern et al. (2024), employing the same method for constructing the set of distinct preference profiles. However, the condition that the initial preference profile must satisfy and the arguments used in the proof are significantly dif- ferent. The proof of the following lemma can be found in Appendix E
5.2. General (- Improvement Feedback Distribution
Now, we extend the negative results to every l-improvement feedback distribution when S T" - 2, with the exception of the special case where Pl/Pt,- = (m 1)/(m all i E {2..... m J. In Appendix H, we discuss in de- tail why this result cannot be applied in this case. We also show that for t S m - 4, no deterministic rule can identify the Condorcet winner under any t-improvement feedback queries. Thus, while the negative result does not extend to randomized algorithms for this specific t-improvement feed- back distribution, it still holds for deterministic algorithms across all distributions and all values of t S m - 4.
for
Lemma 5.1. Suppose there exist a, b E M and a preference profile such that D and Datbb are t-indistinguishabbl, and it holds that
To show the desired result, we use the following lemma, which proved in Appendix G.
Pr 1a (EM
Σ
+
Pr bbb (EM((
Σ
Lemma 5.4. Unless Pt/P: = (m fmn-8//m-i--- for all E (,...., m - 2}. then for any m 2 6 and t S m//2 2, and pair of candidates a E M, there is a preference profile such that
Then, there exists a family of preference profiles (D') JOEM such that all preference profiles in the family are indistngguishable from one another, and each preference profile E has the Condorcet winner.
Σ (EM
Pr Pr x] oND
Σ #EM((()
Pr 16bb00 >a x], onD
and D and Datsb are t-indistinguishable.
5.1. Uniform (- Improvement Feedback Distribution
In the following lemma, we claim that there a preference profile that satisfies the conditions of Lemma 5.1, when the algorithm has access to uniform f-improvement feed- back queries, for & E [m 1]. The proof is deferred to Appendix F.
As before, by combining Lemma 5.4. Lemma 5.1 and Lemma 3.3, we get the following theorem.
Theorem 5.5. For
6 and S m/2 2, unless the L-improvement feedback distribution satisfies Pt Pt/P:
(m fm-im/m-i-- for all i {,...., m 1}, no random- ized algorithm with access to t-improvement feedback queries can identify the unique Condorcet winner with a probability exceeding 1/m.
Lemma 5.2. For any m 2 13 and any t E [m - 1], and pair of candidates a, b E M, there is a preference profile D)
7

---

Computing Voting Rules with Improvement Feedback
6. Experiments
cating that it is their top choice), we update our estimates by adding all pairs (a, c) for each c E M \ {a). For pairwise comparison queries, we randomly sample pair of candi- dates (a, b) and ask the agent to compare them, directly updating based on the comparison outcome.
In the previous sections, we show that improvement feed- back queries are not sufficient in the worst case iden- tify the winner under most positional scoring rules and any Condorcet-consistentt rule. In this section, we empiri- cally evaluate the effectiveness of (-improvement feedback queries compared to pairwise comparison queries over one positional scoring rule, namely Borda count, and one Con- dorcet consistent rule, namely Copeland's 's rule. Copeland's rule calculates the number of candidates each candidate de- feats in pairwise comparisons and returns the candidate with the most wins. For both rules, access to the weighted ma- jority graph suffices to determine the winner. In this graph, each candidate is represented as node, and directed edge (a, b) is weighted by the margin by which candidate a de- feats candidate b in a head-to- he-h comparison.
Using the estimated weighted majority graph, we compute the Borda and Copeland winners- bott derived from the same graph. We then evaluate the true score of each selected winner under the full preference profile and divide it by the true score of the actual winner, i.e., the candidate who would have been selected using complete information. This approximation ratio is averaged over 500 trials, and we report both the mean and standard deviation.
For all the experiments, we set the number of candidates m = 20 and vary the number of agents from 50 1000 in increments of 50. Here, we illustrate the results for the uni- form improvement feedback distribution, and in Appendix I, we surprisingly show that all three improvement feedback distributions behave identically. We also set t = 5, and in Appendix I, we show that the results are quantitatively similar for different values of For each experiment, we iterate over 500 iterations!.
We evaluate the performance of the feedback mechanisms under three different distributions of rankings. The first is the impartial culture (IC), where every ranking in ((M) is equally likely to appear, providing a uniform distribution over rankings. The second distribution is derived from the Mallows model, which is parameterized by a central ranking o² and a noise parameter & E [0, 1]. The probability of a ranking a is proportional to "á((o,a") where d(a,," )) is the Kendall tau distance between and o². As & approaches O, the distribution concentrates most of the probability mass o², while as é approaches I, the distribution converges to the impartial culture. In our experiments, we set é = 1/3.
In Figure 1, we plot the average approximation ratio along with standard deviations. We notice that under the IC model, the two types of feedback--iimpooeement feedback queries and pairwise comparison - behave identically. We believe this is because rankings in IC are sampled uniformly at random, meaning there is no underlying structure or con- sistent patterns for either feedback mechanism to exploit. On the other hand, under the PL model, pairwise compari- son queries provide a better approximation to the optimal score than t-improvement feedback queries, while under the Mallows model, the opposite is true. A posítive explana- tion for these phenomena lies in the differences in how the models generate rankings. In the Mallows model, as the pa- rameter 6 decreases, the rankings converge more closely to the underlying ranking, making it more likely that the Borda and Copeland winners coincide with the plurality winner. Since t-improvement feedback is highly effective at identi- fying the top alternative each time we query candidate a and receive a as a response (indicating it is the top choice) we directly increase a's score relative to all other candi- dates-it excels in this setting. On the other hand, under the PL model, utilities for candidates are drawn uniformly at random, which implies that the relative probabilities of candidates being ranked higher or lower can exhibit more variance compared to the Mallows model, especially when the PL parameters are widely spread out. As a result, the probability that two candidates are frequently ranked close
The third distribution is the Plackett-Luce (PL) model, which generates rankings through a sequential selection process where each candidate a E M is assigned a utility Un > O. The probability of selecting a candidate at any step assign
is proportional to its utility. For our experiments, utilities uniformly at random from the interval [0, 1].
We consider three different t-improvement feedback dis- tributions: (1) Uniform distribution: each candidate in the l-above neighborhood of the queried candidate is returned with equal probability, (2) Linear decay distribution: the probability of returning a candidate in the t-above neighbor- hood decreases linearly with the distance from the queried candidate and (3) Exponential decay distribution: the prob- ability of returning a candidate in the t-above neighborhood decreases exponentially with the distance from the queried candidate.
We construct an estimate of the weighted majority graph using the two types of feedback by making one random query per user. Specifically, for the t-improvement feedback queries, upon randomly querying a candidate a, if the agent returns an alternative b from a's t-above neighborhood, we update our pairwise comparison estimates by adding the pair (b, a). If the agent returns the queried candidate a (indi-
'The code for the experimental part can be found in httpss//gitubb.oom/asiii VatosilisvvOOO/oomputt Voting-Rules- withs-with- Seprovement-Feedback
8

---

Computing Voting Rules with Improvement Feedback
(a) Borda IC
(b) Borda PL Model
Borda Mallows Model
1.00
0.94
0.92
spооx. rato
0.95
eporox
0.92
0.00
0.94
0.90
0.50
parviss unf
24 raise
parniise
S improvement.uu arlf
0.90
Simmrovemeet.uut
2000
200
400
1000
400
500
(d) Copeland IC
(c) Copeland PL Model
(f) Copeland Mallows Model
1.00
0.64
0.05
0.85
0.06
0.60
0.60
300r0w
0.58
0.75
0.92
0.90
parriss
rinse
wise
0.54
0.65
Jnlf
0.88
S-morrvemencc.ur
200
400
600
800
1000
200
400
600
1000
200
400
600
800
1000
number agents
agents (1)
agents
Figure 1: Approximation ratio of the optimal Borda score (top) and the optimal Copeland score (bottom) for different numbers of agents and various underlying ranking distributions, with i under the uniform improvement feedback distribution.
to each other (or even swapped in rank) is higher under the PL model. This increased variance in relative rankings benefits pairwise comparison queries because they directly compare the probabilities of individual pairs and can more effectively distinguish small differences in candidates' util- ities. In summary, it seems that the effectiveness of each type of feedback is inherently tied to the structure of the underlying preference profile.
bine t- t-improvement feedback with other methods, such as pairwise comparisons or partial rankings, potentially over- coming the limitations highlighted in our work by leveraging the complementary strengths of different feedback types.
While negative results hold under the assumption that voters report their preferences truthfully and introducing strategic behavior would weaken these impossibility results, understanding strategic behavior in this setting is an inter- esting future direction as well.
7. Discussion
Our work examines fundamental limitations in inferring collective decisions from restricted forms of feedback, set- ting that frequently arises in real-world applications where full preference information is costly or impractical to elicit. Understanding which social choice rules exhibit robustness under such informational constraints is critical for the prin- cipled design of aggregation mechanisms that are both im- plementable and representative.
Impact Statement
This paper aims to advance the theoretical foundations of decision-making through iterative feedback mechanisms, with potential applications in Machine Learning, Al align- ment, and democratic decision-making systems. Our find- ings are primarily theoretical, focusing on understanding the limitations and capabilities of feedback- based prefer- ence aggregation under various voting rules. As such, the immediate societal consequences of this work are limited to contexts where human feedback is used to guide large-scale automated systems.
An immediate question that is left open is whether our negative results extend to all values of under general t- improvement feedback distributions. Additionally, it would be interesting to explore how the results change when agents are characterized by different t values, reflecting varying levels of effort in providing feedback. Another promising direction involves hybrid feedback mechanisms that com-
One potential societal risk tied to our work stems from the misapplication of the theoretical results. The core of our paper demonstrates that certain feedback mechanisms fail reliably learn voting outcomes in the wors! case, even when

---

Computing Voting Rules with Improvement Feedback
provided with ideal data access. If misunderstood im- properly communicated, these findings could inadvertently justify the dismissal of valuable feedback mechanisms or discourage the adoption of participatory pocision-mmkinn systems in settings where iterative input from users could still provide meaningful outcomes.
Oren, J., Filmus, Y., and Boutilier, C. Efficient vote elici- tation under candidate uncertainty. In IJCAI 2013, Pro- ceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3-9, 2013, pp. 309-316. ICCA/AАAI, 2013.
Ouyang. I.., Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., Schulman, J., Hilton, J., Kelton, F., Miller, L., Simens, M., Askell, A., Welinder, P., Christiano, P., Leike, J., and Lowe, R. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35:27730-27777 27744, 2022.
References
Bajesy, A., Losey, D. P., O'Malley, M. K., and Dragan, A. D. Learning from physical human corrections, one feature a time. In Proceedings of the 2018 ACM/IEEE International Conference Human-Robot Interaction, pp. 141-149, 2018.
Procaccia, A. D. A note on the query complexity of the Con- dorcet winner problem. Information Processing Letters, 108(6):390-333, 2008.
Bentert, M. and Skowron, P. Comparing election methods where each voter ranks only few candidates. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 2218-2225, 2020.
Schick, T., Yu, J. A., Jiang, Z.,, Petroni, F., Lewis, P., Izacard, G., You, Q., Nalmpantis, C., Grave, E., and Riedel, S. PEER: A collaborative language model. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenRe- view.net, 2023.
Brandt, F., Conitzer, V., Endriss, U., Lang, J., and Procac- cia, A. Handbook of compulational social choice. Cambridge University Press, 2016.
Christiano, P. F., Leike, J., Brown, T. B., Martic, M., Legg, S., and Amodei, D. Deep reinforcement learning from human preferences. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017.
Shivaswamy, P. and Joachims, T. Coactive learning. Journal of Artificial Intelligence Research,
2015.
Small, C., Bjorkegren, M., Erkkilä, T., Shaw, L., and Megill, Scaling deliberation by mapping high dimen- sional opinion spaces. Recerca: revista de pensament i andlisi, 26(2), 2021.
C. Polis:
2017, Long Beach, CA, USA, pp.
Dey, P. and Bhattacharyya, A. Sample complexity for win- ner prediction in elections. Proceedings of the 2015 In- ternational Conference on Autonomous Agents and Mul- tiagent Systems, pp. 4421-1430, 2015.
Tucker, A. D., Brantley, K., Cahall, A., and Joachims, T. Coactive learning for large language models using im- plicit user feedback. In Forty-first International Confer- ence on Machine Learning, 2024.
Filmus, Y. and Oren, J. Efficient voting via the top-k elicita- tion scheme: a probabilistic approach. In Proceedings of the fifteenth ACM conference on Economies and compu- tation, pp. 295-312, 2014.
Yang. Z., Jun, M., Tien, J., Russell, S., Dragan, A. D., and Biyik, E. Trajectory improvement and reward learning from comparative language feedback. In Conference on Robot Learning, 6-9 November 2024, Munich, Ger- many, volume 270 of Proceedings of Machine Learning Research, pp. 5389 5404, PMLR, 2024.
Halpern, D., Hossain, S., and Tucker-Foltz, J. Computing voting rules with elicited incomplete votes. In Proceed- ings of the 25th ACM Conference on Economics and Computation, EC 2024, New Haven, CT, USA, July 8-11, 2024, pp. 941-9631 ACM, 2024.
Jin, D., Mchri, S., Hazarika, D.. Padmakumar, A., Lee, S., Liu, Y., and Namazifar, M. Data-efficient alignment of large language models with human feedback through natural language. CoRR, abs/2311. 144543, 2023.
Micha, E. and Shah, N. Can we predict the election outcome from sampled votes? In Proceedings of the AAAI Confer- ence on Artificial Intelligence, pp. 1176-2183, 2020.
10

---

Computing Voting Rules with Improvement Feedback
A. Proof of Lemma 3.2
Proof. Let a, b be the candidates of the statement.
and f < m t, a, b are more than positions apart in both rankings. Therefore, it holds that ProND, 5e 9 (a) b] pr 1 (b) al 0. Moreover, since i > 1 and PronD (a) = a) = PronDe,, lo (b) 0.
Since j j-i
> 1, it holds that
Furthermore, for every E S-bb. the following holds:
ProwDiy (7o-Deyil'a()) = =p
(k) =x]- Pr Pro (i, = x 1 = x²|
k=max(+ (-axxx((t))1) (-1)
m-2
+ (1 - p)
Σ
Pr|T (k) = 2] Pro Dro (a) = x | ab (A) x]
kmm
E
PronDes (0) (8-0t(k) = z]|
P. m
max(ixxi))) (1)
+ (1 - p).
Σ
ProwDes (g - (k)) z]
m 2
k=m-t-1
1
Pi,
m 2
k=max +t,]
m 2
+ (1 - -p) m 2
Pm,
k=m-t-1 t-1
1 m 2
1
(1
m
172 2
where the second equality holds because S-aa is chosen uniformly random, and the second last equality holds because the sum of probabilities of returning a candidate ranked above the queried candidate, over all valid positions within the t-above neighborhood, equals 1.
Similarly,

---

Computing Voting Rules with Improvement Feedback
j-2
Pran-essel = x] = p
Σ
Pr(p = 1) Pro-Das, (1) = x (k) x]
k m-max(j-ii -1)-1
f-1
+ (1-p)
Σ
Pr|t "(k) = =x]- Pro PronDiss (90 = x 7 -6 (k) = x]
k=max (-1,)
j-2
1
Σ
PronDes (b) = x ( = x]]
p m 2
momax(j-t.))-
+ +(1-p)
Pro-Des. (b) - x 7 5 (bk) x]]
m 2
k=max(f-t.)
j-2
1
P' m 2
Pj
k=max(j 1,1)-1
+ +(1- p)
Pi,k
m 2
k=max(E-t)) (f-11)
1
1
1
p m - 2
(1 p)
m
- 172
2
Next, we prove that for p =
P
and every x E S-ab. holds that Pio = a] = Pro (x) = b).
PP
Note that
i+-11
(( a p p.
Σ
Pr( P (k) a) ProwDi (x) 1 7--aa(k) =c]
i
Pro-Deseld (x) = a - = x]]
p m 2
Pk41,
2
k=
p P.
2
where the last equality is by definition of P.
12

---

Computing Voting Rules with Improvement Feedback
Similarly,
2+1-2
Pro-Dese b] =
Σ
Pr(r
x] Pro P.ProDD (m) = =bl (8)))((k) x]
k=j-1
B+1-1
+11 -
Pr( x] Pro ProwDise (2) b -5-00 (k) z]
j+t-2
p
Σ
Pro (x) bl 8- (k:) = x]
m -2
k=j-1
1-p p
ProwDinnelool | 800 (k) = x]
1 m- 2
j+f-2
1-p 8+1-1
p
Σ
Σ Ph+l,e
Pk+2, +
2
m. 1 2
k=j-1
k=l
-
P +
P..
2
- 2
Observe that can make the two probabilities above equal by setting p PP-P--P:- Lastly, for any 2, S-ab it holds that Pro-Das, lgt (z) yl Pr Pro-paze (x) y). since the two preference profiles differ only with respect a, b. From all the above, we get that Daj,, and Dogeh are t- t-mnistinguushable by setting p stated in the lemma.
P
B. Proof of Lemma 4.1
Proof. Given D, where, without loss of generality, scy(a, D) > scz(b, D), we construct a family of preference profiles (D)) in the same way in Lemma 4.1 of Halpern al. (2024). Briefly, we sample a permutation over the candidates uniformly random. If (b) c, sample ranking from Daesh; otherwise, if (b) # c, we sample ranking from D. When scy(a, D)= > scy(b, D). Halpern et al. (2024) show in Lemma 4.1 that c is the unique score maximizer in D
It remains to show that {D* Jeear are l-indistinguishable from one another. Note that if D and Da are l-indistinguishable, then π o D and π Darsh are also t-indistinguishable for all T. Consequently, for every D and D and for all x, y E M, we have:
Pr Dn
(4o (x) =y]
Σ
Pr
(x) = y) m!! +
Σ =EC(M)==(()=c
Pr a (c)( = 5)] (x)
1
oniTOD
m!
(b)
Σ
Pr
(x) y]
m!
TEC(M)
Σ
Pr
l0' (x) = =y]
+
Σ
Pr a
(c((x) = =y]
m!!
mn!
TEC(M) Jm (b)
(EC(M)
Pr (x) y), aNDe
where the first and third equalities follow because и is chosen uniformly at random from L(M) and the second and fourth equalities follow from the fact that π o D and π o Dat>b are i-indistinuuisaable, and the lemma follows.
13

---

Computing Voting Rules with Improvement Feedback
C. Proof of Lemma 4.3
Proof. First, we note that sCepta (a, -) = Pro--lo = = - Pro-Dlq'(a) = al. where the second equality is derived from the fact that when a is the top choice of an agent the agent just returns this candidate. Since the algorithm knows Pro~Dla' (a) a}. the plurality score of candidate is computable.
Second, note that
E bEM
Pr and
(b(()
=a a|=
m min(m.i++)
E
Σ
Σ
p/ss anD
Pr lo (a) i (b) -
DEM
F=i-1
min(m,i+t)
Σ
Σ
Σ
Pi Pr la = i =
anD
F=H
(a)
min(m.+t))
Σ
Σ
Σ
Pr la (a) = à (b)
Pr lo tb) 5] onD
Pis
onD
FH1
(a)
min(m.itt)
Σ
Σ
pjs Pr (a) = anD
1=
1=
Σ P
Pr )~D)
(a)
l
(a)=
=1 SC,7 (a,7(a,))) D).
where the first equality follows from the definition of Pr Pro-. la' (b) = a). the second equality follows by rearranging the summations, the second last equality follows from the definition of P. and the last equality follows from the definition of s7. Since the algorithm knows the quantity Pr (1% (b) = al for all a, b E M, it can learn sea; (a, D) for every E M.
The lemma follows by noticing that for each 5 A1 5ptu + X2 57, from linearity of expectation we have that scz(a, D) A1 pC (a, D) + X2 sCs, (a, D) for any A and A2-
Proof. Let a, b be any two candidates and = (si...., sm) be any positional scoring rule.
We will first define an additional family of preference profiles, denoted D; which will be used to prove impossibility results for the uniform t-improvement distribution.
Lemma C.1. Let Dg be preference profiles that are defined with respect to two candidates and b, as follows:
1. With probability p. candidate a is fixed at position i, and candidate b is fixed at position i + 1, where mar(2, m - t) S
< m -1 1.
2. With probability 1 - p. candidate is fixed at position m, and candidate is fixed at position m
3. Select a uniformly random ranking S over the set of all remaining candidates (excluding and b). This ranking determines the relative order of the remaining candidates, which are then placed in the positions not occupied by or b.
For any E (m- - 11. in the uniform t-improvement feedback distribution, the preference profiles D, and Dattb are min(i.t)
t-indistinguishable, when p E+mon(),0)
Proof. Let b be the candidates of the statement.
Firstly, we need to show that ProwD, lg (a) = b] = Pr,-D, lgt = a]. Under the uniform t-improvement feedback
distribution, with probability p. candidate a appears immediately above candidate b in the ranking. In this case, candidate b
14

---

Computing Voting Rules with Improvement Feedback
returns candidate a with uniform probability over the l-above neighborhood positions, which is minti.r) Similarly, with probability 1 - p. candidate appears immediately above candidate a in the ranking. In this case, candidate a returns candidate over the t-above neighborhood positions, which is :. By construction of De, these two probabilities are equal for the choice of p min(i, 1)/(1- + min(i,
Now, notice that when querying a candidate I E S_ab, the agent can return or b only if x is ranked at some j > i+ 1 when a is at position i and b at position ? 1. Since i 2 max(2, m t), under the uniform t- t-improvement feedback distribution, querying any candidate x E Saab ranked at position j > + results in the agent returning a or b with equal probability, which is 1/minljj - 1,4). Hence, Pr ProND, 1 (x) = a| = Pr Pro.D, D. 1n' (x) b].
Moreover,
TroDD,lbl0 = =x)
= =p
Σ
Pr(p = =x] Pro D. (b) = x (k)) = xx]
k=i- 11
+ p1 2
Pr|p (k) = =x]- Pr br. = x ) = x]
k=m-t-1
Σ
Pr PronD,laa(0) (b) = x 7 (R)) = x]]
=p m- - 2
k=j- miimmmn(i.)++1
m-2
+ (1 - p)
Pr PronD, (b) = x 7 (A) = x]
m 2
kmm-t-1 t-1
p m11 (mi-min(i.))+1
1
Σ
P1+1, + (1 (1-p).
1
Pm-1. 1,k
m
k=
1
min(i, t) -1
1
P m 2
+ (1 - p) m 2
min(i,t)
where the second equality holds because - is chosen uniformly at random and the last equality holds since each agent returns every candidate in the l-above neighborhood with the same probability. Similarly,
Pr Pro-D, (a)(a) = x] pp. p.
Σ
Pr(p5-ob(k) =||. Pr (1)(() = x (S-a((k) m]
k=i- 1,t)
m-2
(1 p)
Σ
Pr(p--et (k) = x] Prowb, (1) x -S-ot(k) (k) = m])
k=m-t
Σ
Pr ProwD (a) = x 1- 5- ab (k)) = x]]
p'' m - 2
k= min(i-111)
+ +(1- - -p).
1
m-
Σ
Pr PronD, (a) =x 5-00 (k) = x]
m - 2
k=m-t
= =p. m- - 2
1
Σ
Pi + (1 p) m
1 m
Σ P
k=i-min(i- 1.t)
1
t-1
=p m 2
+ (1 - p)
m - 2 t
15

---

Computing Voting Rules with Improvement Feedback
Therefore, have Pr Dr 16 =] Pr Prow lab (b) .r. for the choice of p min(i, 0/(( + min(i,
Lastly, for any y, E Sab holds that Pr Pran 1 (z) yl Prannuen (x) (z) y), since the two preference profiles differ only with respect to a, b. From all the above, we get that Dj and Dets are t-indistinguishable by setting p as stated in the lemma.
We will continue with the following three lemmas.
D. Proof of Lemma 4.5
Proof. Consider the preference profile D 5+,,, stated in Definition 3.1. From Lemma 3.2, we get that for every p
E [2. (2....,m.. m D Dimii+1 and s,m,+1 t-indistinguishable for every value of S if P.-P..
P
P it holds that scs(a, Dim,++1) > sca(b, Di.m,++),, for some E , - - 2}. then by setting Dimi++1 the statement of the lemma is satisfied. Now, suppose that for every i E f2...., m 2}. holds that scy(a, Dimm.it) sc, (b, Dim,i4)) This means that
8
8 = (1 (1-p) 8i+1
8141
Therefore, we get
[+1
8441
8i+1 P ++1
84
p
Pt. Pit1
8, + 8141
pi
and result: s/p: x for all E (2...., 1- 1} and the lemma follows.
Lemma D.1. If s P. = μ does not hold for all i {max((, (2, m - t)......,,,, m 1) for some μu, then there exists a preference profile D such that sca(a, (a, D)= sca(b, D), and D and Datsb are t-imdistinguishablee, for every & [m 1].
Proof. Consider the preference profile D, as stated Lemma C. From Lemma C. we get that for every E {maz((, m min(i.t)
()...., m 2], D. and Due=b are L-indistinguishable for every value of I, if E+mm)(i,t) Under uniform l-improvement feedback distribution, we know that pt we have
p and P P = min(i.)) for all E {max((2 m i -t), ; 22- 2}. Hence,
pt m-
min(i, 1/2 1/min(i, + min(i,
1/1
P
Pit1 +
PL Ph-1
for some E (marx(2, m - f)..... ... m 2}. soz, (a, D.) > scy(b, D.), then by setting = D,, the statement of the lemma satisfied. Now, suppose that for every E {max(2, (2, m t),... ......... m 2), scz(a, Di,m,tt1) scy(b, D Dimm,t1).. This means that
8m-1
p. = 8 (1 p) 8m p=
St 8:11 + Sm-1
Therefore, we get
pt
P. P
8m
8; 81+1
p p
P + pt m-1
8i 8i41 1 + 8mn-1
8m-1
pt m-1
pt pd
Now, observe that, substituting i -m-2inn the above, we get 8m-2 -m
which implies that
8m-2
8m
Pt.
pr
m-
pr
By induction on i, we get for all {mar((2 m ................................ ., m 1}. that
and the lemma follows.
Lemma D.2. If s. pt ffrr all E f2...., m-t - 1} for some X and sa/ Pt = μ for all E {max((2 m m-t)...... m m-13 for some p. and μ + X. then there exists preference profile such that scz(a, D) > scg(b, D), and D and Dotsh are t-indistiguishable.
16

---

Computing Voting Rules with Improvement Feedback
Proof. First, we note that when L m 1 or m 2, from the hypothesis of the lemma we directly get that <b/P3 -... = sy 6m-1/ P Pm-1= = p.. Therefore for these two cases the lemma directly follows. Next, we focus the case where S. m 3.
Here we consider the following preference profile, denoted by D:
1. With probability p. candidate a is fixed at position 2, and candidate is fixed at position m.
2. With probability (1 (1-P) 11/2, candidate a is fixed at position 1, and candidate b is fixed at position m - 1.
3. With probability (1 (1-p) 21/2, candidate a is fixed at position m, and candidate b is fixed at position 1.
4. Select uniformly random ranking م over the set of all remaining candidates (excluding and b). This ranking determines the relative order of the remaining candidates, which are then placed in the positions not occupied by a or b.
First, we will show that D and D are t-indsstnguuisabbl. Since in all the cases a, are more than m -3 positions apart. it holds that Pro & (b) = a| = ProwD % (a) b] = 0. Furthermore, Pro- lo6 (b) = bj Pr D (a) = aa P.
Next note that for any x E S ab. it holds that
= x| ProwD (a) = z] = p- Pr|r (1) = 2] (ro-Dla م (1)=
+ (1 (1-p).
m-2
Pr|75-at()) =x] PronDla x (k-ah(k) x]
2 kmm-t--
PronDl = x -S- (1) x]|
p m- 2
+
(1
- p)
1
2
PronDly (a) = x 7 s = x]]
2
m - 2
k=m 1-1
1
(1
- p)
1
m-2 2 Σ
p P2,1
pm,
m
2
m
k=m
(1
2(m - 2) p)
p+1 1
= p m 2
2(m 2)
where the second equality comes from the fact that S is picked uniformly at random and the third equality by the fact that each agent returns a candidate from the t-above neighborhood.
Similarly, for any x E S-ab. it holds that
2
Pro-DIgh Ig' (b) = x2 = p
Σ
Pr|75-ab ab (k) = =x]. Pro = x (k)) = x]]
A 1
(1
p)
m
P (k)) = x]. Pr ProwDPr(g't0 x -5- (x)) x])
2
k=m -tt-tt- 2-2
1
Prow la' (b) = x (k)) x]]
p
m -2
k=m-t-1
(1- p)
1
m-
Pro (b) = x
- (k) = x]
2
M
k=m-t-
1
m-2
(1-p)
1
3
p m- 2
Pm,,411
p pm11.
2
m- 2
k=m-t-1
k=m 2
+ (1 p)
1+1
= p m- 2
2(m - 2)
2(m - 2)
17

---

Computing Voting Rules with Improvement Feedback
Therefore, have that ProwDlubb()) = x| = Pro Pron (b) =| for all S-bb- Next, we see that
Pro-Dlo((x)=d) = p Pr( (k)) (k) x (2) = a (k)) x]
2=2
1-
Pr(s as (k) x] Pr (rowDl = a 7 (b())) z]
H+1
Pr (1) = a 5 (l()) = z|
= -p m -
k=2
1-p P
(1)) = a 1 78-0 = x]
2
2
1+1
p
Σ
Pk+12 +
1-p 1
Pk+111
M
2
m- k=1
1-p
1
= p m 2
P2
Pf
2
m
where the second equality comes from the fact that 7 ab is picked uniformly at random and the last equality by definition of P. Similarly,
Pro=Dl<(())=))
b]
1-p
p
Σ
Sa = x] Pro- = (k- (k) x]
2
k=1
1 1-p,
Pr( S- (m- 2) = x) Pr ProwDlu (1 b ~ (m 2) x]
2
1-p
p
1
(ranple(()) = b | (aaa)(k)) (k) = x]
2 m
2
k=1
1-p
1
ProNDle' (x)
7 S-ah (m 2) ø|
m
2
1
1-
1
-
pk+1,1
Pm.m-
2 m
2
2
2
k=1
1
1-p
pl
1-1 p
m 2 pt
2 m -
2
2
m-1
Therefore, get Prow (96 (x) a) ProwDla = b] when p r 11-1/12nt p and then D and Doesh become t-indistinguishable
it holds that scz(a, D) # scz(b, D) then the statement of the lemma is satisfied. Now, suppose that scy(a, D) = scy(b, D). This means that
1-p p
1- p 81 +
1-p 8m-1
8m-1
pt P. + Pt.
p.82 82 +
81 =
2
2
2
2 82 + 8m-1
Fort S m - 4 we know that s2/p3 = and 8m-1 -1 = μ. Then from the above equality we get μ = X. For = m - 3 we know that s8/rg- = ... 8m 1/pi-1 = p and the above implies that s2/p3 53/15 = ... 1/ri = μ4, and the lemma follows.
From the above lemma we get that, unless $1 À for all i { 1}, which implies that 5 span 37). there
18

---

Computing Voting Rules with Improvement Feedback
exists preference profile D satisfying the conditions of the lemma and the lemma follows.
E. Proof of Lemma 5.1
Proof. We use the same construction as in Lemma 4.1 by Halpern et al. (2024), which we briefly restate here for completeness. For each e E M we define D as following: we pick a permutation a uniformly at random. If π rb)) = c then we sample a ranking a ~ т o Da++b, If π (6) + e then we sample a ranking a ~ π D. We need to show that the two following statements are true: (1) Pro-De >a -] ProwD far >o c), for all æ E M \. {c} and (2) {D* JCEM consists of m t-indistinguishable preference profiles. Firstly, we turn our attention to (1).
Fix any E M \ {c). First note that,
Σ
lc t x T(b) 21 Pr(m(b) 2] anDe
Pr
((,2))
(Pronpla (T (x)) (b) = 2] + ProND(T (c) > b (b)- = =])
(c)
ProwDlato y π (z) = y, (b) = 2| Pr(n (x) y x(6) = 2]
VES
ProNDla >o b n a m()) = =] Pr|= (x) =
( 1 =]
Σ Pronply>o (c) b = y. (b) = z) Pr|x (c) = y T(6) = =]
VES-ab
ProwDla to (c) = z] Pr|T (c) x(b) = 2]
1
Pro-Dla>a21 I]
Σ
Pro-Di
m (m 1)
(EM)(a)
(EM)(()
1
Σ HaM
Pro-Dla>o214
Σ (EM
(1- PT-DDob to zl)
(2)
(m- 1)
where the second equality holds, since æ is a permutation selected uniformly at random and conditioned on x(b) = C,
= π o Datt and conditioned on (b) = x, D = π D. The second last equality holds again from the fact that π is a permutation selected uniformly at random and that D is independent of x.
By the same reasoning
also argue that,
Σ
Pr I F e T(b)= = =]. Pr(z(b) =
=E(c,))
Σ
Pronple t a a]+ E
Pra-nbboo
m. (m -1
*EMi(h)
1 am-(m-- - 1)
Σ
(1-ProwDla x!) + Σ
PronD(b>o
(3)
xEMMMa}
zEMr(6)
By combining Equation (2) and Equation (3), and the fact that Σ EveMriat ProwD(a to x ExEM),6) ProwD x). we conclude that
Pr P1 2] Pr(=(b) - 2| xE(c,))
Σ
Σ
Pr lo c/ 2] Pr( =
Pr
(4)
=E(c,))
19

---

Computing Voting Rules with Improvement Feedback
Next, note that
E
ProwDelo>o x m(6) = =| Pr(T(b) z]
Mo,)
E
(TannT ta n (x) x(b) = m
xEM)(sn)
1.
Pro-ply Fa 1/ π (c) y, ( = = (T() =
m
(o)
Pr( 1, (z) = // =(b) =]
Σ Pra-Dyy>oal (c) y, (xx) - a,, = 2| Pr( Pr(m-((c) y/ (x) x(6) = =]
yEM
Σ t
(c) 0
a, a, (x) - U/ mb) = =] Pr(n P = a, (x) M(6) = =|
yEM
Σ y.
ProNDlu 3/+
E BEMMaa
Σ MEM
PronDla to y)
m(m 1) - 2)
(5)
where the second equality holds, since æ a permutation selected uniformly at random and conditioned on (b) & {c, x). D D. The last equality holds again from the fact is permutation selected uniformly random and that D is independent of æ.
By the exact same reasoning, we get that
Σ ProNDelD to cl (b)) 2] Pr(T(b)
xc,)
Σ
Pronply
to +1+
Σ
ProwDla>o v1+ Σ
ProwDlyrod)
m - 1m - 2)
V.''MM(e
BEM(/a}
DEMi(a}
(6)
From Equation (5) and Equation (6), we get
Σ PranDoc ta x (b) = 2] Pr(x(b) = =
Σ
PronD > c((bb = 2] Pr(T(b) = =]. (7)
ZE =(,
Lastly, by combining Equation (4) and Equation (7), get ProwDe x) > ProNDe fr >o as desired.
As for (2), we already have shown in Lemma 4.1 that the family of (D* consists of preference profiles that are all l-indistinguishable from one another. Hence, the lemma follows.
F. Proof of Lemma 5.2
Proof. We will distinguish into the following cases:
Case 1:2 < / < m - 3. Let D3,m,2 2 be the preference profile defined in Lemma 3.2. Since 2 < m m- for p T% + the preference profiles Ds,m, and 3,m,2 are t-indistinguishable.
Under D3,m22 we have Prow (a >o b) = and Pro-
[b >o a) p. Additionally, for each ab
20

---

Computing Voting Rules with Improvement Feedback
have that Dro.Ds...a -o x = p m=4. since with probability p. appears at position 3, followed by b at position m.
and the remaining m 2 candidates are uniformly distributed across the remaining positions and with probability (1 p),
appears at the last position. Similarly, we have Pro-Ds.m.3 >~ x| (1 (1-p): m-3 m-2 since with probability (1 - p),
b appears at position 2, followed by a at position m. and the remaining candidates are distributed uniformly, and with
probability appears last.
Thus, we have that
Σ
Pr Pa anD D
E
Pr ow))
Pplax Lo a]
Pr la
> >o b|
Σ
m-2 P p (m - 3) p.
own)
[a)
xES-ab
=ES
and similarly, for b, we have:
b 2|= anD
Pr
E
Pr Pr
I]
Pr Pb 12. a|=
E
m 3
(1 (1-p) + +11 - p) = (m 2) (1 p).
anl)
anD)
m 2
(a)
xES-
DES
Next, we show that
PS p
P
171 2
P
2P
1
2m
- 5"
where the inequality follows from the fact that, under the uniform t-improvement feedback distribution, for t 1, we have that P Po- 1/2 + 1. Then, this implies (hEM Pro-Dla do æ] EneM((a) Pra-Dlb >o æI. as desired.
To ensure that
m-2 we need:
2m-5
P
m 2
2P
2m - 5
2m P2 5P2 > (m ()P 1/2 + 1/1
2m P1 -5P > 2m P2
m/2 + m/t 4P + 11-2/ 2/2
PS
m
2 1+
2
(m 2)1 1 1
t
Under the uniform t-improvement feedback distribution, we have:
1 p +
1
t = H 1+ 2
= 2 3
8
where H3 is the k-th harmonic number. Using the inequality H₁ S In(k) + 1, we get:
2 P1 S In(t 1) t
Since, Pj < In(t 1) - 2.
it suffices to prove that: In(t - 1) + ? < (m 2)(3 - () or in(-11) m < m-2
2
We prove that for any value of m 2 13 and 3 < / < - 3, this is true, follows:
We have that In(t - 1))+ < In(()+ + 7. Let f(t) = In(1) + .. Then (t) = 1/2-//// Hence, f'(m) = 0 and for every 0 < t < m, ft) < 0. Therefore, f is monotone decreasing in (0, m). As a result, f(t) < f(3) = In(3) + m//. Now we need find m such that In(3) + 3 m-2 or m > 6 In( + 6, or m 2 13. This concludes the proof of the case.
21

---

Computing Voting Rules with Improvement Feedback
Case II: 1 E (1,2}. We define the preference profile D as following:
1.
With probability p. candidate a is fixed at position 2, and candidate b is fixed at position 5.
2. With probability p. candidate is fixed position 6, and candidate b is fixed at position 3.
3. Select a uniformly random ranking S over the set of all remaining candidates (excluding a and b). This ranking determines the relative order of the remaining candidates, which are then placed in the positions not occupied by a or b.
First, we show that D and Dast are l-indistinguishable Note that since S 2, we get that Pro-D (a) bj
(b) a| 0, since o, b are more than positions apart. Furthermore, for each S we have:
PrawD(do(a) = x]]
pp. Pr(f = x) Pr ProNDle' = x
x]
+ (1 p)
Σ Pr|p ab (b) = x]. Pro-D Pra-Dle (a) 7- (A) x]
1
Pr PronD do (a) = x S -- (1) = x] + 1-p p
Σ
(ro = x
- (k) = x]]
=p- 1- 2
2 k=5-t
1
1- p
Σ
p.
P2,1
+
Po,
m -
171 2
k=5-t
p 1 p
1
m- m
2 m - 2'
where the first equality is because S ab is sampled uniformly at random and the last equality is since each agent returns a candidate in the t-above neighborhood of the suggested candidate. Similarly,
ProND(e((b) z]|
Σ P ub (kb) = a| (ro) x 7 *((b)= =x] z]
=p.
k=4-t
+ (1 - p)
Pr|sS (k) = x] Pro = x S mkk)) xx]
3-
3
P
ProwD (o (b) = محكم (k) x|+ + 1 1-p P
Σ
ProND = x ( z]
m 2
m 2
k=1-1
k=3-1
3
1- p
po,++1
1
+
P3,
- 2
2
k=1-t
k=3-1
1
p
1
- 2
2
m7
2
22

---

Computing Voting Rules with Improvement Feedback
Furthermore,
(To = a)
14t
Σ Pr(y (0078-o0(k)) (k) =x] Prowolet(T) (k) x]]
=p.
k=
min(m,441)
+ p1-
17178-0t(k3) x] ProwDlu((1) = a (k)) x]
5=
1+1
min(m,441)
P
Σ
Pro-Dlde (e (x) = - = x] + 1 - p
Σ
(ro = a (k)
- = x]]
2
k=2
R=5
1
P + (1 p) p) Pb).
m - 2
where the last equality is by definition of P/- and the second to last is from the fact that - is picked uniformly at random. Similarly,
min(3+t,m))
ProNDiEd 1o = -b] = p
Pr(p = =x] Prow = bb /5-ah = x]]
k=
2+1
+ (1 p)
Pr(p (k) x] Pr 14o (x) = b - (k) x]
mmn(3+ttm
p
Prownlub(1) = b 78 (k:) x]]
m-
2
2+1
1- p
Pro D 1/6 (x) = a6 (k)) = x]]
m
k=
1
(p- P5 + (1 (1-p).1 p))
m 2
For getting Pr (1) a) Pr D (x) b). we need prove that there exists value of p such that: p PS + p1 Pg = (1 p) P3 + p. Pg.
P for any value of p. If m = 7 and f = 2, then P = Pt 1 and Pj- 1/2 and the above holds for p= 1. Now, we focus on the case of m = 6. this case, if t = 1, P1 = P = and P = 0, and the above satisfied for p = 1. If = 2, then PS P3-
Observe that for t = 1 and any m 2 7 and for t = 2 and any m 2 8 it holds that: P3
P. 1/2 and P
and the above is satisfied for p 3.4 Thus, D and Datsh are t-indistinguisaall.
We have shown above that in any case, there is value of p 1/2 such that Pro- ol (x) a] ProwDla' (x) b). This immediately implies that, Pr Pro-D(a > a b] = > ProwD [b >o a] = 1 p. Furthermore, for E S-ab it holds m-5
6 that Pra-p(a >a x] = 2 p m-2 (1-p) and Pro-D(b >a x] m-2 p = (1 p). This is because with probability p. candidate a is at position 2 and b is at position 5, so a candidate x below is sampled uniformly at random for the remaining m 3 positions. Similarly, with probability 1 - p. candidate a is at position 6, so a candidate x that is ranked below x, sampled uniformly at random from the remaining m 6 positions. Similarly, with probability p. candidate à at position 5, so is sampled uniformly at random for the remaining m 5 positions. Furthermore, with probability 1 p. candidate b is at position 3, with a at position 6, so is sampled uniformly at random for the remaining m 4 positions. Now, for the final step of the proof, need the following inequality to be true:
23

---

Computing Voting Rules with Improvement Feedback
Σ
Pro-Dla>o
Fo
Σ
Pro-Dbbo xi.
zES-
m P+ m - (1-p) > Σ
m p m m-2 (1 p)
-
ab
ub
(m - 3) + (m - 6) (1 - p) > (m - 5) p (m - 4) p)
= 2.p >> 2 (1 11-p)
- p>
As have already shown, in any case, p 1/2. This combined with the fact that Pra-D >o b) Pro-D(b>o a). yields [x) Pra-Dla >o x] Emear(()) Prowo(b >o æ/., which concludes the proof of the case.
{m - 1, 2, m - 33. Let max(2, m - t). We set preference profile D D:, where D; is the preference profile from Lemma C.1. Hence for p ++1 < 1/2, which holds for 2 m and m > 6, and D (-indistinguishable. Observe that ProwD >a a] = - p and Pro-p(a > b] p. Moreover, for each Pro-Dja > z] = p m-i-1 as, with probability p. appears at position b appears position + 1, and then all the remaining candidates occupy the remaining m i positions uniformly at random. Furthermore, with probability 1 candidate appears at position m. Similarly, Pro >a x] = m-i-1 Thus, we get that
Case III:
SSab-
m m-i-1
Σ (a)
Paspla>a0
Σ xES-ab
Pra-pla >o x) + Pranpla>all
E wES-ab
p 1 P. 2
m
and
Σ (BM)(6)
PranD b x
Σ
Pra-nb>> x| + Pro-nbro
m 2 p p. (aM)(a
Σ
#ES_ab
Now, since p < 1/2, it follows that ExEMMA) PronDlb to x) > Ezenr(o) ProNpla >o x] and this concludes the proof of the case.
G. Proof of Lemma 5.4
Proof. We start by considering the preference profile Di,,,i+1 from Definition 3.1 for any i E (2...., m - / - 2}. From Lemma 3.2, we get that Da and Datib i,m,++1 are t-indistinguishable when P a/// P(y)). Now notice that
m-2
Σ
Pro-Dim.nilaa
Σ
Σ Pr( (r) 2] p Pro Dr > b]
(b,a) r=1
m 2 i+1
Σ
m m-3 2 p == -m - -i) .p.
sEMi(bl))
24

---

Computing Voting Rules with Improvement Feedback
and
m
Σ #EM\1b)
Pro
b>
E
Σ
Pr(r ob ((r)= = (1 p) DiinDim a|
(bb r=i+1
m 2-2- (1+ p) (1 p) (m (m--i-1)
m m-2
REM((0.)
If for some i . - 2}. we have that (m i) + (m-i-1) t-indistinguishable, by utilizing Lemma 5.1, we can construct a family of preference profiles (D")ee with m distinct Condorcet winners that are t-indistinguishable. Then, by applying Lemma 3.3, we get the desired result.
p), since Di. and Dam are
Now suppose that (m- -)- p (m 1) (1-21 p) for all i E (,....,
23. Then, since p Pits/(Pt + P(+s),
conclude that
P!
m
Vi = m2....,m-t t-
(8)
Pt
1
Next, we consider the preference profile D2,m-1s422 for any IE [l,...,|+1] Since S m/2 - 2, from Lemma 3.2, we get that D2,m-i,i42 and Dotth Li+2 are t-indistinguishable when P/1 2/15 p + 2(t)) Next, we see that
2 Pr(rS-ab (r) = z) p+ Pr Pra-Da > b]
Pro Pra-Dammiup 2 x|= (EM
Σ
E
Σ
(b.a) r=
2--2 - 2+1
Σ
p p (m -2 2) .p.
m
(EMa(b
and
E
Dam-Dlliia x]
(b)
m-3 Σ
Σ
Pr|75-bb/ =.].P
(baa r=m-i-1
Σ
Σ
Pr(75 (b)r 1] (1 (1-p) p) + ProwDe.. D2.. 41 aa >o a]
3E (b.n)) r=i+2
m 2 - (m 1) +1 p+
m - 2-2- (1+ +1 m m
Σ
(1-p) p) + (1pp)
11 2
(b.a)
(bb
= (m - i- 2) (1-p))
f 1}. we have that (m - + (m----m----))) - we can construct family of preference profiles {D"}eE with m distinct Condoreet winners that are t-indistinguishable and by applying Lemma 3.3, we get the desired result.
As before, if for some E {I....,
(1-p), by utilizing Lemma 5.1,
Now suppose that (m 2) p-pp- i- P (m i i- 22) (1 p) for all i E fl,..., tt..,,t 1}. This means that p 1/2, and since P/42/(P3 pt. + 2) we get that P P Pý P.tz. Since S m/2 2 and ///r = (m -1/(m for all
25

---

Computing Voting Rules with Improvement Feedback
E m?...., 2}, conclude that
P m--
P2
m
(i+ -
P2: 2
Wi ++,1
(9)
Then, from Equation (8) and Equation (9), we get that the only case that we cannot construct two profiles with the desired property is when P/ P//p/ = (m 11/(m - i- 1) for all i { - 2), and this concludes the lemma.
H. Condorcet winner and Deterministic Algorithms
First, we discuss in detail why the negative result of randomized rules cannot be extended in the case where Pf/Pi (1mmm---1)) i- 1) for all i E m 2).
(m 11mmmmmm--
well-known that the Borda score of candidate e M is given by Exeny Pro-ple>o x] (Brandt et al., 2016). candidate is the Condorcet winner if Pro-Dle 7o æ| > Pro~D(æ >a c| for all æ E M \ {c}. This implies that when e is a Condorcet winner, then ProwD(e >a x] > 1/2 for all x E M (c), and therefore, the Borda score of c must be strictly greater than
Now, assume for contradiction that we have a of m preference profiles {DT) that are t-indistinguishable from another, and suppose is the Condorcet winner in D This means the score of c in D must be strictly greater than .......,P
2), then we have that Borda & (ppnn s7). Therefore, from Theorem 4.4 we get that we can learn the Borda score of all the candidates. With similar arguments, as in the proof of Lemma 4.3, we can get that
m-1
When 8 (Pf. ....... Pt. where Pi Pi/Pt,, = (m - 11/(m i- for all E (2....,
8CgBarda D)
(m Pf. Pr 1r ()) (m- Pr lo (a) =1] onD
i=1
Σ
Pr onD (b) = + (m - -1 - 1() Pr oa (a) = =a. anD
bEMMa
(b) a) for any a, e, d' E M and therefore from the above equality, we get that that each candidate must have the same Borda score across all m preference profiles. Consequently, in any preference profile, the total sum of scores for all candidates would be strietly larger than m. mn However, this is contradiction because the sum of Borda scores of all candidates in any preference profile is exactly equal to m m_ Therefore, such family of preference profiles cannot exist for this case.
From the definition of indistinguishability. we have that Pr o)) Pr
Next, we show that for S m 4, no deterministic rule can identify the Condorcet winner under any t-improvement feedback queries.
Theorem H.1. For any m 2 6 and any t S m - 4, no algorithm with access to feeepro queries can identify the unique Condorcet winner.
Proof. Consider the following preference profile D:
With probability 1, we select D2,m,3 from Definition 3.1.
With probability 1. we have a > b > S-ab, where S-ab is uniformly random ranking over all remaining candidates.
With probability 3. we have b > 8-ab, where S-ab is uniformly random ranking over all remaining candidates.
Since t S m - 4, by Lemma 3.2 and the construction of D, we have that D and Datth are t-indistinguishable when p =
pd in the construction of Da m.,, Note that for each E S-ab. ab, we have Pro- >a > Pr > x] >
PS+P3
26

---

Computing Voting Rules with Improvement Feedback
Borda
IC
(b) Borda Model
Borda Mallows Model
1.00
0.96
0.94
0.99
sporow. ratt
0.92
0.90
0.94
0.90
pMrwise
S-morevameent.u
0.00
mmprovmmentlin
0.84
S innproveeer..nn
Simprovam enc.In
mpprovement.xxp
0.82
5 improvemen..oo
S Simoroaament wwrooovmmen...oo
2000
400
(d) Copeland IC
(c) Copeland PL Model
(f) Copeland Mallows Model
0.64
0.00
0.06
0.60
0.60
30000k
0.58
0.75
parrite
28 rwice
patrwise
biinpooweeer...r
0.90
Semproowm mitarif
-mmpronmmenniin
iimproveeerc.nn
seincrovemen.l ent
0.54
0.65
0.88
200
400
600
800
1000
200
400
600
1000
200
400
600
800
1000
number
agents
agents
Figure 2: Different (-improvement feedback distributions
If A J. then Pro~Dia to 6] + PIo-D >o a], implying that one of a or b is the Condorcet winner. However, since D and Daesb are t-indistinguishable, no deterministic algorithm can always output the Condorcet winner.
On the other hand, if p 7. we have Pro-D (a > b] = Pro-D >a a). However, Pra-D(a > x] >> Pro-D >a x] for all x E S-aab. because, in D2,m,3, with probability 1/2 1/33 = 1/6, a appears in the second position and in the last position, while with probability also 1/s, b appears in the third position and a again in the last position, with all other candidates arranged uniformly random. Hence there is one position (namely, position 3) where æ can be below but not b. this case, by utilizing Lemma 5.1 and Lemma 3.3, winner with probability greater than 1/m. Therefore, no deterministic rule can always find the Condorcet winner, and the theorem follows.
show that even randomized algorithm cannot find the Condorcet
I. More Experiments
In Figure 2, we present the approximation ratio of the Borda and Copeland scores across the three different ranking distribu- tions and under the three different 6-improvement feedback distributions. We observe that in all cases, the approximation ratio is similar.
In Figure 3, we illustrate the approximation ratio of the Borda and Copeland scores across the three different ranking distributions for varying values of t and n 500. Once again, we observe that the results do not significantly change for different values t. However, in some cases, we observe that the approximation ratio improves as increases.
For our experiments, we used the Python package pref-voting.
27

---

Computing Voting Rules with Improvement Feedback
(a) Borda IC
(b) Borda PL Model
Borda Mallows Model
0.88
0.952
0.960
0.995
spprox. Fanl
0.958
40ppox ratlo
0.84
вpрск rato
0.990
0.82
0.95
0.80
0.980
0.952
improvement,nif
0.78
pairwise
Improvement.onf
0.975
inpernseeenttar
(d) Copeland IC
(e) Copeland PL Model
(l) Copeland Mallows Model
0.64
0.88
0.62
0.86
0.995
rato
Approx Fallo
0.84
39prox. 1850
0.905
0.58
0.980
pa mwrmiss se
0.78
pairwise Improvement.unt
pairwise improvement.ant
inarovement.unt
12
12
Figure 3: Varying values of t
28


Reviews:
[{"review_id": "2cABZnyFZC", "reviewer": "Reviewer_5Qt1", "summary": "The paper studies the concept of \"improvement feedback\" within computational social choice. Improvement feedback is a response given to a query of a specific voter asking a question along the lines of \"which candidate do you prefer over x?\" The main question of the paper is whether queries in the improvement feedback setting provide enough information to compute the winner of various voting rules.\n\nThe paper provides a few possibility results: It is possible to compute the plurality winner and any positional scoring rule between plurality and a specific scoring rule determined by the setting itself. The paper shows that every other positional scoring rule cannot be exactly computed using this framework. Similarly, it is shown to be impossible to compute the Condorcet winner.\n\nExperiments show that while it is impossible to compute the winner of many voting rules in theory, it is often possible to do so in practice. Using improvement feedback to estimate the winner of the Borda and Copeland rules shows that across three different preferences profiles, it is frequently possible to achieve a high accuracy at estimating these rules. Improvement feedback is compared with the accuracy of estimating these rules using pairwise feedback and shown to be more accurate in some settings/less accurate than others.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful and constructive feedback.\n\n> Slightly more explanation would be useful. Specifically, an explanation of the approximation ratio -- I think I know how this is defined here but I can imagine a few semi-reasonable definitions.\n\nFor a fixed number of agents (n) and a single trial (out of 500), the approximation ratio is defined as follows: we identify the winner using the partial feedback and compute their true score under the full preference profile. This is then divided by the true score of the actual winner, i.e., the candidate who would have been selected using full information. We average this approximation ratio over all 500 trials and report both the mean and standard deviation. We will clarify this point in the revised version.\n\n\n>Additional details on the setup are important, however. Including them in the appendix would be fine. Specifically, I would hope for more detail on the distributions (is Mallow's using Boehmer's re-parameterization?) and the winner determination.\n\n\nWe do not use Boehmer’s re-parameterization, as the number of candidates remains fixed throughout our experiments. We use the classical definition of the Mallows model, where, given a central ranking $\\sigma^*$ and a parameter $\\phi \\in (0, 1]$, the probability of observing a ranking $\\sigma$ is defined as:\n\n$\\frac{\\phi^{d(\\sigma, \\sigma^*)}}{\\sum_{\\sigma' \\in \\mathcal{L}(A)} \\phi^{d(\\sigma', \\sigma^*)}}$. \n\nwhere $d(\\sigma, \\sigma^*)$ denotes the Kendall tau distance between $\\sigma$ and $\\sigma^*$.\n\nFor winner determination, we construct a weighted majority graph based on the available feedback. Specifically, under pairwise feedback, each voter is asked to compare a randomly selected pair of candidates and under $t$-improvement feedback, each voter is queried with a randomly selected candidate and returns one candidate from the $t$-above neighborhood of the queried candidate, according to the $t$-improvement feedback distribution. These responses collectively define a weighted majority graph, which is then used to determine the winner under each feedback type.\n\nWe will make sure to include more detailed descriptions of the setup, including formally defined the weighted majority graph.\n\n> Is the algorithm learning a single weighted majority graph then using it to compute both the Borda and Copeland winners (also, is weighted majority graph defined in the paper?)? Then what is actually being learned from the impartial culture profile when Copeland is so poorly estimated? \n\nYes, the same graphs are used for both Borda and Copeland. \n\nWe also found this behavior surprising. But our conclusion is that it stems from the statistical nature of pairwise comparisons in random preference profiles. Under the IC model, most pairwise majority margins are extremely narrow—typically close to 50-50.  When we sample comparisons uniformly at random, there is a significant chance that sampling noise flips the majority outcome of a pair. For example, if candidate $a$ defeats  $b$ with 51% of the vote, the number of observed comparisons  may still favor $b$ in the sample. In such cases,  $a$ is assigned $0$ points instead of $1$ in the Copeland score. This effect cannot be avoided even when  the number of queries grows. \n\nBorda, on the other hand, is more robust in this setting. Even if the sampled pairwise data slightly misrepresents the majority—for example, favoring $b$ over $a$ 51% to 49%—the inferred Borda score for $a$ still reflects this proportionally. Since the Borda score can be interpreted as the sum of the estimated probabilities of a candidate defeating each other candidate (see line 1230), $a$ would still receive 0.49 points rather than being penalized with a full loss. This smoothness makes Borda less sensitive to small fluctuations.\n\n>Additionally, if you are learning a weighted majority graph using the pref-voting package it should be quite trivial to compute the winner of all C1/C2 rules in the package.\n\nWe considered computing additional C1/C2 rules beyond Borda and Copeland. However, we ran into limitations stemming from the nature of the rules themselves. In particular, to make our definition of approximation ratio meaningful, we must restrict attention to rules that assign scores to candidates—otherwise, it's unclear how to compare the true and estimated winners. This requirement excludes many rules in the pref-voting library, such as Kemeny, Slater, and the Uncovered Set.\n\nWe also considered the minimax rule, which does assign scores. However, we encountered technical issues that made it difficult to include. In particular, the true winner often has a minimax score of zero, resulting in undefined 0/0 approximation ratios. Additionally, minimax scores are typically nonpositive, with the winner being the candidate with the least negative value—this makes interpreting approximation ratios less meaningful. For these reasons, we ultimately decided not to include minimax in our evaluation.", "claims_and_evidence": "The claims made in the paper are supported fairly well.", "methods_and_evaluation_criteria": "The paper makes theoretical claims and supports them appropriately. Experiments add a very interesting new depth to the theoretical results.", "theoretical_claims": "I lightly reviewed the proofs included in the main text of the paper.", "experimental_designs_or_analyses": "The experiments are quite reasonable and appropriate for the question at hand. Slightly more explanation would be useful. Specifically, an explanation of the approximation ratio -- I think I know how this is defined here but I can imagine a few semi-reasonable definitions.", "relation_to_broader_scientific_literature": "The paper builds upon one recent work studying comparison feedback and, less directly, several other papers considering partial information settings and t-wise queries.\n\nThis is a very natural extension of existing research and could conceivably relate to some applications, such as in RLHF.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Overall I find the main idea of the paper to be quite reasonable and generally like the paper. This fits well into existing and ongoing work into learning about partial preferences.\n\nThere is some room for improvement in presentation which I would encourage should the opportunity arise. In particular, I would suggest ensuring that the introduction is primarily focused on building intuition around the paper. This is largely the case but the section could be further simplified. A stronger connection to possible applications would also be useful, if you do see such a connection. Including slightly more natural language/intuition-building throughout the paper would also improve the readability of the work.\n\nI very much like that you have included some experiments. That it is usually possible to effectively learn Borda/Copeland despite not being possible to guarantee highlights, for me, the importance of doing experiments to actually understand the behaviour of a setting. Additional details on the setup are important, however. Including them in the appendix would be fine. Specifically, I would hope for more detail on the distributions (is Mallow's using Boehmer's re-parameterization?) and the winner determination.\n\nI am interested in winner determination because I find the poor accuracy at learning the Copeland winner to be quite surprising. Is the algorithm learning a single weighted majority graph then using it to compute both the Borda and Copeland winners (also, is weighted majority graph defined in the paper?)? Then what is actually being learned from the impartial culture profile when Copeland is so poorly estimated? Perhaps I am missing it but some discussion about the accuracy of Copeland under IC seems quite important.\n\nAdditionally, if you are learning a weighted majority graph using the pref-voting package it should be quite trivial to compute the winner of all C1/C2 rules in the package. While not the main focus of the paper, doing this could be quite interesting (especially given that you already know there is at least one rule, Copeland, which exhibits surprising behaviour).", "other_comments_or_suggestions": "I noticed several minor typos. I would encourage re-reading to catch any that I did not notice.\n\nLine 128, Column 1: You use $\\mathcal{L}$ here and $L$ elsewhere in the paper.\n\nL194C2: \"there are is a family...\"\n\nL205C2: \"any of this preference profiles\"\n\nL309C2 (in the equation): Should there be a $D$ subscript for the probabilities?\n\nL334/335C2: The sentence \"For both rules suffices...\" needs rearranging.\n\nL351C2: \"is assigned a r weight\"", "questions_for_authors": "Do you have any explanation for the relatively poor behaviour of Copeland in the experiments? I found this quite surprising -- is it also surprising to you?\n\n\n(A response is unlikely to change my evaluation but I am quite curious about this.)", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yWXBymUmTq", "reviewer": "Reviewer_dfHM", "summary": "This paper discusses the potential for any learning algorithm to identify a social choice winner f when sampling preferences from a distribution D. It specifically talks about t-improvement feedback, where D is hidden but can be sampled such that -- given a candidate $a$ in position $i$, one of the t candidates that are higher ranking that $i$ can be elicited at a time. Their main theorems distinguish certain sufficient conditions where an algorithm A cannot identify the winner f(.) when they have access to t-improvement feedback, in the worst-case, under position scoring rules and Condorcet-consistent rules.\n\n*NOTE: Score changed 2->3 after reading authors' rebuttal.*", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful and constructive feedback. \n\n\n>The paper is confusing about what information algorithms A has access to, and specifically how they conduct t-improvement feedback. \n\nAs noted in your summary and in lines 60–62, under the $t$-improvement feedback model, when a candidate  $a$ is queried, the response is a random candidate drawn from the $t$-above neighborhood of $a$ in the voter's ranking. This candidate is sampled according to a fixed $t$-improvement feedback distribution, which defines the probabilities over the  $t$-above candidates (lines 63–64). Given a preference profile and a $t$-improvement feedback distribution, this sampling procedure induces a marginal probability of observing $b$ as feedback when querying  $a$.\n\nWhile in practice, such marginals can be estimated by sufficiently many samples, here we make the strong assumption of full information: the algorithm has exact access to the probabilities of seeing $b$ when querying $a$, for every pair $a,b\\in M$ (lines 74–81). This idealized access **strictly strengthens our impossibility results**--if no algorithm can succeed finding the winner with full information, it cannot succeed with less (see lines 82–84, 189-192).\n\n>How these results compare to the theoretical query complexity of t-improvement feedback or pairwise feedback.\n\nOur results do not address query complexity (lines 104–108 rhs). As noted above, we assume idealized access to the exact marginal probabilities of receiving $b$ when querying $a$, thereby abstracting away sampling concerns. As such, our results are orthogonal to work in preference learning that focuses on sample efficiency (e.g., under the Bradley–Terry model).\n\n>How the inability to distinguish between two distributions leads to the claim that algorithms cannot learn f better than random.  proof of Thm 4.4, why can we apply Lemma 3.2?\n\nIndeed, Lemma 3.2 requires the existence of  $m$ preference profiles that are all $t$-indistinguishable from each other and each have a unique winner. Lemma 4.1 constructs exactly such a set of profiles, as stated explicitly. We suspect the confusion may stem from our use of the term “family of profiles”, which we use in line with standard terminology (see Lemmas 4.1–4.3 in Halpern et al.).\n\n>In the second-to-last sentence, why is the scoring rule in span(,)?\n\nThis is a typo. The sentence should refer to scoring vectors  **not in** the span. We apologize for it.\n\n>In Lemma 3.1 why does the requirement on p need to hold? Doesn't \"j-i > t\" and \"m-l > t\" suggest that querying either a or b will (necessarily) never yield the other, since it's outside the scope of t items?\n\nIndeed, these conditions indicate that querying either $a$ or $b$ will never yield the other, so indeed by swapping them the probability of asking one and seeing the other remains the same  (equal to $0$). However, to ensure that the two profiles are indistinguishable, we must guarantee that for **every** $x,y \\in M$ the probability of querying $x$ and observing $y$ is the same under both profiles (see definition in lines 195-200). The value of $p$ is chosen to maintain this property (see lines 550–582).\n\n\n\n>Please clarify the second-to-last sentence in the proof of Lemma 4.2.\n\nFirst part of the proof concerns positions $2$ to $ m-t-1$ (line 263). Second part of the proof concerns positions $m-t$ to $m-1$ (line 234 rhs).  We relate position $2$  to positions $m-t$ to $m-1$  in order to argue that the ratio $s_i/ P_i$ is the same (and equal to $\\lambda$) for all positions from $2$ to $m-1$.\n\n>How these results compare to the NP-hardness of possible/necessary winner problems.\n\nThat line of work  focuses on computational complexity of determining whether a candidate is a possible or necessary winner given partial orders. In contrast, we assume access to full statistical feedback and study whether any algorithm—regardless of computational complexity—can recover the winner. Our impossibility results are information-theoretic, not complexity-theoretic (see lines 104-106).\n\n>What motivates the “t-improvement” concept?\n\nThe notion of $t$-improvement captures interactive settings where users refine suggestions through small, local adjustments—e.g., modifying LLM outputs or adjusting robot behavior—rather than providing full rankings. This interaction model appears in frameworks such as coactive learning and interactive preference learning (see lines 25–35 rhs and 110–114). The parameter $t$ captures the granularity of improvement.\n\n>The paper seems to significantly build on Halpern et al. (2024), though doesn't go into much detail on the work.\n\nWhile our work is conceptually related to Halpern et al, the technical contributions are distinct. The preference profiles we construct differ significanlty and are tailored to the $t$-improvement feedback model rather than pairwise comparisons. Where we do draw on Halpern et al.—e.g., in Lemma 3.2—we reprove the results in our setting for completeness.", "claims_and_evidence": "It could be made clearer how the failure of t-improvement feedback entails their claim that no algorithm can learn the correct output f(.) with high enough probability. The paper is confusing about what information algorithms A have access to, and specifically how they conduct t-improvement feedback. I would like to see this spelled out more explicitly.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "- In Lemma 3.1 why does the requirement on p need to hold? Doesn't \"j-i > t\" and \"m-l > t\" suggest that querying either a or b will (necessarily) never yield the other, since it's outside the scope of t items?\n- Please clarify the second-to-last sentence in the proof of Lemma 4.2. This doesn't seem to follow from prior deductions. The second section of this proof appears quite round-a-bout and I'm not sure why it's there.\n- In proof of Thm 4.4, why can we apply Lemma 3.2? Doesn't that require m distinct distributions, whereas the construction from Lemma 4.1 only guarantees some family of distributions? Also -- in the second to last sentence, why is the scoring rule in span(*,*)? Isn't this part discussing when the scoring rule isn't in span(*,*)?", "experimental_designs_or_analyses": "Experiments look good. They support and provide complementary insight into the paper's main claims.", "relation_to_broader_scientific_literature": "For the most part, yes. The authors discuss relevant literature in partial-order preference elicitation and query complexity. They don't go too much into depth in the literature about pairwise elicitation, such as papers discussing elicitation in the the Bradley-Terry model.", "essential_references_not_discussed": "In Related Work (Sec 1.2), talk about relationship of your work to the possible and necessary winner problems, as introduced by [1,2] (see also Sec 10.3.1 of (Brandt et al., 2016). I would like to see how your results compare to the impossibility results presented by this prior line of research. Also, how do your query complexity findings compare to other preference learning research, such as with pairwise comparisons in the Bradley-Terry model?\n\n[1] Kathrin Konczak and Jérôme Lang. 2005. Voting procedures with incomplete preferences.\n[2] Lirong Xia and Vincent Conitzer. 2011. Determining Possible and Necessary Winners under Common Voting Rules Given Partial Orders.", "other_strengths_and_weaknesses": "**Overall review:**\n\nThe paper does a good job posing an interesting question -- the learnability of outputs f given t-improvement feedback -- and taking steps to solve it under various social choice functions f. It is well-put into context of other work to learn social choice functions. It checks off the boxes I'd like to see out of this type of paper: pose interesting question, frame the model, non-trivial theoretical findings, experiments and discussion.\n\nHowever, there are certain questions I still have:\n- Certain aspects of the proofs are not clear\n- How the inability to distinguish between two distributions leads to the claim that algorithms cannot learn f better than random\n- What information algorithms A have access to when conducting their queries\n- How these results compare to the theoretical query complexity of t-improvement feedback or pairwise feedback\n- How these results compare to the NP-hardness of the possible/necessary winner problems\n\nAlso: \n- The paper seems to significantly build on (Halpern et al., 2024), though doesn't go into too much detail on the work.\n- What motivates the \"t-improvement\" concept? In (p2 LHS) you say t reflects the \"limited cognitive and practical effort\" of users, though this seems like a limited jumping-off point.\n\nTherefore I would recommend the paper gets edited and resubmitted. If the authors can point to the aspects of this paper that address these issues, or answer them simply, I'd be willing to reconsider.", "other_comments_or_suggestions": "Minor:\n- (Typo) In Model (Sec 2), you use $\\mathcal{L}$ and $L$ interchangeably.\n- In Model (Sec 2), you refer to \"pi of D\" as a sample from the distribution D subject to the permutation pi. Is this supposed to be a sample, or a modified distribution itself?\n- (p4 LHS) Please define $q^t_\\sigma$.\n- Format of Lemma 3.1: take the definition of $D_{i,j,l}$ out of the lemma statement.\n- (Typo) In Lemma 3.2: \"...suppose there are is a family...\"\n- (Typo) In Lemma 4.1, you say \"indistinguishable\" instead of \"t-indistinguishable.\"\n- In main body, tell the reader that Lemma 4.1 is proved in Appendix B\n- Proof of Lemma 4.2: is $\\lambda$ defined as $s_i / P^t_i$ here? How is this related to $\\vec{s}^*_t$?", "questions_for_authors": "NA", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UrRtmaFTYy", "reviewer": "Reviewer_5mjJ", "summary": "This paper investigates the feasibility of computing voting rules using improvement feedback, a type of iterative preference refinement distinct from pairwise comparisons. It characterizes the positional scoring rules that can be learned under improvement feedback, demonstrating that while plurality can be determined, many other rules face strong impossibility results. The study also establishes that Condorcet-consistent rules cannot be computed using improvement feedback. Theoretical findings are supported by experimental analyses, showing practical implications of the proposed method.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer.\n\n>Authors consider multiple answer setting, and in that case Condorset winner cannot be determined. However, getting multiple preference answers is costly and difficult and can be decomposed as getting pairwise comparisons n times. Why should we solve the problem which happens only under multiple answers?\n\nWe would like to clarify that in the $t$-improvement model, each query returns only a single candidate—namely, a candidate from the $t$-above neighborhood of the queried option. The model does not assume multiple feedback points per query (lines 60-62).\n\nThe impossibility results we derive are not due to assuming \"multiple answers\" but rather due to the restricted nature of the available feedback. While it's true that repeated pairwise comparisons could reconstruct full rankings, our focus is precisely on the types of settings where such fine-grained elicitation is infeasible (lines 38-40). \n\n\n>Limited discussion of how improvement feedback can be practically elicited in real-world applications.\n\nImprovement feedback models scenarios where users iteratively refine suggestions—e.g., editing LLM-generated text or adjusting robotic actions—by providing local, incremental improvements. This form of interaction is common in coactive learning, preference-based reinforcement learning, and broader human-in-the-loop decision-making systems. We will clarify this motivation even more in the introduction.\n\n\n>The focus on worst-case impossibility results may not fully capture practical performance in realistic scenarios.\n\nAs is typical in theoretical work, our analysis focuses on worst-case guarantees to characterize the fundamental limitations of improvement feedback. However, we agree that worst-case behavior may not reflect typical performance in realistic settings. That is why we conducted experiments on more realistic distributions—including IC, Mallows, and Plackett-Luce—which go beyond the worst-case. These experiments show that improvement feedback can perform competitively with, and in some cases even outperform, pairwise comparisons in approximating voting rule outcomes. This contrast highlights the practical value of improvement feedback despite its theoretical limitations.\n\n>The paper assumes idealized access to feedback distributions, which may not hold in practical settings.\n\nIndeed, access to the exact feedback distribution is an idealized assumption, which **only strengthens our negative results**: if impossibility holds under full information, it certainly holds in more realistic settings with partial or noisy access (lines 80-84, 189-192). However, in practice, these distributions can be approximated via sufficiently many user queries, and one can formally justify this using standard concentration techniques. \n\n>The authors could explore hybrid feedback mechanisms combining improvement feedback with pairwise comparisons to mitigate the limitations identified.\n\nWe agree this is a compelling direction, as noted in the third sentence of our Discussion section. It is a question we have also given considerable thought. The main challenge is that the indistinguishable profiles constructed by Halpern et al. for pairwise comparisons are fundamentally different from those we construct for improvement feedback. Their profiles (respectively, ours) lead to impossibility under pairwise comparisons (respectively, improvement feedback), but do not remain indistinguishable when accessed via the other feedback model. As a result, making progress in this setting would require either (i) extending the impossibility results to hold even when both types of feedback are available, which would require new indistinguishable constructions, or (ii) showing that access to both feedback models enables algorithms to recover the correct winner, by designing techniques that exploit their complementary strengths. We leave this question to future work.\n\n>More discussion on the implications of these results for participatory decision-making systems could enhance the broader impact of the work.\n\nOur work highlights fundamental limitations in inferring collective decisions from restricted forms of feedback, which are common in real-world. Understanding which social choice rules are robust under such bounded input is crucial for designing systems that are both practical and representative. We will expand the discussion in the final version to better highlight these connections. \n\n\n>It would be helpful to consider how strategic behavior by voters might impact the effectiveness of improvement feedback.\n\nOur negative results already hold under the assumption that voters report their preferences truthfully. Introducing strategic behavior would  **weaken** these impossibility results, as it introduces an additional layer of uncertainty and misalignment between observed feedback and true preferences. However, we agree that understanding strategic behaviors in this setting is an interesting direction for future work.", "claims_and_evidence": "- The authors claim that improvement feedback enables learning the plurality rule but fails for many other scoring rules.\n- The paper provides theoretical proofs demonstrating that improvement feedback does not suffice to compute Condorcet-consistent rules.\n- Empirical simulations support the theoretical findings, comparing improvement feedback and pairwise comparisons in approximating voting rule outcomes.", "methods_and_evaluation_criteria": "- Theoretical analysis using formal models of voting and preference aggregation.\n- Characterization of learnability for different voting rules using improvement feedback.\n- Empirical evaluation through simulations on different preference distributions, including Impartial Culture (IC), Mallows, and Plackett-Luce models.\n- Approximation ratios are used to measure the effectiveness of improvement feedback compared to pairwise comparison feedback.", "theoretical_claims": "- Improvement feedback can determine the plurality winner but fails for most other positional scoring rules.\n- No algorithm, deterministic or randomized, can identify a Condorcet winner using improvement feedback with a probability greater than $\\frac{1}{m}$.\n- The impossibility results hold under general improvement feedback distributions, except for a specific case where $P^t_i/P^t_{i+1}$ follows a defined ratio.", "experimental_designs_or_analyses": "- Simulations are conducted using synthetic ranking data generated from IC, Mallows, and Plackett-Luce models.\n- Different t-improvement feedback distributions (uniform, linear decay, and exponential decay) are tested.\n- The performance of improvement feedback is compared against pairwise comparison feedback for Borda and Copeland rules.\n- Results show that under certain preference distributions, improvement feedback performs comparably or even better than pairwise feedback in approximating voting rule outcomes.", "relation_to_broader_scientific_literature": "- Extends prior work on voting rule computation under limited feedback (e.g., Halpern et al. 2024).\n- Builds on research in coactive learning and interactive preference learning by examining feedback mechanisms for collective decision-making.\n- Contributes to computational social choice by analyzing preference aggregation under practical constraints.", "essential_references_not_discussed": ".", "other_strengths_and_weaknesses": "### Strengths\n- Provides a rigorous theoretical foundation for analyzing improvement feedback in voting.\n- Well-structured proof techniques and clear characterization of learnable voting rules.\n- Complementary empirical analysis enhances practical relevance.\n\n### Weaknesses\n- Limited discussion of how improvement feedback can be practically elicited in real-world applications.\n- The focus on worst-case impossibility results may not fully capture practical performance in realistic scenarios.\n- The paper assumes idealized access to feedback distributions, which may not hold in practical settings.", "other_comments_or_suggestions": "- The authors could explore hybrid feedback mechanisms combining improvement feedback with pairwise comparisons to mitigate the limitations identified.\n- More discussion on the implications of these results for participatory decision-making systems could enhance the broader impact of the work.\n- It would be helpful to consider how strategic behavior by voters might impact the effectiveness of improvement feedback.", "questions_for_authors": "Authors consider multiple answer setting, and in that case Condorset winner cannot be determined. However, getting multiple preference answers is costly and difficult and can be decomposed as getting pairwise comparisons n times. Why should we solve the problem which happens only under multiple answers?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Reviewers felt that the problem investigated in this paper to be interesting, the theoretical results being solid, and the experiments being reasonably convincing. Some questions were clarified during the rebuttal and the overall sentiment became positive. There is still room for improvement in presentation as multiple reviewers noticed, but overall this is a nice addition to ICML and a nice contribution to computational social choice.
Decision: Accept (poster)