Math Puzzles (from FiveThirtyEight - new puzzle every Friday) (1 Viewer)

[bostonfred]

That's interesting. I wonder if that's where my long drawn out thing would have ended up

 

[JayMan]

That's interesting. I wonder if that's where my long drawn out thing would have ended up

It probably would have - and then rescaling on the 2x1 problem would also have given a 50% result inferring a n+1 by n generalisation.

But IE's observation of the 90 degrees turn was very clever - quick thinking on his part, switching from the 3x2 to the general n+1 by n model with that 'sqaure constraint'.

 

[Ignoratio Elenchi]

New puzzle, and solution to last week's.

 

[Ignoratio Elenchi]

Here's the full text of this week's puzzle:

Suppose that five politicians, disgusted with the current two-party system, come together to choose a third-party candidate to run in the 2016 presidential election. The politicians’ names are Anders (A), Blinton (B), Cubio ©, Drump (D) and Eruz (E). Not wanting to spend all their time campaigning in Iowa and New Hampshire in winter, they decide instead to pick which of them will be the candidate at a secret meeting with just the five of them. The voting procedure is as follows: They will first hold a vote of A versus B. (The five politicians are the only voters.) The winner of that vote will then be paired against C. That winner will be paired against D, and finally that winner will be paired against E. They will declare the winner of that last matchup to be their candidate.

Each of A, B, C, D and E wants to be the presidential candidate themselves, but also has clear preferences over the others. Furthermore, the politicians’ preferences are common knowledge. Their preferences are as follows (“X > Y” means Candidate X is preferred to Candidate Y):

Candidate A: A > B > C > D > E

Candidate B: B > A > E > D > C

Candidate C: C > D > A > E > B

Candidate D: D > B > A > E > C

Candidate E: E > D > B > C > A

All of the politicians are forward-looking and vote strategically.

Question 1: Who will be chosen as the presidential candidate?

Now assume that A has the flu and is forced to miss the voting meeting. He is allowed to transfer his vote to someone else, but he can’t make that other person commit to vote against her own self-interest.

Question 2: To whom should he transfer his vote, given his candidate preference outlined above (A > B > C > D > E)?

Question 3: Who will win the candidacy now?

Question 4: A month before the meeting, Candidate A must decide whether or not to get the flu vaccine. Should he get it?

I think I have the answer to Question 1. Haven't taken a crack at the rest yet.

 

[bostonfred]

Candidate A: A > B > C > D > E

Candidate B: B > A > E > D > C

Candidate C: C > D > A > E > B

Candidate D: D > B > A > E > C

Candidate E: E > D > B > C > A

Without strategic voting

A vs b

A votes a

B votes b

C votes a

D votes b

E votes b

B wins

B vs c

A votes b

B votes b

C votes c

D votes b

E votes b

B wins

B vs D

A votes b

B votes b

C votes D

D votes D

E votes D

D wins

D vs E

A votes d

B votes E

C votes D

D votes D

E votes E

D wins

 

[bostonfred]

But "all of the politicians are forward-looking and vote strategically."

Candidate A: A > B > C > D > E

Candidate B: B > A > E > D > C

Candidate C: C > D > A > E > B

Candidate D: D > B > A > E > C

Candidate E: E > D > B > C > A

E vs. Anyone - e loses. E literally will never beat anyone in the final election, because there's no reason to vote anything but your actual preference. But people will collude to get their preferred candidate to face e, because it's an auto win.

D will never lose unless people collude. Candidates a and b both prefer themselves and each other to candidate d, but everyone else likes d better than either of them. C and e should almost never collude against d because he's their second choice. E is never going to win against d. C would collude against d to get himself the win, but there's no sense in it.

D always wins.

 

[Ignoratio Elenchi]

Agree with your answer fred, although not sure I agree 100% with the reasoning. Here's how I worked it out.

In the final vote, it will be someone matched up against E. And at that point, everyone can just vote their straight preference since there's no strategy to do otherwise.

If it's A vs E, A wins.

If it's B vs E, B wins.

If it's C vs E, E wins.

If it's D vs E, D wins.

Now let's go one round back, where it's someone matched up against D.

If it's A vs D:

- A and B prefer A

- C and D prefer D

- E would lose to either one of them in the next round anyway, and prefers D

Therefore D wins.

If it's B vs D:

- A and B prefer B

- C and D prefer D

- E would lose to either one of them in the next round anyway, and prefers D

Therefore D wins.

If it's C vs D, note that a vote for C is basically a vote for E, so we can treat this like E vs D instead of C vs D:

