Multiagent System Projects at Hebrew University

The Multiagent Systems Research Group is involved in a wide variety of research projects, covering both theoretical topics as well as implemented simulations. What follows are brief descriptions of a selection of these current (and recent) projects.

• A Strategic/Tactical Architecture for Planning in Dynamic Environments: PhD student Zinovi Rabinovich has been working on a novel planning architecture that is composed of strategic and tactical layers. The planning architecture is motivated by the requirements of dynamic systems, and it provides a clearly-defined optimality measure for an agent operating in a stochastic environment. Although the architecture can be applied in any domain, it is thus particularly well-suited to highly dynamic environments. This work has led to the creation of Extended Markov Tracking (EMT), a computationally tractable method for the online estimation of Markovian system dynamics. We have applied this approach to both single-agent control (including robot-tracking simulations) and multiagent coordination; the control architecture in both cases leverages EMT to simultaneously track and correct system dynamics. In the following papers, preliminary experimental results are presented, along with the relevant mathematical model:

  On the Response of EMT-based Control to Interacting Targets and Models, Zinovi Rabinovich and Jeffrey S. Rosenschein. The Fifth International Joint Conference on Autonomous Agents and Multiagent Systems, Hakodate, Japan, May 2006. To appear.

  Dynamics Based Control: An Introduction, Zinovi Rabinovich and Jeffrey S. Rosenschein. The Third European Workshop on Multi-Agent Systems (EUMAS'05), Brussels, Belgium, December 2005, pages 323--331.

  Multiagent Coordination by Extended Markov Tracking, Zinovi Rabinovich and Jeffrey S. Rosenschein. The Fourth International Joint Conference on Autonomous Agents and Multiagent Systems, Utrecht, The Netherlands, July 2005, pages 431-438 (nominated for best student paper).

• Junta Distributions and the Average-Case Complexity of Manipulating Elections: Encouraging voters to truthfully reveal their preferences in an election has long been an important topic of research. Previous studies have shown that some voting protocols are hard to manipulate, but predictably used NP-hardness as the complexity measure. Such a worst-case analysis may be an insufficient guarantee of resistance to manipulation, and PhD student Ariel Procaccia has demonstrated that NP-hard manipulations may be tractable in the average-case. For this purpose, Ariel augmented the existing theory of average-case complexity with new concepts; he considered elections distributed with respect to junta distributions, which concentrate on hard instances, and introduced a notion of heuristic polynomial time. Ariel used those techniques to prove that a family of important voting protocols is susceptible to manipulation by coalitions, when the number of candidates is constant. This work is reported on in the following papers:

  Junta Distributions and the Average-Case Complexity of Manipulating Elections, Ariel D. Procaccia and Jeffrey S. Rosenschein. The Fifth International Joint Conference on Autonomous Agents and Multiagent Systems, Hakodate, Japan, May 2006. To appear.

  Junta Distributions and the Average-Case Complexity of Manipulating Elections, Ariel D. Procaccia and Jeffrey S. Rosenschein. The Third European Workshop on Multi-Agent Systems (EUMAS'05), Brussels, Belgium, December 2005, pages 282--291.

• Communication Complexity of Coalition Formation: Negotiating a stable distribution of the payoff between agents in a coalition can be difficult. The issue of coalition formation has been investigated extensively in the field of cooperative n-person game theory, but until recently little attention has been given to the complications that arise when the players are software agents. The bounded rationality of such agents has motivated researchers to study the computational complexity of the aforementioned problems. Ariel Procaccia and I have started to examine the communication complexity of coalition formation, in an environment where each of the n agents knows only its own initial resources and utility function. Specifically, we have given a tight Theta(n) bound on the communication complexity of the the following solution concepts: Shapley value, the nucleolus and the modified nucleolus, equal excess theory, and the core. This work is reported on in the following papers:

  The Communication Complexity of Coalition Formation Among Autonomous Agents, Ariel D. Procaccia and Jeffrey S. Rosenschein. The Fifth International Joint Conference on Autonomous Agents and Multiagent Systems, Hakodate, Japan, May 2006. To appear.

  The Communication Complexity of Coalition Formation among Autonomous Agents, Ariel D. Procaccia and Jeffrey S. Rosenschein. The Third European Workshop on Multi-Agent Systems (EUMAS'05), Brussels, Belgium, December 2005, pages 292--301.

• Learning to Identify Winning Coalitions in the PAC Model: Agents situated in a real-world setting may frequently lack complete knowledge of their environment and the capabilities of other agents. Researchers have addressed this problem by exploiting tools from learning theory. In particular, advances in reinforcement learning have yielded learning algorithms that converge to different solution concepts for stochastic games. However, scarcely any studies have attempted to tackle learning in coalition formation, and even fewer have applied the widely known Probably Approximately Correct (PAC) theory to multiagent systems. Ariel Procaccia has begun to consider PAC learning of simple cooperative games, in which the coalitions are partitioned into "winning" and "losing" coalitions. He analyzes the sample complexity of a suitable concept class by calculating its Vapnik-Chervonenkis (VC) dimension, and provides an algorithm that learns this class. He has also studied constrained simple games, and demonstrated that the VC dimension can be dramatically reduced when there exists only a single minimum winning coalition (even more so when this coalition has cardinality 1), while other interesting constraints do not significantly lower the dimension. This work is reported on in the following papers:

  Learning to Identify Winning Coalitions in the PAC Model, Ariel D. Procaccia and Jeffrey S. Rosenschein. The Fifth International Joint Conference on Autonomous Agents and Multiagent Systems, Hakodate, Japan, May 2006. To appear (short paper).

  Learning to Identify Winning Coalitions in the PAC Model, Ariel D. Procaccia and Jeffrey S. Rosenschein. The Third European Workshop on Multi-Agent Systems (EUMAS'05), Brussels, Belgium, December 2005, pages 302--311.

• Behaviosites: Masters student Amit Shabtay has been developing the Behaviosite paradigm, a new approach to affecting the behavior of distributed agents in a multiagent system, which is inspired by biological parasites with behavior manipulation properties. Behaviosites are special kinds of agents that "infect" a system composed of agents operating in that environment. The behaviosites facilitate behavioral changes in agents to achieve altered, potentially improved, performance of the overall system. Behaviosites need to be designed so that they are intimately familiar with the internal workings of the environment and of the agents operating within it, and behaviosites apply this knowledge for their manipulation, using various infection and manipulation strategies. To demonstrate and test this paradigm, we implemented a version of the El Farol problem, where agents want to go to a bar of limited capacity, and cannot use communication to coordinate their activity. Several solutions to this problem exist, but most yield near zero utility for the agents. We added behaviosites to the El Farol problem, and showed that social utility and social fairness increase significantly, with little actual damage to the overall system, and none to the agents. This work is reported on in the following paper:

  Behaviosites: A Novel Paradigm for Affecting Distributed Behavior, Amit Shabtay, Zinovi Rabinovich and Jeffrey S. Rosenschein. The Fifth International Joint Conference on Autonomous Agents and Multiagent Systems, Hakodate, Japan, May 2006. To appear (short paper).

• Information Elicitation: Masters student Aviv Zohar has studied information elicitation mechanisms in which a principal agent attempts to elicit the private information of other agents using a carefully selected payment scheme based on proper scoring rules. Scoring rules, like many other mechanisms set in a probabilistic environment, assume that all participating agents share some common belief about the underlying probability of events. In real-life situations however, the underlying distributions are not known precisely, and small differences in beliefs of agents about these distributions may alter their behavior under the prescribed mechanism. The intent is to design elicitation mechanisms in a manner that will be robust to small changes in belief, and Aviv has shown how to algorithmically design such mechanisms in polynomial time using tools of stochastic programming and convex programming. This work was reported on in the following paper:

  Robust Mechanisms for Information Elicitation, Aviv Zohar and Jeffrey S. Rosenschein. The Fifth International Joint Conference on Autonomous Agents and Multiagent Systems, Hakodate, Japan, May 2006. To appear (short paper).

• On the Complexity of Achieving Proportional Representation: Ariel Procaccia and Aviv Zohar have demonstrated that winner selection in two prominent proportional representation voting systems is a computationally intractable (namely, NP-complete) problem --- implying that these systems are impractical when the assembly is large. On a different note, in settings where the size of the assembly is constant, they showed that the problem can be solved in polynomial time. This work is reported on in the following paper:

  On the Complexity of Achieving Proportional Representation, Ariel D. Procaccia, Jeffrey S. Rosenschein, and Aviv Zohar. Social Choice and Welfare. Submitted.

• Extensive-Form Argumentation Games: Two prevalent approaches to automated negotiation are the application of game-theoretic notions and the argumentation-based angle; these two schemes are frequently at odds. Ariel Procaccia has enhanced the abstract argumentation framework by considering two-agent settings where each of the agents is identified with a set of arguments. A binary attack relation between arguments is given, as well as a payoff function that assigns real values to every possible valid dialogue. Such game-based argumentation frameworks can be lucidly realized as games in extensive form. We have investigated specialized notions of "maximally-defendable" sets of arguments, and the correlation between the properties of the agents' argument sets and the size of the associated game tree. We have also explored algorithmic issues (simplifications and efficient solutions for our argumentation games). This work was reported on in the following paper:

  Extensive-Form Argumentation Games, Ariel D. Procaccia and Jeffrey S. Rosenschein. The Third European Workshop on Multi-Agent Systems (EUMAS'05), Brussels, Belgium, December 2005, pages 312--322.

• Mechanism Design for Bounded Rational Agents: We continue to investigate certain elements of mechanism design, as it can be applied to boundedly-rational computational agents. PhD student Yoram Bachrach has considered self-interested agents in a network flow domain, and has shown that in this domain it is possible to design a mechanism that is both allocatively-efficient and almost completely budget-balanced. This is done by choosing a mechanism that is not strategy-proof but rather strategy-resistant. Instead of using the well-known Vickrey-Clarke-Groves mechanism (which is only weakly budget-balanced), Yoram proposed a mechanism in which finding a beneficial manipulation is an NP-complete problem, and the payments from the agents to the mechanism may be minimized as much as desired. In this way, the mechanism is virtually strongly budget-balanced: for any epsilon greater than zero, we can find a mechanism that is epsilon-budget-balanced. This work is reported on in the following paper:

  Achieving Allocatively-Efficient and Strongly Budget-Balanced Mechanisms in the Network Flow Domain for Bounded-Rational Agents, Yoram Bachrach and Jeffrey S. Rosenschein. The Seventh International Workshop on Agent-Mediated Electronic Commerce: Designing Mechanisms and Systems (AMEC 2005), at The Fourth International Joint Conference on Autonomous Agents and Multiagent Systems, Utrecht, The Netherlands, July 2005.

• Simulations of Evolutionary Systems: Aviv Zohar has explored the role of "tags" (labels that identify an agent as likely to have certain attributes) in evolutionary systems of simple agents. Previous models of tags for the evolution of cooperation demonstrated their effectiveness both in promoting cooperation and in allowing new strategies to take hold in otherwise incompatible populations. While previous work concentrated on interactions within a group of agents, Aviv expanded the use of tags to interactions between groups. Using a simple model of interactions between boundedly rational players playing the prisoner's dilemma, he considered the effects of various parameters on the level of cooperation achieved and on overall social utility: the number of interactions between groups, the number of game rounds, the number of memory states, the mutation rate of agents, and the size of the tag space. Computer simulations of the model suggest that with the tag mechanism in place, cooperation between different groups of players can become common. This work was reported on in the following paper:

  Using Tags to Evolve Trust and Cooperation Between Groups, Aviv Zohar and Jeffrey S. Rosenschein. The Eighth Biennial Israeli Symposium on the Foundations of Artificial Intelligence, Haifa, Israel, June 2005.

• Supporting Privacy in Decentralized Additive Reputation Systems: This is research carried out with former masters student Zvi Topol and Hebrew University PhD student Elan Pavlov. Previous studies have been suggestive of the fact that reputation ratings may be provided in a strategic manner for reasons of reciprocation and retaliation, and therefore may not properly reflect the trustworthiness of rated parties. It thus appears that supporting privacy of feedback providers could improve the quality of their ratings. We showed that supporting perfect privacy in decentralized reputation systems is impossible, but as an alternative created three probabilistic schemes that support partial privacy. On the basis of these schemes, we constructed three protocols that allow ratings to be privately provided with high probability in decentralized additive reputation systems. This work was reported on in the following paper:

  Supporting Privacy in Decentralized Additive Reputation Systems, Elan Pavlov, Jeffrey S. Rosenschein, and Zvi Topol. The Second International Conference on Trust Management, Oxford, United Kingdom, March 2004, pages 108-119.

• Best-Response Multiagent Learning in Non-Stationary Environments: This is research carried out with masters student Michael Weinberg. Multiagent learning, and specifically reinforcement learning, has opened the way for designing autonomous agents capable of acting in an unknown environment by exploring different possible actions and their consequences. However, a major drawback of reinforcement learning is the assumption that the underlying environment is stationary. A rich environment, inhabited by autonomous, self-motivated agents who act to maximize their own payoffs, cannot be treated as a stationary environment.

  We created a learning algorithm that is provably optimal against a restricted class of non-stationary opponents. We inferred a provably accurate model of the opponent's (presumed) non-stationary strategy, and then designed a best-response policy against that strategy. The algorithm works in a very general framework of n-player general-sum stochastic games, and learns both the game structure and the optimal policy. Our work included both theoretical and experimental results of the algorithm. This work is reported on in the following paper:

  Best-Response Multiagent Learning in Non-Stationary Environments, Michael Weinberg and Jeffrey S. Rosenschein. The Third International Joint Conference on Autonomous Agents and Multiagent Systems, New York, July 2004, pages 506-513.

• The Effects of Parenting on Genetic and Learning Agents: This was work carried out with masters student Michael Berger. We explored the effects of using genetic-learning-parenting hybrid agents in an environment, specifically examining what the best combinations of weights are as a function of the rate of change in the environment.

  For stationary environments, a genetic-parenting combination proved best, with genetics having the majority of weight. For environments with low rates of dynamic change, genetic-learning-parenting hybrids proved best, with learning having the majority of weight and parenting having at least as much weight as genetics. For environments with high rates of dynamic change, pure learning agents proved best. Pure parenting operated extremely poorly in all settings. This work is reported on in the following paper:

  When to Apply the Fifth Commandment: The Effects of Parenting on Genetic and Learning Agents, Michael Berger and Jeffrey S. Rosenschein. The Third International Joint Conference on Autonomous Agents and Multiagent Systems, New York, July 2004, pages 1328-1329 (poster).

  We have also submitted a version of this work for journal publication:

  When to Apply the Fifth Commandment: The Effects of Parenting on Genetic and Learning Agents, Michael Berger and Jeffrey S. Rosenschein. Journal of Autonomous Agents and Multiagent Systems. 2004. Submitted.

• Passive Threats among Agents in State Oriented Domains: Yair Weinberger, a masters student, has been working on a new model of threats among negotiating agents in State Oriented Domains that requires no additional domain-specific assumptions. He explored an agent's "threat of passivity" against another agents --- in other words, threatening to remain inactive (and not exploit existing cooperative opportunities), forcing both agents to satisfy their goals on their own (serially). The possibility of this negotiation threat adds interesting complexity to the four basic SOD encounter types, further subdividing them into additional types of encounter. This work is reported on in the following paper:

  Passive Threats among Agents in State Oriented Domains, Yair Weinberger and Jeffrey S. Rosenschein. The Sixteenth European Conference on Artificial Intelligence, Valencia, Spain, August 2004, pages 89-93.

• Negotiation in State-Oriented Domains with Incomplete Information over Goals: This work was carried out with Shlomit Bergman, an MAS Research Group PhD student, and Elan Pavlov, another Hebrew University PhD student. State Oriented Domains (SODs) are domains where agents are concerned with moving the world from an initial state into one of a set of target states. Previous research on Negotiation in this environment (explored by Rosenschein and Zlotkin), provided an analysis of incentive compatible mechanisms over a variety of two-agent, single-encounter types. Their model included the concept of an agent's worth (the agent's benefit from achieving its goal), using it as a baseline for utility calculation of a negotiation's outcome. One scenario left unexamined, however, was the case where agents know one another's worths, but not one another's goals. This situation creates the possibility of agents' lying to one another solely about goals, to influence the outcome of a negotiation.

  We explored this specific case of known worths and unknown goals in two-agent State Oriented Domains, in a variety of encounter types. Through analysis and examples, it was shown that an agent can benefit from declaring less costly goals, but that there are certain limits to the lies an agent can beneficially declare. We also analyzed the connection of this work to classic game theory results, including general work on incentive compatible mechanisms and the revelation principle. This work is reported on in the following paper:

  Negotiation in State-Oriented Domains with Incomplete Information over Goals, Shlomit Bergman, Elan Pavlov and Jeffrey S. Rosenschein. The Sixteenth European Conference on Artificial Intelligence, Valencia, Spain, August 2004, pages 8-12.

• The Role of Middle-Agents in Electronic Commerce: This research was conducted jointly with the masters student Itai Yarom and former PhD student Claudia Goldman at Hebrew University. We explored questions related to the presence of middlemen in electronic markets. How does the existence of intermediaries affect the efficiency of electronic markets? What is the role played by various strategies that these intermediaries might adopt? What if they can pursue more sophisticated pricing strategies?

  We developed a simulation of an electronic marketplace, specifically a marketplace of information. All roles in these simulations were played by automated agents, which were designed to act as information suppliers, as information consumers, or information "middlemen" (called InfoCenters). Simulations were then run to test how these InfoCenter intermediaries affected the market's efficiency and price behavior. We looked at several different strategies for these middle-agents, comparing how they --- and the market --- did in each case. It turned out that InfoCenters could significantly enhance the efficiency of information marketplaces, and sophisticated InfoCenters did the best of all. This work was reported on in the following paper:

  The Role of Middle-Agents in Electronic Commerce, Itai Yarom, Claudia V. Goldman, and Jeffrey S. Rosenschein. IEEE Intelligent Systems, Volume 18, Number 6, pages 15-21, November/December 2003.

• Searching for an Alternative Plan: This work was carried out with former masters student Ariel Felner. Suppose that an intelligent agent accepts as input a complete plan, i.e., a sequence of states (or operators) that should be followed in order to achieve a goal. For some reason, the given plan cannot be followed by the agent, and thus an alternative plan needs to be found --- but we would like the alternative plan to be as close as possible to the original. To achieve this, we defined a number of distance metrics between paths or plans, and characterized these functions and their respective attributes and advantages. We then developed a general algorithm based on best-first search that helps an agent find the most suitable alternative plan efficiently, and proposed a number of heuristics for the cost function of this best-first search algorithm. We then experimentally showed that our algorithm is efficient in finding an alternative plan. This work was reported on in the following paper:

  Searching for an Alternative Plan, Ariel Felner, Alex Pomeransky, and Jeffrey S. Rosenschein. The Second International Joint Conference on Autonomous Agents and Multiagent Systems, Melbourne, Australia, July 2003, pages 33-40.

  Current masters student Yehudit Kelerman is continuing the work, with Ariel Felner, on searching for alternative plans under a model of non-absolute control.

• The Complexity of Multiagent Systems: This research was carried out with current PhD student Zinovi Rabinovich and former PhD student Claudia Goldman. In this work, we represented multiagent systems using computational models, choosing, specifically, Multi-Prover Interactive Protocols to represent agent systems and the interactions occurring within them. This approach enabled us to analyze complexity issues related to multiagent systems. We focused on the complexity of coordination and studied the possible sources of this complexity, showing that there are complexity bounds that cannot be lowered even when approximation techniques are applied. This work was reported on in the following paper:

  The Complexity of Multiagent Systems: The Price of Silence, Zinovi Rabinovich, Claudia V. Goldman, and Jeffrey S. Rosenschein. The Second International Joint Conference on Autonomous Agents and Multiagent Systems, Melbourne, Australia, July 2003, pages 1102-1103 (poster).

• The Trading Agents Competition Project: Each year, an international contest is held called the "Trading Agents Competition", where automated agents compete with one another in a simulation environment. Entries are created as research projects in various universities, and then are pitted against one another in the competition. TAC Classic, the original environment, is a "travel agent" scenario based on complex procurement on multiple simultaneous auctions. In 2003 two of my students, Nadav Wainshal and Nir Sharony, spent many months creating an automated, learning agent that could compete in TAC Classic. Although other teams were far larger (and typically made use of previous years' experience, while that was our first year in TAC), the automated agent that Nadav and Nir created made an impressive showing against its opponents.

  The final TAC competition was held at the International Joint Conference on Artificial Intelligence, August 2003, in Acapulco, Mexico. Nadav and Nir attended the conference, and while their automated agent placed sixth in the field of nine finalists (and not all original submissions even made it to the finals), the scores of the automated agents were quite clustered. Roughly 4% in the final score separated their agent from the eventual winner, and their agent even beat out another competitor, whose creator founded the TAC competition. With additional refinement, Nadav and Nir entered their agent into the 2004 TAC Classic competition, where it again made an excellent showing.

• Other work: In addition to the research reported on above, there was other work carried out in the context of masters and PhD theses, as well as multiagent systems programming projects (described below).

  Shai Roitman is working on coalitions in congested peer-to-peer networks for his masters thesis --- how self-interested agents in a peer-to-peer network could spontaneously form coalitions to assist in the efficient routing of information. Itai Yarom and Zvi Topol examined decentralized marketplaces and web services (their research, "Decentralized Marketplaces and Web Services: Challenges and Opportunities", was presented as a poster at the Workshop on Agent Mediated Electronic Commerce (AMEC-VI), at the Third International Joint Conference on Autonomous Agents and Multiagent Systems, New York, July 2004). Nir Sharony (mentioned above), created a testbed for running iterated prisoner's dilemma experiments, while Yehudit Kelerman created a full auction server, demonstrating the principles of a variety of auction types. Michael Berger (also mentioned above), programmed a project on "The Analysis of an Algorithmic Attempt to Solve Action-Grounding Noise" in the iterated prisoner's dilemma. Osnat Shapira programmed a simulation of Orca (whale) behavior in capturing schools of fish; her paper detailing the experiments was presented at the EUMAS workshop in December 2005, in Brussels.