Conceptio › Archive › arXiv CS

arXiv CSopen access

Constitutional Governance in Metric Spaces

2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

cloud distributed-computing parallel-computing

distributed computing, parallel computing, cloud

Constitutional Governance in Metric Spaces Ehud Shapiro1 and Nimrod Talmon2

arXiv:2605.13362v1 [cs.MA] 13 May 2026

London School of Economics and Weizmann Institute of Science 2 Ben-Gurion University and Input Output

Abstract. Computational social choice and algorithmic decision theory offer rich aggregation theory but no end-to-end, polynomial-time process for egalitarian self-governance: prior work treats aggregation, deliberation, amendment, and consensus in isolation, and key metric-space aggregators are NP-hard. We propose constitutional governance in metric spaces, integrating these stages into one polynomial-time process. The constitution assigns, per amendable component, a metric space, aggregation rule, and supermajority threshold. Each member submits an ideal element—both vote and personal proposal. Any member may then submit a public proposal carrying supermajority public support under the revealed votes—sourced from coalition deliberation, optimization, or AI mediation. The constitutional rule scores proposals against the status quo, adopting the supported proposal of positive maximal score (else retaining the status quo); the same rule, possibly with a higher threshold, amends the constitution itself. We develop the generalised median as the worked rule, establish framework-level guarantees, prove no misreport weakly dominates sincere voting, and study the compromise gap between best peak and unconstrained optimum—zero in one dimension, bounded in general, narrowed in simulation by a simple heuristic. We instantiate the framework on seven canonical settings; the mean appears as a utilitarian alternative in the appendix. By unifying metric-space aggregation, reality-aware social choice, supermajority amendment, constitutional consensus, deliberative coalition formation, and AI mediation, this work delivers a comprehensive solution to the constitutional democratic governance of digital communities and organisations. Keywords: Computational social choice · Constitutional governance · Metric spaces · Efficient aggregation · Deliberation · Digital cooperatives

Introduction

Computational social choice and algorithmic decision theory have produced a rich body of aggregation theory: voting rules, participatory budgeting, committee selection, ranking aggregation, and aggregation over metric spaces. A community wishing to govern itself today, however, still finds no comprehensive, end-toend, efficient process to adopt. Existing contributions tend to address single stages—aggregation, deliberation, amendment, consensus—in isolation, and key aggregators are NP-hard in natural settings. Efficient, well-behaved integration of these stages into a coherent governance process is missing.

Shapiro and Talmon

Concretely, consider a digital community: a freelancers’ guild, a neighbourhood association, a regional dog lovers’ network. The community must elect officers, set rates, allocate a budget, rank strategic priorities, select a governance board, and draft and amend its own bylaws—each a different decision type, with different structure (unordered alternatives, one-dimensional scales, the simplex, permutations, subsets, strings). Today, a community wishing to do so would have to glue together heterogeneous mechanisms with no unifying contract, while accepting that several of the natural aggregators are computationally intractable. We propose constitutional governance in metric spaces, a unified framework to fill this gap. The prevailing constitution specifies, per amendable component of the status quo, a metric space (X, d) and an aggregation rule ϕ with a supermajority threshold σ ∈ [1/2, 1). Each member specifies an ideal element, serving as both vote and personal proposal ; subsequently, any member may submit a public proposal from any source—coalition deliberation, optimization, or AI mediation—carrying supermajority public support under the revealed votes. Public supermajority support sits between anonymous count and active coalition—it identifies supporters without requiring them to coordinate. The constitutional governance rule scores each proposal against the status quo via ϕ, adopts the supported proposal of positive maximal score, and otherwise retains the status quo. The framework amends itself by the same rule at higher thresholds. The framework integrates five lines of prior work. Aggregation over metric spaces [6] provides ideal elements, distance-induced preferences, and a unified treatment across social choice settings. Reality-aware social choice [25] contributes the status quo as an ever-present alternative, sidestepping Plott–McKelveystyle impossibilities. Supermajority-based constitutional amendment [1] contributes the σ-parameterisation and the self-referential h-rule for amending σ itself. Constitutional consensus [13] contributes the operational ratification protocol. Deliberative coalition formation [8, 7] and AI mediation [5] contribute proposalgeneration channels.

Our contributions: Our contributions are: (i) the framework, including the constitutional governance rule, the proposal protocol, and supermajority public support—a novel notion between anonymous count and active coalition; (ii) framework-level guarantees—polynomial-time existence, Condorcet-cycle immunity, reality-awareness, anonymity, and neutrality—inherited by any aggregation rule meeting mild hypotheses; (iii) the generalised median as our worked aggregation rule, with a theorem establishing that no misreport weakly dominates sincere voting under the proposal protocol; (iv) a positive analysis of the compromise gap between the best peak and the unconstrained optimum—zero in one dimension, Lipschitz-bounded in general, and narrowed in simulations by a simple proposal heuristic; and (v) instantiation on seven canonical governance settings.

Constitutional Governance in Metric Spaces

Framework

We follow the spatial model of preferences [9, 6]. A metric space (X, d) consists of a set X and a metric d : X × X → R≥0 satisfying symmetry, d(x, y) = 0 ⇐⇒ x = y, and the triangle inequality. We consider n members. Member i specifies an ideal element vi ∈ X, interpreted as i’s most-preferred element; preferences are induced by distance, so i prefers x to y iff d(vi , x) < d(vi , y). We write V = (v1 , . . . , vn ). The Framework, Informally. The framework specifies what each amendable component of a community’s status quo carries and how proposals to amend it are scored. The status quo is structured: it is a tuple of components—a current commission rate, a current budget, a current board, the current bylaws, and the constitution itself—each amendable independently. The constitution attaches to each component a metric space (X, d) (axis i, following Bulteau et al. [6]) and an aggregation rule ϕ with a supermajority threshold σ ∈ [1/2, 1) (axis ii). Each member specifies an ideal element of the space, serving as both vote and initial proposal. In addition, members may submit public proposals from any source— own intuition, coalition deliberation [8, 7], optimization-based aggregation [6], or AI mediation [5]; the framework specifies admissibility rather than provenance. The constitutional governance rule scores each proposal against the status quo via ϕ, adopts the supported proposal of positive maximal score, and otherwise retains the status quo. The same rule governs ordinary and constitutional decisions; only σ differs. Example 1 (A Running Example: A Freelancer Cooperative). Five freelancers— Alice, Bob, Carol, Dan, Eve—found a digital cooperative for matching members with clients. Their initial constitution fixes, for ordinary decisions, ϕ = generalised median and σ = 1/2; for constitutional amendments, σ = 2/3. Their first ordinary decision allocates the budget across marketing (M ), infrastructure (I), and member benefits (B). The metric space is the simplex ∆2 with Euclidean distance; the status quo is s = (1/3, 1/3, 1/3). In the voting round the members submit v1 = (0.5, 0.3, 0.2), v2 = (0.5, 0.2, 0.3), v3 = (0.3, 0.5, 0.2), v4 = (0.2, 0.4, 0.4), v5 = (0.2, 0.6, 0.2). In a public-proposal round, a member submits the geometric median of V as a public proposal, computed by an off-the-shelf solver—approximately ĉ = (0.34, 0.40, 0.27).3 The round-2 proposal set is V ∪ {ĉ}, and direct computation shows ĉ attains the highest median utility among supported proposals; the epoch quiesces with ĉ as the new budget. A subsequent epoch raises the budget threshold from 1/2 to 3/5. The amendment is decided by the same rule, applied at σ = 2/3 via the self-referential h-rule of [1]. We thread this example through the formalisation that follows. Status Quo, Utility, and Proposal Set. Status quo. A distinguished element s ∈ X represents the current value of the component being amended. Following 3

The geometric median is the L1 optimum, not the constitutional rule; here it serves as a public-proposal candidate, scored against the constitutional median.

Shapiro and Talmon

reality-aware social choice [25], s is ever-present and evolving: when a proposal is adopted it becomes the new status quo for subsequent decisions. Utility. The utility of a proposal p ∈ X for a member with ideal element q is u(q, p) := d(q, s) − d(q, p), positive iff the member strictly prefers p to s. By the triangle inequality u(q, p) ≤ d(q, s), with equality at p = q. Proposal set. The framework operates iteratively. At any round r within an epoch, member i holds an immutable vote vi ∈ X (sealed at the start of the epoch; Section 2) and a current public proposal cri ∈ X ∪ {⊥}, which the member may update across rounds. The round-r proposal set is P r = V ∪ {cri : cri ̸= ⊥}, n ≤ |P r | ≤ 2n. Earlier public proposals that have been overridden no longer appear in P r ; the round-r aggregation runs over P r alone. Note, however, that ε-novelty (Section 2) is enforced against all previously-submitted public proposals in the epoch, active or overridden, so a withdrawn public proposal cannot be re-submitted unchanged. In the running example, P 1 = V at the end of the voting round, and P 2 = V ∪ {ĉ} once the geometric-median public proposal is admitted. The Constitutional Governance Rule. The constitution names, per amendable component, an aggregation rule ϕ : Rn → R and a supermajority threshold σ ∈ [1/2, 1). A proposal p is supported at round r if it has supermajority public support: u(vi , p) > 0 for at least ⌈σn⌉ values of i. The supporting set S(p) := {i : u(vi , p) > 0} is publicly observable once votes are revealed. The utility vector of p is u(p) = (u(v1 , p), . . . , u(vn , p)), and its aggregate score is uϕ (p) := ϕ(u(p)). Definition 1 (Constitutional governance rule, per round). The rule applied at round r adopts the supported proposal p∗ ∈ P r with positive maximal uϕ , breaking ties by a constitutionally-specified tie breaking. If no supported proposal in P r has positive uϕ , the round has no winner. The two roles are kept distinct: σ determines which proposals are admissible (the supermajority gate), while ϕ determines which among them is adopted (the maximal score).4 The Proposal Protocol. The rule is operationalised in epochs, each governed by the prevailing constitution. Voting round. All members simultaneously submit sealed votes; once revealed, votes remain fixed for the duration of the epoch. Public-proposal rounds. Once votes are revealed, each subsequent round permits members to submit, update, or withdraw their public proposal cri , subject to five admissibility conditions: at most one current public proposal per member; proposer-preference, u(vi , cri ) > 0; public support, cri is supported under the now-known votes; ε-novelty, cri lies at distance ≥ ε from every vote and every previously-submitted public proposal in the epoch; and improvement, uϕ (cri ) 4

For even n and σ = 1/2, the threshold ⌈σn⌉ = n/2 represents “at least half” rather than a strict majority: a supported proposal needs only n/2 members to strictly prefer it, leaving open the possibility of a 1/2–1/2 split. A community that prefers strict-majority semantics for even n should set σ slightly above 1/2 (so that ⌈σn⌉ ≥ n/2 + 1). This is a design choice the community makes constitutionally.

Constitutional Governance in Metric Spaces

strictly exceeds the preceding round’s winning score (or zero if there was no winner). Termination. Definition 1 runs at the end of each round. The epoch terminates at two-round quiescence: either the same proposal wins two consecutive rounds, or no proposal is supported for two consecutive rounds. The outcome is the quiescent winner, or s if no proposal was supported. Self-Amendment. The constitution attaches to each component i a metric space (Xi , di ), an aggregation rule ϕi , a threshold σi , and a novelty distance εi . Ordinary components—a current rate, a current budget, a current board— are amended at σi = 1/2. Constitutional components—the metric, the rule, the threshold, the novelty distance, and the member set—govern how other components are amended, and are themselves amended at σi > 1/2 by the same rule, applied to the constitutional component’s own metric space. The threshold σi is amended via the self-referential h-rule of [1]. The running example’s second epoch—raising the budget threshold from 1/2 to 3/5—is exactly this. Full details are deferred to Appendix M.

