# Obvious manipulations of tops-only voting rules††thanks: We thank Jordi
Massó for his very detailed comments. We acknowledge financial support from
UNSL through grants 032016, 030120, and 030320, from Consejo Nacional de
Investigaciones Científicas y Técnicas (CONICET) through grant PIP
112-200801-00655, and from Agencia Nacional de Promoción Científica y
Tecnológica through grant PICT 2017-2355.

R. Pablo Arribillaga Instituto de Matemática Aplicada San Luis, Universidad
Nacional de San Luis and CONICET, San Luis, Argentina, and RedNIE. Emails:
<EMAIL_ADDRESS>and<EMAIL_ADDRESS>Agustín G.
Bonifacio22footnotemark: 2

###### Abstract

In a voting problem with a finite set of alternatives to choose from, we study
the manipulation of tops-only rules. Since all non-dictatorial (onto) voting
rules are manipulable when there are more than two alternatives and all
preferences are allowed, we look for rules in which manipulations are not
obvious. First, we show that a rule does not have obvious manipulations if and
only if when an agent vetoes an alternative it can do so with any preference
that does not have such alternative in the top. Second, we focus on two
classes of tops-only rules: (i) (generalized) median voter schemes, and (ii)
voting by committees. For each class, we identify which rules do not have
obvious manipulations on the universal domain of preferences.

_JEL classification:_ D71, D72.

_Keywords:_ obvious manipulations, tops-onlyness, (generalized) median voting
schemes, voting by committees, voting by quota.

##  1 Introduction

Voting rules are systematic procedures that allow a group of agents to select
an alternative, among many, according to their preferences. Within desirable
properties a voting rule may satisfy, the concept of strategy-proofness has
played a central role for studying the strategic behavior of the agents. A
voting rule is strategy-proof if it is always in the best interest of the
agents to reveal their true preferences. Unfortunately, Gibbard-
Satterthwaite’s celebrated theorem states that, outside of a dictatorship,
there is no strategy-proof (onto) voting rule when more than two alternatives
and all possible preferences over alternatives are considered (Gibbard, 1973;
Satterthwaite, 1975). To circumvent this impossibility result, two main
approaches have been taken. The first approach restricts the domain of
preferences that agents can have over alternatives (see Barberà, 2011, and
references therein). The second approach considers weakenings of strategy-
proofness, and it has been an active field of research in recent years. The
idea underlying this approach is that even though manipulations are pervasive,
agents may not realize they can manipulate a rule because they lack
information about others’ behavior or they are cognitively limited.

Troyan and Morrill (2020) introduce the concept of obvious manipulation in the
context of market design. They assume that an agent knows the possible
outcomes of the mechanism conditional on his own declaration of preferences,
and define a deviation from the truth to be an obvious manipulation if the
best possible outcome under the deviation is strictly better than the best
possible outcome under truth-telling, or the worst possible outcome under the
deviation is strictly better than the worst possible outcome under truth-
telling. A mechanism that does not allow any obvious manipulation is called
not obviously manipulable.

In this paper we study (not) obvious manipulation of voting rules when a
finite set of alternatives is involved. We focus on tops-only rules: rules
that only consider agents’ top alternatives in order to select a social
choice. Obvious manipulations of non-tops-only rules have been thoroughly
studied elsewhere (see Aziz and Lam, 2021). The importance of studying obvious
manipulations of tops-only rules is three-fold. Firstly, because of their
simplicity, tops-only voting rules are important rules on their own right and
are both useful in practice and extensively studied in the literature.
Secondly, assume we have a class of strategy-proof rules defined on a
restricted domain of preferences and we want to study whether those rules are
obviously manipulable in the universal domain of preferences. Then, it is
natural to require tops-onlyness since, under mild assumptions, strategy-
proofness implies tops-onlyness (see, for example, Barberà et al., 1991;
Chatterji and Sen, 2011; Weymark, 2008). Thirdly, obvious manipulations allow
us to discriminate among different tops-only rules, while other recently
studied weakenings of strategy-proofness are incapable to do this because,
under tops-onlyness, those concepts become equivalent to strategy-proofness
(see, for example, Arribillaga et al., 2022).

Our main result gives a characterization of not obviously manipulable rules in
terms of veto power of the agents. An agent vetoes an alternative if there is
a preference report of the agent that forces the rule to never select such
alternative. The veto is strong if the report of _any_ preference with top
different from the alternative forces the rule to never select it. Theorem 1
states that, within tops-only rules, not obvious manipulation is equivalent to
each veto being a strong veto.

Next, we apply our main result to study well-known classes of tops-only voting
rules when they are considered on the universal domain of preferences:
(generalized) median voter schemes and voting by committees.

First, consider a problem where the set of alternatives $X$ is an ordered set.
Without loss of generality, assume
$X=\\{a,a+1,a+2,\ldots,b\\}\subseteq\mathbb{N}$ and $b=a+(m-1).$ For this
problem, Moulin (1980) characterizes all strategy-proof and tops-only (onto)
rules on the domain of single-peaked preferences111An agent’s preference is
single-peaked if there is a top alternative that is strictly preferred to all
other alternatives and at each of the two sides of the top alternative the
preference is monotonic, increasing in the left, and decreasing in the right.
as the class of all generalized median voter schemes. Moulin (1980) also
characterizes the subclass of median voter schemes as the set of all strategy-
proof, tops-only, and anonymous (onto) rules on the domain of single-peaked
preferences. A median voter scheme can be identified with a vector
$\alpha=(\alpha_{1},\ldots,\alpha_{n-1})$ of $n-1$ numbers in $X$, where $n$
is the cardinality of the set of agents $N$ and
$\alpha_{1}\leq\alpha_{2}\leq\ldots\leq\alpha_{n-1}$. Then, for each
preference profile, the median voter scheme identified with $\alpha$ selects
the alternative that is the median among the $n$ top alternatives of the
agents and the $n-1$ fixed numbers $\alpha_{1},\ldots,\alpha_{n-1}$. Since
$2n-1$ is an odd number, this median always exists and belongs to $X$.
Generalized median voter schemes constitute non-anonymous extensions of median
voter schemes.

When the designer cannot guarantee that the domain restriction (single-
peakedness) is met and the full domain of preferences has to be considered,
then strategy-proofness no longer holds. For this reason, it is important to
identify which rules within these families obey the less demanding property of
non-obvious manipulability. In Theorem 2, we show that a median voter scheme
is not obviously manipulable if and only if $\alpha_{1}\in\\{a,a+1\\}$ and
$\alpha_{n-1}\in\\{b-1,b\\}.$ A similar condition applied to the extremal
fixed ballots (for each agent) in the monotonic family of fixed ballots
associated with generalized median voter schemes characterizes those that are
not obviously manipulable (Theorem 3).

Now, consider a problem in which agents have to choose a subset of objects
from a set $K$ (with $\left|K\right|\geq 2$). Then, in this case, $X=2^{K}$
and elements of $X$ are subsets of $K$. A generic element of $K$ is denoted by
$k$. As an example, think of objects as candidates to become new members of a
society that have to be elected by the current members of the society. Barberà
et al. (1991) characterize, on the restricted domain of separable
preferences,222An agent’s preference is separable on the family of all subsets
of objects if the division between good objects and bad objects guides the
ordering of all subsets in the sense that adding a good object to any set
leads to a better set, while adding a bad object leads to a worse set. the
family of all strategy-proof (onto) rules as the class of voting by
committees. Following Barberà et al. (1991), a voting by committees is defined
by specifying for each object $k\in K$ a monotonic family of winning
coalitions $\mathcal{W}_{k}$ (a committee). Then, the choice of the subset of
objects made by a voting by committees at a preference profile is done object-
by-object as follows. Fix a voting by committees
$\mathcal{W}=\\{\mathcal{W}_{k}\\}_{k\in K}$ and a preference profile, and
consider object $k$. Then, $k$ belongs to the chosen set (the one selected by
$\mathcal{W}$ at the preference profile) if and only if the set of agents
whose best subset of objects contains $k$ belongs to the committee
$\mathcal{W}_{k}$.333Voting by committees can be seen as a family of extended
majority voting (one for each object $k$), where the two alternatives at stake
are whether or not $k$ belongs to the collectively chosen subset of objects.
Observe that voting by committees are in fact tops-only, so tops-onlyness is
implied by strategy-proofness on the domain of separable preferences.

