Research map / Multi-agent systems and games / Games and equilibria
Cooperative Bargaining Games Without Utilities: Mediated Solutions from Direction Oracles
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes DiBS, a cooperative bargaining algorithm that uses only agents' normalized-gradient direction oracles (weighted by distance to each agent's preferred state), proving invariance to monotone nonaffine utility transformations, Pareto stationarity and convergence, and validating on formation assignment and portfolio allocation.
Problem
Cooperative multi-agent bargaining when the mediator cannot access agents' utility values or gradients (only their most preferred directions), and existing solutions like Nash and Kalai-Smorodinsky are not invariant to nonaffine utility transformations.
Approach
A bargaining update that sums each agent's normalized negative gradient (direction oracle) weighted by the distance from the current state to that agent's preferred state; this is invariant to strictly increasing transformations of costs since directions are unchanged, and it yields Pareto stationary fixed points with convergence guarantees under strong convexity and smoothness.
Key results
- DiBS remains fair under the nonaffine transform sign(l)l^2 on odd agents in formation assignment, whereas NBS and KSBS produce skewed solutions.
- In portfolio allocation, the median relative error of DiBS with comparison-estimated directions stays below 1 even when the number of comparisons is below the dimension.
- Theory: DiBS fixed points are Pareto stationary, the iterates are bounded, a fixed point always exists, and global asymptotic convergence holds under strong convexity and smoothness.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| apply a monotonic nonaffine transformation to the odd agents’ costs | DiBS · Multi-agent formation assignment | solution fairness | No clear effect |
| apply a monotonic nonaffine transformation to the odd agents’ costs | NBS and KSBS · Multi-agent formation assignment | solution fairness | Hurt |
| increase the number of comparisons used to estimate direction oracles | DiBS with comparison-based directions · Mediated portfolio management | relative error | Helped |
| use comparison-based direction estimates instead of exact direction oracles | DiBS · Mediated portfolio management | median relative error: under $1$ | Mixed |
Surprising findings
- No direction-oracle-only algorithm can find the Nash or Kalai-Smorodinsky solutions for all games satisfying standard assumptions.
Limitations
- Global convergence requires strong convexity and smoothness of agent costs, which the authors list as a restriction to relax.
- Only asymptotic convergence is shown; no non-asymptotic rates.
- Experiments are small-scale (formation with N=10, portfolios), not large-scale learning settings.
Experimental setup
Datasets: historical stock price data via yfinance
Benchmarks: multi-agent formation assignment (N=10) mediated stock portfolio allocation (n=5,10,20,50 stocks)
Metrics: relative error of comparison-based vs. exact direction solut formation outcome fairness under nonaffine transformation
Baselines: Nash bargaining solution Kalai-Smorodinsky bargaining solution naive normalized-gradient sum
Builds on: Nash bargaining solution Kalai-Smorodinsky bargaining solution Sign-OPT Markowitz portfolio theory
Closest papers by meaning
- Aligning Individual and Collective Objectives in Multi-Agent Cooperation (NeurIPS 2024 · similarity 0.85)
- Multi-Sender Persuasion: A Computational Perspective (ICML 2024 · similarity 0.85)
- Fair and Welfare-Efficient Constrained Multi-Matchings under Uncertainty (NeurIPS 2024 · similarity 0.84)
- Sequential Solution Concepts in Cooperative Games with Generalized Characteristic Functions (NeurIPS 2026 · similarity 0.84)
- A Unified Framework for Uniform-Price Resource Allocation Mechanisms (NeurIPS 2026 · similarity 0.84)
- Welfare-Optimal Serial Dictatorships Have Polynomial Query Complexity (AAAI 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.