Two-Valued Strongly Group Strategy-Proof Social Choice Functions

Abstract

We present simple and direct arguments to characterize strongly group strategy-proof social choice functions whose range is of cardinality two. The underlying society is of arbitrary cardinality, and agents can be indifferent among alternatives.

1. Introduction

In this note, we characterize the strong group strategy-proofness of social choice functions in the following framework: The social choice occurs between two alternatives, but it is based on a profile of weak preferences that the agents express over a larger set of alternatives. In other words, despite the fact that we focus on social choice functions with range consisting of two elements, they belong to an arbitrary set of alternatives, in general consisting of more than two elements. Such a setting received a limited attention with respect to the one in which there are only two alternatives on the scene. Related to the latter framework, among others, we mention [1,2,3,4,5]. The higher level of generality we adopt in this paper determines some difficulties that one needs to tackle, mainly because the dependence of irrelevant (i.e., those not in the range) alternatives emerges. Concerning this, see [6] (Example 2.4). However, the difficulties are compensated by the significance of the setting. This significance has been clarified in papers like [6,7,8,9,10], where the same as our framework is adopted. In particular, differently from the authors who assume that only two alternatives are available when the range is of cardinality two, ref. [7] emphasizes that the choice to restrict the range is a possible tool for the mechanism designer, even when more than two choices are socially available in principle. In [8], it is proved that the use of single-dipped preferences leads exactly to social choice functions with the range of cardinality two within a larger set of alternatives. In [6,9], the implementation of a social choice function that asks for preferences on a large set of alternatives rather than only on the two in the range is presented as a tool for balancing between simplicity (only one between two alternatives may form the collective outcome) and, exactly since the irrelevant alternatives count, careful attention to agents’ opinion (by requiring their preferences over all alternatives in order to define a profile of preferences).

The characterization we present (Theorem 3) states that strong group strategy-proofness is equivalent to Paretian property joint with a further property. This is the almost independence of irrelevant alternatives (Definition 5, a property presented in [7] under the name $ab$-based if $\{a,b\}$ is the range of the social choice function), in case of a society consisting of two agents only. Whereas in case the agents are three or more, the property that one has to add to Pareto is the independence from conflict, a property we introduce in Definition 5.

The characterization of two-valued strongly group strategy-proof social choice functions is also one of the tasks of [7]. We point out here that we obtain a characterization different from [7] (Theorem 2). Moreover, whereas the latter leads us to identify the functional form of strongly group strategy-proof social choice functions ([7], Theorem 3¹) through the investigation of several cases and subcases, our characterization Theorem 3 gives [7] (Theorem 3) as an immediate corollary. Finally, we also remark that the arguments we provide do not require the finiteness of the underlying set of agents.

In Section 2, we describe the model and we introduce the notations. Section 3 contains the characterization of strongly group strategy-proof social choice functions. In Section 4, we present a description of the considered functions. Section 5 concludes.

2. The Model

We denote a society by V, whose members are called agents, and we denote a set of alternatives by A. Both sets can be of any cardinality (finite or infinite).

Agents “order” alternatives by means of weak preferences, i.e., complete and transitive binary relations on A.

We denote the set of all weak preferences on the set A of alternatives by $\mathcal{W}$. For simplicity, we only say preference to indicate a weak preference. If p is a preference on A, we write $x{⪰}_{p}y$ for elements x and y of A to mean that the pair $(x,y)$ belongs to the binary relation p. This translates to the statement that according to the preference p, the alternative x is at least as good as the alternative y.

We write $x{\succ }_{p}y$ to mean that the pair $(x,y)$ belongs to the binary relation p, and the pair $(y,x)$ does not. In this case, according to the preference p, the alternative x is better than the alternative y.

Finally, we write $x\sim y$ to mean that both pairs $(x,y)$ and $(y,x)$ belong to p. This means that according to the preference p, the two alternatives are indifferent to each other.

A profile of preferences is a specification of a preference for each agent. Thus, a profile is a function $P:V\to \mathcal{W}$. We write $P={\left(P_v\right)}_{v\in V}$, or, more briefly, $P=\left(P_v\right)$ for a profile.

Definition 1.

