Yasser Mohammad, NEC Corporation

Abstract

Negotiation is an ubiquitous method for reaching agreement in human society. Computational analysis of negotiation has a long history even preceding Nash's seminal work in the fifties With the increased automation of business and industrial processes, Automated Negotiation (AN) is attracting more attention from of the AI community. AN provides a great benchmark for AI agents that lies between single-game solvers and general game playing agents.

Early work in AN focused on the design of mechanisms with theoretical guarantees in negotiations with perfect information. Real world AN applications are - invariably - imperfect information games where uncertainty is over the partner's preferences, ones own preferences, availability of outside options or concurrent negotiations which limits the applicability of these game-theoretic approaches.

Most recent work in AN focuses instead on either designing mediated mechanisms or developing negotiation strategies for the Alternating Offers Protocol (AOP). In both cases, decision theoretic - instead of game theoretic - approaches are used. Despite decades of research in designing negotiation strategies for AOP, there are no known strategies that give it sufficient theoretical guarantees (e.g. completeness, and Pareto-optimality, or even intrinsic guaranteed termination. In this talk, I will argue that this state of affairs is at least partially due to some features of AOP (and its most common multilateral extension SAOP) that make it extremely hard to reason about. It is time to re-examine AOP itself keeping its unmediated nature, simplicity, and applicability to realistic imperfect information scenarios while hunting for better alternative with - at least some - theoretical guarantees. I will also argue that the lack of theoretical guarantees is a emph{practical} problem that contributes to the delayed adoption of AN in businesses.

I will show that we can extend AOP to a much larger class of mechanisms called the Generalized Bargaining Mechanisms GBM that keep - almost - all of its advantages providing both a clear decomposition of the strategy into two policies and - more importantly - a clear decomposition of the mechanism into few component rules. Moreover, the talk provides specific evaluation criteria for both negotiation mechanisms and strategies.

GBMs provide a research program that is still in its infancy. I will describe the first result in which we propose a specific mechanism called Tentative Agreement Unique Offers Mechanism (TAU) that achieves simultaneously Pareto-optimality and completeness guarantees and for which a Bayes-Nash Equilibrium strategy can be found under the complete ignorance assumption. The talk will also present empirical evaluation supporting these theoretical results in which TAU with a simple strategy is shown to achieve better results in terms of welfare, individual utility, Pareto-optimality, completeness, and computational efficiency compared with AOP even using the best available state-of-the-art strategies and baselines for AOP.

The research program presented in this talk—with its promising first result—has the potential of introducing techniques from mechanism design for comparing mechanisms and finding new ones with desired properties to AN research.

[Presentation video]

Speaker Bio: Yasser Mohammad is a Principal Researcher at NEC CORPORATION, a visiting researcher at the National Institute for Advanced Industrial Science and Technology (AIST), Japan and an Associate Professor at Assiut University, Egypt. He received his PhD from Kyoto University, Japan in 2009 in the area of intelligence science and technology, and has since been conducting academic and industrial research in robotics, social intelligence, AI for business operations, and mining time-series data. His current research focuses on automated negotiation, and multi-agent systems. He is the recipient of four best paper awards from ICCAS 2012, IEEE/SICE SII 2011, IEA/AIE 2009, and IEA/AIE 2009 and the author of Conversational Informatics: A data intensive approach (Springer, 2015) and Data mining for Social Robotics (Springer, 2016).