The 538 Riddler: Secret Election

Well, I’m 3-for-3 so far in finding answers to the 538 Riddler and for last week’s answer I got another shoutout from Ollie. This week’s Riddler concerns a secret cabal of politicians who decide to bypass that pesky democratic process and decide among themselves who will become president.

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 (C), 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?

So I was able to work this one out on paper, but I decided to write a program to confirm my answer, which I will show below.

 

So, first let’s look at how I figured out “by hand” the winner of the election. The key here is to look at the last election first, when candidate Eruz will face off against one of the four winners of the previous elections. Using the candidates stated preferences we find:

Aanders vs. Eruz – Aanders would win 4-1.

Blinton vs. Eruz – Blinton would win 3-2.

Cubio vs. Eruz – Eruz would win 3-2.

Drump vs. Eruz – Drump would win 3-2.

Poor candidate Cubio! He literally cannot win no matter what happens with the current voting schedule. What we also see is that any other candidate who survives to the last election vs. Eruz will win. Since all the preferences are known, each of the candidates knows this. Now let’s take a step back and look at the previous election. One of the first three candidates (Aanders, Blinton, or Cubio) will be facing off against candidate Drump.

If these were the last elections, we would see that Drump would beat all three of the preceding candidates. However since we know that Eruz waits to take on the winner, each of these elections becomes a decision between the winner and Eruz:

Aanders vs. Drump = (Aanders vs. Eruz) vs. (Drump vs. Eruz) = (Aanders vs. Drump)

Blinton vs. Drump = (Blinton vs. Eruz) vs. (Drump vs. Eruz) = (Blinton vs. Drump)

Cubio vs. Drump = (Cubio vs. Eruz) vs. (Drump vs. Eruz) = (Eruz vs. Drump)

In all three of those matchups, Drump wins, and so according to the rules setup by the cabal, candidate Drump will win the secret election. It’s interesting to note that even if Cubio were favored in a head-to-head matchup with Drump in the 3rd round, game theory would dictate that the other candidates would still vote for Drump since they know Cubio would be destined to lose to Eruz in the final round, and they prefer Drump over Eruz.

Here’s my “scratch pad” answer to the first question:

Normal election:
AvE = A
BvE = B
CvE = E
DvE = D
so...
AvD = (AvE)v(DvE) = AvD = D
BvD = (BvE)v(DvE) = BvD = D
CvD = (CvE)v(DvE) = EvD = D
D wins the election.

Let’s look at the remaining questions from 538:

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?

Okay, so now we have a wrinkle where candidate Aanders has the opportunity to select another candidate as a proxy. I should say that my answer to these questions about who Aanders should choose as a proxy, and whether Aanders should purposely miss the vote, depend on the idea that all candidates will know who Aanders has chosen as a proxy, and who that person will vote for. If that’s not the case, then I think it could get pretty tricky.

Here are the four different scenarios for elections where Aanders misses the vote, and chooses Blinton, Cubio, Drump, and Eruz as proxies:

A selects B as a proxy:
AvE = A
BvE = B
CvE = E
DvE = E
so...
AvD = (AvE)v(DvE) = AvE = A
BvD = (BvE)v(DvE) = BvE = B
CvD = (CvE)v(DvE) = EvE = E
so...
AvC = (AvD)v(CvD) = AvE = A
BvC = (BvD)v(CvD) = BvE = B
so...
AvB = (AvC)v(BvC) = AvB = B
B wins the election.

_______________________________________
A selects C as a proxy:
AvE = A
BvE = E
CvE = E
DvE = D
so...
AvD = (AvE)v(DvE) = AvD = D
BvD = (BvE)v(DvE) = EvD = D
CvD = (CvE)v(DvE) = EvD = D
D wins the election.

_______________________________________
A selects D as a proxy:
AvE = A
BvE = B
CvE = E
DvE = D
so...
AvD = (AvE)v(DvE) = AvD = D
BvD = (BvE)v(DvE) = BvD = D
CvD = (CvE)v(DvE) = EvD = D
D wins the election.

_______________________________________
A selects E as a proxy:
AvE = A
BvE = E
CvE = E
DvE = E
so...
AvD = (AvE)v(DvE) = AvE = A
BvD = (BvE)v(DvE) = EvE = E
CvD = (CvE)v(DvE) = EvE = E
so...
AvC = (AvD)v(CvD) = AvE = A
BvC = (BvD)v(CvD) = EvE = E
so...
AvB = (AvC)v(BvC) = AvE = A
A wins the election!

