Distributed Time-Sensitive Task Selection in Mobile Crowdsensing

• Commercial MCS tasks can require data from a precise location and time; on-shelf checks can help managers reduce inventory costs while maintaining stock levels.Source: §1 · p. 1
• Prior work addressed centralized allocation, while this paper considers distributed decisions for information constrained by both location and time.Source: §1 · pp. 1–2
• The proposed ADTS algorithm lets heterogeneous users compute task selections and mobility plans using limited information about aggregate task choices.Source: §1 · p. 2
• The centralized task allocation problem for social-surplus maximization is NP-hard, so the authors also propose a lower-complexity greedy approximation as a benchmark.Source: §1 · p. 2
• The authors describe this as the first study of distributed, time-sensitive and location-dependent MCS data collection motivated by real-life commercial applications.Source: §1 · p. 2

• Each user determines task selections and mobility plans using only limited information about aggregate task choices available in MCS apps.Source: • Asynchronous and distributed task… · p. 2
• Asynchronous best-response updates globally converge to a Nash equilibrium, and each update can be computed in polynomial time.Source: • Asynchronous and distributed task… · p. 2
• ADTS achieves the best reported fairness and coverage among the benchmark algorithms in simulations.Source: • Asynchronous and distributed task… · p. 2

• The platform announces task rewards, locations, and execution times, after which each user chooses how to move and which tasks to perform.Source: Figure 1 · p. 2, §2 · p. 2
• Each task has a required location, execution time, and reward; when multiple users perform it, they share the reward evenly.Source: §2 · p. 2
• User attributes include an initial location, movement times and costs between locations, and an eligible-task set.Source: §2 · p. 2
• Movement times and costs may be computed from Google Maps and local transit data using a specified travel mode; users choose tasks and routes to maximize reward minus movement cost.Source: §2 · p. 3
• Task eligibility can reflect reputation, with higher-reputation users able to access more complicated, higher-paying research tasks.Source: §2 · p. 3

3.1 Task-Time Routing

• An available task-time route is a feasible sequence that starts at the user’s initial virtual task and respects task eligibility and movement-time constraints.Its task times increase, and the interval between successive points matches the travel time between their locations.Source: §3.1 · p. 3

3.2 Task Selection Game

• A user’s payoff is the total time-specific reward earned along her route, with shared rewards divided among participants, minus her movement costs.The provider pays only for claimed tasks completed with acceptable quality.Source: §3.2 · p. 4, §3.4 · p. 5

3.3 Equilibrium Existence and Convergence Analysis

• Every task selection game has the finite improvement property, and each best-response update takes O(K^3T^3) time.Simulations suggest the number of updates to a pure Nash equilibrium grows linearly with users across a wide variety of scenarios.Source: §3.3 · p. 4

3.4 Asynchronous and Distributed Task Selection Algorithm

• ADTS has users asynchronously update best responses using aggregate task-participation information; they need not reveal their movement plans to the service provider.The provider updates participant counts after receiving user messages, while users submit claims for task-time points with positive rewards.Source: §3.4 · pp. 4–5

4.1 Centralized Task Allocation Problem

• The CTA benchmark maximizes social surplus, defined as users’ total rewards minus their total movement costs.It assumes the service provider directly controls all users.Source: §4.1 · p. 5, §4 · p. 5
• Under the assumption that movement cost does not decrease as a user visits more locations, an optimal allocation exists in which each task goes to at most one user.Source: §4.1 · p. 6
• The social-surplus-maximizing task selection game is NP-hard, motivating a heuristic greedy centralized algorithm.Source: §4.1 · p. 6

4.2 Greedy Centralized Task Allocation Algorithm

• The greedy centralized algorithm sorts tasks by earliest execution time, then considers users in increasing movement-cost order, assigning an eligible user who can arrive on time and has incentive to perform the task.The algorithm runs in O(KI log I) time.Source: §4.2 · p. 6

5. PERFORMANCE EVALUATIONS

• The evaluation averages 1,000 simulations with randomized user and task locations and task times, generally placing users and tasks in a 1 km × 1 km region.It compares ADTS, the global-optimal CTA benchmark, approximate greedy centralized GC, and uncoordinated earliest-feasible-task GD.Source: §5 · pp. 6–7

5.1 Average User Payoff and Fairness

• ADTS has the highest fairness index; GC has the lowest because it allocates tasks to at most K users, leaving more users unassigned as I grows.ADTS gives each user an equal chance to update her strategy profile.Source: §5.1 · p. 7, Figure 5 · p. 7

5.2 Coverage and Reward Per Measurement

• ADTS provides slightly higher coverage than GC, while its coverage advantage over GD is large because GD lacks user coordination.Coverage rises with I under all schemes as more users can work on tasks.Source: Figure 6 · p. 7, §5.2 · p. 8
• ADTS and GD have lower average reward per measurement than GC, which can mean more sensing data for the provider at the same total reward.The comparison is for K = 10 and cmove = 0.1; Figure 7 plots the metric against I.Source: Figure 7 · p. 7, §5.2 · p. 8

