Necessary and Sufficient Conditions for Weightedness

Get Complete Project Material File(s) Now! »

Initial Segments Complexes Obtained from Qualitative Probability Orders

QualitativeProbabilityOrdersandDiscreteCones

Definition5.1.1.

Anorder9 on2[n] iscalledaqualitativeprobabilityorderon[n]if ∅A (5.1) for every subset A of [n], andsatisfies de Finetti’s axiom, namely for all A,B,C∈2[n] AB ⇐⇒ A∪C B∪C whenever (A∪B)∩C =∅. (5.2) Note that if we have a probability measure p = (p1, …,pn) on [n], where pi is the probability of i, then we know the probability p(A) =Pi∈A pi of every event A. We may now define a relationon 2[n] by AB if and only if p(A)≤p(B); obviouslyis a qualitative probability order on [n], and any such order is called representable (e.g., Fishburn, 1996; Regoli, 2000). Those not obtainable in this way are called non-representable. The class of qualitative probability orders is broader than the class of probability measures for any n ≥ 5 (Kraft et al., 1959). A non-representable qualitative probability orderon [n] is said to almost agree with the measure p on [n] if AB =⇒p(A)≤p(B). (5.3) If such a measure p exists, then the order is said to be almost representable. Since the arrow in (5.3) is only one-sided it is perfectly possible for an almost representable order to have AB but not BA while p(A) = p(B). We begin with some standard properties of qualitative probability or ders which we will need subsequently. Let be aqualitative probability or deron 2[n]. Asusual the following two relations can be derive dfromit. WewriteA≺BifABbutnot BA and A∼B if AB and BA. Lemma 5.1.1. Suppose thatis a qualitative probability order on 2[n], A,B,C,D ∈ 2[n], AB, CD and B∩D = ∅. Then A∪CB∪D. Moreover, if A≺B or C≺D, then A∪C≺B∪D. Proof. Firstly,letusconsiderthecasewhenA∩C =∅. LetB0 = B−CandC0 = C−B and I = B∩C. Then by (5.2) we have A∪C0 B∪C0 = B0∪CB0∪D where we have A∪C0 ≺B0∪D if A≺B or C≺D. Now we have A∪C0 B0∪D⇔A∪C = (A∪C0)∪I(B0∪D)∪I = B∪D. Consider the case when A∩C ,∅. Let A0 = A−C. By (5.1) and (5.2) we now have A0 B. Since now we have A0∩C =∅so by the previous case A∪C = A0∪CB∪CB∪D. One can check that if either A≺B or C≺D we will get a strict inequality A∪C≺ B∪D in this case as well. A weaker version of this lemma can be found in (Maclagan, 1998/99, Lemma 2.2).

Definition 5.1.2.

We say that an orderon 2[n] satisfies the k-th cancellation condition CCk if there does not exist a trading transform (A1, …,Ak;B1, …,Bk) such that Ai Bi for all i∈[k] and Ai ≺Bi for at least one i∈[k].
The key result of (Kraft et al., 1959) can now be reformulated as follows. Theorem 5.1.1 (Kraft-Pratt-Seidenberg). A qualitative probability order is representable if and only if it satisfies CCk for all k = 1,2,…. Itwasalsoshownin(Fishburn,1996,Section2)thatCC2 andCC3 holdforlinear qualitativeprobabilityorders. ThisfollowsfromdeFinetti’saxiomandproperties of linear orders. It can be shown that a qualitative probability order satisfies CC2 and CC3 as well. Hence CC4 is the first nontrivial cancellation condition. As was noticed in (Kraft et al., 1959), for n < 5 all qualitative probability orders are representable, but for n = 5 there are non-representable ones. For n = 5 all orders are still almost representable (Fishburn, 1996) which is no longer true for n = 6 (Kraft et al., 1959).
It will be useful for our constructions to rephrase some of these conditions in vector language. To every such linear order , there corresponds a discrete cone C() in Tn, where T ={−1,0,1}, as defined in (Fishburn, 1996).

Definition5.1.3.

