A new paper (FOCS 2005)
http://research.yahoo.com/publication/YRL-2005-051.pdf
by Jon Kleinberg and Prabhakar Raghavan
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 the 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 extracting 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.
This archive was generated by hypermail 2b30 : Tue Jun 09 2009 - 05:00:11 EDT