acceptodds
Under review as a conference paper at ICLR 2027

Learning to Bargain through an Allocation-Sensitive Value Bridge

Abstract

Learning to bargain within a larger sequential decision problem requires agents to identify which exchanges to make and which proposals others will accept. When the value of an exchange is endogenous to the surrounding task, agents face sparse and high variance reward signals during bargaining. We introduce a hierarchical reinforcement-learning framework that addresses this by learning an allocation-sensitive value bridge that provides immediate post-bargaining feedback without prescribing agent behavior or relying on negotiation demonstrations. We test this framework in a four-player variant of the board game Settlers of Catan with two independently seeded self-play league lineages. Our experiments demonstrate that agents trained with the value bridge win more often against common opponents, reach agreement more often, and rely more on negotiated player exchange. This performance improvement is attributable to gains in bargainer ability. Ablations show that without the value bridge the bargainer loses selectivity, performs no better than a random bargainer, and the complete agent wins well below par. These results show that economically recognizable bargaining behavior can emerge from task-oriented self-play using a learned interface between negotiation and long-horizon control.

Primary area:
reinforcement learning
Keywords:
reinforcement learning, multi-agent systems, hierarchical reinforcement learning, bargaining, negotiation, self-play, Settlers of Catan

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_DjqoOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies bargaining embedded in a long-horizon task. It models the environment as two linked stochastic games. A macro policy controls the outer game and decides when to start bargaining, and a separate bargaining policy makes and answers proposals. The agents are neural network policies trained from scratch with PPO in self-play. Bargaining uses structured propose, accept and counteroffer actions. Experiments use four-player Catan with two PPO league lineages. The update-450 agent beats common opponents 9 to 12 points more often than the update-50 agent. Policy swaps attribute this gain to the bargainer, while the macro policy shows no detectable improvement. Agreement rates and player-to-player trades rise. In a six-point variant, replacing the bridge with a full-state critic difference or with a completion bonus alone leads to near-universal acceptance and a win rate of 8.6% to 11.7%.

Critical strengths

When the value of a trade depends on the rest of the task, passing long-horizon value to a bargaining sub-policy is a real credit-assignment problem, and the paper states it clearly. The evaluation is statistically careful. All comparisons use common random numbers and paired bootstrap intervals, and the crossed policy-swap design attributes gains to specific components. The authors are candid about limitations, including that the intervals reflect gameplay noise rather than seed variance. The placement analysis and the record of failed training runs are useful diagnostics.

Critical weaknesses

W1. The auxiliary critic is trained on a reward that includes the potential Φ\Phi, which is itself a hand-designed resource valuation based on build costs. Its inputs are also hand-picked resource and score features. The bridge signal C(post)−C(pre)C(\text{post}) - C(\text{pre}) may therefore largely approximate ΔΦ\Delta\Phi, which is a fixed pricing rule. This contradicts the claim of "no prescribed exchange values".

W2. The ablation uses a reduced six-point game, one seed per ablation arm, and only updates 50 and 100. The full-state arm is evaluated at update 50 only. The experiment is not enough.

W3. All arms share a completion bonus that is never defined. The collapse to near-universal acceptance is most directly explained by this bonus dominating the reward, not by the absence of the bridge. A no-bonus control is missing, and the development runs in A.13 use different settings and cannot replace it.

W4. There are no external opponents and no strong baselines. All opponents come from the same training population, with no fixed external agent such as a rule-based bot. The bargainer may simply exploit the acceptance habits of co-evolved opponents. The only bargainer baseline is a random bargainer, which the authors admit trades destructively.

W5. Novelty is limited and related work is missing. Rewarding a sub-policy with the change in a learned value function is common in hierarchical RL. In task-embedded negotiation, Diplomacy agents already evaluate agreements with learned value functions (Kramár et al., 2022; Meta FAIR, 2022), and the paper does not discuss them. The two-level stochastic-game formalism in Section 3 is not used for any result.

