Title: Manipulative Elicitation -- A New Attack on Elections with Incomplete Preferences,
Abstract: Lu and Boutilier proposed a novel approach based on "minimax regret" to use
classical score based voting rules in the setting where preferences can be any
partial (instead of complete) orders over the set of alternatives. We show here
that such an approach is vulnerable to a new kind of manipulation which was not
present in the classical (where preferences are complete orders) world of
voting. We call this attack "manipulative elicitation." More specifically, it
may be possible to (partially) elicit the preferences of the agents in a way
that makes some distinguished alternative win the election who may not be a
winner if we elicit every preference completely. More alarmingly, we show that
the related computational task is polynomial time solvable for a large class of
voting rules which includes all scoring rules, maximin, Copeland$^\alpha$ for
every $\alpha\in[0,1]$, simplified Bucklin voting rules, etc. We then show that
introducing a parameter per pair of alternatives which specifies the minimum
number of partial preferences where this pair of alternatives must be
comparable makes the related computational task of manipulative elicitation
\NPC for all common voting rules including a class of scoring rules which
includes the plurality, $k$-approval, $k$-veto, veto, and Borda voting rules,
maximin, Copeland$^\alpha$ for every $\alpha\in[0,1]$, and simplified Bucklin
voting rules. Hence, in this work, we discover a fundamental vulnerability in
using minimax regret based approach in partial preferential setting and propose
a novel way to tackle it.