arxiv: 2605.13362 · v2 · submitted 2026-05-13 · 💻 cs.MA · cs.AI· cs.DC· cs.GT· econ.TH

Recognition: no theorem link

Constitutional Governance in Metric Spaces

Ehud Shapiro , Nimrod Talmon

Authors on Pith no claims yet

Pith reviewed 2026-05-15 05:54 UTC · model grok-4.3

classification 💻 cs.MA cs.AIcs.DCcs.GTecon.TH

keywords constitutional governancemetric spacesgeneralized mediansupermajority amendmentpolynomial-time protocolsocial choicedigital sovereigntyself-amendment

0 comments

The pith

Constitutional governance in metric spaces integrates voting, proposal submission, and supermajority amendment into a single polynomial-time protocol that communities can run on personal devices.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes a framework in which a constitution specifies, for each amendable component, a metric space, an aggregation rule such as the generalized median, and a supermajority threshold. Members report ideal points, public proposals backed by supermajority support are collected from deliberation or aggregation, and the rule selects the proposal with the highest positive score or retains the status quo. This produces a coherent, efficient process that covers aggregation through constitutional self-amendment without requiring external authorities. A sympathetic reader would care because the protocol unifies previously isolated stages of social choice into one executable system that supports digital sovereignty for communities.

Core claim

The constitution assigns per amendable component a metric space, aggregation rule, and supermajority threshold; amendments are formed by members voting with ideal elements, then submitting public proposals that carry supermajority support under the revealed votes; the constitutional rule adopts any supported proposal with positive maximal score or retains the status quo. The generalized median rule at majority threshold ensures no misreport weakly dominates sincere voting, and the framework is instantiated across electing officers, setting rates, allocating budgets, ranking priorities, selecting boards, drafting bylaws, and amending the constitution itself.

What carries the argument

The constitutional rule that adopts a supported public proposal with positive maximal score or retains the status quo, built on the generalized median aggregator in metric spaces.

If this is right

The protocol runs in polynomial time on members' personal devices, enabling digital sovereignty without central servers.
Seven canonical governance tasks—electing officers, setting rates, allocating budgets, ranking priorities, selecting boards, drafting bylaws, and amending the constitution—become instances of the same mechanism.
Supermajority thresholds and the generalized median together limit strategic manipulation while allowing compromise proposals.
Constitutional consensus emerges directly from repeated application of the same rule to the constitution itself.
The framework unifies metric-space aggregation, reality-aware social choice, and deliberative coalition formation under one executable protocol.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If sourcing of supermajority proposals can be automated reliably, the same protocol could support ongoing rule adaptation in large-scale online organizations without periodic offline meetings.
The compromise gap between best peak and unconstrained optimum studied in the paper implies that communities may need auxiliary mechanisms to surface high-support proposals that sit near the median.
Because the rule retains the status quo when no positive-score proposal exists, repeated cycles could produce gradual convergence rather than oscillation between extremes.

Load-bearing premise

Public proposals carrying supermajority support can be sourced reliably from deliberation, vote aggregation, or AI mediation, and the generalized median rule at majority threshold prevents any misreport from weakly dominating sincere voting.

What would settle it

An explicit preference profile and misreport under the generalized median at majority threshold where the misreporting voter obtains a strictly better outcome than sincere voting, or a concrete community setting in which no public proposal ever gathers the required supermajority support.

read the original abstract

