Francesca Busetto

Giulio Codognato

Simone Tonin

Integer Programming and Nondictatorial Arrovian Social Welfare Functions

Keywords:

. Our main theorem provides a complete characterization of the domains admitting nondictatorial Arrovian social welfare functions with ties by introducing a notion of strict decomposability.

Introduction

In two pathbreaking papers, [START_REF] Sethuraman | Integer programming and Arrovian social welfare functions[END_REF], ( 2006)) introduced the systematic use of integer programming in the traditional field of social choice theory, initiated by [START_REF] Arrow | Social choice and individual values[END_REF]. As remarked by these specialized literature 2 -are suitable to be used to represent ASWFs "with ties" -that is ASWFs which admit indifference between distinct alternatives in their range. Indeed, we provide a theorem establishing that there exists a one-to-one correspondence between the set of feasible solutions of a ternary IP and the set of ASWFs with ties.

We use our generalized integer programs to systematically study nondictatorial ASWFs. We first show how these tools can be used to obtain a new and simpler proof of Kalai and Muller's Theorem 2 for ASWFs without ties. To this end, we introduce a simpler but equivalent version of the concept of decomposability proposed by these authors. More important, this analysis is the basis for going beyond the already known results on nondictatorial ASWFs.

In fact, Kalai and Muller's Theorem 2 provides a complete characterization both of the domains of antisymmetric preference orderings admitting nondictatorial ASWFs without ties and those admitting dictatorial ASWFs without ties. The problem of characterizing the domains of antisymmetric preference orderings admitting nondictatorial ASWFs with ties has so far been left open. We overcome this problem by using ternary integer programming: in our main theorem, we provide a complete characterization of these domains by introducing the notion of strict decomposability.

This new characterization result raises the question of which is the relationship between decomposable and strictly decomposable domains. We conclude our analysis showing that all strictly decomposable domains are decomposable whereas the converse relation does not hold.

Notation and definitions

Let E be any initial finite subset of the natural numbers with at least two elements and let |E| be the cardinality of E, denoted by n. Elements of E are called agents.

Let E be the collection of all subsets of E. Given a set S ∈ E, let S c = E \ S.

Let A be a set such that |A| ≥ 3. Elements of A are called alternatives. Let A 2 denote the set of all ordered pairs of alternatives. 2 We have to stress that we still apply the basic tools of integer linear programming and that the programs we introduce could be equivalently defined on the set {0, 1, 2}. Nonetheless, here we prefer to follow [START_REF] Sethuraman | Anonymous monotonic social welfare functions[END_REF], and keep using the value Let R be the set of all the complete and transitive binary relations on A, called preference orderings.

Let Σ be the set of all antisymmetric preference orderings.

Let Ω denote a nonempty subset of Σ. An element of Ω is called admissible preference ordering and is denoted by p. We write xpy if x is ranked above y under p.

A pair (x, y) ∈ A 2 is called trivial if there are not p, q ∈ Ω such that xpy and yqx. Let T R denote the set of trivial pairs. We adopt the convention that all pairs (x, x) ∈ A 2 are trivial.

A pair (x, y) ∈ A 2 is nontrivial if it is not trivial. Let N T R denote the set of nontrivial pairs.

Let Ω n denote the n-fold Cartesian product of Ω. An element of Ω n is called a preference profile and is denoted by P = (p 1 , p 2 , . . . , p n ), where p i is the antisymmetric preference ordering of agent i ∈ E.

A Social Welfare Function (SWF) on Ω is a function

f : Ω n → R. f is said to be "without ties" if f (Ω n ) ∩ (R \ Σ) = ∅. f is said to be "with ties" if f (Ω n ) ∩ (R \ Σ) = ∅.
Given P ∈ Ω n , let P (f (P)) and I(f (P)) be binary relations on A. We write xP (f (P))y if, for x, y ∈ A, xf (P)y but not yf (P)x and xI(f (P))y if, for x, y ∈ A, xf (P)y and yf (P)x.

A SWF on Ω, f , satisfies Pareto Optimality (PO) if, for all (x, y) ∈ A 2 and for all P ∈ Ω n , xp i y, for all i ∈ E, implies xP (f (P))y.

A SWF on Ω, f , satisfies Independence of Irrelevant Alternatives (IIA) if, for all (x, y) ∈ N T R and for all P, P ∈ Ω n , xp i y if and only if xp i y, for all i ∈ E, implies, xf (P)y if and only if xf (P )y, and, yf (P)x if and only if yf (P )x.

An Arrovian Social Welfare Function (ASWF) on Ω is a SWF on Ω, f , which satisfies PO and IIA.

An ASWF on Ω, f , is dictatorial if there exists j ∈ E such that, for all (x, y) ∈ N T R and for all P ∈ Ω n , xp j y implies xP (f (P))y. f is nondictatorial if it is not dictatorial.

Given (x, y) ∈ A 2 and S ∈ E, let d S (x, y) denote a variable such that d S (x, y) ∈ {0, 1 2 , 1}. An Integer Program (IP) on Ω consists of a set of linear constraints, related to the preference orderings in Ω, on variables d S (x, y), for all (x, y) ∈ N T R and for all S ∈ E, and of the further conventional constraints that d E (x, y) = 1 and d ∅ (y, x) = 0, for all (x, y) ∈ T R.

Let d denote a feasible solution (henceforth, for simplicity, only "solution") to an IP on Ω. d is said to be a binary solution if variables d S (x, y) reduce to assume values in the set {0, 1}, for all (x, y) ∈ N T R, and for all S ∈ E. It is said to be a "ternary" solution, otherwise.

A solution d is dictatorial if there exists j ∈ E such that d S (x, y) = 1, for all (x, y) ∈ N T R and for all S ∈ E, with j ∈ S. d is nondictatorial if it is not dictatorial.

An ASWF on Ω, f , and a solution to an IP on the same Ω, d, are said to correspond if, for each (x, y) ∈ N T R and for each S ∈ E, xP (f (P))y if and only if d S (x, y) = 1, xI(f (P))y if and only if d S (x, y) = 1 2 , yP (f (P))x if and only if d S (x, y) = 0, for all P ∈ Ω n such that xp i y, for all i ∈ S, and yp i x, for all i ∈ S c .

Finally, consider the following condition of decomposability, introduced by [START_REF] Kalai | Characterization of domains admitting nondictatorial social welfare functions and nonmanipulable voting procedures[END_REF] to characterize the domains of antisymmetric preference orderings admitting nondictatorial ASWFs without ties.

Ω is said to be decomposable (henceforth, KM decomposable) if there exists a set R, with T R R A 2 , satisfying the following conditions. Condition I. For every two pairs (x, y), (x, z) ∈ N T R, if there exist p, q ∈ Ω for which xpypz and yqzqx, then (x, y) ∈ R implies that (x, z) ∈ R.

