Efficiently determining the appropriate mix of personal interaction and reputation information in partner choice

ABSTRACT

Many multi-agent settings require that agents identify appropriate partners or teammates with whom to work on tasks. When selecting potential partners, agents may benefit from obtaining information about alternative possibilities through gossip (i.e., by consulting others) or using a reputation system (a centralized repository of information about past behavior). This paper defines a statistical model, the "Information-Acquisition Source Utility model" (IASU) by which agents operating in an uncertain world can determine the amount of information to collect about potential partners before choosing one and which information sources they should consult (gossip, reputation system, or additional personal interaction with the agent). The IASU model explicitly represents the cost of information, which may vary by information source. To maximize the expected gain from a choice, it estimates the utility of choosing a partner by iteratively estimating the benefit of additional information. The paper reports empirical studies that compare the effectiveness of the IASU model with a baseline in which only prior experience with a potential partner is used as the basis of the decision and with a model that determines in advance both the amount of information and its allocation among the different sources. Two different application domains are used in these empirical studies, the Surrogate Venture Game model, which concerns choosing an optimal partner for a business venture, and a restaurant domain. The results of the experiments show that the use of the model significantly increases the agents' overall utility.

REFERENCES

• 1: Milton Abramowitz, Handbook of Mathematical Functions, With Formulas, Graphs, and Mathematical Tables,, Dover Publications, Incorporated, 1974
• 2: Rina Azoulay-Schwartz , Sarit Kraus, Acquiring an Optimal Amount of Information for Choosing from Alternatives, Proceedings of the 6th International Workshop on Cooperative Information Agents VI, p.123-137, September 18-20, 2002
• 3: V. Cicirello and S. Smith. The max k-armed bandit: A new model for exploration applied to search heuristic selection. In AAAI-05, July 2005. Best Paper Award.
• 4: Richard Dearden , Nir Friedman , Stuart Russell, Bayesian Q-learning, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.761-768, July 1998, Madison, Wisconsin, United States
• 5: Karen K. Fullam , K. Suzanne Barber, Dynamically learning sources of trust information: experience vs. reputation, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329325]
• 6: Karen K. Fullam , K. Suzanne Barber, Learning trust strategies in reputation exchange networks, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160857]
• 7: Joshua Grass , Shlomo Zilberstein, A Value-Driven System for Autonomous Information Gathering, Journal of Intelligent Information Systems, v.14 n.1, p.5-27, March 2000 [doi>10.1023/A:1008718418982]
• 8: Rohit Gupta , Arun K. Somani, Reputation Management Framework and Its Use as Currency in Large-Scale Peer-to-Peer Networks, Proceedings of the Fourth International Conference on Peer-to-Peer Computing, p.124-132, August 25-27, 2004 [doi>10.1109/P2P.2004.44]
• 9: Philip Hendrix , Barbara J. Grosz, Reputation in the joint venture game, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329342]
• 10: Philip Hendrix , Barbara J. Grosz, Reputation in the joint venture game, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329342]
• 11: T. D. Huynh, N. Jennings, and N. Shadbolt. Fire: An integrated trust and reputation model for open multi-agent systems. Proceeding of 16th European Conference on Artificial Intelligence, pages 18--22, 2004.
• 12: Radford M. Neal , Geoffrey E. Hinton, A view of the EM algorithm that justifies incremental, sparse, and other variants, Learning in graphical models, MIT Press, Cambridge, MA, 1999
• 13: J. Nelder and R. Mead. A simplex method for function minimization. The Computer Journal, 7:308--313, 1964.
• 14: Josep M. Pujol , Ramon Sangüesa , Jordi Delgado, Extracting reputation in multi agent systems by means of social network topology, Proceedings of the first international joint conference on Autonomous agents and multiagent systems: part 1, July 15-19, 2002, Bologna, Italy [doi>10.1145/544741.544853]
• 15: S. D. Ramchurn, C. Sierra, L. Godo, and N. Jennings. A computational trust model for multi-agent interactions based on confidence and reputation. Proceedings of 6th International Workshop of Deception, Fraud and Trust in Agent Societies, pages 69--75, 2003.
• 16: Shulamit Reches , Shavit Talman , Sarit Kraus, A statistical decision-making model for choosing among multiple alternatives, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329374]
• 17: B. Selman, H. A. Kautz, and B. Cohen. Local search strategies for satisfiability testing. In the 2nd DIMACS Challenge on Cliques, Coloring and Satis., 1993.
• 18: M. J. Streeter and S. Smith. An asymptotically optimal algorithm for the max k-armed bandit problem. In AAAI-06, July 2006.
• 19: S. Talman, R. Toester, and S. Kraus. Choosing between heuristics and strategies: an enhanced model for decision-making. In Proceedings of the International Joint Conference of Artificial Intelligence, pages 324--330, 2005.
• 20: W. T. Luke Teacy , Jigar Patel , Nicholas R. Jennings , Michael Luck, Coping with inaccurate reputation sources: experimental analysis of a probabilistic trust model, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082624]
• 21: M. M. Vanzin and K. S. Barber. Decentralized partner finding in multi-agent systems. In Coordination of Large-Scale Multiagent Systems, pages 75--98. Springer, March 2006.
• 22: G. Zacharia and P. Maes. Trust through reputation mechansims. Applied Artificial Intelligence, 14:881--907, 2000.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence