Many Agents

At $\epsilon =\frac{1}{5}$ the auction terminates in $4$ rounds at the assignment $(1,2,3,4)\mapsto (1,2,3,4)$ of value $33$, with final prices $(\frac{21}{5},\frac{17}{5},\frac{11}{5},\frac{22}{5})$. The prices, together with the profits ${\pi }_i={\max }_j(v_{ij}-p_j)$ that each agent can compute from them, certify the outcome: the pair is dual-feasible (${\pi }_i+p_j\ge v_{ij}$ for all $i,j$, checked exactly), so every assignment's value is at most ${\sum }_i{\pi }_i+{\sum }_j{p}_j$; $\epsilon$-complementary slackness bounds that dual objective by the achieved value plus $n\epsilon$; here the gap is exactly $\frac{2}{5}\le n\epsilon =\frac{4}{5}<1$, and with integer values a gap below $1$ makes the assignment exactly optimal. Enumeration of all $24$ assignments confirms the optimum and its uniqueness. The increment is not free: on the $3\times 3$ matrix with a single nonzero value $v_{32}=1$, the auction at $\epsilon =2$ returns an assignment of value $0$ against the optimum $1$: the guarantee degrades to $n\epsilon$, and an increment larger than the differences that matter loses them.

(a) Under the Metropolis weights the sum ${\sum }_i{x}_i^t$ is invariant (the matrix is doubly stochastic) and the disagreement ${\max }_i{x}_i^t-{\min }_i{x}_i^t$ contracts by the factor exactly $\frac{1}{3}$ at every step ($8,\frac{8}{3},\frac{8}{9},\dots$, checked exactly for $t\le 11$): the matrix's eigenvalues are $1,\frac{1}{3},\frac{1}{3},-\frac{1}{3}$ with the discrete Fourier eigenvectors, verified by exact multiplication. Every agent converges to the true average $\frac{7}{2}$.

(b) Under the hub-and-leaves weights the matrix is row- but not column-stochastic; its exact left fixed vector is $\pi =(\frac{2}{5},\frac{1}{5},\frac{1}{5},\frac{1}{5})$, the quantity ${\pi }^{\top }{x}^t$ is invariant (checked exactly at every computed step), and the agents agree on ${\pi }^{\top }{x}^0=\frac{22}{5}\ne \frac{7}{2}$: the hub's number counts double, by design of the weights and of nothing else. (c) With agent 1 stubborn, the fixed-point space of the update is exactly the constants ($\mathrm{rank}(W-I)=3$, computed exactly), the maximum is non-increasing and the minimum non-decreasing (row-stochasticity), agent 1's value never moves, and every agent converges to the stubborn agent's initial value $8$: with $e^t=8\cdot 1-x^t$ one has $e^{t+2}=W^2{e}^t$ and $e_1^t=0$, and since the first column of $W^2$ is $(1,\frac{4}{9},\frac{2}{9},\frac{4}{9})$, $\Vert e^{t+2}{\Vert }_{\infty }\le \frac{7}{9}\Vert e^t{\Vert }_{\infty }$; after $60$ steps the exact iterate is within $10^{-4}$ of $8$. The agent that refuses to average decides what everyone agrees on.

