# WP35 — Formal framework: coordination demand, coordination capacity, and institutions as codes

Status labels used throughout: DEFINITION (a convention), THEOREM / PROPOSITION (a statement proved below or a standard result with the proof reproduced), CONJECTURE (a statement we believe is worth testing, with no proof; what would falsify it is stated). Nothing in this file is an empirical finding. The results concern an idealized communication system; §8 states what is not claimed and which pre-registered test (if any) can speak to each statement. Citations use the keys of research/reference_candidates.csv.

# 1. Primitives and definitions

DEFINITION 1.1 (agents, tasks, plans). A society has $N$ agents. In each period, coordination tasks arrive at rate $\lambda$ per agent. A task requires that $k \ge 2$ participants settle on a common element of a finite plan set $S$, $|S| = s$, the required plan being drawn independently across tasks from a distribution $p$ on $S$ with Shannon entropy $H(p) = -\sum_{x \in S} p(x)\log_2 p(x) \le \log_2 s$ (shannon1948; cover2006). Communication is counted in messages (one transmission between two agents) and in bits (the length of what is transmitted). Verification and record-keeping use a second channel whose cost is counted separately as administrative overhead (DEFINITION 2.1).

DEFINITION 1.2 (coordination demand). The coordination demand of a period is the task volume that must be settled: $D = N \lambda k$ participant-slots per period. In the worst case in which every pair of agents must be reconciled, $D$ is bounded by the number of pairs, $N(N-1)/2$, i.e. $D = \Theta(N^2)$; under bounded $\lambda$ and $k$, $D = \Theta(N)$. Either way $D$ is increasing in $N$.

DEFINITION 1.3 (coordination capacity). Fix a tolerated error rate $\varepsilon \in (0,1)$. The coordination capacity $K$ of an institutional system is the maximal number of tasks it can settle per period such that the fraction of tasks settled on a wrong or inconsistent plan is at most $\varepsilon$. $K$ depends on the available communication budget (bits per period), the code in use (§2), the routing structure (§5) and the overhead (§3).

DEFINITION 1.4 (utilization). $\rho = D/K$. When $D$ and $K$ are measured in the same units (tasks per period), $\log D - \log K = \log \rho$ exactly.

Limitation (not a theorem). The pre-registered empirical index $P = z(\log D) - z(K)$ uses standardized proxies (population, territory, settlement hierarchy for $D$; shares of administrative, legal/monetary, communication and record-keeping indicators for $K$). It is a monotone proxy for $\log\rho$ only under CONJECTURE C1 (§7); it is not a measurement of $\rho$, and the Seshat/V-Dem indicators are not Shannon quantities.

# 2. Theorem 1 — coding gain of a shared code

DEFINITION 2.1 (code). A shared code is an injective map $c: S \to {0,1}^*$ known to all participants, with lengths $\ell(x) = |c(x)|$. It is prefix-free if no codeword is a prefix of another. Institutions in the sense of this paper (standardized names, units, legal forms, accounting categories, calendars) are shared codes in exactly this sense (arrow1974; cremer2007).

Assumption 2.2. Settling a task means that the initiating participant identifies the required plan $x \in S$ to the other $k-1$ participants without ambiguity; messages to different participants are counted separately in messages but identically in bits per recipient, so we state the result per recipient.

THEOREM 1 (coding gain). (i) Without a shared code, identifying an arbitrary element of $S$ without error requires at least $\lceil \log_2 s \rceil$ bits per recipient in the worst case. (ii) With a shared prefix-free code that is optimal for $p$, the expected length per recipient $L_p^* = \min_{c\ \mathrm{prefix\text{-}free}} \sum_x p(x)\ell(x)$ satisfies $$H(p) \le L_p^* < H(p) + 1 .$$ (iii) Hence the expected saving per recipient, $G(p) = \lceil\log_2 s\rceil - L_p^*$, obeys $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 strictly positive as soon as $p$ is sufficiently concentrated ($H(p) < \lceil\log_2 s\rceil - 1$).

Proof. (i) Without a shared code there is no prior agreement on which binary string denotes which plan, so the only error-free strategy is a fixed-length enumeration of $S$ agreed by the trivial convention of listing; any scheme that distinguishes $s$ alternatives with binary strings of a fixed length $m$ needs $2^m \ge s$, i.e. $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 the cost of the codeless baseline, in which the message must be self-describing.)

