2014 · 388 citations · 21 references
ComputingComputer ScienceAlgorithmsAuction TheoryMobile ComputingAuction DesignCombinatorial AuctionsMobile SensingCollaborative SensingLocation AwarenessPolynomial Time ComplexityPolynomial-time AlgorithmsReverse Auction PlatformsTruthful BiddingTruthful Mechanism DesignWinner Determination Problem
In this paper, we tackle the problem of stimulating smartphone users to join mobile crowdsourcing applications with smartphones. Different from existing work of mechanism design, we uniquely take into consideration the crucial dimension of location information when assigning sensing tasks to smartphones. However, the location awareness largely increases the theoretical and computational complexity. In this paper, we introduce a reverse auction framework to model the interactions between the platform and the smartphones. We rigorously prove that optimally determining the winning bids is NP hard. In this paper we design a mechanism called TRAC which consists of two main components. The first component is a near-optimal approximate algorithm for determining the winning bids with polynomial-time computation complexity, which approximates the optimal solution within a factor of 1 + ln(n), where n is the maximum number of sensing tasks that a smartphone can accommodate. The second component is a critical payment scheme which, despite the approximation of determining winning bids, guarantees that submitted bids of smartphones reflect their real costs of performing sensing tasks. Through both rigid theoretical analysis and extensive simulations, we demonstrate that the proposed mechanism achieves truthfulness, individual rationality and high computation efficiency.
21
Anshul Rai, Krishna Chintalapudi, Venkata N. Padmanabhan et al. · 2012 · 1K citations
Dejun Yang, Guoliang Xue, Xi Fang et al. · 2012 · 1K citations
Arvind Thiagarajan, Lenin Ravindranath, Katrina LaCurts et al. · 2009 · 784 citations
Rajib Rana, Chun Tung Chou, Salil S. Kanhere et al. · 2010 · 708 citations