Abstract Humanity needs to deliberate effectively at scale about highly complex and contentious problems. Current online deliberation tools—such as email, chatrooms, and forums—are however plagued by levels of discussion toxicity that deeply undercut the willingness and ability of the participants to engage in thoughtful, meaningful, deliberations. This has led many organizations to either shut down their forums or invest in expensive, frequently unreliable, and ethically fraught moderation of people's contributions in their forums. This paper includes a comprehensive review on online toxicity, and describes how a structured deliberation process can substantially reduce toxicity compared to current approaches. The key underlying insight is that unstructured conversations create, especially at scale, an “attention wars” dynamic wherein people are often incented to resort to extremified language in order to get visibility for their postings. A structured deliberation process wherein people collaboratively create a compact organized collection of answers and arguments removes this underlying incentive, and results, in our evaluation, in a 50% reduction of high-toxicity posts.

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.

Most real‐world negotiation involves multiple interdependent issues, which makes an agent’s utility functions nonlinear. 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; they cannot find a high‐quality solution 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 utility space into several largely independent subspaces. In this paper, we propose a method for decomposing a utility space based on every agent’s utility space. In addition, the mediator finds the contracts in each group based on the votes from all agents, and combines the contract in each issue‐group. This method allows good outcomes with greater scalability than the method without issue‐grouping. We demonstrate that our protocol, based on issue‐groups, has a higher optimality rate than previous efforts, and discuss the impact on the optimality of the negotiation outcomes.

There is an increasing interest in complex automated negotiations, where agents negotiate about multiple, interdependent issues and agent utility functions exhibit low autocorrelation. In these scenarios, the negotiation mechanisms used to find agreement solutions among agents tend to fail due to the complexity of agents’ preference spaces, and this tendency increases as the degree of autocorrelation decreases. In this paper, we propose an automated negotiation model specially tailored for highly uncorrelated utility spaces based on weighted constraints. The model relies on a mediated, auction‐based interaction protocol and a set of heuristic mechanisms for bidding and deal identification. To address the challenges raised by highly uncorrelated utility spaces, we propose to use a quality factor, which allows agents to balance utility and deal probability when placing their bids or when searching for agreement regions among these bids. Experiments show that the proposed negotiation model achieves high optimality results and low failure rates even in negotiation scenarios involving highly uncorrelated utility spaces, thus outperforming previous approaches.

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.

Distributed computing systems are increasingly being created as self-organizing collections of many autonomous (human or software) agents cooperating as peers. Peer-to-peer coordination introduces, however, unique and potentially serious challenges. When there is no one "in charge", dysfunctions can emerge as the collective effect of locally reasonable decisions. In this paper, we consider the dysfunction wherein inefficient resource use oscillations occur due to delayed status information, and describe novel approaches, based on the selective use of misinformation, for dealing with this problem. A model of several servers offering equivalent service to independent clients is presented and studied numerically and analytically; the spreading of misinformation about the queue status is found to dampen oscillations and improve system performance for a wide range of parameters.

Collaborative design is challenging because strong interdependencies between design issues make it difficult to converge on a single design that satisfies these dependencies and is acceptable to all participants. Complex systems research has much to offer to the understanding of these dynamics. This paper describes some insights from the complex systems perspective.

Software agent marketplaces require the development of new architectures, which are capable of coping with unreliable computational and network infrastructures, limited trust among independently developed agents and the possibility of systemic failures.In analogy with human societies, agent marketplaces will benefit from the introduction of appropriate electronic exception handling institutions, whose role will be to help guarantee efficiency and fairness in the face of these challenges.This paper presents a research methodology for designing and evaluating such electronic institutions.It also describes how the methodology has been applied in order to design and evaluate an exception handling architecture for robust software agent marketplaces based on the contract net protocol.