Again, if the domain restriction (separability, in this case) is not
guaranteed to be met, identifying which rules are not obviously manipulable
can be helpful. In Theorem 4, we show that a non-dictatorial voting by
committees is not obviously manipulable if and only if no agent is a vetoer.
In terms of the committees defining the rule, this is equivalent to say that,
for each object: (i) no agent belongs to all the coalitions in the committee,
and (ii) no singleton coalition belongs to the committee. When anonymity is
added to the picture, voting by committees simplifies to voting by quota. In
this case, for each $k\in K$, there is a number $q_{k}$ such that
$\mathcal{W}_{k}$ is the set of all coalitions with cardinality at least
$q_{k}$. We prove that non-obvious manipulability is equivalent to each
committee having quota between 2 and $n-1$ (Corollary 3).

The paper of Aziz and Lam (2021) is the closest to ours and, to the best of
our knowledge, is the first one that applies Troyan and Morrill (2020) notion
of obvious manipulation to the context of voting. Aziz and Lam (2021) present
a general sufficient condition for a voting rule to be not obviously
manipulable. However, they focus on non-tops-only rules. They show that
Condorcet consistent as well as some other strict scoring rules are not
obviously manipulable. Furthermore, for the class of $k$-approval voting
rules, they give necessary and sufficient conditions for obvious
manipulability. Other recent papers that study obvious manipulations, in
contexts other than voting, are Ortega and Segal-Halevi (2022) and Psomas and
Verma (2022).

The rest of the paper is organized as follows. The model and the concept of
obvious manipulations are introduced in Section 2. In Section 3, we present
the main result of our paper that, under tops-onlyness, characterizes non-
obvious manipulable voting rules. Section 4 deals with applications: in
Subsection 4.1 we study (generalized) median voter schemes, and in Subsection
4.2 we study voting by committees. To conclude, some final remarks are
gathered in Section 5.

##  2 Preliminaries

###  2.1 Model

A set of agents $N=\\{1,\ldots,n\\}$, with $n\geq 2$, has to choose an
alternative from a finite and given set $X$ (with cardinality
$\left|X\right|=m\geq 2$ ). Each agent $i\in N$ has a strict preference
$P_{i}$ over $X.$ Denote by $t(P_{i})$ to the best alternative according to
$P_{i}$, called the top of $P_{i}$. We denote by $R_{i}$ the weak preference
over $X$ associated to $P_{i};$ i.e., for all $x,y\in X$, $xR_{i}y$ if and
only if either $x=y$ or $xP_{i}y.$ Let $\mathcal{P}$ be the set of all strict
preferences over $X.$ A (preference) profile is a $n$-tuple
$P=(P_{1},\ldots,P_{n})\in\mathcal{P}^{n},$ an ordered list of $n$
preferences, one for each agent. Given a profile $P$ and an agent $i,$
$P_{-i}$ denotes the subprofile in $\mathcal{P}^{n-1}$ obtained by deleting
$P_{i}$ from $P$.

A (voting) rule is a function $f:\mathcal{P}^{n}\longrightarrow X$ selecting
an alternative for each preference profile in $\mathcal{P}^{n}$. We assume
throughout that a voting rule is an onto function, i.e., for each $x\in X$
there is $P\in\mathcal{P}^{n}$ such that $f(P)=x.$ A rule
$f:\mathcal{P}^{n}\longrightarrow X$ is tops-only if for all
$P,P^{\prime}\in\mathcal{P}^{n}$ such that $t(P_{i})=t(P_{i}^{\prime})$ for
all $i\in N$, $f(P)=f(P^{\prime})$. In this paper, we will focus on tops-only
rules.

Given a rule $f:\mathcal{P}^{n}\longrightarrow X$ and $P_{i}\in\mathcal{P}$,
an alternative report $P_{i}^{\prime}\in\mathcal{P}$ is a (profitable)
manipulation of rule $f$ at $P_{i}$ if there is a preference sub-profile
$P_{-i}\in\mathcal{P}^{n-1}$ such that

$f(P_{i}^{\prime},P_{-i})P_{i}f(P_{i},P_{-i}).$

A rule $f:\mathcal{P}^{n}\longrightarrow X$ is strategy-proof on
$\mathcal{P}^{n}$ if no agent has a manipulation.

Other desirable properties we look at are the following. A rule
$f:\mathcal{P}^{n}\longrightarrow X$ is efficient if for each
$P\in\mathcal{P}^{n}$, there is no $x\in X$ such that $xP_{i}f(P)$ for each
$i\in N$. A rule $f:\mathcal{P}^{n}\longrightarrow X$ is anonymous if it is
invariant with respect to the agents’ names; namely, for each one-to-one
mapping $\sigma:N\longrightarrow N$ and each $P\in\mathcal{P}^{n}$,
$f(P_{1},\ldots,P_{n})=f(P_{\sigma(1)},\ldots,P_{\sigma(n)})$. A rule
$f:\mathcal{P}^{n}\longrightarrow X$ is dictatorial if there exists $i\in N$
such that for each $P\in\mathcal{P}^{n}$, $f(P)=t(P_{i})$.

The Gibbard-Satterthwaite Theorem states that a (onto) rule
$f:\mathcal{P}^{n}\longrightarrow X,$ with $m\geq 3$, is strategy-proof if and
only if it is dictatorial (Gibbard, 1973; Satterthwaite, 1975). This negative
result justifies the study of less demanding criteria of (lack of)
manipulation when rules defined on the universal domain of preferences are
considered. One such weakening of strategy-proofness is presented next.

###  2.2 Obvious manipulations

The notion of obvious manipulations has been introduced by Troyan and Morrill
(2020) when applied to school choice models and later it has been studied by
Aziz and Lam (2021) in the context of voting. They try to describe those
manipulations that are easily identifiable by the agents. To do this, it is
important to specify how much information each agent has about other agents’
preferences. Troyan and Morrill (2020) assume that each agent has complete
ignorance in this respect and, therefore, each agent focuses on the set of
outcomes that can be chosen by the rule given its own report. Now, a
manipulation is obvious if the best possible outcome under the manipulation is
strictly better than the best possible outcome under truth-telling or the
worst possible outcome under the manipulation is strictly better than the
worst possible outcome under truth-telling.

Before we present the formal definition, we present some notation. Given a
preference $P_{i}\in\mathcal{P}$, the option set left open by $P_{i}$ at $f$
is

$O^{f}(P_{i})=\\{f(P_{i},P_{-i})\in X:P_{-i}\in\mathcal{P}^{n-1}\\}.$

Given $Y\subseteq X,$ denote by $B(P_{i},Y)$ to the best alternative in $Y$
according to preference $P_{i}$, and by $W(P_{i},Y)$ to the worst alternative
in $Y$ according to preference $P_{i}$.

###### Definition 1

(Troyan and Morrill, 2020) Let $f:\mathcal{P}^{n}\longrightarrow X$ be a rule,
let $P_{i}\in\mathcal{P},$ and let $P_{i}^{\prime}\in\mathcal{P}$ be a
profitable manipulation of $f$ at $P_{i}$. A manipulation $P_{i}^{\prime}$ is
obvious if

$W(P_{i},O^{f}(P_{i}^{\prime}))\ P_{i}\ W(P_{i},O^{f}(P_{i}))$ (1)

or

$B(P_{i},O^{f}(P_{i}^{\prime}))\ P_{i}\ B(P_{i},O^{f}(P_{i})).$ (2)

The rule $f$ is not obviously manipulable (NOM) if it does not admit any
obvious manipulation.

##  3 Main theorem

