6
$\begingroup$

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.

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

2 Answers 2

6
+50
$\begingroup$

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.

$\endgroup$
12
  • $\begingroup$ 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 $\endgroup$
    – lesath82
    May 8, 2017 at 20:25
  • $\begingroup$ @lesath82: you got the point exactly. Good work. $\endgroup$ May 8, 2017 at 20:35
  • $\begingroup$ @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. $\endgroup$ May 9, 2017 at 1:03
  • $\begingroup$ About filters, I'll take your word! @Ross $\endgroup$
    – lesath82
    May 9, 2017 at 6:38
  • $\begingroup$ 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 $\endgroup$
    – lesath82
    May 9, 2017 at 6:38
6
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ 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$. $\endgroup$ May 29, 2017 at 5:23
  • 1
    $\begingroup$ 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. $\endgroup$ May 29, 2017 at 5:24
  • 1
    $\begingroup$ @Alex thank you, I mentioned your comment in the answer $\endgroup$
    – lesath82
    May 29, 2017 at 8:21

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.