# Axioms for Consensus Functions on then-Cube

Authors: C. Garcia-Martinez; F. R. McMorris; O. Ortega; R. C. Powers
Journal: Journal of Applied Mathematics
 (2017)

---

## Abstract

Ap value of a sequence π=(x1,x2,…,xk) of elements of a finite metric space (X,d) is an element x for which ∑i=1kdp(x,xi) is minimum. The lp–function with domain the set of all finite sequences on X and defined by lp(π)={x:x is a p value of π} is called the lp–function on (X,d). The l1 and l2 functions are the well-studied median and mean functions, respectively. In this note, simple characterizations of the lp–functions on the n-cube are given. In addition, the center function (using the minimax criterion) is characterized as well as new results proved for the median and antimedian functions.


---

## Body

## 1. Introduction

Aconsensus function (akalocation function) on a finite connected graph G=(X,E) is a mapping L:X∗→2X∖{∅}, where 2X denotes the set of all subsets of X, and X∗=⋃k≥1Xk with Xk=X×⋯×X︷ktimes. The elements of X∗ are calledprofiles and a generic one oflengthk is denoted by π=(x1,x2,…,xk). Let d denote the usual geodesic distance, where d(x,y) is the length of a minimum length path joining vertices x and y. Suppose the graph G=(X,E) represents the totality of possible locations. Then a profile π=(x1,…,xk) is formed where xi represents the best location from the point-of-view of client (voter, customer, and user) i. A typical approach in location theory is to find those vertices (locations) in X that are “closest” to the profile π. There has been much work in this area of research, ranging from practical computational methods to more theoretical aspects. Since Holzman’s paper in 1990 [1], there have been many axiomatic studies of the procedures themselves which resulted in a much better understanding of the process of location (for a small sample, see [2–4] and references within). Now suppose the vertex set X is the set of all linear orders (preference ranking) on a given set of alternatives. In this consensus situation, a profile π=(x1,…,xk) could represent the collection of ballots of the voters labeled by the set {1,…,k}; that is, xi is the preferred ranking of alternatives by voter i. Here a closest vertex to π would represent the entire group’s preferred consensus ranking. Many references for this classical situation can be found in [5] and other books on voting theory. Another classic situation, and one pertinent to our study, is the process of selecting a committee from a slate of n candidates. Here each of k voters is to nominate a subset of candidates, so a ballot is simply a profile π=(x1,…,xk) where each xi is a subset of the candidates [6, 7]. The vertices of the graph G are the subsets of candidates and the committee consensus function will return one or more subsets closest to the profile.Four popular measures of the closeness, or remoteness, of a vertexx to a profile π=(x1,…,xk) are as follows:(1)
Theeccentricity of x, e(x,π)=max⁡{d(x,x1),d(x,x2),…,d(x,xk)}(2)
Thestatus of x, Sπ(x)=∑i=1kd(x,xi)(3)
Thesquare status of x, SSπ(x)=∑i=1kd2(x,xi)(4)
Thelpstatus of x, lpSπ(x)=∑i=1kdp(x,xi)The consensus functions based on the these measures of remoteness have been defined as follows:(a)
Thecenter function, denoted by Cen, is defined by (1)Cenπ=x∈X:ex,πis  minimum.(b)
Themedian function, denoted by Med, is defined by (2)Medπ=x∈X:Sπxis  minimum.(c)
Themean function, denoted by Mean, is defined by (3)Meanπ=x∈X:SSπxis  minimum.(d)
Thelp-function, denoted by lp, is defined by (4)lpπ=x∈X:lpSπxis  minimum.The median and mean functions are special cases of the lp–function, but earlier work [8–10] shows a striking difference between the case of p=1 and p>1.In this paper we focus on consensus functions on then-dimensional hypercubeQn=(X,E) whose vertex set is X={(w1,…,wn):wi∈{0,1}}. Of course the natural realization of Qn is the set of all subsets of an n-element set. Recall that, for u=(u1,…,un) and v=(v1,…,vn) vertices in Qn, uv is an edge of Qn if and only if ∑i=1nui-vi=1. We set u≤v if and only if ui≤vi for all i. Let d be the usual Hamming distance, where d(u,v)=∑i=1nui-vi, so that uv is an edge if and only if d(u,v)=1. Let ⊕ denote the additionmodulo 2, and define u⊕v=(u1⊕v1,…,un⊕vn). For a profile π=(x1,…,xk) and u∈Qn let π⊕u=(x1⊕u,…,xk⊕u). Let 0 = (0,…,0) and 1 = (1,…,1). Note that x⊕x=0 for all x∈Qn. Also it is easy to see that, for x,y and z vertices in Qn, d(x,y)=d(x⊕z,y⊕z). We set ej∈Qn to be the vertex with 0’s everywhere except 1 in the jth coordinate. So, for example, in Q5(5)0,0,1,1,0=e3⊕e4,0,0,1,0,1⊕e3=0,0,0,0,10,1,0,1,1⊕0,0,1,1,0=0,1,1,0,1=e2⊕e3⊕e5.Let〈π〉 denote the subgraph induced by the vertices comprising π. Note that 〈π⊕v〉 is isomorphic to 〈π〉 for all v∈Qn, and so intuitively 〈π⊕v〉 is simply a “translation” of 〈π〉 to another position within Qn. Our goal is to use the particular structure of Qn to present a very simple unifying approach to give axiomatic characterizations of the consensus functions Cen, Med, and lp on these graphs. Mulder and Novick [10, 11] have given an elegant set of axioms characterizing the function Med on all median graphs (of which Qn is a special case) whereas our axioms are essentially straightforward properties that follow from the definitions. At present the most general graph for which characterizations exist for Cen, Mean, and lp is a tree [9, 12–14]. An interesting weighted version of Cen on Qn is studied in [6].We mention that the following results can be framed in the more abstract context of finite Boolean algebras, as it is done in [15–17]. We prefer to work in the more specific situation of the n-cube where properties become quite easy to visualize, and yet we are working without loss of generality because every finite Boolean algebra is isomorphic to an n-cube.


