A Simple Construction of Single-Peaked Domains by Recursively Tiling
01991170 Edogawa University Ping ZHAN 1. Introduction
Single-peakedness was introduced by Black in 1948 as a sufficient condition to overcome Condorcet paradox. Since then it has been attracting researchers in various fields. We show a neatly simple method of constructing complete single-peaked domains of any size, unifying results known earlier and published re- cently. The simplest structure of single-peaked do- mains underlined here makes some insights and fur- ther developments on single-peakedness more easily.
2. Definitions and Preliminaries
2.1. Single-peaked and Condorcet domains Consider a finite set of alternativesXwith a linear order>on it fixed. LetL(X)denote the set of pref- erences1 ≺ onX. A domainD ⊂ L(X) issingle- peaked with respect to the linear order>onXif, for all (strict) preference≺∈ Dand allx∈X, the upper contour sets U≺(x) := {y ∈ X | x ≺ y} ∪ {x} are connected (’convex’) in the order >. In other words, suppose x¯ ∈ X is the peak (or top) prefer- ence, we have (i) x′ > x ≥ x¯ ⇒ x′ ≺ x, or (ii)
¯
x≥x > x′ ⇒x′ ≺x.
In what follows: The ground set is identified as the integer set N = {1,2,· · ·, n}. For i, j ∈ N, we writei ≻ j asij if without confusion. Order refers to preference order if without special explanation.
Single-peaked domain is the subset of Con- dorcet domain (abbreviated as CD). A domain D ⊂ L(N) without two cycles{ijk, jki, kij} and {kji, jik, ikj} when restricted on any alternatives i, j, kinN is aCondorcet domain2.
Condorcet domain is characterized by never con- ditions defined as follows. Forhin{i, j, k}andrin {1,2,3}, thenever conditionshNi,j,kr means thath never has rank r. The single-peaked domain corre- sponds to, the middle never ranking the last. While the middle never ranking best is called pit domain.
These two domains, will be discussed further in the following. For more details about CDs, see, e.g., [3].
1It also is a linear order here.
2The definition here is also described as a property of major- ity acyclic in some literature.
LetΩ = {(i, j) | i, j ∈ N, i < j}. For a linear orderσ, a pair(i, j)∈Ωis called aninversion(w.r.t.
σ) ifj ≺σ i. The set of inversions forσ is denoted by Inv(σ). For linear ordersσ, τ ∈ L(N), we write σ ≪ τ if Inv(σ) ⊆ Inv(τ). (L(N),≪) is called the Bruhat poset, the cover and associated graph of Bruhat poset are defined in a natural way.
Here is a recently published result [4].
A domainD ⊂ L(N)is calledminimally richif for everyi ∈ N, there exists an orderσ ∈ Dsuch that σ has ias the top preference. Note that a maximal widthof the graph of Bruhat poset means associated domainDcontaining at least one pair of completely reversed orders, say, α = 12· · ·(n−1)n andω = n(n−1)· · ·21, with Inv(α) =∅and Inv(ω) = Ω.
Furthermore, the domain of all orders that are single-peaked is denoted by SP(N). A domain D is semi-connected if it contains two completely re- versed orders and an entire path connecting them in the associated graph of Bruhat poset ofD. The con- nection of the graph of Bruhat poset associated with domain D is defined in a natural way. Now we are ready to have:
Theorem 2.1(Theorem 1, [4]): The domainSP(N) of all single-peaked orders is a connected and mini- mally rich Condocet domain with maximal width. (In particular,SP(N)is semi-connected.)
Conversely, ifD ⊂ L(N)is a semi-connected and minimally rich Condocet domain, then D is single- peaked.
2.2. Representing CDs by rhombus tiling The characterization of Condorcet domains by rhombus tiling in paper [1] given by Danilov et al uni- fies and also develops several properties known ear- lier. The representation by rhombus tiling also admits a simple and good visualization.
A rhombus tiling (or simply a tiling) is a planar (directed) graph, a subdivision T of a zonogon into a set ofrhombus tileswith two pairs of parallel arcs of same length3. Hence, rhombus tiles can be repre- sented via vector summation.
3The condition of same length is not crucial here.
1-E-5
日本オペレーションズ・リサーチ学会2019年 春季研究発表会
Letξi ∈R×R>0(i∈N) be vectors in upper half- plane. The sum of segments[0, ξi]of (ξ1, ξ2,· · ·, ξn) forms a zonogon, denoted by Z = Zn. This is the symmetric 2n-gon formed by the points ∑n
i−1aiξ over all0≤ai ≤1, withbottomvertex(0,0)and the topvertexξ1+ξ2+· · ·+ξn. A rhombus congruent to the sum of two segments[0, ξi]and[0, ξj]is called anij-tile, or simply atile, where1≤i < j≤n. (see Figure 1).
s HH HH H Y 6 s s
HH HH H Y
6
s * *
s
* 6
s HH HH H Y 1 s 2
3
3 2 1 s
HH HH H Y
s HH
HH H Y
* s6
6
s * *
s6
s HH HH H Y 1 s 2
3
3 2 1
Figure 1: Two tilings of the zonogon of size 3.
Denote the directed graph associated with a tiling T defined above as GT = (VT, AT). The maximal directed path goes from the bottom to the top ofGT. We call such a (maximal) path a snake of T. The zonogon is bounded by two special snakes, the left boundary lbd(Z) and right boundary rbd(Z) ofZ, the former (latter) gives a liner orderα (resp. ω). Every tile ofTcorresponding to an inversion pair ofΩ[1,2].
Let us denote the set of linear orders associated with the snakes in tilingTbyΣ(T). A setD ⊂ L(N) is calledpeak-pitdomain if for each triplei < j < k in N satisfies never conditions, j never ranking the last, best, or both. Moreover, the domainDiscom- pleteif adding any one more order becomes cyclic.
Theorem 2.2(Theorems 1 and 2, [1]): The setΣ(T) is a Condorcet, or peak-pit domain. The domain is complete.
Conversely, any peak-pit domain is contained in a domain of tiling type.
3. A Recursive Construction of Single- peaked Domain by Tiling
For a domainD ⊂ L(N), let us denote the associ- ated tilingT such thatΣ(T) =DasTD. Denote the single-peaked domain by tiling for alternative setN asSPn. Recall Theorem 2.2, SPn is complete and well defined. Note that we haveΣ(TSPn) =SPn. Theorem 3.1: For the single-peaked domainSPn⊂ L(N), the tilingTSPn can be explicitly constructed for every integern= 2,· · ·, in a recursive way.
(Proof) Outline:
Recursive Procedures
(a) Make a tiling withn−1parallel tiles, stack them in vertical, and call the tiling astrip.
(b) Concatenate the strip, along one border, say left one, withTSPn−1.
(c) Rotate the concatenated tiling until the vertex in top tile of the strip adjacent toTSPn−1 becoming the top vertex of concatenated tiling.
Procedures (a)∼(c) are also shown in Figure 2.
s PP PP P
i s 1
s
1 PP
PP P
i s
JJ JJ ]
s s
PP PP P
i
6 s 6
6 TSPn−1
... ...
...
s s
s PP PP P i
s JJ
JJ ]
s
1 PP
PP P
i J]JJJ s
n 1
n−1 2
2 n−1
1 n
Figure 2: The recursive construction forTSPn. Then, for any integersn >1, the tilings built from the above procedures (a), (b) and (c) beingTSPncan be shown by Theorems 2.1 and 2.2. 2 Corollary 3.2: If SPn are the single-peaked do- mains obtained fromRecursive Proceduresin Theo- rem 3.1 for any integern≥1, then we haveSPn= SP(N).
参考文献
[1] V. I. Danilov, A. V. Karzanov, and G. Koshevoy:
Condorcet domains of tiling type.Discrete Ap- plied Mathematics160(2012) 933–940.
[2] S. Elnistsky: Rhombic tilings of polygons and classes of reduced words in Coxeter groups.
Journal of Combinatorial Theory, Series A 77 (1997) 193-221.
[3] B. Monjardet: Acyclic domains of linear orders:
a survey. In: S. Brams, W. Gehrlein, F. Roberts (Eds.).The Mathematics of Preference, Choice and Order,Springer, (2009) 139-160.
[4] C. Puppe: The single-peaked domain revisited:
A simple global characterization. Journal of Economic Theory176(2018) 55-80.
