Hit-or-Wait: Orchestrating the "On-the-Go" Crowd via Decision Theory

TL;DR

On-the-go crowdsourcing promises to solve local problems by tapping into the "spare change" of our daily routines. However, without coordination, these efforts are often redundant or leave gaps. Hit-or-Wait is a new decision-theoretic mechanism that treats trip-based contributions as a sequential optimization problem. By deciding whether to "hit" (notify now) or "wait" (notifying later), the system maximizes the impact of every small contribution without annoying the user.

Background: The Coordination Paradox of the Physical World

In digital crowdsourcing (like Amazon Mechanical Turk), the system can easily route the most important task to an available worker. In the physical world, "workers" are community members walking to lunch or commuting. Their availability is tied to their latitude and longitude.

Previous systems either:

1. Pull-based: Waited for users to check an app (leading to massive missed opportunities).
2. Push-based: Assigned tasks like Uber (highly efficient but disruptive, requiring financial incentives).

Hit-or-Wait seeks the middle ground: Opportunistic Coordination. It asks: "I know you are walking down 5th Ave. Should I ask you to look for a lost cat here, or should I wait because I think you're heading toward an alley that no one has searched yet?"

Methodology: The "Value of Waiting"

The core of the paper is an MDP (Markov Decision Process) framework. The system doesn't just look at what is nearby; it predicts where you are going.

The Formula for Decision

The system solves a recurrence relation where the value of the current policy $V^t(s)$ is the maximum of the reward for hitting now vs. the expected value of future transitions:

System Architecture

To implement this, the authors built a sophisticated backend that includes a Route Manager to map GPS traces to road segments and a Decision Manager that runs the Hit-or-Wait logic based on global task rewards (e.g., the probability an item is in a region given $n$ previous failed searches).

Experimental Insights

The authors validated Hit-or-Wait through two primary lenses:

1. Simulation vs. Reality

Using a large dataset of running routes (RunKeeper), they proved that knowing the "probability of transition" is vital. If task values are uniform, accuracy doesn't matter much. But when task values are varied (e.g., some streets are critical to search, others are redundant), a trained movement model allows Hit-or-Wait to capture 95% of the potential value of a perfectly omniscient system.

2. The Field Study: Trouve

They deployed a lost-and-found app called Trouve.

• Success: 4 items were actually found.
• Efficiency: Waiting for a better road segment increased the contribution's value by over 67%.
• User Experience: Users found 30-second tasks "not disruptive at all" (1.39/5 score), provided they were already passing the area.

The Hidden Factor: Perception of Value

A fascinating finding from the interviews was that people often felt their search was "useless" if they didn't find the item. However, when shown visualizations of how their search filled a gap in a global map, their perceived value increased.

Takeaway for Designers: In on-the-go crowdsourcing, the UI shouldn't just show the task; it should show why this specific person was chosen to do it.

Critical Analysis & Future Work

While robust, the current Hit-or-Wait model is myopic—it treats each user's potential in isolation. A "futuristic" version would account for other users. If the system knows a high-probability helper is coming in 10 minutes, it might "save" a user now for a different task.

Another limitation is terminal state prediction. The system occasionally missed opportunities because a user simply went home (stopped moving) before reaching the "better" task the system was waiting for.

Conclusion

Hit-or-Wait moves physical crowdsourcing from "random acts of kindness" toward "coordinated collective intelligence." By using MDPs to value the future over the present, we can solve massive spatial problems—one routine walk at a time.