Puzzles about or related to Voting & Democracy

Please only ask for at most one solution at a time, i.e. all passwords except one should be left blank! (Hit the "reset" button to make all blank.) Puzzles range from "easy" to "so hard nobody can currently solve them" (i.e. "open"); we've taken pity on you by giving a very-subjective "difficulty level" from [0] to [9]. If you can solve one of the open [9] problems please let warren.wds at gmail.com know! [You can also contribute new puzzles to him...]

For terminology, it may help to consult our glossary. "Range Voting" will generally mean "continuum range voting" and not range voting with scores restricted to the discrete set {0,1,...,99} for mathematical analysis purposes.
(Return to main page. See puzzle index. Puzzle answers only available to those who know the password, i.e, CRV members! Join CRV)

Feb 2007: All three original wide-open math problems have now been (pretty much) knocked off by the combined efforts of W.D.Smith & Forest W. Simmons! They're being demoted to ≤[8] and we added some new [9]s!


Puzzle #0 (Voting power – ultra-easy speed problem):
[0] Three stockholders own 47%, 34%, and 19% of the stock in some corporation, respectively. What are their relative powers in a 2-way vote?

Type password to get answer:

Puzzle #1: The minimum it takes to elect US president:
[1] What is the smallest percentage of votes needed to elect a US president? (Assume 2004's population distribution, and a 2-candidate race; disallow "faithless electors," and assume no need to send any election to coin-tossing, congress, or the courts for resolution. Assume state turnouts proportional to populations – or don't [which leads to a different answer].)

Type password to get answer:

Puzzle #2: Small elections in which many voting systems all disagree:
[5] Find an example election in which Approval Voting, Borda Voting, Plurality Voting, Plurality Voting with Top-Two Runoff, Instant Runoff Voting (IRV), and Condorcet methods, all return different unique-winners. Election examples with fewer voters and fewer voter-types are preferred as "more elegant."

Type password to get answer:

Puzzle #3 (interesting – easy once you see it, otherwise hard!):
[4] Three people enter a room and a red or blue mark is made on each person's forehead. The color of each mark is determined by a coin toss, with the outcome of one coin toss having no effect on the others. Each person can see the others' marks but not his own.
No communication of any sort is allowed, except for an initial strategy session before the game begins. Once they have had a chance to look at the other marks, they must (simultaneously) guess the color of their own marks, or pass. The group shares a hypothetical $3 million prize if at least one player guesses correctly and none guess incorrectly.
The problem is to find a strategy for the group maximizing its chances of winning the prize.
For example, one obvious strategy for the players would be for one player always to guess "red" while the others pass. That would give the group a 50% chance of winning the prize. Can the group do better?

Type password to get answer:

Puzzle #4: Non-monotonicity probabilities in IRV voting:
[6] Consider 17 voters electing one winner from 3 candidates using IRV (Instant Runoff) voting. (Each vote is a preference ordering among the three candidates; the candidate with the fewest top-rank votes is eliminated repeatedly until only one – the winner – remains.) Among all the possible elections of this sort: what fraction have the unhappy "non-monotonic" property that the winner would have lost to some loser L, if only some subset of identically-voting voters had changed their top-rankings away from L? (Disallow elections involving ties.)

Extra credit: What if, instead of 17 voters, we allow the number of voters to tend to infinity?

Open: Solved! [8] What if we then also allow the number of candidates to tend to infinity?

Type password to get answer:

Puzzle #5 (open now solved! – voting systems obeying both ICC and AFB):
[7] Two desirable properties of a voting system – both of which Range Voting has – are "immunity to candidate-cloning" (ICC) and "avoiding favorite betrayal" (AFB).
AFB: voters should never have strategic incentive to "betray" their favorite candidate by voting him below some other.
ICC: political parties should be unable to usefully manipulate an election by running clones of their own, or of an opposed, candidate; voters here are assumed to vote honestly and to have only tiny preferences (which they may express in their votes, if they exist) among the clones.
In contrast: the USA's present "plurality" voting system fails both tests: It was strategically unwise in Florida in 2000 to vote for Nader even if he was your favorite; and by sponsoring extra "clones" of your top opponent, that can cause their vote to be split and hence cause both clones to lose, and you to win.
Question: Is range voting (and obvious variants of it) the only nontrivial single-winner voting system to satisfy both properties? (A "voting system" inputs a set of votes and [deterministically] outputs the name of a winner. The votes are numerical scores for some-or-all candidates, or rank-orderings of some-or-all candidates, optionally with ranking-equalities permitted.)
Note: Many voting systems are known (beyond just variants of range voting) which satisfy AFB, and many also are known (such as Schulze beatpaths, IRV, [but not BTR-IRV!], Woodall-DAC, and Heitzig River) that satisfy ICC. But I do not know of any systems besides range voting variants which satisfy both simultaneously.
Partial credit: Must any such system employ continuum votes? What if the problem is restricted to systems based on pure-rank-order ballots (with candidate-equalities forbidden)?

Type password to get answer:

Puzzle #6: Dice:
[2] Suppose there are 4 dice: Blue, Green, Red, and White. These dice have different numbers than usual printed on their six faces. After observing a long sequence of experiments rolling pairs of these dice, you conclude that

You are now asked to consider rolling the blue and white dice simultaneously. What can you conclude about the probability P that the blue die will produce a higher value than the white one? (Is P>50%?)

Type password to get answer:

Puzzle #7: Probabilities of "Condorcet cycles."
[6] Assume there are V voters, V large, each of whom cast any of the 6 possible votes A>B>C, B>A>C, A>C>B, B>C>A, C>A>B, C>B>A randomly, independently, and with equal likelihood for all 6 votes, in a 3-candidate Condorcet election. In other words, all 6V elections are equally likely.

Then: what is the probability of an A>B>C>A clockwise "Condorcet preference cycle"?

Extra credit: what about if we now permit candidate-equalities in votes so that twelve votes

C>A>B, C>B>A, B>A>C, B>C>A, A>B>C, A>C>B,
C>A=B, C=B>A, B=A>C, B>C=A, A>B=C, A=C>B
become possible. If all 12V elections are now considered equally likely, then what is the probability of an A>B>C>A clockwise "Condorcet cycle"?

Type password to get answer:

Puzzle #8: Probabilities of Favorite-Betrayal Lesser-Evil scenarios with Condorcet voting in 3-candidate elections with equal rankings permitted:
[6] Again suppose there are V voters and all 12V elections are equally likely. We shall only be interested in the V→∞ limit. Suppose the election proceeds as follows. If a candidate exists who pairwise-beats (or at least ties) every other, then he is the winner. (And we disallow elections with more than one winner.) Otherwise, the candidate X, suffering at most one pairwise defeat and with that defeat being the "weakest," wins.

There are two possible ways to define that Y>X is the "weakest defeat":

  1. "Margins": the difference between the number of Y>X voters and X>Y voters is minimal.
  2. "Winning votes": There are the fewest voters ranking Y>X in the defeat of X by Y (we ignore the number of X>Y and X=Y voters, so long as this is a defeat, i.e. the number of Y>X voters exceed the number of X>Y voters).

In either system: what is the probability that this election will include a "Favorite-Betrayal Lesser-Evil (FBLE) scenario" in which, say, A wins, but some "C-top and B>A" voters by dishonestly rating their favorite C below top, can cause the "lesser evil" B to win instead of A (a result they prefer)? Note: It only counts as FBLE if those voters can only achieve their B-wins goal by demoting C below top.

Type password to get answer:

Puzzle #9 (open now solved! – voting systems in which semi-honest voting is strategic):
[7] Let a "voting system" mean a map from a set of votes (each a rank-ordering of the candidates with equality-rankings permitted, or an assignment of a real number score in [0,1] to each candidate) to the identity of a single "winner" candidate.

Call a voter's vote X "semi-honest" if it, while perhaps differing from his honest opinion, has the same rank-ordering as a limit of a sequence of score-assignments that agree in their ordering with the honest one. For example, if the voter honestly feels A>B=C>D>E, then a vote A=B=C>D=E would be semi-honest, a vote A>B=C>D>E would be honest and hence automatically semi-honest, but both B>A and B>C would be dishonest statements that are not even semi-honest.

Question: Does there exist a nontrivial voting system for 4-candidate elections in which semi-honest voting is always strategically optimal? (Range voting has this property for elections with ≤3 candidates.)

Type password to get answer:

Puzzle #10 (cake cutting):
[6] A well known way to cut a cake into two pieces that assures that each person gets at least half of the value of the cake (where the two players may value different cake-parts differently, e.g. one likes chocolate and another likes cherries) is the "cut and choose" protocol where player A cuts the cake and then player B chooses his piece.

Can you devise a similar protocol for three cake-eating players assuring each will regard his/her piece as containing at least as much value as either one of the other pieces?

Type password to get answer:

Puzzle #11 (pie-style cake cutting):
[7] In the previous problem completely arbitrary styles of cake-cutting were permitted, i.e. players could receive arbitrary-shaped (and perhaps not even connected) pieces. In that case no matter what the number N of players, there always exists a way to cut the cake into N pieces so that each player would regard his own piece as at least as valuable (by his own measure of value) as any of the others.

But now suppose that the cake (regarded as a circular disk) must be cut into wedges along radial line segments, with each player getting exactly one wedge. Then: does a way exist to cut the cake into N pieces so each player regards his own piece as at least as valuable as any of the others? Solve the cases N=3 and N=500.

Type password to get answer:

Puzzle #12 (cutting of 2-dimensional cakes):
[7] Given a 2-dimensional disk "cake" and N players each of whom have (perhaps) different everywhere-positive-and-finite value-densities on that cake. Is it possible to cut the cake into N disjoint pieces, one for each player, such that the players are "envy-free," i.e. regard themselves as owning an at-least-as-valuable piece of the cake as any rival? We ask this question twice:

  1. Under the demand that the pieces be contiguous.
  2. Under the demand that the pieces be convex.

Type password to get answer:

Puzzle #13 (range-voting with outlier-discarding):
[2] Suppose each voter's "vote" is an integer numerical score from 0 to 99 for each candidate, for example a legal vote in a 4-candidate election might be (99, 54, 0, 99). Suppose the "final score" for a candidate is the average of all his scores that remain after you discard the top X% and the bottom X% of them. If X=50, this is just the median score, and if X=0 then this is just the usual kind of range voting. These are both important special cases. But more generally any fixed X with 0≤X≤50 can be considered. One of the advantages of ordinary range voting, which appears to be sacrificed in this more general kind of voting, is the fact that with range voting only a small amount of information may be sent by each precinct to central tabulating, summarizing all the ballots (no matter how many) in that precinct. The entire set of ballots need not be sent.

  1. Show that this "appearance" is delusory – this more general kind of range voting still has the small-amount-of-info-summary-can-be-sent property allowing precincts to do their own "subtotals."
  2. Why is this more-general kind of range voting (with X>0) far less democratic than ordinary range voting (with X=0)?
  3. What bad phenomenon would often happen in practice if median-range-voting (the X=50 special case) were adopted? Hint: consider the French Approval-Voting study.

Type password to get answer:

