Chambers of Arrangements

and

Arrow’s Impossibility Theorem

Hiroaki Terao (Hokkaido University)

May 24, 2007, in Cortona, Italy

CONTENTS

1. Basic concepts about hyperplane arrangements

2. Arrow’s Impossibility Theorem (economics version)

3. Arrow’s Impossibility Theorem (arrangement version)

4. A theorem on arrangements and their chambers

5. Implications (?)

0. Basic concepts about hyperplane arrangements

hyperplanes arrangements of hyperplanes chambers numbers of chambers and Zaslavsky’s theorem characteristic polynomials 1. Arrow’s Impossibility Theorem (economics version)

Assume that a society of m people have ℓ policy options and that every individual has his/her own order of preferences on the ℓ policy options.

A social welfare function can be interpreted as a voting system by which the individual preferences are aggregated into a single societal preference.

We require the following two requirements for a reasonable social welfare function:

Two requirements:

(A) the society prefers the option i to the option j if every individual prefers the option i to the option j (Pareto property),

(B) whether the society prefers the option i to the option j only depends which individuals prefer the option i to the option j (pairwise independence).

Arrow’s impossibility theorem

For ℓ ≥ 3, the only social welfare function satisfying the two requirements (A) and (B) is a dictatorship, that is, the societal preference has to be equal to the preference of one particular individual.

(A) the society prefers the option i to the option j if every individual prefers the option i to the option j (Pareto property),

(B) whether the society prefers the option i to the option j only depends which individuals prefer the option i to the option j (pairwise independence).

Why is this theorem true? What is the reason behind the theorem?

Condorcet’s paradox by Marquis Condorcet (1743-94)

A, B, C : 3 people, 1, 2, 3 : 3 options lists of preferences : A : 1 > 2 > 3, B : 2 > 3 > 1, C : 3 > 1 > 2

In this situation it is very hard to decide the societal preference in a “democratic way” like the majority rule.

Roughly speaking, this is the reason why Arrow’s Impossibility Theorem holds.

2. Arrow’s Impossibility Theorem (arrangement version)

A = {H_{1}, H_{2}, …, H_{n}} : a real central arrangement in R^{ℓ} Ch = Ch(A) : the set of chambers H_{j} : defined by α_{j} = 0 H_{j}^{+} := {x ∈ R^{ℓ} | α_{j}(x) > 0} : a half-space H_{j}^{−} := {x ∈ R^{ℓ} | α_{j}(x) < 0} : the other half-space

B := {+, −} ϵ_{j}^{σ} : Ch ⟶ B are defined by ϵ_{j}^{σ}(C) = στ if C ⊆ H_{j}^{τ} (σ, τ ∈ B, j = 1, …, n)

m : a positive integer Ch^{m}, B^{m} : the m-time direct products ϵ_{j}^{σ} : Ch^{m} → B^{m} is induced from ϵ_{j}^{σ} : Ch → B by ϵ_{j}^{σ}(C_{1}, C_{2}, …, C_{m}) = (ϵ_{j}^{σ}(C_{1}), ϵ_{j}^{σ}(C_{2}), …, ϵ_{j}^{σ}(C_{m}))

Definition 1. A map Φ : Ch^{m} ⟶ Ch is called an admissible map if there exists a family of maps φ_{j}^{σ} : B^{m} ⟶ B (1 ≤ j ≤ n, σ ∈ B = {+, −}) which satisfies the following two conditions:

(1) φ_{j}^{σ}(+, +, …, +) = +, and

(2) the diagram

[figure: Ch^{m}; ϵ_{j}^{σ}; Φ; Ch; ϵ_{j}^{σ}; B^{m}; φ_{j}^{σ}; B]

commutes for each j, 1 ≤ j ≤ n, and σ ∈ B = {+, −}.

Let AM(A, m) denote the set of all admissible maps determined by A and m.

When Φ is an admissible map, a family of maps φ_{j}^{σ} (1 ≤ j ≤ n, σ ∈ B = {+, −}) satisfying the conditions in Definition 1 is uniquely determined by Φ, A and m.

Definition 2. For 1 ≤ h ≤ m, let Φ : the projection to the h-th component, φ_{j}^{σ} : the projection to the h-th component. Then Φ is an admissible map with a family of maps φ_{j}^{σ} (1 ≤ j ≤ n, σ ∈ B = {+, −}).

We call the admissible maps of this type projective admissible maps.

A : the braid arrangement in R^{ℓ} (ℓ ≥ 3) A = {H_{ij} | 1 ≤ i < j ≤ ℓ} where H_{ij} := ker (x_{i} − x_{j}) H_{ij}^{+} := {(x_{1}, x_{2}, …, x_{ℓ}) ∈ R^{ℓ} | x_{i} > x_{j}} H_{ij}^{−} = {(x_{1}, x_{2}, …, x_{ℓ}) ∈ R^{ℓ} | x_{i} < x_{j}}.

S_{ℓ} : the permutation group of {1, 2, …, ℓ} Then Ch(A) ↔ S_{ℓ} (0ne-to-one correspondence) : Each chamber of A can be uniquely expressed as {(x_{1}, x_{2}, …, x_{ℓ}) ∈ R^{ℓ} | x_{π(1)} < x_{π(2)} < … < x_{π(ℓ)}} for a permutation π ∈ S_{ℓ} Thus

the set of orders of preferences ↔ S_{ℓ} ↔ Ch(A)