Condition II. For every two pairs (x, y), (x, z) ∈ N T R, if there exist p, q ∈ Ω for which xpypz and yqzqx, then (z, x) ∈ R implies that (y, x) ∈ R.

Condition III. For every two pairs (x, y), (x, z) ∈ N T R, if there exists p ∈ Ω for which xpypz, then (x, y) ∈ R and (y, z) ∈ R imply that (x, z) ∈ R.

Condition IV. For every two pairs (x, y), (x, z) ∈ N T R, if there exists p ∈ Ω for which xpypz, then (z, x) ∈ R implies that (y, x) ∈ R or (z, y) ∈ R.

3 Binary integer programming and Arrovian social welfare functions without ties: the work of Sethuraman, Teo and Vohra

The first formulation of an IP on Ω was proposed by [START_REF] Sethuraman | Integer programming and Arrovian social welfare functions[END_REF], for the case where d S (x, y) ∈ {0, 1}, for all (x, y) ∈ N T R and for all S ∈ E. This binary IP -which we will call IP0 -consists of the following set of constraints:

d E (x, y) = 1, (i)
for all (x, y) ∈ N T R;

d S (x, y) + d S c (y, x) = 1, (ii)
for all (x, y) ∈ N T R and for all S ∈ E;

d A∪U ∪V (x, y) + d B∪U ∪W (y, z) + d C∪V ∪W (z, x) ≤ 2, (iii)
for all triples of alternatives x, y, z and for all disjoint and possibly empty sets A, B, C, U, V, W ∈ E whose union includes all agents and which satisfy the following conditions (hereafter referred to as Conditions ( * )): By introducing integer programming, [START_REF] Sethuraman | Integer programming and Arrovian social welfare functions[END_REF] were able to provide a new representation of ASWFs with respect to the axiomatic one previously used in the Arrow's tradition. In particular, in the 2003 paper, they showed that there exists a one-to-one correspondence between the set of the solutions to IP0 on Ω and the set of the ASWFs without ties on the same Ω. Moreover, in both their 2003 and 2006 papers, they used IP0 to systematically analyze properties of ASWFs such as neutrality and anonymity. [START_REF] Sethuraman | Integer programming and Arrovian social welfare functions[END_REF] also built up a second binary IP on Ω, for many respects related to Kalai and Muller's work on nondictatorial ASWFs. In this IP -which we will call IP0 -constraint (iii) is replaced by the following set of constraints:

A = ∅
d S (x, y) ≤ d S (x, z), (iv) d S (z, x) ≤ d S (y, x), (v)
for all triples x, y, z such that there exist p, q ∈ Ω satisfying xpypz and yqzqx, and for all S ∈ E;

d S (x, y) + d S (y, z) ≤ 1 + d S (x, z), (vi) d S (z, y) + d S (y, x) ≥ d S (z, x), (vii)
for all triples x, y, z such that there exists p ∈ Ω satisfying xpypz, and for all S ∈ E. Constraints (iv) and (v) translate, in terms of variables d S (x, y), Kalai and Muller's Conditions I and II. In their Claim 1, Sethuraman et al. (2003) showed that these constraints are special cases of (iii). Constraints (vi) and (vii) translate Kalai and Muller's Conditions III and IV. In their Claim 2, Sethuraman et al. (2003) showed that also these constraints are special cases of (iii). Their analysis established that any solution d to IP0 on Ω is a solution to IP0 on the same domain and that IP0 and IP0 are equivalent in the case where n = 2.

In the remainder of this section, we will prove that the set of constraints (iv)-(vii) exhibits problems of logical dependence. More precisely, the following proposition shows that one of the constraints (iv) and (v) is redundant.

Proposition 1. d satisfies (i), (ii), and (iv) if and only if it satisfies (i), (ii), and (v).

Proof. Suppose that d satisfies (i), (ii), and (iv). Consider a triple x, y, z. Suppose that there exist p, q ∈ Ω satisfying xpypz and yqzqx, and that

d S (z, x) > d S (y, x), for some S ∈ E. Then, d S (z, x) = 1, d S (y, x) = 0. But then, d S c (x, z) = 0, d S c (x, y) = 1. This implies that d S c (x, y) > d S c (x, z),
contradicting (iv). Therefore, d satisfies (i), (ii), and (v). Suppose that d satisfies (i), (ii), and (v). Consider a triple x, y, z. Suppose that there exist p, q ∈ Ω satisfying xpypz and yqzqx, and that

d S (x, y) > d S (x, z), for some S ∈ E. Then, d S (x, y) = 1, d S (x, z) = 0. But then, d S c (y, x) = 0, d S c (z, x) = 1. This implies that d S c (z, x) > d S c (y, x),
contradicting (v). Therefore, d satisfies (i), (ii), and (iv).

Moreover, the following proposition shows that one of the constraints (vi) and (vii) is redundant.

Proposition 2. d satisfies (i), (ii), and (vi) if and only if it satisfies (i), (ii), and (vii).

Proof. Suppose that d satisfies (i), (ii), and (vi). Consider a triple x, y, z. Suppose that there exists p ∈ Ω satisfying xpypz, and that

d S (z, y) + d S (y, x) < d S (z, x), for some S ∈ E. Thus, d S (z, y) = 0, d S (y, x) = 0, and d S (z, x) = 1. But then, d S c (y, z) = 1, d S c (x, y) = 1, and d S c (x, z) = 0. This implies that d S c (x, y) + d S c (y, z) > 1 + d S c (x, z),
contradicting (vi). Therefore, d satisfies (i), (ii), and (vii). Suppose that d satisfies (i), (ii), and (vii). Consider a triple x, y, z. Suppose that there exists p ∈ Ω satisfying xpypz, and that

d S (x, y) + d S (y, z) > 1 + d S (x, z), for some S ∈ E. Then, d S (x, y) = 1, d S (y, z) = 1, and d S (x, z) = 0. But then, d S c (y, x) = 0, d S c (z, y) = 0, and d S c (z, x) = 1. This implies that d S c (z, y) + d S c (y, x) < d S c (z, x),
contradicting (vii). Therefore, d satisfies (i), (ii), and (vi).

We will use Propositions 1 and 2 in the next section. There, we will provide a natural generalization of Sethuraman et al.'s approach, specifying two integer programs in which variables d S (x, y) are allowed to assume values in the set {0, 1 2 , 1}.

4 Ternary integer programming and Arrovian social welfare functions with ties: a correspondence theorem

In this section, we first introduce a generalization of Sethuraman et al.'s IP0 to the case where d S (x, y) = 1 2 , for some (x, y) ∈ N T R and for some S ∈ E. We will show that this ternary program on Ω -which we will call IP1 -can be used to represent ASWFs with ties. IP1 consists of the following set of constraints:

d E (x, y) = 1, (1)
for all (x, y) ∈ N T R;

d S (x, y) + d S c (y, x) = 1, (2)
for all (x, y) ∈ N T R and for all S ∈ E;