So if Aanders chooses Blinton, Blinton wins. If Aanders chooses Cubio or Drump, then Drump wins. (Poor Cubio can’t even win when controlling two votes!) But Aanders can win the election by choosing his most ideologically opposed candidate as a proxy. Weird! So the answer to question 4 is, yes of course get the flu vaccine (vaccines are good), but pretend to be sick anyway and name candidate Eruz as your proxy, Mr. Aanders.

As I said, I was able to do this on paper by hand, but I decided to write a program to do it anyway. I set up a C++ class called Candidate which is initialized with a list of other candidate preferences in the form of a 5-character string like “ABCDE” for Aanders. Those preferences are used to give a score to each candidate and then the Candidate class can be queried for its preference between two candidates.

It’s possible to designate a proxy candidate which will be queried instead by calling SetProxy. Here’s Candidate:

#define CANDIDATE_COUNT 5

class Candidate
{
char m_id;
int m_scores[CANDIDATE_COUNT];
const Candidate *m_proxy;

public:
Candidate(const char *rankings) : m_proxy(NULL)
{
m_id = rankings[0];
for(int cand = 0; cand < CANDIDATE_COUNT; cand++)
{
m_scores[rankings[cand] - 'A'] = CANDIDATE_COUNT - cand;
}
}
// allow another candidate to vote for me
void SetProxy(const Candidate *proxy) {m_proxy = proxy;}

bool RawPreference(char a, char b) const
{
// if a proxy has been designated, ask it
if(m_proxy != NULL && m_proxy != this)
return m_proxy->RawPreference(a, b);

// otherwise return true if our score for the first candidate is
// greater than the second's score
if(m_scores[a - 'A'] > m_scores[b - 'A'])
return true;
return false;
}
};

Now we need a class to represent the election called, well, Election. Election creates 5 candidates with their respective preferences. A function called SimulateElectionWithAbsenteeAndProxy allows the election to be run, and if values are set for the absentee and proxy parameters, any candidate can be set as absent with any other candidate set as its proxy. (A function called SimulateElection calls it with absentee and proxy set to 0 to signify no absentees.) Here’s Election:

class Election
{
public:
Election()
{
const char *c_rankings[] = {
"ABCDE", "BAEDC", "CDAEB", "DBAEC", "EDBCA"
};

for(int i = 0; i < CANDIDATE_COUNT; i++)
{
m_candidates[i] = new Candidate(c_rankings[i]);
}
}
virtual ~Election()
{
for(int i = 0; i < CANDIDATE_COUNT; i++)
delete m_candidates[i];
}

void SimulateElection()
{
SimulateElectionWithAbsenteeAndProxy(0, 0);
}

void SimulateElectionWithAbsenteeAndProxy(char absentee, char proxy)
{
m_matchups.clear();
if(absentee != proxy && absentee >= 'A' && absentee <= 'E')
{
GetCandidate(absentee)->SetProxy(GetCandidate(proxy));
printf("Simulating election with %c selecting %c as a proxy:\n", absentee, proxy);
}
else
{
printf("Simulating normal election:\n");
}
char winner = Vote('A', 'B');

if(absentee != proxy)
{
printf("When %c was the proxy for %c, %c won.\n\n", proxy, absentee, winner);
GetCandidate(absentee)->SetProxy(NULL);
}
else
{
printf("In a normal election, %c wins.\n\n", winner);
}
}

private:
Candidate *m_candidates[CANDIDATE_COUNT];

std::hash_map<std::string, char> m_matchups;

Candidate *GetCandidate(char c)
{
return m_candidates[c - 'A'];
}

char Vote(char c1, char c2)
{
char resultKey[4] = "XvX";
resultKey[0] = min(c1, c2);
resultKey[2] = max(c1, c2);

auto itr = m_matchups.find(resultKey);
if(itr != m_matchups.end())
{
return itr->second;
}

if(c2 < 'E')
{
// the vote boils down to a choice between the winner of
// these two candidates vs the next candidate
c1 = Vote(c1, c2 + 1);
c2 = Vote(c2, c2 + 1);
}

int c1Score = 0;
for(int i = 0; i < CANDIDATE_COUNT; i++)
{
if(GetCandidate('A' + i)->RawPreference(c1, c2))
c1Score++;
}

char winner = (c1Score >= 3) ? c1 : c2;
printf(" Evaluating %s is same as (%cv%c) = %c\n", resultKey, c1,c2, winner);
m_matchups[resultKey] = winner;

return winner;
}
};

