Skip to main content

Arrow's Theorem via linear programming

Now for the linear programming proof of Arrow's Impossibility Theorem. We use the notation of previous posts. This argument is more or less lifted from Vohra et al. apart from the statement and proof of Proposition 1 below and some explanatory remarks. We take \(\Omega =\Sigma_\Gamma.\) Since all strict linear orderings of \(\Gamma\) occur, for any \(x, y, z\in\Gamma,\) we have the decisiveness inequalities \[ \begin{aligned} d_S(x, y)\le d_S (x, z)\\ d_S(z, x)\le d_S(y, x) \end{aligned} \] Recall that these inequalities followed from the existence of preference relations \(p, q\in\Omega\) such that \(x p y p z\) and \(z q x q y.\) Vohra et al. use a similar argument starting with the decisiveness inequalities, using \(\Omega=\Sigma_\Gamma\) to obtain the fact that for \(x,y,z,u\in\Gamma,\) \[d_S(x,y)\le d_S(y,z)\le d_S(z,u).\] The point is to replace expressions \(d_S(x,y)\) occur with expressions \(d_S\) in which variables are suppressed. There is another combinatorial fac…

Decisiveness VI

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\).


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


Popular posts from this blog

Game theory of property rights, opportunity cost and power relations

As I have been unable to locate a unified game-theoretic account of property rights, opportunity costs and power relations in the literature, I have devised my own. Now that my colleagues and comrades have an example, perhaps their competitive instincts, if not a taste for the epistemic values, will compel them to surpass my efforts. (I'm joking of course--the mathematics is trivial.) There are \(N\) players. Each player \(j\) has a tree \(T_j\) of positions. (As in real life, we each have our own trees.) The position of player \(j\) is a node of \(T_j\). A strategy \(M_j^r(P)\) of rank \(r\) for player \(j\) at position \(P\) is an \((N+1)\)-tuple \[ \left(P'; S_{j,1}^r,\ldots,S_{j,N}^r\right) \] consisting of a child node \(P'\) of \(P\) in \(T_j\) and a sequence \(S_{j,k}^r\subseteq T^r_k\) of subsets of nodes of \(T_k\) \(1\le k \le N\) of rank greater than or equal to the rank \(r=\mathrm{rank}(P)\) of position \(P\) in \(T_j\). We call the child node \(P'\) o…

Read Robert Paul Wolff on Marx

As long as I am slogging through an account of the Temporal Single-System Interpretation of Marx, it would be a tremendous oversight not to read Wolff, Robert Paul. "A Critique and Reinterpretation of Marx's Labor Theory of Value." Philosophy & Public Affairs 10, no. 2 (1981): 89-120. Prof Wolff is an engaging writer-- even when he does linear algebra--and an important Marxist scholar.

Notes on Marx on exchange value and value, versus opportunity cost

Chapter 1, section 1 of Capital is titled, "THE TWO FACTORS OF THE COMMODITY: USE-VALUE AND VALUE (SUBSTANCE OF VALUE, MAGNITUDE OF VALUE)." I will attempt to translate Marx's remarks into contemporary mathematical notation and offer some comments. Marx writes,
Let us now take two commodities, for example corn and iron. Whatever their exchange relation may be, it can always be represented by an equation in which a given quantity of corn is equated to some quantity of iron, for instance 1 quarter of corn = x cwt of iron. What does this equation signify? It signifies that a common element of identical magnitude exists in two different things, in 1 quarter of corn and similarly in x cwt of iron. Both are therefore equal to a third thing, which in itself is neither the one nor the other. Each of them, so far as it is exchange-value, must therefore be reducible to this third thing. -- Marx, Karl. Capital: A Critique of Political Economy (Das Kapital series Book 1) (p. 127…