Find 10 Red Balloons, Collect $40,000

How to Build a Human-Powered Search Engine

Finding Red Balloons

The 2009 DARPA Network Challenge was a “prize competition for exploring the roles the internet and social networking play in the real-time communications”. Ten red weather balloons were to be placed at random locations around the United States. The first team to report the location of the balloons would claim the $40,000 prize.

The team from MIT MediaLab chose an interesting strategy: they offered a cash reward to any person that reported the location of a balloon, but they also offered ½ of that amount to the person that invited the balloon-finder to the team, and ½ of that amount to the person that invited the inviter, and so on. This gave each participant an incentive to recruit teammates, and it worked — the MediaLab team grew to over 5,000 members (more than 4x the size of the next largest team).

On December 5, 2009, DARPA announced that the challenge was live. They planned on running the competition for up to a week. The MediaLab team located all of the balloons and won the challenge in less than 9 hours.

Query Incentive Networks

The MediaLab team’s strategy was based on a paper by Jon Kleinberg and Prabhakar Raghavan titled “Query Incentive Networks”. In it they describe the following network:

“…users seeking information or services can pose queries, together with incentives for answering them, that are propagated along paths in a network.”

A person could post a question along with a cash reward for whoever helps find the answer. Others users could either answer the question or pass along the question to their friends, who would then either answer the question or pass it on, and so on. When the question reaches someone that knows the answer they will pass the answer back through the network and the participants in the chain will split the reward.

Further Study

The DARPA challenge was seen as an important real-world test of Query Incentive Networks and sparked more study:

• In “Time Critical Social Mobilization” the authors explore the specific ratio that the MIT MediaLab team used to split the reward (½), and show that it maximizes the network’s incentive to recruit new members.
• In “Finding Red Balloons with Split Contracts” the authors consider the generalized case of incentive networks with fixed payouts (like the balloon example) rather than negotiated payouts (as in the original paper) . They find that this design reduces “selfishness” of the parents, leading to a larger and more efficient network.

Incentive Trees

In “Fair and resilient Incentive Tree mechanisms”, the authors consider what they generally call “Incentive Trees”: systems that reward participants not only for their individual contributions but also for recruiting more participants. They identify two categories of desirable properties in Incentive Trees: 1) that the participant’s reward be proportional to their effort, and 2) Sybil attack resistance.

Interestingly, they find that is may not be possible for a design to strictly satisfy all of the desirable properties that they propose. The reward mechanisms detailed above are generally vulnerable to Sybil attacks (at least in theory). The authors then propose changes to remove the Sybil vulnerability but find that they have to introduce some undesirable features into the mechanism, such as limiting the amount of reward any single node can collect.

Although the author’s find an “impossibility result” in theory, we find the work to be encouraging — we believe the tradeoffs that they highlight are manageable in a smaller, more social setting. We’ll keep incorporating new results into the platform as they arrive — stay tuned!

Please clap and follow for more content from Incentive Exchange! Follow us here Incentive Exchange, and also on Twitter: @i_dot_e