- A, C and D prefer D

- B and E prefer E

Therefore D wins.

So no matter what happens leading up to that point, D is going to win the third vote and thus go on to be chosen as the candidate.

 

[bostonfred]

2 if a gives his vote to someone, it would have to make other people change their votes. And the only way to do that is to get e preferred to d. Because that would force other people to collude.

Candidate A: A > B > C > D > E

Candidate B: B > A > E > D > C

Candidate C: C > D > A > E > B

Candidate D: D > B > A > E > C

Candidate E: E > D > B > C > A

If a gives his vote to b, then e would beat d. Knowing that e would beat d, people who prefer another candidate over e should want that candidate to beat d.

Candidate d knows he can't beat e in the final election and he would prefer b or a over c or e, so he would change his vote to b. B should beat a and c in the first election without help, so when b faces d, d, knowing that he can't beat e, would vote for b who was his second choice anyways. Candidates c and e disagree, but they're powerless to prevent it.

 

[bostonfred]

3 b

4 yes, because getting the flu sucks. He should just pretend to be sick.

 

[Ignoratio Elenchi]

My take on Questions 2-4 (which are all really part of a single question it seems):

Spoiler

A should give his vote to E. This seems strange because A is E's least preferred candidate. However, with two votes in the final round, E would beat anyone except A. And all the other candidates strictly prefer A to E, so they'll keep voting for A in each prior round to advance him to the final round where he'll win the election.

Q2: Give vote to E

Q3: A wins

Q4: No (or as fred points out, he should do whatever he can to miss the vote). If he shows up, D wins. If he passes his vote to E, A wins.

 

[bostonfred]

I didn't even bother with that once I saw b. Damn it.

 

[Ignoratio Elenchi]

So this is kind of bugging me a little about the puzzle/solution. A has a particular set of preferences, but he knows that these result in D winning (Q1). He also knows he'd be better off if he is able to abstain and pass his vote to E (Q2). So if he stays in the election, he'd discard his own preferences and vote as if he was E, no? In which case the answer to Q1 isn't D, it's A. But then the other voters can also deduce that this is A's optimal strategy, and then perhaps also adjust their own voting to account for it, which might change the result, and then A would react to those changes, and they'd react to A's changes and... ad infinitum? Or does it reach some stalemate/steady state where a certain outcome is inevitable regardless of how many layers of logic we peel through?

Edit: Probably just overthinking it. E getting A's vote works because everyone knows E will vote for himself twice in the final round. A can threaten to vote along with E's preferences down the line but if, say, C and D just call his bluff and get someone else to the final round of voting, A will abandon his threat and vote for his own preference.

 

[heckmanm]

So this is kind of bugging me a little about the puzzle/solution. A has a particular set of preferences, but he knows that these result in D winning (Q1). He also knows he'd be better off if he is able to abstain and pass his vote to E (Q2). So if he stays in the election, he'd discard his own preferences and vote as if he was E, no? In which case the answer to Q1 isn't D, it's A. But then the other voters can also deduce that this is A's optimal strategy, and then perhaps also adjust their own voting to account for it, which might change the result, and then A would react to those changes, and they'd react to A's changes and... ad infinitum? Or does it reach some stalemate/steady state where a certain outcome is inevitable regardless of how many layers of logic we peel through?

WIFOM IMO

 

[Ignoratio Elenchi]

WIFOM IMO

Exactly. But I think it resolves itself because in the final round there's no mystery. Any voter might threaten to act in any particular way but when it comes to the final vote of _ vs. E, no one will have any incentive to vote in any way other than their own preference. A's threat to vote in alignment with E is empty because when it gets to the final round, everyone knows he won't. And everything follows backwards from there.

 

[bostonfred]

That's why you have to work backwards. The final decision will always be somebody vs e. And pretty much everyone hates e. So whoever faces e will win.

Them you figure out what happens when anyone faces d. And c, d and e would all be cool with d winning, if they can't win themselves. A and b aren't too keen on him but they're getting muscled out.

There's no move that a (or b) can make that will threaten the third match (the one where the winner of a/b/c faces d.)

So whatever move a makes has to legitimately threaten to have e beat d. Because apparently everyone agrees that e is a ####### nightmare. Funny that they made him Ted Eruz.

A can only win by getting everyone to band together to keep Ted eruz out of office. They all know that in the final vote, there's no more strategy to be used because the winner of x vs e takes all. So there's no sense in bluffing, especially when everyone knows that a hates e more than anyone and would literally vote for anyone else.