Framework Properties

The constitutional governance rule (Definition 1) is parametrised by an aggregation rule ϕ. This section collects framework-level properties—existence and complexity, anonymity and neutrality, reality-awareness, Condorcet-cycle immunity— each stated with the minimal hypothesis on ϕ it requires. Any instance (the generalised median of Section 4, or any aggregator a community adopts—e.g., the mean in Appendix F) inherits these whenever it meets the hypothesis. Existence and Complexity. The median always exists and is efficiently-computable (note that it satisfies the O(n) hypothesis via linear-time selection). Proposition 1. For any aggregation rule ϕ computable in O(n) time, each round of the constitutional governance rule produces either a round winner or no winner, and runs in O(n · |P r |) ≤ O(n2 ) time. Finite Termination. The proposal protocol of Section 2 runs in epochs of indefinite length, but every epoch terminates after finitely many rounds. We state the guarantee under a mild structural hypothesis. Definition 2 (Totally bounded). A metric space (X, d) is totally bounded if for every ε > 0 and every bounded B ⊆ X, B admits a finite cover by ε-balls. Proposition 2. Fix a constitutionally-specified novelty distance ε > 0. If (X, d) is totally bounded, every epoch of the proposal protocol terminates after finitely many public-proposal rounds. Proof and verification that the seven application settings of Section 5 are totally bounded are in Appendix D. Anonymity and Neutrality. These are treated in Appendix C. Reality-Awareness. Following reality-aware social choice [25], the framework treats the status quo as an ever-present alternative that is retained unless a proposal genuinely improves on it.

Shapiro and Talmon

Proposition 3. If ϕ(0) = 0 ( zero at indifference), the constitutional governance rule retains the status quo unless some supported proposal has uϕ > 0. The generalised median satisfies ϕ(0) = 0, as does any anonymous, monotone aggregator that agrees with indifference at zero. Condorcet-Cycle Immunity. Classical majority rule over three or more alternatives can cycle: a majority may prefer a to b, b to c, and c to a. In onedimensional settings with single-peaked preferences, Black’s median voter theorem [3] guarantees a Condorcet winner. In multidimensional settings, however, Plott [19] showed that a Condorcet winner exists only under a radial-symmetry condition that generically fails, and McKelvey [14] showed that when it fails, the top cycle of majority rule spans the entire space. The constitutional governance rule sidesteps these impossibilities at the framework level—for every aggregation rule ϕ, in every metric space. Theorem 1. For any aggregation rule ϕ, any threshold σ ∈ [1/2, 1), and any metric space (X, d) of any dimension or structure: at every round r, either a supported proposal with positive maximal uϕ is adopted, or the round has no winner. No cycling among proposals is possible. The Plott–McKelvey impossibilities arise from pairwise majority comparisons among alternatives. The constitutional governance rule never forms such comparisons: each proposal is evaluated solely against the fixed status quo s, yielding a real-valued score. The status quo reduces every evaluation to a binary comparison, p versus s, which is well-defined in any number of dimensions. Strategy-Proofness. Strategy-proofness is ϕ-specific; for the generalised median, no misreport weakly dominates sincere voting under the proposal protocol (Theorem 2, Section 4). Monotonicity. Monotonicity is treated in Appendix E.

The Generalised Median

The framework is parametrised by an aggregation rule ϕ. We develop the generalised median as our worked aggregation rule, and study the strategic properties it confers on the constitutional governance rule. The generalised median satisfies the framework-level hypotheses of Section 3: O(n)-computable, symmetric, and zero at indifference. The mean is treated as an alternative utilitarian instantiation in Appendix F. Definition 3 (Generalised median). For σ ∈ [1/2, 1), the generalised median at threshold σ is ϕσ (u) := the ⌈σn⌉-th largest entry of u1 , . . . , un ]. For σ = 1/2 and odd n, ϕσ coincides with the ordinary median. The generalised median has a useful equivalence with support: ϕσ (u(p)) > 0 if and only if at least ⌈σn⌉ entries of u(p) are strictly positive, that is, if and only if p is supported. Under the generalised median instance, the supermajority gate and the positivity of uϕ coincide, so the rule reduces to: adopt the proposal with maximal ϕσ (u(p)) if any has ϕσ > 0, else retain the status quo. Note that personal

Constitutional Governance in Metric Spaces

proposals are subject to the same gate as public proposals: a personal proposal vi is supported only if at least ⌈σn⌉ other members happen to strictly prefer it to the status quo under their revealed votes. The generalised median is motivated by cooperative governance and robustness. Economic models of cooperative behaviour require the cooperative’s decision process to be representable as the maximisation of an objective function [12]; for σ = 1/2, the rule maximises the expected utility of the median member. The median is also robust to outliers: a member with an extreme ideal element shifts the value of ϕσ only insofar as their utility crosses the ⌈σn⌉-th position, not in proportion to the magnitude of their utility. Remark 1 (The median beyond one dimension). In 1D, Black’s median voter theorem justifies the median directly. Beyond 1D, the classical theorem does not apply, but the median retains a privileged status on median spaces [16]—trees, hypercubes, products of lines—as the unique strategy-proof, anonymous, efficient rule. For non-median spaces, the framework sidesteps the multidimensional impossibilities entirely via the status quo (Theorem 1), and cooperative governance provides an independent justification: economic models require maximisation of an objective function, which the median utility supplies. Majoritarity. For σ > 1/2, the median follows a majority. Definition 4 (σ-majoritarity). An aggregation method is σ-majoritarian if, whenever at least ⌈σn⌉ members share an ideal element w that is preferred to s, the rule adopts w. Proposition 4. For σ > 1/2 or odd n, the constitutional governance rule with ϕ = ϕσ is σ-majoritarian. Per-Round Strategic Behaviour. We turn to strategic incentives. We first characterise per-round behaviour, then prove the protocol-level result (Section 4). Proposition 5 (1D dominance, generalised median). In one-dimensional settings with X ⊆ R and d(x, y) = |x − y|, sincere voting is a weakly dominant strategy under ϕσ at any single round, regardless of σ ∈ [1/2, 1) and regardless of public proposals submitted by other members. A worked example of 1D dominance is in Appendix I. In dimensions two and above, the result fails: a single misreporter can manipulate the generalised median over utilities. Proposition 6 (Multidimensional non-SP, generalised median). For X = R2 with Euclidean distance and ϕσ with σ = 1/2, the constitutional governance rule per round is not strategy-proof. The per-round structure of manipulation is characterised by three lemmas in Appendix G; the resulting dichotomy motivates the protocol design of Section 4.

Shapiro and Talmon

Strategy-Proofness Under the Proposal Protocol. The proposal protocol of Section 2 seals votes at the start of the epoch and fixes them throughout, denying the misreporter both the information needed to construct an informed misreport and the option to revise mid-epoch. Under the protocol (and with no information leakage), no misreport weakly dominates sincere voting: for every misreport there is at least one profile of other members’ votes under which sincere strictly outperforms it. Theorem 2 (Protocol-level strategy-proofness, generalised median). For σ = 1/2 and ϕ = ϕσ , under the proposal protocol, no misreport weakly dominates sincere voting: for every member i, every true ideal vi∗ ̸= s, and every misreport ṽi ̸= vi∗ , there exists an epoch (a profile of the other members’ votes and an admissible run) in which member i’s true utility for the outcome is strictly higher under sincere voting than under the misreport. Corollary 1 (1D dominance under the protocol). In one-dimensional settings, sincere voting is a weakly dominant strategy under ϕσ for any σ ∈ [1/2, 1) under the proposal protocol. The case σ > 1/2. The construction in Theorem 2 requires 2(k − 1) ≤ n − 1, where k = ⌈σn⌉; for σ > 1/2, this is infeasible (we would need more voters than n − 1 split between vi∗ and ṽi ). A separating epoch in this regime appears to require a different construction. We conjecture that the result extends to σ > 1/2 but leave it open; intuitively, the higher threshold makes manipulation harder, since flipping support requires changing more entries, and a separating epoch should still exist—but the deciding-vote argument that closes the σ = 1/2 case does not directly generalise. Public-Proposal and Coalition Behaviour. Public-proposal and coalitionchannel behaviour is characterised in Appendix H.

Decision Types

The framework instantiates on a metric space per amendable component (axis i). We adopt the metric-space instantiations of Bulteau et al. [6] for the seven canonical settings of cooperative governance: electing officers, setting rates, allocating a budget, ranking priorities, selecting a board, drafting bylaws, and amending the constitution. Overview. Table 1 summarises the seven settings: the metric space and distance function, the per-round complexity of the constitutional governance rule, and the existence and complexity of Bulteau et al.’s unconstrained Lp aggregation in the same setting. The constitutional governance rule is polynomial-time in every setting, including those for which Lp aggregation is NP-hard, because the rule scores each proposal in P r rather than searching the entire metric space. We work two settings in detail in the main text—1D rate-setting and simplex budgeting, the latter being the running example of Example 1. The other five settings receive compressed treatment below, with full details in Appendix L.

Constitutional Governance in Metric Spaces

Table 1. The seven application settings: metric space, constitutional governance rule (CGR) per-round complexity, and Bulteau et al.’s Lp aggregation. n = members, m = alternatives, |A| = candidates, ℓ = text length. Setting

Metric space

CGR

Lp [6]

Plurality (officers) Discrete on A ∪ {⊥} O(n ) linear 1D elections (rates) X ⊆ R, |x − y| O(n2 ) linear Simplex (budgeting) ∆m−1 , Euclidean O(n2 m) efficient SWF (rankings) Permutations SA , swap distance O(n2 m log m) NP-hard Committee (boards) Subsets 2A , symmetric difference O(n2 |A|) NP-hard (p > 1) Legislation (bylaws) Strings Σ ∗ , weighted Levenshtein O(n2 ℓ2 ) NP-hard Amendments Per component (see §2) polynomial — 2

Worked Setting: Setting a Rate. A community must set various parameters that take values on a one-dimensional scale: a commission rate, a membership fee, a minimum hourly wage, a fraction of revenue allocated to reserves. Each member proposes a value; the current value is the status quo. Model. The metric space is X ⊆ R with d(x, y) = |x − y|. The status quo s ∈ X is the current value. Each member i specifies an ideal value vi ∈ X. The constitutional threshold σ is constitutionally specified per parameter. The 1D structure admits a sharp characterisation of the generalised median’s per-round outcome; see Appendix I. Proposition 12 drives the per-round strategy-proofness result of Proposition 5: in 1D, the winner depends only on the positional voter vm , which a single misreport can move only weakly away from the misreporter’s ideal element. Example 2 (Setting a commission rate). A cooperative of five members sets the commission rate at σ = 1/2. The current rate is s = 20%. Members propose v1 = 10%, v2 = 15%, v3 = 18%, v4 = 22%, v5 = 25%; the median is vm = v3 = 18%. The median utility of each proposal: p 10% 15% 18% 22% 25% ϕ1/2 (u(p)) −6 −1 +2 −2 −5 Only p = 18% is supported, and it has positive median utility, so the rate is amended to 18%. Worked Setting: Allocating a Budget. A community must allocate its budget across categories: marketing, infrastructure, member benefits, a reserve fund. Each member proposes a distribution; the current allocation is the status quo. This is the running example of Example 1. Model. Let A be the set of categories,Pm = |A|. The metric space is the simplex ∆m−1 = {(w1 , . . . , wm ) ∈ i Rm ≥0 : i w = 1} with the Euclidean metric d(x, y) = ∥x − y∥2 . The status quo m−1 s∈∆ is the current allocation. Each member i specifies an ideal allocation vi ∈ ∆m−1 . Round complexity. For each p ∈ P r , computing the utility vector takes O(nm) time, evaluating ϕσ takes O(n) time. Over |P r | ≤ 2n proposals, the per-round cost is O(n2 m). Comparison with L1 over the simplex. Bulteau et

