Voting Systems

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
imatrendytotebag
Posts: 152
Joined: Thu Nov 29, 2007 1:16 am UTC

Voting Systems

Postby imatrendytotebag » Wed Feb 24, 2010 9:14 am UTC

A group of n people need to vote on some sort of proposition. They each vote yes or no. However, some voters are more powerful than others. In general, each voter has power equal to some nonnegative integer. If the sum of the powers of the voters saying "yes" surpasses some predetermined threshold, the proposition passes. We can write such a "voting system" as follows: {threshold;power of 1st voter, power of 2nd voter,...,power of nth voter}

For example: the voting system {2;2,1,1} has three voters with power 2,1,1 respectively. If the first voter votes "yes", the proposition will pass. However, even if he votes "no", the proposition may still pass of the other two voters vote "yes". If a group of voters can pass a measure by all voting "yes" even when the other voters say "no" , we call that group of voters a "winning coalition"

Now the questions:
1) Given n, how many unique voting systems are there? Can they be classified/enumerated in a sensible way? Two voting systems are said to be the same if they have the same winning coalitions. (Note: The way this question is worded implies {2;2,1,1} and {2;1,2,1} are DIFFERENT voting schemes, as the first voter alone is a winning coalition in the first scheme but not the second. However, they are in some sense equivalent, ie there exists a correspondence (bijection) between the voters of the first to the voters of the second which exactly preserves winning coalitions)

2) Suppose we add the following "natural" constraint: Given some subset of the voters, either that subset is a winning coalition or its compliment is a winning coalition, but not both. Now what are the answers to question 1? (Note that {2;2,1,1} does NOT satisfy this condition. {2;1,1,1} DOES).

3) We can think of the voting scheme notation developed above as representing something more abstract, ie a set of voters along with a collection of subsets that are "winning coalitions". In other words, the schemes {2;2,1,1} and {4;4,2,2} represent the same scheme. Is there any sensible way to talk about the "minimal" representation of a voting scheme using this notation?

Gogo, have some fun!
Hey baby, I'm proving love at nth sight by induction and you're my base case.

DavCrav
Posts: 251
Joined: Tue Aug 12, 2008 3:04 pm UTC
Location: Oxford, UK

Re: Voting Systems

Postby DavCrav » Wed Feb 24, 2010 10:54 am UTC

Well, for reasonably large n, the answer to 1) is"many". My first estimate would be all possible sets of subsets of {1,..,n}. This has a lot of overcount, of course, because for example we can have {1} but not {1,2}. So you need to include all oversets of any given set. Hence you can think in terms of generators of all winning coalitions; i.e., minimal subsets of {1..n} that win.

However, there is a problem: suppose you have 1,2,3,4, and you want the following winning coalition generators: {1,2}, {3,4}. I claim this cannot be done, since the most powerful voter from 1 and 2, together with the most powerful voter from 3 and 4, should also be a winning coalition. This complicates matters.

The next problem is that there is a symmetric group acting. This step unfortunately has a(nother) problem, in that different systems will have differently sized symmetry groups, so it's not a case of dividing one by the other.

That said, maybe there's an obvious way to proceed...

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Voting Systems

Postby skeptical scientist » Wed Feb 24, 2010 2:17 pm UTC

I want to use induction - figuring out how many new voting systems you get when you add a person, as a function of the number of old voting systems (possibly partitioned with some simple structural information) - but it's just not working for me.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Voting Systems

Postby Yakk » Wed Feb 24, 2010 8:13 pm UTC

Can we take a set of "winning coalitions", and produce a voting scheme from it?

How hard is it to produce that voting scheme -- is the decision problem (does this set of winning coalitions have a voting solution) in NP? (yes, of course). Is it NP-hard? (dunno)

How hard is it to determine if two voting systems are "the same"? The naive solution is to pump out every subset that wins, and compare -- but that is an exp-time algorithm. It is in co-NP, because you can just demonstrate a winning coalition (in one voting system) that is not in the other, and checking that is trivial. Is it co-NP-hard?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Voting Systems

Postby jestingrabbit » Thu Feb 25, 2010 8:38 am UTC

Yakk wrote:Can we take a set of "winning coalitions", and produce a voting scheme from it?


There are some rules that the sets have to have. The one that is easiest to notice is that if [imath]A \subseteq B[/imath] and A is a winning coalition, then so is B. Problem 2 mentions a further pretty natural constraint.

