aspose file tools*
The moose likes Programming Diversions and the fly likes Optimizing voting Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Optimizing voting" Watch "Optimizing voting" New topic
Author

Optimizing voting

josef andersson
Greenhorn

Joined: Jan 19, 2012
Posts: 8
Been thinking about this problem some time, but I'm stuck and would need some guidelines (not the fully coded solution of course, that's no fun).
Problem: Imagine a reality tv-show where watchers can give 2 votes. Who stays and who guess. So typical votes would be : Jim stays , Laura goes and so on. That makes nice tuples for every vote {J,L}, {D,H} and so on. Easy peasy, but if we add the condition that the votes that gives the most voters "right" wins , ie {J,L}, {D,H},{J,L}, {D,J} gives 3 voters "ok" {J,L}, {D,H},{J,L} - how would i go on with that problem?Iimagine number of permutations if theres 10 actors, 200 voters! I imagine theres some algorithm for finding this but I can't find it, been looking at knapsack, Djikstra and others.
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3015
    
  10
josef andersson wrote:but if we add the condition that the votes that gives the most voters "right" wins , ie {J,L}, {D,H},{J,L}, {D,J} gives 3 voters "ok" {J,L}, {D,H},{J,L}

I've read this section several times now, but have no idea what it means. Can you explain using other words? Are you saying that {J,L}, {D,H}, {J,L}, {D,J} is an example of four vote tuples? And then, what is the solution or result? What is it that makes 3 voters "ok" or "right"?
josef andersson
Greenhorn

Joined: Jan 19, 2012
Posts: 8
Sorry, I'll try to clearify:

" Are you saying that {J,L}, {D,H}, {J,L}, {D,J} is an example of four vote tuples? "
Yes, ie from 4 voters, with the "Stay" and "Leave" vote.

Vote number x {Stay, Leave}

Vote 1 {J,L}
Vote 2 {D,H}
Vote 3 {J,L}
Vote 4 {D,J}


" And then, what is the solution or result? What is it that makes 3 voters "ok" or "right"?

Vote 2 doesn't conflict with any other votes , and thus is clearead at once = one ok vote.

Note vote 4 is in conflict with vote 1 and 3, as it's a "Leave" for J.Thus, Voters 1,3 and 4 can't all get their wishes fulfilled. However, choosing vote 1 and 3 would give more "ok" votes and fulfilled voters than choosing vote 4 only, so we choose vote 1 and 3 = 2 more ok voters.
Now with a small sample set, this is easy to just reason about, but with a big "universe" of people to vote on , and many voters.....well, how could it be solved..
Myke Enriq
Ranch Hand

Joined: Feb 13, 2012
Posts: 109
Well , if I get this right , this voting system is weak. Thinking about it , you can easily get in situations where you do not have a positive result.

10 people and 10 votes. First vote is {1,2} , second is {2,3} ........ 99th vote is {99,100} , and last vote is {100,1}.

Thus each person has precisely one vote for him and one vote against him.


Worse than people with an equal number of votes for as votes against , are the people that have no votes for them (either for or against).


Having said that , you can give each person a score , that is initially 0 , then increased by one for each vote for that person , and decreased by 1 for each vote against.
Thus if you are lucky , you can have a person with the least score and a person with the most score.

Maybe you can give more details on what real life situation you are trying to model with this voting method.
josef andersson
Greenhorn

Joined: Jan 19, 2012
Posts: 8
"
10 people and 10 votes. First vote is {1,2} , second is {2,3} ........ 99th vote is {99,100} , and last vote is {100,1}. "

First sentence should be "100 people and 100 votes", right?
The tuples and votes in the second sentence says you mean 100 people to vote on to stay and leave {Pn,Pn} where n > 0 and < 101 , and 100 voters voting on these
Myke Enriq
Ranch Hand

Joined: Feb 13, 2012
Posts: 109
josef andersson wrote:"
10 people and 10 votes. First vote is {1,2} , second is {2,3} ........ 99th vote is {99,100} , and last vote is {100,1}. "

First sentence should be "100 people and 100 votes", right?
The tuples and votes in the second sentence says you mean 100 people to vote on to stay and leave {Pn,Pn} where n > 0 and < 101 , and 100 voters voting on these


Well , despite this minor inconvenient , can you understand the issue I am talking about ?
The voting method is not giving us enough information (at least in the worst case scenario) to be able to make a decision.
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3015
    
  10
Myke, sure it's possible to have undecidable cases because the votes are tied - but that's hardly unique to this voting system. We can create possible ties in most any voting system. If this is part of a reality show, I imagine they'd just have to have a second vote. They're not going to stay in such a fragile equilbrium for long.