Shapiro and Talmon

al.’s L1 aggregation over the simplex returns the geometric median of the votes, which is computable in Õ(nm) time. The geometric median is in general not an element of V , but the constitutional governance rule restricts to P r . Under the running example, the geometric median was admitted as a public proposal (Example 1) and won the round; this illustrates the open public-proposal channel admitting the optimization-based proposal alongside the peaks. The rule scores it under ϕσ against the constitutional median, not under the rule used to compute it. Experimental support for median rules on the simplex. Puppe and Rollmann [22] compared mean and median voting rules on the simplex in a laboratory experiment, finding that median rules elicit substantially more sincere voting while mean rules induce strategic polarisation. This empirical finding aligns with the per-round strategy-proofness gap between the median and mean instances developed in Section 4. Plurality (electing officers). The five remaining settings receive compact treatment here, with full details in Appendix L (Appendix M for amendments). The metric space is X = A ∪ {⊥} where A is the candidate set and ⊥ denotes the vacant position; d is the discrete metric. With s = ⊥ as the status quo, member utilities are binary: 1 if the proposal matches the member’s preferred candidate, 0 otherwise. The rule selects the candidate with the most supporters, provided that candidate has σ-supermajority support; otherwise the position remains vacant. Social welfare functions (ranking priorities). The metric space is X = SA , the set of permutations over A, with the swap distance (number of adjacent transpositions). Bulteau et al.’s Lp aggregation here corresponds to the Kemeny ranking, which is NP-hard. The constitutional governance rule selects the supported ranking with maximal score in O(n2 m log m) time, trading optimality over the entire space for tractability over the proposal set. Committee elections (selecting a board). The metric space is X ⊆ 2A (subsets of eligible members), with the symmetric difference d(x, y) = |x△y|. Bulteau et al.’s Condorcet aggregation is coNP-hard and Lp for p > 1 is NP-hard. The constitutional governance rule selects the supported board with maximal score in O(n2 |A|) time. With s = ∅ as the status quo (no board), member utilities measure how many of their preferred members the proposed board includes. Legislation (drafting bylaws). A community must draft and amend the bylaws governing membership, decision-making, and dispute resolution. This is the most challenging setting in Bulteau et al. [6]: Lp aggregation is NP-hard for all p ≥ 1. The constitutional governance rule applies regardless: each member submits a text vi ∈ Σ ∗ , the rule scores each proposal under the metric, and the supported text with maximal score is adopted in O(n2 ℓ2 ) time, where ℓ is the length of the longest proposed text. Constitutional amendments. Each amendable constitutional component lives in its own metric space—discrete for the membership set, R for scalar parameters, [1/2, 1) under the h-rule for the threshold itself, a domain of admissible aggregators for ϕ, and weighted Levenshtein for textual provisions—and is amended by

Constitutional Governance in Metric Spaces

the constitutional governance rule applied to that space at σ > 1/2. Section 2 sketched this; full details are in Appendix M. Remark 2 (Semantic metrics). A note on the metric for legislation. Bulteau et al. adopt a weighted Levenshtein distance, a syntactic measure that counts character-level edit operations without regard to meaning. However, two bylaws differing by a synonym substitution are syntactically distant but semantically identical; two differing by a single negation are syntactically close but semantically opposite. Thus, what governance requires is a semantic distance between texts. The constitutional governance rule is metric-agnostic: any distance function over Σ ∗ plugs into the framework with no change to the rule, the protocol, or any framework-level guarantee. Recent work on AI mediation [5] and large language models makes semantic distance increasingly tractable, and the framework absorbs such distances directly. We retain the syntactic Levenshtein distance here for comparability with Bulteau et al.; the design of governance-appropriate semantic distances is an active, orthogonal research direction.

The Compromise Gap: An Empirical Study

The constitutional governance rule selects an outcome from the proposal set P r rather than from the full metric space X. This trades unconstrained optimality for polynomial-time existence (Section 3) and the open-source-of-proposals semantics that a community can actually run (Section 2). We quantify the tradeoff via the compromise gap: the difference between the best peak and the unconstrained optimum. The compromise gap is what public proposals close: any public proposal from any source—a member’s intuition, a coalition’s deliberation, an optimization algorithm, or an AI mediator—narrows the gap when it scores higher than the best peak. Definition and Scope. Fix a metric space (X, d), a vote profile V = {v1 , . . . , vn }, a status quo s, an aggregation rule ϕ, and a threshold σ. Let OPTϕ (V, s) := sup ϕ(u(x)), PEAKϕ (V, s) := max ϕ(u(p)) x∈X

p∈V

be the unconstrained optimum and the best peak. The compromise gap is the non-negative quantity CGϕ (V, s) := OPTϕ (V, s) − PEAKϕ (V, s) ≥ 0. We restrict attention to profiles with OPTϕ (V, s) > 0, since otherwise the status quo is retained under both the unconstrained and the proposal-restricted rules and the comparison is vacuous. A public proposal c ∈ X closes the gap (in part or whole) when ϕ(u(c)) > PEAKϕ (V, s). The gap is fully closed if the proposal set contains an element attaining OPTϕ . The 1D result below is specific to the generalised median; the Lipschitz bound and the simulations apply to any 1Lipschitz ϕ and any (X, d). Zero Gap in One Dimension. The first result is a clean positive: in one dimension with the generalised median, peaks suffice—the gap is zero. Theorem 3 (Zero gap in 1D). Let X ⊆ R with d(x, y) = |x − y|, let n be odd, and let σ = 1/2. Then CGϕσ (V, s) = 0 for every V ⊆ X and every s ∈ X.

Shapiro and Talmon

Theorem 3 is the median voter theorem expressed in our framework: in 1D with odd electorate, the median peak is both the unconstrained optimum and a peak. The result extends to the constitutional scalar parameters of Appendix M.3 (thresholds, timeouts, novelty distances) under the same argument. General Bound. In dimensions two and above, the gap can be positive; minimal examples are in Appendix K. The phenomenon is intrinsic to multidimensional settings: the unconstrained optimum need not coincide with any peak. The following bound holds in full generality. Proposition 7 (Lipschitz bound). If ϕ : Rn → R is 1-Lipschitz in the ℓ∞ norm, then CGϕ (V, s) ≤ minp∈V d(x∗ , p), where x∗ ∈ arg maxx∈X ϕ(u(x)). Both the generalised median and the mean are 1-Lipschitz in ℓ∞ . For the generalised median, this follows from the fact that the sort operator is 1-Lipschitz P in ℓ∞ , soP the order statistic inherits the property. For the mean, | n1 i (ui − u′i )| ≤ n1 i |ui − u′i | ≤ ∥u − u′ ∥∞ . The bound is tight in Example 4, where d(h, V ) = 1 = CG. Remark 3. Sharper bounds than Proposition 7 would exploit the structure of the metric space and the aggregation rule. Two directions are natural. First, instance-dependent bounds: in median spaces [16] (trees, hypercubes, products of lines), generalised medians have additional structure that may yield tighter analytic bounds. Second, smoothed-analysis bounds: under realistic priors on V (e.g., uniform sampling, log-concave distributions), expected CG may admit polynomial-of-n rates rather than worst-case bounds. Both directions are open. We turn to algorithmic gap-closing. Closing the Gap: Pairwise Compromise. The framework’s open publicproposal channel admits public proposals from any source. We study a simple, polynomial-time source—pairwise proposal combinations—and show empirically that it closes a substantial fraction of the gap in realistic configurations. The formal definition of Heuristic P and its complexity are in Appendix J. Heuristic P formalises the simplest public-proposal move: blend two existing proposals into a candidate, score it under the framework’s own rule. The gating step ensures P never recommends a public proposal strictly worse than the current best. The heuristic is proposal-native: input, output, and search space all live in the proposal set or its pairwise combinations. Heuristic P carries no worst-case approximation guarantee. Configurations in which x∗ lies far from every pairwise combination of existing proposals are not addressed by P. We turn to empirical evidence. Simulation: Closing the Gap in Practice. We simulated the compromise gap and Heuristic P across four of the application settings: 2D Euclidean (a stylised common case), the simplex under Euclidean distance, the hypercube under symmetric difference (Appendix L.3), and permutations under swap distance (Appendix L.2). For each profile, we compute OPT exactly (by enumeration in finite spaces, by grid search elsewhere), compute PEAK, and run Heuristic P. We report three statistics per configuration:

Constitutional Governance in Metric Spaces

– Positive-CG frequency: the fraction of profiles with CG > 0, when OPT > 0. – Gap-closing ratio: the mean of (ϕ(u(c∗ ))−PEAK)/CG over profiles with CG > 0 and Heuristic P returning c∗ ̸= ⊥. – Hit rate: the fraction of profiles on which Heuristic P returns a non-⊥ output. Profiles are generated by sampling peaks uniformly: in 2D Euclidean, peaks are drawn uniformly from a bounded region; on the simplex, from the uniform Dirichlet distribution; on the hypercube, uniformly from 2A ; on permutations, uniformly from SA . Sample sizes: 200–500 profiles per configuration. Table 2 reports nine representative rows; the full sweep across all twenty-seven configurations is in Appendix N. Table 2. Compromise gap and Heuristic P across four settings. “Gap-closing” = mean fraction of CG closed by Heuristic P on profiles with CG > 0. Setting

n CG > 0 Gap-closing Hit rate

2D Euclidean 5 2D Euclidean 21 2D Euclidean 51 Simplex (m = 4) 5 Simplex (m = 4) 21 Hypercube (|A| = 8) 5 Hypercube (|A| = 8) 21 Permutations (m = 5) 5 Permutations (m = 5) 21

99% 100% 96% 97% 99% 69% 36% 63% 32%

41% 79% 96% 52% 81% 97% 100% 82% 99%

67% 96% 98% 78% 96% 66% 36% 53% 31%

So, Heuristic P closes a growing fraction of CG as n grows, exceeding 79% at n = 21 in every continuous setting and reaching near-exact on the hypercube. The simulation complements the theoretical results: the worst-case Lipschitz bound is conservative; the empirical gap is consistently smaller; and Heuristic P, the simplest possible public-proposal generator, closes most of it in practice.

Outlook

We have presented a framework that integrates aggregation over metric spaces, reality-aware social choice, supermajority-based constitutional amendment, constitutional consensus, deliberative coalition formation, and AI mediation into a polynomial-time process; we close with implications and open questions. What the framework provides. An aggregation rule that scales across decision types (constitution, rates, budgets, rankings, boards, bylaws), a supermajority gate, and an open channel admitting proposals from any source. Constitutional design reduces to specifying, per component, the metric space, aggregation rule, threshold, and novelty distance. Cooperative governance and the choice of ϕ. The generalised median is motivated by cooperative governance: economic models require the cooperative’s decision process to be representable as the maximisation of an objective function,

Shapiro and Talmon