Computational social choice and algorithmic decision theory offer rich aggregation theory but no comprehensive process for egalitarian self-governance: aggregation, deliberation, amendment, and consensus are each considered in isolation, with key metric-space aggregators being NP-hard. Here, we propose constitutional governance in metric spaces, integrating these stages into a coherent polynomial-time protocol for constitutional governance. The constitution assigns, per amendable component including itself, a metric space, aggregation rule, and supermajority threshold. Amendments proceed by members voting with their ideal elements, followed by members submitting public proposals carrying supermajority public support under the revealed votes. Public proposals can be sourced from deliberation among members, vote aggregation, or AI mediation. The constitutional rule adopts a supported proposal with positive maximal score, if there is one, else retains the status quo. With Constitutional Consensus, a community can run the constitutional governance protocol on members' personal computing devices (e.g., smartphones), achieving digital sovereignty. We focus on the utility of the generalised median, prove that at majority threshold no misreport weakly dominates sincere voting, and study the compromise gap between best peak and unconstrained optimum. We instantiate the framework to seven canonical settings -- electing officers, setting rates, allocating budgets, ranking priorities, selecting boards, drafting bylaws, and amending the constitution. 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 governance of digital communities and organisations.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper sketches a unified constitutional amendment protocol over metric spaces with a claimed poly-time implementation, but the efficiency claim rests on unspecified proposal sourcing that may not stay efficient.

read the letter

The main thing to know is that the authors try to combine metric-space aggregation, amendment, and consensus into one protocol that a community could run on personal devices. The integration itself is the fresh part, along with the per-component choice of metric, rule, and supermajority threshold. They give seven concrete instantiations covering officer elections, budget allocation, and constitutional self-amendment, which helps make the idea concrete rather than purely abstract. They also prove that the generalized median rule has no weak dominance for misreporting at the majority threshold and they measure the compromise gap between the best peak and the unconstrained optimum. Those pieces are solid and worth having on record. The soft spot is the polynomial-time guarantee. The abstract states that standard metric aggregators are NP-hard, yet the protocol needs members to submit proposals that already carry supermajority support. It lists deliberation, vote aggregation, or AI mediation as sources but gives no algorithm or argument showing that finding or verifying such proposals stays efficient in arbitrary metric spaces. If that step requires solving a hard subproblem, the overall claim fails. The incentive result is stated only for majority threshold, while components can use other supermajority levels, so it is unclear whether the property carries over. The adoption rule based on positive maximal score is also not fully spelled out. This is for readers working in computational social choice who care about self-governance protocols for digital groups. Someone already thinking about algorithmic decision theory or online community rules would get value from the unification and the specific proof. It deserves a serious referee to check whether the full proofs close the efficiency and incentive gaps.

Referee Report

3 major / 2 minor

Summary. The manuscript proposes a framework for constitutional governance in metric spaces that integrates aggregation, deliberation, amendment, and consensus into a coherent polynomial-time protocol. The constitution assigns to each amendable component (including itself) a metric space, an aggregation rule, and a supermajority threshold. Amendments proceed via ideal-point voting followed by submission of public proposals carrying supermajority support (sourced from deliberation, vote aggregation, or AI mediation); the rule adopts any such proposal with positive maximal score or retains the status quo. The paper focuses on the generalized median, proving that at majority threshold no misreport weakly dominates sincere voting, studies the compromise gap, and instantiates the framework to seven canonical settings (electing officers, setting rates, allocating budgets, ranking priorities, selecting boards, drafting bylaws, and amending the constitution).

Significance. If the polynomial-time integration and incentive results hold, the work would be significant for providing a self-contained, device-implementable protocol that unifies previously isolated stages of computational social choice into constitutional design for digital communities. The explicit handling of supermajority amendment and the focus on reality-aware rules add practical value beyond standard aggregation theory.

major comments (3)

[Abstract] Abstract: the central claim of a 'coherent polynomial-time protocol' is load-bearing yet unsupported, as the text acknowledges that key metric-space aggregators are NP-hard while relying on sourcing supermajority-supported proposals via vote aggregation or AI mediation without providing an explicit polynomial-time algorithm, verification procedure, or complexity bound for arbitrary metric spaces (as opposed to the seven instantiations).
[Generalized median property] Generalized median incentive property: the stated result that at majority threshold no misreport weakly dominates sincere voting is presented, but the framework assigns variable supermajority thresholds per component; no argument is given that the property extends (or fails to extend) to thresholds above majority, which directly affects the amendment process for most components.
[Amendment process] Amendment rule: the protocol adopts 'a supported proposal with positive maximal score' but the score function is undefined in the abstract and its interaction with the chosen aggregation rule (e.g., generalized median) is not derived, leaving the correctness of the overall selection step unverified.