AsubsetC⊆Tn issaidtobeadiscreteconeifthefollowingproperties hold: D1. {e1,…,en}⊆C, where{e1,…,en}is the standard basis of Rn, D2. {−x,x}∩C ,∅ for every x∈Tn, D3. x+y∈C whenever x,y∈C and x+y∈Tn. WenotethatFishburn(1996)requires0 < Cbecausehisordersareanti-reflexive. In our case, condition D2 implies 0∈C. Given a qualitative probability order on 2[n], for every pair of subsets A,B satisfying BA we construct the characteristic vector of this pair χ(A,B) = χ(A)− χ(B)∈Tn. We define the set C() of all characteristic vectors χ(A,B), for A,B∈2[n] such that B A. The two axioms of qualitative probability guarantee that C() is a discrete cone (see Fishburn, 1996, Lemma 2.1). Following Fishburn (1996), the cancellation conditions can be reformulated as follows: Proposition 5.1.1. A qualitative probability ordersatisfies the k-th cancellation conditionCCk ifandonlyiftheredoesnotexistaset{x1, …,xk}ofnonzerovectorsinC()such that x1 +x2 +···+xk = 0 (5.4) and−xi < C() for at least one i. Geometrically, a qualitative probability order is representable if and only if there exists a non-negative vector u∈Rn such that x∈C()⇐⇒(u,x)≥0 for all x∈Tn−{0}, where (·,·) is the standard inner product; that is, is representable if and only if every non-zero vector in the cone C() lies in the closed half-space H+ u = {x∈ Rn | (u,x)≥0}of the corresponding hyperplane Hu ={x∈Rn |(u,x) = 0}. Similarly,foranon-representable but almost representable qualitative probability order, there exists a vector u∈Rn with non-negative entries such that x∈C() =⇒(u,x)≥0 for all x∈Tn−{0}. In the latter case we can have x∈C() and−x < C() despite (u,x) = 0. Inbothcases,thenormalisedvectorugivesustheprobabilitymeasure,namely p = (u1 +…+un)−1 (u1, …,un),fromwhicharisesorwithwhichitalmostagrees.

SimplicialComplexesandTheirCancellationConditions

In this section we will introduce the objects of our study,simplicial complexes that arise as initial segments of a qualitative probability order. Using cancellation conditions for simplicial complexes,we will show that this class contains the thres hold complexes and is contained in the shifted complexes. Using only these conditions it will be easy to show that the initial segment complexes are strictly contained in the shifted complexes. Showing the strict containment of the threshold complexes will require moreel aborate constructions which will be developed in the rest of the chapter.

Definition 5.2.1.

