Exercise Bank — Making Group Decisions: Voting, Social Choice, and Ensembles

The printed Chapter 10 keeps Exercises 1–6; the bank continues from Exercise 7.

Exercise 7. The team must fix how aggressive the coming refactor will be, on a five-point scale from 1 (touch nothing but the bug) to 5 (rewrite the module). The five agents’ ideal points are 2, 2, 3, 5, 5; each agent prefers options nearer its ideal, and where two options are equidistant it prefers the safer, smaller one. (a) Write out all five rankings and verify that each is single-peaked with respect to the scale. (b) Tally all ten pairwise contests; show that the majority relation is a transitive linear order; and check Black’s promise from Section 10.3: the Condorcet winner is the median ideal. (c) Now let the group decide by the median mechanism — each agent reports an ideal point and the median report is adopted. Show by enumerating its five possible reports that the agent with ideal 5 cannot profit from any misreport, give the two-case argument that no agent ever can, and explain precisely why this does not contradict Gibbard–Satterthwaite. (d) Construct a three-agent, three-option profile on the same scale in which exactly one ranking fails single-peakedness and the majorities cycle; conclude in a sentence what the engineer buys, in Arrow’s terms, by putting a scale rather than an arbitrary menu on the ballot.

Exercise 8. Gibbard–Satterthwaite guarantees that profitable lies exist; measure how common and how findable they are on the smallest interesting electorate. Take three candidates, three voters, and deterministic alphabetical tie-breaking throughout. (a) Implement the Borda and plurality winner functions and a brute-force manipulation search, and count, over all 6^3 = 216 profiles, those at which voter 1 can obtain a strictly preferred winner by misreporting its ranking, under each rule. (b) For the profile in which voter 1 sincerely ranks A \succ B \succ C and the other two vote B \succ A \succ C and C \succ B \succ A, verify the Borda manipulation by hand: the sincere scores, the profitable lie, and the scores it produces. (c) Classify what the search found: under which rule does every profitable lie abandon the voter’s sincere favourite, under which does the typical lie keep the favourite on top while demoting a rival, and which documented personality of each rule (Section 10.2) do the two signatures express? (d) Relate the exercise to Section 10.7: what Gibbard–Satterthwaite asserts, what your census adds to the assertion, and what your search’s running time says about how much protection Bartholdi-style computational hardness offers at this scale.

Exercise 9. A self-consistency harness (Section 3.7) draws five samples. The tempting wrong answer always arrives as the same string, with probability 2/5 per sample; the correct answer arrives in one of three phrasings, each with probability 1/5. (a) With sound clustering — the three phrasings counted as one candidate — compute the exact probability that the majority verdict is correct. (b) Without clustering, the harness counts distinct strings and breaks ties uniformly at random among the leaders: compute the exact probability of a correct return by enumerating all 4^5 draws in exact fractions (fractions.Fraction over itertools.product does it in a dozen lines). (c) Set both figures beside the accuracy of a single sample, name the classical pathology of Section 10.2 that the naive count exhibits, and state the finding plainly: what did holding the election without electoral reform do to the harness? (d) Clustering is itself a rule about which ballots name the same candidate: say what happens to the reformed election if the clusterer fuses the wrong answer with one of the correct phrasings, and conclude what the equivalence judgement must protect for the reform to deserve the name.

Exercise 10. Three review agents hold measured track records of p_1 = 0.9, p_2 = 0.7, and p_3 = 0.6 on binary bug calls, their errors independent. (a) Compute their Nitzan–Paroush weights w_i \propto \log\bigl(p_i/(1-p_i)\bigr). (b) Show exactly that the first agent’s weight exceeds the other two combined, conclude how the weighted rule behaves on every one of the eight vote patterns, verify by enumerating the patterns’ likelihoods that this rule is Bayes-optimal, and compute the accuracy of the weighted rule and of simple majority. (c) The two weaker agents are upgraded to a common competence q: derive the threshold value of q above which the pair, agreeing, outvotes the expert. (d) Compute the panel’s accuracy at q = 0.8 under the weights, and then read the whole exercise through the close of Section 10.7: in what precise sense is the rule of (b) a dictatorship, what makes it legitimate where the unaudited judge of Section 10.6 is merely convenient, and why must the p_i be measured track records rather than the agents’ own announced confidence?

Exercise 11. A judge model compares pairs of candidate patches, one of which is genuinely better. With probability 1/5 it endorses whichever candidate is listed first, regardless of merit; otherwise it judges on merit and names the better candidate with probability 3/4. (a) Compute its accuracy when the better candidate is listed first; when it is listed second; when the order is set by a fair coin; and when the order is set by an adversary — the author of the worse patch controls the listing. (b) The pipeline symmetrises (Section 10.6): the judge sits twice, once per order, with merit judgements independent across sittings, and disagreements are settled by a fair coin. Compute the probabilities of correct agreement, wrong agreement, and disagreement, and the resulting accuracy; compare with (a) and say precisely what symmetrisation has bought and what it has not. (c) Instead of the coin, disagreements are escalated to a stronger arbiter: compute the accuracy conditional on agreement and the fraction of pairs escalated, state what the arrangement costs, and say in what sense one judge has become a two-member jury — and which rule from Table 10.1 the agreement filter is. (d) Redo (b) and (c) assuming the merit judgement is perfectly correlated across the two sittings — the same conviction, delivered twice — and draw the moral: which clause of Section 10.4 do the two sittings satisfy with respect to the position lean but flunk with respect to the convictions?

Exercise 12 (lab). Audit a live judge for the dictator’s tastes of Section 10.6. Build at least twenty pairs of candidate answers whose ground truth you control — for instance, a correct and a subtly buggy implementation of small functions from the team’s repository, the bug planted by you — and have one model, at fixed settings, judge every pair in both orders, recording every verdict. Measure: the first-slot rate f over all judgements, and hence the position-lean estimate \hat{b} = 2f - 1 that the model of Exercise 11 implies; the flip rate — the fraction of pairs whose verdict reverses when the order does; and the accuracy of a single random-order sitting against symmetrised agreement-only judging, together with the escalation rate. Then, for at least ten triples of candidates, obtain all three symmetrised pairwise verdicts and count intransitive triples, connecting any you find to Exercise 2’s finding about who chooses the winner when verdicts cycle. Record the model identifier and the date beside every table: the durable finding is the pattern — whether a lean exists and in which direction, that symmetrisation restores order-invariance by construction, whether agreement-filtered verdicts beat single sittings — not any absolute rate; and note that at this sample size a lean smaller than roughly 0.16 in \hat{b} is indistinguishable from noise, so scale the pair count to the lean you care to detect.