Cooperative Bargaining Games Without Utilities: Mediated Solutions from Direction Oracles
Authors: Kushagra Gupta
Surya Murthy
Mustafa O. Karabag
ufuk topcu
David Fridovich-Keil
Venue: NeurIPS 2025 poster ()
Keywords: cooperative bargaining
game theory
Primary area: theory
TL;DR: We propose a cooperative bargaining algorithm where a mediator has access to only the preferred direction oracle of each agent (and not utilities).

Abstract: Cooperative bargaining games are widely used to model resource allocation and conflict resolution. Traditional solutions assume the mediator can access agents’ utility function values and gradients. However, there is an increasing number of settings, such as human-AI interactions, where utility values may be inaccessible or incomparable due to unknown, nonaffine transformations. To model such settings, we consider that the mediator has access only to agents' $\textit{most preferred directions}-$normalized utility gradients in the decision space. To this end, we propose a cooperative bargaining algorithm where a mediator has access to only the direction oracle of each agent.  We prove that unlike popular approaches such as the Nash and Kalai-Smorodinsky bargaining solutions, our approach is invariant to monotonic nonaffine transformations, and that under strong convexity and smoothness assumptions, this approach enjoys global asymptotic convergence to Pareto stationary solutions. Moreover, we show that the bargaining solutions found by our algorithm also satisfy the axioms of symmetry and (under slightly stronger conditions) independence of irrelevant alternatives, which are popular in the literature. Finally, we conduct experiments in two domains, multi-agent formation assignment and mediated stock portfolio allocation, which validate these theoretical results.

Cooperative Bargaining Games Without Utilities: Mediated Solutions from Direction Oracles
Kushagra Gupta*t
Surya Murthy'
The University of Texas at Austin kushagragOutexas.
The University of Texas at Austin surya. www.myyuutettss.oommmmmmm edu
Mustafa O. Karabag
Ufuk Topeu
The University of Texas at Austin
The University of Texas at Austin
karabagButexas.ccm
utopcu@utexas.ed
David Fridovich-Keil
The University of Texas Austin
dfk@utexas.c .dd
Abstract
Cooperative bargaining games widely used model resource allocation and conflict resolution. Traditional solutions assume the mediator can access agents' utility function values and gradients. However, there is increasing number of settings, such as human-Al interactions, where utility values may be inaccessible incomparable due unknown, nonaffine transformations. To model such settings, we consider that the mediator has access only to agents' most preferred prrectionnsnormalllle utility gradients in the decision space. To this end, propose a cooperative bargaining algorithm where a mediator has access to only the direction oracle of each agent. We prove that unlike popular approaches such as the Nash and SioroiSmyrodiissy bargaining solutions, our approach is invariant to monotonic nonaffine transformations, and that under strong convexity and smoothness assumptions, this approach enjoys global asymptotic convergence Pareto stationary solutions. Moreover, we show that the bargaining solutions found by our algorithm also satisfy the axioms of symmetry and (under slightly stronger conditions) independence of irrelevant alternatives, which are popular in the literature. Finally, we conduct experiments in two domains, multi-agent formation assignment and mediated stock portfolio allocation, which validate these theoretical results.
Project Website:
https://kaugsrha, github. io/diis/doooooo -ae--oo---eeee conn-nuuripp ips
Introduction
We consider the problem of centralized, cooperative multi-agent bargaining where a mediator has access only each agent's most preferred direction move the decision space, and does not know the agents' underlying utility functions. Over the past eighty years, variety of celebrated bargaining solution concepts have been introduced [26]: however, most require the mediator to have access to the explicit utility values and gradients for each agent, e.g., the Nash [99 and Kalai-Smoroding bargaining solutions (NBS and KSBS, respectively). Unfortunately, these existing bargaining solutions cannot cater to an increasing number of important settings.
Equal contribution. Corresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

An example of this is when mediators do not have access to agents' underlying utilities (or their gradients) in human-AI interactions. Humans or Al-based proxies (e.g.. language models) may have clear idea of a desired bargaining outcome, but have difficulty providing a numerical value of the utility associated to arbitrary outcomes. Even if a utility available, they may not wish to share that information for privacy reasons.
separate, but equally important issue arises when agents' utilities are not directly comparable, e.g. because they are scaled in different and potentially nonafline ways. Traditional bargaining solutions like NBS and KSBS are invariant to affine transformations in agents' utilities; however, they can lose this invariance under nonaffine transformations [26] (such as those arising in prospect-theoree models (28) [0], or which are represented by neural network based AI- Al-proxies (T] and yield solutions which favor one agent disproportionately. In such scenarios, despite utilities being incomparable due to different nonaffine scalings, the notion of the agents' most preferred directions remains intact.
Such settings motivate the need for an approach to bargaining in scenarios where the mediator only has access direction oracle which provides the most preferred direction (i.e., the normalized utility gradient) in the decision space for each agent. Inspired by this, we address the following questions:
1. Is it possible to solve for existing bargaining solution concepts which are based on utility values in the setting where the mediator has access only agents' most preferred directions, and their utilities?
Contribution 1. We show that no algorithm with mediator access only direction oracles can find the Nash or Kalai-Smorodinsky bargaining solutions for all bargaining games satisfying standard assumptions in the literature.
2. If not, can we develop solution concept for the direction oracle setting where the mediator effectively balances every agent's 's interests, and is invariant to preference pressevvng non- affine transformations of (polentially unknown)) agent utilities?
Contribution 2. We propose Direction- based Bargaining Solution (DiBS), an iterative algo- rithm which uses only direction oracles, and reasons about every agent's distance from their preferred state throughout the bargaining process. We show that under standard assumptions common in the literature, the solution found by DiBS satisfies the following axioms:
(a) Pareto stationarity (a necessary condition for Pareto optimality, and also sufficient under slightly stronger assumptions).
(b)
Invariance to strictly increasing monotonic nonaffine transformations.
(c) Symmetry, and under slightly stronger conditions, independence of irrelevant alterna- tives.
3. Can we have convergence guarantees to reliably find bargaining solutions which employ only direction oracles?
Contribution 3. We prove that under standard assumptions, fixed points of DiBS exist, all its fixed points are Pareto stationary points, and that assuming that the (hidden) agent costs (i.e., negative utilities) are strongly convex and smooth, DiBS enjoys global asymptotic convergence guarantees to the set of its fixed points.
We note that access to the direction oracle can be easily achieved in practice by giving the mediator access to minimal information comparison oracle for each agent at some state in the bargaining process, the mediator proposes new states to every agent, who responds either "yes", "no" or "indifferent", depending on whether the agent prefers the new state more than the current state. Forming estimates of agents' most preferred directions (i.e., normalized utility gradients) up to arbitrary accuracy from only (potentially noisy) comparison oracle is well-studied problem, with 34. Of course, when agents' utilities are available, the mediator can simply compute their normalized gradients; these will be comparable across agents even if their utilitics are scaled in different nonaffine fashions.
many established algorithms [6] TO 13 24 25
On existing bargaining solutions and related work
We denote vector in bold (e.g., x). We denote [N] == -1, N). For x, E R", inequalities apply elementwise. For some process involving iterations of vector x, we denote the th iteration as Xt.
Notation.

---

