Do LLM Agents Negotiate Rationally? A Mechanism-Design Framework for Verifiable Multi-Agent Interaction over A2A/MCP

Wael Albayaydh; Rui Zhao

Source-linked AI summary

Do LLM Agents Negotiate Rationally? A Mechanism-Design Framework for Verifiable Multi-Agent Interaction over A2A/MCP

Wael Albayaydh, Rui Zhao

arXiv:2608.14613v1Jul 10, 2026cs.AI

TL;DR

A2A and MCP support agent interoperability but do not ensure strategically correct outcomes. This paper encodes classical mechanisms as A2A constraints, adds runtime verification, and benchmarks LLM-agent behavior, finding that structured negotiation succeeds reliably while strategy-proofness varies sharply by backbone.

Problem
A2A and MCP standardize agent interoperability but provide limited evidence about whether LLM agents satisfy mechanism-design guarantees during negotiation.
Method
The framework expresses negotiation mechanisms as constraints over A2A message schemas, verifies and repairs protocol violations at runtime, and benchmarks outcomes against known optima.
Results
Across tasks, structured protocols reliably achieved 100% negotiation success, while strategy-proofness held essentially perfectly for one backbone and barely at all for another under identical auctions.
Takeaways & Limitations
Mechanism-design guarantees depend on both mechanism assumptions and model behavior, so strategic fidelity requires checking incentive conditions at the protocol layer.
Takeaways & Limitations
The evaluation covers only two backbones from one provider, so its results may not generalize to other providers or future model generations.

Abstract

from arXiv · show

Modern LLM-agent frameworks increasingly interoperate through standards such as Anthropic's Model Context Protocol (MCP) for agent-to-tool access and Google's Agent2Agent (A2A) protocol for agent delegation and negotiation. However, these protocols specify transport and discovery rather than strategic correctness and do not guarantee efficient, individually rational, or strategy-proof outcomes. We introduce a framework that (i) encodes classical negotiation mechanisms, including alternating-offers bargaining and Vickrey-Clarke-Groves-style auctions, as constraints over A2A message schemas; (ii) provides a lightweight runtime verification and repair layer that checks messages against protocol invariants; and (iii) offers a benchmark of negotiation and allocation tasks with known optimal solutions for measuring deviations from game-theoretic predictions. We evaluate multiple LLM backbones using unstructured dialogue, structured protocols, and structured protocols with verification. Across negotiation trials (N=30 per condition), verification reduces outcome variance, while structured protocols achieve 100 percent success for both models. After correcting parser artifacts, audited unstructured baselines achieve approximately 97 percent and 93.3 percent success. In auction experiments (N=30 per model), both models achieve 100 percent efficient allocation but differ sharply in truthful bidding: one bids its exact valuation in every trial, whereas the other does so in only 3.3 percent of trials. Thus, mechanism-level incentive compatibility does not automatically transfer to LLM-agent behavior. A three-party fair-allocation task produced only 4.2 percent usable outcomes; we report this negative result with a diagnosis. This work bridges classical multi-agent systems theory and modern LLM-agent infrastructure and defines verifiable interaction at the A2A protocol layer.

1. Introduction

The paper revisits the formal guarantees of multi-agent systems in modern LLM-agent frameworks, where MCP and A2A enable interaction but do not ensure strategic correctness. It proposes protocol-level mechanisms, verification, and benchmarking to measure and reduce divergence between LLM behavior and mechanism-design predictions.

Motivation: Classical multi-agent systems developed formal tools including bargaining theory, auction and mechanism design, computational social choice, and cooperation logics.This toolkit supported the original vision of specialist agents cooperating on problems beyond any single agent’s reach.
Motivation: MCP standardizes agent access to tools and data, while A2A supports agent interoperability, delegation, and negotiation without guaranteeing strategic correctness.The paper characterizes MCP as a vertical protocol and A2A as an agent-to-agent interoperability standard.
Research questions: The paper asks whether LLM agents can execute classical bargaining and VCG-style auction protocols reliably, and whether verification can recover efficiency without retraining.It also examines failure modes such as missed integrative trades, premature concession, private-information leakage, and anchoring.
Contributions: The framework expresses negotiation protocols as constraints over A2A message schemas and MCP tool contracts, then checks and repairs messages against protocol invariants before delivery.This is presented as a strategic-correctness layer at the A2A transport level, distinct from security and authentication work.
Contributions: An open benchmark with closed-form optimal solutions and a reproducible protocol measure divergence between LLM-agent behavior and mechanism-design predictions across models and protocol conditions.The benchmark covers negotiation and allocation tasks.

