Negotiation

"We exchanged seventeen offers, discovered we wanted different things all along, and walked away each convinced we had won. That is the good outcome."

A Buyer Agent With a Reservation Value

A multi-agent system rarely enjoys the luxury of a single objective. A logistics platform has shippers who want low prices and carriers who want high ones. A cloud scheduler has tenants competing for the same accelerators. A team of warehouse robots must divide a pick list, and each one would rather take the short routes. In every case the agents are self-interested, their preferences conflict, and no central authority dictates the outcome. What remains is negotiation: a process by which agents with conflicting preferences exchange proposals to reach a mutually acceptable agreement. This section dissects that process into its three moving parts, derives the classic equilibrium for the two-party case, shows how multiple issues open the door to win-win trades, and ends at the research frontier where large language models negotiate in natural language.

1. The Anatomy of a Negotiation Beginner

Every negotiation, from a haggle in a bazaar to an automated procurement auction, decomposes into the same three components, and keeping them separate is the first discipline of the field. The negotiation protocol is the set of rules: who may make an offer, in what order, when, and what counts as acceptance or breakdown. The negotiation object is what is being decided: a single number like a price, or a vector of issues like price, delivery date, and warranty length together. The agents' strategies are the private decision rules each agent uses: how much to concede each round, what reservation value (the worst deal it will still accept) to hold, and how a looming deadline changes its behavior. The protocol is public and shared; the object is shared; the strategies are private and adversarial. Almost every result in negotiation theory is a statement about how a fixed protocol and object constrain the rational strategies.

The single most studied protocol is alternating offers: the two parties take turns proposing a complete agreement, and on each turn the receiver either accepts (ending the negotiation) or rejects and makes a counter-proposal. It is the backbone of bilateral bargaining, and it has the appealing property that it never lets either side stall indefinitely without cost, provided we make delay expensive. That cost is usually modeled as discounting: a deal worth $v$ today is worth only $\delta v$ next round, with a discount factor $\delta \in (0,1)$ that encodes how much the agent dislikes waiting. Discounting is what turns a protocol with no natural endpoint into one with a sharp prediction, as the next section shows.

2. Bilateral Bargaining and the Rubinstein Equilibrium Intermediate

Consider the cleanest case: two agents must split a surplus of size $1$ (think of it as the gap between the highest price a buyer will pay and the lowest a seller will accept, normalized). They alternate offers, the buyer proposing first, and each round of delay shrinks the pie through the discount factors $\delta_b$ and $\delta_s$. This is Rubinstein's bargaining game, and its remarkable feature is that it has a unique subgame-perfect equilibrium (the refinement of Nash equilibrium developed in Section 28.3): a single, exact prediction of who gets what. The proposer's equilibrium share is

The logic is backward induction. The responder will reject any offer that gives it less than what it could secure by becoming the proposer next round, so the proposer offers exactly that continuation value (no more, no less) and the responder accepts immediately. Agreement is reached in the very first round, with no costly delay, yet the threat of delay is precisely what pins down the shares. Two things fall straight out of the formula. First, patience is power: the agent with the higher $\delta$ (the one who minds waiting less) captures the larger share. Second, there is a first-mover advantage, which shrinks as the agents become equally patient. When $\delta_b = \delta_s = \delta$, the proposer's share is $1/(1+\delta)$, sliding toward an even split as $\delta \to 1$.

Figure 29.6.1 shows the alternating-offers exchange together with the bargaining zone: the band of agreements both sides prefer to no deal, bounded by the buyer's and seller's reservation values, and the point where the equilibrium lands inside it.

The code below plays out this game for concrete discount factors. It computes the equilibrium shares from the formula, then simulates rational play to confirm the deal closes immediately, and reports which agent's patience won it the larger slice.

3. Multi-Issue Negotiation: Manufacturing Win-Win Intermediate

Splitting a single number is a zero-sum fight: every cent the buyer gains, the seller loses. This is distributive bargaining, and it is the whole story only when there is one issue. The moment there are several issues and the agents weigh them differently, a richer possibility opens up: integrative bargaining, in which the agents trade concessions on issues they care little about for gains on issues they care about a lot. The trick has a name from labor negotiations, logrolling: I give you the issue you value most, you give me the issue I value most, and we both come out ahead of any even split.

