wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> unique voting
        
(Message started by: amia on Jun 8^th, 2005, 1:49am)

Title: unique voting
Post by amia on Jun 8^th, 2005, 1:49am

The king was arranging "dark ages" lotto. He selected a lot of candidates for a position and gave them serial numbers from 1 till N (for example 30000).
Each person in the land can bet on a candidate (he can not see what others bet). At the end of each day if a pre determined minimal numbers of voters was reached (for example 300), a winner is picked. Since the king had a single prize, any candidate that got more than one vote can not win. The highest number that got a single vote wins the position and the voter gets the prize.
In the town square there is an updated list that shows how many people voted, and how many of them are erased (due to multiple votes). The actual votes do not appear but the voters’ names next to the relative position of each bet in both the un-erased and erased lists appear. You are the town mathematician (so you can devise a strategy better than the average Joe). A person can vote several times, but each bet costs a lot of money so the objective is to pick the winner with minimum bets. You can choose when to bet, how many times, and what to bet. What is your best strategy?

Title: Re: unique voting
Post by Deedlit on Jun 8^th, 2005, 3:21am

Well, if it ends after n votes, you could vote once for the [n/2] + 1 highest numbers; since there are fewer remaining votes, at least one of your numbers will have a single vote, so you win. If you make any fewer number of votes, you run the risk of having them all cancelled out.

Title: Re: unique voting
Post by amia on Jun 8^th, 2005, 3:52am

Even this, theoretically, does not ensure wining, since there could be more than n votes (the number of votes is checked once at the end of each day). Neverthell, it will likely work but it requires much too many votes. You could use the town square list and how it updates from your votes (and others) too get much lower than this with resonably high chance of winning.

Title: Re: unique voting
Post by asterex on Jun 8^th, 2005, 11:30am

Could you clarify a few things?
What do you mean by "the relative position of each bet"?
How dumb are the citizens? It makes a big difference if they pick at random or they all use the same strategy and cancel each other out.
How large is the prize compared to the cost of voting? The bigger the prize, the more people will cast multiple ballots, and the more likely the voting will end on day one. If it's small, you can sit back and wait until the vote count gets close before you waste your money.
How many voters are there? If there are a lot more voters than candidates, then every candidate will probably get multiple votes the first day and there will be no winner.
Can the candidates vote? They'll probably all vote for themselves, (and maybe cast multiple votes for their greatest opponent to make sure he loses) so your only hope of winning is picking someone who doen't think he has a chance of winning or is too poor to buy a vote.
Are you a candidate, or do you care who wins? (that might be worth more than the prize to you).
Can you sit outside the voting booth and count the number of people who vote each day, as well as recognize which of the candidates themselves came to vote, so you can make your own vote right before the polls close?
The question just seems to depend far too much on the intelligence and the psychology of the other voters to give you any single winning strategy.

Title: Re: unique voting
Post by amia on Jun 8^th, 2005, 10:24pm

on 06/08/05 at 11:30:56, asterex wrote:

A lot of good questions - lets start one by one.
1) "relative position". Both lists (erased/ non-erased) appear from highest serial number of candidate to lowest (without the actual serial number and without knowing how many votes each number got).
2) "how dumb" - I assume, most are average Joes. Not random vote but not as smart as the mathematician and they do not have a predetermined strategy. For example, most will understand not to bet very low numbers. I can supply one or more examples of typical bets if it is requested. Let's assume the mathematician can see probability distributions of past votes.
3) The prize is such that voting for all 300 votes at the end of the first day will cost you in the order of magnitude of 5 times the prize.
4) "number of voters" - there are a lot of potential voters but not actual voters, since getting to town in the middle ages requires a lot of effort. Therefore, you can assume most people will not arrive and the actual procedure will take weeks or months and number of votes per day is low (perhaps when there are few votes to finish this number increases somewhat).
5) The voters do not care who wins and the candidates have no voting or influencing ability.
6) You can sit near the boot, you can arrive once every few days, whatever. The only thing is that you also have a life so it is better to devise strategy that will not require it.
7) "The question .. to give you any single winning strategy" - I agree that it has no close-form solution and if this sort of riddle is not appropriate for this forum I apologize and I'll ask for it to be removed (I'll appreciate feedback on that issue). However, some strategies can be devised and I think it does require thinking. I can also supply more data that might help. You can also decide to look at a few elections (you get the data at the end of each election) and bet only after you studied the dynamics. It is more important to get ideas running than to ensure winning.

Title: Re: unique voting
Post by JocK on Jun 10^th, 2005, 2:08pm

Rather than bother about irrational average Joe's who have to base their strategies on vaguely defined costs of voting, I would like to simplify the problem in such a way that it becomes mathematically tractable:

M players can each select one positive integer. The player who has selected the lowest integer not chosen by any of the other players wins. How should you play? (assuming absence of communication between the players and rational behaviours of your competitors)

Staying close to the originally posted problem, one should solve the M-player problem for M close to 300. Haven't sorted out that one yet...

Starting from more modest M-values, the folowing results emerge:

The two-players problem (M=2) is trivial, and results in a 'prisoners-dilema-type' non-cooperative strategy. (No matter what strategy the opponent follows, it never pays to select a value different from 1, For rational players this would result in both players selecting 1 and both gaining nothing.)

The three-players (M=3) problem is much more complicated, and results in the individual players selecting integer numbers with exponentionally decreasing probabilities. The net effect being that each of the players wins in about 29.56% of the cases.

I am too lazy for the M>3 (and particularly the M=300) problem. Leave that for the uberpuzzlers to chew on... 8)