1# WP35 — Formal framework: coordination demand, coordination capacity, and institutions as codes23Status labels used throughout: **DEFINITION** (a convention), **THEOREM / PROPOSITION** (a statement proved below4or a standard result with the proof reproduced), **CONJECTURE** (a statement we believe is worth testing, with no5proof; what would falsify it is stated). Nothing in this file is an empirical finding. The results concern an6idealized communication system; §8 states what is *not* claimed and which pre-registered test (if any) can speak to7each statement. Citations use the keys of `research/reference_candidates.csv`.89---1011## 1. Primitives and definitions1213**DEFINITION 1.1 (agents, tasks, plans).** A society has $N$ agents. In each period, coordination tasks arrive at rate14$\lambda$ per agent. A task requires that $k \ge 2$ participants settle on a common element of a finite *plan set*15$S$, $|S| = s$, the required plan being drawn independently across tasks from a distribution $p$ on $S$ with Shannon16entropy $H(p) = -\sum_{x \in S} p(x)\log_2 p(x) \le \log_2 s$ (shannon1948; cover2006). Communication is counted in17*messages* (one transmission between two agents) and in *bits* (the length of what is transmitted). Verification and18record-keeping use a second channel whose cost is counted separately as *administrative overhead* (DEFINITION 2.1).1920**DEFINITION 1.2 (coordination demand).** The coordination demand of a period is the task volume that must be21settled: $D = N \lambda k$ participant-slots per period. In the worst case in which every pair of agents must be22reconciled, $D$ is bounded by the number of pairs, $N(N-1)/2$, i.e. $D = \Theta(N^2)$; under bounded $\lambda$ and23$k$, $D = \Theta(N)$. Either way $D$ is increasing in $N$.2425**DEFINITION 1.3 (coordination capacity).** Fix a tolerated error rate $\varepsilon \in (0,1)$. The coordination26capacity $K$ of an institutional system is the maximal number of tasks it can settle per period such that the27fraction of tasks settled on a wrong or inconsistent plan is at most $\varepsilon$. $K$ depends on the available28communication budget (bits per period), the code in use (§2), the routing structure (§5) and the overhead (§3).2930**DEFINITION 1.4 (utilization).** $\rho = D/K$. When $D$ and $K$ are measured in the same units (tasks per period),31$\log D - \log K = \log \rho$ exactly.3233**Limitation (not a theorem).** The pre-registered empirical index $P = z(\log D) - z(K)$ uses standardized proxies34(population, territory, settlement hierarchy for $D$; shares of administrative, legal/monetary, communication and35record-keeping indicators for $K$). It is a monotone proxy for $\log\rho$ only under CONJECTURE C1 (§7); it is not a36measurement of $\rho$, and the Seshat/V-Dem indicators are not Shannon quantities.3738---3940## 2. Theorem 1 — coding gain of a shared code4142**DEFINITION 2.1 (code).** A *shared code* is an injective map $c: S \to \{0,1\}^*$ known to all participants,43with lengths $\ell(x) = |c(x)|$. It is *prefix-free* if no codeword is a prefix of another. Institutions in the sense of44this paper (standardized names, units, legal forms, accounting categories, calendars) are shared codes in exactly this45sense (arrow1974; cremer2007).4647**Assumption 2.2.** Settling a task means that the initiating participant identifies the required plan $x \in S$ to the48other $k-1$ participants without ambiguity; messages to different participants are counted separately in messages49but identically in bits per recipient, so we state the result per recipient.5051**THEOREM 1 (coding gain).**52(i) Without a shared code, identifying an arbitrary element of $S$ without error requires at least53$\lceil \log_2 s \rceil$ bits per recipient in the worst case.54(ii) With a shared prefix-free code that is optimal for $p$, the expected length per recipient55$L_p^\* = \min_{c\ \mathrm{prefix\text{-}free}} \sum_x p(x)\ell(x)$ satisfies56$$H(p) \le L_p^\* < H(p) + 1 .$$57(iii) Hence the expected saving per recipient, $G(p) = \lceil\log_2 s\rceil - L_p^\*$, obeys58$G(p) > \lceil\log_2 s\rceil - H(p) - 1 \ge 0$ whenever $\lceil\log_2 s\rceil \ge H(p)+1$, and $G(p)$ is strictly59positive as soon as $p$ is sufficiently concentrated ($H(p) < \lceil\log_2 s\rceil - 1$).6061*Proof.* (i) Without a shared code there is no prior agreement on which binary string denotes which plan, so the62only error-free strategy is a fixed-length enumeration of $S$ agreed by the trivial convention of listing; any scheme63that distinguishes $s$ alternatives with binary strings of a fixed length $m$ needs $2^m \ge s$, i.e.64$m \ge \lceil\log_2 s\rceil$. (The point is not that $\log_2 s$ is a lower bound for *all* conceivable codes — it is the65cost of the *codeless* baseline, in which the message must be self-describing.)6667(ii) *Lower bound.* For any prefix-free code the Kraft inequality holds: $\sum_x 2^{-\ell(x)} \le 1$ (cover2006,68Thm 5.2.1). Put $q(x) = 2^{-\ell(x)}/Z$ with $Z = \sum_x 2^{-\ell(x)} \le 1$. Then69$$\sum_x p(x)\ell(x) - H(p) = \sum_x p(x)\log_2\frac{p(x)}{2^{-\ell(x)}} = \sum_x p(x)\log_2\frac{p(x)}{q(x)} - \log_2 Z70= D_{KL}(p\|q) - \log_2 Z \ge 0,$$71because $D_{KL} \ge 0$ (Gibbs' inequality) and $-\log_2 Z \ge 0$. *Upper bound.* Choose72$\ell(x) = \lceil -\log_2 p(x)\rceil$. Then $\sum_x 2^{-\ell(x)} \le \sum_x p(x) = 1$, so by the converse Kraft73theorem (cover2006, Thm 5.2.1) a prefix-free code with these lengths exists, and74$\sum_x p(x)\ell(x) < \sum_x p(x)(-\log_2 p(x) + 1) = H(p) + 1$. The optimal code does at least as well.7576(iii) Subtract (ii) from (i). $\square$7778**Remark 2.3.** Theorem 1 is the source-coding theorem of shannon1948 applied to the plan set. Its content for the79paper is only this: *a shared code converts a worst-case identification cost into an average-case cost that is lower80exactly to the extent that tasks are predictable.* The "compression" in the title of the hypothesis refers to this81step and to nothing else.8283---8485## 3. Theorem 2 — break-even scale of an institution8687**DEFINITION 3.1 (institutional cost structure).** Adopting a code costs a fixed set-up $F \ge 0$ (designing and88promulgating the standard), a learning cost $\ell \ge 0$ per agent (each of the $N$ agents must learn the code), and an89administrative overhead $a \ge 0$ bits per task (verification, record-keeping, enforcement). It saves $G > 0$ bits per90task (Theorem 1, per recipient; multiply by $k-1$ if desired — the argument is unchanged).9192**THEOREM 2 (break-even).** Over a horizon with $T$ tasks, the institution lowers total communication cost if and only93if94$$T\,(G - a) > F + N\ell .$$95With $T = N\lambda\tau$ over $\tau$ periods, this is equivalent to96$$\lambda\tau > \frac{F/N + \ell}{G - a}\quad\text{when } G > a,$$97and the inequality can never hold when $a \ge G$.9899*Proof.* Total cost without the institution is $C_0 = T\lceil\log_2 s\rceil$. With it, $C_1 = F + N\ell + T(L_p^\* + a)$.100$C_1 < C_0 \iff F + N\ell < T(\lceil\log_2 s\rceil - L_p^\* - a) = T(G - a)$. If $a \ge G$ the right-hand side is101$\le 0 < F + N\ell$ unless $F = \ell = 0$ and $a = G$, in which case the costs are equal, so strict improvement is102impossible. If $G > a$, substitute $T = N\lambda\tau$ and divide both sides by $N(G-a) > 0$. $\square$103104**Corollary 3.2 (scale advantage).** The threshold $(F/N + \ell)/(G-a)$ is decreasing in $N$: holding $\lambda,\tau$105fixed, a larger society crosses the break-even point sooner, because the set-up cost is spread over more agents. It is106*not* decreasing in $N$ through $\ell$: per-agent learning costs do not benefit from scale. This is the formal version107of the observation that institutions "pay off at scale" (johnson1982; garicano2000; bolton1994), and it also makes108precise when they do not: when overhead $a$ is close to the coding gain $G$, or when horizons $\tau$ are short.109110---111112## 4. Theorem 3 — mismatched code penalty (institutional rigidity)113114**THEOREM 3 (cost of a stale code).** Let the code be optimal for $p$ in the sense of using lengths115$\ell_p(x) = \lceil -\log_2 p(x) \rceil$, and let the true task distribution be $q$ with $q \ll p$ (every plan with116positive $q$-probability has positive $p$-probability). Then the expected length under $q$ satisfies117$$H(q) + D_{KL}(q\|p) \le \mathbb{E}_q[\ell_p(X)] < H(q) + D_{KL}(q\|p) + 1 .$$118The excess cost of using the $p$-code when the world is $q$, relative to the $q$-optimal code, lies in119$(D_{KL}(q\|p) - 1,\ D_{KL}(q\|p) + 1)$ bits per task.120121*Proof.* Since $-\log_2 p(x) \le \ell_p(x) < -\log_2 p(x) + 1$,122$$\mathbb{E}_q[\ell_p(X)] \ge \sum_x q(x)\left(-\log_2 p(x)\right) = \sum_x q(x)\log_2\frac{q(x)}{p(x)} + \sum_x q(x)\left(-\log_2 q(x)\right) = D_{KL}(q\|p) + H(q),$$123and the same computation with the $+1$ gives the strict upper bound. The $q$-optimal code has expected length in124$[H(q), H(q)+1)$ by Theorem 1(ii), which yields the stated interval for the excess. (This is the "wrong code" result of125cover2006, Thm 5.4.3.) $\square$126127**Corollary 4.1 (fragility).** A shock that moves the task distribution from $p$ to $q$ raises the per-task128communication cost of an existing institution by about $D_{KL}(q\|p)$ bits. Combined with Theorem 2, the institution129remains worthwhile after the shock only if $G(p) - D_{KL}(q\|p) > a$ (up to the $\pm 1$ rounding). An institution can130therefore *lower* efficiency after a shock, and the more specialized the code (the smaller $H(p)$ relative to131$\log_2 s$), the larger the divergence a given shock can produce. This is the precise sense in which standardization132trades efficiency for rigidity; it echoes tainter1988's declining marginal returns but gives the mechanism a unit (bits133per task) and a magnitude (a divergence).134135---136137## 5. Theorem 4 — hierarchical routing bound and root load138139**DEFINITION 5.1 (hierarchy).** A hierarchy is a rooted tree whose $N$ leaves are the agents and whose internal140nodes are administrative units; every internal node has at most $b \ge 2$ children; the depth (leaf-to-root distance)141is $d = \lceil \log_b N \rceil$ for a complete $b$-ary tree. A task between two leaves is *settled by relay* when each142participant sends a message up to their lowest common ancestor (LCA) and the LCA sends the settlement down.143144**THEOREM 4.**145(i) *Message bound.* Any pairwise task can be settled with at most $2d$ messages (up-path plus down-path through the146LCA), versus up to $N-1$ messages for a flat broadcast in which the initiator must reach every other agent. For $M$147pairwise tasks the total is at most $2M\lceil\log_b N\rceil$.148(ii) *Root load.* In a complete $b$-ary tree with $N = b^d$ leaves, if the two participants of a task are drawn149uniformly at random among leaves (independently, with replacement), the probability that their LCA is the root is150$1 - 1/b$. Hence the expected number of tasks that pass through the root is $M(1 - 1/b)$.151(iii) *Federated / modular coordination.* If a fraction $\theta \in [0,1]$ of tasks is *local* — both participants152belong to the same first-level module (child subtree of the root) by construction of the task process — and the153remaining $1-\theta$ are drawn uniformly as in (ii), the expected root load is $M(1-\theta)(1 - 1/b)$.154155*Proof.* (i) In a tree there is a unique simple path between two leaves; it passes through their LCA and has length at156most $2d$ since each leaf is at depth $\le d$ and the LCA is at depth $\ge 0$. Sending one message per edge along157the two leaf-to-LCA paths settles the task in $\le 2d$ messages. A flat broadcast from one initiator to the other158$N-1$ agents uses $N-1$ messages. Summing over $M$ tasks gives (i).159(ii) The root has $b$ children, each the root of a subtree with $b^{d-1}$ leaves. The first participant lies in some160child subtree $j$; the second participant, drawn uniformly and independently, lies in the same subtree $j$ with161probability $b^{d-1}/b^d = 1/b$. The LCA is the root exactly when the two participants lie in different child subtrees,162which has probability $1 - 1/b$. Expectation of a sum of $M$ indicators gives $M(1-1/b)$.163(iii) Local tasks never reach the root (their LCA lies inside a module); the non-local fraction behaves as in (ii).164By linearity of expectation the load is $M(1-\theta)(1-1/b)$. $\square$165166**Remark 5.2.** Theorem 4 formalizes the trade-off between centralized administration and federated coordination167(radner1993; bolton1994): a hierarchy cuts the *message* cost of coordination from linear to logarithmic in $N$, but168concentrates a constant fraction $1 - 1/b$ of all non-local tasks on the apex, whose processing rate then bounds $K$169(Definition 1.3). Modularity reduces apex load by the locality fraction $\theta$ at the price of *not* reconciling170across modules. These are the five regimes compared in the pre-registered simulations (no institution, shared norms,171standardized records, centralized administration, federated), and the simulations measure messages and bytes172directly rather than assuming the bounds.173174---175176## 6. Theorem 5 — backlog dynamics under mismatch177178**DEFINITION 6.1 (backlog).** Let $D_t$ be the number of tasks arriving in period $t$ and $K_t$ the number the system179can settle in period $t$. The backlog of unsettled tasks follows the Lindley recursion180$$B_{t+1} = \max\{0,\ B_t + D_t - K_t\},\qquad B_0 \ge 0 .$$181182**THEOREM 5.**183(i) *Deterministic case.* If $D_t = D$ and $K_t = K$ for all $t$, then: if $D \le K$, $B_t \le \max\{B_0 - t(K-D), 0\}$,184so the backlog reaches $0$ after at most $\lceil B_0/(K-D) \rceil$ periods when $D < K$ and stays constant at $B_0$185when $D = K$; if $D > K$, $B_t = B_0 + t(D-K) \to \infty$ linearly.186(ii) *Stochastic case.* If $(D_t - K_t)_{t\ge0}$ is i.i.d. with finite mean, then when $\mathbb{E}[D_t] < \mathbb{E}[K_t]$187the backlog has a proper stationary distribution to which $B_t$ converges from any $B_0$, and when188$\mathbb{E}[D_t] > \mathbb{E}[K_t]$, $B_t \to \infty$ almost surely. (Standard: the recursion is the single-server189waiting-time recursion of Lindley (1952), and the stability dichotomy is Loynes' theorem (1962); the proof for (ii) is190not reproduced here and the result is cited.)191(iii) *Delay under a Markovian approximation.* If arrivals are Poisson with rate $\lambda_D$ and settlements are192exponential with rate $\mu$ (an M/M/1 queue), with $\rho = \lambda_D/\mu < 1$, the expected sojourn time is193$W = 1/(\mu - \lambda_D) = (1/\mu)/(1-\rho)$, which is increasing and convex in $\rho$ on $[0,1)$ and diverges as194$\rho \uparrow 1$.195196*Proof of (i).* If $D \le K$, then $B_{t+1} = \max\{0, B_t - (K-D)\}$; by induction197$B_t \le \max\{0, B_0 - t(K-D)\}$, with equality as long as the argument is nonnegative, which gives the hitting time198when $D < K$ and constancy when $D = K$. If $D > K$, then $B_t + D - K > 0$ for all $t$ (since $B_t \ge 0$), so the199maximum is never binding and $B_{t+1} = B_t + (D-K)$, hence $B_t = B_0 + t(D-K)$.200*Proof of (iii).* The M/M/1 stationary number in system is geometric with parameter $\rho$, so the mean is201$\rho/(1-\rho)$ and Little's law gives $W = \rho/((1-\rho)\lambda_D) = 1/(\mu(1-\rho)) = 1/(\mu - \lambda_D)$ (any202standard queueing reference). The function $f(\rho) = (1-\rho)^{-1}$ has $f' = (1-\rho)^{-2} > 0$ and203$f'' = 2(1-\rho)^{-3} > 0$ on $[0,1)$, and $f(\rho) \to \infty$ as $\rho \uparrow 1$. $\square$204205**Scope of Theorem 5.** This is a *mechanism*, not evidence. Polities are not single-server queues: capacity is206endogenous (institutions are built in response to backlog), arrivals are correlated across periods and agents, and207"unsettled tasks" are not observed in the historical record. The theorem is used in the paper only to motivate two208qualitative predictions — that costs rise smoothly and convexly in utilization, and that sustained $\rho > 1$ is209qualitatively different from $\rho < 1$ — and both are stated as conjectures below.210211---212213## 7. Conjectures (unproved; each with its falsifier)214215**CONJECTURE C1 (proxy monotonicity).** The pre-registered Seshat and V-Dem proxies are monotone in the model's216primitives: the scale variables (population, territory, largest settlement, settlement hierarchy) increase with217$D$ of Definition 1.2, and the four indicator blocks (administration, standardized rules and money, communication218infrastructure, record-keeping) increase with $K$ of Definition 1.3, so that $P = z(\log D) - z(K)$ is monotone in219$\log\rho$ up to measurement error. *Reason:* population and territory raise the number and the dispersion of220participants; written records, legal codes, money and measurement systems are shared codes (Theorem 1); roads,221couriers and postal systems raise bits per period; administrative levels implement the routing of Theorem 4.222*Falsifier:* the proxies for $D$ and $K$ are so collinear (as Seshat's first principal component suggests; shin2020)223that $P$ retains almost no variance, or alternative defensible $K$ weightings reverse the sign of $P$ for a224substantial share of polities — both are reported in `research/measurement.md`.225226**CONJECTURE C2 (sustained overload raises breakdown probability).** Periods with $\rho > 1$ sustained longer than227the time needed to build capacity raise the probability of institutional breakdown. *Mechanism family (not proved):*228unsettled tasks accumulate (Theorem 5), so participants cannot form the common knowledge required for coordinated229action (chwe2000) and local defection spreads by contagion through the interaction network (morris2000); institutions230whose codes are stale after a shock lose their cost advantage (Theorem 3) and are abandoned. *Falsifier:* the231pre-registered H2 tests find $\beta_P$ not positive, or $P$ does not beat the population-only and capacity-only232baselines out of sample.233234**CONJECTURE C3 (smooth, not step).** The relation between $P$ and instability is convex and smooth away from235$\rho \approx 1$ and steepens near it, rather than a discrete threshold. *Reason:* Theorem 5(iii) gives a smooth,236convex delay in $\rho$; discontinuities would require an additional tipping mechanism (e.g. a critical mass in a237contagion model) that the framework does not supply. *Falsifier:* the pre-registered H4 comparison finds that a hinge238or step model beats the smooth model out of sample in $\ge 80\%$ of folds, which would favour a tipping mechanism;239conversely, if neither nonlinear form beats the linear model, C3's "steepening" clause is unsupported.240241---242243## 8. What is not claimed, and which test speaks to each statement244245- **No Shannon measurement of history.** Theorems 1 and 3 are about codes for a plan set with a known distribution.246 Seshat indicators (presence of writing, coins, courts, roads) are not message lengths, and no entropy or divergence247 is computed from historical data anywhere in this project. Shannon quantities appear only in the simulations, where248 the plan distribution $p$ and the messages are defined by the experimenter and can be measured.249- **No causal claim.** The theorems describe an idealized communication system; the empirical tests are associational250 and pre-registered as such (`research/preregistration.md`, §1 and §5); the identification discussion is in251 `research/identification.md`.252- **Endogeneity of capacity.** The framework takes $K$ as given within a period; historically, $K$ is built in response253 to $D$ (johnson1982; shin2020). This is why H1 is pre-registered as an association without a direction.254255| Statement | What can speak to it | Pre-registered test |256|---|---|---|257| Theorem 1 (coding gain) | Simulated messages and bits with vs. without a shared code | H3 (regimes b, c vs a) |258| Theorem 2 (break-even) | Simulated total cost across $N$, $\lambda$, horizon, overhead $a$ | H3 factorial cells; search for cells where institutions lose |259| Theorem 3 (stale code) | Simulated shocks to the task distribution | H3 adverse regimes (shock treatment) |260| Theorem 4 (routing, root load) | Simulated messages and apex load under centralized vs federated regimes | H3 (regimes d, e) |261| Theorem 5 (backlog) | Not testable with the historical data (backlog unobserved); illustrated in simulation only | none (stated as mechanism) |262| Conjecture C1 | Measurement diagnostics: collinearity of $D$ and $K$ proxies, sensitivity of $P$ to weights | `research/measurement.md` |263| Conjecture C2 | Lagged $P$ and subsequent instability vs baselines, out of sample | H2 (Seshat Y1–Y3; V-Dem Y4–Y6), H5 |264| Conjecture C3 | Linear vs hinge vs spline in $P$, out of sample | H4 |265