The whole point of the move is to specifically provide teeth to the bluff by committing to letting e beat them. If there were any way that a could take his vote back when he realized e might win, the whole thing falls apart. It has to be irrevocable.

 

[hagmania]

My one-look answer told me D for Question 1 because he wasn't anyone's last preference.

 

[GregR]

Right. The first assertion to make is that C cannot possibly win and knows. So C's vote will always be cast to help D, his favorite candidate.

 

[bostonfred]

Candidate A: A > B > C > D > E

Candidate B: B > A > E > D > C

Candidate C: C > D > A > E > B

Candidate D: D > B > A > E > C

Candidate E: E > D > B > C > A

Nobody else can bluff the same way that a can. That's the clever part of the puzzle.

Because 3 of the people like d as their first or second choice, the only way to beat d is to threaten to have e beat d.

For example b can't bluff voting for e, because everyone knows that she would already vote for e over d if it came down to that, and they have the numbers to ignore her.

C is apparently also a nightmare. If c gives his vote to e, e will beat d. Nobody wants that. So a or b will win. And since more people want b to win than a, b will win. Which is the worst case for c.

If c gives his vote to b, again, e would beat d, which nobody wants. But again it would work out for b, which is the worst chice from c's perspective.

D is going to win if nobody screws with anything, so there's no value to him in bluffing.

And e can't threaten anything worse than voting himself over d - which he already would. He could shift the tide so that b beats d in the third election, but then b would annuals l annihilate him in the finals, and he'd rather have d than b so that's not an option either.

The way it's constructed, only a can benefit by giving away his vote. It's like the crane technique. If do right, no can defend.

 

[Ignoratio Elenchi]

Edit: Probably just overthinking it. E getting A's vote works because everyone knows E will vote for himself twice in the final round. A can threaten to vote along with E's preferences down the line but if, say, C and D just call his bluff and get someone else to the final round of voting, A will abandon his threat and vote for his own preference.

A can't "abandon his threat" in Question 2, he's not going to the meeting and is giving his vote to a proxy, and that proxy will not go against their own self-interest.

Right. I was initially wondering, if A knows that giving his vote to E causes A to win, then in Question 1 why wouldn't A just vote as if he was E? At first I thought there was no difference, but what you mentioned is precisely the difference. In Question 2 A can't abandon his threat, he's committed his vote to E. In my hypothetical Question 1 scenario, A absolutely would abandon the threat as soon as they made it to the final round (and everyone knows it).

 

[bostonfred]

The whole point of the move is to specifically provide teeth to the bluff by committing to letting e beat them. If there were any way that a could take his vote back when he realized e might win, the whole thing falls apart. It has to be irrevocable.

Oh come on

 

[Ignoratio Elenchi]

Interesting variant on the original problem: If each candidate prefers himself first, and then prefers the other four candidates in some random order, what would you expect each candidate's probability of winning to be?

 

[Ignoratio Elenchi]

Interesting variant on the original problem: If each candidate prefers himself first, and then prefers the other four candidates in some random order, what would you expect each candidate's probability of winning to be?

Perhaps a better way to word this question: Given the setup of the process (A vs B, then winner vs C, then winner vs D, then winner vs E) - if you didn't know anything about the other four candidates ahead of time*, would you rather be A or B, or C, or D, or E?

* - All you know is that each candidate will always prefer himself first, and then his preferences for the other four candidates are random and equally likely to be in any possible order.

 

[rascal]

New puzzle, and solution to last week's.

Yeah, I dont get that at all (last weeks answer).

 

[Ignoratio Elenchi]

Yeah, I dont get that at all (last weeks answer).

I posted this earlier, maybe it will help. There are a few things to note, let me know which part you don't believe/understand:

- If the man can cross, the boat can't, and vice versa. These two possibilities (man can cross, and boat can cross) are mutually exclusive and exhaustive.

- This means that (the probability a man can cross) + (the probability a boat can cross) = 100%.

- Because of the "square" orientation of the bridges, if you turn the whole problem sideways it doesn't change at all. That is, the question "what is the probability a man can cross?" is exactly the same as "what is the probability a boat can cross?"

- So we have two questions, that have the same exact answer, and their answers add up to 100%. Thus the answer must be 50%.

 

[heckmanm]

Interesting variant on the original problem: If each candidate prefers himself first, and then prefers the other four candidates in some random order, what would you expect each candidate's probability of winning to be?

Perhaps a better way to word this question: Given the setup of the process (A vs B, then winner vs C, then winner vs D, then winner vs E) - if you didn't know anything about the other four candidates ahead of time*, would you rather be A or B, or C, or D, or E?

