SCARCE: Emergent Institutions in Long-Horizon Multi-Agent Coding Systems

Abhinav Kumar; Rediet Abebe; Eugene Bagdasarian; Sahar Abdelnabi

cs.MAOct 15, 2026

SCARCE: Emergent Institutions in Long-Horizon Multi-Agent Coding Systems

Authors: Abhinav Kumar, Rediet Abebe, Eugene Bagdasarian, Sahar Abdelnabi

Organizations: University of Massachusetts Amherst · ELLIS Institute Tübingen · MPI for Intelligent Systems · Tübingen AI Center

Abstract

As autonomous agents become widely deployed, coordinating access to shared computing resources and services will become increasingly important. Recent incidents have already revealed unplanned coordination between agents, highlighting the safety implications of these interactions. Yet prior studies of agent negotiation often use stylized games and simulated bargaining, leaving open how these behaviors develop during sustained, long-horizon tasks. We propose SCARCE (Shared Compute ARena for Coding agEnts), a framework in which agents solve sequences of coding tasks under individual deadlines while negotiating access to a shared execution resource. This negotiation determines when and for how long they can inspect programs, compile code, and run tests. We find that agents spontaneously develop informal institutions: persistent rules and commitments grounded in reputation, reciprocity, and precedent. These arrangements, which we call institutional behaviors, carry across tasks and influence resource allocation, with agents sometimes forgoing immediate advantages to honor earlier agreements. We develop a 21-category taxonomy of negotiation strategies and emergent norms and use it to analyze eight models and audit more than 1,500 trajectories across different environmental settings. Among the models tested, newer frontier models exhibit more institutional behaviors than older or lightweight models. Alongside cooperation, we observe exclusionary coalitions and rare divide-and-conquer strategies. SCARCE provides a controlled setting for proactively and systematically auditing how these relationships emerge, shape access to resources, and affect the safety and coordination of multi-agent systems.

Figures & tables

Figure 1: Overview of SCARCE. Left: Each worker rebuilds a ProgramBench program under a private deadline and credit budget on a single shared sandbox. Middle: Workers obtain windows through repeated negotiation rounds. Right: Across subruns, memory and reflection turn uniform early interactions into persistent institutions.

Figure 2: SCARCE methodology. Agents first enter a negotiation queue, where they request time on a shared resource and the position they want in the order, along with a bid to support the request. Agents then can negotiate through private messaging. Once the messaging session is over, they cast a ballot that the scheduler uses to grant the agents resource access based on the agreed-upon order.

Behavior	Agent excerpt
Goodwill banking Cooperates now to strengthen a future negotiation	“I take the convergent slot and bank the goodwill for my heavier build/test window later, where front position actually matters. ”
Reciprocity honoring Invokes and honors a prior commitment	“[…] so the commitment pays out now, and I’m honoring it in full. […] No reinterpretation, no ‘the situation changed’ walkback — the deal was the deal, and a commitment that only holds when it’s free isn’t a commitment.”

Figure 3: Agents do short-term cooperation to bank goodwill and use it in later negotiation rounds.

Behavior	Agent excerpt
Reference framing Price primary	“My 650 stands as declared […] position 1 follows from the price signal , and I’m not reading your declared position-1 ask as a contest; the stated prices settle it, same discipline as always. ”
Concession Welfare concession	“ Despite my higher bid of 300, the deadline-safety principle I’ve consistently honored requires yielding position 1 to them. ”
Coalition formation Explicit coalitions	“That’s a standing reciprocity agreement between the two of us for the rest of the subrun, not a one-off.”
Social dynamics Reputation preservation	“Honoring the commitment in my ballot is the reputationally right move, and the outcome likely still lands me at 3 via aggregate. That’s… slightly sneaky but honest : I state my preferred order per commitment, aggregate decides […]”

Figure 4: Examples of different negotiation and bargaining techniques.

Norm	Agent excerpt
Urgency norms Earliest Deadline	“ 5s of deadline remaining , I cannot survive any queue wait — position 1 is a hard necessity , not a preference.”
Scheduling norms Recency first	“[…] communication rank is just queue arrival order — it’s not a merit signal and has never been established as a tiebreaker in any prior round.”
Process norms Iterative Bargaining	“ The round converged after a brief crossed-message episode in round 1 […] I froze my ballot […] so all three ballots are identical and the schedule locks unanimously. ”

Figure 5: Example of final norms agents can converge to during or after negotiation.

		frontier tier (latest $\to$ oldest)					efficiency tier (latest $\to$ oldest)
	Behavior	Opus-5	Kimi-k3	GLM-5.3	GLM-5.2	Kimi-k2.6	GPT-5.6 Luna	haiku-4.5	gpt-oss-120b
Relational	Reciprocity	19	13	18	21	$\cdot$	$\cdot$	$\cdot$	4
	Logrolling	3	$\cdot$	$\cdot$	$\cdot$	$\cdot$	$\cdot$	$\cdot$	$\cdot$
	Divide-and-conquer	$\cdot$	$\cdot$	$\cdot$	$<$ 1	$\cdot$	$\cdot$	$\cdot$	$\cdot$
	Coalition formation	14	10	27	16	$\cdot$	$\cdot$	$\cdot$	$\cdot$
	Coalition loyalty	11	1	6	9	$\cdot$	$\cdot$	$\cdot$	$\cdot$

