Cooperation among self-interested agents

In open environments there is no central control over agent behaviors. On the contrary, agents in such systems can be assumed to be primarily driven by self interests. In a number of situations, myopic decision making can lead to both unsatisfactory performance by individual agents and undesirable effects at the overall system level. Our goal is to understand domains and environments where self-interested agents may have incentives to cooperate. More specifically, we want to identify and design environmental characteristics and agent behavioral strategies such that the best self-interested behavior is to cooperate with other agents. In such environments, both individual and system-level performance is optimized when agents cooperate. To identify domains with these desirable characteristics, we have to establish mechanisms that can cooperate effectively and is resistant to exploitation. Under the assumption that agents remain in the system for significant time periods, or that the agent composition changes only slowly, we have been studying a probabilistic reciprocity-based strategy for promoting and sustaining cooperation in agent groups. This strategy improves both individual and group performance in the long run. We have also analyzed the effectiveness of this strategy when agents have incomplete information and can over or underestimate the amount of help received. While these initial studies help us understand some basic properties of reciprocity-based agent behaviors, we need to build the underlying theory and investigate other critical aspects of such strategies before practical multiagent systems can be built and deployed effectively in open environments.

Publications from this project

Mahendra Sekaran and Sandip Sen, “To help or not to help,” in the Proc. of the Seventeenth Annual Conference of the Cognitive Science Society (pages 736-741), Pittsburgh, Pennsylvania, July 1995.
Sandip Sen, “Reciprocity: a foundational principle for promoting cooperative behavior among self-interested agents” , in Proc. of the Second International Conference on Multiagent Systems, pages 322–329, AAAI Press, Menlo Park, CA, 1996.
A. Biswas and S. Sen, “Reciprocating with Learned Models,” in the Working notes of the AAAI-98 Spring Symposium on Satisficing Models, pages 15-18. (Symposium Notes available as AAAI Technical Report SS-98-05).
Sandip Sen and Anish Biswas, “Effects of misconception on reciprocative agents,” in Proceedings of the Second International Conference on Autonomous Agents, pages 430–435, ACM Press, New York, NY, 1998.
Anish Biswas and Sandip Sen, “Influence of perspectives on help-giving behaviors,” in Proceedings of the Third International Conference on Autonomous Agents (pages 352–353), ACM Press, New York, NY, 1999. (Poster Paper)
Sandip Sen, Anish Biswas, and Sandip Debnath,“Believing others: Pros and Cons,” in Proceedings of the Fourth International Conference on Multiagent Systems, (pages 279–286) held between June 7–12, 2000 in Boston, MA.
Anish Biswas, Sandip Sen and Sandip Debnath, “Limiting Deception in Groups of Social Agents,” Applied Artificial Intelligence Journal, Volume 14, Number 8, pages 785–797 (Special issue on “Deception, Fraud and Trust in Agent Societies”).

Multiagent learning

Learning and adaptation capabilities enable agent to respond to open, dynamic environments by exploiting new opportunities and avoiding unforeseen pitfalls. When multiple, tightly-coupled agents learn concurrently, assumptions underlying classical machine learning techniques are violated. So, multiagent learning is a challenging and productive problem for both multiagent and learning researchers. We have worked on a variety of multiagent learning techniques including multiagent reinforcement learning (JETAI’98, ICMAS’2000), multiagent case-based learning (ICMAS’96, IJHCS’98), Bayesian network based learning (ML’2000, AAI (to appear)), learning to predict behaviors (AGENTS’99), etc.

Publications from this project