* - All you know is that each candidate will always prefer himself first, and then his preferences for the other four candidates are random and equally likely to be in any possible order.

Top of my head, I'd think "E", because then I only have to win one time.

 

[Ignoratio Elenchi]

Top of my head, I'd think "E", because then I only have to win one time.

If you'd put a gun to my head and gave me 5 seconds to answer this question I would've said the same thing. But I don't believe it's correct.

 

[JayMan]

Top of my head, I'd think "E", because then I only have to win one time.

If you'd put a gun to my head and gave me 5 seconds to answer this question I would've said the same thing. But I don't believe it's correct.

I haven’t run any numbers – but my guess to your assumption is the ‘loveable effect’...

If we look at the first matchup AvsB, it’s a toss-up – A and B will vote for themselves and A being preferred to B in the eyes of (CDE) implies a win for A (and vice versa);

For the sake of the argument, let’s suppose A won against B – looking at the AvsC matchup, conditional probability would suggest that A has a better chance of winning than C: A and C will vote for themselves – B vote is a toss-up (since we can’t conclude anything from him in the first round, he voted for himself)... but without any other knowledge, given that (DE) preferred A to B in the first round, it implies that A is ‘relatively high on their list’ and thus has an advantage over ‘neutral’ C.

Again, just a quick thought.

 

[heckmanm]

Top of my head, I'd think "E", because then I only have to win one time.

If you'd put a gun to my head and gave me 5 seconds to answer this question I would've said the same thing. But I don't believe it's correct.

I haven’t run any numbers – but my guess to your assumption is the ‘loveable effect’...

If we look at the first matchup AvsB, it’s a toss-up – A and B will vote for themselves and A being preferred to B in the eyes of (CDE) implies a win for A (and vice versa);

For the sake of the argument, let’s suppose A won against B – looking at the AvsC matchup, conditional probability would suggest that A has a better chance of winning than C: A and C will vote for themselves – B vote is a toss-up (since we can’t conclude anything from him in the first round, he voted for himself)... but without any other knowledge, given that (DE) preferred A to B in the first round, it implies that A is ‘relatively high on their list’ and thus has an advantage over ‘neutral’ C.

Again, just a quick thought.

This was in response to Iggy's variation, where the preferences are unknown.

* - All you know is that each candidate will always prefer himself first, and then his preferences for the other four candidates are random and equally likely to be in any possible order.

 

[Ignoratio Elenchi]

Top of my head, I'd think "E", because then I only have to win one time.

If you'd put a gun to my head and gave me 5 seconds to answer this question I would've said the same thing. But I don't believe it's correct.

I haven’t run any numbers – but my guess to your assumption is the ‘loveable effect’...If we look at the first matchup AvsB, it’s a toss-up – A and B will vote for themselves and A being preferred to B in the eyes of (CDE) implies a win for A (and vice versa);

For the sake of the argument, let’s suppose A won against B – looking at the AvsC matchup, conditional probability would suggest that A has a better chance of winning than C: A and C will vote for themselves – B vote is a toss-up (since we can’t conclude anything from him in the first round, he voted for himself)... but without any other knowledge, given that (DE) preferred A to B in the first round, it implies that A is ‘relatively high on their list’ and thus has an advantage over ‘neutral’ C.

Again, just a quick thought.

Yep. I haven't worked out the math but I saw a post on Twitter indicating that A/B would be most likely to win, then C, then D, and finally E with a much lower chance than the others. I wrote a simulation and came up with the same exact results.

Without working out a proof or anything, I assume the same basic reasoning you did - roughly that, in the final round, it's not just E vs. "random opponent," it's E vs "the guy who won his way to the final round." It still seems a little counterintuitive to me but I think that's what's going on.

 

[Ignoratio Elenchi]

Now that I think of it, it might actually be kind of misleading to think that E only "has to win once." It's actually kind of the opposite. It strikes me now as I think about the program I wrote to simulate the election results that, at every step in the election process, E is basically being evaluated against potential opponents (it also kind of follows from the solution to the original problem, where we had to work backwards from the final round).

For example, when deciding who to vote for in the first round, each voter isn't merely checking whether they like A better than B or vice versa. They're evaluating what will happen down the line, and they are voting in such a way to get their preferred outcome not in this round, but in the last round (which is all anyone cares about). e.g. In the original problem, we considered what would happen if it was C vs D in the penultimate matchup, and noted that C would lose to E anyway, so a vote for C is essentially a vote for E. We were already effectively voting for or against E before it got to the final round, and I think in a way that's also part of what works against E in the randomized variant of the problem. By going last, E isn't the last one being evaluated - he's really the first!

 

