On Dedekind’s problem for complete simple games

On Dedekind’s problem for complete simple games

0.00 Avg rating0 Votes
Article ID: iaor20133011
Volume: 42
Issue: 2
Start Page Number: 411
End Page Number: 437
Publication Date: May 2013
Journal: International Journal of Game Theory
Authors: ,
Keywords: programming: integer
Abstract:

We state an integer linear programming formulation for the unique characterization of complete simple games, i.e. a special subclass of monotone Boolean functions. In order to apply the parametric Barvinok algorithm to obtain enumeration formulas for these discrete objects we provide a tailored decomposition of the integer programming formulation into a finite list of suitably chosen sub‐cases. As for the original enumeration problem of Dedekind on Boolean functions we have to introduce some parameters to be able to derive exact formulas for small parameters. Recently, Freixas et al. have proven an enumeration formula for complete simple games with two types of voters. We will provide a shorter proof and a new enumeration formula for complete simple games with two minimal winning vectors.

Reviews

Required fields are marked *. Your email address will not be published.