Simple games with minimum

Dani Samaniego; Sascha Kurz

REVIEW 3 major objections 3 minor 26 references

Simple games with minimum

T0 review · 3 major / 3 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves closed formulas for the number of non-isomorphic simple games with a unique minimal winning vector, and shows that their dimension is t, t-1, max(t-1,1), or max(t-2,1) depending on null and veto players.

desk verdict New enumeration and dimension results for simple games with a unique minimal winning vector; the results look right, but the parameterization definition and one proof need tightening. read the letter →

arxiv 2501.18966 v1 pith:BBCDYUCB submitted 2025-01-31 math.CO

Sascha Kurz , Dani Samaniego This is my paper · ORCID

classification math.CO MSC 05A1591A12

keywords simplegameswithminimumuniqueminimalwinningvectormonotoneBooleanfunctionsgeneratingPólyaenumerationtheoremdimensionofweightednullandvetoplayers

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Every simple game is a monotone yes/no rule on coalitions of players, and counting all of them up to renaming the players is an open problem. This paper carves out the subclass with a unique minimal winning vector, called simple games with minimum, and proves closed formulas for the number of non-isomorphic such games with $n$ players. The count is made by representing each game by its desirability-equivalence class sizes $\mathbf n=(n_1,\dots,n_t)$ and its single minimal winning vector $\mathbf m=(m_1,\dots,m_t)$, then using generating functions and Pólya's enumeration theorem to remove class permutations. The same representation yields a dimension theorem: such a game is the intersection of exactly $t$, $t-1$, $\max(t-1,1)$, or $\max(t-2,1)$ weighted majority games, depending on whether null players (never decisive) or veto players (needed for every win) are present. If the formulas hold, this voting-game family is exactly counted and dimensionally classified for every $n$.

What carries the argument

The carrying object is the proper representation $(\mathbf n,\mathbf m)$: $\mathbf n=(n_1,\dots,n_t)$ lists the sizes of the $t$ equivalence classes of players under the desirability relation, and $\mathbf m=(m_1,\dots,m_t)$ records the unique minimal winning vector, normalized lexicographically so that isomorphic games share one pair. The counting machinery is Pólya's enumeration theorem on the symmetric group $S_t$: the single-class generating function $g(x)=x^2/(1-x)^2$ is symmetrized through $g(x^k)$ terms, and the coefficient of $x^n$ in the resulting series is $\mathrm{SG}_{\neg v,\neg n}(n,t,1)$. Null and veto players are added afterward as extra singleton classes following Theorem 3.14. The dimension lower bound is forced by pairs of losing coalitions whose voter exchanges produce winning coalitions, proving that the corresponding weighted factors cannot be merged.

What would settle it

Enumerate, for $n\le 8$, all pairs of a class-size vector $\mathbf n$ and a single vector $\mathbf m$ with $0\le m_i\le n_i$, form the simple game whose winning coalitions are exactly the supersets of coalitions with composition $\mathbf m$, quotient by all player permutations, and compare the number of isomorphism classes with $\mathrm{SG}(n,1)$ in Table 2. A mismatch would identify a missing or duplicated class in the orbit-counting enumeration.

Watch

Extended reading notes

Core claim

The central result is an exact enumeration and a dimension classification. Theorem 3.11 gives $\mathrm{SG}_{\neg v,\neg n}(n,t,1)$, the number of non-isomorphic one-minimal-winning-vector games with no null or veto players, as a finite sum over integer compositions $j_1+2j_2+\cdots+tj_t=t$ of a convolution of binomial coefficients; Theorem 3.14 builds all games from these by appending one null class, one veto class, or both, yielding closed formulas for $\mathrm{SG}(n,t,1)$, and Theorem 3.16 sums over $t\le \lfloor n/2\rfloor+1$ to get $\mathrm{SG}(n,1)$. The dimension theorems state that the minimum number of weighted games whose intersection gives the game is $t$ with no null or veto players, $t-1$ with nulls but no vetoes, $\max(t-1,1)$ with vetoes but no nulls, and $\max(t-2,1)$ with both. Table 2 lists the resulting counts for $n\le 20$.

Load-bearing premise

The formulas assume that every isomorphism class is counted exactly once by the normalized pairs $(\mathbf n,\mathbf m)$, and that a game with null or veto players always arises from a smaller no-null/no-veto game by adding at most one null class and at most one veto class; if two null classes or two veto classes could appear separately in one game, the total count would miss those games.