[heckmanm]

Hmm. I hadn't taken strategic voting into account.

 

[JayMan]

Now that I think of it, it might actually be kind of misleading to think that E only "has to win once." It's actually kind of the opposite. It strikes me now as I think about the program I wrote to simulate the election results that, at every step in the election process, E is basically being evaluated against potential opponents (it also kind of follows from the solution to the original problem, where we had to work backwards from the final round).

For example, when deciding who to vote for in the first round, each voter isn't merely checking whether they like A better than B or vice versa. They're evaluating what will happen down the line, and they are voting in such a way to get their preferred outcome not in this round, but in the last round (which is all anyone cares about). e.g. In the original problem, we considered what would happen if it was C vs D in the penultimate matchup, and noted that C would lose to E anyway, so a vote for C is essentially a vote for E. We were already effectively voting for or against E before it got to the final round, and I think in a way that's also part of what works against E in the randomized variant of the problem. By going last, E isn't the last one being evaluated - he's really the first!

I totally agree with what you are saying - except for the fact that in both examples (originial and your variant) it is assumed that their voting preferences are already predetermined and they don't move away from it - even with more information coming in (i.e. 'B is eliminated so I better vote C now to make sure I win against him in the next round', that sort of reasoning) - which is actually the only fun part in real life: who will O'Malley supporters go for, Sanders or Clinton, once he has been eliminated - that kind of scenarios...

 

[Ignoratio Elenchi]

except for the fact that in both examples (originial and your variant) it is assumed that their voting preferences are already predetermined

Maybe I'm confused but I'm not sure how this is an exception to anything I said. The puzzles (original and variant) both rely on the fact that the voting preferences are predetermined and don't change. I'm not disputing that. The entire outcome of any election can be deduced from the outset because we know everyone's preferences ahead of time. And the way we do that is by recursively considering possible outcomes, working backwards from the final round.

Basically, when the voters are considering A vs B, what they're really thinking about is something like:

(((A vs E) vs (D vs E)) vs ((C vs E) vs (D vs E))) vs (((B vs E) vs (D vs E)) vs ((C vs E) vs (D vs E)))

That's the whole election, decided right from the start. And E is considered in every step. So it's almost like by going last, unless E can beat everyone, then E can't win at all (not sure if that's precisely true, but that's the gist of my idea - it's harder for E to win because everyone knows in advance how things will shake out, so if there's someone they collectively like better than E, that person will get pushed to the final round).

 

[heckmanm]

Now that I think of it, it might actually be kind of misleading to think that E only "has to win once." It's actually kind of the opposite. It strikes me now as I think about the program I wrote to simulate the election results that, at every step in the election process, E is basically being evaluated against potential opponents (it also kind of follows from the solution to the original problem, where we had to work backwards from the final round).

For example, when deciding who to vote for in the first round, each voter isn't merely checking whether they like A better than B or vice versa. They're evaluating what will happen down the line, and they are voting in such a way to get their preferred outcome not in this round, but in the last round (which is all anyone cares about). e.g. In the original problem, we considered what would happen if it was C vs D in the penultimate matchup, and noted that C would lose to E anyway, so a vote for C is essentially a vote for E. We were already effectively voting for or against E before it got to the final round, and I think in a way that's also part of what works against E in the randomized variant of the problem. By going last, E isn't the last one being evaluated - he's really the first!

Do the candidates know each others' preferences, or only their own?

 

[Ignoratio Elenchi]

Do the candidates know each others' preferences, or only their own?

They all know each others' preferences. The puzzle states:

Each of A, B, C, D and E wants to be the presidential candidate themselves, but also has clear preferences over the others. Furthermore, the politicians’ preferences are common knowledge.

 

[heckmanm]

Do the candidates know each others' preferences, or only their own?

They all know each others' preferences. The puzzle states:

Each of A, B, C, D and E wants to be the presidential candidate themselves, but also has clear preferences over the others. Furthermore, the politicians’ preferences are common knowledge.

OK, missed that in my thinking. Not knowing each others' preferences, my brute-force trials favor E, but I haven't figured out how to code for strategery yet.

 

[heckmanm]

This could actually lead to candidates voting against themselves, couldn't it?

A's preference: A-D-B-C-E

Others' preferences mean E would defeat anyone except B

Therefore A should vote for B over himself, to reduce E's chances.

 

[Ignoratio Elenchi]

Do the candidates know each others' preferences, or only their own?

They all know each others' preferences. The puzzle states:

