262,569 research outputs found
Stratum: A methodology for designing heuristic agent negotiation strategies.
Full text linkAutomated negotiation is a powerful (and sometimes essential) means for allocating resources among self-interested autonomous software agents. A key problem in building negotiating agents is the design of the negotiation strategy, which is used by an agent to decide its negotiation behaviour. In complex domains, there is no single, obvious optimal strategy. This has led to much work on designing heuristic strategies, where agent designers usually rely on intuition and experience. In this paper, we introduce STRATUM, a methodology for designing strategies for negotiating agents. The methodology provides a disciplined approach to analysing the negotiation environment and designing strategies in light of agent capabilities, and acts as a bridge between theoretical studies of automated negotiation and the software engineering of negotiation applications. We illustrate the application of the methodology by characterising some strategies for the Trading Agent Competition and for argumentation-based negotiation
Argument-based negotiation within a social context
No full textArgumentation-based negotiation (ABN) provides agents with an effective means to resolve conflicts within a multi-agent society. However, to engage in such argumentative encounters the agents require the ability to generate arguments, which, in turn, demands four fundamental capabilities: a schema to reason in a social context, a mechanism to identify a suitable set of arguments, a language and a protocol to exchange these arguments, and a decision making functionality to generate such dialogues. This paper focuses on the first two issues and formulates models to capture them. Specifically, we propose a coherent schema, based on social commitments, to capture social influences emanating from the roles and relationships of a multi-agent society. After explaining how agents can use this schema to reason within a society, we then use it to identify two major ways of exploiting social influence within ABN to resolve conflicts. The first of these allows agents to argue about the validity of each other’s social reasoning, whereas the second enables agents to exploit social influences by incorporating them as parameters within their negotiation. For each of these, we use our schema to systematically capture a comprehensive set of social arguments that can be used within a multi-agent society
Algorithms for coalition formation in multi-agent systems
Full text linkCoalition formation is a fundamental form of interaction that allows the creation of coherent groupings of distinct, autonomous, agents in order to efficiently achieve their individual or collective goals. Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining which of the possible coalitions to form in order to achieve some goal. This usually requires calculating a value for every possible coalition, known as the coalition value, which indicates how beneficial that coalition would be if it was formed. Now since the number of possible coalitions grows exponentially with the number of agents involved, then, instead of having a single agent calculate all these values, it would be more efficient to distribute this calculation among all agents, thus, exploiting all computational resources that are available to the system, and preventing the existence of a single point of failure.Against this background, we develop a novel algorithm for distributing the value calculation among the cooperative agents. Specifically, by using our algorithm, each agent is assigned some part of the calculation such that the agents' shares are exhaustive and disjoint. Moreover, the algorithm is decentralized, requires no communication between the agents, has minimal memory requirements, and can reflect variations in the computational speeds of the agents. To evaluate the effectiveness of our algorithm we compare it with the only other algorithm available in the literature for distributing the coalitional value calculations (due to Shehory and Kraus). This shows that for the case of 25 agents, the distribution process of our algorithm took less than 0.02% of the time, the values were calculated using 0.000006% of the memory, the calculation redundancy was reduced from 383229848 to 0, and the total number of bytes sent between the agents dropped from 1146989648 to 0. Note that for larger numbers of agents, these improvements become exponentially better.Once the coalitional values are calculated, the agents usually need to find a combination of coalitions in which every agent belongs to exactly one coalition, and by which the overall outcome of the system is maximized. This problem, which is widely known as the coalition structure generation problem, is extremely challenging due to the number of possible combinations which grows very quickly as the number of agents increases, making it impossible to go through the entire search space, even for small numbers of agents. Given this, many algorithms have been proposed to solve this problem using different techniques, ranging from dynamic programming, to integer programming, to stochastic search, all of which suffer from major limitations relating to execution time, solution quality, and memory requirements.With this in mind, we develop a novel, anytime algorithm for solving the coalition structure generation problem. Specifically, the algorithm can generate solutions by partitioning the space of all potential coalition structures into sub-spaces containing coalition structures that are similar, according to some criterion, such that these sub-spaces can be pruned by identifying their bounds. Using this representation, the algorithm can then search through the selected sub-space(s) very efficiently using a branch-and-bound technique. We empirically show that we are able to find solutions that are optimal in 0.082% of the time required by the fastest available algorithm in the literature (for 27 agents), and that is using only 33% of the memory required by that algorithm. Moreover, our algorithm is the first to be able to solve the coalition structure generation problem for numbers of agents bigger than 27 in reasonable time (less than 90 minutes for 30 agents as opposed to around 2 months for the current state of the art). The algorithm is anytime, and if interrupted before it would have normally terminated, it can still provide a solution that is guaranteed to be within a bound from the optimal one. Moreover, the guarantees we provide on the quality of the solution are significantly better than those provided by the previous state of the art algorithms designed for this purpose. For example, given 21 agents, and after only 0.0000002% of the search space has been searched, our algorithm usually guarantees that the solution quality is no worse than 91% of optimal value, while previous algorithms only guarantees 9.52%. Moreover, our guarantee usually reaches 100% after 0.0000019% of the space has been searched, while the guarantee provided by other algorithms can never go beyond 50% until the whole space has been searched. Again note that these improvements become exponentially better given larger numbers of agents
Managing Social Influences through Argumentation-Based Negotiation
No full textSocial influences play an important part in the actions that an individual agent may perform within a multi-agent society. However, the incomplete knowledge and the diverse and conflicting influences present within such societies, may stop an agent from abiding by all its social influences. This may, in turn, lead to conflicts that the agents need to identify, manage, and resolve in order for the society to behave in a coherent manner. To this end, we present an empirical study of an argumentation-based negotiation (ABN) approach that allows the agents to detect such conflicts, and then manage and resolve them through the use of argumentative dialogues. To test our theory, we map our ABN model to a multi-agent task allocation scenario. Our results show that using an argumentation approach allows agents to both efficiently and effectively manage their social influences even under high degrees of incompleteness. Finally, we show that allowing agents to argue and resolve such conflicts early in the negotiation encounter increases their efficiency in managing social influences
Computational Aspects of Extending the Shapley Value to Coalitional Games with Externalities
No full textUntil recently, computational aspects of the Shapley value were only studied under the assumption that there are no externalities from coalition formation, i.e., that the value of any coalition is independent of other coalitions in the system. However, externalities play a key role in many real-life situations and have been extensively studied in the game-theoretic and economic literature. In this paper, we consider the issue of computing extensions of the Shapley value to coalitional games with externalities proposed by Myerson [21], Pham Do and Norde [23], and McQuillin [17]. To facilitate efficient computation of these extensions, we propose a new representation for coalitional games with externalities, which is based on weighted logical expressions. We demonstrate that this representation is fully expressive and, sometimes, exponentially more concise than the conventional partition function game model. Furthermore, it allows us to compute the aforementioned extensions of the Shapley value in time linear in the size of the input
Arguing and negotiating in the presence of social influences
Full text linkWhen agents operate in a society with incomplete information and with diverse and conflicting influences, they may, in certain instances, lack the knowledge, the motivation and/or the capacity to enact all their commitments. However, to function as a coherent society it is important for these agents to have a means to resolve such conflicts and to come to a mutual understanding about their actions. To this end, argumentation-based negotiation provides agents with an effective means to resolve conflicts within a multi-agent society. However, to engage in such argumentative encounters, agents require four fundamental capabilities; a schema to reason in a social context, a mechanism to identify a suitable set of arguments, a language and a protocol to exchange these arguments, and a decision making functionality to generate such dialogues. This paper presents formulations of all of these capabilities and proposes a coherent framework that allows agents to argue, negotiate, and, thereby, resolve conflicts within a multi-agent society
Towards Scalable Governance: Sensemaking and Cooperation in the Age of Social Media
No full textCybernetics, or self-governance of animal and machine, requires the ability to sense the world and to act on it in an appropriate manner. Likewise, self-governance of a human society requires groups of people to collectively sense and act on their environment. I argue that the evolution of political systems is characterized by a series of innovations that attempt to solve (among others) two ‘scalability’ problems: scaling up a group’s ability to make sense of an increasingly complex world, and to cooperate in increasingly larger groups. I then explore some recent efforts toward using the Internet and social media to provide alternative means for addressing these scalability challenges, under the banners of crowdsourcing and computer-supported argumentation. I present some lessons from those efforts about the limits of technology, and the research directions more likely to bear fruit
Agent-based support for mobile users using AgentSpeak(L)
Full text linkThis paper describes AbIMA, an agent-based intelligent mobile assistant for supporting users prior to and during the execution of their tasks. The agent is based on the well-known AgentSpeak(L) agent architecture and programming language, which provides explicit representations of agents’ beliefs, desires and intentions (BDI). AbIMA is implemented using Java 2 Mobile Edition and is tested on a hand-held computer. We also provide conceptual foundations and discuss various challenges relating to the use of cognitive agent architectures for intelligent mobile user support
Formal Semantics of ABN Framework
No full textThis technical document extend upon and give formal meaning to the syntactic definitions presented in [7] and forwards the formal semantics of our argumentation-based negotiation (ABN) dialogue game protocol, which allows agents to argue, negotiate and resolve conflicts in a multi-agent context
- …