Editorial extensions

If this is right

For every $n$, the total number $\mathrm{SG}(n,1)$ can be computed exactly without enumerating monotone Boolean functions; the paper's Table 2 already gives values up to $n=20$.
Every game in the class has an explicit representation as an intersection of at most $t$ weighted games, and the null/veto profile tells exactly whether $t$, $t-1$, $\max(t-1,1)$, or $\max(t-2,1)$ factors are needed.
The bound $t\le \lfloor n/2\rfloor+1$ makes Theorem 3.16 a finite sum, so the formulas apply for arbitrarily large $n$ without new computation beyond the summing.
The recursive formula in Corollary 3.12 reduces the symbolic generating-function work to a dynamic program in $n$ and $t$, so low-$t$ counts are easy to produce.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Because each fixed-$t$ generating function is rational, the counts $\mathrm{SG}(n,t,1)$ are quasi-polynomial in $n$; this is an immediate consequence of the formulas even though the paper does not single it out.
The same parameterization and orbit-counting setup should extend to two or more minimal winning vectors; the paper identifies the rapid growth of the number of minimal winning vectors, not the enumeration method, as the bottleneck.
One could test the dimension theorem directly by computing the dimension of random games in the class with a standard integer-programming formulation and checking the results against the null/veto profile.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Sunny summary: this paper does something real. It gives a closed formula for the number of isomorphism classes of simple games with a unique minimal winning vector, for every number of players and every number of equivalence classes, plus a complete dimension characterization. The enumeration matches earlier special cases and the new values in Table 2 are internally consistent. The dimension proofs (Theorems 4.1–4.4) are clean and convincing; the lower-bound argument with pairs of losing coalitions is particularly nice.

The real weakness is in the parameterization. Definition 2.3, as stated, omits the condition that the N_i are the actual maximal desirability classes. So Remark 2.4 is false: there are pairs satisfying (a)–(c) that do not describe a game with t classes. The example n=(4,3,2), M=(0,0,1) with two null classes is a genuine counterexample. (The stress-test's other example, n=(2,2), M=(1,1), is actually a valid two-class game, so it doesn't land.) Relatedly, the proof of Theorem 3.14 splits into four categories but never proves the key structural fact that null players form at most one equivalence class and veto players form at most one equivalence class. That fact is true for simple games, but it is doing real work in the exhaustiveness of the split. Without it, the summation could in principle undercount or double-count.

I want to be clear that this is patchable, not fatal. The enumeration formulas are not obtained by naively counting the defective Definition 2.3; they build games from a no-null/no-veto base by adding at most one null class and at most one veto class, which is the right construction. The small cases check out. The missing lemma is a few lines. So the central results are very likely correct.

This paper deserves a serious referee. It provides the first exact counts for general t and the dimension for all games with minimum. A competent referee should ask for a corrected Definition 2.3 (citing the full conditions in [17]) and a proof of the null/veto class lemma. After that, I'd be happy with it. Bring it to a reading group if the group likes enumeration or voting theory.

Referee Report

3 major / 3 minor

Summary. The paper studies simple games (monotone Boolean functions) that have a unique minimal winning vector, called simple games with minimum. Building on a pair parameterization (n, M) of non-isomorphic simple games from the authors' earlier paper [17], it derives formulas for the number SG(n, t, 1) of such games with n players and t desirability-equivalence classes, sums these over t to obtain SG(n, 1), and gives dimension formulas: dimension is t, t-1, max(t-1,1), or max(t-2,1) depending on the presence of null and veto players (Theorems 4.1-4.4). Table 2 lists SG(n, t, 1) for n up to 20.

Significance. If the foundational issues are repaired, the paper is a meaningful contribution to the exact enumeration of monotone Boolean functions up to isomorphism: it gives a closed-form enumeration of an infinite family, not merely computational values, and it provides a complete dimension formula for that family. The enumeration uses Pólya's theorem and generating functions in a reproducible way, and the dimension results are proven from the definitions rather than fitted to data. I checked several small parameter ranges and found the formulas in Theorems 3.14 and 3.11 consistent with the nontrivial rows of Table 2. The main obstacle is that the formal definition of the counting object is currently incomplete, which affects the rigor of the central enumeration claim.

major comments (3)

