6
$\begingroup$

Taken from Wikipedeia:

A simple voting game, taken from Game Theory and Strategy by Phillip D. Straffin:

[6; 4, 3, 2, 1]

The numbers in the brackets mean a measure requires 6 votes to pass, and voter A can cast four votes, B three votes, C two, and D one. The winning groups, with bolded swing voters, are as follows:

AB, AC, ABC, ABD, ACD, BCD, ABCD

Using a non-trivial structure, we know that ABCD will always be a member of the set of winning groups. Also, we know that if AB is a winning group, then ABC and ABD are also winning groups. In other words, the set of winning groups AB, ABCD is invalid. Thus, any member of the set, besides ABCD, can be constructed by removing a single element from another set in the group. (Edit: While this is true, it gives the wrong impression.)

In the beginning, the goal was to generate the set of possible winning groups for a given number of players. Using three players as an example, the set of winning groups is:

{1, 2, 3}

{1, 2, 3}, {1, 2}
{1, 2, 3}, {1, 2}, {1}
{1, 2, 3}, {1, 2}, {2}
{1, 2, 3}, {1, 2}, {1}, {2}

{1, 2, 3}, {1, 3}
{1, 2, 3}, {1, 3}, {1}
{1, 2, 3}, {1, 3}, {3}
{1, 2, 3}, {1, 3}, {1}, {3}

{1, 2, 3}, {2, 3}
{1, 2, 3}, {2, 3}, {2}
{1, 2, 3}, {2, 3}, {3}
{1, 2, 3}, {2, 3}, {2}, {3}

{1, 2, 3}, {1, 2}, {1, 3}
{1, 2, 3}, {1, 2}, {1, 3}, {1}
{1, 2, 3}, {1, 2}, {1, 3}, {2}
{1, 2, 3}, {1, 2}, {1, 3}, {3}
{1, 2, 3}, {1, 2}, {1, 3}, {1}, {2}
{1, 2, 3}, {1, 2}, {1, 3}, {1}, {3}
{1, 2, 3}, {1, 2}, {1, 3}, {2}, {3}
{1, 2, 3}, {1, 2}, {1, 3}, {1}, {2}, {3}

# and so on...

This is doable through a relatively simple algorithm as thankfully offered here. (Edit: That algorithm does what was requested, but, per my oversight, generates false positives, e.g. {{1, 2}, {1, 3}, {1, 2, 3}, {1, 2, 3, 4}}.)

However, I want to only generate one set per "isomorphic group." For example, the sets {1, 2, 3}, {1, 2} and {1, 2, 3}, {1, 3} are the same if we swap the labels of 2 and 3. This is the primary goal.

The secondary goal is to only generate the sets of winning groups that could be realized through a voting structure. Using a four player system and a maximum of 20 votes per person, I found sets of winning groups that satisfied the above criteria, but could not be realized. (Edit: See previously mentioned false positives and the answer below.)

$\endgroup$
4
$\begingroup$

You are asking two questions:

  1. How to count "winning groups" up to isomorphism?

  2. Which winning groups are realizable as winning coalitions?

From the point of view of winning groups, we can assume that each voter always casts all her votes, and the resulting games is known as a weighted voting game.

Counting winning groups

Your concept of "winning group" is a same as a monotone Boolean function or an upset. The number of monotone Boolean functions up to permutation is enumerated in the sequence A003182, and grows pretty quickly. For $n=7$ the number is already pretty large: 490,013,148. It's probably not too helpful to list all of them. It is even non-trivial just to calculate the number, see this paper.

You can find all the 16351 non-constant monotone Boolean functions for $n=6$ listed here as sets of minterms, which are (in your parlance) minimal winning coalitions. The minterms form what is known as an antichain, a collection of sets none of which is a subset of another.

Which winning groups are achievable?

Let $S_1,S_2$ be two sets of voters. A swap consists of taking some $x \in S_1 \setminus S_2$ and some $y \in S_2 \setminus S_1$, and forming the new sets $S_1 - x + y, S_2 - y + x$ (that is, we exchange two voters, taking care not to have the same voter twice in any of the sets). Given several sets $S_1,\ldots,S_k$ of voters, a trade is the result of applying arbitrarily many swaps, resulting in a new $k$-tuple $T_1,\ldots,T_k$.

(Alternatively, $T_1,\ldots,T_k$ is a trade of $S_1,\ldots,S_k$ if the multisets $S_1 \cup \cdots \cup S_k$ and $T_1 \cup \cdots \cup T_k$ are the same.)

Let $W$ be a set of "winning coalitions". We say that $W$ is trade robust if whenever $S_1,\ldots,S_k \in W$, in any trade $T_1,\ldots,T_k$ obtained from $S_1,\ldots,S_k$ at least one of the $T_i$ is in $W$. It is easy to see that every set of winning coalitions arising from weighted voting games is trade robust (exercise). Amazingly, Taylor and Zwicker showed that the converse holds as well.

$\endgroup$
  • $\begingroup$ No, the only sets of winning groups which are achievable are those which are trade robust. That's what I state in the second part. $\endgroup$ – Yuval Filmus Mar 18 '16 at 17:33
  • $\begingroup$ The question I'm trying to ask is "For a given set of winning groups, does there exist a weighted voting game in which that set could arise?" To me, it doesn't make sense to think about whether a set is trade robust outside of the game it exists in. Am I missing something, or are we talking about two different questions? If we are talking about two different questions, I can update to include your question since trade robustness is interesting. $\endgroup$ – Jared Goguen Mar 18 '16 at 18:55
  • $\begingroup$ No, we're talking about the same question. A collection $W$ of winning sets is realizable as a weighted voting game iff it is closed upwards and trade robust. A single set isn't trade robust – it's the collection of all of them that should be trade robust. $\endgroup$ – Yuval Filmus Mar 18 '16 at 19:26
  • $\begingroup$ So, for example, {{1, 2}, {1, 3}, {1, 2, 3}} is trade robust because (i) we can't remove 1 from any set because there would be nowhere to add it, (ii) removing 2 or 3 from {1, 2, 3} would result in a trivial swap, (iii) the only remaining swap is {1, 2}, {1, 3} $\rightarrow$ {1, 3}, {1, 2} and this swap results in at least one set (in fact all) being a member of the original set? $\endgroup$ – Jared Goguen Mar 18 '16 at 19:46
  • $\begingroup$ Sounds reasonable. Indeed, this set can be realized by, for example, $w_1=3,w_2=w_3=1,T=4$. Note that all subsets of $W$ need to be trade robust. To make extra sure that you understand, you can take a look at Taylor and Zwicker's paper, or at their book. $\endgroup$ – Yuval Filmus Mar 18 '16 at 20:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.