and for σ = 1/2 the rule maximises the median member’s utility. A community whose objective is utilitarian would select the mean instance (Appendix F). The choice is itself a constitutional decision. The public-proposal market. Section 6 suggests an operational picture: each round is a market in which public proposals compete under ϕ. The framework admits proposals from any source—pairwise heuristics, optimization, AI mediation, coalition deliberation—on equal footing. In NP-hard settings, approximation algorithms and AI mediators are first-class participants: an approximate optimum that beats the peaks wins. Five future work directions. Strategy-proofness for σ > 1/2. Theorem 2 establishes ex-post no-weak-dominance for σ = 1/2. The construction does not extend to σ > 1/2, but we conjecture the result holds (Section 4). A separating epoch for higher thresholds is likely to require a different decisive-vote argument. Sharper compromise gap bounds. The Lipschitz bound of Proposition 7 is loose. Two directions are open: instance-dependent bounds exploiting median-space structure, and smoothed-analysis bounds under realistic priors on V . Cooperative economics. The connection to economic models of cooperatives should be developed, incorporating heterogeneous member preferences, multi-dimensional decision spaces, and the economic consequences of generalised median versus mean instances. Implementation and empirical evaluation. The framework is concrete enough to deploy. Empirical evaluation in realistic cooperative settings— deliberation dynamics, round cadence choices, the interplay between vote updates and public-proposal submissions over time—would complement the formal analysis with operational evidence. Architectural context. The framework can serve as a decision layer for grassroots digital communities [24], alongside the consensus layer of [13] and the federation layer of [26]. Composing the three layers into a complete grassroots-governance architecture is a natural direction.

References 1. Abramowitz, B., Shapiro, E., Talmon, N.: In the beginning there were n agents: Founding and amending a constitution. In: Proceedings of ADT ’21. pp. 119–131 (2021) 2. Anshelevich, E., Bhardwaj, O., Elkind, E., Postl, J., Skowron, P.: Approximating optimal social choice under metric preferences. Artificial Intelligence 264, 27–51 (2018) 3. Black, D.: On the rationale of group decision-making. Journal of Political Economy 56(1), 23–34 (1948) 4. Brady, R.L., Chambers, C.P.: A spatial analogue of May’s theorem. Social Choice and Welfare 49(3–4), 657–669 (2017) 5. Briman, E., Shapiro, E., Talmon, N.: Ai-generated compromises for coalition formation: Modeling, simulation, and a textual case study. In: Theoretical Aspects of Rationality and Knowledge (TARK 2025). EPTCS, vol. 437, pp. 417–432 (2025). https://doi.org/10.4204/EPTCS.437.32 6. Bulteau, L., Shahaf, G., Shapiro, E., Talmon, N.: Aggregation over metric spaces: Proposing and voting in elections, budgeting, and legislation. Journal of Artificial Intelligence Research 70, 1413–1439 (2021)

Constitutional Governance in Metric Spaces

7. Elkind, E., Ghosh, A., Goldberg, P.: Complexity of deliberative coalition formation. arXiv preprint arXiv:2202.12594 (2022) 8. Elkind, E., Grossi, D., Shapiro, E., Talmon, N.: United for change: Deliberative coalition formation to change the status quo. In: Proceedings of AAAI ’21. vol. 35, pp. 5339–5346 (2021) 9. Enelow, J.M., Hinich, M.J.: The Spatial Theory of Voting: An Introduction. Cambridge University Press (1984) 10. Goel, A., Krishnaswamy, A.K., Munagala, K.: Metric distortion of social choice rules: Lower bounds and fairness properties. In: Proceedings of the 2017 ACM Conference on Economics and Computation (EC ’17). pp. 287–304. ACM (2017) 11. Hakimi, S.L.: Optimum locations of switching centers and the absolute centers and medians of a graph. Operations Research 12(3), 450–459 (1964) 12. Hart, O., Moore, J.: The governance of exchanges: members’ cooperatives versus outside ownership. Oxford Review of Economic Policy 12(4), 53–69 (1996) 13. Keidar, I., Lewis-Pye, A., Shapiro, E.: Constitutional consensus. arXiv preprint arXiv:2505.19216 (2025) 14. McKelvey, R.D.: Intransitivities in multidimensional voting models and some implications for agenda control. Journal of Economic Theory 12(3), 472–482 (1976) 15. Meir, R., Shahaf, G., Shapiro, E., Talmon, N.: Sybil-resilient social choice with partial information. Journal of Artificial Intelligence Research 73, 1517–1545 (2022). https://doi.org/10.1613/jair.1.13390 16. Nehring, K., Puppe, C.: The structure of strategy-proof social choice — Part I: General characterization and possibility results on median spaces. Journal of Economic Theory 135(1), 269–305 (2007) 17. Nehring, K., Puppe, C.: Resource allocation by frugal majority rule (2019), working Paper Series in Economics No. 131, Karlsruhe Institute of Technology 18. Peters, H., van der Stel, H., Storcken, T.: Generalized median solutions, strategyproofness and strictly convex norms. ZOR – Methods and Models of Operations Research 38(1), 35–53 (1993) 19. Plott, C.R.: A notion of equilibrium and its possibility under majority rule. The American Economic Review 57(4), 787–806 (1967) 20. Procaccia, A.D., Rosenschein, J.S.: The distortion of cardinal preferences in voting. In: Proceedings of the 10th International Workshop on Cooperative Information Agents (CIA ’06). Lecture Notes in Computer Science, vol. 4149, pp. 317–331. Springer (2006) 21. Procaccia, A.D., Tennenholtz, M.: Approximate mechanism design without money. In: Proceedings of the 10th ACM Conference on Electronic Commerce (EC ’09). pp. 177–186. ACM (2009) 22. Puppe, C., Rollmann, J.: Mean versus median voting in multi-dimensional budget allocation problems: A laboratory experiment. Games and Economic Behavior 130, 309–330 (2021) 23. Shahaf, G., Shapiro, E., Talmon, N.: Sybil-resilient reality-aware social choice. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence. pp. 572–579 (2019) 24. Shapiro, E.: Grassroots distributed systems: Concept, examples, implementation and applications (brief announcement). In: 37th International Symposium on Distributed Computing (DISC 2023). (Extended version: arXiv:2301.04391). pp. 47:1, 47:7. LIPICS, Italy (2023) 25. Shapiro, E., Talmon, N.: Incorporating reality into social choice. In: Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems. pp. 1188–1192 (2018)

Shapiro and Talmon

26. Talmon, N., Shapiro, E.: Grassroots federation: Fair democratic governance at scale. arXiv preprint arXiv:2505.02208; also Proc. of AAMAS’26 (2025)

Proofs