A subset ∆ ⊆ 2[n] is an (abstract) simplicial complex if it satisfies the condition: if B∈∆ and A⊆B, then A∈∆. Subsetsthatarein ∆ arecalledfaces. Abstractsimplicialcomplexesarosefrom geometric simplicial complexes in topology (e.g., Maunder, 1996). Indeed, for every geometric simplicial complex ∆ the set of vertex sets of simplices in ∆ is an abstract simplicial complex, also called the vertex scheme of ∆. In combinatorial optimization various abstract simplicial complexes associated with finite graphs (Jonsson,2005)arestudied,suchastheindependencecomplex,matchingcomplex etc. Abstract simplicial complexes are also in one-to-one correspondence with simple games as defined by (von Neumann & Morgenstern, 1944). Obviously the set of losing coalitions L is a simplicial complex. The reverse is also true: if ∆ is a simplicial complex, then the set 2[n] −∆ is a set of winning coalitions of a certain simple game. A well-studied class of simplicial complexes is the threshold complexes (mostly as an equivalent concept to the concept of a weighted majority game but also as threshold hypergraphs (Reiterman et al., 1985)). A simplicial complex ∆ is a threshold complex if there exist non-negative reals w1,…,wn and a non-negative constant q, such that A∈∆⇐⇒w(A) =X i∈A wi < q. The same parameters define aweighted majority game with the standardnotation [q;w1, …,wn]. A much larger but still well-understood class of simplicial complexes is shifted simplicial complexes (C. Klivans, 2005; C. J. Klivans, 2007). A simplicial complex isshiftedifthereexistsanorderEonthesetofvertices[n]suchthatforanyfaceF, replacinganyofitsverticesx∈Fwithavertex ysuchthat y E xresultsinasubset (F−{x})∪{y} which is also a face. Shifted complexes correspond to complete10 games (Freixas & Molinero, 2009b). Letbe a qualitative probability order on [n] and T∈2[n]. We denote ∆(,T) ={X⊆[n]|X≺T}, where X≺Y stands for XY but not YX, and call it an initial segment of. Lemma5.2.1. Any initial segment of aqualitative probability or derisa simplicial complex. Proof. Supposethat ∆ = ∆(,T)andB∈∆. IfA⊂B,thenletC = B−A. By(5.1)we havethat∅CandsinceA∩C =∅itfollowsfromthedeFinetti’saxiom(5.2)that ∅∪A C∪A which implies that A B. Since ∆ is an initial segment, B ∈ ∆ and AB implies that A∈∆ and thus ∆ is a simplicial complex. We will refer to simplicial complexes that arise as initial segments of some qualitative probability order as an initial segment complex. In a similar manner as for the qualitative probability orders, cancellation conditions will play a key role in our analyzing simplicial complexes. Definition5.2.2. Asimplicialcomplex ∆ issaidtosatisfyCC∗ k iffornok≥2doesthere exist a trading transform (A1,…,Ak;B1,…,Bk), such that Ai ∈ ∆ and Bi < ∆, for every i∈[k]. One can show the connection between CCk and CC∗ k. Theorem 5.2.1. Suppose is a qualitative probability order on 2[n] and ∆(,T) is its initial segment. Ifsatisfies CCk then ∆(,T) satisfies CC∗ k. This gives us some initial properties of initial segment complexes. Sinceconditions CCk, k = 2,3, hold for all qualitative probability orders (Fishburn, 1996) we obtain Theorem 5.2.2. If an abstract simplicial complex ∆ ⊆2[n] is an initial segment complex, then it satisfies CC∗ k for all k≤3. From this theorem we get the following corollary, due to Caroline Klivans (personal communication):
Corollary 5.2.1. Every initial segment complex is a shifted complex. Moreover, there are shifted complexes that are not initial segment complexes.
Proof. Let ∆ be a non-shifted simplicial complex. then it is known to contain an obstruction of the form: there are i, j ∈ [n], and A,B ∈ ∆, neither containing i or j, sothatA∪iandB∪jarein ∆ butneitheri∪Bnor j∪Aarein ∆ (C.Klivans,2005). But then (A∪i,B∪ j;B∪i,A∪ j) is a trading transform that violates CC∗ 2. Since all initial segments satisfy CC∗ 2 they must all be shifted. Ontheotherhand,thereareshiftedcomplexesthatfailtosatisfyCC∗ 2 andhence can not be initial segments. Let ∆ be the smallest shifted complex (where shifting is with respect to the usual ordering) that contains{1,5,7}and{2,3,4,6}Then it is easy to check that neither{3,4,7}nor{1,2,5,6}are in ∆ but ({1,5,7},{2,3,4,6};{3,4,7},{1,2,5,6}) is a trading transform in violation of CC∗ 2. Similarly, the terminal segment G(,T) ={X⊆[n]|TX} of any qualitative probability order is a complete simple game. Theorem2.4.2ofthebook(Taylor&Zwicker,1999)canbereformulatedtogive necessary and sufficient conditions for the simplicial complex to be a threshold. Theorem5.2.3. An abstract simplicial complex∆⊆2[n] is a thres hold complexifandonly if the condition CC∗ k holds for all k≥2. Above we showed that the initial segment complexes are strictly contained in the shifted complexes. What is the relationship between the initial segment complexes and threshold complexes? Lemma 5.2.2. Every threshold complex is an initial segment complex. Proof. The threshold complex defined by the weights w1,…,wn and a positive constant q is the initial segment of the representable qualitative probability order where pi = wi, 1 ≤ i ≤ n and where the threshold set T has the property that w(A)≤w(T) < q for all A∈∆. This leaves us with the question of whether this containment is strict, i.e., are there initial segment complexes which are not threshold complexes. As we know any initial segment of a representable qualitative probability order is a threshold simplex. Onemightthinkthatevrynon-representablequalitativeprobabilityorder would have at least one initial segmentt that is not threshold. Unfortunately that may not be the case. Example 5.2.1. This example, adapted from (Maclagan, 1998/99, Example2.5, Example 3.9),givesanon-representable qualitative probability or derfor which every initial segment complex is threshold. Construct a representable qualitative probability order on 2[5] using the p0 is{7,10,16,20,22}. The order begins ∅≺1≺2≺3≺12≺4≺5≺··· where 1 denotes the singleton set {1} and by 12 we mean {1,2}. Since the qualitative probability order is representable, every initial segment is a threshold complex. Now suppose we interchange the order of 12 and 4. The new ordering, which begins ∅≺1≺2≺3≺4≺12≺5≺··· , isstillaqualitativeprobabilityorderbutitisnolongerrepresentable(Maclagan,1998/99, Example2.5). With one exception,all of the initial segments in this newnon-representable qualitative order are initial segments in the original one and, thus, are threshold. The one exception is the segment ∅≺1≺2≺3≺4 which is obviously a threshold complex.
Another approach to finding an initial segment complex that is not threshold is to construct a complex that violates CC∗ k for some small value of k. As noted above, all initial segment complexes satisfy CC∗ 2 and CC∗ 3 so the smallest condition that could fail is CC∗ 4. We will now show that for small values of n cancellation condition CC∗ 4 is satisfied for any initial segment. This will also give us invaluable information on how to construct a non-threshold initial segment later.
Definition 5.2.3. Twopairsofsubsets (A1,B1) and (A2,B2) aresaidto be compatible if the following two conditions hold: x∈A1∩A2 =⇒x∈B1∪B2, and x∈B1∩B2 =⇒x∈A1∪A2. Lemma5.2.3. Letbeaqualitativeprobabilityorderon2[n],T⊆[n],andlet∆ = ∆n(,T) betherespectiveinitialsegment. SupposeCC∗ s failsand(A1, …,As,B1, …,Bs)isatrading transform, such that Ai ≺TBj for all i, j∈[s]. If any two pairs (Ai,Bk) and (Aj,Bl) are compatible, thenfails to satisfy CCs−1. Proof. Let us define
¯ Ai = Ai−(Ai∩Bk), ¯ Bk = Bk−(Ai∩Bk), ¯ Aj = Aj−(Aj∩Bl), ¯ Bl = Bl−(Aj∩Bl).
We note that
¯ Ai∩ ¯ Aj = ¯ Bk∩ ¯ Bl =∅. (5.5) Indeed, suppose, for example, x ∈ ¯ Ai ∩ ¯ Aj, then also x ∈ Ai ∩ Aj and by the compatibilityx∈Bk orx∈Bl. In both cases it is impossible for xtobeinx∈ ¯ Ai∩ ¯ Aj. We note also that by Lemma 5.1.1 we have
¯ Ai∪ ¯ Aj ≺ ¯ Bk∪ ¯ Bl. Now we observe that ( ¯ Ai, ¯ Aj,Am1,…,Ams−2; ¯ Bk, ¯ Bl,Br1,…,Brs−2). is a trading transform. Hence, due to (5.5), ( ¯ Ai∪ ¯ Aj,Am1,…,Ams−2; ¯ Bk∪ ¯ Bl,Br1,…,Brs−2) is also a trading transform. This violates CCs−1 since (5.6) holds and Amt ≺ Brt for all t = 1,…,s−2. Corollary 5.2.2. Let be a qualitative probability order on 2[n]. Suppose CC∗ s fails and (A1, …,As,B1, …,Bs)isatradingtransform,suchthatAi Bi foralli∈[s]andAi ≺Bi foratleastonei. Ifanytwopairs(Ai,Bi)and(Aj,Bj)arecompatible,thenfailstosatisfy CCs−1. Proof. Without loss of generality we can assume i = 1 and j = 2. Let
¯ A1 = A1−B1, ¯ A2 = A2−B2, ¯ B1 = B1−A1, ¯ B2 = B2−A2. FollowingtheproofofLemma5.2.3andtakingintoaccountLemma5.1.1wehave a trading transform ( ¯ A1∪ ¯ A2,A3,…,As; ¯ B1∪ ¯ B2,B3,…,Bs), where ¯ A1∪ ¯ A2 ¯ B1∪ ¯ B2 and Ak Bk for all k = 3,…,s. ToshowthatthetradingtransformabovewitnessesafailureofCCs−1,weneed to prove that at least one inequality out of ¯ A1 ∪ ¯ A2 ¯ B1 ∪ ¯ B2 and Ak Bk, where k∈{3,…,s}, is strict. Note that, in the initial trading transform, there exists t∈[s] suchthatAt ≺Bt. Ift > 2,thenCCs−1 isclearlyfails. Ift∈{1,2},thenbyLemma5.1.1 we have ¯ A1∪ ¯ A2 ≺ ¯ B1∪ ¯ B2 and CCs−1 fails as well. By definition of a trading transform we are allowed to use repetitions of the same coalition in it. However we will show that to violate CC∗ 4 we need a trading transform (A1,…,A4;B1,…,B4) where all A’s and B’s are different. Lemma5.2.4. Letbeaqualitativeprobabilityorderon2[n],T⊆[n],andlet∆ = ∆n(,T) betherespectiveinitialsegment. SupposeCC∗ 4failsand(A1, …,A4,B1, …,B4)isatrading transform, such that Ai ≺TBj for all i, j∈[4]. Then |{A1, …,A4}|=|{B1, …,B4}|= 4. Proof. Note that pairs (Ai,Bj),(Al,Bk) are not compatible for every i , l and j , k. Otherwise by Lemma 5.2.3 the order fails CC3, which contradicts the fact that every qualitative probability satisfies CC3. Assume, to the contrary, that we have at least two identical coalitions among A1, …,A4 or B1, …,B4. Without loss of generality we can assume A1 = A2. Clearly all A’s or all B’s cannot coincide and there are at least two different A’s and two different B’s. Suppose A1 , A3 and B1 , B2. The pair (A1,B1),(A3,B2) is not compatible. It means one of the following two statements is true: either there is x ∈ A1 ∩A3 such that x < B1 ∪B2 or there is y∈B1∩B2 suchthat y < A1∪A3. Considerthefirstcase. Thesecondcaseissimilar. Weknowthatx∈A1∩A3 andwehaveatleastthreecopiesofxamongA1, …,A4. At the same time x < B1 ∪B2 and there could be at most two copies of x among B1, …,B4. This is a contradiction. Theorem 5.2.4. CC∗ 4 holds for ∆ = ∆n(,T) for all n≤17. Proof. Let us consider the set of column vectors U ={x∈R8 |xi ∈{0,1}and x1 +x2 +x3 +x4 = x5 +x6 +x7 +x8 = 2}. (5.7) This set has an involution x 7→ x¯, where ¯ xi = 1−xi. Say, if x = (1,1,0,0,0,0,1,1)T, then x¯ = (0,0,1,1,1,1,0,0)T. There are 36 vectors from U which are split into 18 pairs{x,x¯}. Suppose now a trading transformT = (A1,A2,A3,A4;B1,B2,B3,B4) witnesses a failureofCC∗ 4. ItmeansthatAi ≺TBj andnotwocoalitionsinT coincide. Letus writethecharacteristicvectorsofA1,A2,A3,A4,B1,B2,B3,B4 asrowsof8×nmatrix M, respectively. Sincesatisfies CC3, by Lemma 5.2.3 we know that no two pairs (Ai,Ba)and(Aj,Bb)arecompatible. Thesamecanbesaidaboutthecomplementary pair of pairs (Ak,Bc) and (Al,Bd), where{a,b,c,d}={i, j,h,l}= [4]. We have Ai ≺Ba, Aj ≺Bb, Ah ≺Bc, Al ≺Bd, Since(Ai,Ba)and(Aj,Bb)arenotcompatibleoneofthefollowingtwostatementsis true: either there exists x∈Ai ∩Aj such that x < Ba ∪Bb or there exists y∈Ba ∩Bb suchthatx < Ai∪Aj. AsT isatradingtransforminthefirstcasewewillalsohave x∈Bc∩Bd such that x < Ah∪Al; in the second y∈Ah∩Al such that y < Bc∪Bd.