Bikramjit Banerjee, Sandip Debnath and Sandip Sen, “Combining Multiple Perspectives,” in the Proceedings of the International Conference on Machine Learning’2000 (pages 33-40), held between June 29 and July 2, 2000 in Stanford University, CA.
Bikramjit Banerjee, Rajatish Mukherjee, and Sandip Sen, “Learning Mutual Trust,” in the Working Notes of AGENTS-00 Workshop on Deception, Fraud and Trust in Agent Societies, pages 9-14, Spain, Barcelona, 2000.
Manisha Mundhe and Sandip Sen, “Evaluating concurrent reinforcement learners,” in Proceedings of the Fourth International Conference on Multiagent Systems (pages 421–422), IEEE Press, Los Alamitos, CA, 2000. (Poster paper)
Anish Biswas and Sandip Sen, “Learning to model behaviors from boolean responses,” in Proceedings of the Third International Conference on Autonomous Agents (pages 396–397), ACM Press, New York, NY, 1999. (Poster Paper)
Sandip Sen & Mahendra Sekaran, “Individual learning of coordination knowledge,” Journal of Experimental & Theoretical Artificial Intelligence , 10, pages 333-356, 1998 (special issue on Learning in Distributed Artificial Intelligence Systems).
Thomas Haynes and Sandip Sen, “Learning Cases to Compliment Rules for Conflict Resolution in Multiagent Systems,” International Journal of Human-Computer Studies, vol. 48, no. 1, pages 31–49,(special issue on Evolution and Learning in Multiagent Systems). A slightly different version can be accessed online from here.
Sandip Sen, Mahendra Sekaran, and John Hale, “Learning to coordinate without sharing information,” in Proc. National Conference on Artificial Intelligence, (pages 426-431) Seattle, Washington, July 1994.

Intelligent Agents for assisting users in Electronic Commerce Transactions

We are working concurrently on a number of related agent systems with the common motivation of empowering the user with choices and recommendations about products and services in electronic commerce environments. We are also interested in developing negotiation mechanisms by which self-interested parties can effectively negotiate settlements.Shopping on the Internet has become a convenient way of purchasing commodities of choice. With the boom of e-commerce, online sellers are flooding the market with their products. We believe that assisting users to reformulate queries to maximize the quality of retrieved information will be a key enhancement of agent technology to information retrieval. To provide this functionality, the use of a rich domain ontology will be necessary. We have identified the types of query reformulation that we believe will be particularly useful and the kind of information to be represented in domain ontologies to enable this functionality. We are comparing representative domains to identify domain characteristics that determine the relative difficulty of providing effective query reformulations.Personal agents have been developed that assist user with information processing needs by generating, filtering, collecting, or transforming information. On the other hand internet stores are providing services customized by the needs and interests of individual customers. Such services can be viewed as “seller’s agents” whose goal is to push merchandise and/or services on to the users. This leads us to believe that there is a growing need for deploying “buyer’s agents” whose goal is to best serve the user’s interests. We propose several key functionalities of such buyer’s agents: informing consumers of complex interactions between specified preferences and prevailing market conditions, providing differential analysis for decision support, learning and updating user preferences to provide effective recommendation.

Publications from this project