[Definition 2.3 and Remark 2.4] Definition 2.3, as written, does not require the classes N_i to be the maximal equivalence classes of the desirability relation, and Remark 2.4 is therefore not a consequence of Theorem 1 of [17] unless the missing maximality condition from the original definition is included. A concrete counterexample is n=(4,3,2) with M=(0,0,1): this pair satisfies conditions (a)-(c), but the two classes with m_i=0 are both null classes, and all null players are desirability-equivalent, so the game actually has two equivalence classes, not three. Counting all solutions of Definition 2.3 would therefore overcount configurations of this kind. Since SG(n,t,1) is defined as the number of such solutions, the object being counted is not the stated class of games with exactly t equivalence classes.
[Theorem 3.14] The exhaustiveness of the four-case split in the proof of Theorem 3.14 assumes that every simple game with minimum has at most one null equivalence class and at most one veto equivalence class. This structural fact is true (null players are all mutually equally desirable because their entries in M vanish, and veto players are all mutually equally desirable because every winning coalition contains all of them), but it is neither stated nor proved in the paper. Without this lemma, the case split could undercount games with several null or veto classes, and the same omission is needed in Proposition 3.4(b) for the bound t <= floor(n/2)+1. The lemma should be stated and proved before Theorem 3.14.
[Table 2] Table 2 contains an internal inconsistency whose source appears to be the defective Definition 2.3: for n=3, t=3 the table reports SG(3,3,1)=1, whereas Theorem 3.14 and Proposition 3.4 give SG(3,3,1)=0. The extra configuration is exactly the non-proper pair with two null classes discussed above. The authors should regenerate Table 2 from a single, corrected definition and ensure that the table, Definition 2.3, and Theorem 3.14 all refer to the same counting object.

minor comments (3)

[Theorem 3.11] The binomial coefficient in the convolution is typeset ambiguously as "n-k / k"; it should read n/k - 1, matching Proposition 3.9 and Corollary 3.12.
[Proposition 3.9] In the proof of Proposition 3.9, the line displaying g(x^a) is missing the indicator function and uses an inconsistent variable n'; rewriting this step with n' and the divisibility condition explicitly would avoid confusion.
[Theorem 4.3] In the lower-bound part of the proof of Theorem 4.3, the phrase "for each 1 <= 2 < j <= t" appears to be a typo for "for each 2 <= i < j <= t"; please correct it.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the enumeration and dimension results derive from an independent published parameterization and self-contained combinatorial and weighted-game arguments; the only flagged issue is a non-circular rigor gap in Definition 2.3.

full rationale

The paper's central enumeration (Theorem 3.14) is obtained by taking the no-null/no-veto count SG¬v,¬n(n,t,1), whose generating function is derived via Pólya's enumeration theorem from g(x)^t, and adding at most one null class, one veto class, or one of each. This is a structural decomposition rather than a reuse of the target quantity SG(n,t,1); the terms SG¬v,¬n(n-i,t-1,1) involve strictly smaller class counts and are not the same as the quantity being computed. The parameterization of simple games by pairs (n,M) is imported from Theorem 1 of [17]; although [17] is by the same authors, it is a separate published theorem with its own proof and is parameter-free with stated assumptions, so under the review rules it counts as independent support rather than circularity. The dimension results (Theorems 4.1-4.4) are proved by explicit weighted-game intersections for upper bounds and by constructing losing-coalition pairs for lower bounds, so they do not presuppose the enumerations. No quantity is fitted to data and no prediction is a renamed input. One non-circular rigor issue should be noted: Definition 2.3 omits the maximality requirement for equivalence classes, so pairs such as n=(3,2,1), M=(0,0,1) satisfy (a)-(c) while containing two null classes, and the proof of Theorem 3.14 does not explicitly justify that null and veto players each form at most one class. This is a completeness/correctness gap in the written proof, not an equivalence-by-construction, and therefore does not raise the circularity score.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces no free parameters and no new physical or combinatorial entities. Its axiomatic load consists of standard theorems (Pólya enumeration, binomial identities) and the prior parameterization from the authors' earlier work, plus the structural fact that all null players are equivalent and all veto players are equivalent.

assumptions (4)

standard math Pólya's Enumeration Theorem
Used in Section 3 (equations (5) and (6)) to count orbits of equivalence class labels under permutations.
domain assumption Parameterization theorem from [17]
Theorem 1 of [17] states that every simple game is uniquely represented by a pair (n,M) up to isomorphism; used throughout Section 3, cited at Definition 2.3 and Remark 2.4.
domain assumption Null players form a single equivalence class; veto players form a single equivalence class.
Used in Theorem 3.14 to decompose games by adding one null class and one veto class; not proved in this paper, follows from the desirability relation.
standard math Chu-Vandermonde identity
Used in the proof of Proposition 3.5.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Simple games with minimum." pith.science (2026). https://pith.science/paper/BBCDYUCB