(ii) Lower bound. For any prefix-free code the Kraft inequality holds: $\sum_x 2^{-\ell(x)} \le 1$ (cover2006, Thm 5.2.1). Put $q(x) = 2^{-\ell(x)}/Z$ with $Z = \sum_x 2^{-\ell(x)} \le 1$. Then $$\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 Z = D_{KL}(p|q) - \log_2 Z \ge 0,$$ because $D_{KL} \ge 0$ (Gibbs' inequality) and $-\log_2 Z \ge 0$. Upper bound. Choose $\ell(x) = \lceil -\log_2 p(x)\rceil$. Then $\sum_x 2^{-\ell(x)} \le \sum_x p(x) = 1$, so by the converse Kraft theorem (cover2006, Thm 5.2.1) a prefix-free code with these lengths exists, and $\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.

(iii) Subtract (ii) from (i). $\square$

Remark 2.3. Theorem 1 is the source-coding theorem of shannon1948 applied to the plan set. Its content for the paper is only this: a shared code converts a worst-case identification cost into an average-case cost that is lower exactly to the extent that tasks are predictable. The "compression" in the title of the hypothesis refers to this step and to nothing else.

# 3. Theorem 2 — break-even scale of an institution

DEFINITION 3.1 (institutional cost structure). Adopting a code costs a fixed set-up $F \ge 0$ (designing and promulgating the standard), a learning cost $\ell \ge 0$ per agent (each of the $N$ agents must learn the code), and an administrative overhead $a \ge 0$ bits per task (verification, record-keeping, enforcement). It saves $G > 0$ bits per task (Theorem 1, per recipient; multiply by $k-1$ if desired — the argument is unchanged).

THEOREM 2 (break-even). Over a horizon with $T$ tasks, the institution lowers total communication cost if and only if $$T,(G - a) > F + N\ell .$$ With $T = N\lambda\tau$ over $\tau$ periods, this is equivalent to $$\lambda\tau > \frac{F/N + \ell}{G - a}\quad\text{when } G > a,$$ and the inequality can never hold when $a \ge G$.

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)$. $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 is $\le 0 < F + N\ell$ unless $F = \ell = 0$ and $a = G$, in which case the costs are equal, so strict improvement is impossible. If $G > a$, substitute $T = N\lambda\tau$ and divide both sides by $N(G-a) > 0$. $\square$

Corollary 3.2 (scale advantage). The threshold $(F/N + \ell)/(G-a)$ is decreasing in $N$: holding $\lambda,\tau$ fixed, a larger society crosses the break-even point sooner, because the set-up cost is spread over more agents. It is not decreasing in $N$ through $\ell$: per-agent learning costs do not benefit from scale. This is the formal version of the observation that institutions "pay off at scale" (johnson1982; garicano2000; bolton1994), and it also makes precise when they do not: when overhead $a$ is close to the coding gain $G$, or when horizons $\tau$ are short.

# 4. Theorem 3 — mismatched code penalty (institutional rigidity)

THEOREM 3 (cost of a stale code). Let the code be optimal for $p$ in the sense of using lengths $\ell_p(x) = \lceil -\log_2 p(x) \rceil$, and let the true task distribution be $q$ with $q \ll p$ (every plan with positive $q$-probability has positive $p$-probability). Then the expected length under $q$ satisfies $$H(q) + D_{KL}(q|p) \le \mathbb{E}q[\ell_p(X)] < H(q) + D{KL}(q|p) + 1 .$$ The excess cost of using the $p$-code when the world is $q$, relative to the $q$-optimal code, lies in $(D_{KL}(q|p) - 1,\ D_{KL}(q|p) + 1)$ bits per task.

Proof. Since $-\log_2 p(x) \le \ell_p(x) < -\log_2 p(x) + 1$, $$\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),$$ and the same computation with the $+1$ gives the strict upper bound. The $q$-optimal code has expected length in $[H(q), H(q)+1)$ by Theorem 1(ii), which yields the stated interval for the excess. (This is the "wrong code" result of cover2006, Thm 5.4.3.) $\square$

Corollary 4.1 (fragility). A shock that moves the task distribution from $p$ to $q$ raises the per-task communication cost of an existing institution by about $D_{KL}(q|p)$ bits. Combined with Theorem 2, the institution remains worthwhile after the shock only if $G(p) - D_{KL}(q|p) > a$ (up to the $\pm 1$ rounding). An institution can therefore lower efficiency after a shock, and the more specialized the code (the smaller $H(p)$ relative to $\log_2 s$), the larger the divergence a given shock can produce. This is the precise sense in which standardization trades efficiency for rigidity; it echoes tainter1988's declining marginal returns but gives the mechanism a unit (bits per task) and a magnitude (a divergence).

