# Voting games and winning coalitions

Let $$N = {1,2,.....,n }$$ be a set of elements called voters. Let $$C=\lbrace S : S \subseteq N \rbrace$$ be the set of all subsets of $$N$$. members of $$C$$ are called coalitions. let $$f$$ be a function from $$C$$ to $$(0,1)$$. A coalition $$S \subseteq N$$ is said to be winning if $$f(S) = 1$$, it is said to be losing coalition if $$f(S) = 0.$$.Such a function f is called a voting game if the following conditions hold

(a) N is a winning coalition.

(b) the empty set is a losing coalition.

(c)if S is a winning coalition and if $$S \subseteq S'$$ , then S' is also winning.

(d)if both S and S' are winning coalitions , then S and S' have a common voter. Source

Show that a. The maximum number of winning coalitions of a voting game is $$2^{n-1}$$

b. Find a voting game for which number of winning coalition is $$2^{n-1}$$

I tried by checking if any element of $$N$$ is a winning coalition then its union with any other element of $$N$$ will also be a winning coalition. Thus there are two options for the remaining elements either become a part of winning coalition or not.Thus there are $$2^{n-1}$$ .I am not sure I am right in my reasoning and unable to prove that this indeed is maximum.Any ideas?Thanks.

• You might have better exposure if you use the tags correctly. This is most certainly not set theory. May 8, 2017 at 19:35
• No idea. Sorry. May 8, 2017 at 19:50
• The problem with argument is that, perhaps, there is no singleton as winning coalition. May 8, 2017 at 19:58
• @Phicar why there cannot exist any singleton as winning coalition? May 8, 2017 at 20:03
• @Pink No, they can, indeed your example works but, perhaps, there is no singleton so argument has to be finished. May 8, 2017 at 20:06

Your example with $2^{n-1}$ winning coalitions is a good one.

To prove there are no more than $2^{n-1}$ winning coalitions, note that a subset and its complement cannot both be winning as they do not share a voter. As no more than half the subsets can be winning, the maximum number of winning coalitions is $\frac 12(2^n)=2^{n-1}$

There are other ways to get $2^{n-1}$ winning coalitions. Pick any odd number $k$ of voters to count. A winning coalition is any group that includes a majority of those voters. There are $2^{k-1}$ subsets of the $k$ that are a majority and you can add in any of the $2^{n-k}$ subsets of the voters that do not count. Any two winning coalitions will have at least one of the $k$ voters that count in common.

• Woha, 25 secs later than you, 200+k user... But I also have to admit that I don't know anything about filters, let alone ultrafilters :-) @Ross May 8, 2017 at 20:25
• @lesath82: you got the point exactly. Good work. May 8, 2017 at 20:35
• @lesath82: I later realized it is not a filter as a filter requires that the intersection of any two subsets in the filter also be in the filter. May 9, 2017 at 1:03
• About filters, I'll take your word! @Ross May 9, 2017 at 6:38
• I love your wonderful generalization of the solution, you have deserved my sportsmanship upvote! I'm updating my answer with a further generalization, if you think this is not fair, feel free to edit my post. @Ross May 9, 2017 at 6:38

Your solution for $2^{n-1}$ winning coalitions is just perfect. Say that $\{1\}$ is a winning coalition, then there are $2^{n-1}$ coalitions that include $1$ and are winners, and $2^{n-1}$ that do not and are losers. These respect all the conditions:

(a) $N$, including $1$, is a winning coalition

(b) the empty set, not including $1$, is a losing coalition

(c) if $S$ is a winning one, thus it includes $1$, then $S'\supseteq S$ also includes $1$ and is a winning coalition as well

(d) $S$ and $S'$ both winners have at least $1$ in common

Let's prove that it's not possible to have more than $2^{n-1}$ winning coalitions. Indeed you may have at most $2^{n-1}$ subsets among which you don't have any pair of complementary subsets. As soon as you have such a pair of winning subsets, you are no longer respecting condition (d) (complementary subsets by definition do not share any element). So $2^{n-1}$ is the maximum.

EDIT: Ross Millikan has exposed a more general valid solution, which includes the one from the OP as a particular case. I'm going to give an even more general setup, easily observed in real life situations. An excellent comment by Alex Ravsky gives a further theoretical completion of the topic.

Pick any $k \neq 0$ voters, they will constitute the committee. Only their votes (that is, presence in a subset) are going to count: votes from the other $N-k$ elements will be irrelevant. Note that $k=N$ (all the voters count) and $k=1$ (the OP's solution, with only one significant voter) are perfectly valid choices. You decide what are "winning coalitions" in the intuitive way derived from real life: those including the majority of the committee. If $k$ is even, you need to elect a "president", whose presence will decide any tie (think of his vote as counting $3/2$ instead of $1$; you may want to have such a president also in a committee with an odd number of members, but it's pretty much useless since it's not going to modify the results). Again you can see that this setup respects conditions (a-d).

• Concerning the kinds of all valid solutions, I have to say that all your committee based voting systems belong to a specific class of weighted voting systems. I’ll call a voting system weighted provided the family of its winning coalitions can be generated as follows. Each voter is given a non-negative number, called weight such that the total sum of weights of the voters equals $1$ and there exists a number $q> 1/2$ such that a coalition is winning iff the sum of weights of voters from it is at least $q$. May 29, 2017 at 5:23
• If I remember right the characterization which I was taught as a student about twenty years ago, :-) a voting system is weighted iff it is exchange stable, that is if for each winning coalitions $S_1$ and $S_2$ and each sets $S_1’\subset S_1$ and $S_2’\subset S_2$ at least one of coalitions $(S_1\setminus S_1’)\cup S_2$ and $(S_2\setminus S_2’)\cup S_1$ still is winning. May 29, 2017 at 5:24
• @Alex thank you, I mentioned your comment in the answer May 29, 2017 at 8:21