minor comments (2)

Ensure all terms such as 'maximal score' and 'compromise gap' receive precise definitions before their first use in the main text.
The seven instantiations would benefit from explicit metric-space definitions and rule specifications in a dedicated table or subsection to improve clarity and reproducibility.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the constructive report and the recommendation for major revision. We address each major comment below with clarifications, proposed revisions, and honest limitations of the current manuscript.

read point-by-point responses

Referee: [Abstract] Abstract: the central claim of a 'coherent polynomial-time protocol' is load-bearing yet unsupported, as the text acknowledges that key metric-space aggregators are NP-hard while relying on sourcing supermajority-supported proposals via vote aggregation or AI mediation without providing an explicit polynomial-time algorithm, verification procedure, or complexity bound for arbitrary metric spaces (as opposed to the seven instantiations).

Authors: We agree the abstract claim requires tightening. The protocol is polynomial-time in the adoption step (a linear scan over submitted proposals to find the one with maximal positive score) and in the voting phase (ideal-point reporting). However, the manuscript does not supply a general polynomial-time algorithm for generating the proposals themselves in arbitrary metric spaces; it instead treats proposal generation as external (deliberation, AI mediation, or domain-specific aggregation oracles). This is a genuine gap for the general case. We will revise the abstract and add a dedicated complexity paragraph stating the assumptions and restricting the polynomial-time guarantee to the seven instantiations plus the adoption/verification steps. revision: partial
Referee: [Generalized median property] Generalized median incentive property: the stated result that at majority threshold no misreport weakly dominates sincere voting is presented, but the framework assigns variable supermajority thresholds per component; no argument is given that the property extends (or fails to extend) to thresholds above majority, which directly affects the amendment process for most components.

Authors: The incentive proof is deliberately stated only for the majority threshold because it relies on the single-crossing property of the generalized median at 50 percent. For thresholds strictly above majority the dominance result does not necessarily hold, as a misreport could strategically shift the effective median enough to clear the higher bar. We will add an explicit remark after the theorem noting the limitation, together with a short discussion that the property is threshold-specific and that higher thresholds may require additional incentive-compatible mechanisms or acceptance of weaker strategy-proofness guarantees. revision: yes
Referee: [Amendment process] Amendment rule: the protocol adopts 'a supported proposal with positive maximal score' but the score function is undefined in the abstract and its interaction with the chosen aggregation rule (e.g., generalized median) is not derived, leaving the correctness of the overall selection step unverified.

Authors: The score function (maximal number of agents whose reported ideal point lies within a given distance of the proposal under the component metric) is defined in Section 3.2 of the full text, but the abstract and the high-level protocol description do not restate it or derive its interaction with the generalized median. We will revise the abstract to include a one-sentence definition of the score and add a short derivation in the amendment subsection showing that, under the generalized median, the maximal-score rule selects a proposal that is at least as close to the median as the status quo when such a proposal exists. revision: yes

Circularity Check

0 steps flagged

No significant circularity; protocol and properties derived internally from stated definitions

full rationale

The paper presents a self-contained framework: it defines the constitution as assigning per-component metric space, aggregation rule, and supermajority threshold; specifies the amendment process as ideal-point voting followed by submission of publicly supported proposals (sourced externally via deliberation/aggregation/AI); and states the adoption rule as selecting a supported proposal with positive maximal score (or retaining status quo). The generalized-median incentive property is proven directly at majority threshold, and the compromise gap is studied as a defined quantity. Seven instantiations are applications of the framework rather than reductions. No load-bearing step reduces by construction to fitted inputs, self-citations, or prior ansatzes; external sourcing of proposals is assumed rather than derived circularly. The poly-time claim holds under the assumption that proposals are provided, with no internal equation or definition forcing the result from its own outputs.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 1 invented entities

The central claim rests on assumptions about metric spaces and voting behavior, with the supermajority thresholds as configurable parameters set by the constitution itself.

free parameters (1)

supermajority threshold
Per-component parameter in the constitution that determines when a proposal is adopted; chosen as part of the governance setup.

axioms (1)