I can't help but think there might be weirder ones out there implied by the rules that we have already, but there are certainly other rules that might be considered. For instance, everyone should be in some winning coalition other than the full coalition and should be excluded from another winning coalition (ie everyone should have a chance to change the outcome). These make the counting problem a lot harder, I expect, but the voting system a lot fairer.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

DavCrav
Posts: 251
Joined: Tue Aug 12, 2008 3:04 pm UTC
Location: Oxford, UK

Re: Voting Systems

Postby DavCrav » Thu Feb 25, 2010 11:47 am UTC

jestingrabbit wrote:
Yakk wrote:Can we take a set of "winning coalitions", and produce a voting scheme from it?


There are some rules that the sets have to have. The one that is easiest to notice is that if [imath]A \subseteq B[/imath] and A is a winning coalition, then so is B. Problem 2 mentions a further pretty natural constraint.

I can't help but think there might be weirder ones out there implied by the rules that we have already, but there are certainly other rules that might be considered. For instance, everyone should be in some winning coalition other than the full coalition and should be excluded from another winning coalition (ie everyone should have a chance to change the outcome). These make the counting problem a lot harder, I expect, but the voting system a lot fairer.


I gave an example of a set of winning coalitions that have no corresponding voting scheme in the 2nd post of this thread...

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Voting Systems

Postby Yakk » Thu Feb 25, 2010 2:50 pm UTC

Yes, not all sets describe winning coalitions.

There is the decision problem -- "does this set describe a set of winning coalitions". It looks like it is in NP (it might not be, if the required vote strengths goes super-exponential, but for some reason I doubt that...)

And, there is the production problem -- "given a set of winning coalitions that happens to be valid, produce a set of vote-weights that result in that winning coalition set". The production problem is no more than polynomial time easier than the decision problem.

Perhaps I should have said "can we take a set of valid winning coalitions, and produce a set of vote-weights that generate those winning coalitions".

I cannot help but think that having an algorithm going "that way" might help with the counting problem.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Voting Systems

Postby skeptical scientist » Thu Feb 25, 2010 6:02 pm UTC

jestingrabbit wrote:
Yakk wrote:Can we take a set of "winning coalitions", and produce a voting scheme from it?


There are some rules that the sets have to have. The one that is easiest to notice is that if [imath]A \subseteq B[/imath] and A is a winning coalition, then so is B. Problem 2 mentions a further pretty natural constraint.

Another constraint I notice is that if \(a, b \notin C\) and \(C \cup \{a\}\) is not a winning coalition but \(C \cup \{b\}\) is, then any winning coalition with a but not b is still a winning coalition if a is replaced by b. This rules out things like the {{1,2},{3,4}} mentioned above. It may be that this, or this plus some similar rules, suffice(s) to check whether a set of winning coalitions is realizable, which might put the problem in P.

I can't help but think there might be weirder ones out there implied by the rules that we have already, but there are certainly other rules that might be considered. For instance, everyone should be in some winning coalition other than the full coalition and should be excluded from another winning coalition (ie everyone should have a chance to change the outcome). These make the counting problem a lot harder, I expect, but the voting system a lot fairer.

It's fairer still if everyone has the same power, and then the number of voting systems is quite easy to count!
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Voting Systems

Postby jestingrabbit » Thu Feb 25, 2010 6:28 pm UTC

DavCrav wrote:I gave an example of a set of winning coalitions that have no corresponding voting scheme in the 2nd post of this thread...


I confess that I totally blanked and didn't read your post. My apologies.

skeptical scientist wrote:Another constraint I notice is that if \(a, b \notin C\) and \(C \cup \{a\}\) is not a winning coalition but \(C \cup \{b\}\) is, then any winning coalition with a but not b is still a winning coalition if a is replaced by b. This rules out things like the {{1,2},{3,4}} mentioned above. It may be that this, or this plus some similar rules, suffice(s) to check whether a set of winning coalitions is realizable, which might put the problem in P.


That looks like some real progress.

I can't help but think there might be weirder ones out there implied by the rules that we have already, but there are certainly other rules that might be considered. For instance, everyone should be in some winning coalition other than the full coalition and should be excluded from another winning coalition (ie everyone should have a chance to change the outcome). These make the counting problem a lot harder, I expect, but the voting system a lot fairer.

It's fairer still if everyone has the same power, and then the number of voting systems is quite easy to count!

