Now or Never: Negotiating Efficiently with Unknown or
Untrusted Counterparts*
Issue title: Special issue of the 22nd RCRA International Workshop on “Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion”
Guest editors: Stefano Bistarelli, Andrea Formisano, Marco Maratea and Paolo Torroni
Affiliations: [a] Computer Science Department, Sapienza University of Rome, Italy [email protected]
Correspondence:
[†]
Address for correspondence: Computer Science Department, Sapienza University of Rome, Italy
Note: [*] This is an extended and revised version of [1].
Abstract: We define a new protocol rule, Now or Never (NoN), for bilateral negotiation processes which allows self-motivated competitive agents to efficiently carry out multi-variable negotiations with remote untrusted parties, where privacy is a major concern and agents know nothing about their opponent. By building on the geometric concepts of convexity and convex hull, NoN ensures a continuous progress of the negotiation, thus neutralising malicious or inefficient opponents. In particular, NoN allows an agent to derive in a finite number of steps, and independently of the behaviour of the opponent, that there is no hope to find an agreement. To be able to make such an inference, the interested agent may rely on herself only, still keeping the highest freedom in the choice of her strategy. We also propose an actual NoN-compliant strategy for an automated agent and evaluate the computational feasibility of the overall approach on both random negotiation scenarios and case studies of practical size.