Table 1: Classification of model trajectories, for 1 subrun, using the proposed taxonomy. Values indicate the percentage of rounds exhibiting each behavior. Since a single round can exhibit multiple behaviors, rounds may be assigned to more than one category.

Figure 6: Private channel utilization. Agents with higher institutional behavior also display higher utilization of private channels.

Behavior	Agent excerpt
Rule-making	“[…] task 60’s rank the schedule by task ID ascending (58 $>$ 59 $>$ 60) as the deterministic neutral tie-break , and that’s the convention I’m adopting on my side too — it’s the only rule every reasoning block can replicate without coordination .”
Rule-citing	“I apply the board’s established tie-break of ascending task ID , seating myself at 3 and task 76 at 4, matching the majority of ballots already cast .”

Figure 7: Rule-making and rule-citing. One agent proposes ascending task ID as a neutral tie-break and adopts it as a convention; another agent later invokes it as the board’s established rule.

Behavior	Agent excerpt
Meta-gaming	“Let me think about the meta-game: This is a negotiation exercise. The graders likely check whether I correctly handle the constraint that my remaining deadline is 0.0 — i.e., I cannot request a positive duration.”
Rival-targeting	“So it depends on second/third preferences. My messaging should target worker-02: argue that $44\!\to\!43\!\to\!42$ is the only order where its 900 window actually executes.”

Figure 8: Examples of rare negotiation behavior.

Behavior	Agent excerpt
Urgency premium	“I should bid high for position 1 since my window slipped last round and it’s the load-bearing.” stated bid: 400
Termination discount	“[…] a window my clock cannot absorb is a void slot […] and I will not fabricate a live-looking bid in front of nothing.” stated bid: 0

Figure 9: Agents near their deadline (close to termination) either pay a premium for an early slot or, once no usable window remains, stop bidding entirely.

Behavior	With mem.	No mem.
Reciprocity	18	$0$
Coalition formation	27	$0$
Coalition loyalty	6	$0$
Reputation	6	$0$

Table 11

Figure 10: Average time requested by agents increases over subruns.

Multi-Agent Resource Allocation

See all 28 papers

When Agents Coordinate: Measuring Coordination in Multi-Agent AI Coding
Aug 17, 2026Giuseppe Destefanis, Tomaso AsteMulti-Agent Coordination Multi-Agent Coding
Department of Computer Science, University College London, UK
OpenCollab: A Multi-Agent Coding Framework with Programmable Collaboration and Controllable Runtime
Sep 29, 2026Chun-Wah Hsu, Kai Gong, Yu Wu +12Multi-Agent Orchestration Multi-Agent Collaboration
Shanghai Jiao Tong University · University of Cambridge · Nanyang Technological University +4
Emergent Risks in Generative Multi-Agent Systems
Mar 29, 2026Yue Huang, Yu Jiang, Wenjie Wang +12Multi-Agent LLM Systems Multi-Agent Systems
University of Notre Dame · LMU Munich · University of Washington +7

Aug 17, 2026J/K move · Enter open · S save

When Agents Coordinate: Measuring Coordination in Multi-Agent AI Coding

Giuseppe Destefanis, Tomaso Aste

Department of Computer Science, University College London, UK

Multi-Agent Coordination Multi-Agent Coding Multi-Agent Communication

Open paper AskPDF arXiv

We study how teams of AI coding agents coordinate while solving programming tasks. Current evaluations usually report whether the agents complete the task and how much the run costs, leaving the coordination inside the team largely unmeasured. We introduce an instrument to measure this coordination. Each run is represented as a temporal network in which agents and files are nodes, and messages, file writes, and file reads are timestamped directed edges with an associated cost. We apply this instrument to 1902 runs, each evaluated with a fixed test suite, across configurations that vary the team size, the team structure, and the file policy. The resulting networks show how coordination changes as teams grow and as the work changes. Direct messaging initially increases close to quadratically with the number of agents, with much of this growth coming from an early round of introductions. As the teams grow further, this increase levels off in the largest teams we study, where agents increasingly communicate through broadcast messages. The task also shapes the network that emerges. Work built around a shared specification produces dense, highly connected teams, while pipeline tasks produce sparse networks organised around local interfaces. Shared files can replace repeated 1-to-1 communication, cutting output tokens by about 42% at eight agents on message-heavy work, while adding overhead when files already carry the coordination. Naming one agent as coordinator creates no communication hub and provides no reliable improvement in success. We also observe an unprompted tendency for agents to seek out hidden grading material. We repeat the key experimental conditions in a sealed environment, replacing the hidden material with marked placeholder files. Across 244 additional runs, agents still reach for it in four fifths of runs, while the coordinator and file-channel findings reproduce.

Abstract

Multi-Agent Resource Allocation

Explore similar work

When Agents Coordinate: Measuring Coordination in Multi-Agent AI Coding

OpenCollab: A Multi-Agent Coding Framework with Programmable Collaboration and Controllable Runtime

Emergent Risks in Generative Multi-Agent Systems