There is a tradition of imprecision in this subject.

^{1} First, some notation from previous posts.

Suppose that \(f:\Omega^n\rightarrow \Sigma_\Gamma\) is an Arrovian social welfare function. Define the map \(\Delta:\Gamma^2\times\Omega^n\rightarrow 2^E\) by
\[
\Delta(x, y)(P)=\lbrace j \in E: x p_j y\rbrace.
\]
**Definition.** The set \(S\subseteq E\) is **weakly decisive for \(x\) over \(y\)** with respect to the Arrovian social welfare function \(f\) if
\[
\begin{aligned}
(\forall P\in\Omega^n)(S=\Delta(x,y)(P) \Rightarrow x f(P) y)
\end{aligned}
\]
**Definition.** The set \(S\subseteq E\) is **decisive for \(x\) over \(y\)** with respect to the ASWF \(f\) if
\[
\begin{aligned}
(\exists P\in\Omega^n)(S=\Delta(x,y)(P)\land x f(P) y)
\end{aligned}
\]
The following statement is implicit in Vohra *et al.*^{2,3}

**Proposition.** Suppose that \((x,y)\in\Gamma^2\) is a nontrivial pair (in \(\Omega\)). Let \(S\subseteq E\) be nonempty. If \(S\) is decisive for \(x\) over \(y\), then \(S\) is weakly decisive for \(x\) over \(y\).

**Proof.** Suppose there exists \(Q\in\Omega^n\) with \(S=\Delta (x, y)(Q) \land x f (Q) y\). Now suppose that \(S=\Delta (x, y)(P)\). Then \(\forall j\in E, x q_j y \Leftrightarrow x p_j y\). Since \(x f (Q) y\), by independence of irrelevant alternatives, \(x f (P) y\). **QED.**

For nontrivial \((x, y)\in\Gamma^2\) we can unambiguously define "\(S\) is decisive for \(x\) over \(y\)" by the expression "\(S=\Delta (x, y)(P)\land x f (P) y\)." The proposition shows that this condition is independent of the choice of the preference profile \(P\in\Omega^n\) such that \(S=\Delta(x,y)(P)\).

## The linear program associated to an Arrovian social welfare function

We are given a collection \(\Gamma\) of at least three alternatives, denoted \(x,y,z\), a set \(\Omega\) of admissible preference relations, where \(\Omega\subseteq\Sigma_\Gamma\) is the set of preference relations, and an Arrovian soclal welfare function \(f:\Omega^n\rightarrow\Sigma_\Gamma\).
From \(f\) we define a family \(\prod\nolimits_f\) of \(01\)-valued variables.
\[
\begin{aligned}
\prod\nolimits_f := \left\lbrace d_S(x,y)\right\rbrace_{S\subseteq E,(x, y)\in\Gamma^2}
\end{aligned}
\]
satisfying the conditions

**A**,

**B** and

**C** below.

**A.** If \((x,y)\in\Gamma^2\) is a nontrivial pair, then
\[
d_S(x,y) =
\begin{cases}
1,&\textrm{if}\,\forall P\in\Omega^n, S=\Delta(x,y)(P)\Rightarrow x f(P) y;\\
0,&\textrm{otherwise.}
\end{cases}
\]

**B.** If \((x,y)\in\Gamma^2\) is a trivial pair, then
\[
d_S(x,y) =
\begin{cases}
1,& \textrm{if}\,S\not=\emptyset;\\
0,&\textrm{otherwise.}
\end{cases}
\]

**C.** If \((x,x)\in\Delta_\Gamma\), then for each \(S\subseteq E\), \(d_S(x,x)=0.\)
These variables satisfy the following constraints.

0. **Irreflexive.** \(\forall (x,x)\in\Delta_\Gamma,S\subseteq E, d_S(x,x)=0.\)

1. **Unanimity.** \(\forall (x,y)\in\Gamma^2\setminus\Delta_\Gamma, d_E(x,y)=1\)

2. **Independence of Irrelevant Alternatives.** \(\forall (x,y)\in\Gamma^2\setminus\Delta_\Gamma\),
\[
d_S(x,y)+ d_{E\setminus S}(y,x)=1.
\]

3. **Transitivity.** \(\forall (x,y),(y,z),(z,x)\in\Gamma^2\setminus\Delta_\Gamma,\)
\[
d_{\Delta(x,y)(P)}(x,y) +d_{\Delta(y,z)(P)}(y, z)+d_{\Delta(z, x)(P)}(z, x)\le 2.
\]

