The Accountability Horizon: An Impossibility Theorem for Governing Human-Agent Collectives

Haileleol Tibebu; Hewan Shemtaga

cs.AIApr 9, 2026

The Accountability Horizon: An Impossibility Theorem for Governing Human-Agent Collectives

Authors: Haileleol Tibebu, Hewan Shemtaga

Organizations: University of Illinois at Urbana-Champaign, Champaign, IL, USA · Responsible Intelligence Institute, Addis Ababa, Ethiopia

Abstract

Existing accountability frameworks for AI systems, legal, ethical, and regulatory, rest on a shared assumption: for any consequential outcome, at least one identifiable person had enough involvement and foresight to bear meaningful responsibility. This paper proves that agentic AI systems violate this assumption not as an engineering limitation but as a mathematical necessity once autonomy exceeds a computable threshold. We introduce Human-Agent Collectives, a formalisation of joint human-AI systems where agents are modelled as state-policy tuples within a shared structural causal model. Autonomy is characterised through a four-dimensional information-theoretic profile (epistemic, executive, evaluative, social); collective behaviour through interaction graphs and joint action spaces. We axiomatise legitimate accountability through four minimal properties: Attributability (responsibility requires causal contribution), Foreseeability Bound (responsibility cannot exceed predictive capacity), Non-Vacuity (at least one agent bears non-trivial responsibility), and Completeness (all responsibility must be fully allocated). Our central result, the Accountability Incompleteness Theorem, proves that for any collective whose compound autonomy exceeds the Accountability Horizon and whose interaction graph contains a human-AI feedback cycle, no framework can satisfy all four properties simultaneously. The impossibility is structural: transparency, audits, and oversight cannot resolve it without reducing autonomy. Below the threshold, legitimate frameworks exist, establishing a sharp phase transition. Experiments on 3,000 synthetic collectives confirm all predictions with zero violations. This is the first impossibility result in AI governance, establishing a formal boundary below which current paradigms remain valid and above which distributed accountability mechanisms become necessary.

Figures & tables

Agent	$\alpha^{E}$	$\alpha^{X}$	$\alpha^{D}$	$\alpha^{S}$	$A(m)$	$\eta(m,G)$
$m_{1}$ (diagnostic)	0.85	0.30	0.60	0.70	0.605	1.00
$m_{2}$ (treatment)	0.70	0.25	0.50	0.60	0.505	0.67
$m_{3}$ (allocator)	0.40	0.80	0.70	0.30	0.560	0.33

Table 1: Autonomy profiles for HAC

\mathcal{H}_{1}

(clinical decision support). Weight vector:

\mathbf{w}=(0.30,0.30,0.20,0.20)

Statistic	$\alpha^{E}$	$\alpha^{X}$	$\alpha^{D}$	$\alpha^{S}$
Mean ( $k=8$ agents)	0.75	0.92	0.65	0.85
Std. dev.	0.08	0.05	0.10	0.07
Min compound $\alpha^{X}\cdot\alpha^{E}$	0.621	—	—	—

Table 2: Summary statistics for HAC

\mathcal{H}_{2}

(financial trading). Full system-level parameters in Appendix E.

Figure 1: Human-Agent Collective topologies. Left: feedforward topology (AI outputs reviewed by humans, no feedback) is always governable regardless of autonomy level. Right: feedback cycle topology (AI observes and adapts to human responses) is governable only when compound autonomy remains below the Accountability Horizon $\hat{\Lambda}^{*}$ .

$\theta$	$\hat{\Lambda}$	Budget	$\Delta$	Status
0.00	0.621	1.137	0.000	Below
0.10	0.656	1.032	0.000	Near $\hat{\Lambda}^{*}$
0.13	0.667	1.000	0.000	At $\hat{\Lambda}^{*}$
0.20	0.700	0.900	0.100	Above
0.40	0.784	0.648	0.352	Above
0.60	0.867	0.399	0.601	Above

Table 3: Phase transition in HAC

\mathcal{H}_{2}

under joint autonomy scaling.

|C_{\min}|=3

\hat{\Lambda}^{*}=1-1/3\approx 0.667

(Eq. ( 18 )).