d A∪U ∪V (x, y) + d B∪U ∪W (y, z) + d C∪V ∪W (z, x) ≤ 2, ( 3
) if d A∪U ∪V (x, y), d B∪U ∪W (y, z), d C∪V ∪W (z, x) ∈ {0, 1}; d A∪U ∪V (x, y) + d B∪U ∪W (y, z) + d C∪V ∪W (z, x) = 3 2 , ( 4
) if d A∪U ∪V (x, y) = 1 2 or d B∪U ∪W (y, z) = 1 2 or d C∪V ∪W (z, x) = 1 2
, for all triples of alternatives x, y, z and for all disjoint and possibly empty sets A, B, C, U, V, W ∈ E whose union includes all agents and which satisfy Conditions ( * ).

In fact, we propose now a result which establishes a one-to-one correspondence between the set of the solutions to IP1 on a given Ω and the set of the ASWFs with ties on the same Ω.

Theorem 1. Consider a domain Ω. Given an ASWF on Ω, f , there exists a unique solution to IP1 on Ω, d, which corresponds to f . Given a solution to IP1 on Ω, d, there exists a unique ASWF on Ω, f , which corresponds to d.

Proof. Consider a domain Ω and an ASWF on Ω, f . Determine d as follows. Given (x, y) ∈ N T R and S ∈ E, consider P ∈ Ω n such that xp i y, for all i ∈ S, and yp i x, for all i ∈ S c . Let

d S (x, y) = 1 if xP (f (P))y, d S (x, y) = 1 2 if xI(f (P))y, d S (x, y) = 0 if yP (f (P))x.
Then, for each (x, y) ∈ N T R and for each S ∈ E, we have xP (f (P))y if and only if d S (x, y) = 1, xI(f (P))y if and only if d S (x, y) = 1 2 , yP (f (P))x if and only if d S (x, y) = 0, for all P ∈ Ω n such that xp i y, for all i ∈ S, and yp i x, for all i ∈ S c , as f satisfies IIA. d satisfies (1), as f (P) satisfies PO, and (2), as f (P) is a complete binary relation on A, for all P ∈ Ω n . Consider a triple x, y, z, and disjoint and possibly empty sets A, B, C, U, V, W ∈ E whose union includes all agents and which satisfy Conditions ( * ). Moreover, consider P ∈ Ω n . Then, by Conditions ( * ), we have:

xp i y, for all i ∈ A ∪ U ∪ V ; yp i x, for all i ∈ (A ∪ U ∪ V ) c ; yp i z, for all i ∈ B ∪ U ∪ W ; zp i y, for all i ∈ (B ∪ U ∪ W ) c ; zp i x, for all i ∈ C ∪ V ∪ W ; xp i z, for all i ∈ (C ∪ V ∪ W ) c . Suppose that d A∪U ∪V (x, y), d B∪U ∪W (y, z), d C∪V ∪W (z, x) ∈ {0, 1} and d A∪U ∪V (x, y) + d B∪U ∪W (y, z) + d C∪V ∪W (z, x) > 2.
Then, we have xP (f (P))yP (f (P))z and zP (f (P))x, a contradiction. Suppose that d A∪U ∪V (x, y) = 1 2 and

d A∪U ∪V (x, y) + d B∪U ∪W (y, z) + d C∪V ∪W (z, x) < 3 2 .
Consider the following three cases.

d A∪U ∪V (x, y) + d B∪U ∪W (y, z) + d C∪V ∪W (z, x) > 3 2 .
Consider the following three cases. First, d B∪U ∪W (y, z) = 1 and d C∪V ∪W (z, x) = 1. Then, we have xI(f (P))yP (f (P))z and zP (f (P))x, a contradiction. Second, d B∪U ∪W (y, z) = 1 2 and d C∪V ∪W (z, x) = 1. Then, we have xI(f (P))yI(f (P))z and zP (f (P))x, a contradiction. Third,

d B∪U ∪W (y, z) = 1 and d C∪V ∪W (z, x) = 1 2
. Then, we have xI(f (P))yP (f (P))z and zI(f (P))x, a contradiction. Therefore, d satisfies (3) and (4). Hence, d is a solution to IP1 on Ω which corresponds to f . Suppose that d is not unique. Then, there exist a solution to IP1 on Ω, d , (x, y) ∈ N T R, and S ∈ E such that d S (x, y) = d S (x, y). Consider P ∈ Ω n such that xp i y, for all i ∈ S, and yp i x, for all i ∈ S c . Then, we have xP (f (P))y and xI(f (P))y, or, yP (f (P))x and xI(f (P))y, or, xP (f (P))y and yP (f (P))x, a contradiction. But then, d is unique. Now, consider a solution to IP1 on Ω, d. Determine f as follows. Given (x, y) ∈ T R, let xP (f (P))y, for all P ∈ Ω n . Given (x, y) ∈ N T R and P ∈ Ω n , let S ∈ E be the set of agents such that xp i y, for all i ∈ S, and

yp i x, for all i ∈ S c . Let xP (f (P))y if d S (x, y) = 1, xI(f (P))y if d S (x, y) = 1
2 , and yP (f (P))x if d S (x, y) = 0. f (P) is a complete binary relation on A, for all P ∈ Ω n , by construction and by [START_REF] Kalai | Characterization of domains admitting nondictatorial social welfare functions and nonmanipulable voting procedures[END_REF]. Now, we show that f (P) is also a transitive binary relation on A, for all P ∈ Ω n . Consider a triple x, y, z and a preference profile P ∈ Ω n . Then, there exist three nonempty sets , and yP (f (P))x if and only if d S (x, y) = 0, for all P ∈ Ω n such that xp i y, for all i ∈ S, and yp i x, for all i ∈ S c . Hence, f is an ASWF on Ω, which corresponds to d. Suppose that f is not unique. Then, there exist an ASWF on Ω, f , (x, y) ∈ N T R and P ∈ Ω n such that we have xf (P)y but not xf (P)y. Let S ∈ E be the set such that xp i y, for all i ∈ S, and yp i x, for all i ∈ S c . Then, d S (x, y) = 1 and d S (x, y) = 0, or, d S (x, y) = 1 2 and d S (x, y) = 0, a contradiction. But then, f is unique.