The key to the SimulateElection function is the Vote function. Vote is recursive and hinges on these lines:

if(c2 < 'E')
{
// the vote boils down to a choice between the winner of
// these two candidates vs the next candidate
c1 = Vote(c1, c2 + 1);
c2 = Vote(c2, c2 + 1);
}

If the second candidate passed into Vote is not Eruz, then we know that we need to look ahead to find out what the results of picking each candidate would be in future rounds of voting. This is done by setting the c1 and c2 variables to be the result of recursively calling Vote with (c1, c2+1) and (c2, c2 + 1).

Once I get the results of all future round combinations, I can compare the returned c1 and c2 candidates to see which each of the candidates prefer. That candidate is then considered the winner of that matchup between the two original candidates. (This means that the stored winner of the matchup “BvC” might be “D”.)

With the number of candidates at only 5 we could safely just use the recursive method here and not worry about it, but I use memoization to keep runtime complexity reasonable; I cache previous results using a hash_map so I can quickly look them up.

Finally, once I was able to specify any candidate as an absentee with any other candidate as a proxy, I decided to check all possible absentee/proxy combinations. It should come as no surprise that candidate Eruz can’t win the election no matter what happens; however, candidate Cubio CAN win the election for several of these combinations. Here’s the output of all the different combinations:

Simulating normal election:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = D
 Evaluating AvD is same as (AvD) = D
 Evaluating CvE is same as (CvE) = E
 Evaluating CvD is same as (EvD) = D
 Evaluating AvC is same as (DvD) = D
 Evaluating BvE is same as (BvE) = B
 Evaluating BvD is same as (BvD) = D
 Evaluating BvC is same as (DvD) = D
 Evaluating AvB is same as (DvD) = D
In a normal election, D wins.

Simulating election with A selecting B as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = E
 Evaluating AvD is same as (AvE) = A
 Evaluating CvE is same as (CvE) = E
 Evaluating CvD is same as (EvE) = E
 Evaluating AvC is same as (AvE) = A
 Evaluating BvE is same as (BvE) = B
 Evaluating BvD is same as (BvE) = B
 Evaluating BvC is same as (BvE) = B
 Evaluating AvB is same as (AvB) = B
When B was the proxy for A, B won.

Simulating election with A selecting C as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = D
 Evaluating AvD is same as (AvD) = D
 Evaluating CvE is same as (CvE) = E
 Evaluating CvD is same as (EvD) = D
 Evaluating AvC is same as (DvD) = D
 Evaluating BvE is same as (BvE) = E
 Evaluating BvD is same as (EvD) = D
 Evaluating BvC is same as (DvD) = D
 Evaluating AvB is same as (DvD) = D
When C was the proxy for A, D won.

Simulating election with A selecting D as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = D
 Evaluating AvD is same as (AvD) = D
 Evaluating CvE is same as (CvE) = E
 Evaluating CvD is same as (EvD) = D
 Evaluating AvC is same as (DvD) = D
 Evaluating BvE is same as (BvE) = B
 Evaluating BvD is same as (BvD) = D
 Evaluating BvC is same as (DvD) = D
 Evaluating AvB is same as (DvD) = D
When D was the proxy for A, D won.

Simulating election with A selecting E as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = E
 Evaluating AvD is same as (AvE) = A
 Evaluating CvE is same as (CvE) = E
 Evaluating CvD is same as (EvE) = E
 Evaluating AvC is same as (AvE) = A
 Evaluating BvE is same as (BvE) = E
 Evaluating BvD is same as (EvE) = E
 Evaluating BvC is same as (EvE) = E
 Evaluating AvB is same as (AvE) = A
When E was the proxy for A, A won.

Simulating election with B selecting A as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = D
 Evaluating AvD is same as (AvD) = D
 Evaluating CvE is same as (CvE) = C
 Evaluating CvD is same as (CvD) = C
 Evaluating AvC is same as (DvC) = C
 Evaluating BvE is same as (BvE) = B
 Evaluating BvD is same as (BvD) = D
 Evaluating BvC is same as (DvC) = C
 Evaluating AvB is same as (CvC) = C
