On threshold behavior in query incentive networks

ABSTRACT

Motivated by the role of incentives in large-scale information systems, Kleinberg and Raghavan (FOCS 2005) studied strategic games in decentralized information networks. Given a branching process that specifies the network, the rarity of answers to a specific question, and a desired probability of success, how much reward does the root node need to offer so that it receives an answer with this probability, when all of the nodes are playing strategically? For a specific family of branching processes and a constant failure probability, they showed that the reward function exhibited a threshold behavior that depends on the branching parameter b.

In this paper we study two factors that can contribute to this transition behavior, namely, the branching process itself and the failure probability. On one hand we show that the threshold behavior is robust with respect to the branching process: for all branching processes and any constant failure probability, if b > 2 then the required reward is linear in the expected depth of the search tree, and if b < 2 then the required reward is exponential in that depth. On the other hand we show that the threshold behavior is fragile with respect to the failure probability σ: if σ is inversely polynomial in the rarity of the answer, then all branching processes require rewards exponential in the depth of the search tree.

REFERENCES

• 1: Z. Abrams, R. McGrew, and S. Plotkin. Keeping peers honest in eigentrust. In Proc. Workshop on the Economics of Peer-to-Peer Systems, 2004.
• 2: K. B. Athreya and P. E. Ney. Branching Processes. Dover Publications, Inc., New York, 2004.
• 3: J. J. Brown and P. H. Reingen. Social ties and word-of-mouth referral behavior. J. Consumer Research, 14:350--362, 1987.
• 4: Pedro Domingos , Matt Richardson, Mining the network value of customers, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.57-66, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502525]
• 5: D. Dutta, A. Goel, R. Govindan, and H. Zhang. The design of a distributed rating scheme for peer-to-peer systems. In Proc. Workshop on the Economics of Peer-to-Peer Systems, 2003.
• 6: R. Guha , Ravi Kumar , Prabhakar Raghavan , Andrew Tomkins, Propagation of trust and distrust, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988727]
• 7: Z. Gyöngyi, H. Garcia-Molina, and J. Pedersen. Combating web spam with trustrank. In Proc. Conference on Very Large Data Bases (VLDB), pages 576--587, 2004.
• 8: Sepandar D. Kamvar , Mario T. Schlosser , Hector Garcia-Molina, The Eigentrust algorithm for reputation management in P2P networks, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775242]
• 9: Henry Kautz , Bart Selman , Mehul Shah, Referral Web: combining social networks and collaborative filtering, Communications of the ACM, v.40 n.3, p.63-65, March 1997 [doi>10.1145/245108.245123]
• 10: David Kempe , Jon Kleinberg , Éva Tardos, Maximizing the spread of influence through a social network, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956769]
• 11: D. Kempe, J. Kleinberg, and E. Tardos. Influential nodes in a diffusion model for social networks. In Proc. Colloquium on Automata, Languages and Programming (ICALP), pages 1127--1138, 2005.
• 12: Jon Kleinberg , Prabhakar Raghavan, Query Incentive Networks, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.132-141, October 23-25, 2005 [doi>10.1109/SFCS.2005.63]
• 13: Jure Leskovec , Lada A. Adamic , Bernardo A. Huberman, The dynamics of viral marketing, Proceedings of the 7th ACM conference on Electronic commerce, p.228-237, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134732]
• 14: M. Richardson, R. Agrawal, and P. Domingos. Trust management for the semantic web. In Proc. 2nd International Semantic Web Conference, pages 351--368, 2003.
• 15: Matthew Richardson , Pedro Domingos, Mining knowledge-sharing sites for viral marketing, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775057]
• 16: Bin Yu , Munindar P. Singh, A Social Mechanism of Reputation Management in Electronic Communities, Proceedings of the 4th International Workshop on Cooperative Information Agents IV, The Future of Information Agents in Cyberspace, p.154-165, July 07-09, 2000
• 17: Bin Yu , Munindar P. Singh, Searching social networks, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860587]
• 18: Jun Zhang , Marshall Van Alstyne, SWIM: fostering social network based information search, CHI '04 extended abstracts on Human factors in computing systems, April 24-29, 2004, Vienna, Austria [doi>10.1145/985921.986144]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

General Terms:
Economics, Theory

Keywords:
branching processes, query incentive networks, threshold phenomena