As previously mentioned, in this paper we focus in obvious manipulations of
tops-only rules. Because of their simplicity, tops-only voting rules are both
useful in practice and extensively studied in the literature. Now, assume we
have a class of strategy-proof rules defined on a restricted domain of
preferences and we want to study whether those rules are obviously manipulable
in the universal domain of preferences. Then, it is natural to require tops-
onlyness since, under mild assumptions, strategy-proofness implies tops-
onlyness (see, for example, Chatterji and Sen, 2011; Weymark, 2008).
Furthermore, obvious manipulations allow us to discriminate among different
tops-only rules, while other recently studied weakenings of strategy-proofness
are incapable to do this because, under tops-onlyness, those concepts become
equivalent to strategy-proofness (see, for example, Arribillaga et al.,
2022).555Arribillaga et al. (2022) assume that an agent knows a specific type
of information about the preferences of the other individuals conditional on
his own declaration of preferences, and focus on manipulations for which the
worst possible outcome under the deviation consistent with the agent’s
information is strictly better than the outcome under truth-telling. It can be
seen that, under tops-onlyness, the existence of a manipulation of the
aforementioned type is equivalent to the existence of a classical
manipulation. Obvious manipulations of non-tops-only rules have been
thoroughly studied elsewhere (see Aziz and Lam, 2021). In this section we
provide a necessary and sufficient condition for a tops-only rule to be NOM.

In order to obtain our main result, we first need to define when an agent has
veto power. An agent vetoes an alternative if there is a preference report of
the agent that forces the rule to never select such alternative. Formally,

###### Definition 2

Let $f:\mathcal{P}^{n}\longrightarrow X$ be a rule and let $i\in N,$ $x\in X,$
and $P_{i}\in\mathcal{P}$. Agent $\boldsymbol{i$vetoes$x$via$P_{i}}$ if
$x\notin O^{f}(P_{i}).$

Denote by $V_{i}$ the set of all alternatives that agent $i$ vetoes via some
preference. Given $x\in V_{i}$, let
$\mathcal{V}_{i}^{x}=\\{P_{i}\in\mathcal{P}:$ $i$ vetoes $x$ via $P_{i}\\}$ be
the set of all preferences by which $x$ is vetoed by agent $i$. As it is
observed by Aziz and Lam (2021), if a rule $f$ has no vetoers then it is NOM,
because $O^{f}(P_{i})=X$ for each $i\in N$ and each $P_{i}\in\mathcal{P}$.
However, as the next example shows, there are rules that satisfy NOM and admit
(many) vetoers.666For an example of a non-tops-only rule that satisfies NOM
and admits vetoers, see Lemma 5 in Aziz and Lam (2021).

###### Example 1

Let $a\in X$ and consider the _status quo rule at $a$_,
$f^{a}:\mathcal{P}^{n}\longrightarrow X$, defined as

$f^{a}(P)=\begin{cases}x&\text{if }t(P_{i})=x\text{ for each }i\in N\\\
a&\text{otherwise.}\\\ \end{cases}$

Observe that, if $P_{i}\in\mathcal{P}$ is such that $t(P_{i})=a$, then
$O^{f^{a}}(P_{i})=\\{a\\}$ and thus $V_{i}=X\setminus\\{a\\}.$ Furthermore,
for any $P_{i}\in\mathcal{P},$ $O^{f^{a}}(P_{i})=\\{a,t(P_{i})\\}$. Therefore,
$W(P_{i},O^{f^{a}}(P_{i}))=aR_{i}W(P_{i},O^{f^{a}}(P_{i}^{\prime}))$ and
$B(P_{i},O^{f^{a}}(P_{i}))=t(P_{i})R_{i}B(P_{i},O^{f^{a}}(P_{i}^{\prime}))$
for each $P_{i}^{\prime}\in\mathcal{P}.$ Hence, $f^{a}$ is NOM.

The previous example shows that the condition of a rule having no vetoers is
far from being necessary for the rule to be NOM. What turns out to be
important is what kind of vetoes are admissible by the rule. Next, we
introduce a particular type of veto power that allows us to state a necessary
and sufficient condition for NOM in tops-only rules. We say that the veto of
an alternative by an agent is strong if the report of _any_ preference with
top different from the alternative forces the rule to never select it.
Formally,

###### Definition 3

Let $i\in N$ and $x\in X$. Agent $\boldsymbol{i$stronglyvetoes$x}$ if
$\mathcal{V}_{i}^{x}=\\{P_{i}\in\mathcal{P}:t(P_{i})\neq x\\}.$

Denote by $SV_{i}$ the set of all alternatives strongly vetoed by agent $i$.
Note that $SV_{i}\subseteq V_{i}$ for each $i\in N$. Clearly, the sets
$V_{i},SV_{i}$ and $\mathcal{V}^{x}_{i}$ depend on $f$ but we omit this
reference to ease notation.

###### Theorem 1

A tops-only rule is NOM if and only if every veto is a strong veto, i.e.,
$SV_{i}=V_{i}$ for each agent $i\in N$.777When $m=2$ (two alternatives), the
condition $SV_{i}=V_{i}$ is equivalent to the simple condition that agent $i$
does not veto $t(P_{i})$ with $P_{i}$.

_Proof._ Let $f:\mathcal{P}^{n}\longrightarrow X$ be a tops-only rule.

($\Longrightarrow$) Assume there is $i\in N$ such that $V_{i}\neq SV_{i}.$
Since $SV_{i}\subseteq V_{i}$, $V_{i}\neq\emptyset$ and there is $x\in X$ such
that $x\in V_{i}\setminus SV_{i}$. Then,

$\mathcal{V}_{i}^{x}\neq\\{P_{i}\in\mathcal{P}:t(P_{i})\neq x\\}.$ (3)

By (3), there are two cases to consider:

  1. $\boldsymbol{1}.$

There is
$\boldsymbol{P^{\prime}_{i}\in\mathcal{V}_{i}^{x}$issuchthat$t(P^{\prime}_{i})=x}$.
By ontoness, there is $(P_{i},P_{-i})\in\mathcal{P}^{n}$ such that
$f(P_{i},P_{-i})=x.$ Furthermore, $t(P_{i})\neq x$, since otherwise
$t(P_{i})=x$ and tops-onlyness would imply
$P_{i}^{\prime}\notin\mathcal{V}_{i}^{x}$. Let
$\overline{P}_{i}\in\mathcal{P}$ be such that $t(\overline{P}_{i})=t(P_{i})$
and $b(\overline{P}_{i})=x$. By tops-onlyness, $f(\overline{P}_{i},P_{-i})=x.$
Since $P^{\prime}_{i}\in\mathcal{V}_{i}^{x}$, $x\notin O^{f}(P_{i}^{\prime}).$
Then, $f(P_{i}^{\prime},P_{-i})\neq x$ and therefore
$f(P_{i}^{\prime},P_{-i})\overline{P}_{i}x=f(\overline{P}_{i},P_{-i})$,
implying that $P_{i}^{\prime}$ is a profitable manipulation of $f$ at $P_{i}$.
Furthermore, as $x\notin O^{f}(P_{i}^{\prime})$,

$W(\overline{P}_{i},O^{f}(P_{i}^{\prime}))\ \overline{P}_{i}\
x=W(\overline{P}_{i},O^{f}(\overline{P}_{i})).$

Thus, $P_{i}^{\prime}$ is an obvious manipulation of $f$.

  2. $\boldsymbol{2}.$

There is $\boldsymbol{P_{i}\in\mathcal{P}$suchthat$t(P_{i})\neq
x$and$P_{i}\notin\mathcal{V}_{i}^{x}}$. As $P_{i}\notin\mathcal{V}_{i}^{x}$,
there is $P_{-i}\in\mathcal{P}^{n-1}$ such that $f(P_{i},P_{-i})=x.$ Let
$\overline{P}_{i}\in\mathcal{P}$ be such that $t(\overline{P}_{i})=t(P_{i})$
and $b(\overline{P}_{i})=x$. By tops-onlyness, $f(\overline{P}_{i},P_{-i})=x.$
Since $x\in V_{i},$ there is $P_{i}^{\prime}\in\mathcal{P}$ such that
$P_{i}^{\prime}\in\mathcal{V}_{i}^{x},$ and the proof follows as in the
previous case.

($\Longleftarrow$) Let $i\in N$ be such that $V_{i}=SV_{i}.$ We will prove
that agent $i$ has no obvious manipulations. If $V_{i}=\emptyset,$ the proof
is trivial. Assume that $V_{i}\neq\emptyset.$ For each $P_{i}\in\mathcal{P}$,
as $V_{i}=SV_{i},$

$O^{f}(P_{i})=(X\setminus V_{i})\cup\\{t(P_{i})\\}.$

Then, for each $P^{\prime}_{i}\in\mathcal{P}$,