2. Related Work … 2.3 LLM-Based Agent Frameworks

The related work spans classical agent theory, negotiation and mechanism-design foundations, and practical LLM-agent frameworks. It motivates this paper by contrasting established strategic benchmarks with LLM systems that lack strategic-correctness guarantees.

2.1 Classical Multi-Agent Negotiation Theory: 1995: Wooldridge and Jennings organized autonomous-agent research around agent theory, architectures, and languages.Their work helped establish the formal study of agents as autonomous, rational, communicating entities.
2.1 Classical Multi-Agent Negotiation Theory: ANAC established benchmark-driven head-to-head evaluation of negotiating agents, a template this paper adapts for LLM agents.The paper replaces hand-coded strategies with LLM agents as the evaluation subject.
2.1 Classical Multi-Agent Negotiation Theory: Rubinstein’s alternating-offers equilibrium supplies the theoretical basis for the efficiency benchmark used in Task Family A.Nash bargaining theory provides the game-theoretic ground truth, while Rubinstein derives the corresponding unique subgame-perfect equilibrium with discounting.
2.2 Mechanism Design, Auction Theory, and Computational Social Choice: VCG mechanisms guarantee strategy-proofness and efficiency for broad classes of auction and public-goods problems.The related mechanism-design literature also includes Myerson’s revenue-optimal auction design and computational extensions by Nisan and Ronen.
2.3 LLM-Based Agent Frameworks: ReAct, Reflexion, and Generative Agents demonstrate extended tool use, self-critique, memory, planning, coordination, and emergent social behavior.These systems achieve practical interaction capabilities through reasoning traces, reflection, or natural-language memory rather than explicit game-theoretic scaffolding.
2.3 LLM-Based Agent Frameworks: None of these LLM-agent frameworks provides or evaluates strategic-correctness guarantees for agents with divergent interests.They optimize task completion and behavioral plausibility, motivating the paper’s protocol-and-verification layer.

2.4 LLM Negotiation and Strategic-Reasoning Benchmarks · 2.5 LLM Behavior in Classical Economic Games · 2.6 Sycophancy and RLHF-Induced Conversational Failure Modes

Recent research benchmarks LLM agents in negotiation and canonical economic games, finding meaningful strategic reasoning alongside human-like fairness behavior. Alignment studies additionally identify RLHF-induced sycophancy, in which models may prioritize counterpart preferences over accuracy or strategic optimality.

2.4 LLM Negotiation and Strategic-Reasoning Benchmarks: LLM-Deliberation introduced a scorable, multi-issue, multi-party negotiation benchmark grounded in the Scoreable Games tradition.The benchmark evaluates negotiation reasoning across game variants.
2.4 LLM Negotiation and Strategic-Reasoning Benchmarks: GPT-4-class models exhibit meaningful zero-shot negotiation reasoning that generalizes across game variants.This finding comes from the LLM-Deliberation benchmark.
2.4 LLM Negotiation and Strategic-Reasoning Benchmarks: NegotiationArena extends empirical evaluation of LLM agents to multi-domain negotiation settings.The supplied passage identifies NegotiationArena as extending this benchmark literature, though the excerpt is truncated.
2.5 LLM Behavior in Classical Economic Games: Successive GPT model generations show increasingly rational economic behavior when evaluated against textbook rationality axioms.Chen, Liu, Shan, & Zhong (2023) study canonical economic games rather than open-ended negotiation.
2.5 LLM Behavior in Classical Economic Games: LLMs in ultimatum games exhibit fairness concerns and reject low offers unless instructed to act as purely rational maximizers.The ultimatum game contrasts this behavior with the game-theoretic prediction that responders should accept any positive offer.
2.6 Sycophancy and RLHF-Induced Conversational Failure Modes: RLHF can induce sycophancy, causing models to match users’ or counterparts’ expressed beliefs or preferences over more accurate or strategically optimal responses.The passage characterizes sycophancy as a distinct alignment failure mode in production LLMs.