@misc{pith2026250118966,
  author       = {Pith},
  title        = {Pith review of: Simple games with minimum},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BBCDYUCB}},
  note         = {Machine review of arXiv:2501.18966}
}

read the original abstract

Every simple game is a monotone Boolean function. For the other direction we just have to exclude the two constant functions. The enumeration of monotone Boolean functions with distinguishable variables is also known as the Dedekind's problem. The corresponding number for nine variables was determined just recently by two disjoint research groups. Considering permutations of the variables as symmetries we can also speak about non-equivalent monotone Boolean functions (or simple games). Here we consider simple games with minimum, i.e., simple games with a unique minimal winning vector. A closed formula for the number of such games is found as well as its dimension in terms of the number of players and equivalence classes of players.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

[17]

Enumeration of simple g ames with two equivalence classes of players

Sascha Kurz and Dani Samaniego. Enumeration of simple g ames with two equivalence classes of players. Discrete Applied Mathematics, 334:26–35, 2023

work page 2023
[1]

Complete simple ga mes

Francesc Carreras and Josep Freixas. Complete simple ga mes. Mathematical Social Sciences, 32(2):139–155, 1996

work page 1996
[2]

Article 1, Section 3

US Constitution. Article 1, Section 3. https://constitution.congress.gov/browse/article-1/ section [Online; accessed 28-December-2024]

work page 2024
[3]

¨Uber Zerlegungen von Zahlen durch ihre gr¨ oßten gemeinsame n Teiler

Richard Dedekind. ¨Uber Zerlegungen von Zahlen durch ihre gr¨ oßten gemeinsame n Teiler. Gesammelte Werkey, 2:103–148, 1897

work page
[4]

The dimension for the european union coun cil under the nice rules

Josep Freixas. The dimension for the european union coun cil under the nice rules. European Journal of Operational Research, 156(2):415–419, 2004

work page 2004
[5]

The golden number and ﬁbon acci sequences in the design of voting structures

Josep Freixas and Sascha Kurz. The golden number and ﬁbon acci sequences in the design of voting structures. European Journal of Operational Research, 226(2):246–257, 2013

work page 2013
[6]

Enumeration of weighted g ames with minimum and an analysis of voting power for bipartite complete games with minimum

Josep Freixas and Sascha Kurz. Enumeration of weighted g ames with minimum and an analysis of voting power for bipartite complete games with minimum. Annals of Operations Research, 222(1):317–339, 2014

work page 2014
[7]

Weighted games witho ut a unique minimal representation in integers

Josep Freixas and Xavier Molinero. Weighted games witho ut a unique minimal representation in integers. Optimization Methods & Software, 25:203–215, 2010

work page 2010

Show all 26 references

[8]

Com plete voting systems with two classes of voters: weightedness and counting

Josep Freixas, Xavier Molinero, and Salvador Roura. Com plete voting systems with two classes of voters: weightedness and counting. Annals of Operations Research, 193(1):273–289, 2012. 15

2012
[9]

On anonymous and weig hted voting systems

Josep Freixas and Montserrat Pons. On anonymous and weig hted voting systems. Theory and Decision , 91:1–15, 2021

2021
[10]

Dimension of co mplete simple games with minimum

Josep Freixas and Mar´ ıa Albina Puente. Dimension of co mplete simple games with minimum. European Journal of Operational Research, 188(2):555–568, 2008

2008
[11]

On the enumeration of bipartite simple games

Josep Freixas and Dani Samaniego. On the enumeration of bipartite simple games. Discrete Applied Mathe- matics, 297:129–141, 2021

2021
[12]

The legislative branch

The White House. The legislative branch. https://www.whitehouse.gov/about-the-white-house/ou r-gov [Online; accessed 28-December-2024]

2024
[13]

John R. Isbell. A class of simple games. Duke Mathematical Journal, 25(3):423–439, 1958

1958
[14]

A computation of the ninth Dedekind n umber

Christian J¨ akel. A computation of the ninth Dedekind n umber. Journal of Computational Algebra , 6- 7:100006, 2023

2023
[15]

Directed and weigh ted majority games