$B(P_{i},O^{f}(P_{i}))=t(P_{i})\ R_{i}\ B(P_{i},O^{f}(P_{i}^{\prime}))$

and

$W(P_{i},O^{f}(P_{i}))=W(P_{i},(X\setminus V_{i})\cup\\{t(P_{i})\\})\ R_{i}\
W(P_{i},(X\setminus
V_{i})\cup\\{t(P_{i}^{\prime})\\})=W(P_{i},O^{f}(P_{i}^{\prime})).$

Hence, $i$ does not have an obvious manipulation. $\square$

Corollary 1 shows that under efficiency and tops-onlyness NOM implies a very
limited veto power: at most one agent can veto some alternatives or only one
alternative can be vetoed by some agents.

###### Corollary 1

An efficient and tops-only rule is NOM if and only if some of the following
statements hold:

  1. (i)

There is at most one $i\in N$ such that $V_{i}\neq\emptyset$ and, moreover,
$SV_{i}=V_{i}$.

  2. (ii)

There is $y\in X$ such that $SV_{i}=V_{i}\subseteq\\{y\\}$, for each $i\in N$.

_Proof._ Let $f:\mathcal{P}^{n}\longrightarrow X$ be an efficient and tops-
only rule.

($\Longrightarrow$) Assume both conditions (i) and (ii) do not hold. Then,
there are distinct $i,j\in N$ and distinct $x,y\in X$ such that $x\in V_{i}$
and $y\in V_{j}.$ Now let $P\in\mathcal{P}^{n}$ be such that
$P_{i}:y,x,\ldots$ and $P_{k}:x,y,\ldots$ for each $k\in N\setminus\\{i\\}$.
By efficiency, $f(P)\in\\{x,y\\}.$ Therefore, $P_{i}\notin\mathcal{V}_{i}^{x}$
or $P_{j}\notin\mathcal{V}_{i}^{y}.$ So, by Theorem 1, $f$ is not NOM.

($\Longleftarrow$) By Theorem 1 it is clear that either condition is
sufficient for $f$ to be NOM. $\square$

Corollary 2 states that, under efficiency and anonymity, non-obvious
manipulability is equivalent to having at most one alternative vetoed and
that, if there is one such alternative, the veto is unanimous.

###### Corollary 2

An efficient, anonymous and tops-only rule is NOM if and only if either
$V_{i}=\emptyset$ for each $i\in N$ or there is $y\in X$ such that
$SV_{i}=V_{i}=\\{y\\}$ for each $i\in N$.

_Proof._ It follows from Corollary 1 and anonymity. $\square$

##  4 Applications

In this section, we apply Theorem 1 to study two classes of tops-only voting
rules in two separate (but related) voting problems. Our results allow us to
discriminate those rules in each class that are non-obviously manipulable in
the universal domain of preferences.

In the first problem, presented in subsection 4.1, alternatives are endowed
with a linear order structure. When preferences are single peaked over that
order, the family of (generalized) median voting schemes encompass all tops-
only and strategy-proof (onto) rules. In the second problem, presented in
subsection 4.2, alternatives consist of _subsets_ of objects chosen from a
fixed finite set. When preferences are separable, the class of voting by
committees encompass all strategy-proof (onto) rules.

###  4.1 Median Voter Schemes

In this subsection assume that $X$ is an ordered set. Without loss of
generality, assume $X=\\{a,a+1,a+2,\ldots,b\\}\subseteq\mathbb{N}$ and
$b=a+(m-1).$ A preference $P_{i}\in\mathcal{P}$ is _single-peaked_ on $X$ if
for all $x,y\in X$ such that $x<y<t(P_{i})$ or $t(P_{i})<y<x$, we have
$t(P_{i})P_{i}yP_{i}x$. We denote the domain of all single-peaked preferences
on $X$ by $\mathcal{SP}$. Note that $\mathcal{SP}\subsetneq\mathcal{P}$.

Moulin (1980) characterizes the family of strategy-proof and tops-only (onto)
rules on the domain of single-peaked preferences. This family contains many
non-dictatorial rules. For example, when $n$ is odd, consider the rule
$f:\mathcal{P}^{n}\longrightarrow X$ that selects, for each preference profile
$P=(P_{1},\ldots,P_{n})\in\mathcal{P}^{n}$, the median among the top
alternatives of the $n$ agents; namely,
$f(P)=med\\{t(P_{1}),\ldots,t(P_{n})\\}$.888Given a set of real numbers
$\\{x_{1},\ldots,x_{K}\\}$, where $K$ is odd, define its median as
$med\\{x_{1},\ldots,x_{K}\\}=y$, where $y$ is such that $|\\{1\leq k\leq
K:x_{k}\leq y\\}|\geq\frac{K}{2}$ and $|\\{1\leq k\leq K:x_{k}\geq
y\\}|\geq\frac{K}{2}$. Since $K$ is odd the median is unique and belongs to
the set $\\{x_{1},\ldots,x_{K}\\}$. This rule is anonymous, efficient, tops-
only, and strategy-proof on $\mathcal{SP}$. All other rules in the family
given by Moulin (1980) are extensions of $f$. Following Moulin (1980), and
before presenting the general result, we first introduce the anonymous
subclass and characterize those rules which are NOM. After that, we present
the general class of all strategy-proof and tops-only rules on
$\mathcal{SP}^{n}$ and characterize those that are NOM when operating on
domain $\mathcal{P}^{n}$.

####  4.1.1 Anonymity

A rule $f:\mathcal{P}^{n}\longrightarrow X$ is a median voter scheme if there
is a vector $\alpha=(\alpha_{1},\ldots,\alpha_{n-1})\in X^{n-1}$ of $n-1$
fixed ballots such that, for each $P\in\mathcal{P}^{n}$,

$f(P)=med\\{t(P_{1}),\ldots,t(P_{n}),\alpha_{1},\ldots,\alpha_{n-1}\\}.$

Without loss of generality, throughout the paper we assume that
$\alpha_{1}\leq\ldots\leq\alpha_{n-1}$. When we want to stress the dependence
of the scheme on the vector $\alpha$ of fixed ballots, we write $f^{\alpha}.$
Also, to simplify notation, we use $O^{\alpha}(P_{i})$ instead of
$O^{f^{\alpha}}(P_{i})$. The characterization of median voter schemes is as
follows:

###### Fact 1

(Moulin, 1980) A (onto) rule $f:\mathcal{SP}^{n}\longrightarrow X$ is
strategy-proof, tops-only, and anonymous if and only if it is a median voter
scheme.999The definitions of strategy-proofness, tops-onlyness and anonymity
on an arbitrary subdomain $\mathcal{U}^{n}\subsetneq\mathcal{P}^{n}$ are
straightforward adaptations of the definitions given for the universal domain.

Median voter schemes are strategy-proof on the domain $\mathcal{SP}^{n}$ of
single-peaked preferences. However, when they operate on the larger domain
$\mathcal{P}^{n}$ they may become manipulable. Then, all median voter schemes
are equivalent from the classical manipulability point of view. Next, we give
a simple test to identify which median voter schemes are NOM.

###### Theorem 2

A median voter scheme $f^{\alpha}:\mathcal{P}^{n}\longrightarrow X$ is NOM if
and only if

$\alpha_{1}\in\\{a,a+1\\}\text{ and }\alpha_{n-1}\in\\{b-1,b\\}.$

In order to prove Theorem 2, the following remark and lemma are useful.

###### Remark 1

By definition of option set and $f^{\alpha}$, for each $P_{i}\in\mathcal{P}$,

$O^{\alpha}(P_{i})=\begin{cases}\\{t(P_{i}),t(P_{i})+1,\ldots,\alpha_{n-1}\\}&\text{if
}t(P_{i})<\alpha_{1}\\\
\\{\alpha_{1},\alpha_{1}+1,\ldots,\alpha_{n-1}\\}&\text{if }\alpha_{1}\leq
t(P_{i})\leq\alpha_{n-1}\\\
\\{\alpha_{1},\alpha_{1}+1,\ldots,t(P_{i})\\}&\text{if
}\alpha_{n-1}<t(P_{i})\\\ \end{cases}$