Each of A, B, C, D and E wants to be the presidential candidate themselves, but also has clear preferences over the others. Furthermore, the politicians’ preferences are common knowledge.

OK, missed that in my thinking. Not knowing each others' preferences, my brute-force trials favor E, but I haven't figured out how to code for strategery yet.

Yes, in that case I'd expect E to be the most likely candidate to win, since there he really does only have to win a single election. I don't think he'd be 50/50 to win that round because he'd still be getting matched up against a candidate who was favored enough to make it to the final round, but I think he'd still have a better chance than anyone else to win if there was no forward-looking strategy involved.

 

[Ignoratio Elenchi]

This could actually lead to candidates voting against themselves, couldn't it?

A's preference: A-D-B-C-E

Others' preferences mean E would defeat anyone except B

Therefore A should vote for B over himself, to reduce E's chances.

Yes, that's exactly what happens in the original problem, In a matchup of C vs D, C knows he would to lose to E anyway, due to the others' preferences. And C would rather have D win than E, so C votes for D instead of himself.

 

[JayMan]

That's the whole election, decided right from the start. And E is considered in every step. So it's almost like by going last, unless E can beat everyone, then E can't win at all (not sure if that's precisely true, but that's the gist of my idea - it's harder for E to win because everyone knows in advance how things will shake out, so if there's someone they collectively like better than E, that person will get pushed to the final round).

I agree completely on the fact that the election is set from the start (since preferences are predetermined) - it's a deterministic scenario: ( { [AvD]v[CvD] } v { [bvD]v[CvD] } ) v E.

Maybe I'm the one confused (probably so) - but the fact that 'the politicians preferences are common knowledge' automatically means that one can't adjust his preferences (even before the process) in order to make sure he (or another guy) gets through... cause that would mean 'his preferences are not common knowledge'.

 

[Ignoratio Elenchi]

Maybe I'm the one confused (probably so) - but the fact that 'the politicians preferences are common knowledge' automatically means that one can't adjust his preferences (even before the process) in order to make sure he (or another guy) gets through... cause that would mean 'his preferences are not common knowledge'.

I think we're saying the same thing. A candidate can't and won't adjust his own personal preferences, but when he learns everyone else's preferences he might "adjust" his own voting strategy. If I prefer A to B, then in the first round I'd normally vote for A. But if I know everyone else's preferences, and can see that A would lose to E eventually, but B wouldn't (and I prefer both to E), then I'm "switching" my vote to B. (Not really "switching" anything, of course - as you noted once the preferences are known by all participants the voting is deterministic and the winner is known, the actual voting is basically a formality.)

 

[heckmanm]

That's the whole election, decided right from the start. And E is considered in every step. So it's almost like by going last, unless E can beat everyone, then E can't win at all (not sure if that's precisely true, but that's the gist of my idea - it's harder for E to win because everyone knows in advance how things will shake out, so if there's someone they collectively like better than E, that person will get pushed to the final round).

I agree completely on the fact that the election is set from the start (since preferences are predetermined) - it's a deterministic scenario: ( { [AvD]v[CvD] } v { [bvD]v[CvD] } ) v E.

Maybe I'm the one confused (probably so) - but the fact that 'the politicians preferences are common knowledge' automatically means that one can't adjust his preferences (even before the process) in order to make sure he (or another guy) gets through... cause that would mean 'his preferences are not common knowledge'.

It's hard to get my head around "each candidate has a preferred order (with himself first, of course)" but also "each candidate may vote against himself if it benefits him". Seems like it would go this way, with each candidate running the election in reverse (mentally) before voting:

1. The 4th round (x vs E) would go strictly by each candidate's preference (as was stated above) in each possible matchup. Therefore there is a set of candidates N who could win the election.

1a, If N contains only E, the election is over, as E would beat all contenders

2. In the 3rd round (x vs D), each candidate will vote for their highest ranked candidate in (N), which must contain at least D if we get here. There is a set of candidates M who could win the round.

2a. There is no point in voting for a candidate not in N here, as they have no chance to win, and the vote would be wasted, rather than influencing the outcome.

2b. If M contains only D and E, the election is over, and the outcome is the D vs E result from 1 above

3. In the 2nd round (x vs C), each candidate will vote for their highest ranked candidate in (M), which must contain at least C if we get here. There is a set of candidates L who could win the round.

3a. There is no point in voting for a candidate not in M here, as they have no chance to win, and the vote would be wasted, rather than influencing the outcome.

3b. If L contains only C, D and E, the election is over, and the outcome is the (C vs D) vs E result from 2 and 1 above

