Exercise Bank — Learning in Multi-Agent Systems

The printed Chapter 14 keeps Exercises 1–5; the bank continues from Exercise 6.

Exercise 6. The sprint ships and the suite scores 0.9; the orchestrator, distrusting the scoreboard, buys the full ablation audit — all 2^4 = 16 reruns over N = \{\mathrm{coder}, \mathrm{reviewer}, \mathrm{tester}, \mathrm{docs}\}, which come back clean: any coalition without the coder scores 0; the coder alone scores 0.5; the coder plus exactly one of reviewer or tester scores 0.8; the coder plus both scores 0.9; adding the docs agent changes no coalition’s score. (a) Under the naive scheme — every member’s learning signal is the team score — state what each member receives, and name the pathology this builds for the docs agent (Section 14.3). (b) Compute the four difference rewards D_i = v(N) - v(N \setminus \{i\}) and their sum. (c) Compute the exact Shapley values, using the companion repository’s foundations/algorithms/shapley.py (Chapter 13, whose Exercise 4 drills this same Shapley-versus-leave-one-out contrast as a payroll rather than a learning gradient); then compare the two vectors member by member, explain the direction of every gap, and explain why the slices’ failure to sum to v(N) is harmless for a gradient and fatal for a payroll. (d) Price the two instruments for a twelve-member organisation at 3{,}000 tokens per rerun, name the row of Table 14.2 that each computed quantity instantiates, and say why a learner can afford one of them at every update but not the other — and what CTDE’s centralised critic estimates in place of the reruns.

Exercise 7. Rock–Paper–Scissors, this chapter’s licensed satellite, payoffs +1, 0, -1. A training pipeline produces checkpoints by naive self-play: \theta_0 plays Rock, and each generation \theta_{k+1} is the best response to \theta_k. (a) Write out the checkpoint sequence, show that it cycles with period 3, and show that every checkpoint beats its parent. (b) The pipeline’s promotion gate is “beats the previous checkpoint”: show that this metric certifies improvement for ever while \theta_3 = \theta_0; then score \theta_1, \theta_2, and \theta_3 against the uniform population of each one’s predecessors, and also \theta_4 against \{\theta_0, \dots, \theta_3\} — the mirror’s flattery and the door’s verdict, side by side, with the imbalance \theta_4 farms made explicit. (c) Show that the uniform mixture over the three pure strategies scores exactly 0 against every pure strategy, and say what this makes it as a training population — which ingredient of Section 14.4’s league it corresponds to, and where Rock–Paper–Scissors sits on Figure 14.2. (d) Transfer the lesson to the running team: the tester red-teams the coder with adversarial inputs derived from the coder’s own recent failure modes; state precisely what this evaluation certifies, what it cannot certify, and what AlphaStar’s exploiter agents correspond to in a testing budget.

Exercise 8. The coder and tester, paid only for task success, compress their bug-triage traffic into single-symbol tags: eight recurring defect classes, eight opaque tags, a speaker score-table and a listener score-table, +1 on a correct guess and -1 otherwise, argmax choices with seeded random tie-breaks — a referential game, the workshop version of Section 14.4’s learned codes. (a) Implement it (standard library, seeded) and train one pair until its rolling accuracy over 200 rounds reaches 0.95; report when the pair crosses the threshold and its final greedy accuracy over all eight classes. (b) Train a second pair from a different seed and cross-wire them — pair 1’s speaker with pair 2’s listener: report the cross accuracy for your seeds and the mean over 20 freshly trained pairs, against chance 1/8. (c) Derive the exact baseline: modelling two independently learned codes as uniformly random bijections, compute the probability that they agree on any given class, the expected number of agreements, and the probability of zero agreement — the derangement count D_8 over 8!. (d) A human auditor subpoenas the channel: assuming the auditor can do no better than witness each tag used at least once, compute the expected number of labelled exchanges required, and name the property the learned code lacks that would let the auditor generalise from fewer. (e) State the design rule this measures: on which side of the workshop/border line the tags belong, and what changes the moment the docs agent — or a regulator — must read the channel (Chapter 5, Chapter 19).

Exercise 9. A mini-Calvano, at the scale of an afternoon (Section 14.5). Two vendors sell interchangeable inference capacity: each period both post a price from \{0, 1, \dots, 5\} at zero cost; the cheaper vendor serves the whole unit market at its price, and ties split it. (a) Enumerate the one-shot game’s pure Nash equilibria — by hand or with pure_nash from the companion repository’s foundations/algorithms/games.py — state the monopoly price, and justify calling any sustained symmetric price of 3 or more supra-competitive. (b) Give each vendor memory-one Q-learning: the state is last period’s price pair, \alpha = 0.15, \gamma = 0.95, exploration \varepsilon_t = e^{-\beta t} with \beta = 2 \times 10^{-5}, 500,000 periods, tables initialised at the discounted value of facing a uniformly random rival; report the long-run greedy prices across seeds 0–9. (c) Probe the learned arrangement: from the settled greedy cycle, force vendor 1 to price at 1 for a single period and let both resume greedy play; report the path and the ten-period profit ledger of deviating against staying course, and name the machinery the two Q-tables have rediscovered (Section 9.4). (d) Answer the regulator: no channel exists, no instruction to cooperate was given, and neither vendor knows of the other’s existence beyond the market — say where, physically, the “agreement” is stored, and why Chapter 12’s warning about copies of one model is the weaker form of this result.

Exercise 10. Apply Section 14.5’s rubric like an engineer. For each of five coordination problems, rule learn, compose, or compose the skeleton, learn the joints — each verdict defended from the rubric’s criteria (density and locality of interaction, crispness and cost of the objective, closedness of the world, recoverability of failure, and the border tests of auditability, interoperability, and contest) and each accompanied by the concrete failure the opposite ruling invites: (i) routing sub-queries between two co-trained retrieval specialists shipped inside one versioned artefact; (ii) the patch hand-off protocol between the running team and an external vendor’s coding agent; (iii) the approval gate for irreversible production migrations; (iv) corridor-crossing among warehouse robots trained in a high-fidelity simulator and deployed as one fleet (Section 14.3); (v) the running team itself — orchestrator, coders, reviewer, tester, bounded budget — for which the ruling must also say which parts are skeleton and which are joints, and why the CTDE conditions hold inside the joints yet fail at the skeleton.

Exercise 11 (lab). The chapter claims that an agent which never sees a gradient but accumulates a playbook is learning (Table 14.1); measure it. Fix a live model, a temperature, and a family of twelve short bug-hunt tasks — each a small Python function with one planted defect drawn from a recurring set of defect types (a boundary error in a range, a mutable default argument, a string compared with a number, floating-point equality, a shadowed built-in, mishandled empty input, and fresh disguises of the same), presented in a fixed order. Run two arms: in the memory arm, after each episode the agent appends at most three lines to a persistent playbook (“what to check first next time”), and every later episode’s prompt carries the playbook so far; in the control arm, the episodes are identical but no playbook exists. Score an episode as solved if the planted defect is correctly identified. Compare first-half and second-half solve rates within each arm, and the between-arm gap in the second half; if the control arm already solves nearly everything in episodes 1–3, harden the tasks until it does not, since a ceiling measures nothing. Then answer: at which of the chapter’s three timescales did the memory arm learn, what gradient was involved, and what the result implies about a team of such agents — each member’s accumulating playbook shifting the ground under the others’, per Section 14.1 and Section 4.8 — for which no convergence theory yet exists. Record the model identifier and the date beside the table: the numbers are perishable, and the durable finding is the between-arm gap, not any absolute rate.