2016/09/16 by Martin Olsen, Olsen, Martin
Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Game Theory and Applications #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.1609.04960
Consider a situation with n agents or players where some of the players form a coalition with a certain collective objective. Simple games are used to model systems that can decide whether coalitions are successful (winning) or not (losing). A simple game can be viewed as a monotone boolean function. The dimension of a simple game is the smallest positive integer d such that the simple game can be expressed as the intersection of d threshold functions where each threshold function uses a threshold and n weights. Taylor and Zwicker have shown that d is bounded from above by the number of maximal losing coalitions. We present two new upper bounds both containing the Taylor/Zwicker-bound as a special case. The Taylor/Zwicker-bound imply an upper bound of n \choose n/2. We improve this upper bound significantly by showing constructively that d is bounded from above by the cardinality of any binary covering code with length n and covering radius 1. This result supplements a recent result where Olsen et al. showed how to construct simple games with dimension |C| for any binary constant weight SECDED code C with length n. Our result represents a major step in the attempt to close the dimensionality gap for simple games.