H, I, J such that xp i y, for all i ∈ H, yp i x, for all i ∈ H c , yp i z, for all i ∈ I, zp i y, for all i ∈ I c , zp i x, for all i ∈ J, xp i z, for all i ∈ J c . Let A = H \ (I ∪ J), B = I \ (H ∪ J), C = J \ (H ∪ I), U = H ∩ I, V = H ∩ J, W = I ∩ J. Then, A, B, C, U, V, W ∈ E are disjoint
d A∪U ∪V (x, y) + d B∪U ∪W (y, z) + d C∪V ∪W (z, x) > 3 2 , contradicting (4)
d A∪U ∪V (x, y) + d B∪U ∪W (y, z) + d C∪V ∪W (z, x) > 3 2 , contradicting (4)
d A∪U ∪V (x, y) + d B∪U ∪W (y, z) + d C∪V ∪W (z, x) < 3 2 , contradicting (4)
We introduce now a second ternary IP on Ω, which incorporates -like Sethuraman et al.'s IP0 -a reformulation of Kalai and Muller's Conditions I-IV. In constructing it, we draw the consequences of Propositions 1 and 2 and eliminate the redundancies inherent in Sethuraman et al.'s IP0 . In fact, this second ternary IP -which we will call IP1 -consists of constraints ( 1), (2), and the following four logically independent constraints:

d S (x, y) ≤ d S (x, z), ( 5
) if d S (x, y) ∈ {0, 1}; d S (x, y) < d S (x, z), ( 6
) if d s (x, y) = 1 2
, for all triples x, y, z such that there exist p, q ∈ Ω satisfying xpypz and yqzqx, and for all S ∈ E;

d S (x, y) + d S (y, z) ≤ 1 + d S (x, z), ( 7
) if d s (x, y), d s (y, z) ∈ {0, 1}; d S (x, y) + d S (y, z) = 1 2 + d S (x, z), ( 8
) if d S (x, y) = 1 2 or d S (y, z) = 1 2
, for all triples x, y, z such that there exist p, q ∈ Ω satisfying xpypz and zqyqx, and for all S ∈ E. 3In the remainder of this section, we prove two propositions which establish the relationships between IP1 and IP1 . Proposition 3. If d is a solution to IP1 on Ω, then it is a solution to IP1 on the same Ω.

Proof. Let d be a solution to IP1 on Ω. Consider a triple x, y, z and S ∈ E. Suppose that there exist p, q ∈ Ω which satisfy xpypz and yqzqx. Let U = S, W = S c , and A = B = C = V = ∅. Then, A, B, C, U, V, W are sets whose union includes all agents and which satisfy Conditions ( * ). Suppose that d S (x, y) ∈ {0, 1} and d S (x, y) > d S (x, z). Consider the following two cases. First, d S (x, z) ∈ {0, 1}. Then,

d U (x, y) + d U ∪W (y, z) + d W (z, x) > 2, contradicting (3). Second, d S (x, z) = 1 2 . Then, d U (x, y) + d U ∪W (y, z) + d W (z, x) > 3 2 , contradicting (4)
. Therefore, d satisfies [START_REF] Sethuraman | Anonymous monotonic social welfare functions[END_REF]. Suppose now that d S (x, y) = 1 2 and d S (x, y) ≥ d S (x, z). Then,

d U (x, y) + d U ∪W (y, z) + d W (z, x) > 3 2 , contradicting (4)
d U (x, y) + d U (y, z) + d C (z, x) > 2, contradicting (3)
. Second, d S (x, z) = 1 2 . Then,

d U (x, y) + d U (y, z) + d C (z, x) > 3 2 , contradicting (4)
d A∪U ∪V (x, y) + d B∪U ∪W (y, z) + d C∪V ∪W (z, x) > 2.
Consider the case where A = ∅ and W = ∅. Then, there exist p, q ∈ Ω satisfying xpzpy and yqzqx. Suppose that A = {1} and W = {2}. Then,

d {2} (y, z) + d {2} (z, x) > 1 + d {2} (y, x),
contradicting (7). The cases where B = ∅, V = ∅, and C = ∅, U = ∅ lead, mutatis mutandis, to the same contradiction. Consider the case where U = ∅ and V = ∅. Then, there exist p, q ∈ Ω satisfying xpypz and zqxqy. Suppose that U = {1} and V = {2}. Then,

d {2} (z, x) > d {2} (z, y),
contradicting [START_REF] Sethuraman | Anonymous monotonic social welfare functions[END_REF]. The cases where V = ∅, W = ∅, and U = ∅, W = ∅, lead, mutatis mutandis, to the same contradiction. Therefore, d satisfies (3). Suppose that d A∪U ∪V (x, y) = 1 2 and

d A∪U ∪V (x, y) + d B∪U ∪W (y, z) + d C∪V ∪W (z, x) < 3 2 .
Consider the case where A = ∅ and B = ∅. Then, there exist p, q ∈ Ω satisfying xpzpy and yqxqz. Suppose that A = {1} and B = {2}. Then,

d {2} (y, x) = 1 2 and d {2} (y, x) ≥ d {2} (y, z),
contradicting (6). The case where A = ∅ and C = ∅ leads, mutatis mutandis, to the same contradiction. Consider the case where A = ∅ and W = ∅. Then, there exist p, q ∈ Ω satisfying xpzpy and yqzqx. Suppose that A = {1} and W = {2}. Suppose that d {2} (y, z) = 0 and d {2} (z, x) = 0. Then,

d {1} (x, z) + d {1} (z, y) > 1 + d {1} (x, y), contradicting (7). Suppose that d {2} (y, z) = 1 2 and d {2} (z, x) = 0. Then, d {2} (y, z) + d {2} (z, x) < 1 2 + d {2} (y, x),
contradicting (8). Consider the case where U = ∅ and C = ∅. Then, there exist p, q ∈ Ω satisfying xpypz and zqyqx. Suppose that U = {1} and C = {2}. Then, d {1} (x, y) = 1 2 and

d {1} (x, y) + d {1} (y, z) < 1 2 + d {1} (x, z),
contradicting (8). The case where V = ∅ and B = ∅ leads, mutatis mutandis, to the same contradiction. Suppose that d A∪U ∪V (x, y) = 1 2 and

d A∪U ∪V (x, y) + d B∪U ∪W (y, z) + d C∪V ∪W (z, x) > 3 2 .
Consider the case where A = ∅ and W = ∅. Then, there exist p, q ∈ Ω satisfying xpzpy and yqzqx. Suppose that A = {1} and W = {2}. Suppose that d {2} (y, z) = 1 and d {2} (z, x) = 1. Then,

d {2} (y, z) + d {2} (z, x) > 1 + d {2} (y, x), contradicting (7). Suppose that d {2} (y, z) = 1 2 and d {2} (z, x) = 1. Then, d {2} (y, z) + d {2} (z, x) > 1 2 + d {2} (y, x),
contradicting (8). Consider the case where U = ∅ and C = ∅. Then, there exist p, q ∈ Ω satisfying xpypz and zqyqx. Suppose that U = {1} and In this section and the next, we use the integer programs developed above to deal with the issues concerning the dictatorship property of ASWFs. To begin with, we focus here on ASWFs without ties. [START_REF] Kalai | Characterization of domains admitting nondictatorial social welfare functions and nonmanipulable voting procedures[END_REF] were the first who provided a complete characterization of the domains of antisymmetric preference orderings which admit nondictatorial ASWFs without ties. They did this by means of two theorems. In their Theorem 1, they showed that, for a given domain Ω, there exists a nondictatorial ASWF without ties for n > 2 if and only if, for the same Ω, there exists a nondictatorial ASWF without ties for n = 2. In their Theorem 2, Kalai and Muller showed that there exists a nondictatorial ASWF without ties on Ω for n ≥ 2 if and only if Ω satisfies the conditions of KM decomposability introduced in Section 2.

