Voting games and winning coalitions

Question

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.

Answer 1

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.

Answer 2

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).