[1] János Kramár, Tom Eccles, Ian Gemp, Andrea Tacchetti, Kevin R. McKee, Mateusz Malinowski, Thore Graepel, and Yoram Bachrach. Negotiation and honesty in artificial intelligence methods for the board game of Diplomacy. Nature Communications, 13:7214, 2022. doi: 10.1038/s41467-022-34473-5.

[2] Meta Fundamental AI Research Diplomacy Team (FAIR), Anton Bakhtin, Noam Brown, et al. Human-level play in the game of Diplomacy by combining language models with strategic reasoning. Science, 378:1067–1074, 2022. doi: 10.1126/science.ade9097.

Questions for authors

Q1. What results do a βΔΦ\beta\Delta\Phi-only bargaining reward and a bridge trained with β=0\beta = 0 give?

Q2. What is the completion bonus? How do the full method and the ablation arms behave without it? Do the full-state arm and the full method use the same normalization?

3 comments

Thank you for your excellent feedback -- we found many of your suggestions valuable and will work to incorporate them.

W1 / Q1 (bridge ≈\approx potential). Three points. (1) The two signals are weakly related. We measured this directly on the paper's own update-400 games (15,214 executed trades involving the evaluated agent). The change in the potential explains 12% of the variance of the bridge signal; the best possible fixed per-resource price list explains 7%; on bank trades, where the price is fixed by rule, those explain 2%. We also note that potential-based reward shaping (PBRS) enters the critic's target with a negative sign (a perfectly fit critic equals the win value minus 0.2 Φ0.2\,\Phi), so the correlation we measure is not an artifact of training on Φ\Phi. We will replace "no prescribed exchange values" a more precise statement: the bargainer's reward contains no fixed exchange values; the PBRS, derived from the build-cost table, contributes to the critic's training and explains a small share of the signal the bargainer sees. (2) The learned signal conditions on information the potential does not. The critic reads every player's holdings, so the reward for a trade includes what the trade does to the counterparty's position: that term is non-zero in 47% of the agent's trades and flips the sign of the reward in 6%. The critic's value also moves for third parties, whose own potential cannot move (median ∣\dv∣|\dv| 0.042 against 0.134 for the traders), and the identical exchange, three wheat for one ore, is valued anywhere from −0.06-0.06 to +0.29+0.29 depending on the state. A potential of the agent's own hand gives that exchange one value in every state. (3) The experiments you suggested. We are in the process of training a bargainer rewarded with the potential alone and a bridge with no potential anywhere in its training (one fresh seed each, the published budget) and evaluated both at updates 50 and 100 against the same control seeds. We will include their results in an updated PDF by 16 November and in the final version.

W3 / Q2 (completion bonus). The completion bonus is 0.005 per executed proposal. The bridge reward is normalized to an RMS of 0.05 and clipped at $\pm$0.15, so the bonus is one tenth of a typical bridge reward and one thirtieth of the largest. All arms, including the full-state arm, use the same normalizer and target. A no-bonus arm (fresh seed, same budget) wins 26.6% [21.5,32.3] at update 50 and 25.8% [20.8,31.5] at update 100, against the bridge's 25.4% and 27.3%, with a learned-minus-random contrast of +13.7+13.7 at both updates. The bonus is not the mechanism. The collapse of the sparse arm comes from the absence of a per-trade signal that discriminates between trades, not from a bonus rewarding any trade. The definition and the normalization will now be in the text.

