1 Introduction↩︎

Large language models now power autonomous agents that operate in high-stakes negotiation settings, including insurance pricing, procurement contracts, and financial services. These systems act on behalf of users whose private constraints such as maximum budgets or reservation values must remain confidential throughout the negotiation process. Existing defenses leverage cryptographic primitives — including computation sharing protocols, proof-of-knowledge schemes, and lattice-based encryption — to prevent direct exposure of constraint values to opposing parties.

However, cryptographic protection of explicit data does not address a more subtle threat: the negotiation behavior itself constitutes a side channel. An agent’s offer sequence, concession trajectory, response timing, and convergence speed are all observable by the counterparty, and together they form a rich behavioral trace from which private constraints can be inferred even when the underlying data is cryptographically protected.

Consider a concrete example. Alice employs an autonomous agent to negotiate a health insurance premium, with a private budget of $3,000. The agent is configured with a zero-knowledge proof preventing the insurer from learning her budget directly. Nevertheless, the agent opens at $2,600, advances to $2,850 in the second round, and reaches $2,950 in the third. The accelerating concession pattern - large early moves tapering toward a sharp plateau - reveals to a sophisticated counterparty that Alice’s true budget is close to $3,000. No cryptographic mechanism prevents this inference: the information leaks through the structure of the behavior, not through any disclosed value.

This class of vulnerability which we term behavioral privacy leakage has not been formally studied in sequential negotiation systems. Prior work on privacy-preserving negotiation focuses exclusively on protecting explicit constraint data, leaving the behavioral side channel unaddressed. Meanwhile, the differential privacy literature, which provides strong formal guarantees against statistical inference, was developed for static database settings and does not transfer directly to multi-round strategic interactions where convergence and utility must also be preserved.

This paper closes that gap. We formalize behavioral differential privacy for sequential negotiation agents, develop a mechanism that provably satisfies \((\varepsilon, \delta)\)-differential privacy over observable negotiation traces, and prove that the mechanism converges almost surely while preserving high negotiation utility.

1.0.0.1 Contributions.

This work makes four key contributions:

1. Formalization. We introduce the first rigorous formalization of behavioral differential privacy adapted to sequential negotiation: a constraint-space adjacency structure that captures budget proximity, paired with \((\varepsilon, \delta)\)-DP guarantees over the distribution of observable offer sequences.

2. Mechanism. An adaptive randomized negotiation policy with a safety critic that calibrates noise to the negotiation phase, preserves feasibility at each round, and satisfies differential privacy via the post-processing theorem.

3. Theoretical guarantees. Formal proofs that the mechanism achieves \((\varepsilon, \delta)\)-DP under a public-proxy clipping assumption, that the offer sequence converges almost surely, and that the mechanism incurs at most \(O(\sigma_{\max}^2)\) Nash surplus loss relative to the deterministic baseline, where \(\sigma_{\max}\) governs the privacy-utility tradeoff.

4. Empirical validation. Evaluation on 3,000 synthetic bilateral negotiations generated from the proposed model. The mechanism reduces adversarial inference accuracy by 43–50% relative to a non-private baseline, while maintaining or slightly improving non-private utility and achieving a 90.4% negotiation success rate.

2 Related Work↩︎

2.1 Autonomous Negotiation Agents↩︎

Recent advances in foundation models have enabled increasingly capable autonomous agents [1], [2]. Multi-agent frameworks such as MetaGPT [3] and CAMEL [4] demonstrate sophisticated collaborative reasoning, and LLM-based negotiators [5], [6] exhibit strategic behavior in bilateral settings. However, none of these systems mitigate the privacy risks arising from observable negotiation behavior. Our work is the first to address this gap.

2.2 Cryptographic Privacy in Negotiation↩︎

Cryptographic techniques — secure multi-party computation (MPC) [7], [8], zero-knowledge proof systems [8]–[10], and fully homomorphic encryption [11], [12] — are employed to prevent the leakage of the agents’ actual negotiation constraints. In this way, an agent’s private reservation value cannot be deduced from any of the values that are revealed during the negotiation. They do not, however, prevent inference from how an agent behaves: concession trajectories, response timing, and convergence patterns remain fully observable and carry substantial information about hidden constraints. Our approach is complementary — it targets the behavioral side channel that persists even under full cryptographic protection. Concurrently, [13] proposes a device-native negotiation architecture using zero-knowledge proofs, but identifies behavioral inference attacks as an open problem and defers randomized concession schedules to future work.

