Arrow Research search

Author name cluster

Efrat Manisterski

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.

7 papers
1 author row

Possible papers

7

AIJ Journal 2010 Journal Article

Solving coalitional resource games

  • Paul E. Dunne
  • Sarit Kraus
  • Efrat Manisterski
  • Michael Wooldridge

Coalitional Resource Games (crgs) are a form of Non-Transferable Utility (ntu) game, which provide a natural formal framework for modelling scenarios in which agents must pool scarce resources in order to achieve mutually satisfying sets of goals. Although a number of computational questions surrounding crgs have been studied, there has to date been no attempt to develop solution concepts for crgs, or techniques for constructing solutions. In this paper, we rectify this omission. Following a review of the crg framework and a discussion of related work, we formalise notions of coalition structures and the core for crgs, and investigate the complexity of questions such as determining nonemptiness of the core. We show that, while such questions are in general computationally hard, it is possible to check the stability of a coalition structure in time exponential in the number of goals in the system, but polynomial in the number of agents and resources. As a consequence, checking stability is feasible for systems with small or bounded numbers of goals. We then consider constructive approaches to generating coalition structures. We present a negotiation protocol for crgs, give an associated negotiation strategy, and prove that this strategy forms a subgame perfect equilibrium. We then show that coalition structures produced by the protocol satisfy several desirable properties: Pareto optimality, dummy player, and pseudo-symmetry.

Details DOI

AIJ Journal 2009 Journal Article

Computing the fault tolerance of multi-agent deployment

  • Yingqian Zhang
  • Efrat Manisterski
  • Sarit Kraus
  • V.S. Subrahmanian
  • David Peleg

A deployment of a multi-agent system on a network refers to the placement of one or more copies of each agent on network hosts, in such a manner that the memory constraints of each node are satisfied. Finding the deployment that is most likely to tolerate faults (i. e. have at least one copy of each agent functioning and in communication with other agents) is a challenge. In this paper, we address the problem of finding the probability of survival of a deployment (i. e. the probability that a deployment will tolerate faults), under the assumption that node failures are independent. We show that the problem of computing the survival probability of a deployment is at least NP-hard. Moreover, it is hard to approximate. We produce two algorithms to accurately compute the probability of survival of a deployment—these algorithms are expectedly exponential. We also produce five heuristic algorithms to estimate survival probabilities—these algorithms work in acceptable time frames. We report on a detailed set of experiments to determine the conditions under which some of these algorithms perform better than the others.

Details DOI

JAAMAS Journal 2009 Journal Article

Multi-goal economic search using dynamic search structures

  • David Sarne
  • Efrat Manisterski
  • Sarit Kraus

Abstract This paper investigates cooperative search strategies for agents engaged in costly search in a complex environment. Searching cooperatively, several search goals can be satisfied within a single search effort. Given the searchers’ preferences, the goal is to conduct a search in a way that the expected overall utility out of the set of opportunities found (e. g. , products when operating in a market) minus the costs associated with finding that set is maximized. This search scheme, given in the context of a group search, applies also to scenarios where a single agent has to search for a set of items for satisfying several different goals. The uniqueness of the proposed mechanism is in the ability to partition the group of agents/goals into sub-groups where the search continues for each group autonomously. As we show throughout the paper, this strategy is favorable as it weakly dominates (i. e. , can improve but never worsen) cooperative and autonomous search techniques. The paper presents a comprehensive analysis of the new search method and highlights the specific characteristics of the optimal search strategy. Furthermore, we introduce innovative algorithms for extracting the optimal search strategy in a range of common environments, that eliminates the computational overhead associated with the use of the partitioning technique.

Details DOI

IJCAI Conference 2007 Conference Paper

  • Efrat Manisterski
  • David Sarne
  • Sarit Kraus

In this paper we present new search strategies for agents with diverse preferences searching cooperatively in complex environments with search costs. The uniqueness of our proposed mechanism is in the integration of the coalition's ability to partition itself into sub-coalitions, which continue the search autonomously, into the search strategy (a capability that was neglected in earlier cooperative search models). As we show throughout the paper, this strategy is always favorable in comparison to currently known cooperative and autonomous search techniques: it has the potential to significantly improve the searchers' performance in various environments and in any case guarantees reaching at least as good a performance as that of other known methods. Furthermore, for many common environments we manage to significantly eliminate the consequential added computational complexity associated with the partitioning option, by introducing innovative efficient algorithms for extracting the coalition's optimal search strategy. We illustrate the advantages of the proposed model over currently known cooperative and individual search techniques, using an environment based on authentic settings.

PDF Details

IJCAI Conference 2007 Conference Paper

  • Efrat Manisterski
  • Ron Katz
  • Sarit Kraus

This paper presents a novel approach for providing automated trading agents to a population, focusing on bilateral negotiation with unenforceable agreements. A new type of agents, called semi-cooperative (SC) agents is proposed for this environment. When these agents negotiate with each other they reach a pareto-optimal solution that is mutually beneficial. Through extensive experiments we demonstrate the superiority of providing such agents for humans over supplying equilibrium agents or letting people design their own agents. These results are based on our observation that most people do not modify SC agents even though they are not in equilibrium. Our findings introduce a new factor ---human response to provided agents --- that should be taken into consideration when developing agents that are provided to a population.

PDF Details
v2026.09.13