Well, yeah... but that's cheating!

I guess if we're looking at political parties voting in a house of parliament my fairness conditions aren't necessarily satisfied. So, yeah, my rules are crap and your rule rules.

ps when I quote skep's last post from the "post a reply" page, I get a scree of html gibberish, though it works fine from the main page. Just thought I'd mention.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

DavCrav
Posts: 251
Joined: Tue Aug 12, 2008 3:04 pm UTC
Location: Oxford, UK

Re: Voting Systems

Postby DavCrav » Fri Feb 26, 2010 9:30 am UTC

Yakk wrote:There is the decision problem -- "does this set describe a set of winning coalitions". It looks like it is in NP (it might not be, if the required vote strengths goes super-exponential, but for some reason I doubt that...)


I had an idea about this: is the largest voting strength that a person needs about [imath]2^n[/imath] (possibly [imath]2^{n\pm 1}[/imath] or something like it)? My reason is that how high it needs to go has something to do with each person being able to beat all those with lower strengths single-handedly. Any other system can be taken to lie below this one (in the sense that the strength of person i is at most that of this one).

Something like this. Anyway, I have to go give a lecture.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Voting Systems

Postby jestingrabbit » Fri Feb 26, 2010 10:53 am UTC

skeptical scientist wrote:Another constraint I notice is that if \(a, b \notin C\) and \(C \cup \{a\}\) is not a winning coalition but \(C \cup \{b\}\) is, then any winning coalition with a but not b is still a winning coalition if a is replaced by b. This rules out things like the {{1,2},{3,4}} mentioned above. It may be that this, or this plus some similar rules, suffice(s) to check whether a set of winning coalitions is realizable, which might put the problem in P.


We actually want to broaden this out a bit I think. If A and B are disjoint from C and D and if [imath]C\cup A[/imath] loses, [imath]C\cup B[/imath] wins, and [imath]D\cup A[/imath] wins, then [imath]D\cup B[/imath] wins. There's also a similar condition where we swap 'wins' for 'loses' in the above.

I don't think that's implied by SS's version, but its certainly implied by the setup imatrendytotebag has proposed.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
snowyowl
Posts: 464
Joined: Tue Jun 23, 2009 7:36 pm UTC

Re: Voting Systems

Postby snowyowl » Fri Feb 26, 2010 11:37 am UTC

Awesome question. I'm going to write down the first few terms in the sequence of values of n to to see if a pattern appears.

n=1: 3 voting systems "always pass", "always reject", "person gets to choose". Yep, these are all valid voting systems, corresponding to {0;0}, {1;0} and {1;1}.
n=2: 6 voting systems {0;0,0}, {1;0,0}, {1;1,0}, {1;0,1}, {1;1,1}, {2;1,1}
n=3: 20 that I could find; there might be more: {0;0,0,0}, {1;0,0,0}, {1;1,0,0}x3, {1;1,1,0}x3, {2;1,1,0}x3, {1;1,1,1}, {2;1,1,1}, {3;1,1,1}, {2;2,1,1}x3, {3;2,1,1}x3, where "x3" means that there are three permutations of the 3 people which produce different voting systems.

I think that this problem could be expressed in terms of Boolean logic: each voting system can be written in a form such as"A or (B and C)", which corresponds to {2;2,1,1}. Such a statement can only use "And" and "Or" expressions; no "Not"s. But my proof of this has a few holes in it, and I'm not sure it's a useful proof anyway. Or even if it's true.
The preceding comment is an automated response.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Voting Systems

Postby skeptical scientist » Fri Feb 26, 2010 5:11 pm UTC

snowyowl wrote:I think that this problem could be expressed in terms of Boolean logic: each voting system can be written in a form such as"A or (B and C)", which corresponds to {2;2,1,1}. Such a statement can only use "And" and "Or" expressions; no "Not"s. But my proof of this has a few holes in it, and I'm not sure it's a useful proof anyway. Or even if it's true.

Well, this is true but not useful, since you can just express it as a disjunction of conjunctions where each conjunction represents a single winning coalition. Since a voting system is determined by its winning coalitions, each voting system gets represented this way. We can write the conjunctions without using negations since if people in a winning coalition all vote yes, it doesn't matter whether the others vote yes or no. We can also simplify our expressions by only taking a disjunction of conjunctions corresponding to minimal winning coalitions.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 8 guests