Negotiation and Consensus Mechanisms

An advertising platform ran three campaign agents against a shared daily budget of 12,000 pounds. Each agent wanted as much as it could get. The first implementation was first-come-first-served: whichever agent asked first, got. The agent whose cron job fired at 00:00:01 took 11,400 pounds. The other two split 600 between them and produced nothing worth measuring.

So the team added priorities: campaign A is highest, then B, then C. Now A took 11,400 every single day and C never ran at all for nineteen consecutive days. The rule was working perfectly, and the outcome was worse — because a static priority applied repeatedly is not arbitration, it is a decision made once and enforced forever.

What was needed was a way for agents that want incompatible things to reach an allocation that reflects what each of them actually gains. That is negotiation, and its cousin — several agents needing to agree on one answer — is consensus. Both are mechanisms for resolving disagreement without a dictator, and both go wrong in specific, learnable ways.

Where negotiation sits among the patterns

The distinguishing feature of negotiation is that neither party can impose an outcome. If one can, you do not have a negotiation and you should not pay for one — you have an assignment, and pretending otherwise just adds rounds of theatre before the inevitable.

Bilateral negotiation: two agents, one dimension

Two concepts carry all the weight.

An agent's utility function maps an outcome to a number saying how good it is for that agent. Its reservation value is the worst outcome it would still accept — the point at which walking away is better than agreeing. Everything else is bookkeeping.

The gap between the two reservation values is the zone of possible agreement, or ZOPA. If the buyer will pay at most 100 and the seller will accept at least 70, the ZOPA is the interval from 70 to 100 and it is 30 wide. Any price in it makes both parties better off than no deal. If the buyer's maximum were 65, the ZOPA would be empty and no amount of negotiating helps — a fact worth detecting in one line rather than discovering after twenty rounds.

1from dataclasses import dataclass23@dataclass4class Party:5    name: str6    opening: float          # first offer, favourable to itself7    reservation: float      # the walk-away point8    is_buyer: bool910    def offer_at(self, t: int, T: int) -> float:11        """Linear concession from opening toward reservation over T rounds."""12        frac = min(1.0, t / T)13        return self.opening + (self.reservation - self.opening) * frac1415    def accepts(self, price: float, my_next: float) -> bool:16        if self.is_buyer:17            return price <= self.reservation and price <= my_next18        return price >= self.reservation and price >= my_next1920def negotiate(buyer: Party, seller: Party, T: int = 5):21    if buyer.reservation < seller.reservation:22        return {"agreement": False, "reason": "empty ZOPA", "rounds": 0}23    for t in range(T + 1):24        s_offer = seller.offer_at(t, T)25        b_offer = buyer.offer_at(t, T)26        if buyer.accepts(s_offer, b_offer):27            return {"agreement": True, "price": s_offer, "rounds": t}28        if seller.accepts(b_offer, s_offer):29            return {"agreement": True, "price": b_offer, "rounds": t}30    return {"agreement": False, "reason": "deadline", "rounds": T}

A worked round-by-round

Seller opens at 120 with a reservation of 70. Buyer opens at 60 with a reservation of 100. Five rounds of linear concession. Seller concedes (120-70)/5 = 10 per round; buyer concedes (100-60)/5 = 8 per round.

At round 4 the seller's ask of 80 is below the buyer's own offer of 92, so the buyer accepts immediately at 80. Surplus split: buyer gains 100 - 80 = 20, seller gains 80 - 70 = 10. The total is 30, exactly the ZOPA width — the negotiation captured all available value, but not evenly, because the seller conceded faster (10 per round against 8).

That last observation is the practical lesson. Concession rate determines the split. If the seller had conceded 5 per round over ten rounds instead, the deal would have landed nearer 95 and the split would have reversed. Nothing about the agents' preferences changed; only the schedule did.

In a negotiation with a fixed deadline, the party that concedes more slowly captures more of the surplus — regardless of who values the item more.

This also explains the deadline effect. Both agents concede fully by round T, so a short deadline forces fast concession and pushes the deal toward the midpoint; a long deadline rewards patience. If one agent has a real deadline and the other does not, the one without it wins almost everything — which is why in the ad-budget system you must give every agent the same deadline, or the allocation is decided by clock skew rather than by value.

Auctions: negotiation with many bidders

Bilateral offers do not scale to twelve agents wanting one GPU slot. Auctions do, in one round.

1def vickrey(bids: dict[str, float]):2    """bids: agent -> declared value. Winner pays the second-highest bid."""3    if len(bids) < 2:4        raise ValueError("second-price needs at least two bids")5    ranked = sorted(bids.items(), key=lambda kv: kv[1], reverse=True)6    (winner, _), (_, second) = ranked[0], ranked[1]7    return {"winner": winner, "price": second}89vickrey({"a": 42.0, "b": 37.0, "c": 51.0, "d": 29.0})10# {'winner': 'c', 'price': 42.0}