etc. but brain starting to hurt

 

[JayMan]

Maybe I'm the one confused (probably so) - but the fact that 'the politicians preferences are common knowledge' automatically means that one can't adjust his preferences (even before the process) in order to make sure he (or another guy) gets through... cause that would mean 'his preferences are not common knowledge'.

I think we're saying the same thing. A candidate can't and won't adjust his own personal preferences, but when he learns everyone else's preferences he might "adjust" his own voting strategy. If I prefer A to B, then in the first round I'd normally vote for A. But if I know everyone else's preferences, and can see that A would lose to E eventually, but B wouldn't (and I prefer both to E), then I'm "switching" my vote to B. (Not really "switching" anything, of course - as you noted once the preferences are known by all participants the voting is deterministic and the winner is known, the actual voting is basically a formality.)

Totally agree on the bold (heckmanm says the same also)... it's only then that we move away from a deterministic scenario (when adjusting voting strategy) to one where it's a cat and mouse game of "I know he knows I like that guy, but he'll lose in the next round to the guy I hate" etc. possibilities - and those, by definition, can't be completely looked at to draw probabilities for each guy

 

[Ignoratio Elenchi]

1. The 4th round (x vs E) would go strictly by each candidate's preference (as was stated above) in each possible matchup. Therefore there is a set of candidates N who could win the election.

1a, If N contains only E, the election is over, as E would beat all contenders

2. In the 3rd round (x vs D), each candidate will vote for their highest ranked candidate in (N), which must contain at least D if we get here.

N doesn't have to contain D. Consider a set of preferences such that only A or E could win the election. In that case, there's no clear winner in the final round so you move back to the penultimate round, but D still isn't a contender.

What you kind of have to do is "replace" each candidate with the winner as you move backwards. II think one way to visualize it is to set up columns for the five candidates, and in each round the n-1 candidates on the left are each run against the candidate on the right. You start at the top and move down until you reach a row that has all the same letter in it (or only a single letter) and that's the winner of the election.

For the original puzzle, we start with:

A B C D E

A-D are each run against E. A, B and D would beat E in the final round, but C wouldn't, so moving back to the prior round we have:

A B E D

Note I replaced C with E, since a vote for C in this round is really a vote for E. Matching the first three up against D gives us:

D D D

At this point there are only Ds left, which means no matter what happens, D will win the election.

For the example where A gives his vote to E, we have:

A B C D E

A E E E

A E E

A E

A

So A wins. Note in the second row, where it's normally "everyone against D" we're not actually comparing A to D, we're comparing A to E (since E would beat D in the final round).

 

[Ignoratio Elenchi]

Maybe I'm the one confused (probably so) - but the fact that 'the politicians preferences are common knowledge' automatically means that one can't adjust his preferences (even before the process) in order to make sure he (or another guy) gets through... cause that would mean 'his preferences are not common knowledge'.

I think we're saying the same thing. A candidate can't and won't adjust his own personal preferences, but when he learns everyone else's preferences he might "adjust" his own voting strategy. If I prefer A to B, then in the first round I'd normally vote for A. But if I know everyone else's preferences, and can see that A would lose to E eventually, but B wouldn't (and I prefer both to E), then I'm "switching" my vote to B. (Not really "switching" anything, of course - as you noted once the preferences are known by all participants the voting is deterministic and the winner is known, the actual voting is basically a formality.)

Totally agree on the bold (heckmanm says the same also)... it's only then that we move away from a deterministic scenario (when adjusting voting strategy) to one where it's a cat and mouse game of "I know he knows I like that guy, but he'll lose in the next round to the guy I hate" etc. possibilities - and those, by definition, can't be completely looked at to draw probabilities for each guy

Maybe we're misunderstanding each other, but I don't believe it's possible to conceive one of those "cat and mouse" games in this puzzle. At one point I was worried that I was overlooking that possibility, but I wasn't. Everything is deterministic because there's no strategy to the final round. Everyone will vote for who they like best because there's no advantage to doing otherwise.

Someone earlier referred to it as WIFOM ("Wine in front of me," from The Princess Bride) In that case there's no solution because ultimately you can't deduce which glass of wine I poisoned.

But in the election, it eventually resolves itself. I could try to trick you, but in the final round of voting there's no point of trickery. I can vote for the person I prefer more, or I can vote for the person I prefer less (but why would I do that?) And because there's no uncertainty about what I'd do in the final round, then there's no uncertainty about what I'd do in any round prior to that either.

 

[JayMan]

And because there's no uncertainty about what I'd do in the final round, then there's no uncertainty about what I'd do in any round prior to that either.