2.3 Differential Privacy↩︎

Differential privacy (DP) [14]–[16] provides rigorous statistical guarantees via calibrated noise mechanisms, including the Laplace mechanism [14] and composition theorems [17], [18]. DP has been successfully applied to machine learning via DP-SGD [19], PATE [20], and federated learning [21], [22]. These formulations, however, are designed for static database or training settings. Applying DP to sequential strategic interactions introduces new challenges: the adjacency relation must be defined over constraint spaces rather than datasets, and the mechanism must preserve both convergence and negotiation utility across multiple rounds. We address these challenges directly.

2.4 Side-Channel Attacks and Behavioral Leakage↩︎

Membership inference [23], [24], model inversion [25], [26], attribute inference [27], and training data extraction [28], [29] demonstrate that ML systems leak private information through observable outputs. Timing attacks [30], [31] and power analysis [32] show that implementation behavior constitutes an independent leakage channel. Recent work [33]–[35] demonstrates behavioral leakage in AI systems broadly, but does not formalize inference attacks over sequential negotiation traces or provide convergence-preserving defenses. Related work evaluates contextual privacy leakage in collaborative LLM agents [36], but addresses voluntary over-disclosure between agents rather than adversarial inference of private constraints from offer trajectories.

2.5 Game-Theoretic Foundations↩︎

Nash bargaining [37] and Rubinstein’s alternating-offers model [38] establish the theoretical foundations for rational bilateral negotiation. Mechanism design [39], [40] studies incentive-compatible protocol construction. Our work builds on these foundations but asks a distinct question: how should a rational agent randomize its strategy to prevent private constraint inference, while preserving the game-theoretic properties that guarantee agreement?

2.6 The Gap This Work Fills↩︎

Table 1 summarizes the landscape. No prior work simultaneously (i) formalizes a DP adjacency relation over negotiation constraint spaces, (ii) provides convergence guarantees under randomization, and (iii) validates against adversarial inference models on synthetic bilateral negotiation simulations. Concurrent work [13] identifies the behavioral side channel as an open problem but does not formalize or solve it. This paper addresses all three.

3 Threat Model↩︎

We consider a passive external adversary who observes the full sequence of messages exchanged during a negotiation but does not participate in or interfere with the negotiation process.

3.1 Adversary Capabilities↩︎

The adversary has access to the complete observable negotiation trace \(\tau = (o_1, o_2, \ldots, o_T)\), where each \(o_t\) denotes the offer made at round \(t\). Specifically, the adversary observes:

• The sequence of offers: \((o_1, o_2, \ldots, o_T)\)

• Inter-round timing intervals: \((\Delta t_1, \Delta t_2, \ldots, \Delta t_{T-1})\)

• The final agreed value and outcome

• The total number of rounds to convergence

The adversary does not observe the agent’s private constraint \(\theta\) (e.g., maximum budget) directly. Using a dataset of historical negotiations, the adversary trains a predictive model \(\mathcal{A}: \tau \mapsto \hat{\theta}\) to infer \(\theta\) from observable traces. We evaluate against three adversary instantiations: gradient-boosted trees (XGBoost), random forests, and neural networks.

3.2 Privacy Goal↩︎

