  In this paper, we study incentive mechanisms for retrieving information from
networked agents. Following the model in [Kleinberg and Raghavan 2005], the
agents are represented as nodes in an infinite tree, which is generated by a
random branching process. A query is issued by the root, and each node
possesses an answer with an independent probability $p=1/n$. Further, each node
in the tree acts strategically to maximize its own payoff. In order to
encourage the agents to participate in the information acquisition process, an
incentive mechanism is needed to reward agents who provide the information as
well as agents who help to facilitate such acquisition.
  We focus on designing efficient sybil-proof incentive mechanisms, i.e., which
are robust to fake identity attacks. %We consider incentive mechanisms which
are sybil-proof, i.e., robust to fake identity attacks. We propose a family of
mechanisms, called the direct referral (DR) mechanisms, which allocate most
reward to the information holder as well as its direct parent (or direct
referral). We show that, when designed properly, the direct referral mechanism
is sybil-proof and efficient. In particular, we show that we may achieve an
expected cost of $O(h^2)$ for propagating the query down $h$ levels for any
branching factor $b>1$. This result exponentially improves on previous work
when requiring to find an answer with high probability. When the underlying
network is a deterministic chain, our mechanism is optimal under some mild
assumptions. In addition, due to its simple reward structure, the DR mechanism
might have good chance to be adopted in practice.
