Now or Never: Negotiating Efficiently with Unknown or Untrusted Counterparts *

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.