A social choice function (scf for brevity) is a map $\varphi :\mathcal{P}\to A$, where $\mathcal{P}\subseteq {\mathcal{W}}^V$.

Nonempty subsets of V are called coalitions. Given a profile P and a coalition D, we write $P_D$ to indicate ${\left(P_v\right)}_{v\in D}$, and we use the notation $P=(P_D,P_{-D})$, where $-D$ denotes the set theoretical complement $V\setminus D$ of D. If the coalition consists of only one agent, say $D=\left\{u\right\}$, we write $P=(P_u,P_{-u})$ for simplicity.

Definition 2.

A coalition D can weakly manipulate a scf $\varphi :\mathcal{P}\to A$ at the profile $P\in \mathcal{P}$ if there exists a profile $Q=(Q_D,P_{-D})\in \mathcal{P}$ such that for every agent v in D, $\varphi \left(Q\right){⪰}_{P_v}\varphi \left(P\right)$, and for at least one agent $v_0$ in D, $\varphi \left(Q\right){\succ }_{P_{v_0}}\varphi \left(P\right)$. In this case, we also say that D can weakly manipulate ϕ at P, declaring Q.

If we want to rule out the possibility that agents coordinate and form a group (a coalition) that can weakly manipulate the outcome of the social choice in the sense described in the previous definition, then we define the notion of strong group strategy-proofness, which is formalized below.

Definition 3.

A scf ϕ is said to be strongly group strategy-proof (sGSP for simplicity) if it cannot be weakly manipulated at any profile by any coalition.

If a scf is sGSP, the grand coalition V, in particular, cannot weakly manipulate it at any profile. This implies a kind of weak Pareto efficiency of the scf. We next give the definition.

Definition 4.

A scf $\varphi :\mathcal{P}\to A$ with range R is said to be Paretian with respect to R (weakly Pareto efficient with respect to R) if, for each profile P, there is no alternative x in the range R such that for every agent v in V, $x{⪰}_{P_v}\varphi \left(P\right)$, and for at least one agent $v_0$ in V, $x{\succ }_{P_{v_0}}\varphi \left(P\right)$.

In the case of onto scfs, this is the standard definition of weak Pareto efficiency.

Proposition 1.

Any sGSP scf is Paretian with respect to its range.

Proof. 

If not, for a sGSP function $\varphi$, consider a profile P and an alternative x that violate Definition 4. The relation $x\in \varphi \left(\mathcal{P}\right)$ ensures that for a certain profile $Q\in \mathcal{P}$, it is $\varphi \left(Q\right)=x$. Hence, coalition V can weakly manipulate $\varphi$ at profile P, declaring Q, which is a contradiction. □

We specify below the assumptions on the scfs we deal with.

• -. (range): the range of the scfs consists of two elements of A. For the rest of the considerations in this paper, we fix that the range is $\{a,b\}\subseteq A$;

• -. (domain): the domain $\mathcal{P}$ of the scfs is of the form $\mathcal{P}={\times }_{v\in V}{\mathcal{W}}_v$, where for each agent v, ${\mathcal{W}}_v$ is a subset of $\mathcal{W}$ that contains at least one preference where a is preferred to b, one preference where b is preferred to a, and one preference where a and b are indifferent to each other².

For a profile $P=\left(P_v\right)$, we write

$\begin{array}{c}D(a,P):=\{v\in V:a{\succ }_{P_v}b\},\hfill \\ D(b,P):=\{v\in V:b{\succ }_{P_v}a\},\hfill \\ I\left(P\right):=\{v\in V:a{\sim }_{P_v}b\}.\hfill \end{array}$

From now on, we simply write Pareto property and Paretian scf without referring to the range, since it is assumed to coincide with the set $\{a,b\}$. For two-valued social choice functions, the property of Pareto can be clearly characterized as follows:

Proposition 2.

If $\varphi :\mathcal{P}\to \{a,b\}$, then ϕ is Paretian if and only if the following two conditions hold true:

(1) $D(a,P)\ne \varnothing =D(b,P)\Rightarrow \varphi \left(P\right)=a,$

(2) $D(b,P)\ne \varnothing =D(a,P)\Rightarrow \varphi \left(P\right)=b.$

We use the notations