Bargaining game with known utilities. Consider a game with N agents, the 8th of which has differentiable cost (i.e., negative utility) function (()) : E=" - R. where x S R" denotes the state of the game. Each agent wants to minimize their cost, which corresponds to moving to a set of preferred states in S, x* E arg minxes (xx) and we assume that x* exists. The mediator must conduct bargaining process to output a bargaining solution state x Every agent incentivized to participate in the bargaining process by being assigned a disagreement penalty of d' E R in case no bargaining solution is agreed upon. Let {(xx == [e' (x).... ... e (x)] d := .......
,d'...,'''' ,d' and f= ([()]xx 8). It is assumed that S n (x Ih= d {(x)) is non-empty. We denote such bargaining game by Bg (f, d), and any process finding a bargaining solution to (s(e, d) must output a solution state x and the corresponding agent costs [(x1). A detailed description of bargaining
games can be found in existing literature, cf. 18 22 26
is widely recognized that there is no one correct approach to solve a bargaining problem. Nash proposed a set of desirable axioms (given below) that a bargaining solution should satisfy [I9 22] showing his Nash Bargaining Solution (NBS) can be found by optimizing the product of agents' utilities:
Axiom 1 (Weak Pareto Optimality)- A state x² is weakly Pureto optimal if there does not exist a state y & such that e(xt) > E(y), y # x!.
Axiom 2 (Symmetry). The bargaining solution is invariant to permating the agents' order.
Axiom 3 (Invariance to Affine Transformations). Applying an affine transformation h1) = a'l + 8', R, at E R,, E IR to the thh agent's 's cost does not change the bargaining solution state.
Axiom 4 (Independence of Irrelevant Alternatives). If a bargaining problem Bs (R, d) has solution state x E S' with S' C S then the bargaining problem Bs (e, d) also has solution state xt.
The following assumptions are standard in the bargaining literature, c.f., 22 26
Assumption 1. The state space S is convex, and the set of Pareto points lies in interior of S. Assumption 2. The agent cost L is twice-differentiable and convex.
We remark that no axiom is universally accepted in the literature. For example, popular and well-studied bargaining solution that does away with Axiom Dis the Smooo-SSmryyy bargain- ing solution (KSBS) [9. The KSBS satisfies Axioms 33 in addition to the axiom of individual monotonicity, which states that for two bargaining problems (s(e, d) and Bs (e, Sf C S and arg minxxes (x) arg min (x)), then (' S (x where x x denote the solutions to (e, d) and Bs df) respectively.
Numerous other bargaining solutions exist which relax some combination of Axioms 1 aad satisfy other axioms 222 26 29] However, for the purposes of our discussion, is sufficient to focus on the NBS and KSBS to illustrate our arguments. Formally, the NBS optimizes the product of agent utilities (negative costs), and consists of the iterates (for 2 and some appropriate step sizes o > 0)
((()))
X Xx=
Ork
(xxx)*
(NBS)
while the Kalai- Smorodinsky bargaining solution has geometric solution to the bargaining problem, seeking to equalize the proportional cost benefits of every agent, i.e., finding a state XksBs such that
d' l (xKSBS) d' - (xKSBS)
Vi,j [N]
(KSBS)
d' es (x*
de e (xxri)
A condition which is closely related to Pareto optimality, given in Axiom and applicable when agent costs are smooth, is Pareto stationarity.
Definition 1 (Pareto Stationarity). For a bargaining game as defined above, xps E S is said to be Pareto stationary if zero is convex combination of agents' cost gradients at xps, i.e., 3 3 2 0,
1,..., N, such that Σ 3'Ve (xps) = and Σi B 1.
Pareto stationarity is necessary condition for Pareto optimality 15 23 and sufficient condition for strong Pareto optimality (given below) when agent costs are strictly convex and twice differentiable 8 23 Pareto stationarity is a first-order characterization and acts useful alternative to Axiom
3

---

because it is often difficult to check if point is Pareto optimal in many bargaining settings. As such, many works addressing bargaining challenging coveentneti settings seek to satisfy Henceforth, we will also consider Pareto stationarity in the bargaining solution we introduce. Under an additional assumption of strict convexity, any weakly Pareto optimal point found by NBS is also strongly Pareto optimal, which is defined in the axiom below.
Pareto stationarity [00 32 33
Axiom 5 (Strong Pareto Optimality). A state x is strongly Pareto optimal V i (x1) > el (y(y)
]j E [N] such that é (x!)= < Ø (y).
2.1 Limitations of existing bargaining solutions
We first provide formal definition for the direction oracle. Definition 2 (Direction Oracle). A direction oracle for agent i, O (x), gives the most preferred direction for agent at a state x, given by
O (x) 02
X + x
Sensitivity to nonaffine scaling, Although utility-value based bargaining solutions like NBS and KSBS are robust to affine utility transformations, they remain adversely susceptible more general monotonic transformations. Such nonaffine transformations may occur due to agents reporting exaggerated scaled utilities in order to bias the bargaining solution, or unintentionally when trying to model preferences as numerical utility from data involving comparisons, like in reinforcement 3T. Another source of such transformations inadver-
learning from human feedback (RLHF) tently appearing is when agents have utilities which fit hand-tailored reward functions representing preferences; this is especially common when deploying reinforcement learning "sparse" reward scenarios, where crafted dense reward is used as a proxy for sparse high-level preferences [16] (7). While such transformations corrupt utility values and change bargaining solutions, they still roughly preserve agent preferences; bargaining solutions employing only direction oracles should remain robust to such nonaffine monotonic transformations (this will be proved in Section 3
Existing bargaining solutions cannot be found with direction oracles. Most bargaining solutions, including NBS and KSBS require the mediator to have access agent costs/utilities. Intuitively, this is explained by the fact that these existing bargaining solutions require reasoning about agents' benefits in the cost space. For example, implementing the soBStin solution requires knowledge of both agent cost values and gradients. However, when the mediator has access to only the direction oracles i
o 1, 1...., NN, the agents' cost values and gradient magnitudes are not available. This lack of information makes it impossible to find points which satisfy the NBS and KSBS solution concepts (even if they exist). This result is formalized in Proposition] [ (proof in Appendix A.I).
Proposition (Inadequacy of NBS and KSBS for the direction oracle). There does not exist any bargaining algorithm in which mediator with access to only direction oracles OD: can find the Nash or the Smorodiimyyy bargaining solutions for all problems satisfying Assumptions 7
Proposition I establishes that existing bargaining solutions require reasoning about quantities which inaccessible in the direction oracle setting. The proof of Proposition I given in Appendix A. exploits the invariance of direction oracles to strictly monotonically increasing (possibly nonaffine) transformations combined with the shortcoming of NBS and KSBS being sensitive such nonaffine scalings. We provide an example below to help explain Proposition
Example 1. Consider bargaining game (,,,) (x 1)2], [1, 1]), for which both NBS and KSBS
lie at 1/2. However, for the game with the nonaffine transformation f(y) y² (monotonically
strictly increasing in S) applied to agent 1, ([x*, (x 1) [1, [1,1]] 1)) both NBS and KSES are not at æ = 1/2. However, in both games, the most preferred directions for agents and 2 are to go towards
1 respectively. Thus, even if an algorithm employing only direction oracles finds NES and KSBS for (,,,) (x - 1)3]. 1]). it will not be able to find them for
0. and
(x (Ix,,
Thus, there is clear need for introducing new solution concept for bargaining problems which (i) can be identified by algorithms that employ only direction oracles, and (ii) is still robust to non-affine monotonic cost transformations.

---

2.2 Naive direction oracle-based bargaining can lead to unfair solutions
When the mediator has access to direction oracles, it is natural to construct a simple bargaining procedure which utilizes the sum of normalized gradients, i.e., at state the mediator creates estimates of ve (x)) Vi [N], and for some a > 0, proceeds to the next state x+, given by
N Eopi - -x
N
(e(()
x = xxaa
V
At a glance, eq. 22) resembles a utilitarian approach to bargaining which would minimize the sum of agents' costs 126 however, in fact the update rule eq. (2) differs drastically as weighs the direction associated with each agent i equally. While eq. corresponds to a valid bargaining solution satisfying Pareto stationarity (see Appendix D). we argue that this simplistic bargaining solution can lead to unfair solutions, as demonstrated by the following toy example.
Consider again the two-agent bargaining game [ [x² (x - 1)²), [1. Due to symmetry, a "fair" bargaining solution will reside at x = 1/2. Let eq. (2) be initialized at some To E (0, 1), zo o 1/2. Then, because ( (x) x Zo. which is not a fair solution as zo can be initialized arbitrarily in (0, 1) far away from x = =/2..
Example 2.
= (=///// ( lla, we get convergence at
Existing direction-oracle based bargaining algorithms give unfair solutions. There two existing works which attempt to conduct bargaining exclusively through directions, (7] 17 Both works consider the two-agent setting, and propose iterative procedures for finding mutually beneficial directions, given the most preferred directions of both agents. However, both approaches consider bargaining scenarios with self-interested agents-which can lead to unfair solutions in cooperative bargaining settings; ef. Example 2, where agents never have a mutually beneficial direction. In such situation, both algorithms stop wherever initialized and find points which are technically Pareto stationary, but heavily favor one agent. Further, [17] does not readily extend beyond the two-agent case in which finding mutually beneficial directions becomes combinatorially hard, and 7 reports a loss of mutual improvement and convergence guarantees in cases with more than two agents. A related but orthogonal line of work pertains to flocking in multi-agent scenarios 21 we discuss the differences between flocking and our bargaining solution in Appendix F
3 Bargaining with Direction Oracles
It is clear that the mediator must take care when employing normalized gradients. The information which a solution concept like eq. (2) lacks is a notion of how far a potential solution is from each agent's 's preferred state. Existing bargaining solutions approach this issue by considering values in the cost spuce L, which is not accessible in the direction oracle setting. Instead, the direction oracle setting, one must conduct such reasoning in the state space S. Even if the mediator has access to L, reasoning in the state space can be beneficial as the components for each agent L can be nonaffinely scaled, while S is shared uniformly by all agents.
natural way to conduct such reasoning is incorporate how far will the bargaining solution state be from each agent's preferred state (which is computable even in the direction oracle setting). To this end, we propose Direction- based Bargaining Solution (DiBS): starting from some state Xo. DiBS conducts the following iterations to find a bargaining solution:
X f(xx)= Xx + ak
Σ
X x
122 (xxA)((x))))
N
X2= CEk
||xe
(DiBS)
where {axJa20 are appropriate step sizes, and * E arg minxxs e (x) is a choice from the set of preferred states for the tth agent and fixed for all iterations. For the sake of convenience, if ( = O we define vé' (1) = 0. We remark that both the quantities used by DiBs i.e., ve' (x)/ (x0lla and " are available through direction oracles which are implementable practice
5

---

Note how DiBS differs from NES in its iterations, NBS gives more importance to those agents who have lower cost improvements (by scaling agent gradients with (x))), while DiBS gives more importance to those agents who are further away from their preferred states (by scaling agent gradients with x|x-x" (2) l2).
without using explicit agent costs- elaborate upon this in Section 3.2
Given the most preferred directions "p'(s))
(xx) and preferred states x** of each agent, every iteration DiBS has linear complexity in both the number of agents and the number of state dimensions. We
remark that the most preferred states x can be efficiently calculated as a precomputation step by
the mediator (if the agent is unable to directly provide them) using existing methods [13]
3.1 Theoretical properties of Direction-based Bargaining Solution DiBS
To establish the legitimacy of DiBS as a bargaining solution, we will first show that it finds Pareto stationary points. This can be seen by viewing DiBS as dynamical system, and analyzing its fixed points. We define these concepts below. All proofs for our results can be found in Appendix [A]
Definition 3 (Fixed/Equilirrium Points). Consider function fa I R" and the corresponding discrete-time dynamical system X++1 = fa(x)). Then, X is a fixed point of the dynamical system f. (x() Similarly, x is an equilibrium point of the continuous- time dynamical system fx( for function fo R + R" if (X) = 0.
dynamical system's 's ability to converge depends upon the system's 's stability properties. In particular, we will be interested in global asymptotic convergence.
Definition 4 (Global Asymptotic Convergence). Consider functions fg R R", R - R" and set S. The discrete-time dynamical system X fxxx)), has global asymptotic convergence to G if lim4-+00 x(k) E G x(0) E S. Similarly, the continuous-ting dynamical system (t) f. (x),
has global asymptotic convergence to if lim x(t) E g x(0) E
We begin by showing that any fixed point for DiBS is also Pareto stationary and that DiBS has global asymptotic convergence to the (non-empty) set of its fixed points (proof in Appendix(A.2)
Theorem 1 (Convergence of of to Pareto Stationary Points). Direction-based Bargaining Solution
DoBS has the following properties:
1. Any fixed point of DiBS is also a Pareto stationary point.
2. Under Assumption the iterates of DiBS are bounded in R
3. Under Assumptions a fixed point of DiBS always exists.
4. Assuming that agent costs l are p² -sroonlly convex and that Assumptions 1 continuous analog of DiBS
hold, the
V ( (x)
x h(x) =
enjoys global asymptotic convergence to its equilibrium points. Further, the agent costs are L' -mooth, then DiB5 enjoys global asymptotic convergence to the set of its (Pareto station- ary) fixed points for stepsizes 0% >> 0 chosen such that Σi= 0z 6o and E of < co.
Theorem establishes that DiBS has desirable convergence properties, and is useful for finding Pareto stationary points when mediator only utilizes direction oracles in bargaining game. Now, show that DiBS also inherits several key axioms from the cooperative bargaining literature (proof in Appendix A.3).
Theorem 2 (Bargaining axioms satisfied by DiBS The Direction-hased Bargaining Solution DDBS
satisfies the following axioms:
1. The solution found by DtBS is Pareto stationary (and strongly Pareto optimal if agent costs are twice differentiable and strictly convex).
2. The solution found by DEBS is invariant to strictly monotonically increasing nonaffine transformations.

---

3. The solution found by DiBS satisfies the Axiom of Symmetry (Axiom 2.
4. If DiBSShas only one fixed point for problem, then the solution found by DiBS satisfiees the axiom of independence of irrelevant alternatives (Axiom
Importantly, Theorem 2 establishes the invariance of DiBS to monotonic nonaffine transformations, which is not obtained by NES and KSBS This invariance particularly attractive it allows [iBS] to be robust against transformations which can occur due to imperfect cost function modeling or agent exaggerations, while still retaining the agents' relative preferences between states.
3.2 Practically obtaining a direction oracle
As mentioned earlier, it is possible to implement a direction oracle given only binary comparison oracle, where at some state x in the bargaining game, the mediator asks every agent whether they prefer different state more than the current state, and the agents reply with the minimal information of "yes", "no", or "indifferent". Formally, a comparison oracle for the zth agent who queried at state x about state y. Oe.0t [x,y y) is defined as
if < (()),
O (x,))
0,
if = (x), -1,
if (xx).
What information can the comparison oracle give? Optimization solely using comparison oracles a well-studied problem the single-agent setting. As consequence, numerous algorithms exist in the literature which can estimate the normalized negative cost gradient, i.e., the most preferred direction, for an agent with only comparison oracles and can find the normalized gradients up to arbitrary accuracy for smooth functions. The number of queries required to estimate the normalized gradients up to a required accuracy bounded, and many of the existing algorithms are also robust to This implies that if the zth agent's 's cost (x(x) is inaccessible to the mediator, the mediator can use any of the above off- shelf algorithms employing the minimal information comparison oracle as a practical way to estimate the agent's 's most preferred direction - VV'' (x)/II with arbitrary accuracy. Further, the mediator can use the same algorithm to find the most preferred state = E arg minxes E' (x) for the agent, details of which are given in Appendix
noisy binary oracle evaluations (6] TO 13
24 34]
Experiments
We now evaluate our bargaining solution in practical problems. Our main aims (i) to investigate the solution quality DiBi (ii) to test the invariance of monotonic nonaffine transformations, and (iii) to investigate the how the performance of affected by the accuracy of normalized gradient estimates formed via comparison oracles.
4.1 Nonconvex multi-agent formation assignment under different bargaining solutions
In this experiment, N agents, either odd even, lie in two-dimensional plane, and attracted to a center point c, while simultaneously exhibiting group-specific cohesion and repulsion behaviors. The position of the 2th agent is x [0, 10] x [0, 10] C R and the game state is x fx ..... ...,x" V), with S C R Agents with the same parity index (odd or even) prefer to remain close, while agents of different parities prefer greater separation. The 5th agent's preferences modeled using cost function of the form
Ll (x) = a b|xx -ell2
(( (6- (6-00% a. a. R
(4)
where the pairwise interaction weights R,,,13 R4 control group attraction and repulsion. We emphasize that the cost functions given in eq. (4 are nonconvex due to the difference of exponentials.
Baselines. We choose N agents, all implementation details can found Appendix C.
We compare DiBS (with access only direction oracles) against NBS and KSBS (both of which have

---

Initial point (even agents)
Initial point (odd agents)
aa) NBS
(h) KSBS
(c) DiBS (ours)
Center point
Final point (even agents)
Final point (odd agents)
(d) NBS
scaled
(c) KSBS
scaled
(f) DiBS (ours) scaled
Figure 1: Formations achieved by different bargaining solutions. While DiBS yields qualitatively
similar outcomes to NBS and KSBS in the original setting, it is also robust to monotone nonaffine scalings. KSBS is solved single shot, with iteration trajectories to plot (see Appendix C.I
access to the full costs e) We emphasize that DiBS NBS and KSBS are different bargaining solution concepts, and while no concept is strictly "better" than the rest, we conduct this comparison to illustrate our motivation for developing DiBS
DiBS leads to balanced solutions. Figure I (a)-(c) shows the initial and final positions of all agents. For DiBS and NBS also plot the variation of agent positions across iterations. KSBS is solved in one shot and does not have such variations available for plotting (see Appendix C.I). We observe that all three methods NBS preferences, and balance their interests in different ways. At the solution, NBS and KSBS slightly prioritize clustering attractive agents while DiBS slightly prioritizes minimizing agent distances from the center, but overall all methods balance the three high-level objectives for all agents. Despite the nonconvex costs, observe that all methods converge for the example.
KSBS
DiBS reach reasonable solutions which respect agents'
Invariance DiBS to monotone nonaffine transformations F show the bargaining process when the costs given in eq. (4) for the odd agents undergo a monotone nonaffine transfor- mation, i.e., si'n (x))
which retains the agents' relative preferences between states. As highlighted before, such transformations may occur due to a variety of reasons, such as modeling imperfections or exaggerated utilities. We observe that while NBS and KSBS completely change their solutions and present skewed, unfair outcomes that favor the odd agents with exaggerated utilities, our method DiBS]stil retains fair outcome.
4.2 Mediated portfolio management through comparisons
In this experiment, we demonstrate the performance of DiBS where the direction oracle is approxi- mated using comparisons.
Setting. A mediator allocates a shared stock investment fund across set of stocks based on the preferences of a group of N investors. The mediator's 's decision corresponds to portfolio vector The ith investor has cost function modeled using the well-known Markowitz portfolio theory [14), given by (x) x Σ X N' x, where Σ is the covariance matrix of stock returns, jı the vector of expected returns, and X the reward tradeoff coefficient.
x E R", where x 2 0 and 1 T

---

Stocks
10
10 Stocks
Relative Error in Solution
20 Stocks
100
50 Stocks
10
10-2
10-3
10
10
100
1000
10000
Number of Comparisons (Per Agent, Per Iteration)
Figure 2: Results for the portfolio management example, showing the 1.5th 25th 50th 75th and 98.5th percentiles. DiBS offers promising performance even when the direction oracle is estimated through comparisons. Dots represent outliers; ef. Appendix C.2 for further details.
Modeling diverse investor preferences. The expected return vector μ² and covariance matrix Σ are computed from historical stock price data 22 in an investor-specific time window. Ultimately, each agent is assigned personalized investment profile by randomly sampling:
A time horizon from the following predefined investment windows: 5 days, month, months, months, year, years, years, all time (8 years). All windows end common date of December 31, 2023.
A risk-reward tradeoff coefficient X uniformly sampled from the interval [0.0, 0.1].
This initialization results in agent-specific cost functions that reflect diverse set of investor types and stock market views. We sample 100 scenarios in this manner. All implementation details are given Appendix C.2 Additional results for different numbers of investors are in Appendix B
Baseline and metric. We compare two versions of DiBS one which uses the direction oracle yielding the solution dir and one which uses comparisons approximate direction oracles via the estimator used in Sign-OPT (6) yielding the solution X We allow this estimator to query the comparison oracle 1, 10, 100, 1000 and 10000 times at every iteration for every agent i. For both
versions starting at Xo, we calculate the relative error for each sample scenario, defined as [ ximpl
X Xo
DiBS offers promising performance even when the direction oracle is estimated through parisons. Figure shoows the relative errors for DiBS using comparisons vs. true direction oracles for = 5, 10, 20, 50 stocks and N 10 agents. We observe that, expected, the accuracy increases with the number of comparisons allowed, and as the dimension of the problem (i.e., the number of stocks) increases, the number of comparisons which is required for accurate estimation of O.: increases. We remark that even when the number comparisons allowed significantly lower than the number of dimensions and, therefore, there is significant error in the direction estimates, the median relative error of DiBS employing comparisons remains under 1, indicating improvement over the initial state towards the solution of DiBS employing exact directions.
5 Conclusion
We consider increasingly important class of cooperative bargaining problems, in which mediators do not have access to agent utilities (which may be incomparable), and can instead only access agents' most preferred directions. These settings arise in human-Al interactions, privacy-sensitive

---

applications, and multi-agent agentt interactions with exaggerated or snperfectlymodellee utilities. We show that no direction oracle-based algorithm can recover popular existing bargaining solutions NNS KSBS) for all bargaining games that satisfy standard assumptions. Therefore, we propose new bargaining solution for this setting (DiBS), and show that it identifies Pareto stationary solutions, is invariant to monotonically increasing nonaffine transformations, and satisfies the axiom of symmetry. Under additional mild assumptions, we also show that [DBS satisfies the axiom of independence of irrelevant alternatives, and enjoys global asymptotic convergence to Pareto stationary solutions. Finally, we conduct experiments in two settings to validate our results and show that DiBS performs well when direction oracles estimated using only comparison oracles, which are straightforward to implement in practice. Future work should investigate (i) relaxing the strong convexity assumption which is required in the proof of global convergence, (ii) providing non-asymptotic convergence results, and (iii) conducting experiments in large-scale learning settings.
Acknowledgments and Disclosure of Funding
The authors would like thank Filippos Fotiadis for insightful discussions on related topics. This research was supported by the Army Research Laboratory under cooperative agreements INF. 23-2-001 I and I9 the National Science Foundation under grant numbers 2336840 and 221 1432, Office of Naval Research (ONR) grant ONR N00014-24-1-2797, and Army Research Office (ARO) grant ARO W91 1911NF-23-1-031 The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of these sponsors or the U.S. Government.
10

---

References
[1] Saurabh Arora and Prashant Doshi. A survey of inverse reinforcement learning: Challenges, methods and progress. Artificial Intelligence, 297:103500, 2021.
[2] Ran Aroussi. yfinance: Download market data from Yahoo!Finance's API. htttss://githn com com//ranarouss//yffnanncc 2015. Apache Software License 2.0. Accessed: 2025-05-15.
[3] Jeremy Bernstein, Yu-Xiang Wang. Kamyar Azizzadenesheli, and Animashree Anandkumar. signsgd: Compressed optimisation for non-convex problems. In International Conference Machine Learning, pages 560-569. PMLR, 2018.
[4] Vivek S Borkar and Vivek S Borkar. Stochastic approximation: dynamical systems viewpoint, volume 9. Springer, 2008.
[5] Luitzen Egbertus Jan Brouwer. Über Abbildung von Mannigfaltigkcitnn Mathematischee annalen, 71(1):97-115, 1911.
[6] Minhao Cheng, Simranjit Singh, Patrick H. Chen, Pin- Yu Chen, Sijia Liu, and Cho-Jui Hsieh. Sign-opt: A query-efficient hard-label adversarial attack. In International Conference on Learning Representations, 2020. URL http:p/:/.pppaareeeeeeeees//rrrs
[7] Harri Ehtamo, Eero Kettunen, and Raimo P Hämäläinen. Searching for joint gains in multi-party negotiations. European Journal of Operational Research, 130(1):54-69, 2001.
[8] Joerg Fliege, LM Grana Drummond, and Benar Fux Svaiter. Newton's method for multiobjective optimization. SIAM Journal on Optimization, 20(2):602-66) -226 2009.
[9] Ehud Kalai and Meir Smorodinsky. Other solutions to Nash's bargaining problem. Economet- rica: Journal of the Econometric Society, pages 513-518, 1975.
[10] Mustafa O Karabag, Cyrus Neary, and Ufuk Topcu. Smooth convex optimization using sub- zeroth-order oracles. In Proceedings of the AAAI Conference on Artificial Intelligence, vol- ume 35, pages 3815-382. 2021.
[11] Timo Kaufmann, Paul Weng, Viktor Bengs, and Eyke Hüllermeier. A survey of reinforcement learning from human feedback. Transactions on Machine Learning Research, 2025. ISSN 2835-8856. URL / wtt.://wwee/oororrrddddoo/oorrr
Survey Certification.
[12] Hassan Khalil and Jessy W Grizzle. Nonlinear systems, volume Prentice hall Upper Saddle River, NJ, 2002.
[13] Sijia Liu, Pin-Yo Chen, Xiangyi Chen, and Mingyi Hong. signSGD via zeroth-order oracle. In International Conference on Learning Representations, 2019. URL https://openrevier net//forum?xd-BBJo-DCCCC77
[14] Harry Markowitz. Portfolio selection. The Journal of Finance, 7(1):77-91, 1952. ISSN 00221082, 15406261.
[15] I Maruşciac. On Fritz John type optimality criterion in multi-objective optimization. Mathematica-Ren Revue d' a'analyse numérique de théorie de l'approximation. L. L'analyse numérique et la théorie de l'approximation, pages 109-114, 1982.
[16] Tongzhou Mu, Minghua Liu, and Hao Su. Drs: Learning reusable dense rewards for multi-stage tasks. In The Twelfth International Conference on Learning Representations, 2024. URL
https://openreviex. wttp:/tteeeeottttdeee.eet.
[17] Surya Murthy, Mustafa O Karabag, and Ufuk Topcu. Sequential resource trading using comparison-based gradient estimation. arXiv preprint arXiv:2408. / /1186, 2024.
[18] Yadati Narahari. Game theory and mechanism design, volume 4. World Scientific, 2014.
[19] John F Nash al. The bargaining problem. Econometrica, 18(2):15-1622. 1950.

---

[20] Aviv Navon, Aviv Shamsian, Idan Achituve, Haggai Maron, Kenji Kawaguchi, Gal Chechik, and Ethan Fetaya. Multi-task learning as bargaining game. In International Conference on Machine Learning, pages 16428-16446. PMLR, 2022.
[21] Reza Olfati-Saber. Flocking for multi-agent dynamic systems: Algorithms and theory. IEEE Transactions on automatic control, 51(3):401-422 2006.
[22] Alvin Roth. Axiomatic models of bargaining, volume 170. Springer, 1979.
[23] Abhishek Roy, Geelon So, and Yi-An Ma. Optimization on Pareto sets: On a theory of multi-objective optimization. arXiv preprint arXiv:2308.021455 2023.
[24] Aadirupa Saha, Tomer Koren, and Yishay Mansour. Dueling convex optimization. In Interna- tional Conference on Machine Learning, pages
PMLR, 2021.
[25] Aadirupa Saha, Tomer Koren, and Yishay Mansour. Dueling convex optimization with general preferences. Forty-second International Conference on Machine Learning, 2025. URL
[26] William Thomson. Cooperative models of bargaining. Handbook of game theory with economic applications, 2:1237-1284, 1994.
[27] Alexander Trott, Stephan Zheng, Caiming Xiong, and Richard Socher. Keeping your dis- tance: Solving sparse reward tasks using self-balancing shaped rewards. Advances in Neural Information Processing Systems, 32, 2019.
(28) Amos Tversky and Daniel Kahneman. Advances in prospect theory: Cumulative representation of uncertainty. Journal of Risk and uncertainty, 5:297-323, 1992.
[29] Eric Van Damme. The Nash bargaining solution is optimal. Journal of Economic Theory, 38(1): 78-100, 1986.
[30] Peter P Wakker. Prospect theory: For risk and ambiguity. Cambridge university press, 2010.
[31] Binghai Wang. Rui Zheng, Lu Chen, Yan Liu, Shihan Dou, Caishuang Huang, Wei Shen, Senjie Jin, Enyu Zhou, Chenyu Shi, et al. Secrets of RLHF in large language models part ii: Reward modeling. arXiv preprint arXiv:2401. 20000000000 2024.
[32] Mao Ye and Qiang Liu. Pareto navigation gradient descent: a first-order algorithm for op- timization in Pareto set. In Uncertainty in artificial intelligence, pages 2246-2255. PMLR, 2022.
[33] Yi Zeng, Xuelin Yang, Li Chen, Cristian Ferrer, Ming Jin, Michael Jordan, and Ruoxi Jia. Fairness-aware meta-learning via Nash bargaining. Advances in Neural Information Processing Systems, 17:83235-832611 2024.
[34] Chenyi Zhang and Tongyang Li. Comparisons are all you need for optimizing smooth functions. arXiv preprini arXiv:2405. 1454, 2024.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer:
[Yes]
Justification: All claims are covered in contributions presented in Proposition and Theorem
|
Theorem
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: Yes, in Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
13

---

Justification: All assumptions are stated in the fleorem//roopositoon statement. All proofs are in Appendix
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: All experimental details with values required for reproducing experiments are covered in Appendix C.T and Appendix C2
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
14

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We provide code and executable scripts in supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ peaips.cc/publicguuu.ee CoodeSumeeieeeeee ssi iessonPolll mollicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We do not do any network training, but all experiment details are provided in Appendix [.. and Appendix C.2
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: These are reported via the caption the box plot in Figure and the details in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
15

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Provided in Appendix C.3
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: Our work conforms with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no socictal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
16

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Existing asset is mentioned and cited appropriately in the experiments section.
Guidelines:
The answer NA means that the paper does
existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
17

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Our assets are the code which has instructions to use and will included in supplementary material.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
18

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: Our work does not involve LLMs as any important, original or non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy btteps:/nneuripee /t/CCooffreeccs//2222 for what should or should be described.
19

---

Appendix table of contents
Proofs
20
B Additional experiments for mediated portfolio management
24
Experimental details
25
D On naive bargaining algorithm given in Equation
26
Obtaining preferred states using direction oracles
26
Relation to multi-agent consensus and flocking,
26
A Proofs
A.1 Proof of Proposition I
To prove Proposition I we first establish the invariance of the direction oracle presented in Equa- tion to strictly increasing monotonic (possibly nonaffine) transformations.
Proposition 2. Consider an N Naagent burgaining game Bs(e, d) with associated direction oracles
opi,i [N]. Let g¹ R - RR E [N] be strictly monotonically increasing, possibly nonaffine functions. Let (e) = (g), (L (x))]. Then, for the direction oracles OD. i E [N] g(2):
associated with the utility transformed bargaining game Bs (g(g d), we have O = DD i g(t)*
[N].
Proof. For agent j. we have
Vg(P(x)) = g((((x)) (x)
(chain rule)
[x(((x))
(x()
(x((((x)) (x)
OD =OP ViE [N]
((E)
We can now prove proposition by contradiction. Assume that there exists a deterministic algorithm A which can recover NBS or KSBS by only using direction oracles O. for all bargaining games Consider nonaffine, strictly monotonically increasing function g: R R. with g'(() 0 VVZ R. applied to transform only agent j's utilities. Then, one can
(s(L, d) satisfying Assumptions
construct new bargaining game (e, d), where l corresponds the costs
* (xx) = (x)),,), i=j.
(x),
As NBS and KSBS
not invariant to nonaffine transformations, one choose such that NBS and KSBS for Bs e, d) are different than the ones corresponding to Bs(e, d). However, from Proposition 2 have O O.. V E [N]. When algorithm A is used to solve the bargaining [N]. However, because O
problem (s(e, d). A query O deterministic algorithm, will return the same solution as it did for (s(E, d), which cannot be the bargaining solution for B& (e, d) because of the nonaffine transformation g. Hence, by contradiction, there is no such A.
oD and A is
20

---

A.2 Proof of Theorem
Proof Sketch: We first show that the iterates of DiBS are bounded, and that a fixed point of DiBS always exists. We then show that any fixed point of DiBS is also Pareto stationary. Then proceed to analyze the continuous- asymptotic converge to it's equilbrium points (fixed points of DiBS). Finally, we show that there is way to choose step size such that DiBS retains these convergence properties.
dynamical system corresponding to DiBS show that enjoys global
Iterates of DiBS remain bounded. Consider a ball B in with finite radius big enough to contain x Vi E [N] If DiBS iterates diverge, they must escape this ball. Consider the situation when the DiBS iterates are at the boundary this ball at some point x. Consider the vectors
(x( (x)ll
g'
|X
x 12-
Because x* E B,i [N], all -.... N point inside the ball B. Then the quantity Ee of lies in the convex cone of g" and must also point inwards the ball B. Thus the next iterate must lie within the ball B, can never escape this ball of finite radius and remain in S.
2. A fixed point of DiBS always exists. Using the fact that the DiBS iterates remain bounded in S, and the convexity of the Euclidean ball, from Brouwer's fixed point theorem [5], we get that a fixed point DiES always exists in S.
3. Fixed points of DiBS are Pareto stationary. Let xt be fixed point of DiBS then for some
a >
Ve((x!)
x x
||x
x1
V
(x!)
|xx -xl-x*1 ||2 0,
which satisfies the definition of Pareto stationarity given in Definition 1 with
xx -x x |la/ (x
8
N Li=1 ||x - |l//1
4. Global asymptotic convergence continuous-time analog DiBS uous time dynamics corresponding to DiBS given by
Consider the contin-
N
( [e((x)
x = -x()) =
||x- 1xx-x"1 112
At an equilibrium point x! ht we have that (xx)) = 0. Now consider for the 5th agent,
(e(x)
hx(x) (V ||x ||x=x**lla
Vhi(x) = (x((x) (v
(1 [
)
||x- x2 H1(()), H.(xx) = V26(x)
[[Ve(()]11
(x)
x
|Xx
x*1
[ (x
)) H)((x)
(x)(())
x lle
(x)
(x) E
:=A(x)
:()(
We will show that for all agents i, u (Vh((x) + (h;(x) < A such that huu) *
0, E R". For any u || (x),, have u B(x) = = B(x)u 0. For any
21

---

T (x(x), we have
1|x
u B(x)u=
Hx(x)u
[ 2
(x)
Xx x
V
(x)x) (1
(x) 1
(x) 1
(x)
(u 1. (x))
> +
(H; > 111)
u (x) 1> 2XAA x* u 1 V
0,
u B(x)u=
(5)
with a similar line of logic for u B(x) T u. Now we will consider A(x). We have, for
u L (x(,), u A(x) =0 = u T Au = O. For u || (f()), let = 78% (x), E IR) (0),
we have
u = ((x))=><1V<(>>
0VX
(from strong convexity assumption)
> 0V u (x)
u A(x)u
(6)
0,
(x)
with similar logic for u T "A(x) T u. Combining eq. and eq. we get that
-u [VVhhh(() + (h,(x) 1) u SYEEE R" x0,x**)
N
= u (Vh(x) Vh(x)) u= Σ u (Vh,(x) + Vha(x) u <V {0)
Now, let us make a Lyapunov function V(x): : R - R for h(x) given by
V(x) h(x) h(x)
vxx) = h(xx) (Vh(x) + Vh(x)*) l(x)
Further, have V(x) -> as ||x|| - Co. Further from eq. V(x S 0, with V(x) 0 only when x is an equilibrium of h. Thus, by classical results in nonlinear systems theory, we have that all equilibrium points of å -h(x) are local asymptotically stable, and by LaSalle's invariance theorem we have that the system the continuous time dynamics
x -x((x) converges globally asymptotically to the set of equilibrium points 12 Theorem
4.4].
5. DiBS retains continuous-time guarantees with correct step sizes. We have that the mapping h(x) R" + R is L, Lipschitz for some Ln > 0. Then, using any square summable sequence of step sizes og > 0 such that 00 O = co, Ex=p oz < do retains the global convergence properties for DiBS 4. Chapter 2]. To see the Lipschitzness of h, we have
hx(x)-
hx(y)
Ve (x)
Vy(
es (x))22 ||x x x
1ly - 1
(x)
Velry)
ve(y)
||x ||--x*111
(y) (Ily - xx ||x x (12)
V 878 (x)
(v)
(x)
Ve(()
V
||x ||x-x* 112
+ [ (Ily -x x|x x 20 (12)
[ 1|2
(Ve
22

---

Bounding term II, we have
(y)
II (y))l
y112
||x y
(reverse triangle inequality)
Now for term I, we have
Ve ve(y)
VE (2> (x)
v (x)1l [y))())
V (
Ve (y))la (x) ve(()) + (1 VI (y)
(x) (2
< (V VV (2(())22 = [V Ve(y))l
Ve(x)ll2
Now from μ² strong convexity of (-).
[[V((x)) 2 p² x1
[ I |=|x x*1112
Further, from L smoothnesss of (.), we have [| we have
(e((y)) s b'||x y/1. Thus,
2L n²
K
xx - y
Combining these bounds for I and II, get
2T2
[1a(xx) h,(y)l12
+ +1
||x
y122
/r
Summing over all agents, we have
N
21 11²
Ln
Σ
1+
1=1
Thus, I La Lipschitn
A.3 Proof of Theorem
1. Pareto. The fact that DiBS finds Pareto stationary solutions follows directly from Theorem Pareto stationarity a necessary condition for Pareto optimality, and a sufficient condition when agent costs are strictly convex and twice differentiable [1] 23
2. Invariance. For invariance to strictly increasing monotonic functions, let a nonaffine
transformation g² R - R. (t) > 0 AAA E IR be applied to (x). Let e(x) = have
(g) .g......'''.. N (eN)) (C.).....
Then in the proof of Proposition
( = Vg(e((x)) = =g/ (E(()) V
20
Vē(() (x((x)
(1)22 (x)ll
0f OP'' (N].
Thus, both the pieces of information used for each player by DiBS remains invariant to the transformation for each agent. This leads invariance of DiBS against strictly monotonic nonaffine transformations.
Further, because of monotonicity, arg minx (e((()) arg miny (x)
x
23

---

3. Symmetry. It is trivial to see that DiBS satisfies the axiom of symmetry because the DiBS takes the input from each agent at the same state during each iteration. is invariant to permutations of agents.
4. Independence of Irrelevant Alternatives. We know that DiBS is globally asymptotically convergent the of its fixed points from Theorem T This means that if there only single fixed point, DiBS will have global asymptotic convergence to this point, which satisfies Axiom
B Additional experiments for mediated portfolio management
We include the results for the mediated portfolio management experiment repeated for N = 2, and
5 investor agents. These experiments have similar trends as mentioned in Section 4.2 plots attached here in Figures
The result
Stocks
10
10 Stocks
Relative Emor in Solution
20 Stocks
10
50 Stocks
10
10
10 -3
10-4
10
100
1000
10000
Number Comparisons (Per Agent, Per Iteration)
Figure 3: Repeating the Mediated Portfolio Management experiment for N 2 agents.
Stocks
10
10 Stocks
Relative Error in Solution
000000
Stocks
10
Stocks
10
10
10-3
10-1
10
100
1000
10000
Number of Comparisons (Per Agent, Per Iteration)
Figure Repeating the Mediated Portfolio Management experiment for = 3 agents.
24

---

Stocks
10
10 Stocks
Relative Error in Solution
yp 00
20 Stocks
100
50 Stocks
10
10-2
10-3
10-1
10
100
1000
10000
Number of Comparisons (Per Agent, Per Iteration)
Figure 5: Repeating the Mediated Portfolio Management experiment for N = 5 agents.
Experimental details
C.1 Multi-agent formation assignment implementation details
Parameter values. We choose с = (), 10 and 6 = 0.01. The agents were initialized in circle centered with radius of 3. The value of the group attraction and repulsion values used for the experiment are
if i and are both odd even otherwise
0.1
3
if i and j are both odd or even
Bi
0.9
otherwise.
Based these values, agents want maintain distance of 0.5493 with agents of the same group and distance of 2.7465 with agents of the other group.
Algorithmic Details. DiBS and NBS were both run for 5000 iterations. KSBS
solved in one
shot, as it based on a geometric argument with no iterative scheme. To solve KSBS we minimized the sum of loss improvements y for each agent i, while ensuring equal loss improvements for all agents. This was encoded the objective
C(r) =
7
1
,,.,,..,777
N
1=1
1=1
For NBS and
KSBS
= OVIE [N].
C.2
Mediated portfolio management implementation details
Implementation details. We conducted 100 random initializations for each number of stocks (5, 10, 20, 50). Every random initialization was run for 1, 10, 100, 1000, 10000 comparisons made per agent per iteration. Real life stock data was procured sing the yf ifinnce Python package [2] (under the Apache license). We ensured that the simplex constraints for this example were met by using the following strategies:
Projecting all agent gradients onto the simplex before performing an update.
2. Shrinking the step size by factor of 10 if a step would cause any element in the state to become less than zero. If the step size becomes less than 10-12, 12 we stop the algorithm. The initial step size set to be 0.01.
25

---

For terminating the algorithms, we used the termination condition of either the step size reaching 10 12, or the algorithm completing 1000 iterations.
As mentioned, the box plot was made using 100 random initializations for each number of stocks (5, 10, 20, 50). In the box plots for Figures 2 4 and outliers (dots) were chosen to be data points that were below Q1 - 1.5(Qa- Q1) or above Q3 + 1.5(Q3 Q1). Here, Q1, Q3 denote the first and third quartiles respectively.
C.3 Hardware Details
All experiments were run on a desktop with a 12th Gen Intel(R) Core(TM) 17-12700 12-core CPU,
D On naive bargaining algorithm given in Equation 2
The solution found by the iterates of the naive bargaining algorithm given in eq. satisfy
1. Pareto Stationarity: This is because if its iterates converge at some point we have for (x)(x) eq. that E; 2 O, which satisfies Definition with Bi = 1/N.
2. Symmetry: This is trivial to see because eq. is invariant to permuting the agents' order.
3. Invariance to monotone nonaffine transformations: this follows for eq. (2) from the proof of Proposition
E
Obtaining preferred states using direction oracles
In this section, we include a more in-depth discussion on how one can obtain preferred states using only direction oracles. Recall that each agent provides access to direction oracle OP' (x)
(e()) that specify the direction of steepest descent for agent's 's objective et. Despite not [V
observing or V directly, several results from the zeroth- and first-order optimization literature show that preferred (locally optimal) states can be recovered using only such directional feedback.
simple and widely studied approach to perform gradient descent-like update of the form:
x = X, + 1
where 7) is suitably chosen step size. Methods that use this update, including SIGNSGD [3 and SIGN-OPT (6), have been shown to converge to stationary points for smooth functions. Under Lipschitz and smoothness assumptions, these methods satisfy bounds of the form
[V o
VQ
where is the dimension of state x, T is the number of descent iterations, and the number of sampled directional queries per iteration.
Relation to multi-agent consensus and flocking.
At structural level, the DiBS update may appear reminiscent of distributed consensus flocking dynamics (2I) which also involve averaging normalized direction vectors across agents. However, these methods assume specific inter-agent potential functions and neighborhood graphs that govern attraction and alignment behaviors. In contrast, DiBS does not assume any specific potential function for the agents. Each agent possesses an independent cost function (z),, and the mediator aggregates their direction oracles using dynamic weights that depend on distances to their respective preferred states. Consequently, DiBS generalizes beyond consensus-seeking to general cooperative bargaining framework that aims to achieve Pareto-stationary and fair outcomes rather than spatial alignment or agreement.
26


Reviews:
[{"review_id": "TpudpWAa0s", "reviewer": "Reviewer_Rh96", "summary": "The paper focuses on cooperative bargain games, when utility functions are not available, or different agents' utilities are not comparable. The contributions include: 1) showing that no algorithms with only direction oracle access can find Nash or Kalai-Smorodinsky bargaining solutions for all bargaining games; 2) proposing Direction-based Bargaining Solution (DiBS), an interative algorithm that incorporates agents' distance from preferred state, using only direction oracles. 3) showing that fixed points of DiBS exists and are Pareto stationary.", "questions": "* You mentioned that naive direction oracle-based bargaining can lead to unfair solutions. In experiments, DiBS seems to have more balanced solutions. Is there any theoretical explanation for this?\n* How to find the preferred state with direction oracle access? Intuitively, you could follow the oracle directions. But the algorithm is nonstandard as you don't have the full gradient, so it'll be helpful to explicitly state the algorithm.", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "* Identifies a practical problem of cooperative bargaining games without utility access, which has wide applications with AI proxy agents.\n* Proposes DiBS, which provably achieves Pareto stationarity under standard assumptions\n* The paper is well-writen, and has strong technical contributions.", "was_revised": true, "final_justification": "I'm happy to keep the score, which is already 5. However, I have a low confidence score for my assessment as it is not my area of expertise.", "rebuttal": "Thank you for your comments and review! Please find our responses below.\n\n``You mentioned that naive direction oracle-based bargaining can lead to unfair solutions. In experiments, DiBS seems to have more balanced solutions. Is there any theoretical explanation for this?``\n\nThe naive direction oracle based bargaining method given in equation (2) indeed can result in unfair solutions (as argued in example 2). On the other hand, as correctly observed by the reviewer, our method DiBS indeed results in balanced solutions. The *theoretical explanation* behind this, is that the DiBS algorithm does not have a simple/naive aggregation of direction oracles, instead DiBS can be interpreted as a weighted aggregation of directions, where weights for all agents evolve dynamically throughout the bargaining iterations (given at line 207, Section 3). These weights evolve in a manner which ensures fair/balanced solutions, with agents far away from their desired states having more priority. In comparison, a simple aggregation of directions such as given by equation (2) represent a weighting scheme which does not evolve in a manner which ensures balanced solutions.\n\n\n\n``How to find the preferred state with direction oracle access? Intuitively, you could follow the oracle directions. But the algorithm is nonstandard as you don't have the full gradient, so it'll be helpful to explicitly state the algorithm.``\n\nAs we mention in Section 3.2 (lines 269-279), there are various different methods in existing optimization literature which can be used to find preferred states from just direction oracle, some recent and relevant methods being the references [5,9,12,22,32] in our manuscript. A popular method is to conduct a gradient descent like procedure with the *signum values of the direction oracle*, for example in SignSGD [A], or Sign-OPT [5], having an update of the form $x \\leftarrow x - \\eta\\cdot \\textrm{sign}(g)$, where $g$ is the direction oracle output. These papers show that with a properly chosen step size $\\eta$, such methods enjoy convergence to agents' preferred states. These methods utilize the fact that for smooth functions, the signum transformed gradient will only travel in the wrong direction for a component, if that component is already close to the optimal value.\n\nWe are happy to appropriately modify our manuscript to reflect this discussion, add prior work's algorithm in the appendix and mention the precise convergence rates for these prior methods.\n\n[A] Bernstein, Jeremy, et al. \"signSGD: Compressed optimisation for non-convex problems.\" International conference on machine learning. PMLR, 2018."}, {"review_id": "YFvejmoopn", "reviewer": "Reviewer_S2R2", "summary": "The paper proposes a solution concept for bargaining that is invariant under nonmonotone utility transformations, and show that it enjoys desirable properties. Furthermore, existing concepts do not satisfy all these desiderata simultaneously. On the algorithmic side, the authors show dynamics that asymptotically converge to the concept.", "questions": "1. Could you please let me know if I'm not on the right track with my confusion around L38 described above?\n2. What can be said about non-asymptotic guarantees, especially under discretization?", "limitations": "Yes.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I am not an expert on bargaining, so I will focus mostly on the quality of writing and clarity.\n\nOverall, I found the paper well-written. However, as a non-expert on bargaining, I would have certainly appreciated a bit more information at the very beginning of the paper, if anything to remind the reader of the main challenges of bargaining and the settings it tries to capture.\n\nOn L38, I would have appreciated a more nuanced discussion about how reasonable it is to be unsatisfied with the existing approaches' lack of nonaffine invariance. Under a nonaffine transformation, the relative amount with which an outcome is better than another is not preserved. So, it seems quite unclear to me what, abstractly, we would want to require out of a good bargaining approach. The authors liquidate this quite fast, by saying that \"despite utilities being incomparable due to different nonaffine scalings, the notion of the agents’ most preferred directions remains intact.\" I don't disagree, but why is focusing on direction, instead of scaling, reasonable? And under this relaxed goal, is it obvious that prior approaches behave unreasonably? Up until that point, in the mind of the reader, the only negative regarding the prior approaches is just a lack of affine invariance and the possibility of them \"favor(ing) one agent disproportionately\". Nothing has been said about their inability to try to move, in some sense, in the direction most preferred by each player.\n\nI found the overall discussion on relations with the existing literature well done. \n\nMinor comments:\n- Reference [2]: I think the capitalization of \"Yahoo! Finance\" and \"API\" is probably incorrect\n- Reference [4]: I don't speak German, but I believe they capitalize nouns. If so, it might be worth double checking that the capitalization used is correct\n- Citations: A quite large number of references point to arXiv. Perhaps this is correct, but I find it somehow unusual. Could you please double check that you are citing the most relevant version (for example, if a paper has been accepted in proceedings or into a journal, please provide a citation to that published version, or a note on why the arXiv version is the correct version you refer to).", "was_revised": true, "final_justification": "The author's rebuttal has helped clarify a point of confusion regarding line 38, as mentioned above. The authors have shown goodwill to fix the typos and minor issues I raised. I maintain a positive opinion of the paper. As mentioned in the review, I am not an expert on bargaining, and my review focused mostly on the quality of writing and clarity.", "rebuttal": "Thank you for your review and comments! Please find our responses below.\n\n``Could you please let me know if I'm not on the right track with my confusion around L38 described above?\n``\n\nWe thank the reviewer for bringing up this point and allowing us to clarify. The reason why it is desirable for a bargaining algorithm (and solution) to be invariant to nonaffine scalings of agents' objectives is because it destroys any incentive for those agents to exaggerate the degree to which they prefer one outcome over another. However, the chain rule reveals that - for any (potentially unknown) nonaffine but monotone scaling function $\\sigma: \\mathbb{R} \\to \\mathbb{R}$ and objective function $\\ell^i$ for agent $i$ - $\\nabla \\sigma(\\ell^i(x)) = \\sigma'(\\ell^i(x)) \\nabla \\ell^i(x)$ which implies that $\\nabla \\sigma(\\ell^i(x))$ is parallel to $\\nabla \\ell^i(x)$ (and thus, while the normalized gradients are equal, algorithms like NBS and KSBS which use the unnormalized gradient now get changed values). This argument is currently stated in the proof of Proposition 1 (line 446 in the Appendix), but we will factor it into a standalone Lemma and reference it in the main text in order to improve clarity.\n\nFinally, we demonstrate in Example 1 and Proposition 1 that existing approaches such as NBS and KSBS can fail to recover the same solution when they lack access to the true (pre-transformation, un-exaggerated) objective functions. By exaggerating its reported objective values, therefore, one agent can easily bias the result. On the other hand, since the ordinal comparisons between points remain the same, DiBS is unaffected by this type of misreporting.\n\nWe believe that the reviewer may also be suggesting that existing bargaining approaches could, in principle, handle non-affine transformations if they knew the transformation itself and could apply its inverse to recover the underlying objectives. However, the key feature of DiBS is that it assumes the mediator only has access to a direction oracle for each agent's objective function. In particular, the mediator does not observe the actual objective values and is agnostic to possible (non-affine) objective transformations. Consequently, DiBS identifies the same solution for any monotone transformation.\n\n``What can be said about non-asymptotic guarantees, especially under discretization?``\n\nThank you for bringing this up. We agree that it would be useful to understand DiBS's nonasymptotic convergence behavior. Unfortunately, our analysis to date has not led to any meaningful results. We certainly intend to continue, but at this point we must defer that effort for future work.\n\n``Other minor comments that the reviewer brings up:``\n* On capitalization in references: Thank you for pointing this out, we will edit references [2] and [4] appropriately.\n* Arxiv citations: Thank you for this observation, we will replace the citations for those papers who have published versions available."}, {"review_id": "0d8EJhshEM", "reviewer": "Reviewer_PReA", "summary": "This paper studies cooperative bargaining games where mediators lack access to agents' utility values but only have query access to a direction oracle that returns each agent’s normalized utility gradient which is their most preferred direction in the decision space. Existing solutions like Nash (NBS) and Kalai-Smorodinsky (KSBS) bargaining require utility values or gradients and fail under nonaffine utility transformations. The authors prove that no algorithm using only direction oracles can recover NBS or KSBS.  The authors propose Direction-based Bargaining Solution (DiBS) in which mediator iteratively updates the state using agent’s preferred state which is obtained via precomputation or oracles. This weights each agent’s direction by their distance to their ideal state by prioritizing agents farther from their goals and uses only direction oracles and preferred states. Under convexity and smoothness assumptions, DiBS converges globally to Pareto stationary points. DiBS is robust to strictly increasing nonaffine utility transformations, which is a preferred invariance property not satisfying by NBS/KSBS.  It also satisfies Pareto stationarity, symmetry, and independence of irrelevant alternatives under uniqueness assumption.  In practice, direction oracles can be estimated from binary comparison oracles, like agents answer yes or no to state proposals. This is validated in two example domains of nonconvex multi-agent formation and stock portfolio allocation with diverse investor preferences.  Overall, this paper is a significant contribution to addressing problems related to human-AI collaboration, privacy-aware systems, or preference learning, etc. where utilities are hard to specify.", "questions": "- The prosed method requires knowing agents’ ideal states. How robust is it to approximate states and noisy comparisons? The authors mention pre-computation, but I think it might be useful to have some sensitivity analysis.  \n- Classical bargaining uses disagreement points to anchor negotiations which the proposed method omits. Does it weaken fairness in asymmetric scenarios?  \n- How does the proposed method compare to simple heuristics, like weighted averaging of directions, in speed, fairness, robustness?\n- Could the proposed method extend to settings where agents’ goals evolve during bargaining?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n- This work has significant novelty. Prior works have used directional information but are limited to two agents or produces unfair outcomes. \nThe proposed method seems to be the first multi-agent bargaining solution with direction oracles that guarantees fairness and axiomatic properties. The focus on nonaffine invariance is also new.  \n- The theoretical proofs seem sound. It is intuitive that DiBS fixed points correspond to Pareto stationary points, and invariance to nonaffine transformations holds by construction.  \n- Experiments show that the proposed method achieves balanced solutions comparable to NBS and KSBS, it is indeed robust to nonaffine transformation and works well with comparison based gradient estimates.  \n\nWeaknesses:\n- The theoretical proofs of global convergence assume strong convexity, while experiments show that event formation converges even for non-convex cost. However, this is standard for theoretical analysis in this topic. The model also assumes static preferences.\n- Experiments lack comparison with simple heuristics, like weighted averaging of directions.", "was_revised": true, "final_justification": "This paper presents strong theoretical results. The authors have addressed all my questions during the rebuttal.", "rebuttal": "Thank you for your review and comments! Please find our responses below.\n\n``The prosed method requires knowing agents’ ideal states. How robust is it to approximate states and noisy comparisons? The authors mention pre-computation, but I think it might be useful to have some sensitivity analysis.``\n\nThank you for this interesting question! We interpret your question as having two parts:\n1. **How accurately can one calculate preferred states using noisy comparisons/ noisy normalized gradients estimates?**\n    We remark that prior works in single agent optimization have a rich variety of methods which can be used to estimate preferred states with noisy comparisons/normalized gradients. \n* In case of noisy comparisons, one can use the method in [A] to find the preferred state up to desired accuracy, with a known query complexity of achieving a state within a certified error tolerance (see Theorem 2, [A]). \n* In case of accurate comparisons but noisy normalized gradients, one can use methods which work with noisy gradient directions like Sign-OPT [B] or Sign-SGD [C], which conduct a gradient descent like procedure with the signum values of the direction oracle and show that these methods converge to preferred states with suitable step size selection. They utilize the fact that for smooth functions, the signum transformed gradient will only travel in the wrong direction for a component, if that component is already close to the optimal value. For example, with $Q$ comparisons per iteration, after $T$ iterations, even by using imperfect and noisy normalized gradient estimates, SignOPT yields a state $x$ such that $$\\mathbb{E}[\\|\\nabla \\ell^i(x)\\|_2] = \\mathcal{O}\\left( \\frac{\\sqrt{n}}{\\sqrt{T}} + \\frac{n}{\\sqrt{Q}} \\right).$$ Another approach, which uses a cutting plane/ellipsoid based method to obtain preferred states is [D], which iteratively identifies and rejects certifiably sub optimal regions of the state space, to find a preferred state upto desired accuracy.\n2. **How robust is our method DiBS to noisy estimates of preferred states $x^{*,i}$?**\nThank you for this interesting question. We tried to conduct some analysis for this question, but our efforts have not yet led to a meaningful result, and exact theoretical robustness guarantees remain an interesting direction for future work. However, we have conducted some empirical studies on the nonconvex multi-agent formation experiment of Section 4.1 (\nwhere due to the symmetry of the problem, noisy agent preferred states can substantially change the problem geometry). We noticed that qualitatively the formations resulting from the true and noisy preferred states are visually quite similar and, as expected, the noisy state formation gets closer to the original solution as the approximation gets better and noise decreases. We are happy to share the quantitative results of this empirical study, and also revise our manuscript to include this study.\n\n    \n    \n``Classical bargaining uses disagreement points to anchor negotiations which the proposed method omits. Does it weaken fairness in asymmetric scenarios?``\n\nThe reviewer is correct in pointing out that our proposed approach does not consider improvement over a disagreement point. Instead, the notion of fairness we consider is that the bargaining solution not be too close to any one particular agent's preferred state -- this means in scenarios where one agent starts close to their preferred state (i.e., the disagreement point is close to their preferred state), our approach specifically de-emphasizes their contribution to the update, and drives the update to a less favourable state for this agent, while making the solution more favourable for other agents. We believe that we can adjust the DiBS update rule to account for disagreement points: either by introducing a term that scales directions based on how close the disagreement point is to each agent's optimum, or by projecting the DiBS update into the space of mutually improving directions. We believe this can be an exciting direction for future work, and thank the reviewer for raising this comment!\n\n``How does the proposed method compare to simple heuristics, like weighted averaging of directions, in speed, fairness, robustness?``\n\n*We note that the heuristic of a simple weighted averaging scheme where the weights are constant does not act as a valid bargaining solution, because the iterates of such a simple heuristic need not converge.* As an example, consider the bargaining game $\\mathcal{B}_{[0,1]}([x^2, (x-1)^2], [1,1])$ given in Example 2 of our paper, but instead of using equation (2), consider using a weighted averaging update rule which weighs both the gradients by $a, b$ respectively, where $a\\neq 0, b\\neq 0, a+b = 1$. Let $a>\\frac{1}{2}$ without loss of generality, then we have that the iterates of such an update rule do not have equilibrium for any $x\\in[0,1]$, and the updates never converge, because the iterates either want to move to 0 (agent 1's preferred state) for $x\\in(0,1]$, or to 2 (agent 1's preferred state) when $x=0$. We hope this also clarifies why we do not have experimental comparisons with such simple heuristics, which was brought up by the reviewer in the weaknesses section.\nThus, it is not possible to compare DiBS on robustness or fairness against such weighted average schemes. \n\nFurther, we remark that DiBS can be viewed as a non-trivial weighted averaging of directions scheme, but where the weights evolve dynamically across iterations. DiBS provides one way to construct weights using only information available through comparisons.\n\nRegarding the speed of DiBS, assuming that preferred states $x^{ *,i}$ are found as a precomputation step, calculating the weights $||x-x^{ *,i}||$  involve only 1 vector subtraction and 1 norm calculation, which leads to an efficient linear time complexity of $\\mathcal{O}(nN)$ per iteration, where $n$ is the state dimension and $N$ is the number of agents. This is in addition to the complexity of calculating the normalized gradients, which will also be incurred by any algorithm which utilizes normalized gradients. \n\n``Could the proposed method extend to settings where agents’ goals evolve during bargaining?``\n\nThank you for this interesting question. As of now, the proposed approach only considers the setting where agent costs $\\ell^i$ and preferred states $x^{*,i}$ are fixed, and do not evolve with time. Extending the approach to accomodate evolving agents' goals is an direction for future work, and we hypothesize this might consist of constructing updates which converge on a faster time scale than the timescale on which the agent goals evolve.\n\n[A] Jamieson, Kevin G., Robert Nowak, and Ben Recht. \"Query complexity of derivative-free optimization.\" Advances in Neural Information Processing Systems 25 (2012).\n    \n[B] Cheng, M., Singh, S., Chen, P. H., Chen, P. Y., Liu, S., & Hsieh, C. J. Sign-OPT: A Query-Efficient Hard-label Adversarial Attack. In International Conference on Learning Representations (2020).\n\n[C] Bernstein, Jeremy, et al. \"signSGD: Compressed optimisation for non-convex problems.\" International conference on machine learning. PMLR, 2018.\n\n[D] Karabag, Mustafa O., Cyrus Neary, and Ufuk Topcu. \"Smooth convex optimization using sub-zeroth-order oracles.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. No. 5. 2021."}, {"review_id": "AbKhPPRktP", "reviewer": "Reviewer_XLAd", "summary": "The paper presents a cooperative bargaining solution satisfying Pareto stationarity, invariance to monotonic utility transformations, symmetry, and IIA. This solution concept can be found with a new protocol, DiBS, which has access to only utility gradients for each agent. This expands beyond traditional approaches, NBS and KSBS, which require more information from the agents in order to compute. Direction oracles can be found practically using comparison queries. Experiments demonstrate the validity of DiBS and some failures by the NBS and KSBS solutions when utilities are scaled in a non-affine manner.", "questions": "- On line 274 - can you please clarify or cite a specific query complexity for estimating the normalized gradient?\n- Can you comment on how theoretically accurate a direction oracle approach would be for computing DiBS? This question appears to be what is experimentally validated through Sec 4.2.\n- In Sec 4.2, can you please clarify how this example is a cooperative bargaining game? Whereas it was clear how the example in Sec 4.1 compared DiBS to NBS and KSBS, I'm not immediately seeing how you're computing DiBS, given the error on line 337.\n- (Extensions) As you mention on line 269, \"Optimization solely using comparison oracles is a well-studied problem in the single-agent setting.\" What you suggest in this paper seems like an application of comparison/direction oracles into the multiagent space. I'm wondering what other types of problems you think this technique could be applied to beyond cooperative bargaining.", "limitations": "NA", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nOverall the paper presents an interesting formulation of the bargaining game and noteworthy extension, where the mechanism only has access to gradients as opposed to full utility information from the agents. The paper presents the problem coherently, demonstrates two theorems satisfied by DiBS, and how to feasibly obtain gradient information from agents. I am not left with any significant questions after reading this work.\n\n\nWeaknesses:\n\nMy main concern of the paper is only if DiBS (line 207) has already introduced in the multiagent control systems literature. I can't point to a specific paper, but I would think that the solution {normalized gradient weighted by individual agent loss} would have already been proposed, perhaps pertaining to the problem of distributed averaging (related to Flocking by Olfati-Saber, 2006). Are you familiar with this span of literature?\n\nAlso, global asymptotic convergence may not be the most surprising finding  given that the loss functions are assumed to be smooth (Thm 1.4) and convex (Assumption 2). This is noted by [3, Chapter 2] on line 491. But overall this paper does seem like a worthwhile contribution to the literature.\n\n\nMinor:\n- Line 114: Please explain or cite why these iterates converge to NBS.\n- Please elaborate on how SignSGD can be used to compute the most preferred states, on Line 218, for readers who are not familiar.\n- Why is proof of Theorem 1 a proof \"sketch\" (line 452)?", "was_revised": true, "final_justification": "The rebuttal sufficiently addressed my comments. I will keep my score positively as-is.", "rebuttal": "Thank you for your review and comments! Please find our responses below.\n\n``My main concern of the paper is only if DiBS (line 207) has already introduced in the multiagent control systems literature ...... perhaps pertaining to the problem of distributed averaging (related to Flocking by Olfati-Saber, 2006). Are you familiar with this span of literature?``\n\nThank you for pointing out this line of literature! There are some similarities but also noticeable differences between the two.\n\nAs described in the paper you referenced [A], flocking could be achieved using a potential function to be specified between agents and using the averaged unnormalized gradients of these potentials as the update rule. When this potential function is piece wise linear in agents' positions, then the flocking algorithm update condenses to having a weighted averaging of directions. In [A], the author considers a potential function that is very close to a piecewise linear function of the distances between the agents (see Fig. 3 of [A]). Consequently, their update rule (averaged unnormalized gradients of the potential functions) boils down to averaging gradient directions. In contrast, DiBS does not assume any structure of the agent objectives (potential functions in flocking), and its updates will always be dictated by directions regardless of the agent objectives. Finally, we note that DiBS dynamically weights these directions according to the agents' respective distances to their optima. \n\nWe are happy to updated our related works section to reflect this discussion.\n\n``On line 274 - can you please clarify or cite a specific query complexity for estimating the normalized gradient?``\n\nThis complexity varies with the method one wants to use. For example, ST-CR (reference [16] in our manuscript) guarantees that after $k$ comparisons to estimate a $n$ dimesnional normalized gradient, either the agent is at a near-optimal point (i.e., small gradient magnitude), or the angle between the true normalized gradient $\\nabla \\ell$ and the estimated normalized gradient $\\nabla \\tilde \\ell$ is bounded as\n$$\\angle(\\nabla \\tilde \\ell, \\nabla \\ell) \\leq \\sin^{-1}(\\sqrt{1- \\frac{1}{2n}}^{\\lfloor{\\frac{k-n}{n-1}\\rfloor}}).$$\n\n``Can you comment on how theoretically accurate a direction oracle approach would be for computing DiBS? This question appears to be what is experimentally validated through Sec 4.2.``\n\nThank you for this interesting question. Based on the context from previous question, we believe that the reviewer intends to ask \"how theoretically accurate a *comparison* oracle approach would be for computing DiBS?\" As we mentioned in the previous question, using the comparison oracle, the direction can be estimated to any desirable accuracy, and one may potentially show that the update direction of DiBS using the comparison oracle will have bounded error with respect to DiBS using the exact directions. However, this is non-trivial and providing a more formal theoretical statement to this end remains a direction for future work. we present empirical evidence of promising robustness properties of DiBS against such errors in Section 4.2, as the reviewer correctly points out.\n\n``In Sec 4.2, can you please clarify how this example is a cooperative bargaining game? Whereas it was clear how the example in Sec 4.1 compared DiBS to NBS and KSBS, I'm not immediately seeing how you're computing DiBS, given the error on line 337.``\n\nThis example in question refers to the mediated portfolio management experiment.\n\n**Purpose of Portfolio experiment.** As we mention above, the purpose of experiment in Section 4.2 is to see how reliably can DiBS solution be computed using only comparison oracles, i.e., using only $\\mathcal O_{\\mathbf{\\ell}}^{\\mathcal C, i}$ introduced in equation 3 to approximate $\\mathcal O_{\\mathbf{\\ell}}^{\\mathcal D, i}$ introduced in equation 1. The error metric mentioned in line 337 is used to measure the quality of solution produced by DiBS using only comparisons. In this example, we do not compare DiBS against NBS or KSBS, but demonstrate a practical implementation of DiBS using comparisons.\n\n**How is the portfolio experiment a bargaining game?** Each of the N investors is an agent. The statespace dimension is the number of stocks being considered, and each component of the state represents what fraction of the portfolio should be allocated to a particular stock. All agents pool their investments into a joint portfolio. The mediator (who managing the portfolio on behalf of investors) must conduct a bargaining process to find an portfolio allocation which is amenable to all agents, each of whom have a quadratic cost given by Markowitz portfolio theory (reference [13] in our paper), $\\ell^i(x) = x^\\top \\Sigma^i x - \\lambda^i \\mu^{i\\top} x$. The quantities $\\Sigma^i, \\mu^i$ are computed from real stock data taken over different time periods for each agent, reflecting differing market perspectives for each agent. The quantity $\\lambda^i$ quantifies the risk-reward tradeoff coefficient for every agent. This is the set up for the bargaining game. We solve this game for 100 different randomly sampled time intervals of stock data and randomly sampled $\\lambda^i$ for each agent, (leading to 100 $(\\Sigma^i, \\mu^i, \\lambda^i)$ tuples) and each of these games (initialized at $x_0$) is solved by the DiBS algorithm in two ways\n* Directly using the true normalized gradients of the quadratic cost above in the DiBS updates (leading to solution $x^\\dagger_{dir}$).\n* Using only comparisons to estimate the normalized gradients, using only $1, 10, 100, 1000, 10000$ comparisons per iteration per agent in the DiBS updates (leading to solutions $x^\\dagger_{comp}$).\n\nOur aim is to see how different the true and estimated DiBS iterates are, thus the error metric on line 337 that the reviewer mentions is used. It shows the relative error, given by $\\frac{\\|x^\\dagger_{dir} - x^\\dagger_{comp}\\|}{\\|x^\\dagger_{dir} - x_0\\|}.$\nThe numerator measures how close the comparison based solution is to the direction based solution. The denominator is acting as a normalizer to account for the size of state space (and also to account for the fact that $x_0$ changes across initializations). The statistics are reported over the 100 game initializations, each $x_0$ being different.\nWe hope this clarifies how the protfolio experiment in Section 4.2 is a bargaining game. We are happy to provide any further clarifications required.\n\n``Extensions - I'm wondering what other types of problems you think this technique could be applied to beyond cooperative bargaining.``\n\nThanks for this interesting question. One interesting direction we think can be applying such comparison/oracle based techniques for the flocking problem that you mentioned. It will be very interesting to see if in a decentralized setting, self interested agents can employ such oracles as an alternative to predefined potential functions.\n\n\n\n\n\n``Minor comments pointed by reviewer``\n* **Line 114:** thank you, we will add appropriate citation for the NBS iterates converging to desirable point.\n* **Please elaborate on how SignSGD can be used to compute the most preferred states on Line 218:** SignSGD [B] (and related inspired algorithms) use a sampling scheme to estimate a normalized gradient $\\tilde g$, and then use a gradient descent like procedure with the signum values of the normalized gradient estimates, $x \\leftarrow x - \\eta \\cdot\\text{sign}(\\tilde g)$. They utilize the fact that for smooth functions, the signum transformed gradient will only travel in the wrong direction for a component, if that component is already close to the optimal value. As such, these methods converge to preferred states with appropriately chosen step sizes $\\eta$. For example, one method inspired from SignSGD, the Sign-OPT algorithm, (reference [5] in our paper) samples random directions $u_1, ..., u_Q$ and queries whether the function value increases or decreases along each direction via the comparison oracle. The sign information is used to construct an estimate of the gradient direction of a function $\\ell^i$, $\\hat g^i$ as\n$\\hat{g}^i = \\frac{1}{Q} \\sum_{q=1}^Q \\mathcal O^{\\mathcal O, i}_{\\mathbf \\ell}(x + \\epsilon u_q, x) \\cdot u_q,$ where $Q$ is the number of comparisons and $\\epsilon>0$ is a small smoothing parameter.\nThis gradient estimate is then used to perform a gradient descent type update to estimate $x^{*,i}$ as $x \\leftarrow x - \\eta \\hat{g}^i$. Despite the lack of gradient magnitude information, the method achieves a convergence rate of $\\mathbb{E}[||\\nabla \\ell^i(x)||_2] = \\mathcal{O}\\left( \\frac{\\sqrt{n}}{\\sqrt{T}} + \\frac{n}{\\sqrt{Q}} \\right)$ where $n$ is the state dimension, $T$ is the number of iterations, and $Q$ is the number of sampled directions/comparisons made per iteration. We will update the manuscript to reflect this discussion.\n* **Why is proof of Theorem 1 a proof \"sketch\" (line 452)?** The sketch consists of only the first paragraph (lines 452 - 456). The rest is the full proof. We will modify our manuscript to make this more clear. Thank you for pointing this out.\n\n\n[A] Olfati-Saber, Reza. \"Flocking for multi-agent dynamic systems: Algorithms and theory.\" IEEE Transactions on automatic control 51.3 (2006): 401-420.\n\n[B] Bernstein, Jeremy, et al. \"signSGD: Compressed optimisation for non-convex problems.\" International conference on machine learning. PMLR, 2018."}]

Author rebuttal:

Meta-review: This submission considers cooperative bargain games. In particular, it studies the case when utility functions are not available, or different agents' utilities are not comparable. The following main contributions are contained in the submission:
1) It is shown that no algorithm with only direction oracle access can find Nash or Kalai-Smorodinsky bargaining solutions for all bargaining games.
2) The authors propose the concept of a Direction-based Bargaining Solution (DiBS), an iterative algorithm which uses only direction oracles, and reasons about every agent’s distance from their preferred state throughout the bargaining process.
3) It is shown that fixed points of DiBS exist and are Pareto stationary (under strong convexity and smoothness assumptions).

All reviewers are very positive about this submission, and all remaining questions could be clarified in the discussion such that no severe weaknesses remain. The strengths are the following: The studied problem is of practical interest in several settings, including, e.g., human-AI interactions. The technical contribution has significant novelty: While prior works have used directional information limited to two agents or produces unfair outcomes, the proposed method seems to be the first multi-agent bargaining solution with direction oracles that guarantees fairness and axiomatic properties. The paper is very well-written. Furthermore, the experiments show that the proposed method achieves balanced solutions comparable to NBS and KSBS, it is indeed robust to non-affine transformation and works well with comparison based gradient estimates.
Decision: Accept (poster)