Puzzle #14 (mostly open – Social science/economics research. Suggested by Aaron Krowne):
[9] Compare macro-economic metrics, including soft ones like "economic freedom" (a number of indexes for this exist). One might hypothesize that countries with "better voting systems" will progress "forward" in these various metrics faster than countries with worse voting systems. There may already be enough historical data in the 20-50 most recent years past to reveal some interesting economic-political correlations. Colloquially, this seems to be happening. Median incomes in the US [which has one of the worst voting systems] continue to fall (since the 70s), the Gini index is rising, class mobility is falling, the prison population is rising (and accelerating), the black market sector is growing, and economic freedom is falling. Meanwhile Ireland and Switzerland [with two of the best, in my opinion, governmental setups] have impressive economies. (2010: Oops! – Ireland's banks just blew sky high due to massive risk taking and speculation, then the government bailed them out sending the ountry into huge debt over 10×GDP, but Ireland was supposedly a great success when we wrote this, i.e. before that happened...)

Type password to get answer:

Puzzle #15 (open now solved! – multiwinner EP & PR voting systems):
[7] The goal of a "multiwinner voting system" is to, from the "votes," determine W winners from C candidates where 0<W<C. The system is "proportional" (PR) if, supposing the voters and candidates each are colored one of a finite number of colors (i.e. voter Joe is "green," candidate Mary is "black"), and supposing each voter prefers each candidate of his own color above all others (and says so in her vote), then the winning slate of candidates will have the same color composition as the voters (up to unavoidable integer-roundoff effects and limitations caused by perhaps too few candidates existing of some color). For example, the famous Hare/Droop-STV system [single transferable vote with "Droop quotas" and "reweighting"] invented by Hare and Droop in 1800s England, is PR. That is, if there are 60% red, 30% black, and 10% white voters, then we will automatically get 6,3, and 1 red, black, and white winners respectively in a Hare/Droop-STV election with W=10 assuming enough candidates of each color are available. The voting system is required to depend upon the votes only, hence does not know the candidate- or voter-colors. "Votes" are either preference orderings or numerical scores (and perhaps other things would also be permissible – if you can solve this we are willing to be generous with the conditions). The system is "efficiently parallelizable" (EP) if an election with an enormous number of voters can be handled by efficient combination of subresults computed in each election district from only the votes in that district, and these subresults consist of a very small amount of data compared to the large number of votes that they summarize. For EP to hold, we require all this data to be transmitted unidirectionally, i.e. voters→district-agency→central-agency. For example the plurality system is EP because each district can simply compute its total vote counts for each candidate, then pass only these subtotals on to the central election agency.

Question: Does there exist a nontrivial multiwinner voting system which is both PR and EP? (And if "yes," then please construct one!)

Type password to get answer:

Puzzle #16 (Raising the mean of both sets by shuffling them – easy):
[0] Suppose you have two sets A and B of numbers. Now rearrange the numbers to get two new sets A' and B' (same numbers, but moved around). For example we could have A={1, 3} and B={2, 4} which after rearrangement becomes A'={1, 2} and B'={3, 4}. Note that in this example, the mean of A decreased but the mean of B increased, with overall mean staying the same.
Question: Is it possible to make the means of both sets increase? (And if "yes," then please construct example!)

Type password to get answer:

Puzzle #17 – Probability of "Peru scenario":
[6] Consider V voters electing one winner from 3 candidates using IRV (Instant Runoff) voting. (Each vote is a preference ordering among the three candidates; the candidate with the fewest top-rank votes is eliminated repeatedly until only one – the winner – remains.) Assume all 6V elections are equally likely.

Question: What is the probability, conditioned on there being a "Condorcet winner" W who would pairwise-beat every other candidate, that W will be eliminated in the first IRV round? (Disallow elections involving ties and concern yourself only with the V→∞ limit.) We call this the "Peru scenario" since it apparently happened in the 2006 Peru national election.

Extra Credit: Also evaluate the same probability in the alternative Dirichlet probabilistic model.

Type password to get answer:

Puzzle #18 – IRV refuses to elect a candidate who beats every other pairwise by 99:1 margin?
[2] In the Instant Runoff (IRV) voting method, Prove it is possible for a candidate L to win, even though a candidate W "should have" won in the sense that, for every candidate X, including X=L, the ballots indicate that W pairwise-beats X by at least a 99:1 margin?

Type password to get answer:

Puzzle #19 – A situation with random other voters where your strategically best range vote is honest.
[4] Suppose there are N>0 voters in addition to you in a range-voting election with 3 candidates. Suppose you know absolutely nothing about how the other N voters voted, i.e. regard all their scores for all candidates as 3N random numbers independently uniform within the permitted range. (Equivalently: regard every possible vote by each of them as equally likely.)

Suppose your true utilities for the elections of the candidates are 0 for the worst candidate, 1000 for the middle candidate, and 2000 for the best candidate.

Prove that for each N>0, including the limit when N→∞, your uniquely strategically-best range vote is the "honest" one (0, 0.5, 1) assuming the score-range is the interval [0,1], and in particular that this honest vote yields superior expected utility for you than either "exaggerated" approval-style vote (0, 0, 1) or (0, 1, 1). Also, prove this is still true even if your utility for the middle candidate is not exactly 1000 – i.e. if it is slightly perturbed away from 1000, with the size of the perturbation being small enough compared to some power of N, then your strategically best range vote is not approval-style.

Type password to get answer:

Puzzle #20 – (partly open) How often do "Condorcet cycles" arise in real elections with rank-order ballots? Give some prominent real historical examples of such elections. [6]

Type password to get answer:

Puzzle #21 – (partly open) how many arcs must be deleted from an n-node directed graph to get rid of all cycles?
[8] Let F(n) denote the maximum, over all n-node directed graphs G (note: singly-directed arcs only; bidirected arcs not allowed), of the minimum number of arcs you need to erase from G in order to cause G to become acyclic. For example, F(2)=0 and F(3)=1. Find values of F(n), upper and lower bounds on F(n), and asymptotics.

Type password to get answer:

Puzzle #22 – How bad can Condorcet cycles be?
[7] As is well known, voters who provide rank-order ballots can create a preference cycle in which each candidate is beaten pairwise by some other (and in which, therefore, it is not easy to claim there is any clear winner). This can happen with 3 candidates. We now investigate just how nasty such things can be.
(a) Is it possible for every pair of candidates to both be pairwise-beaten by some other candidate? If so, find the smallest number of candidates that makes that possible.
(b) Is it possible for every triple of candidates to all three be pairwise-beaten by some other candidate? If so, find the smallest number of candidates that makes that possible.
(c) Is there any upper limit on K such that every K-tuple of candidates can all K be pairwise-beaten by some other candidate?
(d) What is the largest possible number of 3-candidate preference cycles that can occur simultaneously in an N-candidate election?
(e) What is the largest possible number of 4-candidate preference cycles that can occur simultaneously in an N-candidate election?
(f) Is it possible for every 4-tuple of candidates (considered on their own with all others erased from all votes) to contain at least one preference cycle in an N-candidate election with N≥5?

Type password to get answer:

Puzzle #23 – Avoiding favorite-betrayal (Chris Benham):
[2] Is there a nontrivial voting system in which the votes are strict rank-orderings of all the candidates, and in which there is never any strategic incentive for a voter to "betray his favorite" by ranking him below top?

Type password to get answer:

Puzzle #24 – What is the probability plurality elects the candidate a majority least-likes? [6]
(a) Consider 7 voters electing a unique winner from 3 candidates using plurality voting. Among all the possible elections of this sort: what fraction have the unhappy property that a majority of the voters agree that the winner is actually the candidate they least-like? (Assume all 6 possible votes A>B>C, A>C>B, B>A>C< B>C>A, C>A>B, C>B>A equally likely, all voters independent.)
(b) What if now instead of 7 voters, we consider the limit as the number of voters tends to infinity, and ask what is the probability that the plurality winner in a vote for best candidate, coincides with the plurality "winner" in a vote for worst candidate?

(Hint: your probabilities should range between about 2% and 10%.) Type password to get answer:

Puzzle #25 – Pancyclicity:
[6] In any N-player round-robin tournament in which each player has the same score ("score" is number of other players he defeats pairwise; we only consider "win" and "loss" game results with "draws" are forbidden), prove that each pairwise defeat A>B is part of at least one K-player preference cycle (for example, with K=4, a 4-player cycle including A>B might be "A>B>C>D>A", but A>C>B>D>A does not count as a "4-cycle including A>B") and this is simultaneously true for every cycle-length K with 3≤K≤N.

Type password to get answer:

Puzzle #26 – Super-bad tournaments:
[5] Call an N-player round-robin tournament "super-bad" if every player A loses pairwise to some other player, who loses to another,... who loses to player B, i.e. there is a path of pairwise defeats leading from A to B, for every A and B. This seems about as bad as things possibly could be (from the standpoint of determining who should be the "winner") but we shall see that it is an extremely common state of affairs.
(a) Prove a tournament is super-bad if and only if each player is a member of at least one "cycle" of K defeats, for every value of K from 3 to N simultaneously.
(b) Assuming each pairwise defeat-or-victory is determined by a coin flip ("random tournament"), find the probability P(N) that an N-node tournament is super-bad. In particular, compute P(20) accurate to 8 decimals.
(c) Let us say that a player who either pairwise-defeats, or "defeats" via a 2-long path, each other player, has "bragging rights." In the same probabilistic model as in (b), show that, with probability tending exponentially toward 1 as N→∞, every player has bragging rights.
(d) Show that not only does every player A "defeat" every player B via a 2-hop defeat-path AXB, indeed this happens (with probability→1 exponentially as N→∞) for at least N/5 distinct 2-defeat paths. Further, there are (again with probability→1 exponentially as N→∞) at least

(N-2)(N-3)(N-4)···(N+1-L) / (3N)

different L-defeat paths from each A to each B where L=⌊log2N⌋ .

Type password to get answer:

Puzzle #27 – A quantity like the "Ramsey numbers" but defined for directed rather than undirected graphs.
[8] Let R(n) denote the smallest number Q such that every tournament with ≥Q players (i.e, complete directed graph on ≥Q nodes) contains an acyclic n-player subtournament. Re-expressed in voting-theory language: R(n) is the smallest number Q of candidates in a ranked-ballot election, such that it is guaranteed that at least one subset containing at least n of those candidates can be unambiguously ranked in relation to one another! Find values of R(n), upper and lower bounds, and asymptotic behavior. In particular, prove that R(n) grows exponentially with n.

Type password to get answer:

Puzzle #28 – How many votes suffice to create any "tournament" configuration?
[8] In a ranked-ballot voting system,
(a) Show that any "tournament" (i.e. configuration of (n-1)n/2 pairwise-beats relationships among n candidates) is attainable where "A beats B" when more voters say A>B than B>A in their ballots, and there are enough voters. (And let us agree not to allow "ties.")
(b) Define M(n) to be the minimum number of rank-order-ballot votes required to create any n-player tournament in the this way (maximized over all such tournaments; elections with "ties" not permitted). Then show M(2)=1, M(3)=M(4)=M(5)=M(6)=3, and M(n) is always an odd number and M(n+1)≥M(n).
(c) Show M(n)≤2n-1 and M(n)≤n+1.
(d) Show M(n)≥Cn/lg(n) for all sufficiently large n, where lg(X)=log2X, if C is any constant with 0<C<1/2.
(e) Show M(n)≤Kn/lg(n) for all sufficiently large n, for some positive constant K.
(f) But what if, to declare that "A beats B," we need, not a mere majority of voters, but in fact a fraction-f supermajority (for some f=ε+1/2)? Prove then that unattainable tournaments exist (for each ε>0) and indeed that an unattainable tournament with O(ε-2) players exists – and not only exists, but in fact a random tournament of that size is highly likely to be unattainable.

Type password to get answer:

Puzzle #29 – Team comparisons.
[2] Suppose two "teams" of N numbers are compared by comparing the largest number on the first team, with the largest on the second; then the second-largest on the first team, with the second-largest on the second; and so on, with the team that wins the most comparisons being "the better team." (This is actually a pretty realistic model of, e.g, chess teams.)
(team mergers) Suppose A is a better team than B, and C is a better team than D. Does it (or does it not) follow that the union of A and C, is a better team than the union of B and D?
(transitivity) Suppose A is a better team than B, and B is a better team than C. Does it (or does it not) follow that A is a better team than C?
(structures) Which possible "betterness structures" are possible among N-man teams?
("different" comparison method) Suppose we instead compare teams by comparing every number of team #1 with every number on team #2; whichever team wins the most comparisons, is "better." For 3-man teams, show that this "different" method of comparing teams, is actually equivalent to the old method.

Type password to get answer:

Puzzle #30 – Election where Borda and Approval voting maximally disagree.
[2] Find an example election with 4 candidates in which Approval and Borda Voting give reversed results. (Solutions with fewer voters preferred. For extra credit, can you generalize your example to N candidates?)

Type password to get answer:

Puzzle #31 – Election where Borda reverses
[2] Find an example election with N candidates in which Borda Voting gives reversed results when the last-place (or first-place) candidate is removed. Even better: do this for every "weighted positional" voting system.

Type password to get answer:

Puzzle #32 – The "Three Stooges voting problem" (Alan Frieze):
[6] There are 3 candidates for Mayor: A.Moe, B.Larry, and C.Curly. There are N voters and the winner is a function F(x1, x2,..., xN) of the votes of each voter, xj∈{A,B,C}.
Warning: F is not the simple majority function and it is known only to the manufacturers of voting machines. The Stooge Holistic Information Times claims the voting system is "fair" because if yi≠xi for all i∈{1,2,...,N}, then F(x1, x2,..., xN) ≠ F(y1, y2,..., yN).
But conspiracy theorists claim there exists j so that the value of F is completely determined by xj, i.e. some voter j holds total power. Are they right?

Type password to get answer:

Puzzle #33 – (Wisest allocation of vote-weights):
[3] Suppose there are some very large number N of independent voters who need to make a yes/no decision. We suppose this decision has a "right" and "wrong" answer. Suppose voter K would have (independent) probability PK of making the "right" decision on his own. (Hopefully all the PK≥1/2, i.e. hopefully humans are better decision-makers than coin tosses. The PK may differ because some voters are wiser or better informed than others, but we'll assume the PK-1/2 don't vary too tremendously.) Suppose voter K gets to cast WK votes.
Question: What (approximately) is the best choice of the weights WK, maximizing the chance that the collective decision will be the right one?

Type password to get answer:

Puzzle #34 – How much ignoring does Instant Runoff Voting do?
[5] It has often been noted that Instant Runoff Voting (IRV) ignores a large portion of a large number of the votes, which is one reason behind some of the crazy paradoxes IRV suffers. In this puzzle, we shall prove a theorem showing, quantitatively, that IRV always ignores asymptotically all the information in the votes. Suppose there are V voters and C candidates.
A. Prove that IRV never examines more than a fraction (HC-1/2)/C of the CV "cell entries" inside the votes, where Hn=1+1/2+1/3+1/4+...+1/n is the nth "harmonic number." When C=10, this fraction is 6121/25200≈24%, when C=20, it is 15%, and when C→∞ it goes to 0.
B. Prove that IRV usually will not elect Condorcet winners (even when Condorcet Winners exist) in the random election model in the limit C→∞ with V fixed, nor in any limit V,C→∞ with C≥V0.51.

Type password to get answer:

Puzzle #35 – Gerrymandering cancellation theorem
[2] Suppose there are two political parties A & B and two corresponding kinds of voters (all voters are total party-loyalists). Suppose the country is gerrymandered by party A.
(a) What is the largest fraction of congress that they can, by means of that gerrymandering, cause to become As? (Compare with this: in Ohio in 2006, ≈60% of voters voted Democratic, but only 39% of the congressmen they elected were Democratic.)
(b) Now suppose the country instead is optimally-gerrymandered by party B. Prove this theorem: the "double congress" elected via gerrymandering(A) [congress #1] and via gerrymandering(B) [parallel congress #2] is, in net, of the same composition as the electorate.
(c) Does any analogue of the gerrymandering cancellation theorem hold if there are three or more parties and voter-types?

Type password to get answer:

Puzzle #36: Additive utilities:
[5] A common model in social choice theory is one in which each human has a "utility" (real number) for each possible event, and it is deemed "best" to alter events in order to maximize the sum (over all humans) of the utility. In this and the next few puzzles we explore the foundations and limits of that picture.
(a) If the quantity to be maximized is not ∑n Un but rather g(∑n f(Un)) where f and g are some 1-to-1 smooth functions, then argue that this is really just the same thing as the original additive-utility picture. (This is just "utilities in disguise" where f and g are the "disguising functions.")
(b) Recognize that many common symmetric functions in mathematics are just addition in disguise. In particular, do this for the product function ∏n Un, the Lp-norm functions (∑n Unp)1/p with p>0, and (in a limit sense) the max and min functions.
(c) But not every smooth continuous function invariant under permutations of its N arguments, and monotonic in each, is just addition in disguise. When N=3 prove that the "combined addition and multiplication" function abc+a+b+c is not just addition in disguise.
(d) But when N=2 it is: prove that ab+a+b is just addition in disguise.
(c') An example of a 2-person combining function which is not just addition in disguise is ab+ab.
(e) It seems reasonable to demand that any method of combining N real utilities to get a single real "social utility" must

  1. be symmetric, i.e. invariant under permutations of its N arguments,
  2. be smooth and monotonic-increasing in each argument alone,
  3. feature "zero," that is, there exists a "don't give a damn" utility value Z such that combining U with Z always yields U.
  4. feature "inverses," i.e. for each individual utility U, there exists a "negated" utility V such that combining U with V yields a constant value, and in particular, the value Z.
  5. be "self consistent," that is, if you combine a,b,c,d, then you ought to get the same result as combining in pairs such as (a,b) and (c,d) and then combining the resulting two values.
where I have ordered these demands in decreasing order of subjective reasonableness. Prove that these demands force the utility-combining function to be the same thing as real-number addition (or one of its disguises).
(f) Can you argue from biology, human physiology, or biochemistry that additive utility truly does exist?

Type password to get answer:

Puzzle #37: Additive utilities II:
[4] Prove that the following three axioms force any "social utility" to be just the sum of (perhaps "in disguise" as in the previous puzzle) the individual utilities:
Axiom 1. [invariance under voter reordering] Social utility does not depend in which order the voters are permuted.
Axiom 2. [utility-order-invariance under adding a constant] After you add an arbitrary constant C to every utility of some particular voter, then if A was a "better" candidate than B (higher social utility) then it still is.
Axiom 3. [non-silly] With random real number input (i.e. each individual utility independently sampled from some probability density), there will (at least with some positive probability) exist some unique candidate yielding maximum social utility, i.e. the social utility does not merely always say all candidates are equal; and the social utility exists for generic real number input (personal utilities) at least within some neighborhood of the vector with all entries C (for some constant C).

Type password to get answer:

Puzzle #38: NonAdditive utilities:
[4] Criticize the axioms that underlay the preceding two puzzles' proofs that utility-aggregation must be additive. Then consider the following non-additive utility-combining method, suggested by Clay Shentrup:
The "Shentrup Social Utility," as a function of the personal utilities of each of V people, is:

SSU = Maxx   x · (#people whose utility is at least x).
Which of those axioms does SSU obey and which does it disobey?

Type password to get answer:

Puzzle #39: Utility=Log(Wealth)?
[4] Claude Elwood Shannon (and much earlier, Daniel Bernoulli) had the idea that "utility" and "money" were approximately related by the formula utility=log(wealth). Let's explore that.
(a) Show that this formula is consistent with the idea that doubling your wealth causes the same increase in happiness, regardless of your initial wealth.
(b) Suppose you are offered the opportunity to participate in this wager: if event E happens, each dollar you bet is replaced by R>1 dollars; but if E does not happen, you lose all the money you bet. The probability of E is (you believe) P. How much money should you bet, in order to maximize your expected Shannon-utility?
(c) Show that, under the Shannon formula, or indeed any formula of the form utility=ConcaveDownFunction(wealth), removing some money from a random person and giving it to another random other person, decreases the expected sum of utilities, i.e. "random theft is socially bad." [Similarly, making any fair monetary bet causes negative expected utility gain, i.e. such a utility function is "risk averse."] Also, transferring money from poorer to richer people is socially bad, but transferring money from richer to poorer people (provided the rich one stays richer) is socially good.
(d) Criticize the Shannon formula.
(e) How could you try to do a better job than Shannon? Try to devise a formula that smoothly handles negative wealth (i.e. debt). What about wagers involving risk of death? How should a bettor optimally handle them?

Type password to get answer:

Puzzle #40: Feel alike ⇒ vote same?
[5] A single-winner voting system satisfies FAVS if the best strategy for any set of "feel alike" voters is for all members of the set to vote in the same manner.
(a) Show that instant runoff voting (IRV) fails FAVS.
(b) Show that Borda voting fails FAVS.
(c) Show that the Schulze beatpaths Condorcet method (with Simpson-Kramer min max as a tiebreaker, i.e. of two tied Schulze winners, the one with a milder worst-defeat is preferred) fails FAVS.
(d) Show that Approval voting satisfies FAVS – but fails it if we allow incomplete-information scenarios (i.e. in which the strategic-voter-set does not have complete information about all the other votes).
(e) Show that range voting always satisfies FAVS in both complete and incomplete information scenarios.
(It is not clear whether satisfying FAVS is desirable, but this result is of interest for refuting the vague claim that strategy in range voting is comparatively "complicated" or "messy.")

Type password to get answer:

Puzzle #41: Invisibly Corrupted Computer Programs.
[8] Explain how it is possible for an operating system such as LINUX to be corrupted (so that, e.g, "Mortimer Snerd" can always log in) in such a way that scrutinizing the full source code for LINUX will fail to uncover anything special about Mortimer Snerd – even if the scrutinizer is amazingly incredibly wise and intelligent. (Thus, inspecting the source code of a program is inadequate for security purposes.) Hint: LINUX is written in the C language, and the gcc C-compiler is also written in C and is part of LINUX.

Type password to get answer:

Puzzle #42: Probability of Condorcet cycle:
[5] Suppose there are some odd number V≥3 of voters, each casting a random rank-ordering of the C candidates as her ballot. Let P(V,C) be the probability that a Condorcet ("beats all") winner does not exist. Prove the surprising and elegant exact equality P(V,4)=2·P(V,3).

Type password to get answer:

Puzzle #43: Approval voting strategy most likely to elect Condorcet winner
[6] Suppose there are C candidates and V voters, and each voter's honest ranking of the candidates, is random (all C! orderings equally likely). Suppose we hold a single-winner approval-voting election and every voter approves her top J candidates (for some J with 0<J<C).
(a) Which value of J leads to the largest chance that the election winner will be a Condorcet ("beats all") winner (based on the true, honest voter preference orderings)?
(b) What if we have two approval style elections sequentially, where voters approve the top J candidates in election #1, the top K finishers get to run in election #2, and voters approve their top L candidates in the "runoff" election #2. What is the "best" (J,K,L) which causes society to have the greatest chance of electing a Condorcet winner?

Type password to get answer:

Puzzle #44: Shannon Utility Honesty property
[2] Suppose you can buy arbitrary amounts of substances 1, 2, …, n. If Vk is the amount of substance k that you buy, your total utility is

U = u1V1 + u2V2 + … + unVn

i.e. uk>0 is your utility density for substance k. Suppose that the total amount of money you spend to buy substance k is xk, and the total amount of money you can (and must) spend is X=∑1≤k≤nxk. Prove that under the following pricing scheme, your best strategy is to provide an amount of money xk exactly proportional to uk. Magic pricing scheme: If you spend $xk to buy substance k, then you get volume

Vk = A+Bln(xk)
of it, where A and B, B>0, are arbitrary constants. Thus, selling people stuff with this pricing scheme can be used to assess their honest utility densities.

Type password to get answer:

Puzzle #45: (open now solved!) Min-Max matrix product
[8] The min-max product C = A*B of two n×n matrices A and B (yielding another C) is defined by

Cij = max1≤k≤nmin{Aik, Bkj}.
This is just like the usual matrix product but replace the additions by maxes and the multiplications by mins. It is known that two n×n matrices can be multiplied in a subcubic number of elementary steps; V.Strassen in 1969 found an O(n2.807)-step algorithm and the current record, due to D.Coppersmith and S.Winograd building on a great mass of previous theory, is O(n2.376).

Question: is there a subcubic algorithm to compute min-max matrix products? [Application to voting: This yields a subcubic algorithm to find the Schulze beatpaths candidate-ordering starting from the pairwise matrix.]

Type password to get answer:

Puzzle #46: Probability of unclear election winners
[6] In the random election model, with 3 candidates and rank-order votes from V→∞ voters,

  1. What is the probability that some two weighted positional voting methods will disagree on the winner?
  2. And what is the probability that every weighted positional voting method's winner will agree but disagree with the Condorcet winner?
  3. Prove the latter problem cannot happen if the model of voters instead is that voters and candidates are points on a line and voters prefer candidates located closer to them.

Type password to get answer:

Puzzle #47: "Vote for N" leading to unclear election winners
[5] Find a rank-order-ballot election with 5 candidates and as few voters as you can, in which

Type password to get answer:

Puzzle #48: How many votes to count to get confidence?
[5] Suppose there are N voters in a 2-choice election. Each voter is an independent fair coin flip. We shall be interested only in the limit N→∞. Then: what is the minimum fraction F of the votes that need to be counted to obtain probability 1-C or greater (0<C<1/2) that the winner among the counted votes, is in fact the winner among all the votes? (Assume the votes are counted in random order.) Hint: The answer is F = cos(πC)² = cos(π[1-C])².

Type password to get answer:

Puzzle #49: Machievellian Agenda Manipulation
[4] Suppose there are 3 voters and their opinions of the candidates are as follows:

Voter#1: A>C>B>E>F>D>G>H
Voter#2: F>G>C>D>B>H>A>E
Voter#3: B>D>G>C>E>F>H>A

Candidate H seems to be the least-deserving of election. Construct a "knockout tournament" sequence of head-to-head elections to cause H to win.

Type password to get answer:

Puzzle #50: How many checks to get confidence?
[6] Suppose you want to know, with correctness probability ("confidence") at least C, whether a given set of N objects contains B or more "bad" objects. What is the minimum number S of randomly chosen objects (sampled without replacement) that you need to examine to answer the question?

In a voting application, the "objects" might be "precincts" or "voting machines."

Type password to get answer:

Puzzle #51: Getting true (not fake) randomness
[2] The Ohio 2004 presidential election was recounted. The recount was supposed to be of a random subset of precincts. But election administrators arranged a conspiracy to recount a nonrandom subset of precincts, intentionally selected to make sure that the recounts would discover little or no discrepancy. (They were later convicted and jailed, despite their defense that they were just following orders from higher-ups.) This leads to the question: how can we pick true random choices for such purposes, that, all players can be confident, were not pre-arranged?

Type password to get answer:

Puzzle #52: How many votes to count to get 100% certainty of winner?
[3] Suppose the candidate with the leading vote share (in a plurality-style election) has a fraction V of the votes, 0<V≤1. How many of the N votes must be counted in order for the counter (who does not initially know either V or the winner's name) to reach 100% certainty of the identity of this winner?

Type password to get answer:

Puzzle #53: Districting is unavoidably "chaotic"
[3] Suppose it is your job to divide a country (compact connected set in the plane) into N equipopulous electoral "districts" (ditto) for some given N≥2. To avoid bias, the only information that is allowed to affect your districting-drawing is (1) the shape of the country, and (2) the population-density function. Here "shape" is a EW-mirror-invariant notion, i.e. two shapes that are the same after mirroring "East" for "West" are the "same" shape. Further, to force you to deliver districts which are not completely asinine, we demand that

The total length of all district-boundaries, is at most twice the minimum possible length.
  1. Prove that arbitarily tiny changes ("tiny" measured in any Lp norm) in population density (caused by, e.g, a tiny fraction of the people moving) necessarily will sometimes cause vast changes in your districting, i.e. every district will change by at least a positive constant fraction of all the area in the country and at least a positive constant fraction of the people who used to reside in that district, no longer will. (This is unfortunate because it means that sometimes, some politician will find himself, after redistricting, in a new district very unrelated to his old one.)
  2. Prove that even if we allow the districting to depend also on the previous districting, then it still is not possible to avoid "chaos."

Type password to get answer:

Puzzle #54: Better than average
[0] In 1987 John J. Cannell publicized the fact that all 50 US states reported that their students were better than the national average on standardized tests.

  1. Is that actually possible?
  2. Is something close to it possible – i.e. can we have a probability distribution on the real interval [0, 100] such that there is an arbitrarily high probability that a random sample will be above average?

Type password to get answer:

Puzzle #55: How often is voting honestly worse than not voting with Instant Runoff Voting?
[5] In IRV, voting honestly can be worse (for a set of co-feeling voters) than not voting at all.

  1. Find a concrete example of that.
  2. In the random elections model, with 3-candidate V-voter elections (V→∞) show that the likelihood of that is 16.2%. More precisely, this is the chance that a random IRV election will be a situation in which adding some extra number of voters of some common type (such as "A>B>C") will cause the winner to get worse from their point of view. (Also show it is 7.4% in the Dirichlet model.)
  3. (Open) [9] In the limit of a large number C of candidates, what happens to this likelihood?
  4. In a random 3-candidate IRV election as above but now restricting attention to the subset of such elections in which the IRV and plurality voting winners differ, what is the likelihood? If we (further) restrict to the (contained) subset in which for some constant K with 0<K<1 (for example K=99%, but the precise value is irrelevant) the second-placer gets ≤K times as many top-rank votes as the first-placer, and the third-placer gets ≤K times as many top-rank votes as the second-placer, and the IRV and plurality winners differ, then show this probability tends to 100% in the V→∞ limit.
  5. In contrast, with both Approval and Range voting, voting honestly is never worse than not voting at all.

Type password to get answer:

Puzzle #56: How often is voting honestly worse than not voting (with Condorcet)? [Mostly open]
[9] In every Condorcet voting system, it is a known theorem that voting honestly sometimes is worse (for a set of co-feeling voters) than not voting at all. In this puzzle we investigate how frequent that phenomenon is. Define a V-voter C-candidate election scenario to be a "participation failure" if there is some rank-order-ballot vote Q, and some t>0, such that adding t extra identical Q-type ballots, will cause the election result to worsen (from the point of view of the t extra voters).

  1. Is a participation failure scenario possible when C=3? If so, what is its likelihood P3 (in the "random election model") in the limit V→∞?
  2. Same question when C=4.
  3. Same question when C→∞.
In particular consider the three simplest Condorcet systems, "Simpson-Kramer minmax" (the candidate with the least-severe worst-pairwise-defeat, wins), "basic Condorcet" (the candidate with the least sum-of-defeat-margins, wins), and "Copeland" (the candidate who pairwise-defeats the most opponents wins).

Type password to get answer:

Puzzle #57: How often is dishonesty better strategy than honesty with IRV?
[3] With V voters there are exactly C!V possible different C-candidate elections employing rank-order ballots (as would be the case with IRV=instant runoff voting).

  1. Prove that in the limit V→∞ with C≥3 held fixed, the percentage of these elections in which some co-voting voter-subset would have gotten a better IRV winner by voting dishonestly, tends to 100%.
  2. Further, prove that the probability that any particular random voter-type would have gotten a better IRV winner by voting dishonestly, is at least (C-2)/C, i.e. tends to 100% when V→∞ if then C is made large.
  3. Note that the difficulty (for the particular co-voting voter-subset) of actually determining a dishonest vote strategy that does this, is easy – polynomial time algorithm – in fact trivially easy if the honest-voting IRV winner is known.
  4. Compare IRV in this respect with Approval Voting and Range Voting. (See also puzzle 62 for Condorcet voting.)

Type password to get answer:

Puzzle #58: Gerrymandering
[5] Let N be a number of the form N=2pq with q odd. (Every number may be written in such a form, of course.)
Suppose there are N small disjoint discs ("equipopulous towns") in a convex plane region ("country"), no three collinear, each town either red or blue, with the ratio of red:blue being ⌈q/2⌉:⌊q/2⌋.

Red gerrymander:
Prove that it is possible to divide the country into 2p disjoint convex subsets ("districts") such that each contains q towns which are ⌈q/2⌉ red versus ⌊q/2⌋ blue, i.e. so that every district is majority-red. (May be necessary to cut through towns so that a district contains, e.g, half a town, but the total number of towns, counting fractional parts fractionally, is always exactly q per district and always it is an exact ⌈q/2⌉:⌊q/2⌋ red:blue ratio in each.)
Blue gerrymander:
If p≥1 prove that it is possible to divide the country into q disjoint contiguous districts (each containing exactly 2p towns) such that each district is either exactly red-blue balanced (albeit we can add a smidgen of extra blue to each if we permit slightly inexact equipopulousness or if we make one fewer balanced district) or is 100% red.

In other words (and oversimplifying slightly), in a slightly-red-majority country, red always can gerrymander to get 100% of all the congressmen (even if forced to use convex districts only); while blue can gerrymander to get almost all the congressmen (even if forced to use contiguous districts only).

Type password to get answer:

Puzzle #59: Gerrymandering "Squareland"
[4] Starting at bit #273 after the binary"decimal" point, π in binary first has a string of 240 bits containing exactly 50% 1-bits and 50% 0-bits. The only reason we are bringing in π is to get 240 random bits that I clearly did not choose maliciously; they really are "random." It is:

001000011110011
000111000110100
000001001101110
111101111100101
010001100110110
011110011010011
101001000011000
110110011000000
101011000010100
110110111110010
010111110001010
000110111010011
111110000100110
101011011010110
110101010001110
000100100010111

Regard this as a 15×16 checkerboard with one person per square, each person either red (1) or blue (0): "Squareland."

  1. Gerrymander squareland into 16 contiguous districts, each one consisting of exactly 15 squares, such that red has a majority in as many districts as possible. ["Contiguous" here means one can reach any square in the district by a succession of horizontal & vertical singlesteps starting from any other, and always staying inside the district.]
  2. Same thing, but now try to make blue have a majority in as many districts as possible.
  3. Prove your gerrymanders are optimal.
  4. It was claimed on page 31 of [N. Apollonio, R.I.Becker, I.Lari, F.Ricca, and B.Simeone: The Sunfish against the Octopus: opposing compactness to gerrymandering, pp 19-41 in: B. Simeone and F. Pukelsheim (Eds.) Mathematics and Democracy: Recent Advances in Voting Systems and Collective Choice, Springer 2006], that for any odd s≥3, any (s+1)×s "squareland" containing exactly 50% red and 50% blue people (one person per square) could be gerrymandered to yield s red congressmen versus only a single blue congressman (each congressman representing a disjoint district, consisting of exactly s squares, containing a majority of his color, and districts must be contiguous). If you achieve 15:1 congressional ratios in the preceding problems, then you have verified their claim for one particular case with s=15 – but they are, far more generally, claiming it for every odd s≥3 and no matter what the 50-50 configuration of 1s and 0s.
    Prove: they were wrong.
  5. What if we weaken their claim so that it holds, not for every 50-50 configuration of 1s and 0s, but instead merely for a positive constant fraction of random 50-50 configurations when s→∞? Is it then true?
  6. (Open) [9] Define F(s) to be the minimum [over all 50-50 configurations of 1s and 0s arranged in an s×(s+1) array, s odd] of the maximum number of majority-0-districts that can be achieved among s+1 contiguous s-resident districts. What is F(s)'s asymptotic behavior when s→∞?
  7. Prove that for asymptotically 100% of 50-50 configurations of 1s and 0s, a gerrymanderer can achieve asymptotically 100% red-majority s-resident districts.

Type password to get answer:

Puzzle #60: Range and Approval as "universal" voting systems
[5] Suppose every voter has a private preference ordering of all candidates, and "approves" those above some threshold that she chooses. Depending on how the voters set their thresholds, different approval-election winners will result. Call the set of possible approval-voting winners "A."

  1. Prove the Condorcet ("beats all") winner, if one exists, is always in A.
  2. Prove the Plurality winner is always in A.
  3. Prove the AntiPlurality winner is always in A.
  4. Prove the Borda winner – or indeed the winner in any "weighted positional" voting system – is always in A.
  5. Prove the top-2-runoff (plurality, then a second round among the top 2 finishers) winner is always in A.
  6. Prove the IRV (Instant Runoff Voting) winner is always in A.
In this sense Approval Voting is "universal" in that it can imitate all these other commonly proposed voting systems (and range voting then is even more universal).

Type password to get answer:

Puzzle #61: Voting system "stability" (S.J.Brams)
[4] An election outcome is "stable" if it is achieved by some set of (honest) votes such that no voters of any single type have an incentive to change their votes. Further, it is "strongly stable" if no subset of colluding (perhaps un-alike) voters have incentive to change their votes. Otherwise it is "unstable." (Here "election outcomes" are allowed to be "lotteries.") When considering approval voting it is of interest to restrict attention to "semi-honest" votes, i.e. in which each voter genuinely prefers all her approved candidates over all her disapproved ones (and we forbid all-approved or all-disapproved "null votes").

  1. For semi-honest approval voting, prove that an election winner is strongly stable if and only if it is a unique Condorcet ("beats-all") winner.
  2. Prove that it is impossible for any Condorcet voting system always to elect a stable winner – even if we only demand such stability in cases where the winner is a "beats-all" winner. (So in this sense, Condorcet systems are actually worse at electing Condorcet winners than approval voting, despite the fact that approval voting is not a Condorcet voting system!)
  3. Prove that it is impossible with any deterministic voting system based on rank-order ballots (except for a "dictatorship"; and we shall assume the system always elects candidates who are unanimously top-ranked) always to elect a stable winner.
  4. Prove that approval voting does not always elect a stable winner.

Comment: The idea here is the approval-votes fluctuate with time in response to opinion polls, random noise, and voter re-strategizing – but stay semi-honest. Once the votes reach a "stable" configuration, they stop fluctuating because from then on nobody has incentive to change and repeated opinion polls delivering the same answer eliminate the random noise.

Type password to get answer:

Puzzle #62: How often is dishonesty better strategy than honesty with Condorcet?
[4] With V voters there are exactly C!V possible different C-candidate elections employing rank-order ballots. We shall be considering the "large electorate" limit V→∞ with C held fixed.

  1. Prove that when C is made large, the percentage of Condorcet-system elections in which some co-voting voter-subset would have gotten a better winner by voting dishonestly, tends to 100%.
  2. Also note that it is very easy for this voter-type to determine such a better-than-honesty strategy.
  3. (Partly Open) [8] Suppose now that we choose a random voter-type. What is the probability that it can improve the election result by voting dishonestly, in the limit limC→∞limV→∞? I do not know the answer in general, but have been able to prove this limit is 100% for several commonly used Condorcet methods.

Type password to get answer:

Puzzle #63 (ACE): Optimal size for a legislature
[2] Consider the amount of communication a congressman has to do with both his constituency and with his fellow legislators.

  1. Argue that it is minimized if the size of the legislature is proportional to the square root of the country's population P.
  2. But can you argue for other "optimal legislature size" functions such as P1/3 or P2/5 or log(P)?

Type password to get answer:

Puzzle #64: Expected number of votes counted before certain
[6] Suppose you have N voters, V of whom vote for the leading candidate Larry (Plurality voting).

A counter starts counting the N votes one by one in random order until first becoming sure that Larry won (and this counter knows N, but does not a priori know V or Larry's identity).

  1. How many votes, in expectation, are counted?
  2. A naive attempt at an answer is N²/(2V). Explain why this and similar naive attempts are wrong. ([9] Get good upper bounds on the error.)

Type password to get answer:

Puzzle #65: Partitioning squareland into some nice patterns [4]

  1. Can a 6×10 checkerboard be partitioned into 12 districts, each consisting of exactly 5 squares (and each contiguous) and each of a different shape? (Here "same shape" means either rotating or mirroring.)
  2. What about an N×10 checkerboard for some N≥7? Can it be partitioned into 2N 5-square districts, each contiguous and all different in shape?
  3. What if we try to partition a W×H checkerboard into 35 districts, each consisting of exactly 6 board-squares (and each contiguous) and each of a different shape? For which W and H can this be done?

Type password to get answer:

Puzzle #66: Optimal Districting
[8] Divide an equilateral triangle, square, regular pentagon, regular hexagon, circle, and the surface of a sphere, into N equal-area pieces with the least cutting. ([9] And what about "districting" in three or higher dimensions?)

Type password to get answer:

Puzzle #67: Dice can do damned near anything?
[7] Can Alice construct some number of dice such that, no matter which two of them Bob selects, Alice can select a third which "beats" either ("beats" means more than half the time during any long-enough sequence of rolls of die#1 versus die#2, will roll a higher number)? And if so, what is the minimum number of dice Alice needs?

More generally: what is the minimum number F(n) of dice Alice needs so that no matter which n of them Bob selects, Alice can select another from her collection which pairwise-beats all Bob's dice?

Type password to get answer:

Puzzle #68: A random person
[3] You would like to select a random (uniform) person. How should you do it? Pollsters often want to do that, or say that they've done it. But do they really? After you think about what it takes to select a random person, you can ponder that from a position of strength.

Type password to get answer:

Puzzle #69: Optimal way to form a "coalition"
[3] In many (all?) parliamentary governments, if no one political party has a majority of the seats in parliament, then it is necessary for some subset of the parties – together holding a majority of seats – to form a "coalition" to govern. Assume each party has a positive "regret" value associated with being in a coalition with each other party (with the regret values being known functions of the ordered pair of parties). Prove that finding the optimum coalition – minimizing the sum (or the max) of regrets – or even merely approximating optimality to within a factor of some positive power of N (where N is the number of parties) is NP-hard. Hence, if P≠NP, there is no efficient algorithm to determine or approximate optimum coalitions.

Type password to get answer:

Puzzle #70: "Marriages" and "Capitalism."
[5] Suppose there are N men and N women. Each man has a preference order on the women, and vice versa. We wish to arrange N marriages pairing them off. But, if the set of marriages has the property that some man m and woman w would both prefer each other to their current partners, then we say it is "unstable."

  1. Prove there is a (simple) method that always succeeds in arranging N stable marriages.
  2. Prove the "superiority" of heterosexual marriages over homosexual ones by showing that in the same problem with 2N people – but now all of the same sex (and each has a preference ordering on the 2N-1 others) – a stable set of N marriages can fail to exist. ([9] And, with random preference orderings, what is the probability of that?)
  3. What if we have three "sexes" (N members of each are present) and we need to arrange N "marriages" which are disjoint triples each containing one representative of each sex. Prove that a "stable" set of marriages always exist in which no person X would prefer to leave their marriage and join another (kicking out the X's-sex member Y of that one) both of whose other-sex members would prefer X to Y (we assume each person has a preference order on all representatives of each foreign sex). But on the other hand, if each person is assumed to have a preference order on pairs of foreign-sex people then prove that arranging N stable marriages can be impossible.
  4. Returning to the conventional 2-sex problem: What if we want, among all possible stable N-marriage pairoffs, to find the "optimum" one, maximizing utility summed over all people (we assume each person now has a known real "utility" value for marrying each other person). State an efficient way to find this optimum.
  5. What if we want the optimum N-marriage pairoff, but now not requiring stability? Demonstrate that optimizing utility can be incompatible with stability. (Can this be viewed as a "failure of capitalism"? Is there any way instead to see it is a "success"?)
  6. State an efficient method for finding the optimum (but perhaps unstable) N-marriage pairoff.
  7. In the 2-sex problem, show that no matter what procedure is employed to produce the N stable marriages, it (sometimes) will always pay for somebody to lie about their preference order.
  8. Demonstrate that there is no efficient way to find the optimum 3-sex N-"marriage" triples (assuming each person has a pre-stated utility value for each other; the "optimum" maximizes utility of X's two partners for X, summed over all X).

Type password to get answer:

Puzzle #71: The impossibility of districting into squares & triangles
[6] Consider (on a flat Earth) a rectangular "country."

  1. Prove that, for a generic rectangle, there is no way to divide it into any finite number N of squares (we are not requiring the squares to be equal and not pre-specifying N).
  2. However, certainly some rectangles can be divided into N squares. (Prove that is this is possible for some value of N≥1, then it is possible for an infinite set of N≥1.) In that case, prove that, for some well-behaved smooth population density function within the rectangle you create, that there is no way to divide it into N squares with all populations equal, for any N≥2.
  3. But, argue it is no problem to divide a rectangle into N equipopulous rectangles.
  4. What if we want to divide a rectangle into N equipopulous triangles?

Type password to get answer:

Puzzle #72: Coloring districts [6]

  1. Suppose we have a rectangular "country" (on a flat Earth) divided into triangular districts, any two of which either share an entire edge, or share at most a single point ("face-to-face"). How many colors (at most) are needed to color the districts so that no two districts which share nonzero boundary length, have the same color?
  2. Suppose our rectangle instead is divided into convex quadrilaterals (again subject to the "face-to-face" condition), How many colors (at most) are needed now?
  3. Suppose our country (now of any shape) is divideable into (and divided into) face-to-face parallelograms. How many colors (at most) are needed now?
  4. What if we further demand that the face-to-face parallelograms each be rectangles?
  5. Consider districting some (planar, simply-connected) country using the shortest splitline algorithm. How many colors then (at most) are needed?

Type password to get answer:

Puzzle #73: Manipulation of most reasonable voting methods is easy
[6] An election using some voting method is "weakly monotone" with respect to some "manipulator" co-voting voter subset if, for every pair of candidates (A,B), either

  1. B cannot be made to win for any manipulator votes, or
  2. if all the manipulators rank B top and A bottom, then A will not win.
Prove that, for weakly monotone elections, there is a simple way (polynomial time algorithm) for the manipulator set to determine a voting strategy that almost always succeeds in improving the election result for them if such an improvement is achievable.

Type password to get answer:

Puzzle #74: How bad can "Shortest Splitline" districts be? [4]

  1. Suppose we have a rectangular "country" (on a flat Earth) and suppose the population distribution inside it is uniform. If we partition it into N districts using the shortest splitline algorithm, then how much worse (in terms of total length of cutting) can it be than the hypothetical optimum districting which minimizes cutting length? In particular: prove the worst (i.e. maximum) possible ratio in the limit N→∞ is (31/2+3-1/2)/121/4≈1.24080647880279946525.
  2. One might now boldly conjecture that the shortest splitline algorithm never produces cutlength exceeding the optimum by more than some constant factor C no matter how the initial country is shaped, and no matter how the population is distributed inside the country, and no matter what number N≥1 districts we want. Disprove that conjecture with uniform population density.
  3. Also disprove the conjecture for a square-shaped country containing nonuniform population.
  4. This "Approximation Conjecture" is, however, reborn if we restrict attention to convex countries with uniform population densities. ([9] I presently have no full proof or disproof even for a rectangular country, but I believe in this conjecture. Later note: I believe I've proved the conjecture.) Prove the shortest splitline algorithm applied to a convex country will only employ all-internal splitlines, and will only produce convex districts.
  5. Prove the Approximation Conjecture in the case of convex planar countries with arbitrary smooth population densities everywhere bounded below and above by positive constants, in the N→∞ limit.

Type password to get answer:

Puzzle #75: Monty Hall problem
[2] This is a famously tricky probability puzzle. A television game show host asks a contestant to choose one of three closed doors. Behind each door is a prize to be awarded to the contestant. One of the prizes is valuable (pot of gold), other two are not (worms). The contestant chooses a door. But before opening it, the host opens a different door (revealing worms) and asks: would you like to switch doors? Should she switch?

Type password to get answer:

Puzzle #76: Monarch family lines
[3] The English Monarchs adopted the rule that the first-born male legitimate child of the Monarch, would (after the Monarch died) become the new one – but if there were none, then the oldest female legitimate child would be crowned. If neither existed, then the line of Monarchs would come to an end. (In practice, at that point, there would usually be a war. Also, things generally went very badly for children who were too young at the time of their enthronement. But we shall ignore that.)

Suppose each Monarch has N legitimate children who survive him, N≥0, with probability P(N) – for some fixed probability distribution P(0), P(1), P(2), ... (all positive).

  1. Prove that with probability 100%, the Monarch-line will end.
  2. Find the expected number of generations the line persists.
  3. Even though the royal line will die out with probability 100%, prove that the number of descendants of some particular individual can (in this model) grow indefinitely without end, and indeed will do so with positive probability under this model exactly when ∑n≥0 nP(n) > 1.

Type password to get answer:

Puzzle #77: Learning how to play games
[8] "Matrix games" arise all the time in political science, economics, and of course, gameplaying. The rules are: there is a rectangular "payoff matrix" M. There are two players, "White" and "Black." If White chooses strategy w and Black chooses strategy b (both announce simultaneously), then Black pays White M[w,b] dollars. (Which could be negative.) It is known that there always exists an optimal policy for both players, which is always a so-called "mixed strategy" in which you employ strategy n with probability p[n] for some magical fixed probability-vector p, randomly choosing which pure-strategy to use. This probability-vector describes your optimal policy completely. Your problem as a gameplayer, then, is to determine what that optimal vector is.

  1. If you somehow knew the probability vector of your opponent, then explain how quickly to determine your best vector.
  2. Prove that the following approach will converge to yield optimum vectors for both players after G games are played in the limit G→∞. Start with each vector initially equal to the uniform probability distribution. Play "games" versus yourself. Each game, have each "side" assume his opponent's probability vector is the same as this probability distribution on moves: "choose a random previous game and pick the move that side made in that game (except if the random game is the first, then make a random-uniform move)." Under this assumption, have the other side make a move, then pick your best response. That is your move.

Type password to get answer:

Puzzle #78: Florida counties' biased enforcement of rules for overseas ballots in 2000
[4] In the 2000 US presidential election in Florida, after Gore challenged the election there was only one class of ballots which had not yet been counted – late-arriving overseas ballots. So they became critical.

The NY Times (Front page, 15 July 2001) manually examined the 2490 late-arriving overseas ballots in FL 2000. They found that 680 violated state election laws and rules and hence should have been rejected. Here's how they got counted:

In Bush-won counties: 530 accepted, 523 rejected and hence uncounted.
In Gore-won counties: 150 accepted, 666 rejected.

I.e. of the 680 uncompliant but accepted ballots 80% were in Bush counties. (Bush-Gore margin: 537.) (The NY Times also examined the 1824 flaw-free late-overseas ballots, but there was almost no bias there since only 11 were rejected.)

If the enforcement-levels for these laws and rules had been unaffected by whether Gore or Bush happened to be winning in each county, then show that the chance of an anti-Gore bias this-or-more-severe would happen by luck, was below 10-50.

Type password to get answer:

Puzzle #79: Biased purging in Ohio 2004
[3] Between 2000 and 2004 (before the November 2004 Bush vs. Kerry US presidential election) "purging" of lists of registered voters was carried out by various Ohio counties. Consider a county to have been "purged" if the number of registered voters dropped at least 6.5% in this period. (Note this definition is necessarily somewhat arbitrary, e.g. some counties might consider themselves to have "purged" even if their number of registered voters increased from 2000-2004. For the purposes of this puzzle we are making an "effective" definition of purging based on results, not a definition based on alleged intentions.)

The 16 Kerry-Won Counties:      The 72 Bush-Won Counties:
4 purges                        0 purges
(Athens, Belmont,
Jefferson, Monroe)

[Source: www.feminist.org   Ohio registered voter dataset]

Assume that the probability that a county performed a purge was unaffected by whether they were a Bush- or Kerry-county. What is the probability that this large an anti-Kerry bias arose by luck?

Type password to get answer:

Puzzle #80: Biased Voter turnout in Lucas County Ohio 2004
[3] In the 2004 US presidential election in Lucas County in the critical state of Ohio:

  1. In Toledo:
    • The 110 lowest-turnout precincts (all the ones with <68% turnout) were won by Kerry.
    • Bush won 9 of the 15 highest-turnout precincts (all the ones with >85% turnout).
  2. Outside of Toledo:
    • The 6 lowest-turnout precincts (all the ones with <66.6% turnout) were won by Kerry.
    • Bush won 37 of the 45 highest-turnout precincts (all the ones with >84% turnout).

A. Assuming that registered voters were equally likely to vote regardless of whether they supported Bush or Kerry (and that there was no unethical vote- or turnout manipulation) show the probability P that an anti-Kerry bias this or more severe would have happened by luck, obeyed P<10-13.

B. But perhaps Democratic registered voters (Kerry was Democratic) are just less likely to vote than Republican ones – e.g. Democrats are just less-socially-responsible! Consider that possibility.

Type password to get answer:

Puzzle #81: Hierarchical government
[5] A. Suppose there are N people in a country. They wish to elect n congressmen (1≤n<<N).

Straightforward way:
The people are divided at random into n disjoint subsets of cardinality N/n each. Each district then elects one congressman in a single-winner election.
Hierarchical way:
The people are divided at random into N/3 disjoint subsets of cardinality 3 each. Each triple selects one of its members to promote to "the next level." We now proceed recursively using the N/3 next-level people only, etc, each level reducing the number of people by a factor of 3, until only n people remain. (Assume N/n is an exact power of 3 to avoid hassles. In the present-day USA, N/n≈312≈106.)

Suppose the people are of two types "black" and "white." All are total racists, i.e. only vote for members of their own race. Analyse how a small racial imbalance in the population (say 0.000001 away from perfect balance) is magnified in the congress.

B. The above could be criticized as a naive, unrealistic model. Here is another. Assume the blacks, though in the minority, try to dominate the government. They gerrymander the districts so each is either all-white or has a slight black majority. They also manipulate the triples in the hierarchical scheme so that each triple is either 2 blacks versus 1 white, or 3 whites. How well do these government-takeover plans work?

C. Suppose the whites "fight back" in the hierarchical scheme by making all triples be 2:1 or 1:2 (if this is possible). Then what?

D. Finally suppose our blacks and whites are so racist they cannot stand being in the same triple. I.e. all triples are now totally segregated 3:0 or 0:3. Then what?

Type password to get answer:

Puzzle #82: Proxies and cycles
[7] Imagine a government set up as follows. Each voter can either vote on a decision, or grant her vote to somebody else that she chooses (her "proxy"). That proxy would then have two votes, or if she were the proxy of two people, would have three, et cetera.

But difficulties arise if a chain of voter-to-proxy arrows is ultimately cyclic. In that case everybody in the cycle "passes the buck" and nobody actually votes. The goal of this puzzle is to model this.

Suppose there are N voters in all (N large) and everybody chooses their proxy uniformly independently at random from among the other N-1 voters. For each voter the probability that they vote is P and the probability they "pass the buck" is Q=1-P. Then what is the number of voters we expect to be disenfranchised because their vote is transferred into a "buck-passing cycle"?

Type password to get answer:

Puzzle #83: Zero-info honesty
[5] The Zero-Info Honesty criterion (ZIH) for a voting method states: "If all the other voters vote randomly independently (all votes equally likely) then it should be strategically optimal for you to cast an honest vote."

Here "honest" means "rank in honest order of preference" (for a rank-order voting method) but means "rank with favorite=max, most-hated=min, and other linearly interpolated according to your utilities for their election" for range voting.

A. Prove that range voting disobeys ZIH. (This can be regarded as a flaw in range voting; on the other hand, note that optimal zero-info range voting strategy is never to be so-dishonest as to rank A>B if you honestly feel B>A.)

B. Prove that Borda and Plurality voting both obey ZIH.

C. [9] It naively seems like Instant Runoff Voting (IRV) and many (perhaps all) usually-proposed Condorcet Methods should obey ZIH. Can you prove or disprove that?

Type password to get answer:

Puzzle #84: Optimum districting longer for larger country?
[1] Consider the "optimum" (i.e. with shortest total length of the inter-district boundaries) way to divide a country A into N districts. Now consider a new country B which contains A as a strict subset.

Is the optimum N-district partitioning of B always longer than (or the same length as) the optimum N-district partitioning of A?

Type password to get answer:

Puzzle #85: Condorcet cycle probability (Dirichlet model)
[5] In puzzle 7 we had asked for the probability of an A>B>C>A clockwise "Condorcet preference cycle" in a 3-candidate rank-order-ballot election in which all V voters cast any of the 6 possible ballot-types
ABC, ACB, BAC, BCA, CAB, CBA
with equal likelihood independently, in the limit V→∞. We found the answer was a certain exact formula whose approximate value was 8.78%. Now consider the "Dirichlet model" in which the six vote count totals are selected by tossing 5 points random-uniformly onto a line-segment and choosing the 6 intervals that result. In more hifalutin words the 6 totals are chosen uniformly at random from the 5-dimensional simplex
ABC+ACB+BAC+BCA+CAB+CBA=100,   ABC≥0, ACB≥0, BAC≥0, BCA≥0, CAB≥0, CBA≥0
(using 3-letter variable names) in 6-dimensional space. What is the probability of an A>B>C>A clockwise Condorcet cycle then?

Extra Credit: What is the probability that a Condorcet Winner exists in a four-candidate election (vote counts similarly random uniform but now from the 23-dimensional simplex).

Type password to get answer:

Puzzle #86: Copeland is comparatively good with strategic voters
[5] The "Copeland" rank-order-ballot voting system elects whoever wins the most pairwise contests. (The "Copeland score," i.e. total number of pairwise contests you win, must be between 0 and N-1 inclusive in an N-candidate contest; pairwise-ties count as half.) One of Copeland's defects is its propensity for having co-winners with equal-maximal Copeland score. It is important to add some tie-breaking method to Copeland to repair that flaw. In this puzzle we shall show that Copeland enjoys some advantages related to strategic voters.

  1. Show that Copeland is a "Condorcet voting method,"
  2. Show that N-candidate Copeland using Borda-score for tie-breaking is "highly resistant to burial strategy" if N≤4 in the following sense. If C is the winner with honest votes, then the act by "X>C>others"-voters of "burying" C by changing their vote to "X>others>C" can only elect X (at least if we neglect the possibility of perfect pairwise-ties between two candidates) as a probability→0 event in the random-elections model in the limit of a large number of voters. [Very few Condorcet methods enjoy such good burial-resistance, so this makes Copeland quite special.]
  3. But the reader is warned that this is a limit statement special to the random elections model. Show that with N=3 and N=4, the act by "X>C>others"-voters of "burying" C by changing their vote to "X>others>C" can elect X.
  4. If N≥5 show that burial does succeed in Copeland/Borda sometimes, i.e. the act by "X>C>others"-voters of "burying" C by changing their vote to "X>others>C" can elect X. Indeed, in the random elections model, show burial succeeds at least a positive constant fraction of the time.
  5. Despite the ways (shown in this puzzle) in which Copeland is atypically strategy resistant among Condorcet voting methods, it is poor in another way: it is very vulnerable to candidate-cloning.

Type password to get answer:

Puzzle #87 (Generalized "Monty Hall" probability puzzles, cf. puzzle #75): [2]

  1. Mr. Smith has two children, at least one of whom is a boy. What is the probability that the other is a boy?
  2. John Allen Paulos, a mathematician at Temple University, has proposed a 10-door version of the Monty Hall Problem. Once again, there is a car behind one door and goats behind all the others. You pick one door, but before it's opened Monty will always open seven other doors to reveal goats. Then he'll give you a chance to stick with your original door or switch to either of the remaining two unopened doors. Suppose you originally chose Door 1, and Monty opens every other door except Door 5 and Door 8. Should you switch to 5 or 8? And what are the odds the car is behind either 5 or 8?

Type password to get answer:

Puzzle #88 ("Optimum" voting system maximizing chance of Condorcet winner):
[8] Which weighted positional voting system, in a 3-candidate election (in the "Dirichlet" probability model) maximizes the chance of electing a Condorcet "beats-all" winner? (Also, for comparison, compute this chance for Plurality, Borda, AntiPlurality, and IRV.)

Type password to get answer:

Puzzle #89 (Probability of Majority-top winner in Dirichlet election):
[4] In the "Dirichlet model" of random 3-candidate elections (rank-order voting: 3!=6 possible vote types) what is the probability that some candidate will win with a majority of the top-rank votes (thus avoiding any need for a "runoff")?

Bonus questions: Also solve for arbitrary number C≥3 of candidates insetad of merely C=3, and also in the random election model.

Type password to get answer:

Puzzle #90 (Burial works in Condorcet voting):
[3] Prove "burial stategy" works (sometimes) in every Condorcet voting method. That is, there exists a situation with N candidates (for each fixed N≥3) in which A wins, but the B>A>others voters can make B win by strategically re-voting B>others>A.

Type password to get answer:

Puzzle #91 (Number of count-types to publicize):
[3] (This puzzle suggested by The League of Women Voters of New Mexico.) Suppose voters in an N-candidate election submit a rank-order ballot which ranks some subset of the N candidates in order, then leaves the remaining candidates unranked. For example in a 5-candidate election a legal vote would be "C>A>B>(all unranked candidates)." How many different kinds of "total" should the election office in each precinct publish in order to hold an election

  1. Using a Condorcet method based on the "pairwise matrix"?
  2. Using "instant runoff voting"?
  3. Using Borda count?
  4. Using range and approval voting?

(Give both a formula in terms of N, and compute the numbers when N=10.)

Type password to get answer:

Puzzle #92 (Permit cycles in Condorcet ballots?):
[3] Although it seems senseless to cast a rank-order ballot which includes a cycle (such as A>B>C>A)... permitting voters to do that would have the advantage that would allow "dumb totalizing" voting machines to process votes for all Condorcet systems based on "pairwise matrices." (It is beyond the capability of such a machine to detect cycles and thus forbid illegal votes, but if we make cyclic-votes legal, then there is no problem.) Votes in an N-candidate election could be cast as (N-1)N/2 pairwise one-bit "A>B versus A<B" choices.

In this puzzle we explore the consequences of permitting cyclic ballots.

  1. Is it really beyond the capability of a "dumb totalizing" machine to detect cyclic ballots?
  2. Show that casting a cyclic ballot can be strategically useful with both "Simpson-Kramer min-max" and "basic Condorcet" voting. In other words, we expect strategic voters sometimes intentionally to employ this option; doing so is not "senseless" strategically although it still does seem senseless as an honest vote.
  3. (Open [9]) What about with "Tideman ranked pairs" and "Schulze beatpaths" Condorcet voting?

Type password to get answer:

Puzzle #93 (Supermajorities):
[6] Suppose, in order for us to say that "society prefers A over B" we demand that A would beat B in a 2-choice majority vote, by at least a fraction-F supermajority (for some F with ½≤F<1).

  1. Prove that, for any F, no matter how close to 100%, preference cycles are possible.
  2. Suppose, by happenstance, society happens to be so hugely decisive that for every candidate-pair A,B, it prefers A over B (or the reverse) by a (>2/3) supermajority. In such a case, prove preference cycles are impossible.
  3. Suppose each candidate is a point in an n-dimensional "issue space." Suppose each voter has a utility function, on that space, which is concave-∩ (but different voters may have different utility functions). Prove, for each n≥2, that cycles of n-to-1-ratio supermajority preferences are possible (e.g. a cycle of 2/3-supermajority preferences is possible in the 2-dimensional case).
  4. Suppose each voter has a utility function, on that space, which either is the (negated) distance to the candidate, or which is the inner product with the candidate's location (both will work). Further, suppose the voters are distributed according to a log-convex probability density (for example a multidimensional normal density). Then prove that no cycle of (≥F)-supermajority preferences can exist if F≥1-e-1≈63.212%.

Type password to get answer:

Puzzle #94: The "YN model" – a simple voting model in which range voting behaves optimally while many competing voting systems can behave pessimally:
[7] The "YN-model" is a simple model of voting (with a fair amount of realism) in which range voting performs optimally with "honest voters." There are m independent "issues" and 2m "candidates"; each candidate announces a clear yes or no stance on each issue, and by some benificent miracle we have a full democratic marketplace, i.e, every possible issue-stance is represented. Hence (in the case m=4) we can name the 16 candidates YYYY ("yes" on all 4 issues), YYYN, YYNY,..., NNNN. Suppose, for each voter, the utility of electing any given candidate is just the number of issues on which that candidate agrees with the voter. Finally, we suppose without loss of generality that all m issues each would win if put to a single-issue yes/no vote, therefore the objectively best candidate is YYYY. The "without loss of generality" is because we could just rename the issues to make "yes" become "no" for that issue, e.g. the issue "raise taxes?" becomes "do not raise taxes," so with such canonical renaming we can always cause the best candidate to be named YYYY.

  1. Prove that range voting, with "honest voters" (who always score their favorite m, their least-favorite 0, and everybody else linearly-interpolated between according to their utility) will always elect the best candidate in the YN model (i.e, here, YYYY).
  2. But show that plurality voting can unambiguously elect the worst candidate (here NNNN) while causing the best candidate (YYYY) to have zero votes.
  3. Hence Instant Runoff (and Coombs), in such an election, would fail to elect YYYY. Can IRV ever elect the worst candidate NNNN?
  4. Show that Condorcet Cycles can happen in the YN model.
  5. Show that all Condorcet methods (with honest voters) can elect the worst candidate NNNN and can mis-order the finishers exactly backwards so that candidates with more Ns always are majority-preferred over those with fewer!
  6. Show that Borda voting (with honest voters) both can elect the worst candidate NNNN and order the candidates exactly backwards.
  7. Show that Approval voting (with honest voters who approve the top F percent of the available candidates and disapprove the rest, where F is any fixed value with 0<F≤50%) can elect the worst candidate NNNN. (And range voting can also do this with strategic voting.)
  8. (Partially open [9]) What about Coombs voting? Can it elect the worst candidate NNNN?
  9. What about Copeland voting? Can it elect the worst candidate NNNN?

Comment: Most analyses of voting system "properties" ignore the fact that "issues" exist and candidates have stances on them. The YN model is approximately the simplest and most natural possible voting model which doesn't ignore that. It turns out that honest range voting is always optimal in the YN model and is "self consistent." But most other commonly proposed voting methods turn out to be both "self contradictory" and non-optimal (indeed they can even behave pessimally) in the YN model.

Type password to get answer:

Puzzle #95 (The "random YN model"):
[8] The "YN-model" answers to the previous puzzle have been attacked as not very relevant to real life. That is, the election examples constructed to demonstrate that, e.g. Plurality voting can elect the worst winner NNNN, are (speculate the critics) unlikely to arise. To address that, now consider random voters. That is, every possible issue-stance (from among the 2m) are equally likely and we pick some large number V (far exceeding 2m) of such random voters. We than canonize them by reversing the signs of some of the issues so that for each issue considered alone, "Y" is the majority winner. (This canonical-renaming is purely for convenience and has no genuine effect.)

  1. "Honest" range voting (defined in previous puzzle) always elects the best candidate YYY...YY.
  2. Show that, with honest plurality voting, a "bad" candidate (over 50% "N"s in his name) will be elected with chance greater than some absolute positive constant C. (And what is C?)
  3. Show that, with honest approval voting where voters approve the top F-fraction of the candidates (for any fixed F with 0≤F<50%) a "bad" candidate (over 50% "N"s in his name) will be elected with chance greater than C.
  4. Show the same thing for Borda voting.
  5. STILL OPEN [9]: What about with Condorcet, Coombs, and IRV voting?

Type password to get answer:

Puzzle #96 (Human "happiness" and Darwinian evolution):
[2] Here are some nowadays well-accepted scientific findings about the nature of human happiness (revealed by survey studies). Are all of these findings predicted by just one theory – Darwinian evolution?

  1. If asked to choose between (i) get $240 and (ii) 25% chance of getting $1000, most people choose (i). But if asked to choose between (i) lose $740 and (ii) 75% chance of losing $1000, most people choose ii.
  2. More generally it seems people are assymetrically risk-averse about losses but willing to take risks for gains. choose ii.
  3. Within a single country or region, people with more wealth and social status tend to be happier. However, people in rich countries are not substantially happier than those in poor countries (except for people so poor they are literally in danger of dying soon – they genuinely are less happy).
  4. A person who has less stuff than his neighbors (e.g. they have a swimming pool, you do not), tends to be unhappy. But that same person in the same circumstances would be happier if transplanted to a different location with poor neighbors, so that now he had the most stuff comparatively speaking. I.e. happiness is not about absolute wealth, it is more about relative wealth.
  5. 80% of your happiness level is explained purely by your preset "set point" which is determined by genetics (or anyhow is not modifiable) and only 20% by the circumstances you find yourself in. If you improve/worsen your circumstances you get happier/sadder – but only temporarily before returning to your "set point" (even though the improvement/worsening is permanent).

Type password to get answer:

Puzzle #97 ("Allais Paradox" for utilities):
[2] Maurice Allais conducted the following experiment in the 1950s. He asked people to preference-order the following four alternatives:

  1. You get $1 million.
  2. Get $5M with chance 0.1, $1M with chance 0.89, and zero with chance 0.01.
  3. Get $1M with chance 0.11, and zero with chance 0.89.
  4. Get $5M with chance 0.1 and zero with chance 0.90.

Allais claimed that most people prefer A>B and D>C. Does that make sense?
  1. Use "utilities" to prove that anybody who prefers A>B (prefers A over B) must prefer C>D. (This is true regardless of the utility values of the different amounts of money, and it is also true if both the ">" relators are replaced by "<" or both by "=".)
  2. So how can we explain Allais' survey finding? Does it mean that the whole utility model is not a good basis for human behavior? If so, what should it be replaced by?

Type password to get answer:

Puzzle #98 (Random Sampling of a Subset):
[4] Suppose we make n independent tosses of a p-biased coin. (As is well known) the number h of heads that results is np in expectation, with variance=npq.

Now suppose we toss some coin (with unknown bias) N times, with the result we get H heads. A random subsample of n of the N tosses is then selected (0≤n≤N, and note this sampling is without replacement). It contains (say) h heads. Prove that h's mean=nH/N=np (if we define p=H/N and q=1-p) and its variance=npq×(N-n)/(N-1). Note the "sampling without replacement correction factor" (N-n)/(N-1).

Type password to get answer:

Puzzle #99 (Efficient generation of correct "random election" pair-margins matrices):
[6] Many election methods for N-candidate elections with rank-order ballots, as their first step, compute the "pairwise table" giving the "margin" by which A defeats B (i.e. the number of voters who prefer A>B minus the number who prefer B>A, for every A,B).

Suppose all V votes are independent random orderings (all N! orderings equiprobable) with V very large.

  1. In the V→∞ limit, what kind of probability density do these matrices arise from?
  2. Find a way to generate the N×N pairwise matrix resulting from such votes, without actually generating and processing all the votes. I found an interesting O(N5)-time, O(N2)-space algorithm. (Note these time and space bounds do not involve V.) However, soon after, I realized that there was a simpler algorithm running in only O(N2)-time and O(N)-space.

Type password to get answer:

Puzzle #100 (Copeland Tie Probability and Behavior):
[6] The "Copeland" voting method for N-candidate elections with rank-order ballots is: (1) The number of candidates whom X pairwise-defeats is X's "Copeland score." (2) The candidate with greatest Copeland score is the winner.

  1. What (as a function of N in the limit of V→∞ voters each of whom casts an independent random ordering as her vote, all N! orderings equiprobable) is the probability that this will yield at least two tied-winners? In particular, show that the tie-probability is ≈17.5% when N=4 and ≈24.8% when N=10.
  2. What is the chance for a (≥3)-way tie?
  3. (Open) When N→∞ show that the chance of a tie shrinks to 0.
  4. What will be the typical winning Copeland Score?
  5. What do you estimate is the tie probability in real life (as opposed to in part a's "random elections model")?

Type password to get answer:

Puzzle #101 (Weighted sampling):
[4] You are a pollster. You want to predict whether the N voters are going to vote YES or NO in the forthcoming election. If you pick a sample of n (1≤n<<N) future voters at random, the variance in your prediction of the number of YES votes would be npq where q=1-p and p is the probability a random voter votes YES. But you want to outperform that – you want smaller prediction variance using a smaller sample! Can you do that? And how? Does this really work?

Type password to get answer:

Puzzle #102 (Probability Condorcet Winner exists):
[8] In the random election model (also called the "impartial culture")

  1. Find an exact formula, expressed as a 1-dimensional integral, for the probability P(N) that a "Condorcet Winner" (i.e. a candidate who pairwise-defeats all the others by majority-vote) exists in a V-voter N-candidate rank-order-ballot election in the V→∞ limit. [Hint: it will help immensely to have solved puzzle #99 first.]
  2. Then find a simpler asymptotic formula, valid when N→∞, not involving any integrals.
  3. Your formula should prove that the probability that a Condorcet Winner exists is less than N-0.99 for all sufficiently large N. Prove this is also true in the Dirichlet model.

Type password to get answer:

Puzzle #103 (Counting rank-order votes in "D-dimensional politics"):
[5] Suppose politicians and voters are points in a D-dimensional "issue space." Suppose, given a choice between two candidates, voters prefer the one located nearer to them.

  1. Suppose there are N candidates. What is the number of possible rank-order votes that the rules of the voting system allow a voter to cast?
  2. But some of those legally-permitted votes would be dishonest for every voter and hence would never occur. How many honest vote-types could actually occur?
  3. Compare the two preceding answers.

Type password to get answer:

Puzzle #104 (Voting system incentivizing voter to reveal honest utilities):
[8] Is there any way to incentivize a voter (by asking her a single question) to state her sincere normalized utilities for the N candidates, e.g. X=10, Y=3, Z=0? We know that in this case the voter would consider a 30% chance of getting X instead of Z to be equal in value to a guarantee of getting Y. But can we use that kind of knowledge to solve this problem?

Type password to get answer:

Puzzle #105 (Identifying Condorcet Winners by examining few pairs):
[8] A "Condorcet winner" is a candidate who defeats every rival pairwise. (To avoid annoyance, assume there are no pairwise ties.) As is well known, if N≥3 then there can fail to be a Condorcet winner in an N-candidate election. Obviously, in an N-candidate election, we can decide whether a Condorcet winner exists (and if one does exist, identify who) by examining all (N-1)N/2 candidate-pairs.

  1. [2] Show that it suffices to examine at most 2N-3 candidate-pairs. Indeed, more strongly, it suffices to examine 2N-2-⌊lgN⌋ pairs where lgN=log2N.
  2. [2] Show that at least N-1 pairs need to be examined.
  3. [9] Can this "window" [N-1, 2N-3] of bracketing bounds be shrunk? As a step in that direction, show that there is a randomized algorithm which will examine at most 2N-3 pairs but which in expectation (i.e. on average) will examine a number asymptotic to 1.5N.
  4. [8] What if you have a "quantum computer"? Then find sublinear-stepcount algorithms to verify, find, and/or disprove the existence of Condorcet winners (with confidence≥99.99% of answer being correct), assuming we can consult a unit-time "quantum oracle" which, given two any candidates A and B, will inform us who defeats the other pairwise.

Type password to get answer:

Puzzle #106 (Quick elimination of no-hopers in Instant Runoff Voting):
[2] IRV vote-counting software software by "Election Solutions Inc." often immediately simultaneously eliminates a large number of low-vote-getting candidates because "his/her defeat was mathematically inevitable."

  1. Show it is not necessarily legitimate to eliminate a subset of candidates each of whose IRV "defeats are inevitable."
  2. But show that there is a simple criterion for identifying an (often-large) subset of the candidates, which it is legitimate to initially simultaneously eliminate.

Type password to get answer:

Puzzle #107 (IRV gets it wrong):
[1] Clay Shentrup wants to know an argument that instant runoff voting (IRV) gets the winner wrong in at least one of these two elections:

#voters their vote          #voters their vote
------- ----------          ------- ----------
8       B>A>C               4       B>A>C
5       C>B>A               6       C>B>A
4       A>C>B               5       A>C>B
(winner = C)                2       B>C>A
                            (winner = C)

Type password to get answer:

Puzzle #108 (1D political spectrum model):
[6] Here is a simple model of elections: the "voters" (of which there are an infinite number) are the uniform distribution on the real interval (-1, 1). The N candidates each are independent random samples from that distribution, i.e. points x on the real line with -1<x<+1. Voters prefer candidates located nearer to them. In this puzzle assume voter honesty.

  1. The optimal-behaving voting systems: Show that every Condorcet method, Coombs (repeated elimination of the candidate with the most last-place votes), and Approval where voters approve candidates within distance D [where D is a random number from some fixed positive probability density on (0, 2) – each voter with independent randomness], all will elect the candidate closest to 0. [Which, we remark, would seem to be the best winner.]
  2. The asymptotically optimal-behaving systems: Show Borda and range voting (where voters score their favorite max, their most-hated min, and everybody else linearly interpolated in between according to their utility, where utility is a decreasing concave-∩ or linear function of voter-candidate distance) will with probability→1 when N→∞ elect a candidate within (-ε, ε). More generally than Borda, also show this for every weighted positional voting method with a strictly decreasing concave-∩ positive weight sequence. "Concave-∩" is not the tightest possible condition on the weights so that this works – what is?
  3. The bad-behaving systems: With approval voting where voters approve candidates within distance D (for some fixed D, 0<D<\ ;1), we get an exact tie between all candidates in the subinterval (D-1, 1-D). The worst case D→0+ is plurality voting. The best case is D=1 where the candidate nearest to 0 wins. Range voting with a "stairstep" utility(distance) function acts the same as that type of approval voting. With approval voting where voters approve the top-F fraction of the candidates (for some fixed F, 0<F≤1/2), we get in the N→∞ limit that the winner will lie within distance ε of one of the two points ±(1-2F). The best case is when F=1/2. With instant runoff, the winner's probability density is supported on (-2/3, 2/3) and is rather peculiar – it has 4 peaks!

Type password to get answer:

Puzzle #109 (Information content of ballots):
[3] The number of possible approval-style ballots in an N-candidate election, is 2N; but 2N-2 if the two "silly" (all-approve or all-disapprove) ballots are excluded. The number of possible rank-order-style ballots in an N-candidate election, is N!.

  1. Compare these formulas. Which is greater?
  2. Suppose we have "tactical" (rather than "honest") voters in an election where the two "front runner" candidates are known; and suppose the tactical voters always rate these two candidates maximum or minimum (i.e. never rating them intermediate). Now what are the counting formulas, and which is greater?
  3. Finally, suppose we have tactical voters who employ the "moving average strategy." That is: there is a publicly known ordering of the candidates from a priori most-likely-to-win to a priori least-likely-to-win. The voters begin by awarding the two frontrunners the max and min allowed votes, then go through the remaining candidates in decreasing order of victory-chances, awarding each the max- or min-allowed-vote depending on whether the voter regards him as better than average or worse than average where the "average" is taken among the preceding candidates only. Now what are the counting formulas, and which is greater?
  4. How could you encode a rank-order ballot Gore>Kennedy>Bush using 3 bits? In the other direction, suppose you knew Gore, Kennedy, and Bush were the three candidates; how could you decode the binary number 010 to determine what the rank-order ballot was?
  5. Further, show how to encode and decode three independent rank-order ballots (honest voters) using only 8 bits in all (for an average of only 8/3≈2.667 bits per ballot). More generally, anything which has only W possible values, can be encoded using log2W bits per thing (if there is a long sequence of them) and using ⌈log2W⌉ bits (if there is only one).

Can you draw any "take-home lessons" from this exercise?

Type password to get answer:

Puzzle #110 (Counting rank-order votes):
[5] In an N-candidate election, cast a rank order vote in which equalities in rank are allowed. For example, if N=4, the vote A>B=C>D would be permitted. If equalities were not allowed, the number of possible votes would be N! – but we are allowing them, so how many are there?

Type password to get answer:

Puzzle #111 (CTT voting in legislatures):
[3] Is CTT voting a bad idea for voting in legislatures?

Type password to get answer:

Puzzle #112 (Probabilities voting methods "vulnerable to strategy"):
[8] A single-winner election with honest voters and some given voting method will be called "vulnerable to strategy" if there exist some subset of the voters, who, by changing their votes, could cause the winner to change to somebody else whom they (unanimously) prefer. [This subset is not required to consist of identical voters; their honest and/or strategic votes both are allowed to be multi-element sets.] This puzzle investigates the probability that an election is vulnerable to strategy, in the random election model (also called the "impartial culture") with V→∞ voters.

  1. In 2-candidate simple-majority elections, show every election is invulnerable to strategy. Hence in the rest of this problem assume the number N of candidates is fixed with N≥3.
  2. For plain plurality, Borda, and indeed every nontrivial weighted positional method, show that the strategy-vulnerability probability→1.
  3. Also show this for "Coombs elimination" (whose rules are: the candidate with the greatest number of last-place rankings is repeatedly eliminated until only one remains – the winner).
  4. Show for approval voting where the honest voters approve the top-F-fraction of the N candidates, for any fixed F with 1/N≤F≤1-1/N, that the strategy-vulnerability probability→1.
  5. Show for range voting the strategy-vulnerability probability→1.
  6. Show for median-based range voting the strategy-vulnerability probability→1. (This is despite the theorem by Balinski & Laraki that median-based range voting is "optimum" in terms of their definition of "vulnerability to strategy.")
  7. Argue that for most Condorcet methods (including Nanson-Baldwin, Schulze-beatpaths, and least-reversal "basic" Condorcet), the strategy-vulnerability probability→1.
  8. However, show for Instant Runoff Voting (IRV), and also for the following two Condorcet methods which somewhat resemble IRV in their workings: WBS-IRV and BTR-IRV, that the strategy-vulnerability probability goes to a constant depending on N, and for each N with 3≤N<∞ the constant is strictly positive (and also is below 1 if N=3, and presumably below 1 for every fixed N with 3≤N<∞). [Incidentally, note: plain IRV is not a Condorcet method.] However, for IRV the constant goes to 1 when N→∞.
  9. Find upper and lower bounds and/or estimates, for these constants. Note by this measure, IRV is "superior" to Borda, Approval, Plurality, and most Condorcet methods; can you argue that WBS-IRV and/or BTR-IRV in turn are "superior" to IRV?
  10. Further, argue that for a very wide class of voting methods (seemingly including all "reasonable" ones), the liminf probability of vulnerability to strategy exceeds some positive constant.
  11. But: criticize our definition of "vulnerable to strategy" and indeed criticize the whole idea of comparing voting methods based on the "probability in the random election model of vulnerability to strategy" as misleading. Find some examples of (also reasonable-sounding) alternate definitions/models in which some of the above results become quite different.

Type password to get answer:

Puzzle #113 (What do rank-order-ballot[equalities permitted] systems do if given approval-style votes):
[4] Suppose the ballots are rank-orderings of the N candidates in which equalities in rank are allowed. Now suppose that only "approval-style" such ballots are cast, i.e. involving at most one ">" and all the others are "=". Thus the vote A=B>C=D=E would be permitted but A>B=C>D=E would not.

  1. Prove that every Condorcet voting system will deliver the same winner as approval voting.
  2. Further, this generalization of the Borda-system's rules to allow equalities in the rank-order ballots, also will always deliver the same winner as approval voting: each set of K co-equal candidates on a ballot, is given Borda score the average of the Borda scores that K candidates with those rankings, would have normally gotten. For example, the ballot A=B>C=D=E would yield Borda scores for C, D, and E of (0+1+2)/3=1 each, and Borda scores for A and B of (3+4)/2=3.5 each.
  3. However, the following natural generalization of the instant runoff voting (IRV) system's rules to allow equalities in the rank-order ballots, will not necessarily deliver the same winner as approval voting: a ballot ranking K candidates co-equal top, is regarded as casting 1/K votes for each; the candidate with the fewest votes is eliminated (both from the election and all ballots); and then we continue on recursively in the resulting (N-1)-candidate election until only one candidate remains (who wins).

Type password to get answer:

Puzzle #114 (One quantitative measure of clone-immunity [Jack Rudd]):
[5] Suppose you have two camps of supporters, camp A and camp B. You have an n-candidate election, in which 1 candidate (candidate A) is from camp A, and the other candidates (B1, B2, B3,..., Bn-1) are from camp B. The A-supporters want to elect A, the B-supporters want to elect anyone but A.

There is, however, a twist to this election: the A-supporters have to vote first. Their votes are then displayed publicly, and the B-supporters vote in response to this. Both camps can co-ordinate their votes so as to get an optimal result from their point of view.

Let c be the least number such that, if the proportion of the electorate in the A camp is greater than c, they can force the election of candidate A. Then prove:

  1. For Plurality, Top-Two Runoff, IRV and Condorcet voting, c=½.
  2. For Approval and Range voting, c=½.
  3. For Borda voting, c is a function of n. Find this function, and to what value it converges as n tends to infinity.
  4. Prove that for Anti-Plurality voting, c is a function of n. Find this function, and to what value it converges as n→∞.
Extension: what happens if we remove the "twist" that the A-supporters vote first (now everybody votes simultaneously by secret ballot)?

Type password to get answer:

Puzzle #115 (How often do "wrong winners" occur in real life with IRV [Clay Shentrup]):
[2] Instant Runoff Voting (for example) can exhibit many paradoxes including nonmonotonicity, no-show paradox, and reversal failure. One form of nonmonotonicity is: X wins, but increasing X in some votes causes X to lose (or the time-reverse of this scenario also is non-monotonic). One form of no-show paradox is: X loses, but adding some new X-bottom votes causes X to win. In reversal failure, X wins, but if all the votes are reversed ("trying to select the worst candidate") then X still "wins."

Suppose we examine real-life IRV elections and find some percentage P of elections in which you can tell that such a paradox existed. Critics have objected to such discoveries by complaining: "But this 'paradox' is merely hypothetical. E.g. you hypothesize that some extra X-bottom voters appear, etc, causing the paradox. But really they did not. So your so-called paradox doesn't bother me. I want to see real life elections where IRV clearly generated the 'wrong winner' otherwise I'm unimpressed."

  1. Argue that, even if there is no way to tell who the "right winner" even was, still, the percentage of IRV elections with wrong winners due to such paradoxes, must be at least P/2.
  2. Now attack your own last answer: explain why that argument to deduce P/2 as a lower bound, while presumably approximately valid (and we recommend you believe it for practical purposes) really is not rigorous.

Type password to get answer:

Puzzle #116 (Inferring political "positions" of politicians in D-space):
[6] At present there are 100 senators, and each votes about 600 times on a yes-no question during a 2-year senate. Each senator's 600 bits are publicly known. (Actually, some senators abstain from voting sometimes, so there will be fewer than 600 bits; and sometimes senators get replaced in the middle of the term, in which case there would be more than 100 senators.) Devise an algorithm to place the senators along a line ordered from "leftmost" to "rightmost," in such a way that nearby senators tend to usually agree in their votes, whereas far-apart senators usually disagree in their votes. More generally, instead of a line, we could have a D-dimensional "issue space." (D=2 is of interest for pictorial purposes, but we could also consider D=3, etc.) Given some number D>0, devise an algorithm to place the senators as points in D-space in such a way that nearby senators tend to usually agree in their votes, whereas far-apart ones usually disagree.

Type password to get answer:

Puzzle #117 (Bayes-Laplace-Dirichlet law & "soft quorum" for range voting):
[5] Suppose there is some binary quantity B (i.e. yes=1 or no=0, for example "do you think there should be a $5/gallon gasoline tax?"). You ask a random sample of S≥0 people for their values of B, and the result is that Y say "yes" while N say "no" where Y+N=S.

  1. Given this data: what is the Bayesian estimate of the probability P that a random person says "yes"?
  2. And what is the variance in this estimate?
  3. How can a similar formula be used to make range voting have a "soft quorum"?

Type password to get answer:


Return to main page