In order to be accepted by negotiating parties, negotiation protocols need to be fair and unbiased. We extend the bilateral turn-taking negotiation protocol to multiparty multilateral turn-taking peer negotiation protocols maintaining its fairness properties. We define the de- sign space of such protocols and capture the design decisions that go into creating them. We use this design space to introduce two novel protocols adhering to the fairness prop- erties: Stacked Alternating Offer Protocol (SAOP) and Alternating Multi-offer Consensus Protocol (AMCP). A method for measuring speed and social welfare properties of multi- party multilateral turn-taking peer negotiation protocols is introduced and used to evaluate SAOP and AMCP using automated negotiation agents from the Automated Negotiation Agent Competition (ANAC). We show that against our expectations, the agents prefer to use the more complex AMCP protocol. Both protocols are usable in automated, human, and hybrid negotiations. The design space enables more informed design decisions when creating protocols and lays the foundation for further studies in finding desirable protocol properties that in turn improve the quality of the negotiation outcome.

This paper presents a general framework for multilateral turn-taking protocols and two fully specified protocols namely Stacked Alternating Offers Protocol (SAOP) and Alternating Multiple Offers Protocol (AMOP). In SAOP, agents can make a bid, accept the most recent bid or walk way (i.e., end the negotiation without an agreement) when it is their turn. AMOP has two different phases: bidding and voting. The agents make their bid in the bidding phase and vote the underlying bids in the voting phase. Unlike SAOP, AMOP does not support walking away option. In both protocols, negotiation ends when the negotiating agents reach a joint agreement or some deadline criterion applies. The protocols have been evaluated empirically, showing that SAOP outperforms AMOP with the same type of conceder agents in a time-based deadline setting. SAOP was used in the ANAC 2015 competition for automated negotiating agents.@en