Josef, you still haven't said what the final result should be for the example you gave. I'm guessing that the unstated goal of this vote is to choose exactly one person to leave:
Vote number x {Stay, Leave}

Vote 1 {J,L}
Vote 2 {D,H}
Vote 3 {J,L}
Vote 4 {D,J}

Okay, that means there are four possibilities to consider: J leaves, L leaves, D leaves, or H leaves. Here's one way to consider them:

If J leaves, that violates votes 1, 2, and 3. (3 votes against)
If L leaves, that violates votes 2 and 4 (2 votes against)
If D leaves, that violates votes 1, 2, 3, 4 (4 against)
If H leaves, that violates votes 1, 3, 4 (3 against)

By this count, L should leave. However, this effectively ignores any real effect of the "stay" votes, since that part of the vote is violated only in cases where the "leave" vote is also violated. To fix this, we could count differently, counting the Stay and Leave votes separately. I will use S and L to represent these: vote 1S is voter 1's vote for who should Stay. And vote 3L is voter 3's vote for who should Leave. Okay:

If J leaves, that violates votes 1S, 1L, 2L, 3L, and 3S. (5 votes against)
If L leaves, that violates votes 2L and 4L (2 votes against)
If D leaves, that violates votes 1L, 2S, 2L, 3L, 4S, 4L (6 against)
If H leaves, that violates votes 1L, 3L, 4L (3 against)

So again, the result is that L should leave, as this violates the least number of votes. However, the totals are different this time. One might imagine there would be some scenarios where these counting methods would yield different results.

So, does one of these match the way you would count the result? Or is there another way you'd like to look at it?
Myke Enriq
Ranch Hand

Joined: Feb 13, 2012
Posts: 109
In case of a reality show , I imagine that voting is done by phone or SMS , and that each vote costs some $.
Therefore the ideal voting algorithm should try to maximize the number of time people vote.

The equal importance for a negative vote as for a positive one , gets us into situations mentioned above where you have a lot of votes bu still can not make a sound decision.

In fact , any method where a negative vote equals a constant * the value of a positive vote , will still lead to tie situations.

A better approach could be one where you count the number of positive and negative votes for a person X , then you ponder that with the total number of votes for the person Y to decide between the 2.

Meaning the value choose_between_personX_and_personY = (positiveXvotes - negativeXvotes) / total_nr_votes_X versus (positiveYvotes - negativeYvotes) / total_nr_votes_Y
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3015
    
  10
Myke Enriq wrote:In case of a reality show , I imagine that voting is done by phone or SMS , and that each vote costs some $.
Therefore the ideal voting algorithm should try to maximize the number of time people vote.

You must watch very different reality shows than I've seen. I guess you're assuming (a) the audience is who gets to vote, and (b) direct income from the audience is more important than lost advertising revenue due to pissing people off. Possible, but neither is an assumption I choose to make.

Then again, if we did accept your assumption, then ties would be a good thing, since they would force additional votes. So, what's the problem with ties?

Myke Enriq wrote:The equal importance for a negative vote as for a positive one , gets us into situations mentioned above where you have a lot of votes bu still can not make a sound decision.

In fact , any method where a negative vote equals a constant * the value of a positive vote , will still lead to tie situations.

Perhaps you meant that it can lead to tie situations? Surely you don't mean it's a definite thing, right?

Maybe you're trying to say that this system makes ties more likely. That's probably true. But it's hardly the paralyzing problem you seem to think it is. And we don't even know if the voting rules are something the poster has control over.

Myke Enriq wrote:A better approach could be one where you count the number of positive and negative votes for a person X , then you ponder that with the total number of votes for the person Y to decide between the 2.

Better than what? I haven't recommended anything; I'm just asking questions trying to find out what the poster actually means.
Myke Enriq
Ranch Hand

Joined: Feb 13, 2012
Posts: 109
Anyhow , so far the rule is A < B <=> (VforA - VagainstA) * (VforA + VagainstA)< (VforB - VagainstB) * (VforB + VagainstB)

This rule is better because is also counts the total nr of votes for a person thus it tries to use the information "A has received more votes (be it for or against) than B".

I do feel that this could be optimized. I wonder if by this rule if A < B and B < C then A must be < C ?

It also has the disadvantage that if A gets 5 votes for and 5 against , and B gets only 1 vote for , then A < B , although it tries to take into account the total number of votes.

For the situation "A gets 5 votes for and 5 against , and B gets only 1 vote for" I think A should be > B as for profit purposes A brings more value to the show since it gets more people involved and entertained.


 
It is sorta covered in the JavaRanch Style Guide.
 
subject: Optimizing voting