C = {2}. Then, d {1} (x, y) = 1 2 and d {1} (x, y) + d {1} (y, z) > 1 2 + d {1} (x, z), contradicting (
Sethuraman et al. opened the way to an analysis of the problem of dictatorship in terms of integer programming. More precisely, in the 2003 paper, they showed a result establishing a be-univocal relation between the solutions of IP0 for n = 2 and its solutions for n > 2. Since their arguments can straightforwardly be re-expressed in terms of IP1, their result can be stated as follows.

Theorem 2. There exists a nondictatorial binary solution to IP1 on Ω, d, for n = 2, if and only if there exists a nondictatorial binary solution to IP1 on Ω, d * , for n > 2.

Kalai and Muller's Theorem 1 can therefore be obtained, by our Theorem 1, as a corollary of Theorem 2.

Corollary 1. There exists a nondictatorial ASWF without ties on Ω, f , for n = 2, if and only if there exists a nondictatorial ASWF without ties on Ω, f * , for n > 2. Now, we go forward along the line opened by [START_REF] Sethuraman | Integer programming and Arrovian social welfare functions[END_REF], providing a characterization of domains admitting nondictatorial binary solutions to IP1. As it will be made clear shortly, this result is the heart of the new, simpler proof of Kalai and Muller's Theorem 2 for ASWFs without ties, in terms of integer programming.

In order to obtain our characterization theorem, we need to introduce a reformulation of Kalai and Muller's concept of decomposability suitable to be applied within the analytical context of IP1. We will show below that this reformulation is equivalent to the original version proposed by Kalai and Muller. Our reformulation is based on the existence of two sets, R 1 , R 2 ∈ A 2 -instead of only one -which satisfy the two conditions we are going to introduce.

Consider a set R ⊂ A 2 . Consider the following conditions on R.

Condition 1. For all triples x, y, z, if there exist p, q ∈ Ω satisfying xpypz and yqzqx, then (x, y) ∈ R implies that (x, z) ∈ R.

Condition 2. For all triples x, y, z, if there exist p, q ∈ Ω satisfying xpypz and zqyqx, then (x, y) ∈ R and (y, z) ∈ R imply that (x, z) ∈ R.

A domain Ω is said to be decomposable if and only if there exist two sets R 1 and R 2 , with ∅ R i N T R, i = 1, 2, such that, for all (x, y) ∈ N T R, we have (x, y) ∈ R 1 if and only if (y, x) / ∈ R 2 ; moreover, R i , i = 1, 2, satisfies Conditions 1 and 2.

With regard to this definition of a decomposable domain, let us notice the main differences with Kalai and Muller's original notion, introduced to make it compatible with the integer programming analytical setting: Conditions 1 and 2 differ from Conditions I and II as the former refer to triples, rather than pairs, of alternatives. Moreover, Condition 2 is reformulated in terms of a pair of preference orderings -instead of only one -consistently with our formulation of constraints ( 7) and (8). Also, our formulation does not require that R 1 and R 2 contain T R, whereas Kalai and Muller's one requires that R contains T R. In particular, let us stress that our definition requires that R 1 and R 2 satisfy only two conditions -instead of four, as in Kalai and Muller's version. As Corollary 3 below makes it clear, this implies a redundancy of Kalai and Muller's Conditions II and IV, which parallels the redundancy of constraints (v) and (vii) proved in Propositions 2 and 3.

On the basis of our reformulation of the concept of decomposability, we state and prove now the characterization theorem. Theorem 3. There exists a nondictatorial binary solution to IP1 on Ω, d, for n = 2, if and only if Ω is decomposable.

Proof. Let d be a nondictatorial binary solution to IP1 on Ω, for n

= 2. Let R 1 = {(x, y) ∈ N T R : d {1} (x, y) = 1} and R 2 = {(x, y) ∈ N T R : d {2} (x, y) = 1}. Then, for all (x, y) ∈ N T R, (x, y) ∈ R 1 if and only if (y, x) / ∈ R 2 , as d satisfies (2). Moreover, ∅ R i N T R, i = 1, 2
, as d is nondictatorial. Consider a triple x, y, z and suppose that there exist p, q ∈ Ω satisfying xpypz and yqzqx. Moreover, suppose that (x, y) ∈ R 1 and (x, z) / ∈ R 1 Then, d {1} (x, y) = 1 and

d {1} (x, y) > d {1} (x, z), contradicting (5)
. Hence, R i , i = 1, 2, satisfies Condition 1. Consider a triple x, y, z and suppose that there exist p, q ∈ Ω satisfying xpypz and zqyqx. Moreover, suppose that (x, y), (y, z) ∈ R 1 , and (x, z) / ∈ R 1 . Then, d {1} (x, y) = 1, d {1} (y, z) = 1, and

d {1} (x, y) + d {1} (y, z) > 1 + d {1} (x, z), contradicting (7)
. Hence, R i , i = 1, 2, satisfies Condition 2. We have proved that Ω is decomposable. Conversely, suppose that Ω is decomposable. Then, there exist two sets R 1 and R 2 , with ∅ R i N T R, i = 1, 2, such that, for all (x, y) ∈ N T R, we have (x, y) ∈ R 1 if and only if (y, x) / ∈ R 2 ; moreover, R i , i = 1, 2, satisfies Conditions 1 and 2. Determine d as follows. For each (x, y) ∈ N T R, let d ∅ (x, y) = 0, d E (x, y) = 1; moreover, let d {i} (x, y) = 1 if and only if (x, y) ∈ R i ; d {i} (x, y) = 0 if and only if (x, y) / ∈ R i , for i = 1, 2. Then, d satisfies (1) and (2) as, for all (x, y) ∈ N T R, we have (x, y) ∈ R 1 if and only if (y, x) / ∈ R 2 . Consider a triple x, y, z and suppose that there exist p, q ∈ Ω satisfying xpypz and yqzqx. Moreover, suppose that

d {1} (x, y) > d {1} (x, z).
Then, we have (x, y) ∈ R 1 and (x, z) / ∈ R 1 , contradicting Condition 1. Therefore, d satisfies [START_REF] Sethuraman | Anonymous monotonic social welfare functions[END_REF]. Consider a triple x, y, z and suppose that there exist p, q ∈ Ω satisfying xpypz and zqyqx. Moreover, suppose that

d {1} (x, y) + d {1} (y, z) > 1 + d {1} (x, z).
Then, we have (x, y), (y, z) ∈ R 1 and (x, z) / ∈ R 1 , contradicting Condition 2. Therefore, d satisfies (7). d is nondictatorial as ∅ R i N T R, i = 1, 2. Hence, d is a nondictatorial binary solution to IP1 on Ω.

The previous result provides a simplified proof of Kalai and Muller's Theorem 2 since this theorem can be immediately obtained as a corollary of Theorem 3.

Corollary 2. There exists a nondictatorial ASWF without ties on Ω, f , for n ≥ 2, if and only if Ω is decomposable.

Proof. It is a straightforward consequence of Propositions 3 and 4, Theorems 1 and 3, and Corollary 1.

From Theorem 3, we obtain a further corollary, which -as anticipated above -establishes the equivalence between our notion of decomposability and Kalai and Muller's notion, and implies that Kalai 6 Integer programming and nondictatorial Arrovian social welfare functions with ties: a new characterization theorem

In the analysis developed above, the integer programming setup -in particular the IP1 introduced in Section 4 -has proved to be an effective tool in order to provide simplified demonstrations of Kalai and Muller's crucial results on ASWFs without ties.

In this section, we further exploit IP1 to progress in the investigation of nondictatorship. As already reminded, Arrow's impossibility theorem is established for ASWFs admitting ties in their range and defined on the unrestricted domain of preference orderings. Kalai and Muller's characterization theorem overcomes Arrow's impossibility result by considering ASWFs without ties in their range, defined on the domain of antisymmetric preference orderings.

We take a step forward along this way: our main theorem establishes a characterization of the domains of antisymmetric preference orderings admitting nondictatorial ASWFs with ties.

We start our analysis by proving the following result, which extends Theorem 2 above to the case of ternary solutions to IP1. In order to obtain our characterization theorem for ASWFs with ties, we need to introduce a new notion of decomposability, stricter than the one introduced in Section 5 (which was shown to be equivalent to the notion of KM decomposability). We define it as "strict decomposability." The next section will be devoted to establish the exact relationship between the two notions of decomposability and strict decomposability.

(u, v) ∈ N T R and S ∈ E such that d * S (u, v) = 1 2 . Given (x, y) ∈ N T R, let d {1,2} (x, y) = 1, d ∅ (x, y) = 0, d {1} (x, y) = d * S (x, y), d {2} (y, x) = d * Sc (y, x).
Then, consider a set R ⊂ A 2 . Consider the following conditions on R.

The relationship between decomposable and strictly decomposable domains

In this section, we analyze the relationship between the notions of decomposable and strictly decomposable domain. The following example illustrates the two notions. xq -1 y. Then, it is immediate to verify that d = d is a binary solution to IP1 on Ω, for n = 2, and that agent 1 is not a dictator for d . Suppose that agent 2 is a dictator for d . Consider (x, y) ∈ N T R such that d {1} (x, y) = d {2} (y, x) = 1 2 . Suppose that yqx. This implies that d {1} (x, y) = 0 and agent 1 is not a dictator for d , a contradiction. But then, we must have that xqy. Consider variables d {1} (y, x) and d {2} (x, y). Suppose that d {1} (y, x) = 1 and d {2} (x, y) = 0. Then, agent 2 is not a dictator for d , a contradiction. Suppose that d {1} (y, x) = 0 and d {2} (x, y) = 1. Then, agent 1 is not a dictator for d . This implies that d {1} (y, x) = d {2} (x, y) = 1 2 and this, in turn, implies that d {2} (x, y) = 0 and agent 2 is not a dictator of d , a contradiction. Then, d = d is a nondictatorial binary solution to IP1 on Ω, for n = 2.

Again, we straightforwardly obtain a correspondent result for nondictatorial ASWFs as a corollary of Theorem 6. A first proof of this result is due to [START_REF] Maskin | Fonctions de préférence collective définies sur des domaines de préférence individuelle soumis à des constraintes[END_REF]. Corollary 6. If there exists a nondictatorial ASWF with ties on Ω, f , for n ≥ 2, then there exists a nondictatorial ASWF without ties on Ω, f , for n ≥ 2.

Proof. It is an immediate consequence of Propositions 3 and 4, and of Theorems 1, 2, 4, and 6. 4On the basis of the previous results, the following theorem can be immediately proved.

Theorem 7. If a domain Ω is strictly decomposable, then it is decomposable.

Proof. Let Ω be a strictly decomposable domain. Then, by Theorem 5, there exists a nondictatorial ternary solution to IP1 on Ω, d, for n = 2. But then, by Theorem 6, there exists a nondictatorial binary solution to IP1 on Ω, d, for n = 2. Hence, by Theorem 3, Ω is decomposable.

The following example shows that the converse of Theorem 7 does not hold.

Example 2. Let A = {a, b, c, d} and Ω = {p ∈ Σ : apbpcpd, cpapdpb, dpcpbpa, bpdpapc}. Then, Ω is decomposable but it is not strictly decomposable.

1 2

 1 in order to incorporate indifference between social alternatives into the analysis.

  First, d B∪U ∪W (y, z) = 0 and d C∪V ∪W (z, x) = 0. Then, we have zP (f (P))yI(f (P))x and xP (f (P))z, a contradiction. Second, d B∪U ∪W (y, z) = 1 2 and d C∪V ∪W (z, x) = 0. Then, we have xI(f (P))yI(f (P))z and xP (f (P))z, a contradiction. Third, d B∪U ∪W (y, z) = 0 and d C∪V ∪W (z, x) = 1 2 . Then, we have zI(f (P))xI(f (P))y and zP (f (P))y, a contradiction. Suppose now that d A∪U ∪V (x, y) = 1 2 and

  sets of agents whose union includes all agents and which satisfy Conditions ( * ). Moreover, they satisfyA ∪ U ∪ V = H, B ∪ U ∪ W = I, C ∪ V ∪ W = J.Consider the following eight cases. First, xP (f (P))yP (f (P))z and zP (f (P))x. Then, d A∪U ∪V (x, y) = 1, d B∪U ∪W (y, z) = 1, d C∪V ∪W (z, x) = 1, and d A∪U ∪V (x, y) + d B∪U ∪W (y, z) + d C∪V ∪W (z, x) > 2, contradicting (3). Second, xP (f (P))yP (f (P))z and xI(f (P))z. Then, d C∪V ∪W (z, x) = and

2 , 2 ,

 22 . Fifth, xP (f (P))yI(f (P))z and zP (f (P))x. Then, d B∪U ∪W (y, z) = and d A∪U ∪V (x, y) + d B∪U ∪W (y, z) + d C∪V ∪W (z, x) > 3 contradicting (4). Sixth, xP (f (P))yI(f (P))z and xI(f (P))z. Then, d B∪U ∪W (y, z) = and d A∪U ∪V (x, y) + d B∪U ∪W (y, z) + d C∪V ∪W (z, x) > 3 contradicting (4). Seventh, xI(f (P))yI(f (P))z and xP (f (P))z. Then, d A∪U ∪V (x, y) = 1 2 and

  . Therefore, d satisfies (6). Consider a triple x, y, z and S ∈ E. Suppose that there exist p, q ∈ Ω satisfying xpypz and zqyqx. Let C = S c , U = S, and A = B = V = W = ∅. Then, A, B, C, U, V, W are sets whose union includes all agents and which satisfy Conditions ( * ). Suppose that d S (x, y), d S (y, z) ∈ {0, 1} and d S (x, y)+d S (y, z) > 1+d S (x, z). Consider the following two cases. First, d S (x, z) ∈ {0, 1}. Then,

  8). The case where V = ∅ and B = ∅ leads, mutatis mutandis, to the same contradiction. Consider the case where U = ∅ and W = ∅. Then, there exist p, q ∈ Ω satisfying xpypz and yqzqx. Suppose that U = {1} and W = {2}. Then, d {1} (x, y) =1 2 andd {1} (x, y) ≥ d {1} (x, z),contradicting (6). The case where V = ∅ and W = ∅ leads, mutatis mutandis, to the same contradiction. Therefore, d satisfies (4). Hence, d is a solution to IP1 on Ω. 5 Integer programming and nondictatorial Arrovian social welfare functions without ties: a new proof of Kalai and Muller's Theorem 2