# 5. Theorem 4 — hierarchical routing bound and root load

DEFINITION 5.1 (hierarchy). A hierarchy is a rooted tree whose $N$ leaves are the agents and whose internal nodes are administrative units; every internal node has at most $b \ge 2$ children; the depth (leaf-to-root distance) is $d = \lceil \log_b N \rceil$ for a complete $b$-ary tree. A task between two leaves is settled by relay when each participant sends a message up to their lowest common ancestor (LCA) and the LCA sends the settlement down.

THEOREM 4. (i) Message bound. Any pairwise task can be settled with at most $2d$ messages (up-path plus down-path through the LCA), versus up to $N-1$ messages for a flat broadcast in which the initiator must reach every other agent. For $M$ pairwise tasks the total is at most $2M\lceil\log_b N\rceil$. (ii) Root load. In a complete $b$-ary tree with $N = b^d$ leaves, if the two participants of a task are drawn uniformly at random among leaves (independently, with replacement), the probability that their LCA is the root is $1 - 1/b$. Hence the expected number of tasks that pass through the root is $M(1 - 1/b)$. (iii) Federated / modular coordination. If a fraction $\theta \in [0,1]$ of tasks is local — both participants belong to the same first-level module (child subtree of the root) by construction of the task process — and the remaining $1-\theta$ are drawn uniformly as in (ii), the expected root load is $M(1-\theta)(1 - 1/b)$.

Proof. (i) In a tree there is a unique simple path between two leaves; it passes through their LCA and has length at most $2d$ since each leaf is at depth $\le d$ and the LCA is at depth $\ge 0$. Sending one message per edge along the two leaf-to-LCA paths settles the task in $\le 2d$ messages. A flat broadcast from one initiator to the other $N-1$ agents uses $N-1$ messages. Summing over $M$ tasks gives (i). (ii) The root has $b$ children, each the root of a subtree with $b^{d-1}$ leaves. The first participant lies in some child subtree $j$; the second participant, drawn uniformly and independently, lies in the same subtree $j$ with probability $b^{d-1}/b^d = 1/b$. The LCA is the root exactly when the two participants lie in different child subtrees, which has probability $1 - 1/b$. Expectation of a sum of $M$ indicators gives $M(1-1/b)$. (iii) Local tasks never reach the root (their LCA lies inside a module); the non-local fraction behaves as in (ii). By linearity of expectation the load is $M(1-\theta)(1-1/b)$. $\square$

Remark 5.2. Theorem 4 formalizes the trade-off between centralized administration and federated coordination (radner1993; bolton1994): a hierarchy cuts the message cost of coordination from linear to logarithmic in $N$, but concentrates a constant fraction $1 - 1/b$ of all non-local tasks on the apex, whose processing rate then bounds $K$ (Definition 1.3). Modularity reduces apex load by the locality fraction $\theta$ at the price of not reconciling across modules. These are the five regimes compared in the pre-registered simulations (no institution, shared norms, standardized records, centralized administration, federated), and the simulations measure messages and bytes directly rather than assuming the bounds.

# 6. Theorem 5 — backlog dynamics under mismatch

DEFINITION 6.1 (backlog). Let $D_t$ be the number of tasks arriving in period $t$ and $K_t$ the number the system can settle in period $t$. The backlog of unsettled tasks follows the Lindley recursion $$B_{t+1} = \max{0,\ B_t + D_t - K_t},\qquad B_0 \ge 0 .$$