When A was the proxy for B, C won.

Simulating election with B selecting C as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = D
 Evaluating AvD is same as (AvD) = D
 Evaluating CvE is same as (CvE) = C
 Evaluating CvD is same as (CvD) = C
 Evaluating AvC is same as (DvC) = C
 Evaluating BvE is same as (BvE) = E
 Evaluating BvD is same as (EvD) = D
 Evaluating BvC is same as (DvC) = C
 Evaluating AvB is same as (CvC) = C
When C was the proxy for B, C won.

Simulating election with B selecting D as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = D
 Evaluating AvD is same as (AvD) = D
 Evaluating CvE is same as (CvE) = E
 Evaluating CvD is same as (EvD) = D
 Evaluating AvC is same as (DvD) = D
 Evaluating BvE is same as (BvE) = B
 Evaluating BvD is same as (BvD) = D
 Evaluating BvC is same as (DvD) = D
 Evaluating AvB is same as (DvD) = D
When D was the proxy for B, D won.

Simulating election with B selecting E as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = D
 Evaluating AvD is same as (AvD) = D
 Evaluating CvE is same as (CvE) = E
 Evaluating CvD is same as (EvD) = D
 Evaluating AvC is same as (DvD) = D
 Evaluating BvE is same as (BvE) = E
 Evaluating BvD is same as (EvD) = D
 Evaluating BvC is same as (DvD) = D
 Evaluating AvB is same as (DvD) = D
When E was the proxy for B, D won.

Simulating election with C selecting A as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = D
 Evaluating AvD is same as (AvD) = A
 Evaluating CvE is same as (CvE) = E
 Evaluating CvD is same as (EvD) = D
 Evaluating AvC is same as (AvD) = A
 Evaluating BvE is same as (BvE) = B
 Evaluating BvD is same as (BvD) = B
 Evaluating BvC is same as (BvD) = B
 Evaluating AvB is same as (AvB) = B
When A was the proxy for C, B won.

Simulating election with C selecting B as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = E
 Evaluating AvD is same as (AvE) = A
 Evaluating CvE is same as (CvE) = E
 Evaluating CvD is same as (EvE) = E
 Evaluating AvC is same as (AvE) = A
 Evaluating BvE is same as (BvE) = B
 Evaluating BvD is same as (BvE) = B
 Evaluating BvC is same as (BvE) = B
 Evaluating AvB is same as (AvB) = B
When B was the proxy for C, B won.

Simulating election with C selecting D as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = D
 Evaluating AvD is same as (AvD) = D
 Evaluating CvE is same as (CvE) = E
 Evaluating CvD is same as (EvD) = D
 Evaluating AvC is same as (DvD) = D
 Evaluating BvE is same as (BvE) = B
 Evaluating BvD is same as (BvD) = D
 Evaluating BvC is same as (DvD) = D
 Evaluating AvB is same as (DvD) = D
When D was the proxy for C, D won.

Simulating election with C selecting E as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = E
 Evaluating AvD is same as (AvE) = A
 Evaluating CvE is same as (CvE) = E
 Evaluating CvD is same as (EvE) = E
 Evaluating AvC is same as (AvE) = A
 Evaluating BvE is same as (BvE) = B
 Evaluating BvD is same as (BvE) = B
 Evaluating BvC is same as (BvE) = B
 Evaluating AvB is same as (AvB) = B
When E was the proxy for C, B won.

Simulating election with D selecting A as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = D
 Evaluating AvD is same as (AvD) = A
 Evaluating CvE is same as (CvE) = C
 Evaluating CvD is same as (CvD) = C
 Evaluating AvC is same as (AvC) = A
 Evaluating BvE is same as (BvE) = B
 Evaluating BvD is same as (BvD) = B
 Evaluating BvC is same as (BvC) = B
 Evaluating AvB is same as (AvB) = A
When A was the proxy for D, A won.

Simulating election with D selecting B as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = E
 Evaluating AvD is same as (AvE) = A
 Evaluating CvE is same as (CvE) = E
 Evaluating CvD is same as (EvE) = E
 Evaluating AvC is same as (AvE) = A
 Evaluating BvE is same as (BvE) = B
 Evaluating BvD is same as (BvE) = B
 Evaluating BvC is same as (BvE) = B
 Evaluating AvB is same as (AvB) = B
