Polytopality of Simple Games

Abstract

The Bier sphere (Formula presented.) and the canonical fan (Formula presented.) are combinatorial/geometric companions of a simple game (Formula presented.) (equivalently the associated simplicial complex K), where P is the set of players, (Formula presented.) is the set of wining coalitions, and (Formula presented.) 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 (Formula presented.) are polytopal (canonically polytopal) in the sense that the corresponding Bier sphere (Formula presented.) (fan (Formula presented.)) can be realized as the boundary sphere (normal fan) of a convex polytope. We characterize (roughly) weighted majority games as the games (Formula presented.) 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 (Formula presented.) 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.