THEOREM 5. (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}$, so the backlog reaches $0$ after at most $\lceil B_0/(K-D) \rceil$ periods when $D < K$ and stays constant at $B_0$ when $D = K$; if $D > K$, $B_t = B_0 + t(D-K) \to \infty$ linearly. (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]$ the backlog has a proper stationary distribution to which $B_t$ converges from any $B_0$, and when $\mathbb{E}[D_t] > \mathbb{E}[K_t]$, $B_t \to \infty$ almost surely. (Standard: the recursion is the single-server waiting-time recursion of Lindley (1952), and the stability dichotomy is Loynes' theorem (1962); the proof for (ii) is not reproduced here and the result is cited.) (iii) Delay under a Markovian approximation. If arrivals are Poisson with rate $\lambda_D$ and settlements are exponential with rate $\mu$ (an M/M/1 queue), with $\rho = \lambda_D/\mu < 1$, the expected sojourn time is $W = 1/(\mu - \lambda_D) = (1/\mu)/(1-\rho)$, which is increasing and convex in $\rho$ on $[0,1)$ and diverges as $\rho \uparrow 1$.

Proof of (i). If $D \le K$, then $B_{t+1} = \max{0, B_t - (K-D)}$; by induction $B_t \le \max{0, B_0 - t(K-D)}$, with equality as long as the argument is nonnegative, which gives the hitting time when $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 the maximum is never binding and $B_{t+1} = B_t + (D-K)$, hence $B_t = B_0 + t(D-K)$. Proof of (iii). The M/M/1 stationary number in system is geometric with parameter $\rho$, so the mean is $\rho/(1-\rho)$ and Little's law gives $W = \rho/((1-\rho)\lambda_D) = 1/(\mu(1-\rho)) = 1/(\mu - \lambda_D)$ (any standard queueing reference). The function $f(\rho) = (1-\rho)^{-1}$ has $f' = (1-\rho)^{-2} > 0$ and $f'' = 2(1-\rho)^{-3} > 0$ on $[0,1)$, and $f(\rho) \to \infty$ as $\rho \uparrow 1$. $\square$

Scope of Theorem 5. This is a mechanism, not evidence. Polities are not single-server queues: capacity is endogenous (institutions are built in response to backlog), arrivals are correlated across periods and agents, and "unsettled tasks" are not observed in the historical record. The theorem is used in the paper only to motivate two qualitative predictions — that costs rise smoothly and convexly in utilization, and that sustained $\rho > 1$ is qualitatively different from $\rho < 1$ — and both are stated as conjectures below.

# 7. Conjectures (unproved; each with its falsifier)

CONJECTURE C1 (proxy monotonicity). The pre-registered Seshat and V-Dem proxies are monotone in the model's primitives: the scale variables (population, territory, largest settlement, settlement hierarchy) increase with $D$ of Definition 1.2, and the four indicator blocks (administration, standardized rules and money, communication infrastructure, record-keeping) increase with $K$ of Definition 1.3, so that $P = z(\log D) - z(K)$ is monotone in $\log\rho$ up to measurement error. Reason: population and territory raise the number and the dispersion of participants; written records, legal codes, money and measurement systems are shared codes (Theorem 1); roads, couriers and postal systems raise bits per period; administrative levels implement the routing of Theorem 4. Falsifier: the proxies for $D$ and $K$ are so collinear (as Seshat's first principal component suggests; shin2020) that $P$ retains almost no variance, or alternative defensible $K$ weightings reverse the sign of $P$ for a substantial share of polities — both are reported in research/measurement.md.

CONJECTURE C2 (sustained overload raises breakdown probability). Periods with $\rho > 1$ sustained longer than the time needed to build capacity raise the probability of institutional breakdown. Mechanism family (not proved): unsettled tasks accumulate (Theorem 5), so participants cannot form the common knowledge required for coordinated action (chwe2000) and local defection spreads by contagion through the interaction network (morris2000); institutions whose codes are stale after a shock lose their cost advantage (Theorem 3) and are abandoned. Falsifier: the pre-registered H2 tests find $\beta_P$ not positive, or $P$ does not beat the population-only and capacity-only baselines out of sample.

CONJECTURE C3 (smooth, not step). The relation between $P$ and instability is convex and smooth away from $\rho \approx 1$ and steepens near it, rather than a discrete threshold. Reason: Theorem 5(iii) gives a smooth, convex delay in $\rho$; discontinuities would require an additional tipping mechanism (e.g. a critical mass in a contagion model) that the framework does not supply. Falsifier: the pre-registered H4 comparison finds that a hinge or step model beats the smooth model out of sample in $\ge 80%$ of folds, which would favour a tipping mechanism; conversely, if neither nonlinear form beats the linear model, C3's "steepening" clause is unsupported.

# 8. What is not claimed, and which test speaks to each statement

• No Shannon measurement of history. Theorems 1 and 3 are about codes for a plan set with a known distribution. Seshat indicators (presence of writing, coins, courts, roads) are not message lengths, and no entropy or divergence is computed from historical data anywhere in this project. Shannon quantities appear only in the simulations, where the plan distribution $p$ and the messages are defined by the experimenter and can be measured.
• No causal claim. The theorems describe an idealized communication system; the empirical tests are associational and pre-registered as such (research/preregistration.md, §1 and §5); the identification discussion is in research/identification.md.
• Endogeneity of capacity. The framework takes $K$ as given within a period; historically, $K$ is built in response to $D$ (johnson1982; shin2020). This is why H1 is pre-registered as an association without a direction.