domain assumption Metric spaces allow representation of ideal points and distances for preference aggregation via rules like the generalized median.
Invoked for the voting and amendment stages in the protocol.

invented entities (1)

Constitutional Consensus protocol no independent evidence
purpose: To enable digital sovereignty by running the full governance process on personal devices.
Newly proposed integrated framework combining existing concepts.

pith-pipeline@v0.9.0 · 5571 in / 1331 out tokens · 52929 ms · 2026-05-15T05:54:27.773902+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages · 1 internal anchor

[1]

In: Proc

Abramowitz, B., Shapiro, E., Talmon, N.: In the beginning there werenagents: Founding and amending a constitution. In: Proc. of ADT’21. pp. 119–131 (2021) Constitutional Governance in Metric Spaces 15

work page 2021
[2]

Artificial Intelligence264, 27–51 (2018)

Anshelevich, E., Bhardwaj, O., Elkind, E., Postl, J., Skowron, P.: Approximating optimal social choice under metric preferences. Artificial Intelligence264, 27–51 (2018)

work page 2018
[3]

Journal of Political Economy 56(1), 23–34 (1948)

Black, D.: On the rationale of group decision-making. Journal of Political Economy 56(1), 23–34 (1948)

work page 1948
[4]

Social Choice and Welfare49(3–4), 657–669 (2017)

Brady, R.L., Chambers, C.P.: A spatial analogue of May’s theorem. Social Choice and Welfare49(3–4), 657–669 (2017)

work page 2017
[5]

In: Theoretical Aspects of Rationality and Knowledge (TARK 2025)

Briman, E., Shapiro, E., Talmon, N.: Ai-generated compromises for coalition for- mation: 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

work page doi:10.4204/eptcs.437.32 2025
[6]

Journal of Artificial Intelligence Research70, 1413–1439 (2021)

Bulteau, L., Shahaf, G., Shapiro, E., Talmon, N.: Aggregation over metric spaces: Proposing and voting in elections, budgeting, and legislation. Journal of Artificial Intelligence Research70, 1413–1439 (2021)

work page 2021
[7]

arXiv preprint arXiv:2202.12594 (2022)

Elkind,E.,Ghosh,A.,Goldberg,P.:Complexityofdeliberativecoalitionformation. arXiv preprint arXiv:2202.12594 (2022)

work page arXiv 2022
[8]

In: Proceedings of AAAI ’21

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)

work page 2021
[9]

Cam- bridge University Press (1984)

Enelow, J.M., Hinich, M.J.: The Spatial Theory of Voting: An Introduction. Cam- bridge University Press (1984)

work page 1984
[10]

In: Proceedings of the 2017 ACM Conference on Economics and Computation (EC ’17)

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)

work page 2017
[11]

Operations Research12(3), 450–459 (1964)

Hakimi, S.L.: Optimum locations of switching centers and the absolute centers and medians of a graph. Operations Research12(3), 450–459 (1964)

work page 1964
[12]

Oxford Review of Economic Policy12(4), 53–69 (1996)

Hart, O., Moore, J.: The governance of exchanges: members’ cooperatives versus outside ownership. Oxford Review of Economic Policy12(4), 53–69 (1996)

work page 1996
[13]

arXiv preprint arXiv:2505.19216 (2025)

Keidar, I., Lewis-Pye, A., Shapiro, E.: Constitutional consensus. arXiv preprint arXiv:2505.19216 (2025)

work page arXiv 2025
[14]

Journal of Economic Theory12(3), 472–482 (1976)

McKelvey, R.D.: Intransitivities in multidimensional voting models and some im- plications for agenda control. Journal of Economic Theory12(3), 472–482 (1976)

work page 1976
[15]

Journal of Artificial Intelligence Research73, 1517–1545 (2022)

Meir, R., Shahaf, G., Shapiro, E., Talmon, N.: Sybil-resilient social choice with par- tial information. Journal of Artificial Intelligence Research73, 1517–1545 (2022). https://doi.org/10.1613/jair.1.13390

work page doi:10.1613/jair.1.13390 2022
[16]