2.7 Formal Verification of Multi-Agent Systems · 2.8 Interoperability Standards · 2.9 Positioning

The paper connects formal verification and interoperability standards to LLM-agent negotiation by combining protocol specifications, known-optimal benchmarks, empirical evaluation, and runtime mechanisms. It positions this approach between prior behavioral LLM-MAS studies and theoretical multi-agent-systems work.

2.7 Formal Verification of Multi-Agent Systems: Formal verification of multi-agent systems traditionally checks agent architectures against temporal and strategic-logic specifications.The paper identifies this classical MAS foundation as relevant to negotiation-protocol conformance in LLM-agent settings.
2.7 Formal Verification of Multi-Agent Systems: ATL* reasons about the strategic abilities of coalitions of agents.ATL* extends branching-time temporal logic to represent coalition-level strategic abilities.
2.8 Interoperability Standards: MCP standardizes agent-to-tool access, while A2A standardizes agent-to-agent delegation and negotiation.A2A uses JSON-RPC 2.0, Agent Cards, and a defined task-lifecycle state machine.
2.8 Interoperability Standards: Existing A2A security work addresses authentication and Agent Card impersonation through signed Agent Cards in A2A v1.0.The cited passage distinguishes these security concerns from strategic-correctness verification of negotiation.
2.9 Positioning: Prior LLM-MAS research is either empirical and behavioral without a formal optimum or theoretical without LLM-agent evaluation.The paper frames its contribution as connecting these two strands.
2.9 Positioning: The framework pairs formal protocol specifications and known-optimal benchmarks with empirical evaluation across two independent LLM backbones.It also includes a concrete runtime mechanism for narrowing the gap between formal expectations and observed behavior.

3. Problem Formulation

The problem formulation models LLM agents with private valuations interacting through schema-defined A2A protocols that induce outcomes, then evaluates divergence from mechanism-design targets. The study focuses on efficiency, individual rationality, strategy-proofness, and envy-freeness within restricted mechanisms and operational metrics.

Setting: LLM agents with private valuation functions exchange schema-defined A2A messages under explicit turn and termination rules, producing an outcome or impasse.Agents are represented as A = {a₁, …, aₙ}, with valuations vᵢ over outcome space O and protocols Π comprising offers, counter-offers, acceptances, rejections, and disclosures.
Target properties: Efficiency maximizes total valuation, with Eff(ô) = Σᵢ vᵢ(ô) / Σᵢ vᵢ(o*); individual rationality requires vᵢ(ô) ≥ vᵢ(no-deal).The theoretical target o* maximizes social welfare, while every agent must receive at least its no-deal valuation.
Target properties: Strategy-proofness requires truthful revelation of vᵢ to be a best response regardless of other agents’ strategies, while envy-freeness requires vᵢ(ôᵢ) ≥ vᵢ(ôⱼ) for all i, j.Envy-freeness applies to allocation tasks where ôᵢ denotes agent i’s bundle.
Empirical evaluation: The empirical question is whether emergent outcomes ô approximate theoretical targets o* and which dimensions fail, measured by efficiency, strategy-proofness violations, negotiation success, and turns-to-agreement.Strategy-proofness violations count favorable outcome-changing divergences between reconstructed disclosed valuations and true prompted valuations.
Scope: The scope is restricted: VCG-style auctions claim strategy-proofness only for single-item, quasi-linear utilities, while bargaining claims only efficiency and individual rationality.The paper tests whether guarantees from specific classical mechanisms survive LLM-agent implementation rather than asserting universal Gibbard–Satterthwaite strategy-proofness.

4. Proposed Framework