## 2. The Axioms and Characterizations of Cen, Med, andlp-Function

In this section we give two very simple properties that will allow us to establish a general result that can be used to give a new way to viewCen,Med, and lp defined on Qn. Let f:X∗→2X∖{∅} be a consensus function on Qn=(X,E). Our key axiom for a consensus function f is the following.Translation (T). For any profile π and vertices u and v of Qn,(6)u∈fπimplies  thatu⊕v∈fπ⊕v.Note that this is equivalent tou∈f(π) if and only if u⊕v∈f(π⊕v).Now letf and g be consensus functions on Qn and let x0 be a vertex. We say f and gagree at x0 if for any profile π(7)x0∈fπiffx0∈gπ.Theorem 1.
If the consensus functionsf and g on Qn both satisfy (T) and agree at a vertex x0, then f=g.Proof.
Letπ be a profile and v∈X. Then there exists v′∈X such that v⊕v′=x0. Since f satisfies (T), we have(8)v∈fπiffv⊕v′=x0∈fπ⊕v′.Because f and g agree at x0,(9)x0∈fπ⊕v′iffx0∈gπ⊕v′.Since g satisfies (T),(10)v⊕v′=x0∈gπ⊕v′iffv∈gπ.Hence v∈f(π) if and only if v∈g(π).Theorem1 implies that if f and g are consensus functions on Qn and both satisfy (T); then f=g if the conditions placing0 in f(π) are the same as the conditions placing0 in g(π).As observed before,d(x,y)=d(x⊕z,y⊕z) for x,y, and z vertices in Qn. Using this and the definitions it is easy to see that Cen, Med, and lp all satisfy (T). Therefore, characterizations will follow once the conditions are obtained for when 0∈Cen(π), 0∈Med(π), and 0∈lp(π). We present these results in a series of lemmas and corollaries.Letu∈Qn and set u=d(0,u), that is, the number of ones that appear in the representation u as a vertex of Qn. Let π=(x1,x2,…,xk) be a profile on Qn. Then π is defined to be(11)π=max⁡x1,x2,…,xk.Lemma 2.
LetCen be the center function on Qn and π a profile. Then(12)0∈Cenπiffπ≤π⊕u,∀u∈Qn.Proof.
The result is clear becaused(x,y)=d(x⊕z,y⊕z) in Qn, and e(0,π)=π for any profile π.Corollary 3.
Letf be a consensus function on Qn. Then f=Cen if and only f satisfies (T) and for every profile π and u∈Qn(13)0∈fπiffπ≤π⊕u.Mulder and Novick [10] give an elegant characterization of Med on Qn, which was extended to all median graphs in [11]. We will give another characterization using the approach given by Theorem 1. For a profile π=(x1,…,xk) let xi=(x1i,…,xni). The next result has been noted in [10].Lemma 4.
LetMed be the median function on Qn and π=(x1,…,xk) a profile. Then(14)0∈Medπiff∑j=1kxij≤k2∀i.Corollary 5.
Letf be a consensus function on Qn. Then f=Med if and only f satisfies (T) and for any profile π=(x1,…,xk),(15)0∈fπiff∑j=1kxij≤k2∀i.For the functionlp it is easy to see from the definitions that, for any profile π and a in Qn,(16)0∈lpπiffa=0⊕a∈lpπ⊕a.As in [17] we consider the p-characteristic of a profile π=(x1,x2,…,xk) to be the number(17)Charpπ=∑i=1nxip.Lemma 3.12 in [17] gives the following result.Lemma 6.
Consider the functionlp on Qn, and let π=(x1,…,xk) be a profile. Then(18)0∈lpπiffCharpπ≤Charpπ⊕aforeveryainQn.Corollary 7.
Letf be a consensus function on Qn. Then f=lp if and only f satisfies (T) and for any profile π=(x1,…,xk),(19)0∈fπiffCharpπ≤Charpπ⊕aforeveryvertexainQn.Here are three other examples of consensus functions that satisfy the Translation property. However it is clear that these functions would not be useful in committee elections or as location functions, for instance.Example 1.
Letf1 be the consensus function on Qn defined by f(π)={x1} for any profile π=(x1,…,xk). That is, f1 is a standard projection function. Then clearly f1 satisfies (T).Example 2.
Letf2 be the consensus function on Qn defined by f2(π)=X for all profiles π. That is, f2 is the constant function with ouput being the entire vertex set X. Then f2 satisfies (T), and moreover it can be easily shown that it is the only constant function that satisfies (T).Example 3.
Letf3 be the consensus function on Qn defined by f3(π)={π} for all π where {π} is the set of vertices appearing in the profile π. Then clearly f3 satisfies (T).The functionf2 allows us to see some of the implications of imposing (T). First we need to recall one of the crucial axioms for the characterization of the consensus function Med [10, 11, 18].Consistency (C). The consensus function f satisfies (C) if, for profiles π1 and π2,(20)fπ1∩fπ2≠∅impliesfπ1π2=fπ1∩fπ2.Proposition 8.
A consensus functionf on Qn satisfies (T), (C), and(21)⋂x∈Xfx≠∅if and only if f=f2.Proof.
Clearlyf2 satisfies the conditions, so now let f be a consensus function that satisfies (T), (C), and the intersection condition. Let v∈f(x) for all x∈X. Then since f satisfies (T) we have v⊕x∈f(x⊕x)=f(0) for all x∈X. Now let w be an arbitrary vertex. Then w=v⊕(v⊕w)∈f(0) and thus f(0)=X. So if z is any vertex in X, z⊕x∈f(0) and since f satisfies (T) we have(22)z=z⊕x⊕x∈f0⊕x=fx.Therefore f(x)=Xfor  allx∈X, which means that f(π)=X for all profiles π of length 1. Using (C) and induction we conclude that f(π)=X for all profiles π, that is, f=f2.