Example 1 .

 1 Let A = {a, b, c, d} and Ω = {p ∈ Σ : apbpcpd, cpdpapb, dpcpbpa}. Then, Ω is decomposable and strictly decomposable.Proof. Let us notice that N T R = A 2 . The triples x, y, z for which there exist p, q ∈ Ω such that xpypz and yqzqx are c,a,b; d,a,b; a,c,d; b,c,d. The triples x, y, z for which there exist p, q ∈ Ω such that xpypz and zqyqx are a,b,c; a,b,d; a,c,d; b,c,d. Let R 1 = {(a, b),(b, a), (c, d), (d, c)} and R 2 = {(a, c), (c, a), (a, d), (d, a), (b, c), (c, b), (b, d), (d, b)}. Then, we have ∅ R i N T R, i = 1, 2. Moreover, for all (x, y) ∈ N T R, we have (x, y) ∈ R 1 if and only if (y, x) / ∈ R 2 . R 1 vacuously satisfies Conditions 1 and 2. R 2 satisfies

  contradicting[START_REF] Sethuraman | Integer programming and Arrovian social welfare functions[END_REF]. f satisfies PO as, for all (x, y) ∈ T R, we have xP (f (P))y, for all P ∈ Ω n ; moreover, for all (x, y) ∈ N T R and for all P ∈ Ω n , xp i y, for all i ∈ E, implies xP (f (P))y, by[START_REF] Arrow | Social choice and individual values[END_REF]. f satisfies IIA as, for each (x, y) ∈ N T R and for each S ∈ E, we have xP (f (P))y if and only if d S (x, y) = 1, xI(f (P))y if and only if d S (x, y) = 1 2

