Skip to content

Behavioral Privacy Leakage in Agentic Negotiation: Formalizing and Mitigating Inference Attacks via Randomized Policies

🕒 Published (v1): 2026-07-07 00:00 UTC · Source: HuggingFace · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

Autonomous LLM negotiation agents leak private budget constraints through observable behavioral patterns (concession trajectories, timing, convergence speed) even when cryptographic protections guard explicit values. This paper formalizes behavioral differential privacy for sequential negotiation and introduces an adaptive randomized policy that achieves \((\varepsilon, \delta)\)-DP with provable convergence. On 3,000 synthetic bilateral negotiations, adversarial inference accuracy drops by 43–50% while negotiation success stays above 90%.

Problem

Cryptographic defenses (ZK-proofs, MPC, FHE) protect explicit constraint values in agentic negotiation but leave a behavioral side channel fully exposed: an adversary observing offer sequences, concession shapes, response timing, and convergence patterns can train ML models that infer a private budget with ~83% accuracy. No prior work formally defines a differential-privacy adjacency relation over negotiation constraint spaces or proves convergence under randomization for this setting.

Method

The mechanism replaces the deterministic concession policy \(o_t = o_1 + (\theta - o_1)\cdot(t/T)^\alpha\) with a randomized variant:

  1. Adaptive noise schedule: Per-round Gaussian noise \(\eta_t \sim \mathcal{N}(0, \sigma_t^2)\) with \(\sigma_t = \sigma_{\max}\cdot(1 - t/T)^\beta\), front-loading randomization in early rounds (where trajectories are most diagnostic) and tapering near convergence.
  2. Safety critic: Deterministic clip \(o_t^{\text{safe}} = \text{clip}(\tilde{o}_t, o_{\min}, \theta)\) enforces feasibility; privacy carries through via the post-processing theorem.
  3. Privacy accounting: Sequential composition gives \(\varepsilon_{\text{total}} = \sum_{t=1}^T \Delta/\sigma_t\); the Advanced Composition Theorem tightens this to \(\varepsilon_{\text{total}} \leq \sqrt{2T\ln(1/\delta)}\,\varepsilon_0 + T\varepsilon_0^2\).
  4. Formal DP adjacency: Defined over constraint space \(\Theta\) (budget proximity \(|\theta - \theta'| \leq \Delta\)) rather than over datasets, applied to the distribution of observable offer sequences.

Key Contributions

  • First formalization of behavioral differential privacy for sequential multi-round negotiation, with a constraint-space adjacency structure.
  • Adaptive randomized negotiation policy with a phase-calibrated noise schedule and safety critic that satisfies \((\varepsilon, \delta)\)-DP under a public-proxy clipping assumption.
  • Theorem 2: almost-sure convergence of the offer sequence via Borel-Cantelli (noise variance sum \(\sum_t \sigma_t^2 < \infty\)).
  • Theorem 3: Nash surplus lower-bounded as \(\mathbb{E}[\text{NS}(\mathcal{M})] \geq \text{NS}(\pi^*) - O(\sigma_{\max}^2)\).
  • Empirical evaluation against three adversary classes including a meta-learning adaptive adversary.

Results

  • Adversarial inference accuracy (baseline → randomized, \(\sigma_{\max}=0.25\)):
  • XGBoost: 81.7% → 38.5% (43.2% reduction)
  • Random Forest: 83.3% → 40.2% (43.1% reduction)
  • Neural Network: 83.0% → 32.5% (50.5% reduction)
  • Adaptive meta-learning adversary: only +1.6% recovery over standard NN (34.1% vs 32.5%)
  • Nash surplus: 0.908 (randomized) vs 0.890 (deterministic baseline) — slight improvement due to asymmetric clipping
  • Negotiation success rate: 90.4% (vs 97.0% deterministic baseline), meeting the \(\geq 90\%\) utility target
  • Convergence time: \(1.54\times\) baseline (below the \(1.5\times\) threshold target, per Table 3; ablation cites 1.43×)
  • Optimal operating point: \(\sigma_{\max} = 0.25\); further increasing noise (\(\sigma_{\max}=1.0\)) reduces inference accuracy to 26.5% at cost of 90.5% success rate

Limitations

  • Experiments use only synthetic data (3,000 negotiations); no real-world negotiation dataset validation due to confidentiality constraints.
  • Formal \((\varepsilon, \delta)\)-DP proof requires clipping to a public proxy \(\bar{\theta} \geq \theta\), but experiments clip to private \(\theta\), leaving a gap between formal guarantee and empirical setup.
  • Noise schedule \(\sigma_t \to 0\) at final round makes \(\varepsilon_T = \Delta/\sigma_T \to \infty\); a practical floor \(\sigma_{\min} = 0.05\) is enforced but not tightly accounted for (Rényi DP or zCDP deferred).
  • Threat model is passive adversary only; active or adaptive adversaries that probe constraints across repeated interactions are not addressed.
  • Multi-issue (multi-attribute) negotiation extension is sketched but not formally analyzed or empirically validated.
  • \(\varepsilon_{\text{total}}\) can be large in absolute value for typical parameters, limiting the strength of the formal guarantee without complementary empirical grounding.

Relevance to Agentic AI / LLM Agents

This paper directly addresses a security vulnerability unique to deployed LLM negotiation agents: the agent's strategic behavior itself constitutes a side channel that leaks user-private information regardless of data-layer protections. As LLM agents are increasingly deployed in high-stakes economic settings (procurement, insurance, financial services), behavioral privacy leakage becomes a first-class concern alongside prompt injection and tool misuse. The work introduces a formal privacy framework — differential privacy adapted to sequential strategic interaction — that could generalize to other agentic contexts where observable action sequences encode private user state (e.g., retrieval patterns, query timing, tool-call sequences). It also highlights that standard cryptographic defenses are necessary but insufficient for agentic systems that act over time.