Y. Luo and L. Bölöni

Analyzing and exploiting the competitiveness of scenarios for negotiating convoy formation under time constraints


Cite as:

Y. Luo and L. Bölöni. Analyzing and exploiting the competitiveness of scenarios for negotiating convoy formation under time constraints. Multiagent and Grid Systems - an International Journal, 6(5,6):415–435, December 2010. Special Issue of Advances in Agent-mediated Automated Negotiations

Download:

Download 

Abstract:

In the convoy formation problem, two embodied agents are negotiating the synchronization of their movement for a portion of the path from their respective sources to destinations. As equilibrium strategies are not practically possible, we are interested in strategies with bounded rationality, which achieve good performance in a wide range of practical negotiation scenarios. Naturally, the performance of a strategy is dependent on the strategy of the opponent and the characteristics of the scenario. The goal of this paper is to develop a \em collaborativeness metric of the negotiation scenario which formalizes our intuition of collaborative scenarios (where the agents' interests are closely aligned) versus competitive scenarios (where the gain of the utility for one agent is paid off with a loss of utility for the other agent). We are using the Children in the Rectangular Forest (CRF) game as a canonical model of convoy formation, assume zero initial knowledge and a negotiation protocol requiring mandatory, but non-binding evaluations of the opponents offer. We also assume that the negotiation happens in physical time. We describe two negotiation strategies: the comparatively simple Internal Negotiation Deadline (IND) strategy and the computationally more expensive Uniform Concession (UC) strategy. Then, we describe how these strategies can be augmented by collaborativeness analysis: we approximate the collaborativeness metric in the first several negotiation rounds, and use the result to cut short the negotiation when the estimated collaborativeness is lower than a threshold. Through an experimental study, we show that augmenting the strategies with collaborativeness analysis significantly improves their performance for low collaborativeness scenarios, with only a minimal penalty in high collaborativeness scenarios.

BibTeX:

@article{Luo-2010-MAGS,
    author = "Y. Luo and L. B{\"o}l{\"o}ni",
    title = "Analyzing and exploiting the competitiveness of scenarios for negotiating convoy formation under time constraints",
    journal = "Multiagent and Grid Systems - an International Journal",
    note = "Special Issue of Advances in Agent-mediated Automated Negotiations",
    year = "2010",
    volume = {6},
    number = {5,6},
    month = {December},
    issn = {1574-1702},
    pages = {415--435},
    abstract = {
    In the convoy formation problem, two embodied agents are negotiating
    the synchronization of their movement for a portion of the path from
    their respective sources to destinations. As equilibrium strategies
    are not practically possible, we are interested in strategies with
    bounded rationality, which achieve good performance in a wide range
    of practical negotiation scenarios. Naturally, the performance of a
    strategy is dependent on the strategy of the opponent and the
    characteristics of the scenario. The goal of this paper is to
    develop a {\em collaborativeness metric} of the negotiation scenario
    which formalizes our intuition of collaborative scenarios (where the
    agents' interests are closely aligned) versus competitive scenarios
    (where the gain of the utility for one agent is paid off with a loss
    of utility for the other agent).
    We are using the Children in the Rectangular Forest (CRF) game as a
    canonical model of convoy formation, assume zero initial knowledge
    and a negotiation protocol requiring mandatory, but non-binding
    evaluations of the opponents offer. We also assume that the
    negotiation happens in physical time. We describe two negotiation
    strategies: the comparatively simple Internal Negotiation Deadline
    (IND) strategy and the computationally more expensive Uniform
    Concession (UC) strategy. Then, we describe how these strategies can
    be augmented by collaborativeness analysis: we approximate the
    collaborativeness metric in the first several negotiation rounds,
    and use the result to cut short the negotiation when the estimated
    collaborativeness is lower than a threshold. Through an experimental
    study, we show that augmenting the strategies with collaborativeness
    analysis significantly improves their performance for low
    collaborativeness scenarios, with only a minimal penalty in high
    collaborativeness scenarios.
    },
}

Generated by bib2html.pl (written by Patrick Riley, Lotzi Boloni ) on Fri Oct 06, 2017 18:15:24