When B was the proxy for D, B won.

Simulating election with D selecting C as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = D
 Evaluating AvD is same as (AvD) = D
 Evaluating CvE is same as (CvE) = C
 Evaluating CvD is same as (CvD) = C
 Evaluating AvC is same as (DvC) = C
 Evaluating BvE is same as (BvE) = E
 Evaluating BvD is same as (EvD) = D
 Evaluating BvC is same as (DvC) = C
 Evaluating AvB is same as (CvC) = C
When C was the proxy for D, C won.

Simulating election with D selecting E as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = E
 Evaluating AvD is same as (AvE) = A
 Evaluating CvE is same as (CvE) = E
 Evaluating CvD is same as (EvE) = E
 Evaluating AvC is same as (AvE) = A
 Evaluating BvE is same as (BvE) = E
 Evaluating BvD is same as (EvE) = E
 Evaluating BvC is same as (EvE) = E
 Evaluating AvB is same as (AvE) = A
When E was the proxy for D, A won.

Simulating election with E selecting A as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = D
 Evaluating AvD is same as (AvD) = A
 Evaluating CvE is same as (CvE) = C
 Evaluating CvD is same as (CvD) = C
 Evaluating AvC is same as (AvC) = A
 Evaluating BvE is same as (BvE) = B
 Evaluating BvD is same as (BvD) = B
 Evaluating BvC is same as (BvC) = B
 Evaluating AvB is same as (AvB) = A
When A was the proxy for E, A won.

Simulating election with E selecting B as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = D
 Evaluating AvD is same as (AvD) = A
 Evaluating CvE is same as (CvE) = E
 Evaluating CvD is same as (EvD) = D
 Evaluating AvC is same as (AvD) = A
 Evaluating BvE is same as (BvE) = B
 Evaluating BvD is same as (BvD) = B
 Evaluating BvC is same as (BvD) = B
 Evaluating AvB is same as (AvB) = B
When B was the proxy for E, B won.

Simulating election with E selecting C as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = D
 Evaluating AvD is same as (AvD) = D
 Evaluating CvE is same as (CvE) = C
 Evaluating CvD is same as (CvD) = C
 Evaluating AvC is same as (DvC) = C
 Evaluating BvE is same as (BvE) = B
 Evaluating BvD is same as (BvD) = D
 Evaluating BvC is same as (DvC) = C
 Evaluating AvB is same as (CvC) = C
When C was the proxy for E, C won.

Simulating election with E selecting D as a proxy:
 Evaluating AvE is same as (AvE) = A
 Evaluating DvE is same as (DvE) = D
 Evaluating AvD is same as (AvD) = D
 Evaluating CvE is same as (CvE) = E
 Evaluating CvD is same as (EvD) = D
 Evaluating AvC is same as (DvD) = D
 Evaluating BvE is same as (BvE) = B
 Evaluating BvD is same as (BvD) = D
 Evaluating BvC is same as (DvD) = D
 Evaluating AvB is same as (DvD) = D
When D was the proxy for E, D won.

And here’s the entire SecretElection.cpp file:

// SecretElection.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <hash_map>
#include <string>

#define min(a,b) ((a) < (b)) ? (a) : (b)
#define max(a,b) ((a) > (b)) ? (a) : (b)

#define CANDIDATE_COUNT 5

class Candidate
{
char m_id;
int m_scores[CANDIDATE_COUNT];
const Candidate *m_proxy;

public:
Candidate(const char *rankings) : m_proxy(NULL)
{
m_id = rankings[0];
for(int cand = 0; cand < CANDIDATE_COUNT; cand++)
{
m_scores[rankings[cand] - 'A'] = CANDIDATE_COUNT - cand;
}
}
// allow another candidate to vote for me
void SetProxy(const Candidate *proxy) {m_proxy = proxy;}

bool RawPreference(char a, char b) const
{
// if a proxy has been designated, ask it
if(m_proxy != NULL && m_proxy != this)
return m_proxy->RawPreference(a, b);

// otherwise return true if our score for the first candidate is
// greater than the second's score
if(m_scores[a - 'A'] > m_scores[b - 'A'])
return true;
return false;
}
};