S. Debnath, P. S. Dutta and S. Sen, “A Shopper`s Assistant,” to appear in the Proceedings of the Fifth International Conference on Autonomous Agents to be held between May 28–June 1, 2001 in Montreal, Canada. (Poster paper)S. Sen, P.S. Dutta, R. Mukherjee, “Agents that represent Buyer’s interest in E-commerce,” in the Working Notes of the AAAI-2000 Workshop on Knowledge Based Electronic Markets.R. Mukherjee, P.S. Dutta, S. Sen, “Analysis of domain-specific ontologies for agent-oriented information retrieval,” in the Working Notes of the AAAI-2000 Workshop on Agent-Oriented Information Systems.R. Mukherjee, P. S. Dutta, G. Jonsdottir, and S. Sen, “Movies2Go – An Online Voting Based Movie Recommender System,” to appear in the Proceedings of the Fifth International Conference on Autonomous Agents to be held between May 28–June 1, 2001 in Montreal, Canada. (Poster paper)S. Sen and A. Biswas and S. Ghosh, “Adaptive Choice of Information Sources,” in “Intelligent Information Agents,” Matthias Klusch (Editor), pages 258-278, Springer-Verlag: New York, 1999.

Negotiation approaches

We are interested in developing negotiation frameworks using which self-interested agents can improve their payoffs in non-cooperative environments. We are studying a number of different approaches under varying assumptions about interaction history, knowledge requirements, and agent capabilities.

Improving efficiencies of envy-free divisions: Researchers have developed procedures for dividing up goods between self-interested parties such that the allocation is envy-free, i.e., when every party (agent) believes that its share is not less than anyone else’s share. These procedures, however, are not efficient (in the sense of pareto optimality) in general. Envy-free procedures allow agents to ignore the utility metrics of other agents if they are satisfied with a fare share of the goods being divided. We are interested in studying augmentations of these procedures in which agents use models of the decision strategies or utility metrics of other agents to try to obtain more than their fare share without sacrificing the envy-free guarantee.
Bayes net based agent models: Modeling using Bayesian networks Relationship between agents in a society can be represented using a Bayesian network where the topology of the network together with the conditional and prior probabilities represent an agent’s view of the influence of different factors on outcomes of agent interactions. Such a Bayes net model can also aid an agent in its negotiation with other agents. We are particularly interested in procedures to be used by an agent to create a favorable negotiation context in which negotiation takes place between two agents. We provide a decision mechanism by which an agent can take actions to create a favorable negotiation context in addition to choosing a negotiation offer that is likely to be accepted by the other agent. We are also interested in decision procedures that elicit useful information about other agents that flesh out the Bayes net model. We have developed a maximin entropy decision procedure that allows the modeling agent to choose actions to produce guaranteed minimal improvement of the model accuracy.
Risk evaluation in partner selection: We consider situations where a rational agent has to choose one of several contenders to enter into a partnership. We assume that the agent has a model of the likelihood of different outcomes and corresponding utilities for each such partnership. Given a fixed, finite number of interactions, the problem is to choose a particular partner to interact with where the goal is to maximize the sum of utilities received from all the interactions. We develop a multinomial distribution based mechanism for partner selection and contrast its performance with other well-known approaches which provide exact solution to this problem for infinite interactions.
Contracting in Supply Chains: We assume an open supply chain environment where manufacturers award sub-contracts to bidding suppliers using an auction scheme. Task scheduling decisions for a supplier should be targeted towards creating a schedule that is flexible in accommodating short-notice tasks or schedule adjustments due to unforeseen events. We believe that task scheduling heuristics will be crucial in determining the competitiveness of a supplier in the marketplace. This is particularly true when a supplier can provide scarce resources or services that other suppliers cannot provide and hence can significantly increase its contract prices and, therefore, profitability.
Learning in repeated single-stage games: Multiagent learning literature has looked at iterated two-player games to develop mechanisms that allow agents to learn to converge on Nash Equilibrium strategy profiles. Often, in general sum games, a higher payoff can be obtained by both players if one chooses not to respond optimally to the other player. We have found that in certain situations, modeling agents, who select actions proportional to expected utility based on observed probability distributions of opponent actions, can perform better than those that converge to Nash Equilibrium. We also experiment with an interesting action revelation strategy that can give the revealer better payoff on convergence than a non-revealing approach.

Publications from this project

B. Banerjee and S. Sen, “Selecting partners,” in “Game theory and decision theory in agent-based systems”, Simon Parsons, Piotr Gmytrasiewicz, & Michael Wooldridge (Editors), Kluwer, (to appear).
Sandip Sen and Anish Biswas, “More than envy-free” in the Working Papers of the AAAI-99 Workshop on Negotiation: Settling Conflicts and Identifying Opportunities, pages 44-49. (Workshop Notes available as AAAI Technical Report WS-99-12).
Bikramjit Banerjee, Sandip Debnath and Sandip Sen, “Using Bayesian Network to aid Negotiations among Agents” , in the Working Notes of the AAAI-99 Workshop on Negotiation: Settling Conflicts and Identifying Opportunities (also available as AAAI Technical Report WS-99-12), pages 44-49, 1999.
Bikramjit Banerjee, Anish Biswas, Manisha Mundhe, Sandip Debnath, and Sandip Sen, “Using Bayesian Networks to Model Agent Relationships,” Applied Artificial Intelligence Journal, Volume 14, Number 9, pages 867–880, 2000 (Special issue on “Deception, Fraud and Trust in Agent Societies”).
Rajatish Mukherjee, Bikramjit Banerjee, and Sandip Sen, “Learning Mutual Trust,” in Fraud, Deception, and Trust in Agent Societies, Rino Falcone, Munindar Singh, & Yao-Hua Tan (Editors), Springer-Verlag, (invited submission).

Evolutionary Design of agent societies

As an alternative to hand-crafting agent designs, evolutionary techniques provide a useful alternative to designing agent systems or agent behaviors.Cooperative Coevolution: We use one or more populations of agents to evolve effectively coordinated groups using novel techniques like shared memory based cooperative coevolution and strongly typed genetic programming (IEEE-EC’98, ICGA’95, GP’97).Competitive Coevolution: We have used multiple populations of competing agents to simulate “escalating arms races” that leads to robust agent behaviors which can compete against a wide variety of opponents (book chapter in ADAPTION AND LEARNING IN MULTIAGENT SYSTEMS’96).Adaptive Systems approach to Social Dilemmas: We have used a novel genetic algorithm based framework to develop agent societies that can avoid social dilemmas like Braess Paradox and the Tragedy of the Commons (ICGA’97, ICMAS’2000, GECCO’2000).

Publications from this project

Sandip Sen and Partha Sarathi Dutta,“Searching for optimal coalition structures,” in Proceedings of the Fourth International Conference on Multiagent Systems (pages 286–292), held between July 7–12, 2000 in Boston, MA.
Manisha Mundhe and Sandip Sen, “Evolving agent societies that avoid social dilemmas,” in Proceedings of GECCO-2000 (pages 809–816), held between July 8–12, 2000 in Las Vegas, Nevada.
Narendra Puppala, Sandip Sen, and Maria Gordin, “Shared Memory Based Cooperative Coevolution,” in Proc. of the International Conference on Evolutionary Computation’98, IEEE Press, 1998.
Maria Gordin, Narendra Puppala and Sandip Sen, “Evolving Cooperative Groups: Preliminary Results” in the Working Papers of the AAAI-97 Workshop on Multiagent Learning, pages 31-35. (Workshop Notes available as AAAI Technical Report WS-97-03).
Thomas Haynes & Sandip Sen, “Co-adaptation in a team,” to appear in International Journal of Computation Intelligence and Organizations, vol 1, no. 4.
Neeraj Arora and Sandip Sen, “Resolving Social Dilemmas Using Genetic Algorithms:Initial Results”, in the Proc. of the Seventh International Conference on Genetic Algorithms, pages 689-695, Lansing, MI, 1997.
Thomas Haynes and Sandip Sen, “Crossover Operators for Evolving a Team” in the Proceedings of Genetic Programming 1997: the Second Annual Conference, pages 162–167, San Francisco, CA, 1997.
Thomas Haynes, Sandip Sen, Dale Schoenefeld, and Roger Wainwright, “Evolving a Team”, in the AAAI Fall Symposium on Genetic Programming, in Cambridge, MA, November, 1995.

Sensor Networks

A wireless ad hoc sensor network consists of a number of sensors spread across a geographical area. Each sensor has wireless communication capability and some level of intelligence for signal processing and networking of the data. Some examples of wireless ad hoc sensor networks are the following:

Military sensor networks to detect and gain as much information as possible about enemy movements, explosions, and other phenomena of interest.
Wireless traffic sensor networks to monitor vehicle traffic on highways or in congested parts of a city.
Wireless surveillance sensor networks for providing security in shopping malls, parking garages, and other facilities.
Wireless parking lot sensor networks to determine which spots are occupied and which are free.

Our Research

Comparing Reputation Schemes for Detecting Malicious Nodes in Sensor Networks

Remotely deployed sensor networks are vulnerable to both physical and electronical security breaches. The sensor nodes, once compromised, can send erroneous data to the base station, thereby possibly compromising network effectiveness. We assume the sensor nodes are organized in a hierarchy and use offline neural network based learning technique to predict the sensed data at any node given the data of its siblings. This allows us to detect malicious nodes even when the siblings are not sensing data from the same distribution. The speed of detection of compromised nodes, however, critically depends on the mechanism used to update the reputation of the sensor nodes over time. We compare and contrast the relative strengths of a statistically grounded scheme and a reinforcement learning based scheme both for their robustness to noise and responsiveness to change in sensor behavior. We first extend an existing mechanism to improve detection capability for smaller errors. Next we analyze the influence of different discount factors, including unweighted, exponential, and linear discounts, to study the tradeoff between responsiveness and robustness. We both develop a theoretical analysis to understand the tradeoff and perform experimental verification of our predictions by varying the number of compromised nodes, network size, and patterns in sensed data.

Robust Trust Mechanisms for Monitoring Aggregator Nodes in Sensor Networks

Sensor nodes are often deployed in large numbers to monitor extended sensor fields. In such scenarios data aggregation plays a crucial role on summarizing data forwarded to base stations in sensor networks. As sensor networks are commonly deployed in open and unattended areas, they are vulnerable to physical tampering as well as remote attacks. Existing security techniques focus primarily on methods used by an aggregator node to monitor and detect compromised behavior by nodes that report data to it. We propose a novel mechanism, combining techniques from statistics and artificial intelligence, by which nodes reporting to an aggregator node can monitor whether the latter is reporting incorrect aggregated values. In our framework, nodes are arranged in a hierarchy. We develop a reputation management scheme in which each child node keeps a reputation value of its parent. For each data reporting event, a node is privy only to the data value it reported and the aggregated value forwarded by its parent node. Each node then calculates the probability of the parent reporting correctly aggregated values over an epoch of events by adapting a statistical hypothesis testing scheme. This probability is used to incrementally update the trustworthiness of the parent node using a learning scheme. When the trustworthiness of a node falls below a threshold it can no longer be trusted with the aggregation task and should be reallocated or eliminated from the network. We evaluate the robustness of our adaptation of a couple of statistical hypothesis testing schemes and analyze their applicability for different types of malicious behaviors by compromised sensor nodes.

References

Sensor Networks: Survey

M. Tubaishat and S. Madria., Sensor Networks: an Overview., IEEE Potentials, 22, 2, 20-23, April 2003
A. Bharathidasan and V.A.S. Ponduru., Sensor Networks: an Overview., UC Davis
I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci., A Survey on Sensor Networks., IEEE Communication Magazine, August 2002
S. Tilak, N.B. Abu-ghazaleh, and W. Heinzelman., A taxonomy of Wireless Micro-Sensor Network Models., ACM SIGMOBILE Mobile Computing and Communications Review, 6, 2, 28-36, April 2002
M.A.M. Vieira, D.C. da Silva Jr., C.N. Coelho Jr., and J.M. da Mata., Survey on Wireless Sensor Network Devices., Emerging Technologies and Factory Automation(ETFA03), September 2003
John Serri, Reference Architecture and Management Model for Ad hoc Sensor Networks, October 2004

Security in Sensor Networks

L. Zhou and Z.J. Haas., Securing Ad Hoc Networks., IEEE Network Special Issue on Network Security., 13, 6, 24-30, November 1999
A. Perrig, R. Szewczyk, V. Wen, D. Culler, and J.D. Tygar., SPINS: Security Protocols for Sensor Networks., ACM Mobile Computing and Networking, July 2001
A.D. Wood, J.A. Stankovic, and S.H. Son, JAM: A Jammed-Area Mapping Service for Sensor Networks, In The 24th IEEE International Real-Time Systems Symposium (RTSS), December 2003
W. Du, J. Deng, Y.S. Han, and P.K. Varshney, A Pairwise Key Pre-distribution Scheme for Wireless Sensor Networks, CCS’03, October 2003
C. Yin, S. Huang, P. Su, and C. Gao., Secure Routing for Large-scale Wireless Sensor Networks., In Proc. of International Conference on Communication Technology (ICCT’03), April 2003
J. Deng, R. Han, and S. Mishra., A Performance Evaluation of Intrusion-Tolerant Routing in Wireless Sensor Networks., 2nd International Workshop on Information Processing in Sensor Networks (IPSN 03), April 2003
A.D. Wood and J.A. Stankovic, Denial of Service in Sensor Networks, IEEE Computer, 35, 54-62, September 2002
[8] C. Karlof and D. Wagner., Secure Routing in Wireless Sensor Networks: Attacks and Countermeasures., Sensor Network Protocols and Applications (SNPA’03), May 2003
H. Chan, A. Perrig, and D. Song., Random Key Predistribution Schemes for Sensor Networks., IEEE Symposium on Security and Privacy (SP), May 2003
G. Jolly, M.C. Kuscu, P. Kokate, and M. Younis., A Low-Energy Key Management Protocol for Wireless Sensor Networks., IEEE Symposium on Computers and Communications(ISCC’03)., June 2003
P. Ganesan, R. Venugopalan, P. Peddabachagari, A. Dean, F. Mueller, and M. Sichitiu., Analyzing and Modeling Encryption Overhead for Sensor Network Nodes., WSNA’03, September 2003
Q. Huang, J. Cukier, H. Kobayashi, B. Liu, and J. Zhang., Fast Authenticated Key Establishment Protocols for Self-Organizing Sensor Networks., WSNA’03, September 2003
Y.C. Hu, A. Perrig, and D.B. Johnson., Rushing Attacks and Defense in Wireless Ad Hoc Network Routing Protocols., WiSe’03, September 2003
M. Bohge and W. Trappe., An Authentication Framework for Hierarchical Ad Hoc Sensor Networks., WiSe’03, September 2003

An automated, intelligent meeting scheduling system

Intelligent agents are being used widely and effectively to assist users in their information processing chores. We have developed a distributed negotiation mechanism by which automated scheduling agents can schedule meetings on behalf of their associated users. The meeting scheduler is implemented on a network of workstations. By using a simple graphical user interface, users can request meetings to be scheduled. These requests are processed by distributed agents communicating via e-mail. Users can also specify their preference/constraints on different meeting and calendar attributes. The scheduling agents intelligently adapts to user preferences and priorities of associated users with regards to meeting lengths, topics, attendees, days of the week, hours of the day, etc. The system is designed to be adaptive to environmental demands as well as to user preferences.

This project has been supported partially by a Research Initiation Award from the National Science Foundation.

Implemented Systems

Market-aware agents that help consumers choose products/services

Personal agents have been developed that assist user with information processing needs by generating, filtering, collecting, or transforming information. On the other hand internet stores are providing services customized by the needs and interests of individual customers. Such services can be viewed as “seller’s agents” whose goal is to push merchandise and/or services on to the users. This leads us to believe that there is a growing need for deploying “buyer’s agents” whose goal is to best serve the user’s interests. In particular, such agents should alert the user of the complex interactions between specified preferences and prevailing market conditions. The availability of such information makes the user a more informed customer. We discuss the design and prototype implementation of a buyer’s agent in an apartment locator application.

Publications from this project

Karina Hernandez and Sandip Sen ,“A Buyer’s Agent,” in Proceedings of the Fourth International Conference on Autonomous Agents (pages 156–162), held in Barcelona, Spain between June 2-8, 2000.
S. Sen, P.S. Dutta, R. Mukherjee, “Agents that represent Buyer’s interest in E-commerce,” in the Working Notes of the AAAI-2000 Workshop on Knowledge Based Electronic Markets.
R. Mukherjee, P.S. Dutta, S. Sen, “Analysis of domain-specific ontologies for agent-oriented information retrieval,” in the Working Notes of the AAAI-2000 Workshop on Agent-Oriented Information Systems.

LawBOT: an assistant for legal research

We are developing an Internet based agent designed to assist legal researchers in retrieving laws and case reports electronically warehoused at a diverse set of databases maintained by local, state, and federal governments. LawBOT is implemented as a collection of agents which are employed according to users’ preferences to collect, filter, organize and recommend relevant case histories, state statutes or supreme court cases. Our goal is to create a system that can be effectively used not only by lawyers but also by the lay person to retrieve legal documents relevant to the issue that the user wants to research.

Publications from this project

Sandip Debnath, Sandip Sen, and Brent Blackstock, “LawBOT: an assistant for legal research,” IEEE Internet Computing, Volume 4, Number 6, pages 32–37, November/December, 2000.