To see this when $t(P_{i})<\alpha_{1}$, take
$x\in\\{t(P_{i}),t(P_{i})+1,\ldots,\alpha_{n-1}\\}$ and let
$P_{-i}\in\mathcal{P}^{n-1}$ be such that $t(P_{j})=x$ for each $j\in
N\setminus\\{i\\}$. Then, $f^{\alpha}(P_{i},P_{-i})=x$ an so $x\in
O^{\alpha}(P_{i}).$ Furthermore, if $x<t(P_{i})$, let
$P_{-i}\in\mathcal{P}^{n-1}$ be such that $t(P_{j})=x$ for each $j\in
N\setminus\\{i\\}.$ Then, $f^{\alpha}(P_{i},P_{-i})=t(P_{i})$ and, therefore,
$f^{\alpha}(P_{i},P_{-i}^{\prime})\neq x$ for each
$P_{-i}^{\prime}\in\mathcal{P}^{n-1}$. Thus, $x\notin O^{\alpha}(P_{i})$.
Symmetrically, it can be proven that $x\notin O^{\alpha}(P_{i})$ when
$x>\alpha_{n-1}$. The cases $t(P_{i})\in\\{\alpha_{1},\ldots,\alpha_{n-1}\\}$
and $t(P_{i})>\alpha_{n-1}$ follow similar arguments and are omitted.

###### Lemma 1

Let $f^{\alpha}:\mathcal{P}^{n}\longrightarrow X$ be a median voter scheme and
let $i\in N$. Then, $x\in V_{i}$ if and only if either $x<\alpha_{1}$ or
$x>\alpha_{n-1}$.

_Proof._ ($\Longrightarrow$) Assume that $x\in V_{i}.$ Then, there is
$P_{i}\in\mathcal{P}$ such that $x\notin O^{\alpha}(P_{i}).$ Thus, by Remark
1, either $x<\alpha_{1}$ or $x>\alpha_{n-1}$.

($\Longleftarrow$) First, assume $x<\alpha_{1}$ and let $P_{i}\in\mathcal{P}$
be such that $t(P_{i})=\alpha_{1}.$ Then,
$x\notin\\{\alpha_{1},\alpha_{1}+1,\ldots,\alpha_{n-1}\\}=O^{\alpha}(P_{i}).$
Thus, $x\in V_{i}.$ Now, let $x>\alpha_{n-1}$ and let $P_{i}\in\mathcal{P}$ be
such that $t(P_{i})=\alpha_{n-1}.$ Then,
$x\notin\\{\alpha_{1},\alpha_{1}+1,\ldots,\alpha_{n-1}\\}=O^{\alpha}(P_{i}).$
Thus, $x\in V_{i}.$ $\square$

_Proof of Theorem 2_. Let $f^{\alpha}:\mathcal{P}^{n}\longrightarrow X$ be a
median voter scheme and let $i\in N.$ The proof relies in the following two
facts:

$x<\alpha_{1}\text{ and }x\in SV_{i}\text{ if and only if }x=a,$ (4)

and

$\alpha_{n-1}<x\text{ and }x\in SV_{i}\text{ if and only if }x=b.$ (5)

To see (4), assume first that $x\in SV_{i}$ and $a<x<\alpha_{1}.$ Let
$P_{i}\in\mathcal{P}$ be such that $t(P_{i})=a.$ Then, $x\in
O^{\alpha}(P_{i})=\\{a,a+1,\ldots,\alpha_{n-1}\\},$ contradicting that $x\in
SV_{i}$. Next, assume that $x=a$. Let $P_{i}\in\mathcal{P}$ be such that
$t(P_{i})\neq a$. Then, by Remark 1, $x\notin O^{\alpha}(P_{i}).$ Hence, $i\in
SV_{i}$. Thus, (4) holds. The proof of (5) is symmetric and therefore it is
omitted. To complete the proof of the theorem, assume $f^{\alpha}$ is NOM. By
Theorem 1 and Lemma 1, $SV_{i}=\\{x\in X:x<\alpha_{1}\text{ or
}x>\alpha_{n-1}\\}$. By (4) and (5), $\\{x\in X:x<\alpha_{1}\text{ or
}x>\alpha_{n-1}\\}\subseteq\\{a,b\\}$. Therefore, $\alpha_{1}\in\\{a,a+1\\}$
and $\alpha_{n-1}\in\\{b-1,b\\}$. Now assume that $\alpha_{1}\in\\{a,a+1\\}$
and $\alpha_{n-1}\in\\{b-1,b\\}$. Then, $\\{x\in X:x<\alpha_{1}\text{ or
}x>\alpha_{n-1}\\}\subseteq\\{a,b\\}$. By Lemma 1, $V_{i}\subseteq\\{a,b\\}$
and, hence, by (4) and (5), $SV_{i}=V_{i}$. Therefore, by Theorem 1,
$f^{\alpha}$ is NOM. $\square$

####  4.1.2 General Case

Now we present the characterization of all strategy-proof, tops-only (onto)
rules on the domain of single-peaked preferences for all $n\geq 2$. A
generalized median voter scheme can be identified with a set of fixed ballots
$\\{p_{S}\\}_{S\in 2^{N}}$ on $X=\\{a,a+1,\ldots,b\\}$, one for each subset of
agents $S$. Then, for each preference profile, the generalized median voter
scheme identified with $\\{p_{S}\\}_{S\in 2^{N}}$ selects the alternative
$x\in X$ that is the smallest one with the following two properties: (i) there
is a subset of agents $S$ whose top alternatives are smaller than or equal to
$x$, and (ii) the fixed ballot $p_{S}$ associated to $S$ is also smaller than
or equal to $x$. Formally, we say that a collection $p=\\{p_{S}\\}_{S\in
2^{N}}$ is a monotonic family of fixed ballots if: (i) $p_{S}\in X$ for all
$S\in 2^{N}$ with $p_{N}=a$ and $p_{\varnothing}=b$, and (ii) $T\subseteq Q$
implies $p_{Q}\leq p_{T}$. A rule $f:\mathcal{P}^{n}\longrightarrow X$ is a
_generalized median voter scheme_ if there exits a monotonic family of fixed
ballots $p=\\{p_{S}\\}_{S\in 2^{N}}$ such that, for each
$P\in\mathcal{P}^{n},$

$f(P)=\min_{S\in 2^{N}}\max_{j\in S}\\{t(P_{j}),p_{S}\\}.$

When we want to stress the dependence of the scheme on the collection $p$ of
fixed ballots, we write $f^{p}.$ Also, to simplify notation, we use
$O^{p}(P_{i})$ instead of $O^{f^{p}}(P_{i})$. The characterization of
generalized median voter schemes is as follows:

###### Fact 2

(Moulin, 1980) A (onto) rule $f:\mathcal{SP}^{n}\longrightarrow X$ is
strategy-proof and tops-only if and only if it is a generalized median voter
scheme.

The dictatorial rules are strategy-proof and tops-only, therefore they are
generalized median voting schemes. It is easy to see that if the agents $i$ is
the dictator, then $p_{\\{i\\}}=a$ and $p_{N\backslash\\{i\\}}=b$. Trivially
these rules are NOM. Next, we give a simple test to identify which non-
dictatorial generalized median voter schemes are NOM.

###### Theorem 3

A non-dictatorial generalized median voter scheme
$f^{p}:\mathcal{P}^{n}\longrightarrow X$ is NOM if and only if, for each $i\in
N$,

$p_{N\setminus\\{i\\}}\in\\{a,a+1\\}\text{ and }p_{\\{i\\}}\in\\{b-1,b\\}.$
(6)

In order to prove Theorem 3, the following remark and lemma are useful.

###### Remark 2

By monotonicity of $p,$ $p_{N\setminus\\{i\\}}\leq p_{S}$ for each $S$ such
that $i\notin S$ and $p_{T}\leq p_{\\{i\\}}$ for each $T$ such that $i\in T.$
Assume that $p_{N\setminus\\{i\\}}\leq p_{\\{i\\}}.$ By definition of option
set and $f^{p}$, for each $P_{i}\in\mathcal{P}$,