## 3. Alternative Characterizations of the Median and Antimedian Functions onQn

For any profileπ=v1,…,vk such that(23)vi=x1i,…,xni∈0,1nfor i=1,…k, let Maj(π)=(w1,…,wn) be the vertex in X such that(24)wi=1iff∑j=1kxij>k2for i=1,…,n. We will say that a location function f satisfies the condition (Maj) if(25)Majπ∈fπfor any profile π. We have previously noted that the median function satisfies (T) and we will show below that, as expected, Med satisfies (Maj). However, there are other location functions that satisfy these two conditions, such as f2, for example. But, arguably f2 is not a very reasonable method of consensus or location. So our next step is to invoke a condition that restricts the range of a location function.For any profileπ=(v1,…,vk) such that(26)vi=x1i,…,xni∈0,1nfor i=1,…,k define theCondorcet score of π to be(27)Csπ=i:∑j=1kxij=k2.Observe that if the profile length k is odd, then Cs(π)=0. A location function f satisfiesRestricted Range (RR) if(28)fπ≤2Csπfor any profile π.We can now give a completely different characterization ofMed from that found in [10].Theorem 9.
Letf be a location function on Qn. Then f=Med if and only if f satisfies (T), (Maj), and (RR).Proof.
Assumef=Med. We already know that f satisfies (T), so we only need to show that Med satisfies (Maj) and (RR).
We will follow the notation given above. Letπ=(v1,…,vk) be a profile such that(29)vi=x1i,…,xni∈0,1nfor i=1,…,k and let Maj(π)=(w1,…,wn)=w. Now let a=(y1,…,yn)≠w be such that ym≠wm for some m. First note that, for every j, because wj and xji are equal for at least k/2 of the i’s,(30)∑i=1kyj-xji≥∑i=1kwj-xji.Since(31)Sπa=∑i=1kda,viwhereda,vi=∑j=1nyj-xjiwe have(32)Sπa=∑i=1k∑j=1nyj-xji=∑j=1n∑i=1kyj-xji≥∑j=1n∑i=1kwj-xji=Sπw.Therefore w∈Med(π) and f satisfies (Maj).
Letu=(u1,…,un) be the vertex in X such that(33)ui=1iff∑j=1kxij≥k2for i=1,…,n. For any vertex a=(y1,…,yn) such that w≤a≤u and for any i∈{1,…,n} such that ∑j=1kxij=k/2 we get that wi=0, ui=1, and of course yi∈{0,1}. Observe that(34)∑i=1kyj-xji=k2=∑i=1kwj-xji.Since yi=wi whenever ∑j=1kxij≠k/2 it follows that Sπ(a)=Sπ(w) and so a∈Med(π). Moreover, if b=(z1,…,zn) is vertex in X such that zm≠wm for some m∈{1,…,n} where ∑j=1kxmj≠k/2, then(35)∑i=1kzm-xmi>k2>∑i=1kwm-xmi.In this case, Sπ(b)>Sπ(w) and so b∉Med(π). It now follows that(36)Medπ=Majπ⊕∑α∈Aiα:A⊆S,where(37)S=α∈1,…,n:∑j=1kxαj=k2.Therefore, Medπ=2S=2Cs(π) and hence Med satisfies (RR).
For the converse, assume thatf satisfies (T), (Maj), and (RR). We will show that f=Med. Let π=(v1,…,vk) be a profile. Then, using Theorem 9,(38)v∈Medπiff0∈Medπ⊕viff∑j=1kyij≤k2∀i,where vj⊕v=(y1j,…,ynj) for j=1,…,k. Observe that Maj(π⊕v)=0, and since f satisfies (Maj) it follows that 0∈f(π⊕v). Since f satisfies (T) we get(39)v=0⊕v∈fπ.It now follows that Med(π)⊆f(π) for any profile π. Therefore,(40)Medπ≤fπfor any profile π. We know that Med(π)=2Cs(π) and, by (RR), that fπ≤2Csπ for any profile π. Hence f(π)=Med(π) for any profile π and we are done.The three consensus functions we have considered all minimize a criterion in order to produce vertices that are close to a given profile of vertices, and as such are useful in location theory. When finding locations to place noxious entities, it is more appropriate to maximize rather than minimize these objective functions, and the resulting “anti”-functions have also been well-studied. Because we have proved Theorem9 about the median function, we mention theantimedian function, denoted by AM, defined by (41)AMπ=x∈X:Sπxis  maximum.A M has been characterized on Qn in [19], but we will give an alternate characterization as a corollary to Theorem 9. As before π=(v1,…,vk) is a profile such that(42)vi=x1i,…,xni∈0,1nfor i=1,…,k. Let Min(π)=(m1,…,mn) be the vertex in X such that(43)mi=1iff∑j=1kxij<k2for i=1,…,n. We will say that a location function f satisfies condition (Min) if(44)Minπ∈fπfor any profile π. Corollary 3 now follows from the proof of Theorem 9 in the obvious way by reversing the inequalities.Corollary 10.
Letf be a location function on Qn. Then f=AM if and only if f satisfies (T), (Min), and (RR).



---

*Source: 8025616-2017-01-09.xml*