Concretely, suppose two agents negotiate three issues, and each issue has $10$ units to divide. Agent A weights the issues $(1, 6, 3)$ and agent B weights them $(6, 1, 3)$: A cares most about the second issue, B about the first, and they agree on the third. An even five-five split on every issue gives each agent a utility of $50$. But if A concedes the first issue entirely to B and B concedes the second entirely to A, while they split the third, each agent's utility jumps to $75$. No units were created; the agents simply moved each issue toward whoever valued it more. The set of agreements that cannot be improved for one agent without hurting the other is the Pareto frontier (introduced in Section 28.5), and integrative bargaining is the art of climbing onto it. The even split sits strictly inside the frontier, leaving joint value on the table that differing priorities can recover.

4. A Runnable Bargaining Demo Intermediate

The program in Code 29.6.1 implements both halves of the story in pure Python: the single-issue Rubinstein game with discounting, and the three-issue integrative negotiation that finds a Pareto-improving trade. It depends on nothing outside the standard library, so the equilibrium and the win-win deal are computed from first principles rather than asserted.

from itertools import product

# ---------- Part 1: single-issue alternating-offers bargaining (Rubinstein) ----------
# Two agents split a surplus of size 1. Each round of delay discounts the pie by
# the agent's discount factor delta. The subgame-perfect-equilibrium share for the
# proposer is x* = (1 - delta_responder) / (1 - delta_proposer * delta_responder).
def rubinstein_shares(delta_p, delta_r):
    x_p = (1 - delta_r) / (1 - delta_p * delta_r)      # proposer's equilibrium share
    return x_p, 1 - x_p

def simulate_alternating(delta_b, delta_s, max_rounds=50):
    # Buyer proposes first. Each proposer offers the responder exactly its discounted
    # continuation value, so a rational responder accepts at once.
    xb_star, _ = rubinstein_shares(delta_b, delta_s)   # buyer share when buyer proposes
    xs_star, _ = rubinstein_shares(delta_s, delta_b)   # seller share when seller proposes
    history = []
    for r in range(1, max_rounds + 1):
        if r % 2 == 1:                                 # buyer's turn to propose
            offer_to_seller, resp_cont = 1 - xb_star, delta_s * xs_star
            accept = offer_to_seller + 1e-12 >= resp_cont
            history.append((r, "buyer", xb_star, 1 - xb_star, accept))
        else:                                          # seller's turn to propose
            offer_to_buyer, resp_cont = 1 - xs_star, delta_b * xb_star
            accept = offer_to_buyer + 1e-12 >= resp_cont
            history.append((r, "seller", 1 - xs_star, xs_star, accept))
        if accept:
            break
    return history

print("=== Single-issue alternating-offers bargaining (Rubinstein) ===")
db, ds = 0.90, 0.80
xb, _ = rubinstein_shares(db, ds)
print(f"discount factors: buyer delta_b={db}, seller delta_s={ds}")
print(f"SPE shares (buyer proposes first): buyer={xb:.4f}, seller={1-xb:.4f}")
print("round  proposer  buyer_share  seller_share  agreement")
for r, who, bs, ss, acc in simulate_alternating(db, ds):
    print(f"  {r:>2}   {who:>6}      {bs:.4f}       {ss:.4f}       {'YES' if acc else 'no'}")

# ---------- Part 2: multi-issue negotiation, finding a Pareto-improving trade ----------
issues = ["budget", "deadline", "scope"]
wA = {"budget": 1, "deadline": 6, "scope": 3}          # A cares most about the deadline
wB = {"budget": 6, "deadline": 1, "scope": 3}          # B cares most about the budget
UNITS, resA, resB = 10, 60, 60                         # units per issue; walk-away utilities

def utility(weights, alloc_to_self):
    return sum(weights[i] * alloc_to_self[i] for i in issues)

even = {i: 5 for i in issues}                          # naive distributive 50/50 split
uA_even = utility(wA, even)
uB_even = utility(wB, {i: UNITS - even[i] for i in issues})
print("\n=== Multi-issue negotiation: distributive vs integrative ===")
print(f"weights A: {wA}")
print(f"weights B: {wB}")
print(f"even 5/5 split  -> u_A={uA_even}, u_B={uB_even}  (sum={uA_even+uB_even})")

