Klein, Mark


Scalable Complex Contract Negotiation with Structured Search and Agenda Management

AAAI Conferences

A large number of interdependent issues in complex contract negotiation poses a significant challenge for current approaches, which becomes even more apparent when negotiation problems scale up. To address this challenge, we present a structured anytime search process with an agenda management mechanism using a hierarchical negotiation model, where agents search at various levels during the negotiation with the guidance of a mediator. This structured negotiation process increases computational efficiency, making negotiations scalable for large number of interdependent issues. To validate the contributions of our approach, 1) we developed our proposed negotiation model using a hierarchical problem structure and a constraint-based preference model for real-world applications; 2) we defined a scenario matrix to capture various characteristics of negotiation scenarios and developed a scenario generator that produces test cases according to this matrix; and 3) we performed an extensive set of experiments to study the performance of this structured negotiation protocol and the influence of different scenario parameters, and investigated the Pareto efficiency and social welfare optimality of the negotiation outcomes. The experimental result supports the hypothesis that this hierarchical negotiation approach greatly improves scalability with the complexity of the negotiation scenarios.


Preface

AAAI Conferences

Hybrid group autonomy, organizations and teams composed of humans, machines and robots, are important to AI. Unlike the war in Iraq in 2002, the war in Afghanistan has hundreds of mobile robots aloft, on land, or under the sea. But when it comes to solving problems as part of a team, these agents are socially passive. Were the problem of aggregation and the autonomy of hybrids to be solved, robot teams could accompa- ny humans to address and solve problems together on Mars, under the sea, or in dan- gerous locations on earth (such as, fire-fighting, reactor meltdowns, and future wars). “Robot autonomy is required because one soldier cannot control several robots ... [and] because no computational system can discriminate between combatants and innocents in a close-contact encounter.” (Sharkey, 2008) Yet, today, one of the fundamental unsolved problems in the social sciences is the aggregation of individual data (such as preferences) into group (team) data (Giles, 2011) The original motivation behind game theory was to study the effect that multi- ple agents have on each other (Von Neumann and Morgenstern, 1953), known as interdependence or mutual dependence. Essentially, the challenge addresses the ques- tion: why is a group different from the collection of individuals who comprise the group? That the problem remains unsolved almost 70 years later is a remarkable com- ment on the state of the social sciences today, including game theory and economics. But solving this challenge is essential for the science and engineering of multiagent, multirobot and hybrid environments (that is, humans, machines and robots working together).


Efficient Issue-Grouping Approach for Multi-Issues Negotiation between Exaggerator Agents

AAAI Conferences

Most real-world negotiation involves multiple interdependent issues, which makes an agent's utility functions complex. Traditional negotiation mechanisms, which were designed for linear utilities, do not fare well in nonlinear contexts. One of the main challenges in developing effective nonlinear negotiation protocols is scalability; it can be extremely difficult to find high-quality solutions when there are many issues, due to computational intractability. One reasonable approach to reducing computational cost, while maintaining good quality outcomes, is to decompose the contract space into several largely independent sub-spaces. In this paper, we propose a method for decomposing a contract space into sub-spaces based on the agent's utility functions. A mediator finds sub-contracts in each sub-space based on votes from the agents, and combines the sub-contracts to produce the final agreement. We demonstrate, experimentally, that our protocol allows high-optimality outcomes with greater scalability than previous efforts. We also address incentive compatibility issues. Any voting scheme introduces the potential for strategic non-truthful voting by the agents, and our method is no exception. For example, one of the agents may always vote truthfully, while the other exaggerates so that its votes are always "strong." It has been shown that this biases the negotiation outcomes to favor the exaggerator, at the cost of reduced social welfare. We employ the limitation of strong votes to the method of decomposing the contract space into several largely independent sub-spaces. We investigate whether and how this approach can be applied to the method of decomposing a contract space.



Thirteenth International Distributed AI Workshop

AI Magazine

This article discusses the Thirteenth International Distributed AI Workshop. An overview of the workshop is given as well as concerns and goals for the technology. This article discusses the Thirteenth International Distributed AI Workshop. An overview of the workshop is given as well as concerns and goals for the technology.


Thirteenth International Distributed AI Workshop

AI Magazine

This article discusses the Thirteenth International Distributed AI Workshop. An overview of the workshop is given as well as concerns and goals for the technology.