Polytopality of Simple Games

Abstract

The Bier sphere Bier(G) = Bier(K) := K ⋆∆ K◦ and the canonical fan F an(Γ) = F an(K) are combinatorial and geometric companions of a simple game G = (P, Γ) where P is the set of players, Γ ⊆ 2P is the set of wining coalitions, and K = 2P \ Γ 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 G are polytopal (canonically polytopal) in the sense that the corresponding Bier sphere Bier(G) (fan F an(Γ)) 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 and show that simple games such that Bier(G) is nonpolytopal do not exist in dimension 3. The results are obtained with Marinko Timotijević and Rade Živaljević, and are part of authors’ continued work on the topic of Bier spheres.