| paper | Tackling the Protocol Problem in Automated Negotiation |
| authors | — |
| venue | AAMAS 2025 |
| filed under | unclassified |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | no |
The paper contains no numbered Theorem, Lemma, Corollary, or Proposition asserting a computational result, so bit (a) fails outright. The proposed \(\eta_{ab}\) construction is a distribution over independent complete negotiation games: its masses weight outcomes but do not alter the protocol, histories, or equilibrium. It is therefore at most a new distributional protocol-synthesis problem, not a qualifying continuous population mirror of this paper.
fails bit a — no named computational result to mirror
The masses \(\eta_{ab}\) only weight independently solved games and never enter the game dynamics, so denominator clearing repeats sessions rather than producing a high-multiplicity society.
fatal: True
The nearest formulation covers only the unnumbered TAU/WAR performance claim; it leaves the GBP formalism, PBE analysis, and broader protocol-synthesis agenda untouched, and it cannot cover a named computational theorem because none is present.
Strictly, this paper has no qualifying anchor under the programme’s rule: it contains no numbered Theorem, Lemma, Corollary, or Proposition, and no stated complexity result such as \( \mathrm{P} \), NP-hardness, or FPT. The strongest positive case therefore rests on an unnumbered theorem-like claim, not on an eligible named computational result.
The best anchor is the paper’s claim that TAU using WAR is an Outcome-Perfect Negotiation Mechanism for bilateral discrete negotiation scenarios with no information about partner preferences, provided no outcome has the same utility as the final agreement for one negotiator but not the other. This claim is asserted and sketched in this paper, not cited as a numbered result from elsewhere. It is also the paper’s most concrete substantive claim: TAU is the protocol, WAR is the strategy, and the claimed guarantees are perfect rationality, completeness, Pareto-optimality, ordinal Kalai fairness, and welfare.
My lead mirror would be Typed Outcome-Perfect Protocol Design\(_\infty\). The natural high-multiplicity regime is not one negotiation involving millions of simultaneous people; it is a large population of repeated procurement negotiations. An enterprise may conduct millions of transactions, while only a modest catalogue of buyer and supplier types recurs: for example, buyers with the same quantity–price–delivery utility and suppliers with the same utility, reservation value, information state, and tie-breaking rule.
Formally, let \(A\) and \(B\) be finite sets of buyer and supplier types. A type contains the complete utility function \(u_a^A,u_b^B:\Omega^+\to\mathbb{Q}\), the information available to the agent, and its deterministic tie-breaking order. Here \(\Omega\) is a finite outcome space and \(\phi\) is disagreement. Let \(\eta_{ab}\in\mathbb{Q}_{\ge 0}\) be the fraction of negotiation sessions pairing buyer type \(a\) with supplier type \(b\), with \(\sum_{a,b}\eta_{ab}=1\). The joint masses \(\eta_{ab}\), rather than only the marginals, preserve the matching structure between the two roles. After clearing denominators, \(\eta\) is exactly a finite population of repeated bilateral negotiations.
The agents’ information remains private: a buyer observes its own type and the public history, not the supplier’s type. The common prior over partner types is derived from \(\eta\), but is not revealed as an individual identity. A protocol \(G\) is a finite GBP rule table, including the assignment, responder, activation, filtering, update, and evaluation rules. TAU is one admissible \(G\). A strategy profile \(\pi\) is a type-contingent offering and selection policy, with WAR among the admissible policies.
For each type pair \((a,b)\), the protocol and strategy induce a finite or ultimately periodic transcript and an outcome \(\omega_{ab}\in\Omega^+\). WAR is represented exactly as in the paper: it offers irrational outcomes first, then rational outcomes in utility order, and repeats its final offer forever once repetition begins; selection accepts rational outcomes.
Define \(D_{ab}(G,\pi)\in[0,1]\) as the product of five normalized indicators: rationality, completeness, Pareto-optimality, ordinal Kalai fairness, and welfare. For the all-perfect version, each factor is \(1\) precisely when:
The continuous problem is:
\[ \max_{G,\pi}\; \Phi_\eta(G,\pi) = \sum_{a,b}\eta_{ab}D_{ab}(G,\pi), \]
subject to \(\pi\) being a Perfect Bayesian Equilibrium of every supported type-pair game. A solution consists of the protocol table \(G\), the type-contingent strategy table \(\pi\), an equilibrium belief system, and the induced transcripts. The decision version asks whether \(\Phi_\eta(G,\pi)\ge q\). The strict TAU/WAR verification problem fixes \(G=\mathrm{TAU}\), \(\pi=\mathrm{WAR}\), and asks whether \(\Phi_\eta=1\).
This is recognizably the paper’s question rather than an arbitrary fractional relaxation. The outcome of every negotiation remains one discrete \(\omega\) or \(\phi\); only the population of repeated negotiation scenarios becomes continuous. The paper itself uses procurement as its motivating example and explicitly speaks of protocol quality over sets of negotiation scenarios, so weighting repeated typed scenarios by \(\eta\) is something its authors could plausibly recognize.
The fixed TAU/WAR version is likely Class A: with explicit \(\Omega\) and finitely many types, each transcript and each metric can be checked in polynomial time, followed by a weighted sum. The broader protocol-synthesis version may be difficult because of protocol history and PBE constraints, but that difficulty would remain with a single type pair. It would therefore be protocol-design hardness, not continuum-specific hardness. The useful research questions are whether the all-perfect guarantee survives denominator clearing, how the optimum changes with the number of types, and whether one can optimize over an implicitly represented outcome space using configuration or separation methods.
The weakest point is substantial: this is an extension, not a direct population mirror. The paper studies a small number of agents inside one negotiation, while the proposed continuum is a population of repeated negotiation encounters. Moreover, TAU is history-sensitive, so individual type marginals alone are insufficient; the matching masses \(\eta_{ab}\) and clone-consistent tie-breaking are essential. Finally, because there is no numbered computational result in the paper, this positive case fails the programme’s strict anchor gate. I would defend the model as a credible ChoCo research problem inspired by the paper’s central TAU/WAR claim, but not as a formally anchored continuous mirror of a named complexity theorem.
The negative case is unusually strong because the strict anchor gate closes before modelling begins. This paper contains no numbered Theorem, Lemma, Corollary, or Proposition, and no complexity claim. Its central TAU/WAR statement is an unproved, unnumbered assertion about protocol performance. It is therefore not a qualifying computational result under ChoCo’s rules. A continuous mirror of it cannot be a mirror of a named computational theorem, because none is present.
Even if that gate is waived, the proposed \(\eta_{ab}\) model does not continuize the paper’s population. Each unit of \(\eta\) is a complete, independent negotiation scenario containing one buyer and one supplier. Clearing denominators produces many repeated sessions, not one negotiation involving a high-multiplicity society. The sessions do not interact; the protocol never observes \(\eta\); and changing the masses does not change any transcript, equilibrium, or agreement for a fixed type pair. The distribution merely supplies weights for averaging independently solved games.
That is a legitimate Bayesian or distributional protocol-evaluation problem, but it is not the paper’s computational problem placed over a continuous society. In the paper, the object is a protocol for a finite set of individually situated agents, with offers, threads, responders, activation order, and histories. The proposed continuum instead ranges over instances of that game. The distinction matters: a population of repeated procurement transactions is a plausible application story, but it makes the continuum a prior over negotiation scenarios rather than a population whose aggregate state is being computed or altered.
The proposed model also does not preserve the general GBP structure by type masses alone. In a multilateral negotiation, outcomes depend on the labelled ownership and responder graph, activation schedule, correlated private information, and complete negotiation history. A marginal distribution of agent types loses those relationships. Adding a joint distribution over all role assignments and histories would preserve them, but would produce a distribution over complete labelled games, not the paper’s continuous analogue. Adding a large interaction network would instead create a new network or graphon bargaining model. Either repair changes the problem rather than continuizing the TAU/WAR claim.
The proposed objective is not fully faithful either. The paper’s rationality, completeness, optimality, fairness, and welfare measures are defined as evaluation rates over negotiations or outcome spaces, not as five per-transcript indicators \(D_{ab}\). “PBE of every supported type-pair game” is also not the right equilibrium condition once partner types are uncertain: the relevant belief system belongs to a single Bayesian game over type profiles and histories. These defects are repairable, but the repaired formulation is an expected-score protocol-synthesis problem of the form
\[
\max_{G,\pi}\int D(s;G,\pi)\,d\nu(s),
\]
not a continuous-population version of the paper’s result.
The strongest charitable conclusion is therefore narrow. One could build a worthwhile research programme on anonymous or mean-field bargaining, or on protocol design under a continuous prior over utility types. But that would be a new negotiation-theory problem motivated by this paper, not a continuous mirror of one of its computational results. The universal impossibility claim cannot be proved—those new models may well be valuable—but under ChoCo’s population scope and anchor rule, this paper supplies no defensible continuous mirror.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.