W2 (ablation scope). The revised paper reports five arms, three of them on fresh seeds, at updates 50 and 100 (150 where available), including the two cells missing from the submission (sparse at update 150: 15.6% [11.7,20.6]; full-state at update 100: 7.8% [5.1,11.8]. One fresh seed per arm, matched to a three-seed control at the same update, and the six-point game remain limitations and are stated as such. Six points is where every arm could be trained from scratch and matched to that control; a ten-point arm costs about three weeks on five nodes. The ten-point arms mentioned above are the first step at closing that gap.

W4 (external opponents). We agree a fixed external opponent would strengthen the evaluation, and we do not have one: the available Catan bots (the JSettlers robot, Catanatron's players) live in other engines with different trading protocols and cannot be dropped into ours. We add this to limitations. Two observations bear on the concern that the bargainer exploits co-evolved acceptance habits. First, the Panel B opponents come from an independently seeded league run that the evaluated agent never trained against, and the bargainer effect there is the same size as against its own run (+23.4+23.4 and +25.8+25.8 points over a random bargainer). Second, the effect scales with the opponents' bargaining ability rather than being a fixed habit: against tables whose bargainers are early checkpoints the agent gains a further +10.9+10.9 [3.5,18.4] and +13.3+13.3 [6.6,20.3] points.

W5 (novelty, Diplomacy, Section 3). We now cite Kramar et al.\ (2022) and FAIR (2022). Both evaluate agreements with a full-state value model trained at large scale, the latter with human dialogue data. Our question is the complementary one: when the full-state value difference is too small to train a bargainer from scratch (our full-state arm: 7.8--8.6%, no better than random), a low-dimensional allocation-sensitive critic restores a usable signal. On Section 3: the bridge is the difference of the surrogate value across the bargaining subgame defined there; we now state the measured quantities in those terms and shorten the rest.

Thank you again. The revised PDF now contains the experiments you asked for.

Q1 (potential-only reward; bridge with β = 0). At ten points (fresh seed per arm, through update 250), a bridge trained with no potential anywhere is level with the full league agent at update 250 (paired: −3.9 [−10.5, 2.7] and −2.0 [−8.2, 4.3]). A bargainer rewarded with the potential alone keeps pace through update 200 and then falls behind (−6.2 [−12.9, 0.4] and −7.4 [−12.9, −2.0]). Inside the fixed update-400 macro policy, the PBRS-only bargainer is behind the co-trained bargainer (−4.3 [−10.2, 1.6] and −9.4 [−15.2, −3.5]), while the bridge without PBRS is level (+5.1 [−0.4, 10.5] and −5.5 [−11.7, 0.8]). The learned signal does not need the potential, and the potential alone does not match it.

W1. Over 15,214 executed trades, the change in the potential explains 12% of the variance of the bridge signal, the best fixed per-resource price list 7%, and bank trades 2%; the two signals disagree in sign on 29% of trades, and the opponents' holdings contribute a non-zero term in 47%. The text now states precisely that the potential enters only the critic's training target, not the bargaining reward.

W3 / Q2. The completion bonus (0.005, one tenth of the normalized bridge reward's RMS target) and the shared normalizer are now defined in the appendix. A no-bonus arm wins 26.6% at update 50 against 25.4% for the full recipe.

W2 / W5. The six-point ablation now reports updates 50–150 for all arms, and the ten-point arms above extend it; one seed per arm is stated as a limitation, and the arms are continuing to update 400. Kramár et al. (2022) and FAIR (2022) are now discussed in Related Work.

We hope this addresses your main concerns, and would be grateful if you would consider them in your final assessment.

I would like to thank the additional experiment results provided by the authors. However, I believe the novelty is limited as stated by reviewer DQ1Q. I would like to see more realistic scenarios to be studied in the future version of the paper. Therefore, I remain my score.

Reviewer_MpJmOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper proposes a "allocation-sensitive value bridge" for sequential decision-making problems that have bargaining games embedded within them applied to the canonical example Settlers of Catan. The full game is decomposed into a macro-game, which controls non-bargaining actions, and bargaining subgames that take place between steps of the macro game and separately. The main focus is on training a surrogate value function for the bargaining game, which uses a lower dimension feature space and potential-based reward shaping, because the difference in macro-level value function is too small (or provides too little information). Many experiments are run that demonstrate improved bargaining leading to higher win rate and specifically emergence of successful bargaining behavior (more accepted deals with other players and less counter-proposals).

Critical strengths

The paper addresses a particularly difficult setting of a mixed-motive multiplayer competitive setting with bargaining subgames. The solution to the credit assingment problem (allocation-sensitive value bridge) makes sense, and seems to work quite well. Altogether, the approach that decomposes the problem into macro-game control and bargaining subgames, separate surrogate value function learned with lower-dimensional features and potential-based reward shaping, game-theoretic RL training regime.. is a natural fit for this class of games.

There are several different experiments that support that bargaining is improved (and that the improved bargaining is what is most important.

From Section 5.3 Emergent Bargaining Behavior. "These descriptive patterns are economically recognizable but are not prescribed by the reward design: neither the shaping potential nor the completion bonus specifies an agreement rate, counteroffer frequency, or division of trade between the bank and other player". This is true, and this whole section was a good take-away from the results and approach.

The paper is well written and easy to follow, up to Section 5 (several comments regarding clarity of Section 5 can be clarified by questions below).

Critical weaknesses

My main criticism regards novelty; the paper mostly applies a collection of known techniques that are all appropriate for a game like Catan. And while they are cast into a reinforcement learning setting, the approach is reminiscent of earlie AI approaches where adding domain expertise and heuristics was the way to scale to larger problems (e.g. decompose the game into two parts based on the form of the game, separate features for the surrogate value function specifically for the bargaining subproblem, a potential function for reward shaping within the bargaining game). There are no new algorithms and the approach is applied to a single game.

Less critical: The paper is quite well written up to Section 5, but Section 5 is more difficult from a presentation standpoint. Section 5 starts by explaining things as if the reader has read appendix sections A.10 - A.13.

Questions for authors

“We compare the update-50 and update-450 agents against the same intermediate opponents within each league lineage”. What are the update-50 and update-450 agents? These are never explained.

“In lineage 221099” .. what is a lineage? Is it related to the league seed? By “lineage” do you mean “independent run of PSFP”? If so, why call that a “lineage”.. that word choice makes all of Section 5 quite confusing.

In Fig 1, are these two tables from completely separate experiments?

“In lineage 221099, win rate increases from 16.4% to 28.8%, a paired gain of 12.4 percentage points with 95% confidence interval of [5.5,19.5]. In lineage 408751, win rate increases from 14.5% to 23.6%, a gain of 9.0 points with interval [2.6,15.5] “ Am I supposed to see this from Fig 1 or are these values obtained by averaging over columns?

Sec 5.4: Value-Bridge Ablation. “We evaluate whether useful bargaining depends on the allocation-sensitive value bridge in a separate six-victory-point experiment “ Why reduce to 6 victory points for this experiment? That seems arbitrary, and (I assume) does not match the context in which everything was trained?

2 comments

Thank you for the thorough review, the suggestions and comments -- we found them quite valuable. Response to your questions:

Q1--Q2 (update-NN agents, lineage). An update-NN agent is the checkpoint of a league run after NN PPO updates (update 50 ≈\approx 9M transitions, update 400 ≈\approx 74M). A "lineage" was one independently seeded run of the league (PFSP) procedure, that is, an independent run as you suggest. We have renamed it "league run" throughout and define both terms in the first paragraph of Section 5.

Q3--Q4 (Fig.\ 1, the 12.4 and 9.0 points). The two panels of Fig.\ 1 are the two league runs of the same experiment, with the same opponents and seeds within each run. The 12.4- and 9.0-point gains are paired differences over the 256 shared games per cell (update-450 minus update-50 agent on identical boards and dice) with bootstrap intervals over games. They are not column averages. The caption now says this.

Q5 (why six points). Simply put, budget. A ten-point ablation arm costs about three weeks on five nodes. At six points every arm can be trained from scratch and compared against a three-seed control at the same update. The league agents of Sections 5.1--5.3 are ten-point; the ablation is a separate, self-contained six-point experiment, and the text now says so where it is introduced. We have since added three fresh-seed arms at six points (no bonus, potential-only, bridge without shaping) and are training two of them at ten points now; we will include those results in an updated PDF by 16 November.

Presentation of Section 5. The definitions the section depends on (update-NN, league run, panels, paired design) are now in the first paragraph of Section 5. We hope this will make it easier on the reader.

Novelty. We do not claim a wholly new algorithm. The contribution is primarily the formulation of a specific way to learn a skill (bargaining) whose value is endogenous to a larger surrounding control problem, and an empirical analysis of it: in a mixed-motive task where the full-state value difference gives no usable signal (7.8--8.6%, at random), a low-dimensional allocation-sensitive critic does (25--27%), and controlled swaps attribute the resulting gains to the bargainer. The new arms sharpen this: neither the completion bonus nor the shaping potential explains the signal (a bridge trained without any potential reaches par by update 100).

Thank you again. The revised PDF is now uploaded. As described in our earlier reply, Section 5 now opens with definitions of update-N agents and league runs ("lineage" is renamed throughout), the Figure 1 caption explains the two panels and how the paired gains are computed, and the reason for the six-point ablation is stated where it is introduced. We have also added ten-point arms (Section 5.5) comparing the value bridge with a potential-only bargainer and with a bridge trained without the potential, which address whether the hand-designed shaping explains the signal.

Reviewer_DQ1QOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper works on bargaining within a large sequential decision problem. The authors make use of hierarchical reinforcement learning as a solution (also introduce a value bridge for it) to mitigate the issues caused by sparse and high variance reward signals. This notion is tested on the game Settlers of Catan.

Critical strengths
  • Seperation to two different problems i.e. sequential decision making and bargaining into two different RL problems and using hierarchical RL to solve it is a strong idea with good foundation.
  • Good writing and clear presentation.
Critical weaknesses
  • The problem case is described well but not demonstrated, a toy example case as a demonstration could help motivate the problem.
  • Single test environment.
  • Not much specification of how reinforcement learning (hierarchical rl) is applied and trained.
  • Incremental novelty
Questions for authors
  • Can you motivate why bargaining itself requires another hierarchical RL level and can not be efficiently learned in a single RL training for the whole game? It is written that those signals can be sparse and high variance but why do you think bargaining requires special attention that will be solved by another RL/
  • Do you think the results would change in any other direction if this is tested on another game?
  • Can you provide more details on how you use reinforcement learning for the bargainer?
2 comments

Excellent questions -- thank you for your positive view of the overall idea and your feedback. Responses to your questions:

Q1 (why a second RL level). The empirical answer is in the ablation. A bargainer rewarded with the change in the full-game critic, which is the signal a single flat RL approach would provide, is no better than a random bargainer at updates 50 and 100 (8.6%, 7.8%). The same architecture rewarded with the allocation-sensitive critic reaches 25--27%, with or without the shaping potential. The reason is credit assignment: bargaining decisions are many and short-lived, and each one's effect on the game value is small relative to the critic's error, so the bargainer needs a surrogate value that is sensitive to the allocation. We add two sentences to the introduction making this concrete and point to the ablation.

Q2 (other games). We expect the ingredient that mattered, a per-trade signal sensitive to the allocation, to carry to other task-embedded negotiations such as Diplomacy-style agreements or resource markets, and the specific potential based reward shaping not to. We now say this in the discussion, and state the single environment as a limitation.

Q3 / weaknesses (training details, single environment, toy example). The bargainer's training details (reward, normalization, completion bonus, PPO settings, budget) are now in the main text, with A.10--A.13 kept for the rest.

Thank you for your explanations. My questions are largely addressed. However the novelty is very limited and as reviewer MpJm states the work is largely based on "collection of known techniques that are all appropriate for a game like Catan". Although I find the work and the problem addressed interesting, and also like the hierarchical RL use, given there is only one game demonstration with a standard use of hierarchical RL I'll keep my score. It would be interesting to see how hierarchical RL can be further specialized into bargaining maybe making use of more game theoretic principles or bargaining specialized RL modules.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.