OEIS A132183 · regular Boolean functions · complete simple games

Ranked Voting Rules

A committee votes yes or no, and its members are ranked from strongest to weakest. A voting rule says which groups of yes-voters pass a motion. A rule is regular if a winning group stays winning when it gains a member, and when a member is swapped for a stronger one. The sequence counts these rules: 2, 3, 5, 10, 27, 119, 1173, 44315, … and, new here, the values for 10 and 11 members.

Every rule is a cut through this diagram

Each box is a group of yes-voters (a coalition). The strongest member is the leftmost square. A line goes up from one coalition to another that is one step stronger: it gains the weakest member, or one member is replaced by the next stronger one.

Click a coalition to flip it. Everything above a winning coalition wins too, and everything below a losing one loses, so a regular rule is exactly a way to cut the diagram into a losing bottom and a winning top.

0winning coalitions
noself-dual
0regular rules for this size

Weakest winning coalitions

These few coalitions (thick outlines) pin down the whole rule. A rule is self-dual when a group wins exactly when the members left out of it would lose: no ties and no two disjoint winners.

winsloses

How the new terms were counted

For 9 members there are 284 billion rules, and in 2010 they were listed one by one. For 10 and 11 that is hopeless, so the rules have to be counted without being listed.

The diagram has a hidden product structure. Split off the two strongest members and it falls into four copies of the diagram for the remaining members, one for each way the top two can vote. The copies are tied together in a chain by two kinds of line.

the top two trade places: same coalition of the rest the strongest of the rest is promoted into the top two

A rule for the whole committee is then four smaller rules, one per copy, nested inside each other along the chain. Nested families can be counted with running totals over the list of small rules. With the top two split off, the 16,175,190 rules for 8 members give the count for 10. With the top four split off (sixteen copies), the 44,315 rules for 7 members give the count for 11 in a few minutes.

The numbers

The first column includes the two trivial rules (always pass, never pass); subtract 2 for the number of complete simple games. Self-dual counts are A109456; the same computation reproduces all of them, which is one of the checks. This page counted the rules for 2 to 6 members in your browser: . Method, proofs, programs and logs: oeis-results/A132183.