Query Incentive Networks

The concurrent growth of on-line communities exhibiting large-scale social structure, and of large decentralized peer-to-peer file-sharing systems, has stimulated new interest in understanding networks of interacting agents as economic systems. Here we formulate a model for query incentive networks, motivated by such systems: users seeking information or services can pose queries, together with incentives for answering them, that are propagated along paths in a network. This type of information-seeking process can be formulated as a game among the nodes in the network, and this game has a natural Nash equilibrium. In such systems, it is a fundamental question to understand how much incentive is needed in order for a node to achieve a reasonable probability of obtaining an answer to a query from the network. We study the size of query incentives as a function both of the rarity of the answer and the structure of the underlying network. This leads to natural questions related to strategic behavior in branching processes. Whereas the classically studied criticality of branching processes is centered around the region where the branching parameter is 1, we show in contrast that strategic interaction in incentive propagation exhibits critical behavior when the branching parameter is 2.

Authors

• Jon M. Kleinberg
• Prabhakar Raghavan

Keywords

• Peer to peer computing
• Information systems
• Joining processes
• Computer science
• Social network services
• Large-scale systems
• Nash equilibrium
• Routing
• Internet
• Power system modeling
• Strategic Behavior
• Network Path
• Strategic Interaction
• Branching Process
• Social Networking Sites
• Reachable
• Tree Model
• Constant Factor
• Random Networks
• Subtree
• Sequence Of Values
• Positive Probability
• Breadth-first Search
• Constant Probability
• Mean Value Theorem
• Probability Of Extinction
• Negligible Cost
• Behavior Of Nodes
• Rational Coefficients
• Existence Of Nash Equilibrium