$\begin{array}{c}{\mathcal{P}}_0:=\{P\in \mathcal{P}:D(a,P)=\varnothing =D(b,P)\},\hfill \\ {\mathcal{P}}^{\prime }:=\{P\in \mathcal{P}:D(a,P)\ne \varnothing \ne D(b,P)\}.\hfill \end{array}$

For a profile P in ${\mathcal{P}}_0$, $I\left(P\right)=V$. Any such profile is called a profile of unanimous indifference. Of course, unless $A=\{a,b\}$, ${\mathcal{P}}_0$ contains more than one element.

A profile in ${\mathcal{P}}^{\prime }$ expresses a conflict situation in the obvious sense that in the society V at least one agent considers the alternative a better than the alternative b and at least one agent considers b better than a. For this reason, we refer to such profiles as conflict profiles.

3. Characterization of Strongly Group Strategy-Proof Social Choice Functions

From Propositions 1 and 2, it follows that

Proposition 3

([7], Lemma 1). If $\varphi :\mathcal{P}\to \{a,b\}$ is sGSP, then it verifies Properties (1) and (2) of Proposition 2.

Proposition 3 reveals that the values of a sGSP social choice function at two profiles, which are neither of unanimous indifference nor conflict profiles, coincide if they have the same restriction to the set $\{a,b\}$. We now prove that the same is also true for conflict profiles. We could say that on the set $\mathcal{P}\setminus {\mathcal{P}}_0$, a sort of independence of irrelevant alternatives (iia) holds.

Let us introduce a definition that extends that of scfs, which is iia

Definition 5.

A scf ϕ is said to be almost-iia  if

(3)$\left(\begin{array}{c}P,Q\in \mathcal{P}\setminus {\mathcal{P}}_0\hfill \\ D(a,P)=D(a,Q)\hfill \\ D(b,P)=D(b,Q)\hfill \end{array}\right)\Rightarrow \varphi \left(P\right)=\varphi \left(Q\right).$

Note that if the requirement $P,Q\notin {\mathcal{P}}_0$ is omitted, (3) is exactly the independence of irrelevant alternatives.

Proposition 4.

Any sGSP scf is almost-iia.

Proof. 

If one of the two sets $D(a,P)$ or $D(b,P)$ is empty, the thesis follows from Proposition 3. We can then assume both profiles P and Q to be conflict profiles.

Assume by contradiction that $\varphi \left(P\right)\ne \varphi \left(Q\right)$. For example, without any loss of generality, assume $\varphi \left(P\right)=a$ and $\varphi \left(Q\right)=b$. We define two profiles, R and T, as follows:

$R_v=\left\{\begin{array}{cc}{P}_v\hfill & \mathrm{if}v\in D(a,P)\cup D(b,P)\hfill \\ \\ Q_v\hfill & \mathrm{if}v\notin D(a,P)\cup D(b,P)\hfill \end{array}\right.$

$T_v=\left\{\begin{array}{cc}{P}_v\hfill & \mathrm{if}v\in D(a,P)\hfill \\ \\ Q_v\hfill & \mathrm{if}v\notin D(a,P)\hfill \end{array}\right.$

Of course, both profile R and T belong to $\mathcal{P}$.

From $\varphi \left(P\right)=a$, it follows that $\varphi \left(R\right)=a$: if not, coalition $D(b,P)\cup I\left(P\right)$ can weakly manipulate $\varphi$ at profile P, declaring R. Analogously, from $\varphi \left(Q\right)=b$, it follows that $\varphi \left(T\right)=b$: if not, coalition $D(a,Q)$ can weakly manipulate $\varphi$ at profile Q, declaring T. At this point, coalition $D(b,P)$ can weakly manipulate $\varphi$ at profile R, declaring T. This is a contradiction that proves the thesis. □

According to the terminology of [7], Proposition 4 states that any sGSP social choice function with range $\{a,b\}$ is $ab$-based.

We state a consequence of Proposition 4 that will be useful in the sequel.

Remark 1.

Let ϕ be a sGSP scf, let u be an agent, and let P and $P^{\prime }$ be two profiles such that either $u\in D(a,P)\cap D(a,P^{\prime })$ or $u\in D(b,P)\cap D(b,P^{\prime })$. Then, $\varphi \left(P^{\prime }\right)=\varphi \left((P_u,P_{-u}^{\prime })\right)$.

Let us prove that in the case of a society consisting of just two agents, almost-iia, together with the Pareto property, is the same that strong group strategy-proofness.

Theorem 1.

If $\left|V\right|=2$, then a scf $\varphi :\mathcal{P}\to \{a,b\}$ is sGSP if and only if it is Paretian and almost-iia: in other words, if and only if it verifies (1) and (2) and (3).

Proof. 

By Propositions 3 and 4, any sGSP scf verifies (1), (2) and (3). To prove the converse, assume by contradiction that a scf $\varphi$ verifying (1), (2) and (3) can be weakly manipulated at a certain profile P. If $D(a,P)=\varnothing$, then either P is a profile of unanimous indifference or Condition (2) applies. In both cases, no manipulation is possible. The same conclusion holds for the case $D(b,P)=\varnothing$. Hence, P must be a conflict profile. The only possibility is that $P=(P_u,P_v)$, with $a{\succ }_{P_u}b$ and $b{\succ }_{P_v}a$. Assume $\varphi \left(P\right)=a$ (the case $\varphi \left(P\right)=b$ is analogous). The only coalition that can weakly manipulate $\varphi$ at P is then $\left\{v\right\}$. We now verify that there is no profile $Q=(P_u,Q_v)$ such that $\varphi \left(Q\right)=b$; hence, manipulation is impossible. If $a{⪰}_{Q_v}b$, then Condition (1) implies $\varphi \left(Q\right)=a$. On the other hand, if $b{\succ }_{Q_v}a$, then the two profiles P and Q have the same restriction to $\{a,b\}$; hence, the relation $\varphi \left(Q\right)=a$ follows from (3). □

When there are more than two agents in the society, a different condition added to the Pareto property characterizes strategy-proofness of a social choice function: its restriction to the set of conflict profiles has to be constant. We formally introduce the condition.

Definition 6.

A scf $\varphi :\mathcal{P}\to \{a,b\}$ is said to be conflict-independent  if it is constant on the set ${\mathcal{P}}^{\prime }$ of conflict profiles. In other words, this is valid if the following implication holds true:

(4)$P,Q\in {\mathcal{P}}^{\prime }\Rightarrow \varphi \left(P\right)=\varphi \left(Q\right).$

Proposition 5.

If $\left|V\right|>2$, then any sGSP scf is conflict-independent.

Proof. 

Consider a profile $P\in \mathcal{P}$ such that both the sets $D(a,P)$ and $D(b,P)$ are singletons, say $D(a,P)=\left\{u\right\}$ and $D(b,P)=\left\{v\right\}$. Without any loss of generality, assume $\varphi \left(P\right)=a$. Since $\varphi$ is sGSP, necessarily $\varphi \left(P^{\prime }\right)=a$ for each profile $P^{\prime }$ with $u\in D(a,P^{\prime })$. If not, by Remark 1, coalition $V\setminus \left\{u\right\}$ can weakly manipulate $\varphi$ at profile P, declaring $P^{\prime }$.

Consider a profile R having $D(a,R)=\left\{u\right\}$ and $D(b,R)=\left\{w\right\}$, where the agent w is different from v. From the previous observation, we have $\varphi \left(R\right)=a$. The latter relation implies that the value of $\varphi$ is a at each profile $R^{\prime }$, having $D(b,R^{\prime })=\left\{w\right\}$ and $D(a,R^{\prime })=\left\{z\right\}$ (for any $z\ne w$). In fact, if for such a profile $\varphi \left(R^{\prime }\right)=b$, then, by Remark 1, coalition $V\setminus \left\{w\right\}$ could weakly manipulate $\varphi$ at profile $R^{\prime }$, declaring R. Applying to profile $R^{\prime }$, encompassing the same reasoning used for profile P, it follows that $\varphi \left(P\right)=a$ for any profile P, such that for at least one agent $z\ne w$, it is $z\in D(a,P)$.

Since the choice of w was arbitrary in $V\setminus \left\{u\right\}$, the relation $\varphi \left(P\right)=a$ holds for any profile P such that the set $D(a,P)$ is not empty, particularly for any profile in ${\mathcal{P}}^{\prime }$. □

Note that sGSP social choice functions are not necessarily conflict-independent if $\left|V\right|=2$, as the following example shows.

Example 1.

Let $V=\{1,2\}$. The function $\varphi :{\mathcal{W}}^V\to \{a,b\}$ defined by setting

$\varphi \left(P\right)=\left\{\begin{array}{cc}a\hfill & if \left|D\right(a,P\left)\right|>\left|D\right(b,P\left)\right|\hfill \\ \\ b\hfill & if \left|D\right(a,P\left)\right|<\left|D\right(b,P\left)\right|\hfill \\ \\ a\hfill & if \left|D\right(a,P\left)\right|=\left|D\right(b,P\left)\right| and 1\in D(a,P)\hfill \\ \\ b\hfill & if \left|D\right(a,P\left)\right|=\left|D\right(b,P\left)\right| and 1\notin D(a,P)\hfill \end{array}\right.$

is sGSP and it is not conflict-independent³.

Also note that to prove Proposition 5, we used the the minimal assumption on the domain. It was necessary to obtain that the profiles used in the proof belong to the domain $\mathcal{P}$ of the considered function. We cannot avoid that assumption, as the following example proves.

Example 2.

Let $V=\{1,2,3\}$, and for each v in V, let $\mathcal{P}={\times }_{v\in V}{\mathcal{S}}_v$, where ${\mathcal{S}}_v$ consists of all the strict preference relations on A (this means anti-symmetric preferences; in other words, it encompasses preferences according to which two elements indifferent to each other must coincide).

The function $\varphi :\mathcal{P}\to \{a,b\}$ defined by setting

$\varphi \left(P\right)=a\iff \left|D\right(a,P\left)\right|\ge 2$

is a sGSP scf that is not conflict-independent.

We are now ready to characterize strong group strategy-proofness in the case of a society with more than two agents.

Theorem 2.

If $\left|V\right|>2$, then a scf $\varphi :\mathcal{P}\to \{a,b\}$ is sGSP if and only if it is Paretian and conflict-independent, i.e., if and only if it verifies (1), (2) and (4).

Proof. 

Assume by contradiction that a Paretian and conflict-independent scf $\varphi$ can be weakly manipulated by a coalition D at a profile P. Without any loss of generality, we refer to the case $\varphi \left(P\right)=a$. This means that for a certain profile $Q=(Q_D,P_{-D})$, it is $\varphi \left(Q\right)=b$, and for at least one agent $v\in D$, it is $b{\succ }_{P_v}a$. The fact that $D(b,P)$ is nonempty and that $\varphi \left(P\right)=a$, together with Condition (2) of Proposition 2, imply $D(a,P)\ne \varnothing$. Hence, $P\in {\mathcal{P}}^{\prime }$.

The relation $P_u=Q_u\forall u\in D(a,P)$ ensures that $D(a,Q)\ne \varnothing$. At this point, either $D(b,Q)$ is empty, or it contains at least one agent. In the first case, Condition (1) of Proposition 2 implies $\varphi \left(Q\right)=a$. In the second case, it is $Q\in {\mathcal{P}}^{\prime }$. Thus, with $\varphi$ being conflict-independent, it is $\varphi \left(Q\right)=a$. In both cases, we get a contradiction.

The converse implication follows from Propositions 3 and 5. □

We summarize the two previous Theorems 1 and 2 in one statement:

Theorem 3.

Let $\varphi :\mathcal{P}\to \{a,b\}$ be a scf.

If $\left|V\right|=2$, then ϕ is sGSP if and only if it is Paretian and almost-iia.

If $\left|V\right|>2$, then ϕ is sGSP if and only if it is Paretian and conflict-independent.

Note that in both cases, $\left|V\right|=2$ and $\left|V\right|>2$, the values a social choice function attains on the set ${\mathcal{P}}_0$ are not relevant to establish whether the function is sGSP or not.

4. Functional Form of Strongly Group Strategy-Proof Social Choice Functions

We now recall the definition of some social choice functions from [7] and [5] that give an explicit description of sGSP functions.

Definition 7.

A function ϕ is said to be a veto rule for a if it satisfies

$f\left(P\right)=\left\{\begin{array}{cc}b\hfill & if D(b,P)\ne \varnothing \hfill \\ \\ a\hfill & if D(b,P)=\varnothing \ne D(a,P)\hfill \end{array}\right.$

Symmetrically, ϕ is said to be a veto rule for b if it satisfies

$f\left(P\right)=\left\{\begin{array}{cc}a\hfill & if D(a,P)\ne \varnothing \hfill \\ \\ b\hfill & if D(a,P)=\varnothing \ne D(b,P)\hfill \end{array}\right.$

Note that a veto rule can assume any value at a profile of unanimous indifference. So, veto rules on the same alternative may differ only on profiles of unanimous indifference.

It is obvious that any veto rule satisfies (1), (2) and (4). On the other hand, it is easy to check that any function verifying (1) and (2) that attains the same value, say a (resp. b), at all conflict profiles is a veto rule for b (resp. a veto rule for a). These two observations, together with Theorem 2, imply that

Corollary 1.

In the case $\left|V\right|>2$, the veto rules are all and only the sGSP scfs.

To obtain the description of sGSP functions for the case $\left|V\right|=2$, let us introduce a further social choice function.

Definition 8.

Let π be an order (a permutation) on the set V of agents, assumed to be finite. A function ϕ is said to be a serial dictator with order $\pi$ if it satisfies, for any profile $P\in \mathcal{P}\setminus {\mathcal{P}}_0$, the relation

$\varphi \left(P\right)=\left\{\begin{array}{cc}a\hfill & if h\in D(a,P),\hfill \\ \\ b\hfill & if h\in D(b,P),\hfill \end{array}\right.$

where $h:=min\left\{\pi \right(v):v\notin I(P\left)\right\}$.

Note that, as in the case of veto rules, a serial dictator with any order can assume any value at a profile of unanimous indifference.

When $\left|V\right|=2$, serial dictators satisfy (1), (2) and (3). This observation, together with Theorem 1, implies that when the society consists of only two agents, veto rules and serial dictators with any order are sGSP.

Let us verify that, conversely, any sGSP is necessarily of this kind.

When a sGSP social choice function is not a veto rule, it assumes both values on the set of conflict profiles. Since there are only two agents, say $V=\{1,2\}$, conflict profiles are all and only profiles according to which one of the two agents strictly prefers a to b, and the other agent strictly prefers b to a. Given Proposition 4, such a social choice function is constant on each of the sets

${\mathcal{P}}_{12}:=\{P\in \mathcal{P}:D(a,P)=\left\{1\right\} \mathrm{and} D(b,P)=\left\{2\right\}\}$

and

${\mathcal{P}}_{21}:=\{P\in \mathcal{P}:D(a,P)=\left\{2\right\} \mathrm{and} D(b,P)=\left\{1\right\}\}.$

If $\varphi \left({\mathcal{P}}_{12}\right)=\left\{a\right\}$ and $\varphi \left({\mathcal{P}}_{21}\right)=\left\{b\right\}$, the function is a serial dictator with order the identity on V ($\pi \left(1\right)=1$ and $\pi \left(2\right)=2$). If $\varphi \left({\mathcal{P}}_{12}\right)=\left\{b\right\}$ and $\varphi \left({\mathcal{P}}_{21}\right)=\left\{a\right\}$, the function is a serial dictator with the “reversing” order on V ($\pi \left(1\right)=2$ and $\pi \left(2\right)=1$). Hence,

Corollary 2.

In the case $\left|V\right|=2$, the veto rules and the serial dictators are all and only the sGSP scfs.

Corollaries 1 and 2 together give [7] (Theorem 3). In [7], the proof of Theorem 3 consists of a certain number of steps. Among these, Step 2 uses a characterization of weakly group strategy-proof functions. Such a characterization has been proved, making use of the finiteness of V (see [7] (Footnote 9)). Differently from [7], we do not need to assume the set V to be finite.

Before concluding, we make a comparison of our Corollary 1, in the particular case of $\left|A\right|=2$ and $\mathcal{P}={\mathcal{W}}^V$, with a result in [5].

When the set A consists of exactly two alternatives, there is only one profile of unanimous indifference, hence in this case the set ${\mathcal{P}}_0$ collapses into a singleton. The characterization of sGSP social choice functions stated in Theorem 2 says that when there are at least three agents in the society, for a Paretian social choice function to be sGSP it is necessary and sufficient to fix the value, say $x\in \{a,b\}$, it attains at any of the conflict profiles (hence at all of them), and the value, say $y\in \{a,b\}$, it attains at the (unique) profile of unanimous indifference. Any of these two can be either a or b (they may also coincide). These are exactly the consensus rules introduced in [5]. More precisely, consensus rule with disagreement-default x and indifference-default y. Then in this particular case our Theorem 2 gives back the following result

Theorem 4

([5], Theorem 2). For $\left|V\right|>2$, $\left|A\right|=2$ and $\mathcal{P}={\mathcal{W}}^V$, only consensus rules are sGSP.

This means that in this case, the set of consensus rules coincides with the set of veto rules. Let us describe all these functions in detail as follows:

When $\left|A\right|=2$, it is $A=\{a,b\}$, and there are only three preferences on A: a is better than b (we write a), b is better than a (we write b), and a and b are indifferent to each other (we write ∼). Hence,

$\mathcal{W}=\{a,b,\sim \},$

and there is only one profile of unanimous indifference. We denote it by U. Fix any conflict profile, say C. Given Theorem 2, to completely describe a sGSP function, it is sufficient to know its values at U and at C. There are exactly four sGSP functions:

$\begin{array}{cc}\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{f}\mathrm{i}\mathrm{l}\mathrm{e}\mathrm{s}\to & \begin{array}{cc}C& U\end{array}\\ \mathrm{f}\mathrm{u}\mathrm{n}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{s}\downarrow & \\ \begin{array}{c}{\psi }_1\\ {\psi }_2\\ {\psi }_3\\ {\psi }_4\end{array}& \multicolumn{2}{c}{\begin{array}{|cc|}\hline a& a\\ a& b\\ b& a\\ b& b\\ \hline\end{array}}\end{array}$

According to the terminology of [7], we recognize that ${\psi }_1$ and ${\psi }_2$ (resp. ${\psi }_3$ and ${\psi }_4$) are the veto rules for b (resp veto rules for a).

• On the other hand, referring to [5], we observe that, as expected, they are all the consensus rules (CR for brevity). Precisely, they are

${\psi }_1$ CR with disagreement-default a and indifference-default a;

${\psi }_2$ CR with disagreement-default a and indifference-default b;

${\psi }_3$ CR with disagreement-default b and indifference-default a;

${\psi }_4$ CR with disagreement-default b and indifference-default b.

Remark: We recall that a scf is said to be anonymous when no permutation of the agents can effect its values (“all the agents are equal”).

If the set A of alternatives consists of only two elements, then there is only one preference according to which the two alternatives are indifferent, and, of course, only one profile of unanimous indifference. In this case, any veto rule is anonymous, which means that for the case of a set V consisting of at least three agents, any sGSP scf is anonymous.

For the case $\left|A\right|>2$, the situation is different: a sGSP function may attain any value at each profile on unanimous indifference. Hence, even if only the veto rules are sGSP (this happens, as we already observed, only in the case $\left|V\right|>2$), the possibility for such a function to be anonymous depends on the values it attains at the (many) profiles of unanimous indifference.

5. Conclusions

When designing mechanisms that aggregates preferences, one of the main requests is the property of robustness with respect to manipulation (strategy-proofness). The mechanisms we consider in this paper are the two-valued social choice functions, i.e., rules that, based on how the agents in the society order the alternatives, select one of two alternatives. We focused on the problem of characterizing two-valued social choice functions that resist to weak manipulations by coalitions: strong group strategy-proof social choice functions.

We first verify that each strong group strategy-proof social choice function enjoys two properties: a Pareto efficiency with respect to its range and a mild form of independence of irrelevant alternatives. These two properties characterize such functions if there are only two agents in the society. In larger societies, this characterization is no more true, but the functions happen to verify a much more interesting property: they give rise to the same outcome in a very large set of profiles where the conflict between two alternatives appears (they are conflict-independent). This property, together with the Pareto efficiency, allows to characterize strong group strategy-proofness when there are at least three agents.

After characterizing the strong group strategy-proof scfs, both in the two or more than two agents’ cases, we can explicitly describe their form using two well-known aggregation rules: veto rules and serial dictators.

For the very special case of universal domain on a set of exactly two alternatives, if there are at least three agents in the society, the only possible forms of aggregation corresponding to sGSP scfs are the consensus rules.

It is clear from the discussion that even if a scf is two-valued, the presence of more than two alternatives makes a difference. One more aspect where the difference is evident concerns the anonymity of the considered functions: if the set of alternatives contains at least three elements, then some sGSP scfs are anonymous and some others are not, if the set of alternatives contains only two elements and there are more than two agents in the society, then anonymity is a consequence of strong group strategy-proofness.

Author Contributions

Conceptualization, A.D.S. and K.P.S.B.R.; Methodology, A.D.S. and K.P.S.B.R.; Formal analysis, A.D.S. and K.P.S.B.R.; Investigation, A.D.S. and K.P.S.B.R.; Writing—original draft, A.D.S. and K.P.S.B.R.; Writing—review & editing, A.D.S. and K.P.S.B.R. All authors have read and agreed to the published version of the manuscript.

Data Availability Statement

The original contributions presented in the study are included in the article, further inquiries can be directed to the corresponding author.

Conflicts of Interest

The authors declare no conflicts of interest.

Footnotes

Notes

1. Veto rules for the case of three or more agents; veto rules and serial dictators for the case of two agents.

2. In [7], this is called minimal assumption on the domain.

3. Note that this is the serial dictator with order the identity of V, defined later in Definition 8.

Footnotes

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

References

1. Basile, A.; Rao, S.; Bhaskara Rao, K.P.S. Anonymous, non–manipulable, binary social choice. Games Econ. Behav.; 2022; 133, pp. 138-149. [DOI: https://dx.doi.org/10.1016/j.geb.2022.02.007]

2. Basile, A.; Rao, S.; Bhaskara Rao, K.P.S. Geometry of anonymous binary social choices that are strategy-proof. Math. Soc. Sci.; 2022; 116, pp. 85-91. [DOI: https://dx.doi.org/10.1016/j.mathsocsci.2022.01.001]

3. Lahiri, A.; Pramanik, A. On Strategy-proof Social Choice between Two Alternatives. Soc. Choice Welf.; 2020; 54, pp. 581-607. [DOI: https://dx.doi.org/10.1007/s00355-019-01220-7]

4. Larsson, B.; Svensson, L.G. Strategy-proof voting on the full preference domain. Math. Soc. Sci.; 2006; 52, pp. 272-287. [DOI: https://dx.doi.org/10.1016/j.mathsocsci.2006.03.008]

5. Manjunath, V. Group strategy-proofness and voting between two alternatives. Math. Soc. Sci.; 2012; 63, pp. 239-242. [DOI: https://dx.doi.org/10.1016/j.mathsocsci.2012.02.003]

6. Basile, A.; Rao, S.; Bhaskara Rao, K.P.S. The structure of two-valued coalitional strategy-proof social choice functions. J. Math. Econ.; 2021; 95, 102474. [DOI: https://dx.doi.org/10.1016/j.jmateco.2021.102474]

7. Barberà, S.; Berga, D.; Moreno, B. Group strategy-proof social choice functions with binary ranges and arbitrary domains: Characterization results. Int. J. Game Theory; 2012; 41, pp. 791-808. [DOI: https://dx.doi.org/10.1007/s00182-011-0305-7]

8. Barberà, S.; Berga, D.; Moreno, B. Domains, ranges and strategy-proofness: The case of single-dipped preferences. Soc. Choice Welf.; 2012; 39, pp. 335-352. [DOI: https://dx.doi.org/10.1007/s00355-011-0624-4]

9. Basile, A.; Rao, S.; Bhaskara Rao, K.P.S. The character of non-manipulable collective choices between two alternatives. Soc. Choice Welf.; 2024; [DOI: https://dx.doi.org/10.1007/s00355-024-01546-x]

10. Hagiwara, M.; Yamamura, H. Upper set rules with binary ranges. Soc. Choice Welf.; 2020; 54, pp. 657-666. [DOI: https://dx.doi.org/10.1007/s00355-019-01225-2]