This appendix collects the proofs of results stated in the body, in document order. Proposition 1. For any aggregation rule ϕ computable in O(n) time, each round of the constitutional governance rule produces either a round winner or no winner, and runs in O(n · |P r |) ≤ O(n2 ) time. Proof. The round-r proposal set P r is finite, with n ≤ |P r | ≤ 2n. For each proposal p ∈ P r : computing the utility vector u(p) ∈ Rn takes O(n) time (assuming d evaluates in O(1)); evaluating ϕ(u(p)) takes O(n) time by hypothesis; checking support takes O(n) time. Selecting the supported proposal with positive maximal uϕ takes O(|P r |) time. The total is O(n · |P r |) ≤ O(n2 ). ⊔ ⊓ Proposition 2. Fix a constitutionally-specified novelty distance ε > 0. If (X, d) is totally bounded, every epoch of the proposal protocol terminates after finitely many public-proposal rounds. Proof. We bound the total number of distinct public proposals that can be admitted in a single epoch, which suffices: once no further admissible public proposal exists, two-round quiescence (no public proposal admitted, hence the same proposal set and same winner) is reached in at most one additional round. Fix an epoch with sealed votes V = {v1 , . . . , vn }. By the proposer-preference condition, every admissible public proposal c satisfies u(vi , c) > 0 for the proposer i, i.e., d(vi , c) < d(vi , s). Hence every admissible public proposal lies in n [ B := Bd(vi ,s) (vi ), i=1

the union of open balls around the votes with radii equal to their distances from the status quo. The set B is bounded; since (X, d) is totally bounded, B admits a finite cover by ε/2-balls. Let N denote the size of such a cover. The ε-novelty condition requires that every admitted public proposal lie at distance ≥ ε from every previously-submitted public proposal (active or overridden) and from every vote. Two public proposals in the same ε/2-ball are at distance < ε from each other by the triangle inequality, so each ε/2-ball contains at most one admitted public proposal across the entire epoch. Hence the number of distinct public proposals admitted in the epoch is at most N , finite. When no further admissible public proposals exist the round produces the same winner (or no winner) as the previous round. Two-round quiescence is reached, and the epoch terminates. ⊓ ⊔ Proposition 3. If ϕ(0) = 0 ( zero at indifference), the constitutional governance rule retains the status quo unless some supported proposal has uϕ > 0.

Constitutional Governance in Metric Spaces

Proof. The utility vector at the status quo is u(s) = 0, so uϕ (s) = ϕ(0) = 0. By Definition 1, a proposal is adopted only if it is supported and uϕ (p) > 0; otherwise, the status quo is retained. ⊔ ⊓ Theorem 1. For any aggregation rule ϕ, any threshold σ ∈ [1/2, 1), and any metric space (X, d) of any dimension or structure: at every round r, either a supported proposal with positive maximal uϕ is adopted, or the round has no winner. No cycling among proposals is possible. Proof. Each proposal p ∈ P r receives a real-valued aggregate score uϕ (p) ∈ R. The maximum of a finite set of real numbers always exists, so when at least one supported proposal has uϕ > 0, the set of supported proposals attaining the maximum is non-empty and the constitutionally-specified tie-break selects one for adoption. Otherwise no proposal is adopted. Since each proposal is compared only against the status quo (yielding a real number) and never against another proposal, no pairwise majority comparison enters the rule, and the strict total order on real numbers precludes cycling. ⊓ ⊔ Proposition 4. For σ > 1/2 or odd n, the constitutional governance rule with ϕ = ϕσ is σ-majoritarian. Proof. Suppose at least ⌈σn⌉ members share ideal element w ̸= s. For the proposal p = w, every member with vi = w has u(vi , w) = d(w, s), the maximum possible utility (by the triangle inequality, u(vi , p) ≤ d(vi , s) with equality at p = vi ). The ⌈σn⌉-th largest entry of u(w) is therefore d(w, s), so ϕσ (u(w)) = d(w, s) > 0 and w is supported. For any p′ ̸= w, each of the ⌈σn⌉ members at w has u(w, p′ ) = d(w, s) − d(w, p′ ) < d(w, s). So at least ⌈σn⌉ entries of u(p′ ) are strictly below d(w, s), leaving at most n − ⌈σn⌉ entries that could attain d(w, s). For σ > 1/2 or odd n, n − ⌈σn⌉ < ⌈σn⌉, so the ⌈σn⌉-th largest entry of u(p′ ) is strictly below d(w, s). Hence ϕσ (u(p′ )) < ϕσ (u(w)), and w is the unique winner. ⊔ ⊓ Proposition 5 (1D dominance, generalised median). In one-dimensional settings with X ⊆ R and d(x, y) = |x − y|, sincere voting is a weakly dominant strategy under ϕσ at any single round, regardless of σ ∈ [1/2, 1) and regardless of public proposals submitted by other members. Proof. Order the votes as v(1) ≤ · · · ≤ v(n) , and let k = ⌈σn⌉. In 1D, the utility u(vq , p) = |vq − s| − |vq − p| is monotone in vq for each fixed p (non-decreasing when p > s, non-increasing when p < s); hence the k-th largest entry of u(p) equals u(vm , p) for vm := v(k) (when p > s) or v(n−k+1) (when p < s). Thus ϕσ (u(p)) = |vm − s| − |vm − p| ≤ |vm − s|, with equality only at p = vm ; the winning proposal in V is the one closest to vm , and no public proposal alters this winner. 0 Fix member i with true ideal vi∗ ∈ R. Let vm be the k-th positional vote ′ under sincere reporting and vm under any misreport ṽi . The member’s true ′ ′ utility for the winner is |vi∗ − s| − |vi∗ − vm |, decreasing in |vi∗ − vm |. We show ∗ 0 ∗ ′ |vi − vm | ≤ |vi − vm | for every ṽi .

Shapiro and Talmon

0 0 0 If vi∗ > vm , any misreport ṽi ≥ vm leaves vm unchanged; any misreport 0 ′ 0 ṽi < vm shifts the k-th positional vote leftward, giving vm ≤ vm < vi∗ and ∗ ′ ∗ 0 ∗ 0 ∗ 0 |vi − vm | ≥ |vi − vm |. The case vi < vm is symmetric. If vi = vm , any misreport 0 either leaves vm fixed or shifts to a neighbouring vote, weakly farther from vi∗ . ⊔ ⊓

Proposition 6 (Multidimensional non-SP, generalised median). For X = R2 with Euclidean distance and ϕσ with σ = 1/2, the constitutional governance rule per round is not strategy-proof. Proof (Proof sketch). Take n = 3, s = (0, 0), true ideals v1∗ = (1, 0), v2∗ = (0, 1), v3∗ = (−1, −1). Under sincere voting with no public proposals, no proposal is 1/2supported with positive median utility, so the status quo is retained and member 1’s true utility is 0. Under misreport ṽ1 = (0.5, 0.5), the proposal (0.5, 0.5) has utilities approximately (0.707, 0.293, −0.707) on reported votes, with median 0.293 > 0 and two positive entries;√(0.5, 0.5) is supported and is the winner. ⊔ ⊓ Member 1’s true utility for it is 1 − 0.5 ≈ 0.293 > 0. Theorem 2 (Protocol-level strategy-proofness, generalised median). For σ = 1/2 and ϕ = ϕσ , under the proposal protocol, no misreport weakly dominates sincere voting: for every member i, every true ideal vi∗ ̸= s, and every misreport ṽi ̸= vi∗ , there exists an epoch (a profile of the other members’ votes and an admissible run) in which member i’s true utility for the outcome is strictly higher under sincere voting than under the misreport. Proof. Fix member i, true ideal vi∗ ̸= s, and misreport ṽi ̸= vi∗ ; let k = ⌈n/2⌉. We construct a separating profile: k − 1 of the other members vote vi∗ , k − 1 vote ṽi , and the remaining n − 2k + 1 vote s. (For odd n, n − 2k + 1 = 0; for even n, exactly one member votes s.) No public proposals are submitted in any round, so the analysis reduces to the voting round. Sincere case. Member i votes vi∗ . Total votes: k at vi∗ , k − 1 at ṽi , n − 2k + 1 at s. – Proposal vi∗ : the k voters at vi∗ each have utility d(vi∗ , s); the k − 1 voters at ṽi each have utility d(ṽi , s) − d(ṽi , vi∗ ) ≤ d(vi∗ , s) (triangle inequality); the voters at s have utility −d(vi∗ , s). The k-th largest is d(vi∗ , s), so ϕσ (u(vi∗ )) = d(vi∗ , s) > 0 and vi∗ is supported. – Proposal ṽi : the k − 1 voters at ṽi have utility d(ṽi , s); the k voters at vi∗ have utility d(vi∗ , s) − d(vi∗ , ṽi ) < d(vi∗ , s); the rest have utility −d(ṽi , s). Only k − 1 < k entries equal d(ṽi , s), so the k-th largest is at most d(vi∗ , s) − d(vi∗ , ṽi ) < d(vi∗ , s). Hence ϕσ (u(vi∗ )) > ϕσ (u(ṽi )) and vi∗ wins. The epoch quiesces at vi∗ , and member i’s true utility is d(vi∗ , s). Misreport case. Member i votes ṽi . Total votes: k − 1 at vi∗ , k at ṽi , n − 2k + 1 at s. If ṽi ̸= s: by symmetric analysis, ϕσ (u(ṽi )) = d(ṽi , s) > 0 and ṽi wins. Member i’s true utility for ṽi is d(vi∗ , s) − d(vi∗ , ṽi ) < d(vi∗ , s).

Constitutional Governance in Metric Spaces

If ṽi = s: proposal ṽi = s has all-zero utilities, ϕσ = 0, and is not supported; proposal vi∗ has only k − 1 positive entries (the voters at vi∗ , since member i now votes s), so it is not supported either. No proposal is supported, the status quo is retained, and member i’s true utility is 0 < d(vi∗ , s). In every case, the misreport yields strictly lower true utility than sincere voting. ⊔ ⊓ Corollary 1 (1D dominance under the protocol). In one-dimensional settings, sincere voting is a weakly dominant strategy under ϕσ for any σ ∈ [1/2, 1) under the proposal protocol. Proof. By Proposition 5, the per-round winner is the proposal closest to the ⌈σn⌉-th positional vote, and public proposals do not alter it. Within an epoch votes are fixed, so the per-round winner is invariant across rounds; the epoch quiesces at this winner. Per-round dominance transfers to the epoch outcome. ⊔ ⊓ Theorem 3 (Zero gap in 1D). Let X ⊆ R with d(x, y) = |x − y|, let n be odd, and let σ = 1/2. Then CGϕσ (V, s) = 0 for every V ⊆ X and every s ∈ X. Proof. By Proposition 12, for every x ∈ X the median utility is ϕσ (u(x)) = |vm − s| − |vm − x|, where vm is the positional median of V . This expression is uniquely maximised at x = vm ∈ V , with value |vm − s|. Hence OPTϕσ (V, s) = |vm − s| is attained at a peak, and CGϕσ (V, s) = 0. ⊔ ⊓ Proposition 7 (Lipschitz bound). If ϕ : Rn → R is 1-Lipschitz in the ℓ∞ norm, then CGϕ (V, s) ≤ minp∈V d(x∗ , p), where x∗ ∈ arg maxx∈X ϕ(u(x)). Proof. For every member with ideal q and every pair of points x∗ , p ∈ X, |u(q, x∗ ) − u(q, p)| = |d(q, p) − d(q, x∗ )| ≤ d(x∗ , p) by the reverse triangle inequality. Hence ∥u(x∗ ) − u(p)∥∞ ≤ d(x∗ , p). The 1Lipschitz hypothesis on ϕ gives |ϕ(u(x∗ )) − ϕ(u(p))| ≤ d(x∗ , p). Minimising over p ∈ V yields the claim. ⊔ ⊓

Related Work

Aggregation over metric spaces. Bulteau, Shahaf, Shapiro, and Talmon [6] introduced the framework of aggregation over metric spaces, studying Condorcet aggregation and the Lp family across six social choice settings. The present work uses their metric-space instantiations and admits the Lp family as one source of public proposals (Section 6); the constitutional governance rule trades unconstrained optimality for polynomial-time existence and supermajority discipline. Reality-aware social choice. Shapiro and Talmon [25] introduced the status quo as a distinguished, ever-present alternative in social choice, and showed how it breaks Condorcet cycles. This has been applied to sybil-resilient voting [23, 15] and deliberative coalition formation [8, 7]. The constitutional governance rule places the status quo at the centre: every proposal is compared only to it, yielding a scalar score that cannot cycle in any metric space (Theorem 1).

Shapiro and Talmon

Constitutional governance and consensus. Abramowitz, Shapiro, and Talmon [1] studied the founding and amendment of constitutions, deriving from natural axioms that the initial decision rule must be simple majority and that the unique self-referential amendment process is the h-rule. Keidar, Lewis-Pye, Shapiro, and Talmon [13] instantiated this in the constitutional consensus protocol, combining democratic decision processes for amending the participant set, threshold, and timeout with a Byzantine-fault-tolerant consensus protocol. The present work incorporates the σ-parameterisation and the structural distinction between ordinary and constitutional components, enabling unified treatment of decisions and amendments under a single rule. Median spaces and strategy-proofness. Nehring and Puppe [16] characterised the domains on which strategy-proof, anonymous, and efficient social choice functions exist, identifying median spaces as the exact boundary; Brady and Chambers [4] provided axiomatic characterisations of the median as the unique rule satisfying anonymity and Maskin monotonicity. These results provide theoretical grounding for the generalised median instance beyond one dimension. Nehring and Puppe [17] also proposed the frugal majority rule for budget allocation, philosophically close to our setting in starting from peaks alone; the constitutional governance rule differs by restricting the outcome to actual proposals, producing a unique winner, and anchoring on the status quo. Puppe and Rollmann [22] provided experimental support for median rules over mean rules in budget allocation. Metric distortion and facility location. The metric distortion literature [2, 10, 20] studies how well voting rules approximate optimal social choice when voters and alternatives lie in a common metric space; the median objective admits constant-factor approximation with ordinal information. Hakimi [11] established that on networks the facility location minimising total distance is always at a vertex—classical justification for restricting outcomes to discrete alternatives— and Procaccia and Tennenholtz [21] explored mechanism-design analogues. The compromise gap of Section 6 is a metric-distortion-style quantity, measuring how much restriction to the proposal set costs. The spatial model. The spatial model of elections [9] infers preferences from voter ideal points using an underlying metric, extended in many directions [18]. The framework adopts the spatial model’s distance-induced preferences but differs in restricting solutions to member proposals and centring the status quo.

Anonymity and Neutrality

The rule is neutral among proposals by construction: it depends on a proposal p only through its utility vector u(p), which is computed from d, s, and V . No proposal-specific label, identity, or exogenous weight enters. The rule is anonymous whenever ϕ is a symmetric function of its arguments: under this hypothesis, the rule depends on V only through the multiset of utilities. The generalised median is symmetric, hence the median instance is anonymous.

Constitutional Governance in Metric Spaces

Finite Termination: Verification

The proof of Proposition 2 is in Appendix A. The seven application settings of Section 5 are all totally bounded: bounded subsets of R are totally bounded; the simplex is compact; the discrete, permutation, and subset metrics are defined on finite sets; and balls in Σ ∗ under weighted Levenshtein distance are finite, since strings within a bounded edit distance of a fixed string over a finite alphabet are finitely many.

Monotonicity

Definition 5 (Vote-to-outcome monotonicity). An aggregation method is monotone if, for every vote profile V and every co-winner w, changing a member’s ideal element to w does not cause w to lose. Proposition 8. In one-dimensional settings (with the absolute-value metric) and σ = 1/2, the constitutional governance rule with the generalised median is monotone. Proof. The median utility of a proposal p equals u(vm , p) = |vm − s| − |vm − p|, where vm is the positional median of the votes (a standard 1D fact, formally established in Section 5). When member i changes from vi to w (a co-winner), ′ vm moves towards w or stays fixed; let vm denote the new median. For w: ′ |vm − w| ≤ |vm − w|, so the median utility of w does not decrease. For any p ̸= w ′ ′ −w| −p| ≥ |vm that was a co-winner: |vm −p| ≥ |vm −w| before the move, and |vm ′ ′ after (since vm moves towards w, p remains weakly farther from vm than w is). Hence the median utility of w remains at least that of p in the new profile. ⊔ ⊓ In general metric spaces, monotonicity does not hold; the counterexample below uses seven members and exhibits a profile in which the winner w loses after a member moves to w. The mechanism is that the departing member’s utility for a competing proposal sits at the median position; when the member moves, the next value in the sorted order is revealed at the median and exceeds the unchanged median utility of w. Public-proposal-channel monotonicity. The framework separates two roles. The vote is an immutable, sealed expression of preference. The public proposal is a submission a member is willing to support. Vote-to-outcome monotonicity (Definition 5) is the right axiom for rules in which the vote is the only support mechanism (as in Bulteau et al. [6], whose Lp aggregator is non-monotone for every p > 1). Under our framework, where support is expressed via the publicproposal channel, the relevant axiom is public-proposal-channel monotonicity: submitting a proposal as a public proposal never decreases the submitter’s utility. This holds for the constitutional governance rule by construction, regardless of metric space dimension—admitting a public proposal leaves all other proposals’ scores unchanged, so either the winner is unchanged or it becomes the submitted public proposal. The vote-to-outcome failure in higher dimensions therefore identifies a real but axiom-mismatched concern; the framework’s twochannel design defangs it.

Shapiro and Talmon

E.1 Counterexample We show that the constitutional governance rule with σ = 1/2 is not monotone in general metric spaces. The counterexample uses seven members and a metric space with points s, w, p, v1 , . . . , v5 . Setup. Let d(w, s) = 10, d(p, s) = 10, d(w, p) = 5, and d(vj , s) = 10 for j = 1, . . . , 5. The remaining distances are: Member d(vj , w) u(vj , w) u(vj , p) 1 2 3 4 5 6 (= p) 7 (= w)

13 12 11 9.99 9.98 5 0

−3 −2 −1 0.01 0.02 5 10

−6 −4 −2 −0.01 0.1 10 5

All distances satisfy the triangle inequality; inter-member distances are realised via shortest paths through {s, w, p}. Before the move. Sorted utilities for w: (−3, −2, −1, 0.01, 0.02, 5, 10); median = 0.01. Sorted utilities for p: (−6, −4, −2, −0.01, 0.1, 5, 10); median = −0.01. Every other proposal vj (j = 1, . . . , 5) has only one supporter and median utility well below 0. Thus w is the unique winner, with ϕσ (u(w)) = 0.01 > −0.01 = ϕσ (u(p)). Member 4 moves to w. Member 4 changes its ideal element from v4 to w. The new utilities for member 4 are: u(w, w) = 10 and u(w, p) = 5. Sorted utilities for w: (−3, −2, −1, 0.02, 5, 10, 10); median = 0.02. Member 4’s value jumped from 0.01 to 10, but member 5’s value 0.02 now holds the median position. Sorted utilities for p: (−6, −4, −2, 0.1, 5, 5, 10); median = 0.1. Member 4’s value jumped from −0.01 to 5, and member 5’s value 0.1 now occupies the median position. Now ϕσ (u(p)) = 0.1 > 0.02 = ϕσ (u(w)), so w loses to p. Monotonicity is violated. Mechanism. The triangle inequality guarantees that when a member moves to the winner w, its utility for w increases at least as much as its utility for any competitor p. However, in general metric spaces the median can fail to respond: if member 4’s utility for w was already at a “plateau” of small positive values, its increase does not shift the median of w correspondingly. Meanwhile, member 4’s utility for p was at the median position, and its departure reveals the next value in the sorted order, which exceeds the new median of w. In one-dimensional settings, this cannot occur: the positional median moves monotonically towards w when a member moves to w, preventing any competitor from overtaking.

Mean Aggregation as an Alternative Instantiation

The framework is parametrised by an aggregation rule ϕ (Definition 1); Section 4 develops the generalised median. The mean is an alternative utilitarian instanti-

Constitutional Governance in Metric Spaces

ation. It satisfies all framework-level hypotheses of Section 3—O(n)-computable via direct summation, symmetric, and zero at indifference—and inherits existence and complexity (Proposition 1), anonymity, reality-awareness (Proposition 3), and Condorcet-cycle immunity (Theorem 1). Pn Definition 6 (Mean). The mean aggregation rule is ϕmean (u) := n1 i=1 ui . The mean is the natural utilitarian aggregator: it ranks proposals by total member gain over the status quo, equivalently by aggregate L1 -distance reduction. In the terminology of Bulteau et al. [6], the mean instance corresponds to L1 aggregation under the supermajority gate. Unlike the median, the mean does not coincide with the supermajority gate: a proposal can be supported (i.e., strictly preferred to the status quo by at least ⌈σn⌉ members) yet have negative mean utility, or have positive mean yet fail the gate. The framework’s gate disciplines the mean: a proposal strongly preferred by a minority but opposed by a supermajority is not adopted under the mean instance, because the gate excludes it. This forecloses the classical tyranny-ofthe-intense-minority objection to utilitarianism. Majoritarity. The mean instance is σ-majoritarian under the framework’s gate: if ⌈σn⌉ members share w ̸= s, then w is supported, and—unless a distinct supported proposal has higher mean—w is adopted. Without the gate (i.e., under pure utilitarian mean aggregation as in [6]), the mean instance would not be σmajoritarian: a minority strongly preferring s could overwhelm a supermajority’s aggregate gain. The gate forecloses this case. Per-round non-strategy-proofness. The mean instance is non-SP per round: a member can shift the aggregate by misreporting an exaggerated position, the standard utilitarian-voting weakness. Protocol-level strategy-proofness: open. The mean instance does not admit a proof analogous to Theorem 2. Every voter contributes linearly to every proposal’s utility, so no single voter can be made decisive by a bifurcated profile, and the construction underlying Theorem 2 fails to separate. We state the analogous claim as an open problem. Conjecture 1 (Protocol-level strategy-proofness, mean). Under the proposal protocol with ϕ = ϕmean , no misreport weakly dominates sincere voting. We verified the conjecture in small cases (n = 3 in 1D Euclidean) but have not found a general proof or counterexample. A unified abstract treatment— identifying the minimal sensitivity property on ϕ under which a deciding-vote argument separates sincere from misreport—would accommodate further instances (Lp , min, trimmed means) uniformly. Median or mean. A community choosing between the generalised median and the mean is weighing classical utilitarianism against median-voter representation. The mean maximises aggregate utility and is the natural choice when the community’s objective is the sum of members’ gains. The generalised median protects against tyranny-of-the-minority and is the natural choice when each

Shapiro and Talmon

decision must command supermajority support of broadly aligned values. Either is a constitutional choice, amendable via the framework’s self-amendment mechanism (Section 2).

Per-Round Anatomy of Manipulation under ϕσ

The following three lemmas characterise the structural anatomy of single-round manipulation under ϕσ : every successful misreport falls into one of two cases, each of which has its own diagnostic. Lemma 1 (Self-defeating flip from unsupported). Fix σ ∈ [1/2, 1) and a proposal W that is not supported under sincere voting. Suppose member i unilaterally misreports, and under the misreport W becomes supported. Then u(vi∗ , W ) ≤ 0: member i weakly prefers the status quo to W . Proof. Let k = ⌈σn⌉. W is supported iff at least k entries of u(W ) are strictly positive. Under sincere voting, at most k − 1 entries of u(W ) are positive. Misreporting changes only member i’s entry, so the count of positive entries can increase by at most one—from ≤ 0 to > 0. A flip from unsupported to supported therefore requires u(vi∗ , W ) ≤ 0. ⊔ ⊓ Lemma 2 (Public proposal replicates supported flip). Fix any proposal c ̸= s with u(vi∗ , c) > 0 and any votes of the other n − 1 members. Then c is supported under sincere voting by member i with public proposal ci = c if and only if c is supported under the misreport ṽi = c. Proof. Support depends only on the multiset {u(vj , c) : j ∈ [n]}. The entries for j ̸= i are identical in both scenarios. The entry from member i is u(vi∗ , c) > 0 in the public-proposal scenario by hypothesis, and u(c, c) = d(c, s) > 0 in the misreport scenario since c ̸= s. Both entries are strictly positive, so the count of positive entries—and hence the support status of c—is the same. ⊔ ⊓ Lemma 3 (Self-defeating winner swap). Suppose under sincere voting, W0 and W̃ are both supported with ϕσ (u(W0 )) > ϕσ (u(W̃ )) > 0, so W0 wins. Suppose member i unilaterally misreports, and under the misreport both ϕσ (u(W0 )) strictly decreases and ϕσ (u(W̃ )) strictly increases. Then u(vi∗ , W0 ) > u(vi∗ , W̃ ): member i strictly prefers W0 to W̃ . Proof. When a single entry in a list of n reals is replaced, the ⌈σn⌉-th largest can strictly decrease only if the replaced entry was at least the original ⌈σn⌉-th largest, and can strictly increase only if it was at most. So a strict decrease of ϕσ (u(W0 )) implies u(vi∗ , W0 ) ≥ ϕσ (u(W0 )); a strict increase of ϕσ (u(W̃ )) implies u(vi∗ , W̃ ) ≤ ϕσ (u(W̃ )). Combining with ϕσ (u(W0 )) > ϕσ (u(W̃ )): u(vi∗ , W0 ) ≥ ϕσ (u(W0 )) > ϕσ (u(W̃ )) ≥ u(vi∗ , W̃ ).⊓ ⊔ Together, Lemmas 1–3 establish a per-round dichotomy: whenever a member could profitably misreport, either (a) the manipulation is self-defeating— the member would weakly prefer the unmanipulated outcome (Lemmas 1, 3),

Constitutional Governance in Metric Spaces

or (b) the same outcome is achievable by sincere voting with a public-proposal submission (Lemma 2). The per-round dichotomy motivates the design of the proposal protocol of Section 4: sealing votes denies the misreporter the information needed to construct case-(a) manipulations, and the open public-proposal channel makes case (b) sincere by construction. Theorem 2 establishes the resulting protocol-level guarantee directly. Remark 4. A concrete example illustrates that the public-proposal channel cannot always replicate a profitable misreport. Take R2 with Euclidean distance, n = 3, s = (0, 0), σ = 1/2, and ideals v1∗ = (2.5, 1), v2∗ = (1, 2), v3∗ = (−1, −1). Under sincere voting, both v1∗ and v2∗ are supported; v2∗ wins with median utility ≈ 0.890 versus v1∗ ’s ≈ 0.433, so member 1’s true utility is ≈ 0.890. Under misreport ṽ1 = (5, −5), v2∗ becomes unsupported and v1∗ wins, giving member 1 true utility ≈ 2.693. By contrast, no public proposal c submitted with sincere voting can lift v1∗ above v2∗ : such a c would need member 2’s utility u(v2∗ , c) > 0.890, which constrains c to a ball around v2∗ excluding the part of R2 closest to v1∗ . The supremum of member 1’s public-proposal-channel utility is ≈ 2.236 < 2.693. Misreport thus has leverage that public proposals do not, by altering the manipulator’s own entry in every proposal’s median computation. The protocol of Section 4, by sealing votes at the start of the epoch, eliminates this leverage.

Public-Proposal and Coalition Behaviour

The strategic role of the public-proposal channel is distinct from the voting channel. A member’s vote is their immutable, sealed expression of preference; their public proposal carries supermajority public support under the revealed votes. The following propositions characterise rational behaviour on the publicproposal side. Proposition 9 (Public proposal is weakly beneficial). Submitting a public proposal c is weakly beneficial for the submitter: either the round winner is unchanged, or it becomes c. A rational member submits c only when their true utility u(vi∗ , c) exceeds their true utility for the previous round’s winner. Proof. Let W be the round winner if member i submits no public proposal, and W ′ the winner if they submit ci = c. Since votes are fixed, admitting c leaves ϕ-scores of all other proposals unchanged, so W ′ ∈ {W, c}. If W ′ = W , the submitter’s utility is unchanged; if W ′ = c, it becomes u(vi∗ , c). A rational member therefore submits only when u(vi∗ , c) exceeds their utility for W . ⊓ ⊔ Proposition 10 (Sincere coalition public proposal is weakly dominant). For any coalition C ⊆ [n] and any joint choice of public-proposal submissions {cj }j∈C , each member’s weakly dominant strategy is to submit a public proposal they personally prefer to the current winner. Submitting a public proposal they do not prefer is weakly dominated. Proof. Each submission is evaluated independently: ϕ depends only on the fixed sincere votes, not on whose slot submitted the public proposal. The joint outcome

Shapiro and Talmon

is the proposal with maximum uϕ among all submissions. If member j submits cj with u(vj∗ , cj ) not exceeding their utility for the current winner, the submission either has no effect (someone else’s public proposal wins, or no public proposal wins) or causes cj to win, making j weakly worse off. ⊔ ⊓ Proposition 11 (Coalition flip requires self-defeating member). Let coalition C ⊆ [n] jointly misreport, and suppose the misreport flips a proposal W from unsupported under sincere voting to supported. Then at least one coalition ∗ member m ∈ C has sincere utility u(vm , W ) ≤ 0: the coalition must include a member who weakly prefers the status quo to W . Proof. Let k = ⌈σn⌉ and let psincere , pmisreport denote the number of positive entries of u(W ) under each scenario. Non-coalition entries are unchanged, so pmisreport − psincere = |MC | − |SC |, where SC = {j ∈ C : u(vj∗ , W ) > 0} and MC = {j ∈ C : u(ṽj , W ) > 0}. A flip from psincere ≤ k − 1 to pmisreport ≥ k ∗ , W ) ≤ 0 and requires |MC | − |SC | ≥ 1, hence some m ∈ MC \ SC has u(vm u(ṽm , W ) > 0. ⊔ ⊓ A coalition flip of an unsupported proposal therefore must include a member acting against their sincere preference. Without side payments or external enforcement, this member is individually irrational, and the coalition is not selfenforcing.

1D Characterisation of the Generalised Median

Proposition 12 (1D characterisation). Let k = ⌈σn⌉, and order the votes as v(1) ≤ · · · ≤ v(n) . The generalised median utility of a proposal p ∈ X is   u(v(n−k+1) , p) if p > s, ϕσ (u(p)) = u(v(k) , p) if p < s,   0 if p = s. Among supported proposals in V , the winner is the one closest to the corresponding positional voter. For σ = 1/2 with odd n, the two positional voters coincide at the median vm , and the winner is the proposal in V closest to vm (which equals vm itself when vm ∈ V and vm ̸= s). Proof. For fixed p and s, the utility u(vq , p) = |vq − s| − |vq − p| is non-decreasing in vq when p > s and non-increasing when p < s. Hence the ordering of utilities by member index tracks (respectively reverses) the ordering of ideal elements by magnitude, and the k-th largest utility equals u(v(n−k+1) , p) when p > s and u(v(k) , p) when p < s. In either direction, the resulting expression is of the form |vm − s| − |vm − p| for the appropriate positional voter, maximised over V at the proposal closest to vm ; if vm ∈ V and vm ̸= s, this proposal is vm itself, with ϕσ = |vm − s| > 0. ⊔ ⊓ Example 3 (1D dominance in the running cooperative). A constitutional amendment in the running example sets the commission rate at σ = 1/2. The current rate is s = 20%. Members vote v1 = 10%, v2 = 15%, v3 = 18%, v4 = 22%, v5 =

Constitutional Governance in Metric Spaces

25%; the positional median is v3 = 18%. By Proposition 5, no member can profit from misreporting. For instance, member 1 (v1∗ = 10%) shifting their report leftward to 5% leaves the median at 18%; shifting rightward to 19% shifts the median to v4 = 22%, farther from the true ideal. Sincere voting weakly dominates.

Heuristic P: Definition and Complexity

Definition 7 (Heuristic P). Given proposal set P r at the start of a round, status quo s, and aggregation rule ϕ: 1. For each pair (p, q) ∈ P r × P r with p ̸= q, compute a bounded set C(p, q) ⊆ X of candidate combinations of p and q (in metric spaces with unique geodesic midpoints, C(p, q) is the singleton midpoint; otherwise C(p, q) enumerates or samples a bounded number of tie-breaking candidates). S 2. Let c∗ ∈ arg max{ϕ(u(c)) : c ∈ p,q C(p, q)}. 3. If ϕ(u(c∗ )) > maxp∈P r ϕ(u(p)), return c∗ as a public proposal; otherwise return ⊥. Proposition 13 (Complexity of Heuristic P). Heuristic P runs in O(|P r |2 (Tc + n)) time, where Tc bounds the cost of computing the candidate combinations for one pair: O(m) for the simplex under Euclidean distance, O(m2 ) for permutations under swap distance, O(|A|) for subsets under symmetric difference (bounded candidate set), and O(ℓ2 ) for strings under weighted Levenshtein. Heuristic P is polynomial in every setting of Section 5.

Compromise Gap: Minimal Examples

Two minimal examples illustrate that in dimensions two and above, the gap can be positive. Example 4 (Star graph). Let X be a star with three leaves ℓ1 , ℓ2 , ℓ3 each at distance 1 from a hub h, with the shortest-path metric. Take V = {ℓ1 , ℓ2 , ℓ3 }, s = ℓ1 , σ = 1/2, so k = ⌈3/2⌉ = 2. The utility vector at h is u(h) = (−1, 1, 1) with ϕσ (u(h)) = 1. For each peak p ∈ V , direct computation gives ϕσ (u(p)) = 0 (with u(ℓ1 ) = (0, 0, 0), u(ℓ2 ) = (−2, 2, 0), u(ℓ3 ) = (−2, 0, 2)). Hence OPT = 1 at h∈ / V , PEAK = 0, and CG = 1. Example 5 (Two-dimensional Euclidean). Proposition 6 exhibits n = 3 peaks in R2 for which no peak is supported and the status quo is retained (PEAK = 0 in our terminology, after enforcing positivity), yet the non-peak point (0.5, 0.5) has positive median utility and is supported. Hence CG > 0. Example 6 (Compromise gap in the running cooperative). The budget profile of Example 1 has CG > 0. The five peaks score below the geometric-median public proposal ĉ = (0.34, 0.40, 0.27): direct computation gives ϕ1/2 (u(ĉ)) ≈ 0.171, while no peak exceeds ≈ 0.140 on the same profile. The public-proposal channel closed the gap; without it, the rule would have adopted the highest-scoring peak with score ≈ 0.140, leaving CG ≈ 0.031 unclaimed. This is the gap that the open public-proposal channel exists to close. In both examples, an interior point of X strictly dominates every peak.

Shapiro and Talmon

Five Remaining Application Settings

This appendix gives full propositions, proofs, and worked examples for the five application settings summarised in Section 5: plurality elections, social welfare functions, committee elections, and legislation. (1D rate-setting and simplex budgeting are worked in the main text; constitutional amendments are detailed in Appendix M.) L.1 Plurality Elections: Electing Officers A community must periodically elect officers—a chairperson, treasurer, or ombudsperson. Each member nominates a candidate; at the end of a term, the position is vacant. Model. Let A be the set of candidates and ⊥ denote the vacant position. The metric space is X = A ∪ {⊥} with the discrete metric: d(x, y) = 1 for x ̸= y, and d(x, x) = 0. Each member’s ideal element is one of the candidates. The status quo s = ⊥ is the vacant position. Utility. Since s = ⊥ and no member’s ideal element is ⊥, every member has d(vq , s) = 1. For a member with ideal element vq and a candidate p ∈ A: ( 1 if vq = p, u(q, p) = d(vq , s) − d(vq , p) = 0 otherwise. Characterisation. For a candidate p ∈ A, let np = |{q : vq = p}| be the number of supporters of p. Proposition 14. The constitutional governance rule selects the candidate with the most supporters, provided that candidate has σ-supermajority support, i.e., at least ⌈σn⌉ supporters. Otherwise no candidate is adopted and the position remains vacant. Proof. For a candidate p, the n utilities consist of np values of 1 and n − np values of 0. The ⌈σn⌉-th largest utility equals 1 iff np ≥ ⌈σn⌉, and 0 otherwise. Among all candidates, the one with the most supporters maximises the median; it is adopted precisely when it meets the gate. ⊓ ⊔ Example 7. A cooperative of five members elects a chairperson with σ = 1/2. The candidates are Alice, Bob, and Carol. If two members prefer Bob, two prefer Alice, and one prefers Carol, no candidate has ⌈5/2⌉ = 3 supporters; the position remains vacant. If three prefer Bob and the rest are split, Bob is elected. If no candidate achieves the threshold, the public-proposal channel admits compromise candidates—e.g., a coalition-suggested candidate—which are scored under the same rule. L.2 Social Welfare Functions: Ranking Priorities A community must rank its strategic priorities—growth, member welfare, service quality, sustainability—to guide resource allocation. Each member proposes a ranking; the current ranking is the status quo.

Constitutional Governance in Metric Spaces

Model. Let A be the set of priorities, m = |A|. The metric space is X = SA (permutations over A) with the swap distance (minimum number of adjacent transpositions to convert one permutation into another). The status quo s ∈ SA is the current ranking. Utility. For member with ideal element vq and a proposed ranking p: u(q, p) = d(vq , s) − d(vq , p). Characterisation. Proposition 15. The constitutional governance rule selects the supported ranking in V ∪ C with maximal score in O(n2 m log m) time. Proof. For each proposal p ∈ P r , the swap distance d(vq , p) equals the number of inversions between the two permutations and is computable in O(m log m) time. Computing utilities for all n members takes O(nm log m), evaluating ϕσ takes O(n), so per-proposal cost is O(nm log m). Over |P r | ≤ 2n proposals, the total is O(n2 m log m). ⊓ ⊔ Comparison with Bulteau et al.. Bulteau et al.’s Lp aggregation here corresponds to the Kemeny ranking, which is NP-hard for all p ≥ 1. The constitutional governance rule trades optimality over the full permutation space for tractability over the proposal set; the Kemeny ranking, computed as a public proposal, is admitted by the framework on the same footing as any other public proposal. Example 8. Three members rank priorities A = {g, w, q} (growth, welfare, quality) at σ = 1/2. The current ranking is s : g ≻ w ≻ q. The proposed rankings are v1 = v2 = s and v3 = w ≻ g ≻ q (one swap from s). The proposal v3 has utility vector (−1, −1, 1), with median −1. The current ranking has all-zero utilities. No proposal is supported with positive median; the status quo is retained, reflecting that two members already prefer it. L.3 Committee Elections: Selecting a Board A community must select a governance board, a dispute panel, or an audit committee from among its members. Model. Let A be the set of eligible members. The metric space is X ⊆ 2A (subsets of A) with d(x, y) = |x△y|, the symmetric difference. As specific cases: X = 2A for unrestricted board size, or X = A for a board of exactly k members. k The status quo s = ∅ is the empty set (no board); the constitution may specify continuity mechanisms between terms. Utility. u(q, p) = |vq △s| − |vq △p|. Characterisation. Proposition 16. The constitutional governance rule selects the supported board with maximal score in O(n2 |A|) time.

Shapiro and Talmon

Proof. For each proposal p ∈ P r , the symmetric difference |vq △p| is computable in O(|A|) time. Per-proposal cost is therefore O(n|A|), and over |P r | ≤ 2n proposals the total is O(n2 |A|). ⊓ ⊔ Comparison with Bulteau et al.. Bulteau et al.’s Condorcet aggregation is coNP-hard, and Lp for p > 1 is NP-hard, in this setting. The framework’s restriction to P r is again the source of tractability. Example 9. Five members (A = {a, b, c, d, e}) form a three-member governance board at σ = 1/2, with s = ∅. Proposed boards: v1 = v2 = {a, b, c}, v3 = {a, c, d}, v4 = {b, c, d}, v5 = {a, b, d}. The framework evaluates each proposal by its generalised median utility relative to the status quo of no board, and selects the supported board with the highest score. L.4 Legislation: Drafting Bylaws A community must draft and amend its bylaws—the rules governing membership, decision-making, dispute resolution, and surplus distribution. Each member may propose a text; the current bylaws (or the empty text, if none exist) are the status quo. The framework’s metric-agnosticism (Section 5) is most consequential here. Model. Let Σ be an alphabet, where characters represent clauses or articles. The metric space is X = Σ ∗ (strings over Σ). Following Bulteau et al. [6], we adopt a weighted Levenshtein distance: insert and delete operations cost 1, swap operations cost 1/ℓ2 where ℓ is the length of the longest proposed text. This weighting makes content more important than order. The status quo s is the current bylaws (or the empty text). As observed in Bulteau et al., the problem decomposes into two phases: Phase 1 selects the set of clauses (formally equivalent to committee elections, Appendix L.3); Phase 2 orders the selected clauses (formally equivalent to social welfare functions, Appendix L.2). Utility. u(q, p) = d(vq , s) − d(vq , p). Characterisation. Proposition 17. The constitutional governance rule selects the supported text with maximal score in O(n2 ℓ2 ) time. Proof. For each proposal p ∈ P r , the weighted Levenshtein distance d(vq , p) between two strings of length at most ℓ is computable in O(ℓ2 ) time by dynamic programming. Per-proposal cost is therefore O(nℓ2 ), and over |P r | ≤ 2n proposals the total is O(n2 ℓ2 ). ⊔ ⊓ Comparison with Bulteau et al.. Both phases of Lp aggregation are NP-hard, and the combined problem inherits the hardness. The framework’s tractability rests on restricting to the proposal set.

Constitutional Governance in Metric Spaces

On the metric. As noted in Section 5, the weighted Levenshtein distance is a placeholder. The framework’s metric-agnosticism means semantic distances— defined via large language models, embedding-based similarity, or domain-specific schemas—plug in directly. AI mediation [5] provides one path: a mediator computes a semantic public proposal between proposed bylaws and submits it under the open public-proposal channel. The rule scores the result under the constitutionally-specified metric, regardless of how the public proposal was generated.

Constitutional Amendment: Full Details

Section 2 sketched constitutional amendment as the same constitutional governance rule applied to the constitutional components themselves at σ > 1/2. This appendix gives the per-component details. We organise around the constitutional components: the membership set, scalar parameters, the supermajority threshold, the aggregation rule, and textual provisions. M.1

Identifying Constitutional Components

The status quo is a tuple s = (s1 , . . . , sN ). A component sj is constitutional if its value governs how some other component si (i ̸= j) is amended—that is, changing sj alone, holding all other components fixed, alters which amendments to si are admissible. A component that is not constitutional is ordinary. The constitutional components of the framework developed here are: the membership set, the per-component supermajority threshold σi , the per-component aggregation rule ϕi , the per-component metric space (Xi , di ), and the per-component novelty distance εi . Each appears as a dependency of the amendment of the component it governs. The downstream effect of constitutional amendment is broader than that of ordinary amendment, and the conventional choice σi > 1/2 for constitutional components reflects this asymmetry. A community is free to choose any σi ∈ [1/2, 1) for any component; the convention is structurally motivated, not imposed by the framework. M.2

Amending the Membership Set

The set of members P is a constitutional component. Unlike committee elections (Appendix L.3)—where each member proposes a complete committee and the rule selects among proposed committees—amending the membership decomposes into independent binary referenda [13]: for each candidate p, each member votes “in” or “out”, and the candidate is added to or retained in P iff a σ-supermajority votes “in”. Additionally, each new member must consent to joining. The per-candidate vote is the simplest instance of the constitutional governance rule: the metric space is {in, out} with d(in, out) = 1, the status quo is the candidate’s current membership status, and the rule reduces to the σsupermajority threshold. The decomposition into per-candidate referenda is appropriate here: the question is whether each individual has sufficient support, not which package of members is collectively preferred.

Shapiro and Talmon

M.3

Amending a Scalar Parameter

Scalar constitutional parameters—a timeout ∆, a quorum fraction, the percomponent novelty distance εi —are amended as instances of 1D elections (Section 5), with the constitutional threshold σ > 1/2 and the metric space a subset of R with absolute distance. Each member proposes a value; the rule selects the proposal closest to the ⌈σn⌉-th positional vote, by Proposition 12. M.4

Amending the Threshold: The h-Rule

The most distinctive constitutional amendment is changing σ itself. This is inherently self-referential: the rule used to decide whether σ should change is determined by σ. Abramowitz et al. [1] show that a natural set of axioms— decisiveness, monotonicity, anonymity, concordance, minimality, and posterior consistency—uniquely determines the amendment process, the h-rule. The h-rule operates as follows. Each member i states a preferred threshold σi ∈ [1/2, 1). Preferences over thresholds are single-peaked. 1. Raising σ: σ is increased to the maximal σ ′ > σ for which a σ ′ -supermajority of members voted for a value ≥ σ ′ . Raising the threshold requires the very supermajority that the new threshold demands. 2. Lowering σ: σ is decreased to the minimal σ ′ < σ for which a σ-supermajority voted for a value ≤ σ ′ . Lowering requires the current supermajority’s agreement. 3. Otherwise σ remains unchanged. The h-rule prevents a minority from imposing stricter requirements or weakening the constitution; [1] establishes that it is the unique rule satisfying their axioms. Running example: raising the budget threshold. The cooperative of Example 1 amends the budget threshold from σ = 1/2 to a higher value after experience with several budget rounds. Members vote on preferred thresholds: v1 = 1/2, v2 = 1/2, v3 = 2/3, v4 = 2/3, v5 = 3/4. The current threshold is σ = 1/2, and the constitutional amendment threshold is itself 2/3 via the hrule. Raising to σ ′ = 2/3 requires a 2/3-supermajority voting for a value ≥ 2/3: members 3, 4, 5 do so, but ⌈(2/3) · 5⌉ = 4 exceeds 3, so the rule does not raise to 2/3. Raising to σ ′ = 3/5 requires a 3/5-supermajority voting for ≥ 3/5: three of five do, and ⌈(3/5) · 5⌉ = 3, so σ is raised to 3/5. The example illustrates the h-rule’s defining property: a stricter threshold cannot be imposed without the level of support it itself demands. This setting is an instance of 1D elections on [1/2, 1), but with the crucial difference that the threshold for amendment is itself the value being amended; the h-rule resolves the self-reference principally. M.5

Amending the Aggregation Rule

Each amendable component si carries an aggregation rule ϕi , itself a constitutional component. A community may constitutionally specify ϕi as the generalised median (Definition 3), the mean (Definition 6), another aggregator from

Constitutional Governance in Metric Spaces

Bulteau et al.’s Lp family, or any anonymous, monotone, O(n)-computable aggregator with ϕ(0) = 0. Amending ϕi proceeds under the constitutional governance rule at σ > 1/2. Each member proposes a preferred ϕi ; the rule selects the round winner. Because amending ϕi is itself a constitutional decision, a community can evolve any component’s aggregation rule from generalised median to mean (or to any admissible aggregator) as collective judgement evolves. M.6 Amending Textual Provisions The community’s bylaws are a constitutional component. Amending them is an instance of legislation (Appendix L.4) at σ > 1/2. Each member proposes a revised text; the constitutional governance rule selects the proposal with maximal score, adopting it only if it is supported. M.7 Ratification Once the constitutional governance rule produces an amendment, the constitutional consensus protocol [13] ratifies it. Constitutional consensus operates in epochs, each governed by the prevailing constitution. A constitutionally-valid amendment is submitted as a transaction, ratified by the consensus protocol, and takes effect in the next epoch. The protocol integrates the decision processes described above with a Byzantine-fault-tolerant consensus mechanism, ensuring amendments are both democratically decided and reliably enacted. We treat constitutional consensus as a black box for the purposes of this paper.

Simulation: Full Sweep

Section 6 reported the headline statistics, table, and findings. This appendix gives the complete sweep across all twenty-seven configurations: four settings (2D Euclidean, simplex, hypercube, permutations), each at three or four electorate sizes. Reading the sweep. The pattern from the headline table generalises across all configurations. In continuous spaces (2D Euclidean, simplex), CG > 0 is near-universal at small n and shrinks slowly with n; Heuristic P’s gap-closing ratio rises from ∼ 40–50% at n = 5 to ∼ 80–96% at n = 21–51. In discrete spaces (hypercube, permutations), CG > 0 is less common—peaks themselves often coincide with the unconstrained optimum—and Heuristic P closes nearly the entire gap when there is one, with the gap-closing ratio frequently at or above 90% across all configurations. The hypercube, a median space, exhibits the cleanest behaviour: gap-closing ≥ 90% in every row. Scope. The simulation does not claim a worst-case approximation guarantee for Heuristic P; configurations are drawn from natural uniform-on-domain priors. Non-uniform priors, larger m or |A|, alternative aggregators (e.g., the mean instance), and empirical evaluation on real cooperative-governance data are left as future work.

Shapiro and Talmon

Table 3. Compromise gap and Heuristic P across four settings and three electorate sizes. “CG > 0” = fraction of profiles (with OPT > 0) for which CG > 0. “Gap-closing” = mean fraction of CG closed by Heuristic P on profiles with CG > 0. “Hit rate” = fraction of profiles on which Heuristic P returns a non-⊥ output. Setting

n CG > 0 Gap-closing Hit rate

2D Euclidean (uniform) 5 2D Euclidean (uniform) 11 2D Euclidean (uniform) 21 2D Euclidean (uniform) 51

98.6% 99.6% 100% 96.0%

41.1% 61.1% 79.4% 96.3%

66.8% 87.8% 96.3% 98.0%

Simplex (m = 3) Simplex (m = 3) Simplex (m = 3) Simplex (m = 4) Simplex (m = 4) Simplex (m = 4)

5 11 21 5 11 21

93.0% 98.0% 98.0% 97.0% 99.0% 99.0%

40.1% 64.4% 81.6% 52.4% 66.0% 81.1%

60.0% 85.7% 95.0% 77.5% 94.0% 96.0%

Hypercube (|A| = 6) Hypercube (|A| = 6) Hypercube (|A| = 6) Hypercube (|A| = 8) Hypercube (|A| = 8) Hypercube (|A| = 8) Hypercube (|A| = 10) Hypercube (|A| = 10) Hypercube (|A| = 10)

5 11 21 5 11 21 5 11 21

39.4% 26.2% 11.7% 68.5% 51.4% 35.5% 85.0% 73.0% 51.0%

99.5% 99.2% 100% 96.5% 95.9% 100% 90.2% 91.4% 96.1%

39.2% 26.0% 11.7% 66.3% 49.4% 35.5% 78.7% 67.5% 49.0%

Permutations (m = 4) Permutations (m = 4) Permutations (m = 4) Permutations (m = 5) Permutations (m = 5) Permutations (m = 5) Permutations (m = 6) Permutations (m = 6) Permutations (m = 6)

5 11 21 5 11 21 5 11 21

27.4% 13.0% 4.8% 63.0% 47.5% 31.7% 85.0% 83.3% 72.0%

98.8% 97.3% 100% 81.8% 89.1% 98.9% 67.1% 77.4% 84.3%

27.1% 12.7% 4.8% 52.9% 42.5% 31.3% 65.3% 69.7% 62.7%

Record · ID 180628 · SHA-256 5b32ea77685af6b4
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.