Agent C values the slot at 51 and pays 42, keeping a surplus of 9. Now consider why C should not shade its bid. If C bids 45 instead of 51, it still wins and still pays 42 — shading gained nothing. If C bids 40, it loses a slot it valued at 51 to a bidder who valued it at 42, destroying 9 of its own surplus. Since the price is set by someone else's bid, misreporting can only cost you. This is why second-price auctions are the default for allocation among agents you wrote yourself: you can trust the numbers your agents report, which means the allocation is actually efficient.

The failure mode is collusion and the degenerate case. With exactly one bidder there is no second price, and implementations that fall back to "pay your own bid" or "pay zero" both create incentives to be the only bidder. Decide explicitly: a reserve price is the standard answer, and the winner pays max(second_bid, reserve).

Consensus: several answers, one decision

Different problem. Here the agents are not competing for a resource; they have each produced a candidate answer and the system must pick one.

Majority voting

1from collections import Counter23def majority(votes: list[str], threshold: float = 0.5):4    counts = Counter(votes)5    top, n = counts.most_common(1)[0]6    return top if n / len(votes) > threshold else None   # None = no consensus

Cheap and often adequate, with one important weakness: it only looks at first choices, so it discards everything the agents know about the alternatives.

Ranked choice with the Borda count

Each agent submits a full ranking. With k candidates, a first place is worth k-1 points, second k-2, and so on.

1def borda(rankings: list[list[str]]) -> dict[str, int]:2    k = len(rankings[0])3    scores = Counter()4    for ranking in rankings:5        if len(set(ranking)) != k:6            raise ValueError("every ranking must be a full permutation")7        for position, candidate in enumerate(ranking):8            scores[candidate] += k - 1 - position9    return dict(scores)

Five agents rank three strategies A, B, C:

By first choices alone: A has 2, B has 2, C has 1 — a tie between A and B, broken by whatever most_common happens to return. By Borda:

• A: 2 + 2 + 0 + 0 + 0 = 4
• B: 1 + 1 + 2 + 2 + 1 = 7
• C: 0 + 0 + 1 + 1 + 2 = 4

Total is 15, which checks out: 5 agents × 3 points each. B wins decisively with 7. And look at why that is the better answer: three of the five agents rank A last, while B is never worse than second for anybody. Plurality could not see that, because plurality throws away every preference after the first.

Counting only first choices can elect the option a majority likes least. If your agents can express a full ranking, discarding it is throwing away most of what they told you.

Quorum

Requiring unanimity means one slow or dead agent blocks every decision. A quorum requires agreement from a majority of the group, so the system keeps deciding while a minority is unavailable.

1def quorum_decide(votes: dict[str, str], group_size: int):2    needed = group_size // 2 + 1              # strict majority of the group3    if len(votes) < needed:4        return {"decided": False, "reason": "not enough responses"}5    top, n = Counter(votes.values()).most_common(1)[0]6    return ({"decided": True, "value": top} if n >= needed7            else {"decided": False, "reason": "no option reached quorum"})

With 5 agents the quorum is 3, so the system tolerates 2 failures. With 4 agents the quorum is still 3, so it tolerates only 1 — the fourth agent bought you nothing in fault tolerance while adding cost and latency. That is why groups are conventionally odd-sized.

Conflict resolution, and a bug that ships constantly

When negotiation and voting both fail to settle a matter, you need a resolution rule. Four common ones:

Now the bug. This is the priority resolver as it is usually first written:

def resolve(claims):                       # claims: list of (agent, priority)    return max(claims, key=lambda c: c[1])[0]     # WRONG

Two defects, both silent. First, max returns the first maximal element, so when two agents tie on priority the winner is decided by list order — which is usually registration order, which is usually alphabetical, which means the same agent wins every tie forever. Second, there is no ageing, so a genuinely lower-priority agent starves exactly as campaign C did for nineteen days.

1import random, time23def resolve(claims, last_win: dict[str, float], age_bonus_per_hour=1.0):4    now = time.time()5    scored = []6    for agent, priority in claims:7        # First sighting starts the clock, so a never-winning agent still ages.8        hours_waiting = (now - last_win.setdefault(agent, now)) / 36009        effective = priority + age_bonus_per_hour * hours_waiting10        scored.append((agent, effective))11    best = max(s[1] for s in scored)12    # Break ties at random among the true maxima, not by list position.13    winners = [a for a, s in scored if abs(s - best) < 1e-9]14    winner = random.choice(winners)15    last_win[winner] = now16    return winner