$O^{p}(P_{i})=\begin{cases}\\{t(P_{i}),t(P_{i})+1,\ldots,p_{\\{i\\}}\\}&\text{if
}t(P_{i})<p_{N\setminus\\{i\\}}\\\
\\{p_{N\setminus\\{i\\}},p_{N\setminus\\{i\\}}+1,\ldots,p_{\\{i\\}}\\}&\text{if
}p_{N\setminus\\{i\\}}\leq t(P_{i})\leq p_{\\{i\\}}\\\
\\{p_{N\setminus\\{i\\}},p_{N\setminus\\{i\\}}+1,\ldots,t(P_{i})\\}&\text{if
}p_{\\{i\\}}<t(P_{i})\\\ \end{cases}$

The proof follows an argument similar to the one used in Remark 1, with
$p_{N\setminus\\{i\\}}$ playing the role of $\alpha_{1}$ and $p_{\\{i\\}}$
playing the role of $\alpha_{n-1}$.

###### Lemma 2

Let $f^{p}:\mathcal{P}^{n}\longrightarrow X$ be a generalized median voter
scheme and let $i\in N$.

  1. (i)

If $p_{N\setminus\\{i\\}}\leq p_{\\{i\\}}$, then $x\in V_{i}$ if and only if
either $x<p_{N\setminus\\{i\\}}$ or $x>p_{\\{i\\}}.$

  2. (ii)

If $p_{\\{i\\}}<p_{N\setminus\\{i\\}}$, then $V_{i}=X.$

_Proof._ Let $f^{p}:\mathcal{P}^{n}\longrightarrow X$ be a generalized median
voter scheme and let $i\in N$.

(i) The proof follows an argument similar to the one used in the proof of
Lemma 1 (invoking Remark 2 instead of Remark 1).

(ii) Let $x\in X$. There are two cases to consider:

  * $\boldsymbol{1}.$

$\boldsymbol{p_{\\{i\\}}<x}.$ Let $P_{i}\in\mathcal{P}$ be such that
$t(P_{i})=p_{\\{i\\}}$. Then, $f^{p}(P_{i},P_{-i})\leq p_{\\{i\\}}$ for each
$P_{-i}\in\mathcal{P}^{n-1}.$ This implies that $x\in V_{i}.$

  * $\boldsymbol{2}.$

$\boldsymbol{x\leq p_{\\{i\\}}<p_{N\setminus\\{i\\}}}.$ Let
$P_{i}\in\mathcal{P}$ such that $t(P_{i})=p_{N\setminus\\{i\\}}$. Then,
$f^{p}(P_{i},P_{-i})\geq p_{N\setminus\\{i\\}}$ for each
$P_{-i}\in\mathcal{P}^{n-1}$ (because $p_{N\setminus\\{i\\}}\leq p_{S}$ for
each $S$ such that $i\notin S$). This implies that $x\in V_{i}.$

In both cases $x\in V_{i}$. Therefore, $V_{i}=X.$ $\square$

_Proof of Theorem 3_. Let $f^{p}$ be a non-dictatorial generalized median
voter scheme.

($\Longleftarrow$) The proof that condition (6) implies that $f^{p}$ is NOM
follows a similar argument to that of the proof of Theorem 2, with
$p_{N\setminus\\{i\\}}$ and $p_{i}$ playing the role of $\alpha_{1}$ and
$\alpha_{n-1}$, respectively. Therefore it is omitted.

($\Longrightarrow$) Assume that $f^{p}$ is NOM. First, assume there is an
agent $i^{\star}\in N$ such that
$p_{\\{i^{\star}\\}}<p_{N\setminus\\{i^{\star}\\}}.$ Then, by Lemma 2 ,
$V_{i^{\star}}=X.$ By Theorem 1, $SV_{i^{\star}}=X.$ Thus, agent $i^{\star}$
is a dictator, contradicting that $f^{p}$ is non-dictatorial. Therefore
$p_{N\setminus\\{i\\}}\leq p_{\\{i\\}}$ for each $i\in N.$ Now, the proof
follows a similar argument to the proof of Theorem 2 and, therefore, it is
omitted. $\square$

###  4.2 Voting by Committees

Now assume that agents have to choose a subset of objects from a set $K$ (with
$\left|K\right|\geq 2$). Then, in this case, $X=2^{K}$ and elements of $X$ are
subsets of $K$. A generic element of $K$ is denoted by $k$ and a generic
element of $X$ is denoted by $S$ . As an example, think of objects as
candidates to become new members of a society that have to be elected by the
current members of the society. Barberà et al. (1991) characterize, on the
restricted domain of separable preferences, the family of all strategy-proof
(onto) rules as the class of voting by committees. A preference $P_{i}$ of
agent $i$ is separable if the division between good objects (those $k\in K$
such that $\\{k\\}P_{i}\emptyset$) and bad objects (those $k\in K$ such that
$\emptyset P_{i}\\{k\\}$) guides the ordering of subsets in the sense that
adding a good object leads to a better set, while adding a bad object leads to
a worse set. Formally, agent $i$’s preference $P_{i}\in\mathcal{P}$ on $2^{K}$
is _separable_ if for all $S\in 2^{K}$ and $k\notin S$,

$S\cup\\{k\\}P_{i}x\text{ if and only if }\\{k\\}P_{i}\emptyset.$

Let $\mathcal{S}$ be the set of all separable preferences on $2^{K}$. Observe
that for any separable preference its top is the subset consisting of all good
objects. That is, for any separable preference $P_{i}\in\mathcal{S},$

$t(P_{i})=\\{k\in K:\\{k\\}P_{i}\emptyset\\}.$

We now define the class of rules known as voting by committees. Let $N$ be a
set of agents and $k\in K$ be an object. A _committee $\mathcal{W}_{k}$ for
$k$_ is a non-empty set of non-empty coalitions (subsets) of $N$, that
satisfies the following monotonicity condition:

$M\in\mathcal{W}_{k}\text{ and }M\subseteq M^{\prime}\text{ imply
}M^{\prime}\in\mathcal{W}_{k}.$

A rule $f:\mathcal{P}^{n}\longrightarrow 2^{K}$ is a voting by committees if
for each $k\in K$ there is a committee $\mathcal{W}_{k}$ such that, for each
$P\in\mathcal{P}^{n}$,

$k\in f(P)\text{ if and only if }\\{i\in N:k\in
t(P_{i})\\}\in\mathcal{W}_{k}.$

By definition, these rules are tops-only and the selected subset of objects at
each preference profile is obtained by analyzing one object at a time. Given a
committee $\mathcal{W}=\\{W_{k}\\}_{k\in K}$, let $f^{\mathcal{W}}$ be its
associated voting by committees. Furthermore, and to ease notation, we write
$O^{\mathcal{W}}(P_{i})$ instead of $O^{f^{\mathcal{W}}}(P_{i})$. Barberà et
al. (1991) characterize this class when it operates on the separable domain as
follows.

###### Fact 3

(Barberà et al., 1991) A (onto) rule $f:\mathcal{S}^{n}\longrightarrow 2^{K}$
is strategy-proof if and only if it is voting by committees.

Observe that, since voting by committees are tops-only, tops-onlyness is
implied by strategy-proofness on the domain of separable preferences.

It is clear that dictatorial voting by committees are NOM. In these rules, the
dictator $i\in N$ is such that $i\in M$ for all $M\in\mathcal{W}_{k}$ and
$\\{i\\}\in\mathcal{W}_{k}$ for all $k\in K$. Next, we give a simple test to
identify which non-dictatorial voting by committees are NOM.

###### Theorem 4

A non-dictatorial voting by committees
$f^{\mathcal{W}}:\mathcal{P}^{n}\longrightarrow 2^{K}$ is NOM if and only if
for each $k\in K$:

  1. (i)

$\bigcap_{M\in\mathcal{W}_{k}}M=\emptyset$, and

  2. (ii)

$|M|\geq 2$ for each $M\in\mathcal{W}_{k}$.

In order to prove Theorem 4, the following remark and lemma are useful.

###### Remark 3

Let $i\in N$. If $S\in 2^{K}$ is such that

  1. (i)

for each $k\in S$, $i\notin\bigcap_{M\in\mathcal{W}_{k}}M$ and

  2. (ii)

for each $k\notin S$, $\\{i\\}\notin\mathcal{W}_{k}$,

then

$S\in O^{\mathcal{W}}(P_{i})\text{ \ for each \ }P_{i}\in\mathcal{P}.$ (7)

