Tackling the Protocol Problem in Automated Negotiation

Automated Negotiation (AN) is a research field with roots extending back to the mid-twentieth century. There are two dominant AN research directions pursued by the AAMAS community in recent years: (1) designing new heuristic or ML/RL/MARL-based strategies for the simplest bargaining mechanism called the Alternating Offers Protocol (AOP) and its extensions and (2) defining new mediated mechanisms that require a trusted third party. Intelligence lies in the strategy in the first direction and the mechanism in the latter. Either way, evaluation is almost always conducted in terms of empirical evaluation in some chosen set of negotiation scenarios. This paper argues for more efforts towards tackling the problem of protocol design in automated negotiation more rigorously by integrating ideas from mechanism-design literature. This requires, as a first step, a common language for expressing different negotiation protocols and strategies. We provide such a language which can represent a wide variety of negotiation protocols (both mediated and unmediated). We briefly outline our early effort in using this approach to provide a novel protocol with a provable Perfect Bayesian Equilibrium strategy that is also empirically effective.