Before AI Agents Negotiate for Us: A Competitive Tournament of Rule-Based, Search, Optimization, Learned, and Language-Model Negotiators Under Scarcity
Organizations: Tecnol´ogico de Monterrey, School of Engineering and Sciences, Av. Eugenio Garza Sada 2501 Sur, Tecnol´ogico, 64849 Monterrey, N.L., Mexico · AI Lab, Freight Technologies Inc. · School of Psychology, University of Monterrey, Monterrey, Mexico
Abstract
Automated bilateral negotiation underlies two-sided matching markets such as freight brokering, where many shippers and carriers negotiate price before a matching mechanism decides who is paired with whom. Prior strategy comparisons typically use isolated one-on-one duels or a single fixed market, so they cannot show how a strategy behaves against several live rivals under a changing balance of supply and demand. We built nine negotiation architectures spanning rule-based, search-based, optimization-based, imitation-learning, and reinforcement-learning families, and ran all nine simultaneously on both sides of a Gale-Shapley matching market under a balanced condition and two scarcity conditions rotated across all 36 exclusion pairs. In the balanced carrier market, an imitation-learned engine (ML2), a reinforcement-learning policy trained only on isolated negotiations (RL), and an expected-utility optimization engine (OPT) formed a statistically tied top group, and no architecture led in every condition and role. RL beat all eight carrier rivals when carriers were scarce, but its match rate collapsed from 62% to 16% when shippers were scarce and it had to compete with the other carrier agents for demand. A second reinforcement-learning policy trained against rival agents (RL2) kept its match rate above 91% in every condition, yet lost on realized payoff to all eight shipper-side rivals in two of the three conditions, traced to a confirmed train/deployment feature mismatch. We also tested nine large language models (LLMs), from 1 to 72 billion parameters, under the same protocol: they lost significantly to the two strongest engines (OPT2 and ML2) in 32 of 36 comparisons and won none. These results show that isolated or single-condition evaluation can hide failure modes that a many-sided, scarcity-varying, statistically corrected tournament exposes directly.
Figures & tables
| Architecture | Key parameters |
|---|---|
| R | Opening offset (carrier) / band width (shipper); concession decay ; threshold curvature |
| RV | As R, plus the occupancy-aware urgency factor derived from Eq. ( 6 ) (up to 50% faster concession when the agent’s own match prospects look poor) |
| IS | 24 belief particles; 7 candidate offers evaluated per turn; particle-sampling band wide; deterministic per-decision seeding (no run-to-run variance at a fixed seed) |
| OPT | Continuous bisection search over expected utility (24 steps); acceptance-probability sigmoid slope ; belief cushion |
| OPT2 | Extends OPT with an online gradient-fitted linear opponent-offer-trend model (60 gradient steps, learning rate ) and an anti-fingerprinting envelope search (200-iteration cap, expected-utility tolerance) |
| ML | Gradient-boosted regression tree (max depth 4, 200 boosting iterations, learning rate ), trained to imitate OPT2’s self-play offers |
| balanced ( ) | carrier_scarce ( ) | shipper_scarce ( ) | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Arch. | match | mean margin (USD) | % of ref. | 95% CI | match | mean margin (USD) | % of ref. | 95% CI | match | mean margin (USD) | % of ref. | 95% CI |
| ML2 | 0.79 | 98.5 | 6.6 | [82.2, 115.6] | 0.84 | 111.9 | 8.0 | [91.2, 135.1] | 0.62 | 65.1 | 4.5 | [52.9, 78.7] |
| RL | 0.62 | 90.4 | 6.9 | [74.6, 107.5] | 0.84 | 142.0 | 10.6 | [123.3, 162.0] | 0.16 | 40.8 | 3.2 | [27.8, 55.2] |
| OPT2 | 0.80 | 83.5 | 5.9 | [67.7, 101.7] | 0.91 | 113.8 | 7.3 | [95.4, 133.4] | 0.69 | 64.4 | 4.4 | [53.0, 77.3] |
| OPT | 0.79 | 79.8 | 5.3 | [66.5, 94.3] | 0.87 | 78.7 | 4.9 | [66.8, 92.1] | 0.76 | 75.4 | 5.1 | [62.5, 90.1] |
| IS | 0.69 | 71.4 | 5.0 | [57.6, 86.5] | 0.82 | 115.2 | 8.1 | [95.0, 136.9] | 0.23 | 30.6 | 2.6 | [19.8, 42.4] |
| balanced ( ) | carrier_scarce ( ) | shipper_scarce ( ) | ||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Arch. | match | mean profit (USD) | % of sale | 95% CI | match | mean profit (USD) | % of sale | 95% CI | match | mean profit (USD) | % of sale | 95% CI |
| RL | 0.82 | 1124.8 | 20.8 | [1032.4, 1220.5] | 0.63 | 779.2 | 14.2 | [699.9, 863.6] | 0.85 | 1233.7 | 21.7 | [1115.5, 1352.1] |
| R | 0.82 | 1094.4 | 20.1 | [1002.5, 1193.9] | 0.66 | 800.5 | 14.8 | [716.2, 883.9] | 0.89 | 1212.9 | 21.9 | [1111.6, 1315.5] |
| OPT | 0.84 | 1082.5 | 20.0 | [990.3, 1177.8] | 0.69 | 867.1 | 15.9 | [781.3, 951.3] | 0.87 | 1143.5 | 20.0 | [1033.2, 1250.3] |
| IS | 0.79 | 1068.9 | 19.6 | [976.0, 1165.3] | 0.70 | 833.1 | 15.3 | [752.5, 918.0] | 0.85 | 1149.7 | 20.8 | [1044.5, 1253.1] |
| RV | 0.80 | 1066.9 | 19.5 | [973.1, 1167.3] | 0.66 | 795.4 | 14.6 | [713.8, 879.7] | 0.86 | 1122.9 | 19.9 | [1010.5, 1237.6] |
| Tier | Model | match | mean margin | 95% CI |
|---|---|---|---|---|
| fixed rivals (pooled across all nine LLM markets) | ||||
| ML2 | 1.00 | 68.6 | [66.5, 70.8] | |
| OPT2 | 1.00 | 63.9 | [61.5, 66.3] | |
| R | 1.00 | 60.9 | [ 68.8, 53.2] | |
| tiny | llama3.2:1b | 0.38 | 18.1 | [ 33.2, 3.8] |
| tiny | qwen2.5:1.5b | 0.80 | 63.6 | [ 88.1, 40.7] |
| Tier | Model | match | mean profit | 95% CI |
|---|---|---|---|---|
| fixed rivals (pooled across all nine LLM markets) | ||||
| R | 1.00 | 1163.1 | [1101.6, 1225.4] | |
| OPT2 | 1.00 | 1148.8 | [1082.2, 1210.8] | |
| ML2 | 0.99 | 1117.7 | [1055.4, 1180.2] | |
| tiny | llama3.2:1b | 0.50 | 2.7 | [0.0, 7.8] |
| tiny | qwen2.5:1.5b | 0.97 | 462.5 | [294.4, 652.3] |
| Tier | Model (role) | first-try-ok | mean latency (s) | p95 latency (s) |
|---|---|---|---|---|
| tiny | llama3.2:1b (carrier / shipper) | 0.32 / 0.26 | 2.3 / 2.3 | 2.5 / 2.4 |
| tiny | qwen2.5:1.5b (carrier / shipper) | 0.45 / 0.58 | 2.3 / 2.3 | 2.4 / 2.4 |
| tiny | deepseek-r1:1.5b (carrier / shipper) | 0.49 / 0.52 | 17.1 / 21.7 | 92.1 / 92.1 |
| small | llama3.1:8b (carrier / shipper) | 0.88 / 0.88 | 2.6 / 2.5 | 2.7 / 2.6 |
| small | qwen2.5:7b (carrier / shipper) | 0.55 / 0.81 | 2.4 / 2.4 | 2.5 / 2.6 |
| small | deepseek-r1:7b (carrier / shipper) | 0.55 / 0.88 | 9.0 / 10.6 | 15.0 / 22.9 |
| Attempt | Action | Amount | Outcome |
|---|---|---|---|
| 0 | accept | 3022.19 | retried: amount must be null for accept |
| 1 | accept | 3022.19 | retried: same schema violation repeated |
| 2 | accept | 3022.19 | retried: same schema violation repeated |
| – | forfeit | – | retry budget exhausted ( exhausted_retries ) |
Automated Negotiation
Automated negotiation studies computational agents that bargain over prices, preferences, and agreements in human, market, and multi-agent settings.
See all 50 papers