To see this, let $P_{i}\in\mathcal{P}$ and let $P_{-i}\in\mathcal{P}^{n-1}$ be
such that $t(P_{j})=S$ for each $j\in N\setminus\\{i\\}$. Observe that
condition (i) for $S$ implies that $N\setminus\\{i\\}\in\mathcal{W}_{k}$ for
each $k\in S$ and, thus, $S\subseteq f^{\mathcal{W}}(P_{i},P_{-i}).$ Moreover,
$k\notin S$ implies, by condition (ii) for $S$, that $k\notin
f^{\mathcal{W}}(P_{i},P_{-i})$. Therefore, $f^{\mathcal{W}}(P_{i},P_{-i})=S$
and (7) holds.

###### Lemma 3

Let $f^{\mathcal{W}}:\mathcal{P}^{n}\longrightarrow 2^{K}$ be a voting by
committees, and let $i\in N$. Then, $S\in V_{i}$ if and only if there is
$k^{\star}\in K$ such that either:

  1. (i)

$k^{\star}\in S$ and $i\in\cap_{M\in\mathcal{W}_{k^{\star}}}M$, or

  2. (ii)

$k^{\star}\notin S$ and $\\{i\\}\in\mathcal{W}_{k^{\star}}$.101010In the
context of voting by committees, when $i\in M$ for each
$M\in\mathcal{W}_{k^{\star}}$, it is usual to say that agent $i$ is a vetoer
of $k^{\star}$ in the sense that alternative $k^{\star}$ must be in the top of
agents $i$’s preference to be included in the outcome of the rule. Such veto
notion is different from the veto condition in the present paper. Our notion
is used to describe when an agent vetoes a subset $S\subseteq 2^{K}$ in the
sense that there is a preference $P_{i}$ for agent $i$ such that $S$ is never
chosen when $i$ declares $P_{i}$.

_Proof._ Let $f^{\mathcal{W}}:\mathcal{P}^{n}\longrightarrow 2^{K}$ be a
voting by committees and let $i\in N$.

($\Longrightarrow$) Assume that $S\in V_{i}.$ Then, there is
$P_{i}\in\mathcal{P}$ such that $S\notin O^{\mathcal{W}}(P_{i}).$ Thus, by
Remark 3, there is $k^{\star}\in K$ such that either $k^{\star}\in S$ and
$i\in\cap_{M\in\mathcal{W}_{k^{\star}}}M$, or $k^{\star}\notin S$ and
$\\{i\\}\in\mathcal{W}_{k^{\ast}}$.

($\Longleftarrow$) There are two cases to consider:

  1. $\boldsymbol{1}.$

There is $\boldsymbol{k^{\star}\in K$suchthat$k^{\star}\in
S$and$i\in\cap_{M\in\mathcal{W}_{k^{\star}}}M}$. Let $P_{i}\in\mathcal{P}$ be
such that $k^{\star}\notin t(P_{i}).$ Then, $k^{\star}\notin f(P_{i},P_{-i})$
and, therefore, $f(P_{i},P_{-i})\neq S$ for each $P_{-i}\in\mathcal{P}^{n-1}.$
Thus, agent $i$ vetoes $S$ with $P_{i}.$ Hence, $S\in V_{i}.$

  2. $\boldsymbol{2}.$

There is $\boldsymbol{k^{\star}\in K$suchthat$k^{\star}\notin
S$and$\\{i\\}\in\mathcal{W}_{k^{\star}}}$. Let $P_{i}\in\mathcal{P}$ be such
that $k^{\star}\in t(P_{i}).$ Then, $k^{\star}\in f(P_{i},P_{-i})$ and,
therefore, $f(P_{i},P_{-i})\neq S$ for each $P_{-i}\in\mathcal{P}^{n-1}.$
Thus, agent $i$ vetoes $S$ with $P_{i}.$ Hence, $S\in V_{i}.$

$\square$

_Proof of Theorem 4_. Let $f^{\mathcal{W}}:\mathcal{P}^{n}\longrightarrow
2^{K}$ be a non-dictatorial voting by committees.

($\Longleftarrow$) By Lemma 3, (i) and (ii) in Theorem 4 imply that
$V_{i}=\emptyset$ for each $i\in N.$ Then, $SV_{i}=V_{i}$ for each $i\in N$
and, by Theorem 1, $f^{\mathcal{W}}$ is NOM.

($\Longrightarrow$) Let $f^{\mathcal{W}}$ be NOM. Then, by Theorem 1,
$SV_{i}=V_{i}$ for each $i\in N$. The next claim states that $V_{i}=\emptyset$
for each $i\in N.$

Claim: $\boldsymbol{V_{i}=\emptyset}$ for each $\boldsymbol{i\in N}.$ Assume,
by contradiction, that there are $i\in N$ and $S\in X$ such that $S\in V_{i}$.
We will show that such $i$ is a dictator, i.e., for each $k\in K$,

$\\{i\\}\in\mathcal{W}_{k},$ (8)

and

$i\in\bigcap_{M\in\mathcal{W}_{k}}M.$ (9)

By Lemma 3, there are two cases to consider:

  1. $\boldsymbol{1}$.

There is $\boldsymbol{k^{\star}\in
S$and$i\in\bigcap_{M\in\mathcal{W}_{k^{\star}}}M}$. By Lemma 3,
$\\{k^{\star}\\}\in V_{i}.$ Assume (8) does not hold. Then, there is $k\in K$
such that $\\{i\\}\notin\mathcal{W}_{k}.$ Let $P_{i}\in\mathcal{P}$ be such
that $t(P_{i})=\\{k,k^{\star}\\}$. Then, $\\{k^{\star}\\}\in
O^{\mathcal{W}}(P_{i})$ and, therefore, $\\{k^{\star}\\}\notin SV_{i}$. This
contradicts $SV_{i}=V_{i},$ so (8) holds. Now, assume that (9) does not hold.
Then, there is $k\in K$ and $M\in\mathcal{W}_{k}$ such that $i\notin M.$ By
Lemma 3, $\\{k^{\star},k\\}\in V_{i}.$ Let $P_{i}\in\mathcal{P}$ be such that
$t(P_{i})=\\{k^{\star}\\}$. Then, $\\{k,k^{\star}\\}\in
O^{\mathcal{W}}(P_{i})$. Thus, $\\{k,k^{\star}\\}\notin SV_{i}.$ This
contradicts $SV_{i}=V_{i},$ so (9) holds. Since both (8) and (9) hold, $i$ is
a dictator.

  2. $\boldsymbol{2}$.

There is $\boldsymbol{k^{\star}\notin
S$and$\\{i\\}\in\mathcal{W}_{k^{\star}}}$. By Lemma 3, $\emptyset\in V_{i}.$
Assume (8) does not hold. Then, there is $k\in K$ such that
$\\{i\\}\notin\mathcal{W}_{k}.$ Let $P_{i}\in\mathcal{P}$ be such that
$t(P_{i})=\\{k\\}$. Then, $\emptyset\in O^{\mathcal{W}}(P_{i})$ and,
therefore, $\emptyset\notin SV_{i}$. This contradicts $SV_{i}=V_{i},$ so (8)
holds. Now, assume that (9) does not hold. Then, there is $k\in K$ and
$M\in\mathcal{W}_{k}$ such that $i\notin M.$ By Lemma 3, $\\{k\\}\in V_{i}.$
Let $P_{i}\in\mathcal{P}$ be such that $t(P_{i})=\emptyset$. Then, $\\{k\\}\in
O^{\mathcal{W}}(P_{i})$. Thus, $\\{k\\}\notin SV_{i}.$ This contradicts
$SV_{i}=V_{i},$ so (9) holds. Since both (8) and (9) hold, $i$ is a dictator.

The fact that $i$ is a dictator contradicts that $f^{\mathcal{W}}$ is non-
dictatorial. Therefore, $V_{i}=\emptyset$ for each $i\in N.$ This finishes the
proof of the Claim.

In order to complete the proof of the theorem, observe that the Claim and
Lemma 3 imply (i) and (ii) in Theorem 4. $\square$

If we add anonymity to Fact 3 the class of voting by committees must be
reduced to a relevant subclass of rules which are called voting by quota. A
voting by committees is a voting by quota if, for each $k\in K$, there is
$q_{k}$, with $1\leq q_{k}\leq n$, such that the associated committee
$\mathcal{W}_{k}$ satisfies that