On the zero-sum game the exploitability of the empirical mixtures — ${\max }_i(Gq{)}_i-{\min }_j(p^{\top }G{)}_j$, computed with exact best responses — falls from $1$ at $10$ steps through $\frac{3}{10}$ at $10^2$ and $\frac{2}{25}$ at $10^3$ to $\frac{13}{500}$ at $10^4$, decreasing at every checkpoint; Robinson's theorem (Robinson 1951) gives convergence to $0$, which no finite run certifies. On Shapley's example the analogous quantity (the sum of the two players' exact best-response gains against the empirical profile, written $\mathrm{NashConv}$ in Appendix B (p. 547)) exceeds $\frac{1}{4}$ at every step $t\le 10^4$ (its minimum on that horizon is $\frac{20516947}{73891216}$, at $t=8596$): the empirical frequencies cycle in ever-longer blocks, and that they converge to nothing is Shapley's theorem (Shapley 1964, §5.3), not a conclusion of the finite run. With the same dynamic and the same tie rule, one changed field, the payoffs' structure, separates the two outcomes.

(i) Against penalties $(\frac{1}{4},\frac{1}{2})$ the exact stationary probability of the better action is $\frac{2}{3},\frac{4}{5},\frac{26}{29},\frac{20}{21},\frac{242}{247},\frac{364}{367}$ at depths $n=1,\dots ,6$: increasing at every step and approaching $1$ (here the closed form is $(3^n-1)/(3^n-1+n)$, from detailed balance, which tends to $1$; Tsetlin's general asymptotic optimality for a best action with penalty probability below $\frac{1}{2}$ (Tsetlin 1961) is cited, not proved). (ii) In the Goore game the joint chain over all $64$ automaton states, solved exactly, puts stationary probability above $\frac{3}{4}$ on exactly two yes-votes, the maximum of the reward curve, although no participant knows the curve, sees the vote, or communicates: the mode of the vote count sits at the optimum (Figure 8.3 (p. 314)b shows the exact distribution). This is stationary concentration, not arrival: the chain keeps returning to the other vote counts, and nothing here proves that deeper memory or more players would drive the mass to one.

(a) At $\epsilon =\frac{1}{6}$ the auction ends after $8$ bids with the frigate in Z3, the aircraft in Z2, the cutter in Z1, the drone group in Z4 and the minehunter in Z5, value $33$, final prices $(\frac{7}{2},\frac{7}{6},\frac{4}{3},\frac{7}{3},\frac{2}{3})$ and duality gap $\frac{2}{3}<1$: the plan is exactly optimal, and enumeration shows it is the unique optimum. In the uncoordinated benchmark all five units go to Z1 and the value is $8$. At $\epsilon \in \{2,3,5\}$ the auction stops at $32$. (b) For every unit $k$ and every increment, with $\sigma$ the auction's assignment, $V(\sigma )$ its value, $u_k={\max }_j(v_{kj}-p_j)$ the unit's profit at the final prices and $g$ the duality gap,

where ${\mathrm{OPT}}_{-k}$ is the optimum without unit $k$; when the certificate proves $\sigma$ optimal, $V(\sigma )=\mathrm{OPT}$ and the bounds bracket the exact cost of withholding $k$ (at $\epsilon =2$, where the auction stops at $32<33$, the bracket brackets $V(\sigma )-{\mathrm{OPT}}_{-k}$ and not $\mathrm{OPT}-{\mathrm{OPT}}_{-k}$: for the aircraft the latter is $7>6=v_{k\sigma (k)}$). Here the exact costs of withholding are $6,7,4,6,5$ for the frigate, aircraft, cutter, drone group and minehunter, each inside its bound (Table 8.2 (p. 324)a); the cutter, which holds the most valuable zone, is the cheapest to lose. (c) Let $W$ be row-stochastic and $\tau (A)=\frac{1}{2}{\max }_{i,l}{\sum }_k|a_{ik}-a_{lk}|$. If $\tau (W^m)<1$ for some $m$, then $W$ has a unique left fixed probability vector $\pi$, and $x^t\to ({\pi }^{\top }{x}^0)1$ for every $x^0$: member $i$ controls the share ${\pi }_i$ of the pooled assessment. Here: equal weights give ${\pi }_i=\frac{1}{5}$ and the limit $\frac{1}{2}$ ($\tau (W)=\frac{2}{3}$); the lead-nation weights give $\pi =(\frac{5}{13},\frac{2}{13},\frac{2}{13},\frac{2}{13},\frac{2}{13})$ (in general ${\pi }_1=5a/(5a+4)$) and the limit $\frac{37}{65}$ ($\tau (W)=\frac{3}{5}$); with M5 stubborn, under either weighting, $\pi$ is the fifth unit vector and the limit is $\frac{1}{5}$ ($\tau (W^2)=\frac{8}{9}$ and $\frac{9}{10}$). Only the lead-nation protocol reaches the threshold $\frac{11}{20}$. The change in one member's assessment that would put the pooled view exactly at the threshold is $\frac{1}{4}$ under equal weights, where the view is below the threshold and the change is an increase. The other four members can make it; M1 cannot, since its assessment of $\frac{4}{5}$ can rise by at most $\frac{1}{5}$, and at the maximal report $1$ the pool reaches only $\frac{27}{50}<\frac{11}{20}$. Under the lead-nation weights the view is above the threshold, and a reduction of $\frac{1}{20}$ by M1, or of $\frac{1}{8}$ by any other member, brings it down to it; each of these is feasible. (d) With M1 and M5 both stubborn there is no agreement: the limits are $(\frac{4}{5},\frac{13}{20},\frac{1}{2},\frac{7}{20},\frac{1}{5})$, each flexible member ending at a mixture of the two stubborn views with weights $\frac{3}{4},\frac{1}{2},\frac{1}{4}$ on M1 for M2, M3, M4; only M2 among the flexible members ends above the threshold.