5.3 Impact of Moving Cost and Speed

• For cmove ≤ 4, GD users can over-select the same task based on the full reward, depressing actual payoffs; above 4, GD payoffs gradually approach nonnegative ADTS and GC levels.Payoffs under ADTS and GC decrease as movement costs rise, and users in those schemes account for reward sharing.Source: Figure 8 · p. 7, §5.3 · p. 8
• As cmove rises, coverage generally falls; as movement speed ν rises, coverage increases under all three schemes, with ADTS slightly above GC.GD's slight coverage increase for cmove ≤ 2 is attributed to inaccurate reward estimation.Source: §5.3 · p. 8, Figure 9 · p. 8, Figure 10 · p. 8

5.4 A Real-World Example Using Google Maps

• In the Google Maps example, ADTS assigns user 1 tasks 3 then 2, while users 2 and 3 take tasks 1 then 2; all three share task 2's $10 reward.The example uses three users and tasks, with user 1 driving and users 2 and 3 walking; the ADTS outcome is described as having high fairness, coverage, and user payoff.Source: §5.4 · pp. 8–9, Figure 11 · p. 8, Table 3 · p. 8

6. CONCLUSION

• ADTS lets users determine task selections and mobility plans in a distributed fashion using limited information about aggregate task choices.The paper examines the problem through both a noncooperative game and centralized optimization.Source: §6 · p. 9
• The social-surplus maximization solution is NP-hard, while ADTS achieves the highest Jain's fairness index and coverage compared with two heuristic schemes in simulations.Source: §6 · p. 9
• The analysis focuses on a fixed set of users; handling users who dynamically join or leave is left for future work.Source: §6 · p. 9

A. PROOF OF THEOREM 1

• The proof shows that Φ is an exact potential function by relating a user's unilateral strategy change to the corresponding change in the potential.Source: A. PROOF OF THEOREM 1 · p. 9
• A finite game with a potential function has the finite improvement property, which the proof applies to the task selection game.Source: A. PROOF OF THEOREM 1 · p. 9
• The derivation expands the left-hand side of equation (18) using equation (12); the cited excerpt identifies this as the way to obtain the expanded expression, without specifying it here.Source: A. PROOF OF THEOREM 1 · p. 9

B. PROOF OF THEOREM 2

• A user's best response is reformulated as a longest path in a weighted directed acyclic graph, giving a polynomial-time solution.Source: B. PROOF OF THEOREM 2 · pp. 10–11
• The graph's vertices represent feasible task-time points and its directed edges represent feasible transitions between them, weighted by negative movement cost.Source: B. PROOF OF THEOREM 2 · p. 10
• Each task-time vertex carries the user's reward after accounting for other users selecting that point; the construction converts vertex values into edge weights for the longest-path formulation.Source: B. PROOF OF THEOREM 2 · p. 10

C. PROOF OF LEMMA 1

• Removing user j's assignment to task q leaves every task covered under the new profile.The proof compares this profile with an optimal profile in which j was assigned to q.Source: C. PROOF OF LEMMA 1 · p. 11
• The proof uses the unchanged movement costs of other users to conclude that the modified profile is also optimal, contradicting its assumption.User j works on one fewer task in the modified profile.Source: C. PROOF OF LEMMA 1 · p. 11

C.1 Discussion of multiple solutions of the social surplus maximization problem

• When task 2 adds no extra movement cost for user 1, assigning it to both users preserves social surplus and yields another optimum.Thus an optimal solution need not be unique or satisfy Lemma 1's form.Source: §C.1 · p. 11

D. PROOF OF THEOREM 3

• A 3-dimensional matching selects triples that do not repeat any element across the three sets; the decision problem asks whether a matching of size M exists.The proof maps tasks across the three time slots to the sets in this matching problem.Source: D. PROOF OF THEOREM 3 · p. 11
• The reduction uses three time slots with M tasks each and enough users whose available routes collectively cover all tasks.Each user chooses one available task-time route, and users whose routes are not selected perform no real task.Source: D. PROOF OF THEOREM 3 · p. 11
• In the restricted setting, rewards exceed movement costs and movement cost depends on destination, so any available users can cover all tasks.The proof also invokes the result that an optimum can be chosen with at most one user assigned to each task.Source: D. PROOF OF THEOREM 3 · p. 12
• The restricted task selection game’s surplus-maximization problem is NP-hard by reduction to 3-dimensional matching, an NP-complete decision problem [5, 9].The proof argues that an optimal allocation corresponds to a matching covering every task exactly once.Source: D. PROOF OF THEOREM 3 · pp. 11–12

E. PROOF OF LEMMA 2

• O(KI log I) is the greedy centralized algorithm’s total runtime for K tasks when I log I > log K.Sorting task execution times takes O(K log K), while sorting users by movement cost for each task takes O(I log I).Source: E. PROOF OF LEMMA 2 · p. 12