Authors: Timotijević, Marinko
Živaljević, Rade 
Jevtić, Filip D. 
Affiliations: Mechanics 
Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: Polytopality of Simple Games
Journal: Experimental Mathematics
Issue Date: 1-Jan-2024
Rank: ~M22
ISSN: 1058-6458
DOI: 10.1080/10586458.2024.2379802
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.
Keywords: Bier spheres | Generalized permutahedra | polytopal spheres | simple games | Steinitz problem
Publisher: Taylor & Francis
Project: cience Fund of the Republic of Serbia, Grant No. 7744592, Integrability and Extremal Problems in Mechanics, Geometry and Combinatorics - MEGIC.

Show full item record

Page view(s)

32
checked on Dec 13, 2024

Google ScholarTM

Check

Altmetric

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.