$M\in\mathcal{W}_{k}\text{ if and only if }\left|M\right|\geq q_{k}.$

Given $q=\\{q_{k}\\}_{k\in K}$, let $f^{q}$ be its associated voting by quota.
Next, we give a simple test to identify which voting by quota are NOM.

###### Corollary 3

A voting by quota $f^{q}:\mathcal{P}^{n}\longrightarrow 2^{K}$ is NOM if and
only if $2\leq q_{k}\leq n-1$ for each $k\in K$.

_Proof._ It follows easily by specifying Conditions (i) and (ii) in Theorem 4
to voting by quota. $\square$

Corollary 3 is rather surprising. In general, rules in which quotas are either
$1$ or $n$ are the most robust to manipulation within all voting by quota from
several standpoints (for example, see Arribillaga and Massó, 2017; Fioravanti
and Massó, 2022). Our result, in contrast, includes them within obviously
manipulable ones.

##  5 Final Remarks

Table 1 summarizes our main findings about tops-only, median voter (MV),
generalized median voter (GMV), voting by committees (VbC) and voting by quota
(VbQ) rules.

Tops-only |  $f$ NOM $\Longleftrightarrow$ $\forall i\in N:$ $SV_{i}=V_{i}$ |  Th. 1
---|---|---
MV |  $f^{\alpha}$ NOM $\Longleftrightarrow$ $\alpha_{1}\in\\{a,a+1\\}$ and $\alpha_{n-1}\in\\{b-1,b\\}$ |  Th. 2
GMV† |  $f^{p}$ NOM $\Longleftrightarrow$ $\forall i\in N:$ $p_{N\setminus\\{i\\}}\in\\{a,a+1\\}$ and $p_{\\{i\\}}\in\\{b-1,b\\}$ |  Th. 3
VbC† |  $f^{\mathcal{W}}$ NOM $\Longleftrightarrow$ $\forall k\in K:$ $\bigcap_{M\in\mathcal{W}_{k}}M=\emptyset$ and $|M|\geq 2$ $\forall M\in\mathcal{W}_{k}$ |  Th. 4
VbQ |  $f^{q}$ NOM $\Longleftrightarrow$ $\forall k\in K:$ $2\leq q_{k}\leq n-1$ |  Cor. 3

  * ${\dagger}$

The characterization applies to non-dictatorial rules.

Table 1: _Summary of results._

Three final remarks are in order. First, following the proof of Theorem 1, it
can be seen that the condition $SV_{i}=V_{i}$ for each $i\in N$ implies NOM
even when tops-onlyness is removed. Although clearly it is not a necessary
condition of NOM (see the proof of Lemma 5 in Aziz and Lam, 2021).

Second, a manipulation is called worst-case obvious if Condition (1) in
Definition 1 holds and best-case obvious if Condition (2) in Definition 1
holds. In the proof of Theorem 1, we show that $SV_{i}\neq V_{i}$ implies that
the rule has a worst-case obvious manipulation. Therefore, by Theorem 1, if a
rule does not have a worst-case obvious manipulation then it does not have a
best-case obvious manipulation either. Therefore, for top-only rules, a
manipulation is obvious if and only if it is a worst-case obvious
manipulation.

Finally, we present some observations for the case in which $X$ is infinite.
If adequate assumptions over the set of preferences are done in order that (1)
and (2) in Definition 1 are well-defined, Theorem 1 is also valid in such
context. For example, let $X=[a,b]\subseteq\mathbb{R}$ and let $\mathcal{U}$
be the set of all continuous preferences on $[a,b]$ with a unique top
(indifferences between non-top alternatives are admitted). If
$f^{\alpha}:\mathcal{U}^{n}\longrightarrow X$ is a median voter scheme and
$P_{i}\in\mathcal{U}$, then the option set is given by:

$O^{\alpha}(P_{i})=\begin{cases}[t(P_{i}),\alpha_{n-1}]&\text{if
}t(P_{i})<\alpha_{1}\\\ [\alpha_{1},\alpha_{n-1}]&\text{if
}t(P_{i})\in[\alpha_{1},\alpha_{1}]\\\ [\alpha_{1},t(P_{i})]&\text{if
}t(P_{i})>\alpha_{n-1}\\\ \end{cases}$

and, therefore, $O^{\alpha}(P_{i})$ is a closed interval. Hence, (1) and (2)
in Definition 1 are well-defined. For these rules, if $a<\alpha_{1}$, for any
$x\in X$ such that $a<x<\alpha_{1}$ an argument similar to the one used in the
proof of Lemma 1 shows that $x\in V_{i}$; and an argument similar to the one
used in the proof of Theorem 2 shows that $x\notin SV_{i}$. The same is true
if $\alpha_{n-1}<b$ for any $x\in X$ such that $\alpha_{n-1}<x<b.$ Therefore,
we have the following simple characterization of median voter schemes when
$X=[a,b]\subseteq\mathbb{R}$ .

###### Theorem 5

  1. (i)

A median voter scheme $f^{\alpha}:\mathcal{U}^{n}\longrightarrow[a,b]$ is NOM
if and only if $\alpha_{1}=a$ and $\alpha_{n-1}=b$.

  2. (ii)

A non-dictatorial generalized median voter scheme
$f^{p}:\mathcal{U}^{n}\longrightarrow[a,b]$ is NOM if and only if
$p_{N\backslash\\{i\\}}=a$ and $p_{\\{i\\}}=b$ for each $i\in N.$

## References

  * Arribillaga et al. (2022) Arribillaga, R. P., A. G. Bonifacio, and M. A. Fernandez (2022): “Regret-free truth-telling voting rules,” _arXiv preprint arXiv:2208.13853_.
  * Arribillaga and Massó (2017) Arribillaga, R. P. and J. Massó (2017): “Comparing voting by committees according to their manipulability,” _American Economic Journal: Microeconomics_ , 9, 74–107.
  * Aziz and Lam (2021) Aziz, H. and A. Lam (2021): “Obvious manipulability of voting rules,” in _International Conference on Algorithmic Decision Theory_ , Springer, 179–193.
  * Barberà (2011) Barberà, S. (2011): “Strategyproof social choice,” _Handbook of social choice and welfare_ , 2, 731–831.
  * Barbera and Peleg (1990) Barbera, S. and B. Peleg (1990): “Strategy-proof voting schemes with continuous preferences,” _Social choice and welfare_ , 7, 31–38.
  * Barberà et al. (1991) Barberà, S., H. Sonnenschein, and L. Zhou (1991): “Voting by committees,” _Econometrica_ , 59, 595–609.
  * Chatterji and Sen (2011) Chatterji, S. and A. Sen (2011): “Tops-only domains,” _Economic Theory_ , 46, 255–282.
  * Fioravanti and Massó (2022) Fioravanti, F. and J. Massó (2022): “False-name-proof and strategy-proof voting rules under separable preferences,” _Available at SSRN 4175113_.
  * Gibbard (1973) Gibbard, A. (1973): “Manipulation of voting schemes: a general result,” _Econometrica_ , 41, 587–601.
  * Moulin (1980) Moulin, H. (1980): “On strategy-proofness and single peakedness,” _Public Choice_ , 35, 437–455.
  * Ortega and Segal-Halevi (2022) Ortega, J. and E. Segal-Halevi (2022): “Obvious manipulations in cake-cutting,” _Social Choice and Welfare_ , 1–20.
  * Psomas and Verma (2022) Psomas, A. and P. Verma (2022): “Fair and efficient allocations without obvious manipulations,” _arXiv preprint arXiv:2206.11143_.
  * Satterthwaite (1975) Satterthwaite, M. A. (1975): “Strategy-proofness and Arrow’s conditions: existence and correspondence theorems for voting procedures and social welfare functions,” _Journal of Economic Theory_ , 10, 187–217.
  * Troyan and Morrill (2020) Troyan, P. and T. Morrill (2020): “Obvious manipulations,” _Journal of Economic Theory_ , 185, 104970.
  * Weymark (2008) Weymark, J. A. (2008): “Strategy-proofness and the tops-only property,” _Journal of Public Economic Theory_ , 10, 7–26.