Arrow Research search

Author name cluster

Onn Shehory

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

22 papers
2 author rows

Possible papers

22

EAAI Journal 2020 Journal Article

Coalition formation with dynamically changing externalities

  • Youcef Sklab
  • Samir Aknine
  • Onn Shehory
  • AbdelKamel Tari

We consider multiple self-interested bounded-rational agents each of which has a goal it needs to achieve. Goals are achievable by executing a set of interdependent tasks. Some tasks exhibit time dependencies and may require sequential execution. For each agent, there may be several alternative sets of tasks that can achieve the goal. Execution of alternatives, may be more beneficial when done by a group of agents and not by a single agent. To jointly achieve goals, agents may form interdependent coalitions. Such coalition formation is computationally intractable. We nevertheless seek a practical solution that is not necessarily optimal yet acceptable by the agents. A solution where agents examine only coalitions in which they are members is inapplicable, as externalities are a major factor given task interdependencies. In this paper we study this coalition formation problem. We describe the problem and introduce a novel Multi-lateral Negotiation Protocol ( MNP ) that solves it by forming interdependent coalitions. We allow agents to heuristically make gradual concessions, revise their proposals and converge on specific alternatives, and nevertheless increase their expected gains.

Details DOI

JAAMAS Journal 2014 Journal Article

Two-sided search with experts

  • Yinon Nahum
  • David Sarne
  • Onn Shehory

Abstract In this paper we study distributed agent matching in environments characterized by uncertain signals, costly exploration, and the presence of an information broker. Each agent receives information about the potential value of matching with others. This information signal may, however, be noisy, and the agent incurs some cost in receiving it. If all candidate agents agree to the matching the team is formed and each agent receives the true unknown utility of the matching, and leaves the market. We consider the effect of the presence of information brokers, or experts, on the outcomes of such matching processes. Experts can, upon payment of either a fee or a commission, perform the service of disambiguating noisy signals and revealing the true value of a match to any agent. We analyze equilibrium behavior given the fee set by a monopolist expert and use this analysis to derive the revenue maximizing strategy for the expert as the first mover in a Stackelberg game. Interestingly, we find that better information can hurt: the presence of the expert, even if the use of her services is optional, can degrade both individual agents’ utilities and overall social welfare. While in one-sided search the presence of the expert can only help, in two-sided (and general \(k\) -sided) search the externality imposed by the fact that others are consulting the expert can lead to a situation where the equilibrium outcome is that everyone consults the expert, even though all agents would be better off if the expert were not present. As an antidote, we show how market designers can enhance welfare by compensating the expert to change the price at which she offers her services.

Details DOI

AIJ Journal 2008 Journal Article

A study of mechanisms for improving robotic group performance

  • Avi Rosenfeld
  • Gal A. Kaminka
  • Sarit Kraus
  • Onn Shehory

Many collaborative multi-robot application domains have limited areas of operation that cause spatial conflicts between robotic teammates. These spatial conflicts can cause the team's productivity to drop with the addition of robots. This phenomenon is impacted by the coordination methods used by the team-members, as different coordination methods yield radically different productivity results. However, selecting the best coordination method to be used by teammates is a formidable task. This paper presents techniques for creating adaptive coordination methods to address this challenge. We first present a combined coordination cost measure, CCC, to quantify the cost of group interactions. Our measure is useful for facilitating comparison between coordination methods, even when multiple cost factors are considered. We consistently find that as CCC values grow, group productivity falls. Using the CCC, we create adaptive coordination techniques that are able to dynamically adjust the efforts spent on coordination to match the number of perceived coordination conflicts in a group. We present two adaptation heuristics that are completely distributed and require no communication between robots. Using these heuristics, robots independently estimate their combined coordination cost (CCC), adjust their coordination methods to minimize it, and increase group productivity. We use simulated robots to perform thousands of experiment trials to demonstrate the efficacy of our approach. We show that using adaptive coordination methods create a statistically significant improvement in productivity over static methods, regardless of the group size.

Details DOI

ECAI Conference 2006 Conference Paper

Reaching Agreements for Coalition Formation Through Derivation of Agents' Intentions

  • Samir Aknine
  • Onn Shehory

This paper addresses the coalition formation problem in multiagent systems. Although several coalition formation models exist today, coalition formation using these models remains costly. As a consequence, applying these models through several iterations when required becomes time-consuming. This paper proposes a new coalition formation mechanism (CFM) to reduce this execution cost. This mechanism is based on four principles: (1) the use of information on task relationships so as to reduce the computational complexity of the coalition formation; (2) the exploitation of the coalition proposals formulated by certain agents in order to derive their intentions, (this principle makes the search for solutions easier, which in turn may result in earlier consensus and agreements-the intention derivation process is performed on a new graph structure introduced in this paper); (3) the use of several strategies for propagating the proposals of the agents in the coalition formation process; and (4) the dynamic reorganization of previous coalitions.

Details

AIJ Journal 1999 Journal Article

Coalition structure generation with worst case guarantees

  • Tuomas Sandholm
  • Kate Larson
  • Martin Andersson
  • Onn Shehory
  • Fernando Tohmé