Now suppose that \(\prod\) is a collection defined by the satisfying B and C above, and in addition the constraints 1--4. Does there exist an Arrovian social welfare function \(f:\Omega^n\rightarrow\Sigma_\Gamma\) such that \(\prod = \prod\nolimits_f\)?
How would we go about defining such an \(f\)? What we can do is define a map
\[
\hat{f}:\Omega^n\rightarrow 2^{\Gamma^2\setminus\Delta_\Gamma}
\]
and show that this induces a map \(f:\Omega^n\rightarrow\Sigma_\Gamma\) by restricting the codomain to the set \(\Sigma_\Gamma\) of finite total orders on \(\Gamma\). Let \(P\in\Omega^n, (x,y)\in\Gamma^2\) and set \(S=\Delta(x,y)(P)\).
Define
\[
\begin{aligned}
x \hat{f}(P) y \Leftrightarrow d_S(x,y)=1.
\end{aligned}
\]
The above formula defines a relation \(\hat{f}(P)\subseteq \Gamma^2\). The relation \(\hat{f}(P)\) is irreflexive by constraint 1; thus \(\hat{f}(P)\subseteq \Gamma^2\setminus\Delta_\Gamma\). Note that by independence of irrelevant alternatives (constraint 3), for any pair \((x,y)\in\Gamma^2\setminus\Delta_\Gamma\), either \(x \hat{f}(P) y\) or \(y \hat{f}(P) x\), but not both. Hence the relation \(\hat{f}(P)\) is connected and asymmetric.
The question now is whether \(\hat{f}(P)\) is transitive. Suppose otherwise; then as the relation \(\hat{f}(P)\) is connected, there exists a condorcet cycle
\[
x \hat{f}(P)y, y\hat{f}(p)z, z\hat{f}(P) x.
\]
Hence there exist sets \(R,S,T\subseteq E\) such that
\[
d_R(x,y) = d_S(y,z) = d_T(z,x) = 1,
\]
where by definition, \(R=\Delta(x,y)(P)\), \(S = \Delta(y,z)(P)\) and \(T=\Delta(z,x)(P)\). But that implies
\[
d_{\Delta(x,y)(P)}(x,y) +d_{\Delta(y,z)(P)}(y, z)+d_{\Delta(z, x)(P)}(z, x)=3
\]
contradicting constraint 4, transitivity. Hence the relation \(\hat{f}(P)\) is a strict total order relation. This defines the required map \(f:\Omega^n\rightarrow \Sigma_\Gamma\). It is straightforward to check that \(f\) satisfies unanimity and independence of independent alternatives.

Oh all right, I'll check. First observe that for \(x,y\in\Gamma\), \(x \hat{f}(P) y \Leftrightarrow x f(P) y\).
For unanimity, suppose that \(P\in\Omega^n\) and that \((\forall j\in E)(x p_j y)\). Then \(E=\Delta(x,y)(P)\), and by constraint 2 and the defining relation above, \(x f(P) y\).
For independence of irrelevant alternatives, let \(P,Q\in\Omega^n\), and suppose that for each \(j\in E, x p_j y \Leftrightarrow x q_j y\). We may assume that \((x,y)\) is a nontrivial pair. Let \(S = \Delta(x,y)(P) = \Delta(x,y)(Q)\). By constraint 2, \(d_S(x,y)=1\) or \(d_{E\setminus S}(x,y) = 1\), but not both. If \(d_S(x,y)=1\), then by the above defining relation, \(x f(P) y \land x f(Q)y\). If \(d_{E\setminus S}(x,y) = 1\), then as \(E\setminus S= \Delta(y,x)(P) = \Delta(y,x)(Q)\), we have \(y f(P) x \land y f(Q) x\). Thus
\[
(\Delta(x,y)(P) =\Delta(x,y)(Q))\Rightarrow (x f(P) y\Leftrightarrow x f(Q) y).
\]
We conclude, by definition of \(f\) and the remarks following, that \(\prod = \prod\nolimits_f\).

### Citations

1. Wiedijk, Freek (2009). "Formalizing Arrow's Theorem." Sadhana

**34** (1): 193--220.

2. Jay Sethuraman, Teo Chung Piaw, and Rakesh V. Vohra.

*Integer Programming and Arrovian Social Welfare Functions.* Mathematics of Operations Research Vol. 28, No. 2, May 2003, pp. 309–326.

3. Vohra, Rakesh V. "2.1 The Integer Program." Mechanism Design: A Linear Programming Approach. Cambridge: Cambridge UP, 2011. 9-10. Print

## Comments

## Post a Comment