# Logrolling: give each issue to whoever values it more (ties split evenly).
logroll = {i: (UNITS if wA[i] > wB[i] else 0 if wA[i] < wB[i] else 5) for i in issues}
allocB = {i: UNITS - logroll[i] for i in issues}
uA_log, uB_log = utility(wA, logroll), utility(wB, allocB)
print(f"logrolling deal -> A gets {logroll}")
print(f"                   u_A={uA_log}, u_B={uB_log}  (sum={uA_log+uB_log})")
print(f"both above reservation {resA}/{resB}: A {uA_log>=resA}, B {uB_log>=resB}")
print(f"joint surplus created by exploiting different priorities: "
      f"+{(uA_log+uB_log)-(uA_even+uB_even)}")

=== Single-issue alternating-offers bargaining (Rubinstein) ===
discount factors: buyer delta_b=0.9, seller delta_s=0.8
SPE shares (buyer proposes first): buyer=0.7143, seller=0.2857
round  proposer  buyer_share  seller_share  agreement
   1    buyer      0.7143       0.2857       YES

=== Multi-issue negotiation: distributive vs integrative ===
weights A: {'budget': 1, 'deadline': 6, 'scope': 3}
weights B: {'budget': 6, 'deadline': 1, 'scope': 3}
even 5/5 split  -> u_A=50, u_B=50  (sum=100)
logrolling deal -> A gets {'budget': 0, 'deadline': 10, 'scope': 5}
                   u_A=75, u_B=75  (sum=150)
both above reservation 60/60: A True, B True
joint surplus created by exploiting different priorities: +50

The two halves of the output make the section's two main points concrete. The single-issue game confirms the equilibrium: the more patient buyer secures roughly $0.71$ of the pie, and the deal closes immediately because the threat of costly delay is enough. The multi-issue result is the more surprising one. Both agents end strictly better off than under the even split, and neither gave up anything it cared about. That $+50$ of joint surplus was always available; it took a negotiation that looked at all the issues together, rather than haggling each one in isolation, to find it.

5. Argumentation-Based Negotiation Advanced

The protocols above exchange only offers: a number, or a bundle of numbers. Agents reveal nothing about why they want what they want. Argumentation-based negotiation enriches the protocol so that an agent can attach a justification to a proposal, and can challenge, support, or rebut the justifications of others. Instead of merely countering "I offer 0.55" with "I demand 0.70," an agent can say "I cannot go below 0.65 because my supplier costs rose," and the other can accept the premise, dispute it, or respond with a reason of its own. This matters for two reasons. First, justifications let agents update each other's beliefs, which can reveal that a proposed deal is infeasible or that an objection rests on a false assumption, collapsing a deadlock that pure offer-exchange would never resolve. Second, arguments can persuade: an agent may change what it is willing to accept once it understands the constraints the other side is under. Argumentation turns negotiation from a sequence of demands into a structured dialogue, at the cost of a much larger and harder-to-analyze message space.

6. Negotiation as Structured Auction, and the LLM Frontier Advanced

Bilateral bargaining is one protocol among many, and when many agents negotiate over the same object at once, the natural protocol is an auction. An auction is simply a negotiation protocol with very tight rules: the auctioneer fixes who may bid, when, and how the winner and price are determined, which removes the open-ended back-and-forth and replaces it with a single structured round (or a few). Seen this way, the mechanism-design results of Section 28.6 are the theory of how to choose those rules so that the agents' best strategies yield an efficient or revenue-maximizing outcome. Auctions reappear throughout this part as the workhorse for task allocation (Section 29.8), where robots or services bid for jobs, precisely because their tight protocol makes the agents' incentives tractable in a way that free-form bargaining does not.

We have taken negotiation from its three components, through the sharp equilibrium of two-party bargaining, into the multi-issue regime where differing priorities create value, and out to the frontier where language models bargain in prose. The thread running through all of it is that a protocol can substitute for a central coordinator when objectives conflict. The next step is to let more than two agents combine their interests: when several self-interested agents would do better as a bloc than alone, they must decide who teams up with whom and how to share the spoils. That is coalition formation, the subject of Section 29.7.