Abstract
Iterative preference elicitation is a practical approach to collective decision-making, yet its vulnerability to strategic manipulation remains a concern. This paper investigates the intersection of iterative elicitation and manipulative voting behavior. By modeling "Locally Dominant Manipulation" and introducing a "Careful" query selection strategy, the authors demonstrate that strategic lying is remarkably rare and has a negligible impact on election outcomes in moderately sized groups.
Introduction
In many real-world scenarios, such as scheduling meetings or ranking items, it is impractical to ask every user for a complete preference ranking. Iterative preference elicitation addresses this by asking a sequence of simple queries (e.g., "Do you prefer Option A or Option B?") until a winner can be determined. However, the assumption of voter honesty is frequently violated in practice. Strategic voters may misrepresent their preferences to ensure a more favorable outcome. This research bridges the gap between iterative elicitation and iterative voting, exploring how systems can remain robust against "on the fly" manipulation.
Modeling Manipulation: The Locally Dominant Strategy
The authors propose a manipulation model where voters act with limited information. A voter employs a Locally Dominant Manipulation if the lie results in a winner that is at least as good as the truthful outcome in all possible scenarios, and strictly better in at least one. To maintain plausibility and minimize cognitive load, voters are assumed to seek a "minimal effort" lie, defined by the smallest swap distance from their true ranking.
Algorithms were developed to allow voters to calculate these lies dynamically based on the current set of Possible Winners (PW)—candidates who could still mathematically win given the partial information revealed so far.
The "Careful" Defense Strategy
To mitigate the risk of manipulation, the paper introduces the Careful Voting Center. This center prioritizes queries involving candidates who are both currently in the Possible Winners set. The rationale is that when both candidates are strong contenders, the mathematical opportunity for a voter to lie effectively is constrained, thereby reducing the incentive for strategic behavior.
Experimental Evaluation
The study utilized the Sushi dataset, a standard benchmark containing 5,000 preference rankings. Simulations were conducted with voter pools ranging from 10 to 250 to test the robustness of various elicitation algorithms.
Manipulation Rates and Outcome Stability
A key finding is that manipulation is significantly harder to execute than expected. Even with "smart" algorithms, voters only found opportunities to lie in 0.1% to 1% of queries. This rarity stems from the requirement that lies must remain consistent with all previous answers provided by the voter.
As shown in the figure above, the manipulation rate consistently decreases as the number of voters increases. For groups larger than 50, individual manipulations failed to change the final winner in any experimental trial. The frequency of insincere responses remained extremely low, typically between 0.001 and 0.01 per query.
Efficiency and Convergence
The Expected Scored (ES) algorithm, which targets current front-runners, proved highly efficient at reaching a winner. Interestingly, the presence of manipulators can sometimes speed up convergence, as the "noise" they introduce helps the system narrow down the winner faster, albeit potentially at the cost of perfect truthfulness in very small groups.
Figure 3 illustrates that while manipulative behavior (+M) requires slightly more queries than purely truthful voting (+T), the ES algorithm remains efficient, typically querying less than 35% of the potential preference data to reach a conclusion.
Conclusion
This research suggests that iterative voting systems are surprisingly robust against strategic manipulation. In realistic scenarios with 50 or more voters, the "Lie on the Fly" approach fails to subvert the democratic process. The "Careful" center strategy further bolsters this resilience, ensuring that even when voters attempt to be strategic, the integrity of the final outcome remains intact. Future work will explore these dynamics in larger candidate spaces and under different voting rules.
Summary updated