[figure: S_{ℓ}^{m} ↔; Ch^{m}; ϵ_{j}^{σ}; Φ; Ch; ϵ_{j}^{σ}; ↔ S_{ℓ}; B^{m}; φ_{j}^{σ}; B]

Other correspondences are:

a social welfare function ↔ Φ a dictatorship ↔ the projection to a component

(A) (Pareto property) ↔ (1) (φ_{j}^{σ}(+, …, +) = +) (B) (pairwise independence) ↔ (2) (commutativity) φ_{j}^{σ} ∘ ϵ_{j}^{σ} = ϵ_{j}^{σ} ∘ Φ (∀j)

Arrow’s impossibility theorem can be formulated as:

Arrow’s Impossibility Theorem (arrangement version) If A is a braid arrangement with ℓ ≥ 3, then every admissible map is projective.

Condorcet’s paradox can be interpreted in terms of arrangements and their chambers:

3. A theorem on arramgements

For a central arrangement A, define the rank of A r(A) = codim _{R^{ℓ}} ⋂_{1≤j≤n} H_{j}

Definition 3. A central arrangement A is said to be decomposable if there exist nonempty arrangements A_{1} and A_{2} such that A = A_{1} ∪ A_{2} (disjoint) and r(A) = r(A_{1}) + r(A_{2}). In this case, write A = A_{1} ⊎ A_{2}

A central arrangement A is said to be indecomposable if it is not decomposable.

Remark 1. A = A_{1} ⊎ A_{2} if and only if the defining polynomials for A_{1} and A_{2} have no common variables after an appropriate linear coordinate change.

Remark 2. It is also known that A is decomposable if and only if its characteristic polynomial χ(A, t) is divisible by (t − 1)^{2}.

An arrangement of only one hyperplane is always indecomposable.

An arrangement of two hyperplanes is always decomposable.

The Boolean arrangement is always decomposable into arrangements with only one hyperplane.

Any nonempty real central arrangement A can be uniquely (up to order) decomposed into nonempty indecomposable arrangements:

A = A_{1} ⊎ A_{2} ⊎ … ⊎ A_{r}.

The following two theorems completely determine the set AM(A, m) of admissible maps.

Theorem 1. For a nonempty real central arrangement A with the decomposition

A = A_{1} ⊎ A_{2} ⊎ … ⊎ A_{r}.

there exists a natural bijection AM(A, m) ≃ AM(A_{1}, m) × AM(A_{2}, m) × … × AM(A_{r}, m) for each positive integer m.

Theorem 2. Let A be a nonempty indecomposable real central arrangement and m be a positive integer. Then,

(1) if |A| = 1, AM(A, m) = {Φ : Ch^{m} → Ch | Φ(C, C, …, C) = C for each chamber C},

(2) if |A| ≥ 3, every admissible map is projective.

Corollary. Decompose a nonempty real central arrangement A into nonempty indecomposable arrangements as A = A_{1} ⊎ A_{2} ⊎ … ⊎ A_{a} ⊎ B_{1} ⊎ B_{2} ⊎ … ⊎ B_{b} with |A_{p}| = 1 (1 ≤ p ≤ a) and |B_{q}| ≥ 3 (1 ≤ q ≤ b). Then, for each positive integer m,

|AM(A, m)| = (2^{a(2^{m}−2)} )m^{b} 4. Implications (?)

What do Theorems 1 and 2 imply?

Theorem 1. For a nonempty real central arrangement A with the decomposition A = A_{1} ⊎ A_{2} ⊎ … ⊎ A_{r}. there exists a natural bijection AM(A, m) ≃ AM(A_{1}, m) × AM(A_{2}, m) × … × AM(A_{r}, m) for each positive integer m.

Theorem 2. Let A be a nonempty indecomposable real central arrangement and m be a positive integer. Then,

(1) if |A| = 1, AM(A, m) = {Φ : Ch^{m} → Ch | Φ(C, C, …, C) = C for each chamber C},

(2) if |A| ≥ 3, every admissible map is projective. hyperplane ↔ a political issue arrangement ↔ a set of political issues A = A_{1} ⊎ A_{2} ⊎ … ⊎ A_{r}. ↔ a set of political issues is grouped into certain subsets For each A_{i} with (|A_{i}| ≥ 3), there is a ”mini-dictator.” For each A_{i} with (|A_{i}| = 1), any voting system (e. g., the simple majority rule) works as long as unanimous decisions are respected.

This is random thoughts which might mean nothing. However, Theorems mean something mathematically.

This work can be downloaded from math.CO/0608591 (to appear in Advances in Math. 2007)

Before I stop, I have two more slides:

Two theorems generalizing basic results concerning (simple) arrangements to multi-arrangements

1. The e-multiplicity and the addition-deletion theorems for multiarrangements ( math.CV/0612739 ) (with T. Abe, M. Wakefield) preprint 2006

The Addition-Deletion Theorem has been generalized to the multi case.

2. The characteristic polynomial of a multiarrangement

( math.CA/0611742 ) (with T. Abe, M. Wakefield) to appear in Advances in Math. 2007

The Factorizaion Theorem has been generalized to the multi case.

The Mathematical Society of Japan - Seasonal Institute for Arrangements of Hyperplanes (Sapporo, JAPAN, August 1-10, 2009)

Series of introductory talks and a workshop

August is the best month in Sappro!

I stop here. Thank you!