Journal of Eco- nomic Theory135(1), 269–305 (2007)

Nehring, K., Puppe, C.: The structure of strategy-proof social choice — Part I: General characterization and possibility results on median spaces. Journal of Eco- nomic Theory135(1), 269–305 (2007)

work page 2007
[17]

131, Karlsruhe Institute of Technology

Nehring,K.,Puppe,C.:Resourceallocationbyfrugalmajorityrule(2019),working Paper Series in Economics No. 131, Karlsruhe Institute of Technology

work page 2019
[18]

ZOR – Methods and Models of Operations Research38(1), 35–53 (1993)

Peters, H., van der Stel, H., Storcken, T.: Generalized median solutions, strategy- proofness and strictly convex norms. ZOR – Methods and Models of Operations Research38(1), 35–53 (1993)

work page 1993
[19]

The American Economic Review57(4), 787–806 (1967)

Plott, C.R.: A notion of equilibrium and its possibility under majority rule. The American Economic Review57(4), 787–806 (1967)

work page 1967
[20]

In: Proceedings of the 10th International Workshop on Cooperative Information Agents (CIA ’06)

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) 16 Shapiro and Talmon

work page 2006
[21]

In: Proceedings of the 10th ACM Conference on Electronic Commerce (EC ’09)

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)

work page 2009
[22]

Puppe, C., Rollmann, J.: Mean versus median voting in multi-dimensional budget allocationproblems:Alaboratoryexperiment.GamesandEconomicBehavior130, 309–330 (2021)

work page 2021
[23]

In: Proceedings of the 28th International Joint Conference on Artificial Intelligence

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)

work page 2019
[24]

In: 37th International Symposium on Dis- tributed Computing (DISC 2023)

Shapiro, E.: Grassroots distributed systems: Concept, examples, implementation and applications (brief announcement). In: 37th International Symposium on Dis- tributed Computing (DISC 2023). (Extended version: arXiv:2301.04391). pp. 47:1, 47:7. LIPICS, Italy (2023)

work page arXiv 2023
[25]

In: Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Sys- tems

Shapiro, E., Talmon, N.: Incorporating reality into social choice. In: Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Sys- tems. pp. 1188–1192 (2018)

work page 2018
[26]

Grassroots Federation: Fair Democratic Governance at Scale

Talmon, N., Shapiro, E.: Grassroots federation: Fair democratic governance at scale. arXiv preprint arXiv:2505.02208; also Proc. of AAMAS’26 (2025) A Proofs This appendix collects the proofs of results stated in the body, in document order. Proposition 1.For any aggregation ruleϕcomputable inO(n)time, each round of the constitutional governance rule produ...

work page internal anchor Pith review Pith/arXiv arXiv 2025
[27]

For each pair(p, q)∈P r ×P r withp̸=q, compute a bounded setC(p, q)⊆X of candidate combinations ofpandq(in metric spaces with unique geodesic midpoints,C(p, q)is the singleton midpoint; otherwiseC(p, q)enumerates or samples a bounded number of tie-breaking candidates)

work page
[28]

Letc ∗ ∈arg max{ϕ(u(c)) :c∈ S p,q C(p, q)}

work page
[29]

in” or “out

Ifϕ(u(c ∗))>max p∈P r ϕ(u(p)), returnc ∗ as a public proposal; otherwise re- turn⊥. Proposition 13 (ComplexityofHeuristicP).Heuristic P runs inO(|P r|2(Tc+ n))time, whereT c bounds the cost of computing the candidate combinations for one pair:O(m)for the simplex under Euclidean distance,O(m 2)for per- mutations under swap distance,O(|A|)for subsets under ...

work page
[30]

CG>0” = fraction of profiles (with OPT>0) for which CG>0. “Gap-closing

Otherwiseσremains unchanged. Theh-rule prevents a minority from imposing stricter requirements or weak- ening the constitution; [1] establishes that it is the unique rule satisfying their axioms. Running example: raising the budget threshold.The cooperative of Ex- ample 1 amends the budget threshold fromσ= 1/2to a higher value after experience with severa...

work page