Fact of the day: Condorset domains, tiling permutations and contractibility


Consider a collection of vectors \(e_1,\ldots,e_n\) in the upper half-plane, such that \(e_k=(x_k,1)\) and \(x_1>x_2\gt \ldots \gt x_n\). Minkowski sum of the segments \(s_k:=[0,e_k]\) is a zonotope \(\Z\). Rhombus in this context are the Minkowski sums \(\Z(k,l)=s_k\oplus s_l, 1\leq k\lt l\leq n\) of pairs of the segments. Tilings of \(\Z\) by \(n\choose 2\) rhombuses \(\Z(k,l)\) define also an oriented graph (formed by the edges of the rhombuses, and oriented up in the plane). An increasing path from the bottom to the top defines then a permutations in \(\sg_n\): each of the vectors \(e_k\) appears in an increasing path once, and the permutation then is the order of these vectors. Collection of all such permutations corresponding to a tiling \(\tau\) is denoted as \(\sg(\tau)\).

Recall that the Condorset paradox describe a situation when in a collection of odd number of permutations (perhaps, with repetitions), the order defined by majority rues on pairs has cycles: an example is
\{(1,2,3),(2,3,1),(3,1,2): 1\succ 2\succ 3\succ 1:
one can see that alternative \(1\) is preferred to alternative \(2\) by majority, etc…

A Condorset domain is a subset in \(\sg_n\) for which the Condorset paradox cannot happen. A well-known example is the one-peaked permutations (whose graph is a unimodal function). Danilov, Karzanov and Koshevoi noticed that for any tiling \(\tau\) of \(\Z\), the collection \(\sg(\tau)\) is a Condorset domain…

On the negative side, Arrow’s impossibility theorem states that any aggregation procedure subject to some natural “axioms” (which the majority voting satisfies) and defined on all of \(\sg_n, n\geq 3\), does not exist.

In another direction, it was noticed (by Benno Eckmann, Graciela Chichilnisky and others, see surveys here and there) – that in the topological version of preference aggregation (social choice) theory, the key trouble in preference aggregation is caused by the nontrivial topology of the space of preferences, and that all those problems tend to resolve when the space is contractible.

Of course, all of this is not directly applicable to the setup of Arrow’s impossibility theorem: there the space of the preferences is discrete. Yet, one can impose some topology there as well (as done here), in the following way:

Let \(\B=\{(k, l)\}, 1\leq k\neq l\leq n\) be the set of ordered pairs of distinct alternatives. We form a simplicial complex by adding a simplex $latex\sigma$ if the collection of pairwise preferences forming the vertices of that simplex do not have a cycle. The maximal number of vertices in such a simples is, clearly, \(n\choose 2\), and each simplex corresponds to a linear order on the indices \(1,2,\ldots, n\), i.e. an element of \(\sg_n\).

One can prove almost immediately, the resulting simplicial complex is homotopy equivalent to \((n-2)\)-dimensional sphere. This in turn, can be used to deduce Arrow’s theorem.

Now, it is natural to ask, what is the topology of the simplicial complex comprised of the simplices in \(\sg(\tau)\), – is it trivial? This wouldn’t prove anything per se, but would be consistent with the previous observations and point at the general meta statement that social choice paradoxes require nontrivial topology.

And indeed, we have an easy

Theorem: the union of simplices on \(\B\) from \(\sg(\tau)\) is contractible for any rhomboidal tiling of \(\Z\).

Proof: The path corresponding to the leftmost border of the zonotope \(\Z\) corresponds to identity permutation, and some adjacent pair of edges in that path span a rhombus of the tiling. Removing this rhombus gives a smaller tiling, whose leftmost border still will have a pair of adjacent edges spanning a rhombus in \(\tau\). Each operation of removal of a rhombus corresponds, in the simplicial complex, to the removal of a vertex and collapse of the unique simplex containing it to its base, preserving the homotopy type. After a few iteration, one arrives to a unique simplex (corresponding to the rightmost path in \(\Z\)). ▢


No comments yet.

Leave a Reply