Cooperative Bargaining Games Without Utilities: Mediated Solutions from Direction Oracles¶

🕒 Published (v1): 2025-01-01 · Source: NeurIPS · Venue: NeurIPS 2025 · link

Ask a follow-up

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

TL;DR¶

Classical cooperative bargaining solutions (Nash, Kalai-Smorodinsky) require access to agent utility values and gradients, which are unavailable or incomparable in human-AI and privacy-sensitive settings. This paper proposes DiBS (Direction-based Bargaining Solution), an iterative mediator algorithm that operates solely on normalized utility gradients (direction oracles), provably converges to Pareto stationary points, and is invariant to monotonic nonaffine utility transformations.

Problem¶

Standard bargaining solutions like NBS and KSBS assume the mediator can read cardinal utility values and gradients—assumptions that fail when agents are humans or LLM-based proxies that cannot report numerical utilities, when utilities are scaled via unknown nonaffine transformations (e.g., RLHF reward models, prospect theory), or when agents withhold utilities for privacy. Moreover, the paper proves (Proposition 1) that no direction-oracle-only algorithm can recover NBS or KSBS for all standard bargaining games, because those solutions are sensitive to exactly the nonaffine transformations that direction oracles cannot distinguish.

Method¶

DiBS replaces utility-weighted gradient steps with direction-oracle-weighted steps scaled by each agent's distance to their individually preferred state:

\[x^{k+1} = x^k - \alpha_k \sum_{i=1}^N \|x^k - x^{*,i}\|_2 \cdot \frac{\nabla \ell^i(x^k)}{\|\nabla \ell^i(x^k)\|_2}\]

Each agent's contribution is the normalized gradient (direction oracle output) multiplied by that agent's Euclidean distance from its optimum, making agents farther from their preferred states more influential—a proxy for "urgency" that is computable without utility values. Direction oracles can themselves be approximated via binary comparison oracles (yes/no/indifferent queries), reducing the required information to pairwise preference comparisons. Agent preferred states \(x^{*,i}\) are precomputed via zeroth-order optimization on the comparison oracle.

Key Contributions¶

Impossibility result (Proposition 1): Proves NBS and KSBS cannot be recovered by any direction-oracle-only mediator for all standard bargaining games.
DiBS algorithm: Iterative, linear-complexity-per-step bargaining algorithm using only direction oracles and preferred-state distances.
Convergence guarantee (Theorem 1): Under strong convexity and smoothness, DiBS globally asymptotically converges to its (Pareto stationary) fixed points with diminishing step sizes satisfying \(\sum \alpha_k = \infty\), \(\sum \alpha_k^2 < \infty\).
Axiom satisfaction (Theorem 2): DiBS satisfies Pareto stationarity, invariance to strictly monotonically increasing nonaffine transformations, symmetry, and (under unique fixed-point conditions) independence of irrelevant alternatives.
Comparison oracle implementation: Shows direction oracles can be estimated to arbitrary accuracy from binary pairwise comparisons using existing sign-gradient estimators (e.g., Sign-OPT).

Results¶

Multi-agent formation (N=10, nonconvex costs): DiBS, NBS, and KSBS all reach qualitatively balanced formations. Under monotone nonaffine cost scaling of odd agents, NBS and KSBS produce skewed solutions favoring scaled agents; DiBS retains a fair, symmetric formation.
Portfolio allocation (N=10 investors, 5/10/20/50 stocks, 100 scenarios): With 10,000 comparisons per agent per iteration, DiBS-via-comparisons achieves median relative error below \(10^{-2}\) relative to DiBS-via-exact-directions for 5 stocks. Even with comparisons far fewer than the problem dimension, median relative error remains below 1 (i.e., comparison-based DiBS still improves over initialization). Accuracy degrades gracefully as stock count grows.

Limitations¶

Global asymptotic convergence proof requires strong convexity of agent costs; the paper acknowledges this excludes the nonconvex formation experiment, where convergence is observed empirically but not guaranteed.
No non-asymptotic (finite-sample) convergence rates are provided.
Uniqueness of the fixed point (required for the independence-of-irrelevant-alternatives axiom) is not guaranteed in general.
Experiments are small-scale; large-scale learning settings (e.g., LLM alignment) are listed as future work.
Comparison oracle query complexity grows with problem dimension, limiting scalability of the oracle-approximation approach in high-dimensional spaces.

Relevance to Agentic AI / LLM Agents¶

This work directly addresses the challenge of multi-agent coordination when agent preferences are encoded in LLMs or RLHF-trained reward models—settings where utility values are either unavailable or distorted by nonaffine reward shaping. DiBS provides a theoretically grounded mediation protocol that requires only preference-direction queries (implementable as "which state do you prefer?" prompts to an LLM agent), making it a principled mechanism for fair resource allocation or negotiation among heterogeneous AI agents. The invariance to nonaffine transformations is specifically motivated by RLHF reward models and sparse-to-dense reward proxies, both central to current LLM agent training pipelines. For multi-agent systems where a central mediator allocates shared resources or resolves conflicts among agents with opaque internal objectives, DiBS offers a convergent, fair, and oracle-efficient protocol.