Computing Voting Rules with Improvement Feedback

We thank the reviewer.

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?

We 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).

The 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).

Limited discussion of how improvement feedback can be practically elicited in real-world applications.

Improvement 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.

The focus on worst-case impossibility results may not fully capture practical performance in realistic scenarios.

As 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.

The paper assumes idealized access to feedback distributions, which may not hold in practical settings.

Indeed, 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.

The authors could explore hybrid feedback mechanisms combining improvement feedback with pairwise comparisons to mitigate the limitations identified.

We 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.

More discussion on the implications of these results for participatory decision-making systems could enhance the broader impact of the work.

Our 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.

It would be helpful to consider how strategic behavior by voters might impact the effectiveness of improvement feedback.

Our 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.

We thank the reviewer for their thoughtful and constructive feedback.

The paper is confusing about what information algorithms A has access to, and specifically how they conduct t-improvement feedback.

As 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$.

While 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).

How these results compare to the theoretical query complexity of t-improvement feedback or pairwise feedback.

Our 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).

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?

Indeed, 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.).

In the second-to-last sentence, why is the scoring rule in span(,)?

This is a typo. The sentence should refer to scoring vectors not in the span. We apologize for it.

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?

Indeed, 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).

Please clarify the second-to-last sentence in the proof of Lemma 4.2.

First 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$.

How these results compare to the NP-hardness of possible/necessary winner problems.

That 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).

What motivates the “t-improvement” concept?

The 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.

The paper seems to significantly build on Halpern et al. (2024), though doesn't go into much detail on the work.

While 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.

We thank the reviewer for their thoughtful and constructive feedback.

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.

For 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.

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.

We 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:

$\frac{\phi^{d(\sigma, \sigma^*)}}{\sum_{\sigma' \in \mathcal{L}(A)} \phi^{d(\sigma', \sigma^*)}}$.

where $d(\sigma, \sigma^*)$ denotes the Kendall tau distance between $\sigma$ and $\sigma^*$.

For 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.

We will make sure to include more detailed descriptions of the setup, including formally defined the weighted majority graph.

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?

Yes, the same graphs are used for both Borda and Copeland.

We 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.

Borda, 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.

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.

We 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.

We 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.