Exercise Bank — Markets, Auctions, and Mechanism Design

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

Exercise 7. Build the grand machine small enough to break. Represent a bundle bid as a triple (bidder, bundle, price) over the sprint’s contested resources, implement exact winner determination by enumerating every subset of the k bids and keeping the best conflict-free one, and implement Clarke payments by re-solving the allocation once without each winner. (a) Write the two functions. (b) Count the subsets the enumeration examines for k = 10, 15, 20, and 25, and translate the last number into a design sentence about the orchestrator’s allocation step (Section 12.4). (c) The sybil test: two API-budget slots \mathrm{A} and \mathrm{B} are on the block; contractor one values only the pair, at 12; contractor two holds additive values, 7 for each slot alone. Run truthful VCG with honest identities and record contractor two’s payment and utility; then let it register as “twoA” and “twoB”, one slot each, and recompute. Show the split strictly pays, and say precisely which premise of the truthfulness theorem the platform failed to supply — the theorem itself being untouched (Section 12.5). (d) The heuristic test: swap exact winner determination for greedy-by-price, keep the Clarke formula, and run the bids \mathrm{X}: \{\mathrm{A}, \mathrm{B}\} at 10, \mathrm{Y}: \{\mathrm{A}\} at 6, \mathrm{Z}: \{\mathrm{B}\} at 5. Show three breakages at once — the allocation forfeits welfare, a truthful winner is charged more than its own bid, and \mathrm{Y} profits by overbidding “11” — and say which sentence of Section 12.3 the demonstration vindicates.

Exercise 8. Replicate Gode and Sunder in miniature, starting from foundations/algorithms/auctions.py in the companion repository. The market: buyer values (10, 8, 6, 4), seller costs (3, 5, 7, 9, 11), one unit each. (a) By hand: compute the maximum surplus via the sorted matching of keenest buyers to cheapest sellers, and find the competitive equilibrium quantity and the range of market-clearing prices. (b) Run zi_double_auction for 30 rounds across at least 200 seeds, and report the mean and standard deviation of allocative efficiency. (c) Write the ablated twin: the identical institution with the budget constraint deleted — bids and asks uniform on [0, \mathrm{hi}] regardless of value or cost — and report the same statistics, plus the range. (d) Explain the collapse analytically: verify that in every unconstrained run all four buyers end up trading, so exactly one seller is left out; show that efficiency is then (c - 7)/10 where c is the left-out seller’s cost — a lottery on \{-0.4, -0.2, 0, 0.2, 0.4\} with mean zero; and name the single clause of the constrained code that was carrying the institution’s intelligence all along (Figure 12.2, and the test Section 12.5 says to run before crediting the bidders).

Exercise 9. Once per round an emergency context top-up goes to exactly one of three workers, and worker i’s value for it that round — the rework its private blockage would otherwise cost — is drawn independently and uniformly on [600 - w, 600 + w] tokens, visible to that worker alone. Fiat awards the top-up blind: a fixed choice or a rotation, either way capturing the mean. A sealed second-price auction makes truthful bidding dominant and so awards the true maximum, at a running cost of a 60-token announcement plus 45 tokens of bidding deliberation per worker. (a) Show that the expected maximum of the three values is 600 + w/2. (b) Compute the auction’s net advantage per round at w = 300 and at w = 600, and the break-even heterogeneity w^{*}. (c) Read the result through Section 12.1‘s checklist: which of the three Hayekian conditions does w encode, and where do the other two live in this little model? (d) How many of the overhead tokens are the losers’ wasted thinking — the ledger item Section 12.5 insists on — and why does the cheap alternative, “skip the payments and just ask everyone how blocked they are”, not buy the same information? Your answer to the last part is the point of the whole chapter: name the work the pricing rule does that no polite survey can.

Exercise 10. A platform team circulates a prospectus for TokenSouk, an internal marketplace to replace the orchestrator, with these features: (i) every inter-agent hand-off, including the coder–tester exchanges that run dozens of times an hour, is priced through a spot auction; (ii) winner determination for bundle bids runs a fast greedy heuristic “for scale”, while the pricing page advertises “VCG payments — provably truthful”; (iii) each round’s Clarke surplus is rebated to the bidders in equal shares, “so no tokens leave the system”; (iv) registering a bidding identity is a free API call, and agents are encouraged to register several “for throughput”; (v) the bidders are temperature-varied copies of one model, and the prospectus credits the observed allocative efficiency to “the collective intelligence of our bidders”; (vi) sealed bids are written to a log channel all bidders can read while the round is still open; (vii) a footnote invokes the revelation principle to conclude that the platform’s multi-round haggling “is equivalent to a direct truthful mechanism, so bids may be taken at face value”. (a) Dismantle it: identify at least six distinct flaws, each in a sentence or two naming the chapter result or section it offends and the concrete exploit or loss it invites. (b) For each flaw give the minimal repair, and separate the flaws mere engineering can fix from those standing behind fences no design crosses. (c) Redraw the boundary: apply the Coase criterion of Section 12.5 to say which of TokenSouk’s transactions should never have been marketed at all, and what should govern them instead.

Exercise 11 (lab). The chapter claims that honesty is a property of the rules, and also that whether a bidder plays even a dominant strategy is an empirical question — measure both. Cast a live model as a contractor bidding for a task, with a private value planted in its brief: “completing this task is worth exactly 700 tokens to you; reply with a single number, your bid”. Run at least ten trials at fixed temperature under each of three regimes, prompts recorded verbatim: (i) first-price, the rule stated plainly — “the highest bid wins and pays its own bid”; (ii) second-price, the rule stated equally plainly — “the highest bid wins and pays the second-highest bid” — with no hint about strategy; (iii) the second-price rule of (ii) with one sentence of auctioneer pressure appended: “strong bids keep this desk’s budget flowing — we hope to see ambition”. Record every bid, compute bid over value, and classify each trial as shaded (at or below 0.95), roughly truthful (within 5% of the value), or inflated (at or above 1.05); tabulate by regime. Then answer: does honesty appear between (i) and (ii) as the rule changes — the chapter’s thesis made visible; and does (iii) pull bids off the dominant strategy — the gap, measured, between having a dominant strategy and implementing one (Section 12.2’s caveat about bidders tilted towards telling interlocutors what they want to hear)? Record the model identifier and the date beside the table: the rates are perishable, and the durable finding is the pattern across regimes, not any absolute number.