Two changes. Ties are resolved by an explicit random choice among agents whose scores are genuinely equal — note the tolerance comparison, because floating-point scores that should tie often differ in the last digit, and s == best would quietly drop the near-tied agents from the draw. And an ageing bonus means a starved agent's effective priority climbs until it wins. The setdefault matters: with a plain get(agent, now), an agent that has never won would always show zero hours of waiting — exactly the agent the bonus exists to help. With age_bonus_per_hour = 1.0, campaign C at priority 1 overtakes campaign A at priority 3 after just over two hours of waiting, which converts permanent starvation into bounded delay.

Deadlock

Negotiation deadlock is not "the negotiation failed". It is "the negotiation cannot progress and will not stop". Three shapes:

Circular resource wait. Agent A holds the rate-limit token and needs the database lock; agent B holds the database lock and needs the token. Neither yields. Detect it by building a wait-for graph and looking for a cycle:

1def find_cycle(wait_for: dict[str, set[str]]) -> list[str] | None:2    """wait_for[a] = set of agents a is blocked on."""3    WHITE, GREY, BLACK = 0, 1, 24    colour = {n: WHITE for n in wait_for}5    path: list[str] = []67    def visit(n):8        colour[n] = GREY9        path.append(n)10        for m in wait_for.get(n, ()):11            if colour.get(m, WHITE) == GREY:12                return path[path.index(m):] + [m]      # the cycle13            if colour.get(m, WHITE) == WHITE:14                found = visit(m)15                if found:16                    return found17        colour[n] = BLACK18        path.pop()19        return None2021    for n in wait_for:22        if colour[n] == WHITE:23            cycle = visit(n)24            if cycle:25                return cycle26    return None

Prevention beats detection here: acquire shared resources in a globally fixed order — always the token before the lock, never the reverse — and a cycle becomes impossible. Where a fixed order is impractical, put a timeout on every acquire so any cycle breaks itself, and back off by a random interval so the same two agents do not immediately re-collide.

Stalled concession. Both agents stop conceding because each expects the other to move. The fix is structural: require monotonic concession — every offer must be no better for yourself than your previous one — and terminate if a round passes with no movement from either side.

Offer ping-pong. Two agents repeat the same pair of offers indefinitely. Detect it by hashing the offer pair each round and stopping when a hash repeats; that is cheaper and more reliable than trying to reason about whether progress is being made.

Whichever fires, the correct output is a structured no-deal: which parties, what the final offers were, which guard tripped. "Negotiation failed" as a bare error is unactionable; "seller stuck at 88, buyer stuck at 84, six rounds without movement" tells you the two sides are only 4 apart and the concession schedules stopped moving before they met.

Where people get it wrong

"Negotiation will find the fair answer." It finds an answer determined by concession rates, deadlines, and outside options — not by fairness. If you want a particular split, encode it in the concession schedules; do not hope it emerges.

"More voting agents means a better decision." Only if their errors are independent. Five agents running the same model on the same prompt produce five correlated votes, so a majority of five may be no more reliable than one. Diversity of model, prompt, or evidence is what makes voting work; identical voters just multiply cost.

"Unanimity is the safest rule." Unanimity means any single agent can veto, including one that is broken or hung. Quorum with an explicit no-consensus outcome is safer in every system where agents can fail.

"A tie is rare enough to ignore." Ties are common — LLM agents often produce identical classifications — and the default tie-break is list order, which is stable, which means the same agent wins forever. That is the campaign-C bug, and it looks like a policy decision rather than an accident.

"Utility values are comparable across agents." Agent A reporting utility 8 and agent B reporting 6 tells you nothing unless both use the same scale with the same meaning. Normalise to a common unit — expected revenue, tokens saved, seconds of latency avoided — or the comparison is arithmetic on incommensurable numbers.

What this means when you build

Check the ZOPA before you negotiate. It is one comparison and it converts twenty wasted rounds into an immediate, honest "no agreement is possible; here is why". Most negotiation code has no such check, which is why so much of it burns tokens discovering that two agents want incompatible things.

Prefer a mechanism that makes honesty optimal over one that requires trust. A second-price auction among your own agents means the numbers they report are the numbers you can plan with. A first-price auction means every agent shades its bid and your allocation is based on strategically distorted values — from agents you wrote, which is a strange place to end up.

Give every consensus mechanism an explicit "no consensus" branch, and make it return something usable: the vote distribution, the margin, and the abstentions. A 3–2 split and a 5–0 split are wildly different situations that a bare winner label makes identical. Route thin margins to a human; that is exactly the case where an extra pair of eyes is cheap relative to being wrong.

And instrument the arbitration itself. Log every conflict with the claimants, their scores, the rule that fired, and the winner. Then look at the win distribution weekly. Nineteen days of campaign C never running was visible in that table from day one — the code was correct, the rule was as written, and only the aggregate showed that the policy was wrong.