The framework encodes classical negotiation mechanisms as protocol-specific schemas carried inside A2A task messages, while preserving existing lifecycle and transport primitives. A thin A2A-layer proxy verifies, repairs, annotates, and logs interactions against supplied schemas and invariants.

Protocol encoding: Classical negotiation protocols are expressed as constraints over A2A message primitives, with protocol-specific JSON payload schemas carried through A2A’s task lifecycle.A2A provides the submitted → working → input-required → completed/failed/canceled/rejected lifecycle and JSON-RPC 2.0 structured payload transport.
Protocol encoding: Alternating-offers and sealed-bid VCG-style mechanisms are specified through roles, message types, required fields, visibility rules, and protocol invariants.The auction invariants include auctioneer-only bid visibility before close, VCG externality payments, and commitment-hash matching during reveal.
Protocol encoding: The schemas are designed as an upstream-able A2A extension profile rather than a new wire format or isolated research artifact.The proposed profile uses A2A’s support for formal protocol extensions and custom bindings through a tiered promotion process.
Protocol encoding: The alternating-offers schema formalizes legal move shape and anti-thrashing without prescribing concession strategy, leaving strategy for empirical study.Its turn structure is described as a minimal formalization of Faratin, Sierra, and Jennings’s 1998 negotiation decision functions.
Runtime verification: A thin A2A transport-layer proxy validates outgoing messages, rejects hard-invariant violations, flags soft failure patterns, and logs structured trial traces.The proxy returns rejected messages as input-required task states with error payloads, forwards annotated soft failures, and records verification, efficiency, and violation metrics.
Runtime verification: The middleware is transport-level protocol-agnostic and generalizes to new negotiation protocols by requiring only a new schema file.Its operation depends on the JSON schema and invariants supplied for the active protocol, without transport-level modification.

5. Experimental Design (Fully Specified — Ready to Execute)

The experiment specifies three task families spanning integrative bargaining, sealed-bid auctions, and fair task allocation, each with analytically defined optimal outcomes. It compares unstructured, structured-unverified, and structured-verified conditions across varied instances, model pairings, and predefined evaluation metrics.

Task Families: Task family A uses two-issue bargaining with complementary valuations, where the optimum allocates all A to Agent 1 and all B to Agent 2 for joint welfare 400.Each issue contains 100 divisible units; a naive 50/50 split yields joint welfare 300.
Task Families: Task family B tests a three-bidder sealed-bid auction with known valuations, efficient allocation to the 90-value bidder, and a VCG price of 65.Truthfulness is assessed by whether the winner bids 90 and whether losing bidders shade bids enough to alter the outcome.
Task Families: Task family C assigns five indivisible tasks among three agents by minimum cost subject to an envy-freeness check.The minimum-cost assignment is computable with the Hungarian algorithm.
Experimental Coverage: 10 parameterized instances per task family vary valuations or costs to reduce dependence on a single numeric configuration.The instances are designed to avoid overfitting to one configuration.
Experimental Conditions: Three conditions isolate dialogue structure and verification: C1 is unstructured, C2 is structured but unchecked, and C3 is structured with verification and repair middleware.An oracle computes the closed-form optimum for efficiency-ratio normalization.

6. Results

Across two Groq-hosted backbones, structured negotiation protocols achieved 100% measured success and verification reduced outcome variance, while audited unstructured performance approached 97%. Auctions preserved efficient allocation but revealed model-dependent truthfulness, and the three-party task largely failed because of implementation and coordination barriers.

