Talk is Cheap, Communication is Hard: Dynamic Grounding Failures and Repair in Multi-Agent Negotiation

Abstract

Grounding requires agents to establish and maintain the mutual understanding needed to coordinate over multiple turns. Yet multi-agent LLM benchmarks often focus on static, one-shot tasks rather than interactive settings in which agents must negotiate and repair shared understanding over time. We introduce an iterated negotiation game with private project values, shared resource constraints, and verifiable joint optima. Individual agents identify optimal allocations in isolation, yet dyads frequently miss exact joint optima when private objectives conflict. Analysis of game traces reveals four recurrent patterns: loss of shared interaction history, anchoring to early proposals, equal-split shortcuts, and abandonment of public agreements at execution. We then vary partner context, information transparency, and incentive framing. Full transparency improves coordination without reliably improving exact-optimum attainment, while explicit joint-reward framing yields gains across several dyads. Our findings show that interaction structure substantially affects dyadic performance: what agents know about one another and whether their incentives are explicitly aligned both influence coordination. Nonetheless, reliable coordination remains difficult when agents bargain over conflicting private objectives. These results identify common-ground formation, joint-plan maintenance, and commitment execution as central targets for improving decentralized multi-agent coordination.