TL;DR
CalBench is a new multi-agent benchmark designed to evaluate how well LLM assistants coordinate real-world tasks like calendar scheduling while protecting user privacy. By testing seven prominent model families, the researchers demonstrate that simply completing a scheduling task is a deceptive metric; models frequently incur unnecessary disruption costs, communicate inefficiently, and fail to balance the tension between privacy and group fairness.
What Problem Does This Paper Address?
As LLMs transition from passive chatbots to autonomous personal delegates, they are increasingly trusted with private user data like calendars, inboxes, and personal preferences. This introduces a fundamental multi-agent challenge: how can an AI assistant coordinate effectively with other assistants without over-sharing or leaking sensitive user information?
Calendar scheduling is a classic distributed constraint optimization problem where no single participant has full visibility or authority. Existing multi-agent benchmarks often fall short because they can be solved by a centralized agent with global knowledge. The authors introduce CalBench to isolate true decentralized coordination under strict partial-information constraints, providing a reproducible testbed to measure the trade-offs between task success, efficiency, fairness, and privacy.
Methods
CalBench models a game where $N$ agents manage separate private calendars and must schedule a stream of $M$ incoming meetings. Because agents cannot inspect each other's calendars, they must rely on language-mediated coordination.
The environment operates through a structured four-phase round for each meeting:
- Cheap-Talk: Agents communicate via configurable channels (private DMs, participant groupchats, or all-agent groupchats) to discuss availability and costs without revealing private semantic contexts.
- Voluntary Rescheduling: Non-participants affected by potential shifts can optionally move existing meetings to free up slots.
- Decision: Participants independently submit atomic batches of scheduling and rescheduling actions.
- Resolution: The environment validates the actions, ensuring all participants chose the same slot and that no hard constraints (like double-booking or moving immovable "blocked" errands) were violated.
To evaluate performance, CalBench uses a full-information global oracle via a CP-SAT solver to define the mathematically optimal schedule. Structural privacy leakage is quantified using Valuations of Possible States (VPS), a metric measuring how much an observer's belief about an agent's calendar shifts toward the truth based on the messages exchanged. For LLMs, this is captured via a reflection-calibrated prompt where agents self-report their changing beliefs after each round.
Datasets
The authors evaluate models using a newly generated benchmark suite consisting of 90 tasks (45 uniform-cost tasks where all events cost 1 unit to displace, and 45 varied-cost tasks where errands carry heterogeneous displacement costs of 1, 10, or 100).
Each task features:
- 5 sequential meetings
- 16 calendar slots
- $N=5$ agents
- 3 rotating participants per meeting
Calendar difficulty is controlled by varying the density of pre-filled errands (sampled from 60%, 80%, or 100% occupancy) and the number of immovable, blocked commitments.
Key Insights and Ideas
- Task Completion $\neq$ Coordination Quality: Simply booking a meeting does not mean the agents coordinated well. Models frequently leave significant avoidable disruption costs on the table compared to the CP-SAT oracle.
- More Talk Does Not Equal Better Results: Raw message volume is a weak proxy for coordination quality. Higher message counts do not reliably predict lower excess costs; what matters is whether the messages convey high-quality, cost-relevant information.
- The Privacy-Fairness Tension: Being overly silent to protect privacy can actively harm group dynamics. When an agent hides its internal displacement costs, it deprives teammates of the context needed to distribute scheduling burdens fairly, resulting in high group-level unfairness.
- First-Speaker Disadvantage: The sequential nature of negotiation creates an exposure asymmetry. The agent that speaks first in a round leaks significantly more privacy (higher VPS) by anchoring proposals, yet fails to secure lower costs for the user it represents.
Key Results
The benchmark evaluated seven model families, revealing stark performance differences, especially when moving from uniform-cost to varied-cost settings.
- Uniform-Cost Games: Most models performed well, near saturation. Qwen 3.6 Plus scheduled the most meetings (93.33% success rate), while DeepSeek V4 Pro achieved the lowest excess cost (0.18) and best fairness (0.396).
- Varied-Cost Games: This setting separated the models cleanly. DeepSeek V4 Pro maintained the highest task success (84.44%), but Llama 4 Maverick emerged as the most balanced delegate, achieving the lowest excess cost (0.24), lowest privacy leakage (VPS of 3.49), and the highest fairness (0.627).
- GPT-5.4 Mini Failure Mode: GPT-5.4 Mini demonstrated a severe coordination failure in varied-cost games. It achieved low privacy leakage (VPS of 4.60) but suffered the highest excess cost (1.49) and worst fairness (1.376). A message audit revealed that it achieved privacy by omitting cost-relevant context entirely, forcing its teammates to absorb unfair scheduling burdens.
Limitations and Future Work
The authors note several limitations in the current setup:
- Topology Constraints: The evaluation is restricted to a single topology ($N=5$ agents, 3 participants per meeting). Future work is required to test larger groups and longer, more complex meeting streams.
- Privacy Proxy Limits: Reflection-calibrated VPS measures reported belief updates rather than probing the latent model state directly.
- Assumption of Truthfulness: The benchmark assumes agents report constraints honestly, leaving strategic misrepresentation, negotiation bluffing, and adversarial deception as open avenues for future research.
Summary updated