ABSTRACT (original article): The Bier sphere and the canonical fan are combinatorial/geometric companions of a simple game (equivalently the associated simplicial complex K), where P is the set of players, is the set of wining coalitions, and is the simplicial complex of losing coalitions. We propose and study a general “Steinitz problem” for simple games as the problem of characterizing which games are polytopal (canonically polytopal) in the sense that the corresponding Bier sphere (fan ) can be realized as the boundary sphere (normal fan) of a convex polytope. We characterize (roughly) weighted majority games as the games which are canonically (pseudo) polytopal (Theorems 1.1 and 1.2) and show, by an experimental/theoretical argument (Theorem 1.4), that simple games such that is nonpolytopal do not exist in dimension 3. This should be compared to the fact that asymptotically almost all simple games are nonpolytopal and a challenging open problem is to find a nonpolytopal simple game with the smallest number of players. CITATION (original article): Timotijević, M. Ž., Živaljević, R. T., & Jevtić, F. D. (2024). Polytopality of Simple Games. Experimental Mathematics, 1–14. https://doi.org/10.1080/10586458.2024.2379802
Bier()=Bier(K):=
◦
K∗△K
Fan(Γ)=Fan(K)
=(P,Γ)
Γ⊆
P
2
K:=∖Γ
P
2
Bier()
Fan(Γ)
Γ
Bier()
Algorithm for constructing convex geometric realizations of Bier spheres
Algorithm for constructing convex geometric realizations of Bier spheres
The algorithm is obtained from simplicial complexes (simple games) on 5 vertexes (players).
The presented algorithm is described in detail in Section 4 of the paper:
(1) M. Ž. Timotijević, R. T. Živaljević, F. D. Jeftić, Polytopality of Simple Games, Experimental Mathematics, 1-14. (2024)
https://doi.org/10.1080/10586458.2024.2379802
It represents a solution of The algorithmic Steinitz problem for special class of polytopes arising from Topological combinatorics and Game theory.
Input for the algorithm is a list Comp5.MX of all non isomorphic simplicial complexes with vertexes [n]={1,2,3,4,5}. The file Comp5.MX should be in the folder where this notebook is located and can be downloaded using the address: https://imi.pmf.kg.ac.rs/pub/m_timotijevic/Comp5.MX
Function ThrQ[K,n] returns False if the simplicial complex K in tne ambient [n] is not threshold and True with appropriate probability measure and a threshold otherwise.
Functions Maximal[K] and Dual[K] return the set of maximal simplexes of a complex K and its Alexander dual in the ambient [n].
(1) M. Ž. Timotijević, R. T. Živaljević, F. D. Jeftić, Polytopality of Simple Games, Experimental Mathematics, 1-14. (2024)
https://doi.org/10.1080/10586458.2024.2379802
It represents a solution of The algorithmic Steinitz problem for special class of polytopes arising from Topological combinatorics and Game theory.
Input for the algorithm is a list Comp5.MX of all non isomorphic simplicial complexes with vertexes [n]={1,2,3,4,5}. The file Comp5.MX should be in the folder where this notebook is located and can be downloaded using the address: https://imi.pmf.kg.ac.rs/pub/m_timotijevic/Comp5.MX
Function ThrQ[K,n] returns False if the simplicial complex K in tne ambient [n] is not threshold and True with appropriate probability measure and a threshold otherwise.
Functions Maximal[K] and Dual[K] return the set of maximal simplexes of a complex K and its Alexander dual in the ambient [n].
Maximal[A_]:=Module[{B,n,G},B=Sort[A];n=Length[B];G={};While[Length[B]>0,G=Union[G,{B[[n]]}];B=Complement[B,Subsets[B[[n]]]];n=Length[B]];Sort[G]]Dual[A_,n_]:=Module[{a111,d111,V111},a111=Complement[Subsets[Table[i,{i,1,n}]],K];d111=Length[a111];V111=Table[k,{k,1,n}];Table[Complement[V111,a111[[i]]],{i,d111,1,-1}]]ThrQ[K_,n_]:=Module[{A,x,Vertices,Gl,d,Vec,Var,p0,poz,term,neqGl,res,com,dual,nejednakosti,t,a1},Vertices=Table[i,{i,1,n}];Gl=Maximal[K];d=Length[Gl];Vec=Table[If[MemberQ[Gl[[i]],j],1,0],{i,1,d},{j,1,n}];Var=Table[,{i,1,n}];p0=True;poz=Table[p0=p0&&Var[[i]]>0,{i,1,n}][[n]];term=Sum[Var[[i]],{i,1,n}]1;neqGl=Table[term=term&&Dot[Vec[[i]],Var]<a1,{i,1,d}][[d]];dual=Dual[K,n];Gl=Maximal[dual];d=Length[Gl];com=Table[Complement[Vertices,Gl[[i]]],{i,1,d}];term=neqGl;Vec=Table[If[MemberQ[com[[i]],j],1,0],{i,1,d},{j,1,n}];nejednakosti=If[d0,term,Table[term=term&&Dot[Vec[[i]],Var]>a1,{i,1,d}][[d]]];res=Minimize[{a1,nejednakosti&&poz},Join[Var,{a1}]][[2]];t=a1/.res[[n+1]];If[NumberQ[t],{True,{Table[/.res[[i]],{i,1,n}],a1/.res[[n+1]]}},{False,{}}]]
x
i
x
i
Below is a code that generates the list NonThr of all non-threshold complexes and Thr of all Thr ones. Returns the number of non threshold and the number of threshold complexes.
This algorithm works for simplicial complexes on 5 vertexes in ambients n=5 and n=6 (simply replace n=5 with n=6 in the next cell).
This algorithm works for simplicial complexes on 5 vertexes in ambients n=5 and n=6 (simply replace n=5 with n=6 in the next cell).
n=5;SetDirectory[NotebookDirectory[]]W=Import["Comp5.MX"];NonThr={};Thr={};For[i=1,i<=Length[W],i++,K=W[[i]];Test=ThrQ[K,n];If[Test[[1]]False,NonThr=Union[NonThr,{K}],Thr=Union[Thr,{K}]]]Length[NonThr]Length[Thr]
Function FixMeasure[K,n] generates a probability measure and a threshold suitable for the construction of geometrical realizations of the Bier spheres of threshold complexes described Section 2 of the paper
(2) F. Jeftić, M. Timotijević, R. Živaljević, Polytopal Bier Spheres and Kantorovich-Rubinstein Polytopes of Weighted Cycles, Descrete and Computational Geometry. 63-4 (2021) , 1275 - 1286
The appropriate data is stored on the list Measures and the subsequent loop generates a list REALIZATIONS of coordinates of Bier spheres of simplicial complexes on the list Thr.
Following cell has to be executed twice.
(2) F. Jeftić, M. Timotijević, R. Živaljević, Polytopal Bier Spheres and Kantorovich-Rubinstein Polytopes of Weighted Cycles, Descrete and Computational Geometry. 63-4 (2021) , 1275 - 1286
The appropriate data is stored on the list Measures and the subsequent loop generates a list REALIZATIONS of coordinates of Bier spheres of simplicial complexes on the list Thr.
Following cell has to be executed twice.
FixMeasure[K_,n_]:=Module{q,A,x,Vertices,Gl,d,Vec,Var,p0,poz,term,neqGl,res,com,dual,nejednakosti,t,a},Vertices=Table[i,{i,1,n}];Gl=Maximal[K];d=Length[Gl];Vec=Table[If[MemberQ[Gl[[i]],j],1,0],{i,1,d},{j,1,n}];Var=Table[,{i,1,n}];p0=True;poz=Tablep0=p0&&Var[[i]]≥,{i,1,n}[[n]];term=Sum[Var[[i]],{i,1,n}]1;neqGl=Tableterm=term&&Dot[Vec[[i]],Var]<=a-,{i,1,d}[[d]];dual=Dual[K,n];Gl=Maximal[dual];d=Length[Gl];com=Table[Complement[Vertices,Gl[[i]]],{i,1,d}];term=neqGl;Vec=Table[If[MemberQ[com[[i]],j],1,0],{i,1,d},{j,1,n}];nejednakosti=Ifd0,term,Tableterm=term&&Dot[Vec[[i]],Var]>=a+,{i,1,d}[[d]];res=Maximize[{1,nejednakosti&&poz},Join[Var,{a}]][[2]];{Table[/.res[[i]],{i,1,n}],a/.res[[n+1]]}Measures=Table[FixMeasure[Thr[[i]],n],{i,1,Length[Thr]}];REALIZATIONS={};Fori=1,i≤Length[Thr],i++,K=Thr[[i]];Mi=Measures[[i]][[1]];threshold=Measures[[i]][[2]];Base=Join[Table[If[ij,1,0],{i,1,n-1},{j,1,n-1}],{Table[-1,{i,1,n-1}]}];VerticesK=Table[Base[[i]]/Mi[[i]],{i,1,n}];a=;VerticesDK=-aVerticesK;Vertices=Join[VerticesK,VerticesDK];REALIZATIONS=Join[REALIZATIONS,{Vertices}]
x
i
1
10^2
1
10^2
1
10^2
x
i
1-threshold
threshold
Function Bier[K,n] generates the bier sphere of a complex K in the ambient [n].
Function PolytopalQ[K,V] returns {1} or {-1} if a triangulation of a sphere described with abstract simplicial complex K and vertexes on the list V is polytopal and {-1,1} otherwise. Function PolytopalQ[K,V] needs all maximal simplexes of the sphere to be properly oriented, hence the function Orient[K].
Function PolytopalQ[K,V] returns {1} or {-1} if a triangulation of a sphere described with abstract simplicial complex K and vertexes on the list V is polytopal and {-1,1} otherwise. Function PolytopalQ[K,V] needs all maximal simplexes of the sphere to be properly oriented, hence the function Orient[K].
Bier[K_,n_]:=Module[{L,k1,k2,i,j,Sp},L=Dual[K,n];k1=Length[K];k2=Length[L];Sp={};For[i=1,i<k1+1,i++,For[j=1,j<k2+1,j++,If[Intersection[K[[i]],L[[j]]]{},Sp=Union[Sp,{Union[K[[i]],n+L[[j]]]}]]]];Sp]Orient[K_]:=Module[{L,k,d,Orijentisan,i,j,A,l,B,pr,ia,iia,c,a,IndA,IndB,Novi},L=K;k=Length[K];d=Length[K[[1]]];Orijentisan={L[[1]]};L=Complement[L,{L[[1]]}];For[i=1,i<k,i++,j=1;While[j≤k-i,A=L[[j]];l=1;While[l≤i,B=Orijentisan[[l]];pr=Intersection[A,B];If[Length[pr]d-1,Break[],l=l+1]];If[l==i+1,j=j+1,Break[]]];ia=Complement[A,pr][[1]];iia=Flatten[Position[A,ia]][[1]];c=0;a=Table[If[iiia,c=1];A[[i+c]],{i,1,d-1}];IndA=Signature[a](-1)^iia;ia=Complement[B,pr][[1]];iia=Flatten[Position[B,ia]][[1]];c=0;a=Table[If[iiia,c=1];B[[i+c]],{i,1,d-1}];IndB=Signature[a](-1)^iia;If[IndA*IndB-1,Novi=A,Novi=Join[{A[[2]],A[[1]]},Table[A[[i]],{i,3,d}]]];Orijentisan=Join[Orijentisan,{Novi}];L=Complement[L,{A}]];Orijentisan]PolytopalQ[K_,Vertices_]:=Module[{L,n,A,Ac,i,p,q,j,X,x,Mat,vrsta},L=Maximal[K];n=Length[L[[1]]];L=Orient[L];Mat={};For[q=1,q≤Length[L],q++,A=Vertices[[L[[q]]]];Ac=Complement[Vertices,A];vrsta={};For[p=1,p<=Length[Ac],p++,X=Ac[[p]];x=Sign[Det[Join[Table[Join[A[[i]],{1}],{i,1,n}],{Join[X,{1}]}]]];vrsta=Join[vrsta,{x}];];Mat=Join[Mat,{vrsta}]];{MatrixForm[Mat],Complement[Union[Flatten[Mat]],{0}]}]
Final loop of the algorithm generates the lists GeoRealized and gVertices of coordinates of the complexes of the list NonThr and coordinates of geometrical realizations of their Bier spheres by solving the system (4.1) from the paper (1).
The code prints the index of a non threshold complex and status of the attempted realization indicated by the function PolytopalQ.
The code prints the index of a non threshold complex and status of the attempted realization indicated by the function PolytopalQ.
Maximal simplexes of non-threshold simplicial complexes and coordinates of convex realizations
Maximal simplexes of non-threshold simplicial complexes and coordinates of convex realizations
Maximal simplexes of non-threshold simplicial complexes on 5-vertexes and coordinates of convex realizations of their 3-dimensional 10-vertex Bier spheres obtained by the algorithm
File containing the list of presented realizations can be downloaded at the address below: https://imi.pmf.kg.ac.rs/pub/m_timotijevic/Bier_Kv5_d3.nb
Sample of the presented realizations found in the notebook:
Maximal simplexes of non-threshold simplicial complexes on 5-vertexes and coordinates of convex realizations of their 4-dimensional 11-vertex Bier spheres obtained by the algorithm
File containing the list of presented realizations can be downloaded at the address: https://imi.pmf.kg.ac.rs/pub/m_timotijevic/Bier_Kv5_d4.nb
Sample of the presented realizations found in the notebook:
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Polytopality of simple games
by Marinko Ž. Timotijević, Rade T. Živaljević & Filip D. Jevtić
Wolfram Community, STAFF PICKS, September 10, 2024
https://community.wolfram.com/groups/-/m/t/3271465
by Marinko Ž. Timotijević, Rade T. Živaljević & Filip D. Jevtić
Wolfram Community, STAFF PICKS, September 10, 2024
https://community.wolfram.com/groups/-/m/t/3271465