The core privacy objective is to prevent a counterparty from reliably inferring the agent’s private constraint \(\theta\) by observing its negotiation behavior. Formally, we require that any two constraint values \(\theta, \theta'\) satisfying the adjacency condition \(|\theta - \theta'| \leq \Delta\) produce statistically indistinguishable offer sequences. Specifically, the randomized mechanism \(\mathcal{M}\) must satisfy \((\varepsilon, \delta)\)-differential privacy over observable traces: \[\Pr[\mathcal{M}(\theta) \in S] \leq e^{\varepsilon} \cdot \Pr[\mathcal{M}(\theta') \in S] + \delta\] for all measurable output sets \(S\). Behavioral DP is thus an application of standard \((\varepsilon, \delta)\)-differential privacy with a novel adjacency relation defined over the constraint space \(\Theta\) rather than over datasets, applied to the distribution of observable offer sequences rather than to a static query response.

3.3 Utility Goals↩︎

Privacy protection must not come at the cost of negotiation effectiveness. We require:

• Negotiation success rate \(\geq 90\%\)

• Nash surplus (defined as \(\text{NS} = o_T / \theta\), the ratio of the final agreed value to the agent’s private constraint) preserved at \(\geq 90\%\) of the deterministic baseline

• Convergence time \(\leq 1.5\times\) the deterministic baseline

3.4 Leakage Taxonomy↩︎

We identify four categories of behavioral leakage in negotiation traces:

1. Temporal leakage. Response timing and round duration reveal urgency and constraint proximity.

2. Trajectory leakage. The shape of the concession path (linear, concave, convex) encodes the agent’s distance from its reservation value.

3. Concession leakage. The magnitude and rate of concessions directly signal the gap between current offer and private budget.

4. Convergence leakage. The number of rounds and the pattern of offer stabilization reveal the tightness of private constraints.

We note that this work focuses on a passive adversary that observes negotiation traces without influencing the interaction. In practice, stronger adversaries may actively adapt their negotiation strategy to probe private constraints or exploit repeated interactions across multiple negotiations. Extending behavioral differential privacy guarantees to such active or adaptive adversaries is an important direction for future work.

4 Methodology↩︎

4.1 Problem Formulation↩︎

Let \(\theta \in \Theta\) denote the agent’s private constraint (e.g., maximum budget), and let \(\tau = (o_1, o_2, \ldots, o_T)\) denote the observable negotiation trace produced by policy \(\pi_\theta\). We seek a randomized policy \(\mathcal{M}\) such that:

1. \(\mathcal{M}\) satisfies \((\varepsilon, \delta)\)-differential privacy over observable traces

2. \(\mathcal{M}\)’s offer sequence converges almost surely (reaching agreement when the counterparty’s reservation value permits)

3. \(\mathcal{M}\) preserves high negotiation utility relative to the deterministic baseline

4.2 Deterministic Baseline Policy↩︎

The deterministic baseline policy \(\pi^*\) follows a concession function of the form:

\[o_t = o_1 + (\theta - o_1) \cdot \left(\frac{t}{T}\right)^\alpha\]

where \(o_1\) is the opening offer, \(T\) is the maximum number of rounds, and \(\alpha > 0\) controls concession speed. Here \(t\) increases from \(1\) to \(T\), so the agent opens below \(\theta\) and concedes monotonically toward it as \(t \to T\); at \(t = T\) the offer reaches \(\theta\), representing full concession to the private constraint. This policy is optimal in expectation but fully reveals \(\theta\) through its concession trajectory, motivating our privacy mechanism.

4.3 Adaptive Noise Schedule↩︎

The core of our mechanism is an adaptive noise schedule that calibrates the magnitude of randomization to the negotiation phase. The phase-adaptive noise parameter \(\sigma_t\) is defined as:

\[\sigma_t = \sigma_{\max} \cdot \left(1 - \frac{t}{T}\right)^\beta\]

where \(\sigma_{\max}\) sets the peak randomization level and \(\beta > 0\) controls the decay of noise with time. At round \(t\), the randomized offer is then:

\[\tilde{o}_t = o_t + \eta_t, \quad \eta_t \sim \mathcal{N}(0, \sigma_t^2)\]

Crucially, perturbation is concentrated in the opening rounds, where offer trajectories are most diagnostic of private constraints, and tapers off near convergence to protect negotiation utility when agreement is imminent.

4.4 Safety Critic↩︎

The addition of noise may produce offers that violate feasibility constraints (e.g., offers exceeding the agent’s true budget \(\theta\)). The safety critic applies a deterministic post-processing step to enforce feasibility at each round: \[o_t^{\text{safe}} = \text{clip}(\tilde{o}_t,\;o_{\min},\;\theta)\] where \(o_{\min}\) is the minimum acceptable offer. Because clipping is a deterministic function applied downstream of the noisy draw, privacy guarantee carries through unchanged, a direct consequence of the post-processing theorem [15]. We note that clipping to the private constraint \(\theta\) may itself constitute a leakage channel in extreme cases, as the ceiling on observed offers can reveal the constraint to a careful adversary; this is acknowledged in Section 7.3, and clipping to a public proxy value \(\bar{\theta} \geq \theta\) is identified as a direction for future work.

4.5 Privacy Analysis↩︎

The stochastic mechanism \(\mathcal{M}\) achieves \((\varepsilon, \delta)\)-DP with respect to the measurable space of observable traces. Round-wise privacy costs are aggregated through sequential composition: \[\varepsilon_{\text{total}} = \sum_{t=1}^{T} \varepsilon_t, \quad \delta_{\text{total}} = \sum_{t=1}^{T} \delta_t\] The per-round privacy budget \(\varepsilon_t\) is determined by the noise magnitude \(\sigma_t\) and the sensitivity \(\Delta = \max_{\theta, \theta'} |o_t(\theta) - o_t(\theta')|\) of the offer function: \[\varepsilon_t = \frac{\Delta}{\sigma_t}\] For the Gaussian mechanism, \(\varepsilon_t\) and \(\delta_t\) satisfy \(\sigma_t \geq \Delta\sqrt{2\ln(1.25/\delta_t)}/\varepsilon_t\); we use \(\varepsilon_t = \Delta/\sigma_t\) as a conservative approximation following [15]. Note that as \(t \to T\), \(\sigma_t \to 0\) and the per-round cost \(\varepsilon_t = \Delta/\sigma_t\) grows unbounded under naive composition; we address this via the Advanced Composition Theorem [17], which yields a tighter bound of \(\varepsilon_{\text{total}} \leq \sqrt{2T \ln(1/\delta)}\,\varepsilon_0 + T\varepsilon_0^2\).

4.6 Algorithm↩︎

4.7 Multi-Issue Extension↩︎

While the current formulation addresses single-issue bilateral negotiation, the framework extends naturally to multi-attribute settings where the agent negotiates price, delivery time, and warranty simultaneously. In such settings, the noise vector \(\boldsymbol{\eta}_t \sim \mathcal{N}(\mathbf{0}, \Sigma_t)\) is drawn from a multivariate Gaussian with covariance matrix \(\Sigma_t\) calibrated to the sensitivity of each attribute. Formal analysis of multi-issue behavioral DP, including cross-attribute privacy leakage and joint convergence guarantees, is left as future work.

5 Experimental Evaluation↩︎

5.1 Experimental Setup↩︎

Empirical assessment of the mechanism uses the dataset described below:

• Simulated negotiations: 3,000 synthetic bilateral negotiations generated using the deterministic baseline policy with private constraints \(\theta\) sampled uniformly from \([\$2,000, \$8,000]\).

We generate synthetic negotiation data based on parameter distributions that reflect real-world negotiations as found in prior literature [41], including concession behavior, bounded rationality and temporal dynamics. The patterns found in the offers and the negotiation’s convergence or divergence are similar to those observed in real-world bilateral negotiations, such as in procurement and insurance settings.

While large-scale real-world negotiation datasets are limited due to confidentiality concerns, our simulation framework captures the key behavioral characteristics necessary to evaluate inference attacks over negotiation traces.

We split the dataset 80/20 for adversary training and evaluation. The privacy mechanism is evaluated across five privacy budget settings: \(\varepsilon \in \{0.1, 0.5, 1.0, 2.0, 5.0\}\). The global sensitivity is set to \(\Delta = 1.0\), corresponding to a unit adjacency bound on the private constraint space.

5.2 Adversary Models↩︎

We evaluate against three adversary instantiations, each trained on \(N = 2,000\) negotiations:

• XGBoost: Gradient-boosted trees with 100 estimators and maximum depth 6.

• Random Forest: Ensemble of 100 decision trees with bootstrap sampling.

• Neural Network: Three-layer feedforward network with ReLU activations, hidden dimensions [128, 64, 32], trained with Adam optimizer.

Each adversary is trained on traces from deterministic baseline negotiations and evaluated on traces from the randomized mechanism. This setting models a realistic deployment scenario in which the privacy mechanism is newly introduced against an adversary specialized for the unmodified protocol. To close the train/test distribution gap, we additionally evaluate in Section 5.7 an adaptive adversary that updates its inference model under the randomized mechanism via meta-learning.

5.3 Privacy Results↩︎

Table 2 reports adversarial inference accuracy under the deterministic baseline and the randomized mechanism with \(\sigma_{\max} = 0.25\).

The randomized mechanism reduces adversarial inference accuracy by 43.2% against XGBoost, 43.1% against Random Forest, and 50.5% against Neural Network. The consistent reduction across all three adversary types demonstrates that the privacy guarantee is robust to the choice of inference model. For reference, a naïve baseline predicting the mean constraint value (\(\hat{\theta} = 0.5\) in normalized space) achieves approximately 10% accuracy under the tolerance-based evaluation criterion (\(|\hat{\theta} - \theta| < 0.05\)) used here, confirming that even the non-private adversary accuracy of \(\sim\)​83% reflects genuine inference from behavioral traces rather than distributional guessing.

5.4 Utility Results↩︎

Table 3 reports negotiation utility metrics under both policies.

Our randomized mechanism achieves a Nash surplus slightly above that of our deterministic baseline (0.908 compared to 0.890), due to a combination of phase-adaptive noise sometimes improving early-round offer positions, and safety critics that prevent very large upward improvements while preserving large downward improvements, together inducing an asymmetric but slightly positive benefit in the agreed value in the late rounds.

Consequently, the randomized mechanism matches or slightly exceeds the non-private Nash surplus (a result of the asymmetric clipping described above), while achieving a negotiation success rate of 90.4%. This satisfies the utility goal of \(\geq 90\%\) success rate defined in Section 3. As illustrated in Fig. 3, the average convergence time increases by a factor of \(1.43\times\) as compared with that of the deterministic version. For reference, this is less than \(1.5\times\), as dictated by our utilities.

5.5 Privacy-Utility Tradeoff↩︎

We then investigate the privacy-utility tradeoff for various noise levels. Figure 2 reveals the anticipated inverse relationship: as \(\sigma_{\max}\) grows, adversarial constraint-inference accuracy falls steadily while Nash surplus remains largely intact. Across all evaluated configurations, we identified the \(\sigma\) value that maximizes privacy gain — achieving a 43–50% reduction in inference accuracy — subject to the constraint that negotiation utility does not fall below the non-private baseline. The setting \(\sigma_{\max} = 0.25\) yields the best balance between these two competing objectives. The monotonic increase in Nash surplus with \(\sigma_{\max}\) is a consequence of the asymmetric clipping described in Section 4.4, where the safety critic systematically preserves downward offer improvements while bounding upward deviations.

5.6 Ablation Study↩︎

Table 4 reports the effect of varying \(\sigma_{\max}\) on privacy and utility metrics.

Note that inference accuracy in Table 4 reports the average across all three adversary models (XGBoost, Random Forest, Neural Network), whereas Table 2 reports per-adversary accuracy. The average of per-adversary values at \(\sigma_{\max} = 0.25\) is consistent with the ablation result. The slight discrepancy in success rate between Table 3 (90.4%) and Table 4 (91.8%) at \(\sigma_{\max} = 0.25\) reflects variance across independent random seeds; both values satisfy the \(\geq 90\%\) utility goal defined in Section 3.

5.7 Adaptive Adversary↩︎

We evaluate robustness against an adaptive adversary that employs meta-learning to adapt its inference strategy to the randomized mechanism. This adaptive adversary improves inference accuracy by only 1.6% compared to the standard neural network adversary (34.1% vs 32.5%). We show that our solution achieves strong privacy guarantees even in the presence of adversaries who adapt to the scheme.

6 Theoretical Guarantees↩︎

6.1 Differential Privacy Guarantee↩︎

Intuition. The mechanism injects calibrated Gaussian noise at each negotiation round, ensuring that small changes in the agent’s private constraint result in only limited changes in the distribution of observable negotiation traces. Assume the safety critic clips offers to a public proxy ceiling \(\bar{\theta} \geq \theta\) rather than to the private constraint \(\theta\) itself. Then the randomized negotiation mechanism \(\mathcal{M}\) with adaptive noise schedule \(\sigma_t = \sigma_{\max} \cdot (1 - t/T)^\beta\) satisfies \((\varepsilon_{\text{total}}, \delta_{\text{total}})\)-differential privacy over observable negotiation traces, where \(\varepsilon_{\text{total}} = \sum_{t=1}^{T} \frac{\Delta}{\sigma_t}\) and \(\delta_{\text{total}} = \sum_{t=1}^{T} \delta_t\) (see Eq. (6)).

Remark (Scope of Theorem 1). Our experiments clip to the private constraint \(\theta\) for direct comparability with the deterministic baseline, and the empirical privacy goals are met under this configuration (Sec. 5.3, 5.7). Tight formal end-to-end accounting under private-\(\theta\) clipping requires a refined adjacency analysis that accounts for the leakage discussed in Sec. 7.3 and is left to future work; replacing private-\(\theta\) clipping with public-proxy clipping closes this gap and is identified as the recommended deployment configuration.

Remark (Practical Floor on \(\sigma_t\)). The formal certificate above assumes \(\sigma_t > 0\) for all \(t\). Since the schedule \(\sigma_t = \sigma_{\max}(1 - t/T)^\beta\) yields \(\sigma_T = 0\) at the final round, naïve application gives \(\varepsilon_T = \Delta/\sigma_T = \infty\). In all reported experiments we therefore enforce a practical floor \(\sigma_t \geq \sigma_{\min} = 0.05\), which keeps every per-round cost finite. The evaluated setting \(T = 3\), \(\sigma_{\max} = 0.25\) operates under this floor. Tighter privacy accounting via Rényi differential privacy or zero-concentrated DP is left as future work.

6.2 Convergence Guarantee↩︎

Intuition. As noise magnitude decreases with time and feasibility enforced by the safety critic, the process behaves similarly to the deterministic baseline in later rounds and converges. Under the randomized policy \(\mathcal{M}\), the safe offer sequence \((o_t^{\text{safe}})_{t=1}^{T}\) converges almost surely to a fixed point in \([o_{\min}, \theta]\) within finite expected rounds, provided \(\sigma_{\max} < \theta - o_{\min}\). Agreement is reached whenever the counterparty’s reservation value lies within this interval; the empirical success rate of \(90.4\%\) (Sec. 5.4) reflects the fraction of negotiations in which this condition holds.

6.3 Utility Bound↩︎

Intuition. Since the added noise has bounded variance and decreases over time, it does not significantly affect the final agreed value and decreases the expected utility only slightly. The expected Nash surplus under the randomized policy \(\mathcal{M}\) satisfies:

\[\mathbb{E}[\text{NS}(\mathcal{M})] \geq \text{NS}(\pi^*) - O(\sigma_{\max}^2)\]

where \(\text{NS}(\pi^*)\) denotes the Nash surplus under the deterministic baseline policy \(\pi^*\).

Remark (Empirical Utility). Theorem 3 provides a worst-case lower bound on expected Nash surplus and does not preclude utility gains. Tables 3 and 4 show that Nash surplus rises monotonically with \(\sigma_{\max}\) in practice, a consequence of the asymmetric clipping described in Section 4.4: the safety critic systematically preserves downward offer improvements while bounding upward deviations, inducing a positive bias that exceeds the theoretical loss term for the evaluated parameter range.

6.4 Remark on Privacy Budget↩︎

We note that \(\varepsilon_{\text{total}}\) may be large in absolute value for typical parameter settings, e.g., \(T = 3\) and \(\sigma_{\max} = 0.25\). However, the \((\varepsilon, \delta)\)-DP certificate functions as a worst-case bound on leakage measured against the chosen adjacency structure. We therefore pair this formal guarantee with empirical evaluation: observed reductions in adversarial inference accuracy serve as a practical, measurable indicator of privacy protection under realistic negotiation conditions. The paper is related to recent work on empirical auditing of differential privacy in machine learning systems [42], [43], where both formal guarantees and observed inference resistance are considered important.

7 Discussion↩︎

7.1 Comparison to Cryptographic Approaches↩︎

Cryptographic privacy mechanisms and behavioral differential privacy address fundamentally different threat surfaces. Cryptographic techniques govern what information is transmitted — structurally preventing any disclosed value from revealing private constraints. Behavioral differential privacy, by contrast, targets how an agent moves through negotiation space, obfuscating the inference surface exposed by observable offer dynamics. Deployed together, the two layers achieve defense-in-depth against both direct disclosure and behavioral inference attacks.

7.2 Deployment Considerations↩︎

Our mechanism introduces three practical considerations for real-world deployment:

• Parameter selection. The choice of \(\sigma_{\max}\) and \(\beta\) involves a privacy-utility tradeoff that must be calibrated to the deployment context. High-stakes negotiations (e.g., large procurement contracts) may tolerate lower utility in exchange for stronger privacy guarantees, while time-sensitive negotiations may prioritize convergence speed.

• Counterparty awareness. If the counterparty is aware that the agent employs a randomized policy, they may adjust their strategy accordingly. Our adaptive adversary evaluation (Section 5.7) shows that even a meta-learning adversary achieves only a 1.6% improvement, suggesting the mechanism is robust to this threat.

• Computational overhead. The randomized policy adds negligible computational cost relative to the deterministic baseline — noise sampling and clipping are \(O(1)\) operations per round. By contrast, cryptographic alternatives such as MPC [7], [8] and fully homomorphic encryption [11], [12] incur per-round costs that grow polynomially in the bit-length of exchanged values, making behavioral DP substantially cheaper to deploy at scale.

7.3 When Behavioral Privacy Is Insufficient↩︎

Our mechanism provides strong privacy guarantees under the threat model defined in Section 3. However, there are settings where behavioral privacy alone is insufficient:

• Side-channel correlation. If the adversary can correlate behavioral traces across multiple negotiations involving the same agent, the accumulated information may allow inference even under randomization. Sequential composition of privacy budgets across negotiations must be carefully managed.

• External information. If the adversary has access to external information about the agent’s constraints (e.g., publicly known budget ranges for a company), behavioral privacy provides weaker guarantees as the prior distribution over \(\theta\) is already narrow.

• Extreme noise regimes. At very high noise levels (\(\sigma_{\max} \geq 1.0\)), the mechanism preserves privacy but may reduce negotiation success rates toward the 90% threshold defined in Section 3.3, leaving little margin for time-critical applications.

• Clipping boundary inference. The safety critic clips the offer to \([o_{\min}, \theta]\), where \(\theta\) is the private constraint of the seller. The clipping boundary reveals the seller’s constraint to a counterparty who observes that offers do not exceed a certain ceiling. While early rounds do introduce enough noise that it is difficult for a counterparty to guess \(\theta\) from the observed clipped values, improving the safety critic so that it clips to a public proxy value \(\bar{\theta} \geq \theta\) is an interesting open direction.

7.4 Game-Theoretic Implications↩︎

Our mechanism has an interesting game-theoretic interpretation. The noise parameter \(\sigma_{\max}\) functions as a commitment device: by publicly committing to a randomized policy, the agent signals to the counterparty that behavioral inference will be unreliable. This commitment may itself affect counterparty behavior — a rational counterparty who knows inference is noisy may adopt a more cooperative strategy, potentially improving overall negotiation outcomes. Formal analysis of the equilibrium implications of behavioral privacy commitments is left as future work.

7.5 Limitations↩︎

Several open challenges remain: (i) the formulation addresses single-issue bilateral negotiation only — extension to multi-issue and multi-party settings requires new adjacency definitions and composition analysis; (ii) the synthetic evaluation uses 3,000 simulated negotiations, and larger real-world datasets would strengthen empirical claims; (iii) \(\varepsilon_{\text{total}}\) may be large in absolute terms — tighter analysis via Rényi DP could yield stronger guarantees; (iv) the threat model assumes a passive adversary — active adversaries who probe constraints through strategic offers represent an important future direction; (v) reported metrics are point estimates; bootstrap confidence intervals (trivial with 3,000 runs) and additional baselines such as fixed-noise and Laplace mechanisms are targeted for an extended version of this work.

8 Conclusion↩︎

Autonomous agents increasingly negotiate on behalf of users in high-stakes domains, yet existing privacy defenses focus exclusively on protecting explicit constraint data through cryptographic mechanisms. This paper identifies and formalizes a complementary threat: behavioral privacy leakage, where an adversary infers private constraints from observable negotiation dynamics even under full cryptographic protection.

We presented a randomized negotiation mechanism that provably satisfies \((\varepsilon, \delta)\)-differential privacy over observable negotiation traces, while guaranteeing almost-sure convergence of the offer sequence and preserving high negotiation utility. The core technical contribution is an adaptive noise schedule that calibrates randomization to the negotiation phase, combined with a safety critic that enforces feasibility at each round via deterministic post-processing. Evaluated on 3,000 synthetic bilateral negotiations, our mechanism reduces adversarial inference accuracy by 43–50%, maintains non-private utility levels, achieves a 90.4% negotiation success rate, and is robust to adaptive adversaries with meta-learning attacks gaining only 1.6%. As autonomous agents take on increasingly consequential roles in commercial and personal negotiation, behavioral privacy will become a critical component of trustworthy AI systems.

Disclosure of Interests.↩︎

The author has no competing interests to declare that are relevant to the content of this article.

References↩︎