class Election
{
public:
Election()
{
const char *c_rankings[] = {
"ABCDE", "BAEDC", "CDAEB", "DBAEC", "EDBCA"
};

for(int i = 0; i < CANDIDATE_COUNT; i++)
{
m_candidates[i] = new Candidate(c_rankings[i]);
}
}
virtual ~Election()
{
for(int i = 0; i < CANDIDATE_COUNT; i++)
delete m_candidates[i];
}

void SimulateElection()
{
SimulateElectionWithAbsenteeAndProxy(0, 0);
}

void SimulateElectionWithAbsenteeAndProxy(char absentee, char proxy)
{
m_matchups.clear();
if(absentee != proxy && absentee >= 'A' && absentee <= 'E')
{
GetCandidate(absentee)->SetProxy(GetCandidate(proxy));
printf("Simulating election with %c selecting %c as a proxy:\n", absentee, proxy);
}
else
{
printf("Simulating normal election:\n");
}
char winner = Vote('A', 'B');

if(absentee != proxy)
{
printf("When %c was the proxy for %c, %c won.\n\n", proxy, absentee, winner);
GetCandidate(absentee)->SetProxy(NULL);
}
else
{
printf("In a normal election, %c wins.\n\n", winner);
}
}

private:
Candidate *m_candidates[CANDIDATE_COUNT];

std::hash_map<std::string, char> m_matchups;

Candidate *GetCandidate(char c)
{
return m_candidates[c - 'A'];
}

char Vote(char c1, char c2)
{
char resultKey[4] = "XvX";
resultKey[0] = min(c1, c2);
resultKey[2] = max(c1, c2);

auto itr = m_matchups.find(resultKey);
if(itr != m_matchups.end())
{
return itr->second;
}

if(c2 < 'E')
{
// the vote boils down to a choice between the winner of
// these two candidates vs the next candidate
c1 = Vote(c1, c2 + 1);
c2 = Vote(c2, c2 + 1);
}

int c1Score = 0;
for(int i = 0; i < CANDIDATE_COUNT; i++)
{
if(GetCandidate('A' + i)->RawPreference(c1, c2))
c1Score++;
}

char winner = (c1Score >= 3) ? c1 : c2;
printf(" Evaluating %s is same as (%cv%c) = %c\n", resultKey, c1,c2, winner);
m_matchups[resultKey] = winner;

return winner;
}
};

int _tmain(int argc, _TCHAR* argv[])
{
Election e;

e.SimulateElection();
for(char absentee = 'A'; absentee <= 'E'; absentee++)
{
for(char proxy = 'A'; proxy <= 'E'; proxy++)
{
if(absentee != proxy)
e.SimulateElectionWithAbsenteeAndProxy(absentee, proxy);
}
}

return 0;
}

Thanks for reading!

UPDATE: For a dynamic programming example of how to solve this, see my next post. And since WordPress has once again destroyed my code formatting, here’s a post with all the latest links to the code.

Author: Wiesman

Husband, father, video game developer, liberal, and perpetual Underdog.

7 thoughts on “The 538 Riddler: Secret Election”

    1. Thanks! Ugh, WordPress is so frustrating with the indenting. I can sometimes get it to work but if I make any edits at all, it will sometimes revert to completely unindented. Still can’t figure it out but I am looking at alternatives for posting code. Hopefully future posts will be more legible.

      Doesn’t Python use indentation as logical signifiers for blocks? It’s a good thing I’m not using it or WordPress would actually change the functionality of the code. LOL.

  1. I think that your logic is incorrect here. The rules of the riddle here clearly state AvB is decided first and the winner of that with C and so forth. If you think about it is just one pass of a bubble sort accross the list of candidates using the sum of each voter’s preference as the comparison (apply 1*delegate multiplier as the value of each person’s vote).

    If you think of it this way, A can never get past the first round, no matter whom he votes for. Also, being sick/absent has no influence to the voting as D will always win (as long as he provides his delegate powers according to whom he wants to win, which would be to C or D).

    to break it down
    legend:
    voter – voter’s choice

    AvB
    A – A
    B – B
    C – A
    D – B
    E – B
    (it doesn’t matter whom A assigns as his delegate here… he’ll never get past)

    I won’t fill out the rest but you can finish it yourself…. D will always win and if A is gone he needs to give his vote to C or D.

    1. The rules of the riddle also clearly state that the candidates are forward-looking and vote strategically and that the preferences of the candidates are known. These are common game theory signifiers, but I could be wrong.

      Either way, we will see the answer on Friday.

Disagree?

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s