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].)
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."
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?
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?
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)?
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
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
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":
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.
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.)
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?
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.
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:
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.
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...)
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!)
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!)
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.
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?
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.
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]
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.
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?
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?
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.
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
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.
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.
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.
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?)
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.
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?
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?
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.
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?
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
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).
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:
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?
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.")
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.
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).
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?
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
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
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.]
Puzzle #46: Probability of unclear election winners [6] In the random election model, with 3 candidates and rank-order votes from V→∞ voters,
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
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])².
Puzzle #49: Machievellian Agenda Manipulation [4] Suppose there are 3 voters and their opinions of the candidates are as follows:
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.
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."
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?
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?
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.
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.
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.
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).
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).
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⌋.
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).
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:
Regard this as a 15×16 checkerboard with one person per square, each person either red (1) or blue (0): "Squareland."
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."
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").
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.
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.
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.
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).
Puzzle #65: Partitioning squareland into some nice patterns [4]
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?)
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?
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.
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.
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."
Puzzle #71: The impossibility of districting into squares & triangles [6] Consider (on a flat Earth) a rectangular "country."
Puzzle #72: Coloring districts [6]
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
Puzzle #74: How bad can "Shortest Splitline" districts be? [4]
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?
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).
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.
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:
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.
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?
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:
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.
Puzzle #81: Hierarchical government [5] A. Suppose there are N people in a country. They wish to elect n congressmen (1≤n<<N).
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?
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"?
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.
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?
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?
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).
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.
Puzzle #87 (Generalized "Monty Hall" probability puzzles, cf. puzzle #75): [2]
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.)
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.
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.
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
(Give both a formula in terms of N, and compute the numbers when N=10.)
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.
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).
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.
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.
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.)
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?
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:
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).
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.
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.
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?
Puzzle #102 (Probability Condorcet Winner exists): [8] In the random election model (also called the "impartial culture")
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.
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?
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.
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."
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)
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.
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!.
Can you draw any "take-home lessons" from this exercise?
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?
Puzzle #111 (CTT voting in legislatures):[3] Is CTT voting a bad idea for voting in legislatures?
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.
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.
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:
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."
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.
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.
Return to main page