Finding red balloons with split contracts

Abstract

The present work deals with the problem of information acquisition in a strategic networked environment. To study this problem, Kleinberg and Raghavan (FOCS 2005) introduced the model of query incentive networks, where the root of a binomial branching process wishes to retrieve an information -- known by each node independently with probability 1/n -- by investing as little as possible. The authors considered fixed-payment contracts in which every node strategically chooses an amount to offer its children paid upon information retrieval to convince them to seek the information in their subtrees. Kleinberg and Raghavan discovered that the investment needed at the root exhibits an unexpected threshold behavior that depends on the branching parameter b. For b>2, the investment is linear in the expected distance to the closest information (logarithmic in n, the rarity of the information), while, for 1<b<2, it becomes exponential in the same distance (i.e., polynomial in n). Arcaute et al. (EC 2007) later observed the same threshold behavior for arbitrary Galton-Watson branching processes.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 36 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.