. Eighth, xI(f (P))yI(f (P))z and zP (f (P))x. Then,

d A∪U ∪V (x, y) = 1 2 and d A∪U ∪V (x, y) + d B∪U ∪W (y, z) + d C∪V ∪W (z, x) > 3 2 ,

  Proposition 4. Let n = 2. If d is a solution to IP1 on Ω, then it is a solution to IP1 on the same Ω. Proof. Let n = 2. Let d be a solution to IP1 on Ω. Consider a triple x, y, z and disjoint and possibly empty sets A, B, C, U, V, W ∈ E whose union includes all agents and which satisfy Conditions ( * ). Suppose that d A∪U ∪V (x, y), d B∪U ∪W (y, z), d C∪V ∪W (z, x) ∈ {0, 1} and

	contradicting (4). Suppose that d S (x, y) = 1 2 and d S (x, y) + d S (y, z) > 1 2 + d S (x, z). Then,
	d U (x, y) + d U (y, z) + d C (z, x) >	3 2	,
	contradicting (4). Therefore, d satisfies (8). Hence, d is a solution to IP1
	on Ω.
	The following result shows that the converse of Proposition 3 holds -and
	IP1 and IP1 coincide -when n = 2.
	d U (x, y) + d U (y, z) + d C (z, x) <	3 2	,

. Therefore, d satisfies (7). Suppose now that d S (x, y) = 1 2 and d S (x, y) + d S (y, z) <

1

2 + d S (x, z). Then,

  and Muller's Conditions II and IV are redundant. Corollary 3. Ω is KM decomposable if and only if it is decomposable. Proof. It is an immediate consequence of Kalai and Muller's Theorem 2 and Corollary 2.

  Theorem 4. There exists a nondictatorial ternary solution to IP1 on Ω, d, for n = 2, if and only if there exists a nondictatorial ternary solution to IP1 on Ω, d * , for n > 2.Proof. Let d be a nondictatorial ternary solution to IP1 on Ω for n = 2. Determine d * as follows. Given (x, y)∈ N T R and S ∈ E, let d * S (x, y) = 1 if 1, 2 ∈ S; d S (x, y) = 0 if 1, 2 ∈ S c ; d * S (x, y) = d {1} (x, y) and d * S c (y, x) = d {2} (y, x) if 1 ∈ S and 2 ∈ S c. Then, it is straightforward to verify that d * satisfies (1)-(4) and that is nondictatorial. Hence, d * is a nondictatorial ternary solution to IP1 on Ω, for n > 2. Conversely, let d * be a nondictatorial ternary solution to IP1 on Ω for n > 2. Determine d as follows. Consider

  Then, it is straightforward to verify that d satisfies (1) and[START_REF] Kalai | Characterization of domains admitting nondictatorial social welfare functions and nonmanipulable voting procedures[END_REF]. Moreover, by Proposition 3, d satisfies (5)-(8) as d * is a solution to IP1 on Ω. But then, d is a solution to IP1 on Ω and this, in turn, implies that it is a solution to IP1 on Ω, by Proposition 4. Finally, d is nondictatorial as d {1} (u, v) = 1 2 . Hence, d is a nondictatorial ternary solution to IP1 on Ω, for n = 2From Theorem 4, we obtain the following corollary, which extends Kalai and Muller's Theorem 1 to the case of ASWFs with ties. It is an immediate consequence of our Theorem 1 in Section 4. There exists a nondictatorial ASWF with ties on Ω, f , for n = 2, if and only if there exists a nondictatorial ASWF with ties on Ω, f

	Corollary 4.