Ingomar Krohn and Peter Sudh¨ olter. Directed and weigh ted majority games. Zeitschrift f ¨ur Operations Research, 42(2):189–216, 1995

1995
[16]

Dimension of the Lisbon vo ting rules in the EU Council: a challenge and new world record

Sascha Kurz and Stefan Napel. Dimension of the Lisbon vo ting rules in the EU Council: a challenge and new world record. Optimization Letters, 10(6):1245–1256, August 2016

2016
[18]

On Dedekind’s prob lem for complete simple games

Sascha Kurz and Nikolas Tautenhahn. On Dedekind’s prob lem for complete simple games. International Journal of Game Theory , 42(2):411–437, 2013

2013
[19]

On the number of inequivalent mon otone Boolean functions of 9 variables

Bartłomiej Pawelski. On the number of inequivalent mon otone Boolean functions of 9 variables. IEEE Transactions on Information Theory, 70(7):5358–5364, 2024

2024
[20]

Kombinatorische Anzahlbestimmungen f ¨ ur Gruppen, Graphen und chemische Verbindungen

George P´ olya. Kombinatorische Anzahlbestimmungen f ¨ ur Gruppen, Graphen und chemische Verbindungen. Acta Mathematica, 68(1):145–254, December 1937

1937
[21]

George P´ olya and R. C. H Read. Combinatorial enumeration of groups, graphs, and chemical compounds. Springer-V erlag, Berlin, Heidelberg, 1987

1987
[22]

Howard Redﬁeld

J. Howard Redﬁeld. The theory of group-reduced distrib utions. American Journal of Mathematics, 49(3):433– 455, 1927

1927
[23]

Alan Taylor and William S. Zwicker. A characterization of weighted voting. Proceedings of the American mathematical society, 115:1089–1094, 1992

1992
[24]

Taylor and William S

Alan D. Taylor and William S. Zwicker. Simple Games: Desirability Relations, Trading, Pseudowei ghtings. Princeton University Press, 1999

1999
[25]

A computation of the ninth Dedek ind number using FPGA supercomputing

Lennart V an Hirtum, Patrick De Causmaecker, Jens Goema ere, Tobias Kenter, Heinrich Riebler, Michael Lass, and Christian Plessl. A computation of the ninth Dedek ind number using FPGA supercomputing. Association for Computing Machinery , 17(3), 2024

2024
[26]

Cycle index

Wikipedia. Cycle index. https://en.wikipedia.org/wiki/Cycle_index. [Online; accessed 28-December-2024]. 16

2024

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.

[1] [17]

Enumeration of simple g ames with two equivalence classes of players

Sascha Kurz and Dani Samaniego. Enumeration of simple g ames with two equivalence classes of players. Discrete Applied Mathematics, 334:26–35, 2023

work page 2023

[2] [1]

Complete simple ga mes

Francesc Carreras and Josep Freixas. Complete simple ga mes. Mathematical Social Sciences, 32(2):139–155, 1996

work page 1996

[3] [2]

Article 1, Section 3

US Constitution. Article 1, Section 3. https://constitution.congress.gov/browse/article-1/ section [Online; accessed 28-December-2024]

work page 2024

[4] [3]

¨Uber Zerlegungen von Zahlen durch ihre gr¨ oßten gemeinsame n Teiler

Richard Dedekind. ¨Uber Zerlegungen von Zahlen durch ihre gr¨ oßten gemeinsame n Teiler. Gesammelte Werkey, 2:103–148, 1897

work page

[5] [4]

The dimension for the european union coun cil under the nice rules

Josep Freixas. The dimension for the european union coun cil under the nice rules. European Journal of Operational Research, 156(2):415–419, 2004

work page 2004

[6] [5]

The golden number and ﬁbon acci sequences in the design of voting structures

Josep Freixas and Sascha Kurz. The golden number and ﬁbon acci sequences in the design of voting structures. European Journal of Operational Research, 226(2):246–257, 2013

work page 2013

[7] [6]

Enumeration of weighted g ames with minimum and an analysis of voting power for bipartite complete games with minimum

Josep Freixas and Sascha Kurz. Enumeration of weighted g ames with minimum and an analysis of voting power for bipartite complete games with minimum. Annals of Operations Research, 222(1):317–339, 2014

work page 2014

[8] [7]

Weighted games witho ut a unique minimal representation in integers

Josep Freixas and Xavier Molinero. Weighted games witho ut a unique minimal representation in integers. Optimization Methods & Software, 25:203–215, 2010

work page 2010