Agree completely on the final round... But I'm not so sure about the previous rounds (I maybe overlooking it), but before the finals - since all 5 candidates can switch their voting strategy on the fly - wouldn't that account for 'Wine in front of me' scenarios?

 

[Ignoratio Elenchi]

And because there's no uncertainty about what I'd do in the final round, then there's no uncertainty about what I'd do in any round prior to that either.

Agree completely on the final round... But I'm not so sure about the previous rounds (I maybe overlooking it), but before the finals - since all 5 candidates can switch their voting strategy on the fly - wouldn't that account for 'Wine in front of me' scenarios?

I don't think so. Here are the preferences from the original puzzle:

Candidate A: A > B > C > D > E

Candidate B: B > A > E > D > C

Candidate C: C > D > A > E > B

Candidate D: D > B > A > E > C

Candidate E: E > D > B > C > A

We know in the final round that A, B and D would beat E, but C wouldn't. There's no mystery, because after this round there's no more voting. And in fact, since everyone already knows exactly what would happen in the final round, there might as well not be any voting in the final round. It's already been determined what will happen.

So when we get to the round before that, what mystery is there? If it's D vs A or D vs B, everyone will just vote for whichever they prefer, since the winner would move on to beat E with 100% certainty. If it's D vs C, that's really the same as D vs E, so everyone will vote for whichever of those two they prefer. And we already know who everyone prefers, so again there's no mystery. (In all of these cases it happens to be D, but that's not the point.) Remember, there's no mystery in the final round because there's no voting after it - well, there's basically no voting in the final round either, and thus there's no mystery in the penultimate round.

It's the same for every round as you move backwards. Because we know exactly what everyone would vote for in the final round, then we know exactly what everyone would vote for in the round before the final round. And then we know exactly what they'd vote for in the round before that, all the way back to the beginning. That's why the puzzle is solvable, all we have to do is trace the preferences backwards and we already know who's going to win.

Could someone deviate from this strategy? Sure, but there would be no point. Any "vote-switching" that would improve the outcome has already been accounted for. If a voter monkeys around and votes for someone we wouldn't have predicted, all they'd end up doing is causing a less favorable outcome for themselves.

 

[heckmanm]

1. The 4th round (x vs E) would go strictly by each candidate's preference (as was stated above) in each possible matchup. Therefore there is a set of candidates N who could win the election.

1a, If N contains only E, the election is over, as E would beat all contenders

2. In the 3rd round (x vs D), each candidate will vote for their highest ranked candidate in (N), which must contain at least D if we get here.

N doesn't have to contain D. Consider a set of preferences such that only A or E could win the election. In that case, there's no clear winner in the final round so you move back to the penultimate round, but D still isn't a contender.

You're right. What I should have said is that N must contain at least one candidate other than E.

I'm trying to write a program to run the election for any randomly-generated set of preferences for each candidate, so that I can then run multiple trials and see if there's a trend toward any particular candidate. So if I can run it 1000 times, do I get 200/200/200/200/200, or some other (significantly different) distribution of wins.

Work is a bit slow this week. I'll tinker around more tomorrow.

 

[Ignoratio Elenchi]

1. The 4th round (x vs E) would go strictly by each candidate's preference (as was stated above) in each possible matchup. Therefore there is a set of candidates N who could win the election.

1a, If N contains only E, the election is over, as E would beat all contenders

2. In the 3rd round (x vs D), each candidate will vote for their highest ranked candidate in (N), which must contain at least D if we get here.

N doesn't have to contain D. Consider a set of preferences such that only A or E could win the election. In that case, there's no clear winner in the final round so you move back to the penultimate round, but D still isn't a contender.

You're right. What I should have said is that N must contain at least one candidate other than E.I'm trying to write a program to run the election for any randomly-generated set of preferences for each candidate, so that I can then run multiple trials and see if there's a trend toward any particular candidate. So if I can run it 1000 times, do I get 200/200/200/200/200, or some other (significantly different) distribution of wins.

Work is a bit slow this week. I'll tinker around more tomorrow.

Random including their preferences for themselves? Or would each candidate still prefer himself first, but then his preferences after that would be random?

Edited to add: Don't want to discourage you from writing a program, I think it's a fun challenge, but I mentioned upthread somewhere that I wrote a program to simulate the elections, not sure if you saw that. So I already know what I believe the answer is, it'll be interesting to see if we come up with the same.

 

[heckmanm]

Random, excluding preferring themselves. I'm making the assumption that if a candidate wasn't his own first preference, he wouldn't be a candidate.