* , for n > 2.

  Consider the following two cases. First, d {1} (y, z) = 1. Then, (x, y) ∈ R * Therefore, d satisfies (8).d is nondictatorial as ∅ R * i ⊂ N T R, i = 1, 2.Hence, d is a nondictatorial ternary solution to IP1 on Ω.Our characterization theorem for ASWFs with ties follows from Theorem 1 as a corollary of Theorem 5. This corollary is the generalization of Kalai and Muller's Theorem 2 for ASWFs without ties.Corollary 5. There exists a nondictatorial ASWF with ties on Ω, f , for n ≥ 2, if and only if Ω is strictly decomposable.Proof. It is an immediate consequence of Propositions 3 and 4, Theorems 1 and 5, and Corollary 4.

	1 , ∈ R 1 , contradicting Condition 4. Second, d {1} (y, z) = (y, z) ∈ R 1 , and (x, z) / 1 2 . Then, (x, y) ∈ R * 1 , (y, z) ∈ R * 1 , and (x, z) / ∈ R * 1 , contradicting Condition 2. Finally, suppose that d {1} (x, y) = 1 2 and
	d {1} (x, y) + d {1} (y, z) <	1 2	+ d {1} (x, z).
	Consider the following two cases. First, d {1} (y, z) = 0. Then, (z, y) ∈ R 2 , (y, x) ∈ R * 2 , and (z, x) / ∈ R 2 , contradicting Condition 4. Second, d {1} (y, z) = 1 2 . Then, (x, y) ∈ R * 1 , (y, z) ∈ R * 1 , and (x, z) / ∈ R * 1 , contradicting Condition 2.

Condition 3. There exists a set R * ⊂ A 2 , with R ∩ R * = ∅, such that, for all triples x, y, z, if there exist p, q ∈ Ω satisfying xpypz and yqzqx, then

(x, y) ∈ R * implies that (x, z) ∈ R.

Condition 4. There exists a set R * ⊂ A, with R ∩ R * = ∅, such that, for all triples of alternatives x, y, z, if there exist p, q ∈ Ω satisfying xpypz

[START_REF] Maskin | Fonctions de préférence collective définies sur des domaines de préférence individuelle soumis à des constraintes[END_REF] independently investigated the same issue.

We notice that, in our formulation of (7) and (8), we suppose that there exist p, q ∈ Ω which satisfy xpypz and zqyqx, whereas[START_REF] Sethuraman | Integer programming and Arrovian social welfare functions[END_REF], in their formulation of (vii) and (viii), supposed that there exists only p ∈ Ω which satisfies xpypz.

We notice that our version of Maskin's Theorem 3 does not cover the case where Ω ∩ (R \ P) = ∅.

and zqyqx, then (x, y) ∈ R and (y, z) ∈ R * imply that (x, z) ∈ R, and (x, y) ∈ R * and (y, z) ∈ R imply that (x, z) ∈ R.

A domain Ω is said to be strictly decomposable if and only if there exist four sets R 1 , R 2 , R * 1 , and R * 2 , with R i N T R, ∅ R * i ⊂ N T R, i = 1, 2, such that, for all (x, y) ∈ N T R, we have (x, y) ∈ R 1 if and only if (x, y) / ∈ R * 1 and (y, x) / ∈ R 2 ; (x, y) ∈ R * 1 if and only if (y, x) ∈ R * 2 ; moreover, R i , i = 1, 2, satisfies Condition 1; R i and R * i , i = 1, 2, satisfy Condition 2; each pair (R i ,R * i ), i = 1, 2, satisfies Conditions 3 and 4. On the basis of the notion of strict decomposability, we provide now the characterization of domains admitting nondictatorial ternary solutions to IP1.

Theorem 5. There exists a nondictatorial ternary solution to IP1 on Ω, d, for n = 2, if and only if Ω is strictly decomposable.

Proof. Let d be a nondictatorial ternary solution to IP1 on Ω, for

Then, d is a binary solution, a contradiction. Hence, ∅ R * i ⊂ N T R. Moreover, by using the same argument developed in the proof of Theorem 3, it can be shown that R i , i = 1, 2, satisfies Conditions 1 and 2. Consider a triple x, y, z and suppose that there exist p, q ∈ Ω satisfying xpypz and zqyqx. Moreover, suppose that (x,

, and

contradicting (8). Hence, R * i satisfies Condition 2, i = 1, 2. Consider a triple x, y, z and suppose that there exist p, q ∈ Ω satisfying xpypz and yqzqx.

. Hence, each pair (R i , R * i ), i = 1, 2, satisfies Condition 3. Consider a triple x, y, z and suppose that there exist p, q ∈ Ω satisfying xpypz and zqyqx. Moreover, suppose that (x,

We have proved that Ω is strictly decomposable. Conversely, suppose that Ω is strictly decomposable. Then, there exist four sets

Moreover, it can be shown that d satisfies ( 5) and (7), by using the same arguments developed in the proof of Theorem 3. Consider a triple x, y, z and suppose there exist p, q ∈ Ω satisfying xpypz and yqzqx. Moreover, suppose that d {1} (x, y) = 1 2 and

Then, (x, y) ∈ R * 1 and (x, z) / ∈ R 1 , contradicting Condition 3. Therefore, d satisfies (6). Consider a triple x, y, z and suppose there exist p, q ∈ Ω satisfying xpypz and zqyqx. Moreover, suppose that d {1} (x, y) = 1 2 and and∅ V * i ⊂ N T R, i = 1, 2. Moreover, for all (x, y) ∈ N T R, we have: and(a, d) ∈ V 2 . We have shown that Ω is strictly decomposable.

The example above specifies a domain which is both decomposable and strictly decomposable. Nonetheless, this is not the general case. In the following, we will show, with a theorem and a further example, that a strictly decomposable domain is always decomposable, but the converse is not true.

In order to obtain these results, we preliminarily show the following theorem on the nondictatorial solutions to IP1 . Theorem 6. If there exists a nondictatorial ternary solution to IP1 on Ω, d, for n = 2, then there exists a nondictatorial binary solution to IP1 on Ω, d, for n = 2.

Proof. Let d be a ternary solution to IP1 on Ω, for n = 2. Determine d as follows. Consider q ∈ Σ. For each (x, y) ∈ N T R, let:

2 and xqy. Then, it is immediate to verify that d is a solution to IP1 on Ω, for n = 2. Suppose that d is nondictatorial. Then, d = d is a nondictatorial binary solution to IP1 on Ω, for n = 2. Suppose that d is dictatorial: say, for example, that, for all (x, y) ∈ N T R, d S (x, y) = 1, for all S containing agent 1. In this case, we can say that agent 1 is the dictator for d . Determine d as follows. Let q -1 ∈ Σ be an antisymmetric preference ordering such that, for each (x, y) ∈ A 2 , xqy if and only if yq -1 x. For each (x, y) and(b, d) ∈ R i , i = 1, 2. We have shown that Ω is decomposable. Now suppose that Ω is strictly decomposable. Then, there exist four sets (d,c) ∈ V 2 as V 2 satisfies Condition 1, a contradiction. Hence, V * i = ∅, i = 1, 2, a contradiction. We have shown that Ω is not strictly decomposable.