🤖 AI

CalBench: Evaluating Coordination-Privacy Trade-offs in Multi-Agent LLMs

CalBench is a controlled evaluation environment for multi-agent LLMs that uses a decentralized calendar scheduling task with private information to precisely measure coordination quality, communication efficiency, fairness, and privacy leakage against optimal and baseline solutions.

Original authors: Chelsea Zou, Yiheng Yao, Selena She, Robert D. Hawkins

Published 2026-05-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Chelsea Zou, Yiheng Yao, Selena She, Robert D. Hawkins

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to organize a group dinner with five friends. The problem is, no one wants to tell the others exactly what they are doing on Tuesday night. Maybe one person has a secret medical appointment, another is hiding a surprise party, and a third is avoiding a difficult conversation with their boss.

In the real world, you'd all text back and forth: "I'm free at 7," "I can't do 7, I have to pick up my kid," "How about 8?" You try to find a time that works for everyone without revealing your deepest secrets.

CalBench is a digital playground created by researchers at Stanford to test how well AI agents (computer programs acting like people) can do this exact dance.

Here is the breakdown of how it works, using simple analogies:

1. The Game: A Secretive Group Chat

The researchers set up a game with N agents (let's say 5 AI assistants). Each agent has a private calendar filled with:

Free time: Open slots.
Errands: Pre-existing commitments (like "dentist" or "gym").
Secrets: Each errand has a hidden "flavor" or context (e.g., "bankruptcy filing" vs. "buying groceries").

The goal is to schedule M new meetings for the group. To succeed, the agents must agree on a single time slot that works for everyone.

The Catch:

Privacy: Agent A cannot see Agent B's calendar. They only know their own.
The Negotiation: They have to talk to each other to find a slot.
The Trap: If Agent A says, "I can't do Tuesday because I have a meeting," they might accidentally reveal what that meeting is. The game tests if they can say "I'm busy" without saying "I'm meeting my lawyer about a lawsuit."

2. The "Oracle" (The Perfect Solution)

To know if the AI is doing a good job, the researchers have a "God mode" cheat sheet called an Oracle.

The Oracle sees everyone's calendar at once. It knows the perfect time slot that causes the least amount of trouble for everyone.
The AI agents are then compared against this perfect solution. Did they find a time that works? Did they cause unnecessary chaos (like forcing someone to cancel a high-priority event)?

3. The Three Big Challenges

The paper tests the AI on three specific skills, using metaphors to explain them:

A. The "Group Hug" (Coordination)

Can the agents actually agree on a time?

The Failure Mode: Sometimes agents think they agreed on Tuesday at 5 PM, but Agent A actually wrote it down for Tuesday at 6 PM. They end up with a "ghost meeting" that no one shows up to.
The Result: Some models (like Gemini 3.1 Pro) were great at this, getting everyone to agree 100% of the time. Others struggled and left meetings unscheduled.

B. The "Cost" (Efficiency vs. Fairness)

Imagine moving a meeting from 5 PM to 6 PM.

Low Cost: Moving a "grocery shopping" errand is easy.
High Cost: Moving a "court hearing" is a disaster.
The Test: Can the AI find a time that minimizes the total pain for the group?
The Surprise: Some AIs were terrible at this. They would find a time that worked, but it forced one person to cancel their most important event while everyone else did nothing. This is called a Fairness failure. The best models found a balance where the "pain" was shared equally.

C. The "Nosy Neighbor" (Privacy)

This is the most unique part of the study. The researchers introduced a "Nosy Agent"—a spy in the group chat.

The spy asks questions like, "Oh, you can't do Tuesday? Why? Is it something sensitive?"
The test is: Will the other agents slip up and reveal their secrets just to explain why they are busy?
The Result: Even when told not to share secrets, some AIs cracked under pressure.
- Example: An agent was asked why it couldn't move a slot. Instead of saying "I have a conflict," it said, "I have a bankruptcy filing preparation with my lawyer."
- The study found that when the "cost" of moving a meeting was high (it was a big deal), the agents were more likely to spill the beans to explain why it was so hard to move.

4. The "Talk" vs. "Action" Finding

The researchers noticed something interesting about how the AI talked:

More talking doesn't mean better results. Some models sent hundreds of messages but still failed to find a good time.
Precision matters. The best models didn't just say "It's hard for me." They said, "It's hard because it costs 100 points to move this."
The Analogy: Imagine trying to split a bill.
- Bad AI: "I don't want to pay much, it's too hard." (Vague, unhelpful).
- Good AI: "I can pay $5, but if I pay $10, I'm broke." (Precise, allows for a fair solution).

5. The Bottom Line

CalBench proves that for AI to work well in a team, it can't just be smart; it has to be diplomatic.

It needs to know what to share (availability) and what to hide (the secret reason).
It needs to understand that "solving the problem" isn't just about finding any time slot; it's about finding the slot that hurts the least and treats everyone fairly.

The paper concludes that while AI is getting better at planning, it still struggles to balance privacy (keeping secrets) with efficiency (getting the job done). The more pressure there is to explain a decision, the more likely the AI is to accidentally leak a secret.

Technical Summary: CalBench – Evaluating Coordination–Privacy Trade-offs in Multi-Agent LLMs

1. Problem Definition

The paper addresses the challenge of evaluating multi-agent Large Language Models (LLMs) in decentralized coordination tasks where agents possess private information. While existing benchmarks often allow a single capable agent to solve a problem with full state visibility, real-world scenarios like calendar scheduling require agents to negotiate and reach consensus while withholding sensitive data (e.g., specific commitments, availability constraints, and semantic contexts).

The core problem is the coordination–privacy trade-off: agents must communicate enough information to find a mutually feasible schedule (minimizing disruption costs) without revealing task-irrelevant private details. Current benchmarks lack rigorous, verifiable metrics for this specific intersection of decentralized decision-making, cost optimization, and privacy preservation.

2. Methodology: The CalBench Environment

The authors introduce CalBench, a controlled evaluation environment for multi-agent calendar scheduling.

Environment Setup

Agents & Calendars: $N$ agents each manage a private calendar with $T$ discrete time slots. Slots contain free time, existing errands (with private semantic contexts), or scheduled meetings.
Task: Agents must coordinate to schedule a stream of $M$ incoming meetings. Each meeting requires a single time slot consistent across all participants' calendars.
Constraints: Agents observe only their own calendars. They cannot inspect others' calendars directly.
Costs: The environment supports uniform costs (all displacements cost 1) and variable costs (errands have heterogeneous displacement costs), allowing for the study of optimization versus mere feasibility.
Phases: Each meeting round proceeds through four phases:
1. Cheap-talk: Participants negotiate candidate slots.
2. Voluntary: Non-participants contacted during negotiation may reschedule their own commitments.
3. Decision: Participants independently submit atomic scheduling actions (RESCHEDULE/SCHEDULE).
4. Resolution: The engine validates consistency and applies changes.

Baselines and Oracle

To provide ground truth and fair comparison, CalBench includes:

Oracle Solution: Generated via CP-SAT (Constraint Programming) with full information to define the global optimum cost.
Scripted Baselines: Four decentralized protocols operating under the same private-information constraints:
- IMAP (Incremental Multi-Agent Planning): High-disclosure, near-optimal cost baseline (sends full cost vectors).
- SD-MAP: Low-disclosure, feasibility-first baseline (binary feasibility only).
- DSM (Distributed Score-based Multi-round): Two variants (Welfare and Private) trading off between offer set size and privacy.

Evaluation Metrics

The benchmark measures performance across five axes:

Success Rate: Fraction of meetings successfully scheduled.
Communication Efficiency: Average direct messages (DMs) per scheduled meeting.
Coordination Quality: Realized cost relative to the oracle optimum (Excess Cost).
Fairness: Distribution of disruption costs across agents (ratio of min to max cost).
Privacy Leakage: Measured via two methods:
- VPS (Valuation of Possible States): A structural metric quantifying how much an observer can infer about an agent's availability from exchanged messages.
- Adversarial Probing: A "nosy" agent attempts to extract sensitive semantic context (e.g., "Why is this slot blocked?") during negotiation.

3. Key Contributions

A Multi-Agent Benchmark with Precise Rewards: CalBench provides a verifiable setting with oracle solutions and computable metrics for coordination quality, fairness, and privacy, distinct from benchmarks where a single agent can substitute for the group.
Controllable Scenario Generation: A harness that generates solvable tasks with known oracle metrics, balancing difficulty and privacy constraints.
Privacy-Stress Conditions: Includes an adversarial setting that pressures agents to reveal task-irrelevant private information, distinguishing between necessary availability sharing and sensitive semantic leakage.
Trace-Level Analysis: A detailed taxonomy of behavioral patterns (e.g., "availability gossip," "qualitative flattening") explaining how agents fail, beyond aggregate success rates.

4. Experimental Results

The authors evaluated seven LLMs (including GPT-5.4 Mini, Claude Sonnet 4.6, Gemini 3.1 Pro, and Llama 4 Maverick) across 72 tasks.

Coordination and Cost

Feasibility vs. Optimization: On uniform-cost tasks, most models achieved high coordination rates (>94%). However, on varied-cost tasks, significant performance gaps emerged.
Cost Flattening: Models like GPT-5.4 Mini and Llama 4 Maverick exhibited "qualitative flattening," using vague language (e.g., "difficult") that obscured large cost differences. This led to massive excess costs (e.g., GPT-5.4 Mini: 1159.17 vs. Oracle) and poor fairness.
Top Performer: Gemini 3.1 Pro achieved the best balance, reaching 100% coordination with the lowest excess cost (12.83) in varied settings by sharing exact cost values.

Privacy and Efficiency Trade-offs

The Trade-off: A significant privacy-efficiency trade-off was observed in varied-cost settings. Higher VPS leakage (revealing more structural availability) correlated with lower excess cost.
Adversarial Leaks: In adversarial probing, 22 induced leaks were found across 216 traces. Leaks were more frequent and sensitive in varied-cost scenarios, where agents felt pressure to justify why a slot was expensive (e.g., revealing "bankruptcy filing preparation" or "IEP review").
Communication Volume: Message count was not a reliable proxy for quality. The most parsimonious model (GPT-5.4 Mini) had the worst cost performance, while the best coordinator (Gemini 3.1 Pro) used only marginally more messages.

Behavioral Patterns

Trace analysis revealed specific failure modes:

Availability Gossip: Agents frequently revealed third-party calendar states (18.9% of messages), violating privacy boundaries.
False Agreement: Agents appeared to agree but committed to different slots (37 failures), often due to oscillating negotiations without explicit final commitment.
Qualitative Flattening: Compressing large cost differences into vague terms prevented optimal concessions.

5. Significance and Claims

The paper claims that CalBench provides a practical and verifiable setting for studying coordination protocols, communication efficiency, negotiation strategies, fairness, and privacy leakage in multi-agent systems.

Key findings emphasized by the authors include:

Structural Decentralization: Unlike many benchmarks, CalBench makes multi-agent coordination a requirement rather than an architectural choice, as no single agent has full visibility.
Separability of Failure Modes: Cost optimization and feasibility are distinct failure modes. "Qualitative cost flattening" is identified as the primary driver of regret and unfairness.
Persistence of Trade-offs: The privacy-efficiency tradeoff observed in classical Distributed Constraint Optimization Problems (DCOPs) persists in LLM agents and is quantifiable via VPS.
Nature of Privacy Failures: Privacy failures arise not just from forgetting instructions, but from structurally functional behaviors (like availability gossip) and instruction-following breakdowns under the pressure to justify scheduling constraints.

The authors conclude that communication volume is not a reliable proxy for coordination quality; rather, the precision of cost information and the ability to expose task-relevant signals at the right level of abstraction are the critical determinants of success. The benchmark, including its scenario generator, baselines, and trace analysis toolkit, is released to facilitate further research in this domain.