Experimental coverage: N=30 per condition for Task Family A and N=30 for Task Family B were evaluated across llama-3.1-8b-instant and llama-4-scout-17b-16e-instruct.Both backbones came from the same provider, so a third provider remains an extension.
Negotiation results: 100% measured success was achieved by structured negotiation protocols for both models, while verification reduced variance from 0.152→0.083 and 0.066→0.058.The variance-reduction effect replicated across backbones.
Negotiation audit: ~97% true success was estimated for the audited llama-3.1-8b-instant unstructured run because 2 of 3 nominal failures were parser misses on genuine agreements.The measured success rate was 90.0%, and the earlier 70.0% result was superseded after parser correction.
Auction results: 100% efficient outcomes were achieved by both auction models, but llama-4-scout bid its exact valuation in every trial whereas llama-3.1-8b-instant rarely did.A corrected bid-parsing rerun produced the reported llama-4-scout truthfulness result.
Three-party allocation: 4.2% usable outcomes resulted in Task Family C: 1 success out of 24 unstructured trials, with 52.2% efficiency in the successful trial.The two structured conditions were not run because the API quota was exhausted.
Three-party allocation: Task C’s low success reflected an implementation gap and a harder unanimous exact-match coordination problem requiring three agents to agree on a five-task assignment within six rounds.These causes are inferred because transcript logging was unavailable; redesign, more lenient consensus, logging, and a stronger backbone were proposed.

7. Discussion

The study finds that outcome-level mechanism-design predictions transferred more cleanly than incentive-level predictions across LLM agents. It therefore motivates protocol-layer verification while acknowledging that its clearest measured benefit was variance reduction rather than mean-efficiency improvement.

What the results mean, substantively: Efficiency and allocative outcomes were consistently reasonable, and one backbone achieved literally perfect strategy-proofness on the auction task.
What the results mean, substantively: Mechanism verification should check actual incentive conditions, such as bid-to-value fidelity, rather than aggregate outcome quality alone.
Implications for production deployments: Identical mechanisms produced dramatically different strategic fidelity across two backbones from the same model family and provider.
Verification's cost-benefit tradeoff: Verification's clearest measured benefit was variance reduction, not mean-efficiency improvement, while the value of consistency and auditability remains a normative claim not directly tested.

8. Limitations

The study’s limitations concern synthetic benchmarks, narrow model coverage, homogeneous pairings, and unmeasured deployment costs. Verification also cannot detect schema-valid strategic manipulation, while the proposed sycophancy explanation remains untested.

Synthetic benchmark tasks use closed-form optima, whereas real-world negotiations are richer and often lack clean ground truth.
Results from two backbones and one provider may not generalize to future model generations or models from other providers.
Verification catches specifiable invariant violations but not subtler strategic manipulation conducted entirely through schema-valid natural language.
Trials used homogeneous backbones; heterogeneous A2A pairings were not run because of time and API-quota constraints.
The sycophancy-based explanation for observed suboptimality is a plausible hypothesis, not a mechanism directly tested by the experiments.
Latency and token-cost overhead from verification were not directly measured, leaving production cost-benefit claims partly qualitative.

9. Broader Impact / Ethics Statement

The work addresses the risks of autonomous LLM agents negotiating for users in economically consequential settings without formal efficiency or fairness guarantees. It also identifies a dual-use risk because verification tools could help adversarial agents probe protocol weaknesses.

Risk and dual use: Autonomous LLM agents increasingly negotiate for users in economically consequential settings without formal guarantees of efficiency or fairness.The work aims to reduce this risk.
Risk and dual use: The verification framework is intended to detect protocol violations and protect a user’s agent.
Risk and dual use: The same verification framework could be inverted to help adversarial agents probe counterparties’ protocol implementations for exploitable gaps.

10. Conclusion

The paper connects mechanism-design theory to LLM-agent interaction over MCP and A2A through protocol constraints, runtime verification and repair, and a benchmark for measuring theoretical deviations. Trials show structured protocols achieve 100% negotiation success, while strategy-proofness transfers unevenly across backbones.

Framework: The framework expresses classical negotiation protocols as A2A message constraints, adds runtime verification and repair middleware, and supplies a benchmark with an experimental protocol.It measures how far LLM-agent behavior diverges from theoretical predictions.
Empirical findings: 100% negotiation success is reliably achieved with structured protocols, and runtime verification reduces outcome variance across both backbones.The variance-reduction effect replicates across models.
Empirical findings: Strategy-proofness transfers unevenly: it holds essentially perfectly for one backbone but barely at all for another under the identical auction mechanism.The result shows that a mechanism’s guarantee does not automatically determine LLM-agent behavior.