# Tractable Agreement Protocols

arXiv: https://arxiv.org/abs/2411.19791 · HTML: https://mlsanity.com/paper/2411.19791/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 42 references that are in the map.
- First posted on arXiv 29 Nov 2024.

## Builds on (most cited first, 15 of 15)

- [Improving Factuality and Reasoning in Language Models through Multiagent Debate](https://mlsanity.com/paper/2305.14325/) (2023)
- [Encouraging Divergent Thinking in Large Language Models through Multi-Agent Debate](https://mlsanity.com/paper/2305.19118/) (2023)
- [ChatEval: Towards Better LLM-based Evaluators through Multi-Agent Debate](https://mlsanity.com/paper/2308.07201/) (2023)
- [Calibrating Predictions to Decisions: A Novel Approach to Multi-Class Calibration](https://mlsanity.com/paper/2107.05719/) (2021)
- [Loss Minimization through the Lens of Outcome Indistinguishability](https://mlsanity.com/paper/2210.08649/) (2022)
- [A Unifying Theory of Distance from Calibration](https://mlsanity.com/paper/2211.16886/) (2022)
- [Online Multivalid Learning: Means, Moments, and Prediction Intervals](https://mlsanity.com/paper/2101.01739/) (2021)
- [U-Calibration: Forecasting for an Unknown Agent](https://mlsanity.com/paper/2307.00168/) (2023)
- [Stronger Calibration Lower Bounds via Sidestepping](https://mlsanity.com/paper/2012.03454/) (2020)
- [On the Distance from Calibration in Sequential Prediction](https://mlsanity.com/paper/2402.07458/) (2024)
- [Mechanisms for a No-Regret Agent: Beyond the Common Prior](https://mlsanity.com/paper/2009.05518/) (2020)
- [Efficient Prior-Free Mechanisms for No-Regret Agents](https://mlsanity.com/paper/2311.07754/) (2023)
- [Tracking and Improving Information in the Service of Fairness](https://mlsanity.com/paper/1904.09942/) (2019)
- [Agreement Implies Accuracy for Substitutable Signals](https://mlsanity.com/paper/2111.03278/) (2021)
- [False Consensus, Information Theory, and Prediction Markets](https://mlsanity.com/paper/2206.02993/) (2022)

## Built on by (most cited first, 13 of 13)

- [Conformal Prediction and Human Decision Making](https://mlsanity.com/paper/2503.11709/) (2025)
- [Networked Information Aggregation via Machine Learning](https://mlsanity.com/paper/2507.09683/) (2025)
- [Human-AI Collaborative Uncertainty Quantification](https://mlsanity.com/paper/2510.23476/) (2025)
- [Emergent Alignment via Competition](https://mlsanity.com/paper/2509.15090/) (2025)
- [Improved Bounds for Swap Multicalibration and Swap Omniprediction](https://mlsanity.com/paper/2505.20885/) (2025)
- [Pre-Trained AI Model Assisted Online Decision-Making under Missing Covariates: A Theoretical Perspective](https://mlsanity.com/paper/2507.07852/) (2025)
- [Multi-Round Human-AI Collaboration with User-Specified Requirements](https://mlsanity.com/paper/2602.17646/) (2026)
- [Optimal Deterministic Multicalibration and Omniprediction](https://mlsanity.com/paper/2606.20557/) (2026)
- [Model Agreement via Anchoring](https://mlsanity.com/paper/2602.23360/) (2026)
- [Optimal Rates for Agentic Networked Information Aggregation](https://mlsanity.com/paper/2609.05318/) (2026)
- [Augmented Feature Boosting for Multicalibration](https://mlsanity.com/paper/2609.33891/) (2026)
- [Optimal Networks for Agentic Information Aggregation](https://mlsanity.com/paper/2609.35537/) (2026)
- [Narrowing the Collaboration Gap, Probably](https://mlsanity.com/paper/2610.19215/) (2026)

## Abstract (arXiv)

We present an efficient reduction that converts any machine learning algorithm into an interactive protocol, enabling collaboration with another party (e.g., a human) to achieve consensus on predictions and improve accuracy. This approach imposes calibration conditions on each party, which are computationally and statistically tractable relaxations of Bayesian rationality. These conditions are sensible even in prior-free settings, representing a significant generalization of Aumann's classic "agreement theorem." In our protocol, the model first provides a prediction. The human then responds by either agreeing or offering feedback. The model updates its state and revises its prediction, while the human may adjust their beliefs. This iterative process continues until the two parties reach agreement. Initially, we study a setting that extends Aumann's Agreement Theorem, where parties aim to agree on a one-dimensional expectation by iteratively sharing their current estimates. Here, we recover the convergence theorem of Aaronson'05 under weaker assumptions. We then address the case where parties hold beliefs over distributions with d outcomes, exploring two feedback mechanisms. The first involves vector-valued estimates of predictions, while the second adopts a decision-theoretic approach: the human, needing to take an action from a finite set based on utility, communicates their utility-maximizing action at each round. In this setup, the number of rounds until agreement remains independent of d. Finally, we generalize to scenarios with more than two parties, where computational complexity scales linearly with the number of participants. Our protocols rely on simple, efficient conditions and produce predictions that surpass the accuracy of any individual party's alone.