Coalition formation is a key topic in multiagent systems. One may prefer a coalition structure that maximizes the sum of the values of the coalitions, but often the number of coalition structures is too large to allow exhaustive search for the optimal one. Furthermore, finding the optimal coalition structure is NP -complete. But then, can the coalition structure found via a partial search be guaranteed to be within a bound from optimum? We show that none of the previous coalition structure generation algorithms can establish any bound because they search fewer nodes than a threshold that we show necessary for establishing a bound. We present an algorithm that establishes a tight bound within this minimal amount of search, and show that any other algorithm would have to search strictly more. The fraction of nodes needed to be searched approaches zero as the number of agents grows. If additional time remains, our anytime algorithm searches further, and establishes a progressively lower tight bound. Surprisingly, just searching one more node drops the bound in half. As desired, our algorithm lowers the bound rapidly early on, and exhibits diminishing returns to computation. It also significantly outperforms its obvious contenders. Finally, we show how to distribute the desired search across self-interested manipulative agents.

Details DOI

AIJ Journal 1999 Journal Article

Emergent cooperative goal-satisfaction in large-scale automated-agent systems

  • Onn Shehory
  • Sarit Kraus
  • Osher Yadgar

Cooperation among autonomous agents has been discussed in the DAI community for several years. Papers about cooperation (Conte et al. , 1991; Rosenschein, 1986), negotiation (Kraus and Wilkenfeld, 1991), distributed planning (Conry et al. , 1988), and coalition formation (Ketchpel, 1994; Sandholm and Lesser, 1997), have provided a variety of approaches and several algorithms and solutions to situations wherein cooperation is possible. However, the case of cooperation in large-scale multi-agent systems (MAS) has not been thoroughly examined. Therefore, in this paper we present a framework for cooperative goal-satisfaction in large-scale environments focusing on a low-complexity physics-oriented approach. The multi-agent systems with which we deal are modeled by a physics-oriented model. According to the model, MAS inherit physical properties, and therefore the evolution of the computational systems is similar to the evolution of physical systems. To enable implementation of the model, we provide a detailed algorithm to be used by a single agent within the system. The model and the algorithm are appropriate for large-scale, dynamic, Distributed Problem Solver systems, in which agents try to increase the benefits of the whole system. The complexity is very low, and in some specific cases it is proved to be optimal. The analysis and assessment of the algorithm are performed via the well-known behavior and properties of the modeling physical system.

Details DOI

AIJ Journal 1998 Journal Article

Methods for task allocation via agent coalition formation

  • Onn Shehory
  • Sarit Kraus

Task execution in multi-agent environments may require cooperation among agents. Given a set of agents and a set of tasks which they have to satisfy, we consider situations where each task should be attached to a group of agents that will perform the task. Task allocation to groups of agents is necessary when tasks cannot be performed by a single agent. However it may also be beneficial when groups perform more efficiently with respect to the single agents' performance. In this paper we present several solutions to the problem of task allocation among autonomous agents, and suggest that the agents form coalitions in order to perform tasks or improve the efficiency of their performance. We present efficient distributed algorithms with low ratio bounds and with low computational complexities. These properties are proven theoretically and supported by simulations and an implementation in an agent system. Our methods are based on both the algorithmic aspects of combinatorics and approximation algorithms for NP-hard problems. We first present an approach to agent coalition formation where each agent must be a member of only one coalition. Next, we present the domain of overlapping coalitions. We proceed with a discussion of the domain where tasks may have a precedence order. Finally, we discuss the case of implementation in an open, dynamic agent system. For each case we provide an algorithm that will lead agents to the formation of coalitions, where each coalition is assigned a task. Our algorithms are any-time algorithms, they are simple, efficient and easy to implement.

Details DOI

AAAI Conference 1996 Conference Paper

A Kernel-Oriented Model for Coalition-Formation in General Environments: Implementation and Results

  • Onn Shehory

In this paper we present a model for coalition formation and payoff distribution in general environments. We focus on a reduced complexity kernel-oriented coalition formation model, and provide a detailed algorithm for the activity of the single rational agent. The model is partitioned into a social level and a strategic level, to distinguish between regulations that must be agreed upon and are forced by agent-designers, and strategies by which each agent acts at will. In addition, we present an implementation of the model and simulation results. From these we conclude that implementing the model for coalition formation among agents increases the benefits of the agents with reasonable time consumption. It also shows that more coalition formations yield more benefits to the agents.

PDF Details

IJCAI Conference 1995 Conference Paper

Task allocation via coalition formation among autonomous agents

  • Onn Shehory
  • Sarit Kraus

Autonomous agents working in multi-agent environments may need to cooperate in order to fulfill tasks. Given a set of agents and a set of tasks which they have to satisfy, we consider situations where each task should be attached to a group of agents which will perform the task. The allocation of tasks to groups of agents is necessary when tasks cannot be performed by a single agent. It may also be useful to assign groups of agents to tasks when the group's performance is more efficient than the performance of single agents. In this paper we give an efficient solution to the problem of task allocation among autonomous agents, and suggest that the agents will form coalitions in order to perform tasks or improve the efficiency. We present a distributed algorithm with a low ratio bound and with a low computational complexity. Our algorithm is an any-time algorithm, it is simple, efficient and easy to implement.

PDF
v2026.09.13