Contents
Preface
Acknowledgments
1 Introduction
1.1 Background and Motivation
1.2 Summary of Results
2 Preliminaries
2.1 Hypergraphs and Simple Games
2.2 Constant Sum Games
2.3 Weighted Majority Games
2.4 Trading Transform
2.5 Necessary and Sufficient Conditions for Weightedness
2.6 At Least Half Property
2.7 Desirability Relation and Complete Games
2.8 Weightedness and Complete Games
2.9 Dual Games
2.10 Substructures
3 Weightedness and Rough Weightedness
3.1 Definitions and Examples
3.2 Games and Ideals
3.3 Criteria for Weighted Majority Games
3.4 Criteria for Roughly Weighted Games
3.5 Complete Simple Games
3.6 Games with a Small Number of Players
3.7 Conclusion and Further Research
4 Generalizations of Rough Weightedness
4.1 Preliminaries
4.2 TheA-Hierarchy
4.3 B-Hierarchy
4.4 C-Hierarchy
4.5 Degrees of Roughness of Games with a Small Number of Players
4.6 Conclusion and Further Research
5 Initial Segments Complexes Obtained from Qualitative Probability Orders
5.1 Qualitative Probability Orders and Discrete Cones
5.2 Simplicial Complexes and Their Cancellation Conditions
5.3 Constructing Almost Representable Orders from Nonlinear Representable Ones .
5.4 An Example of a Nonthreshold Initial Segment of a Linear Qualitative Probability Order
5.5 Proofs of Claim 1 and Claim 2
5.6 Acyclic Games and a Conjectured Characterization
5.7 Conclusion
A Proof of Theorem 3.4.1
B Examples of critical simple games for every number of the 6th spectrum
C Maple’s Codes
C.1 Code for the 5th Spectrum
C.2 Code for the 6th Spectrum
References

GET THE COMPLETE PROJECT
Simple Games: Weightedness and Generalizations