Figure 2: Phase transition at the Accountability Horizon. Left: epistemic budget $|C_{\min}|\cdot(1-\hat{\Lambda})$ drops below the Completeness requirement ( $\sum\rho=1$ ) as joint autonomy scaling $\theta$ increases. Right: accountability residual $\Delta$ grows monotonically above the threshold. Transition at $\theta\approx 0.12$ , corresponding to $\hat{\Lambda}^{*}=0.667$ .

Figure 4: Combined Accountability Horizon $\hat{\Lambda}^{*}(\tau)=\min(1-1/|C_{\min}|,\;1-\tau)$ as a function of smallest mixed cycle size $|C_{\min}|$ and non-vacuity threshold $\tau$ . Green regions indicate higher thresholds (easier to govern); red/orange regions indicate lower thresholds (governance fails at lower autonomy levels). For small $\tau$ , the structural bound dominates; for large $\tau$ , the non-vacuity constraint binds.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Symbol	Definition
$H$ , $M$ , $N$	Sets of human agents, artificial agents, all agents ( $N=H\cup M$ )
$n$ , $k$	Number of human agents, number of artificial agents
$E=(\Omega,O,\mathcal{T})$	Environment: observation space, outcome space, outcome-generation function $\mathcal{T}:\Sigma\times\Omega_{\mathrm{ext}}\to\Delta(O)$
$\mathcal{M}$	Collective structural causal model
$G=(N,\mathcal{E})$	Directed interaction graph
$\mathcal{H}$	Human-Agent Collective

Appendix

Table 7

Parameter	Value
Humans ( $n$ )	10
Machines ( $k$ )	8
Mixed cycles $C(G)$	77
$\|C_{min}\|$	3
$\Lambda(\mathcal{H})$	0.7925
$\hat{\Lambda}$ (min compound)	0.6210

Appendix

Table 5:

\mathcal{H}_{2}

: Multi-Agent Financial Trading (Table 2 Expanded)

Explore similar work

Designing for Accountable Agents: a Viewpoint
Apr 8, 2026Stephen Cranefield, Nir OrenAI Accountability Multi-Agent Systems
Computing Science, University of Aberdeen, Aberdeen, UK
No One to Blame: A Framework of Constitutive AI Unaccountability
Aug 12, 2026Long Hoang Nguyen, Eva Späthe, Sebastian Lins +1AI Accountability AI Agent Governance
Technical University of Munich · University of Kassel
Cooperation After the Algorithm: Designing Human-AI Coexistence Beyond the Illusion of Collaboration
Feb 23, 2026Tatia CodreanuHuman-AI Collaboration AI Governance
Imperial College London, London SW7 2AZ, UK; I-X Imperial AI in Science Affiliate, London, UK; Information Cultures, Media Pedagogies, and Screen-Based Research Group, France

Apr 8, 2026J/K move · Enter open · S save

Designing for Accountable Agents: a Viewpoint

Stephen Cranefield, Nir Oren

Computing Science, University of Aberdeen, Aberdeen, UK

AI Accountability Multi-Agent Systems

Open paper AskPDF arXiv

AI systems are becoming increasingly complex, ubiquitous and autonomous, leading to increasing concerns about their impacts on individuals and society. In response, researchers have begun investigating how to ensure that the methods underlying AI decision-making are transparent and their decisions are explainable to people and conformant to human values and ethical principles. As part of this research thrust, the need for accountability within AI systems has been noted, but this notion has proven elusive to define; we aim to address this issue in the current paper. Unlike much recent work, we do not address accountability within the human organisational processes of developing and deploying AI; rather we consider what it would it mean for the agents within a multi-agent system (MAS), potentially including human agents, to be accountable to other agents or to have others accountable to them. In this work, we make the following contributions: we provide an in-depth survey of existing work on accountability in multiple disciplines, seeking to identify a coherent definition of the concept; we give a realistic example of a multi-agent system application domain that illustrates the benefits of enabling agents to follow accountability processes, and we identify a set of research challenges for the MAS community in building accountable agents, sketching out some initial solutions to these, thereby laying out a road-map for future research. Our focus is on laying the groundwork to enable autonomous elements within open socio-technical systems to take part in accountability processes.

Abstract

Explore similar work

Designing for Accountable Agents: a Viewpoint

No One to Blame: A Framework of Constitutive AI Unaccountability

Cooperation After the Algorithm: Designing Human-AI Coexistence Beyond the Illusion of Collaboration