Profit Maximization in Mobile Crowdsourcing: A Competitive Analysis
Mobile Crowdsourcing, which uses a crowd of workers to complete computer-complexity tasks, has become more and more popular. How to maximize the total profit, which is the difference between total task utility and total worker costs, is a key design goal in such crowdsourcing system. However, this p...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2021-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9352787/ |
| _version_ | 1819276896752369664 |
|---|---|
| author | Qi Li Lijun Cai Huanle Xu Tao Meng |
| author_facet | Qi Li Lijun Cai Huanle Xu Tao Meng |
| author_sort | Qi Li |
| collection | DOAJ |
| description | Mobile Crowdsourcing, which uses a crowd of workers to complete computer-complexity tasks, has become more and more popular. How to maximize the total profit, which is the difference between total task utility and total worker costs, is a key design goal in such crowdsourcing system. However, this problem is extremely hard because even in the offline situation, this problem has been proved to be NP-hard. In the online situation, we need to consider not only future unknown task arrivals, but also the heterogeneity of both tasks and workers. In this paper, we address this challenging problem from following aspects. To solve this problem, we first build an optimization framework to formulate this problem by explicitly modelling task utility and worker costs. Then, under this framework, we design efficient online assignment algorithms to assign tasks to workers. To analyze the efficiency of our proposed algorithms, we develop a dual-fitting method to analyze both primal objective and dual objective. We prove that our designed algorithms can achieve a constant competitive ratio of 2. Finally, we conduct extensive trace-driven simulations to demonstrate that the online algorithms can outperform baseline algorithms by nearly 20% in terms of the total profit achieved. |
| first_indexed | 2024-12-23T23:47:30Z |
| format | Article |
| id | doaj.art-92180b4f95544fe2ae71379982469d34 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-23T23:47:30Z |
| publishDate | 2021-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-92180b4f95544fe2ae71379982469d342022-12-21T17:25:29ZengIEEEIEEE Access2169-35362021-01-019278272783910.1109/ACCESS.2021.30587899352787Profit Maximization in Mobile Crowdsourcing: A Competitive AnalysisQi Li0https://orcid.org/0000-0002-1774-6955Lijun Cai1Huanle Xu2Tao Meng3https://orcid.org/0000-0002-9787-2002College of Computer Science and Electronic Engineering, Hunan University, Changsha, ChinaDepartment of Information Engineering, The Chinese University of Hong Kong, Hong KongDepartment of Information Engineering, The Chinese University of Hong Kong, Hong KongCollege of Computer and Information Engineering, Central South University of Forestry and Technology, Changsha, ChinaMobile Crowdsourcing, which uses a crowd of workers to complete computer-complexity tasks, has become more and more popular. How to maximize the total profit, which is the difference between total task utility and total worker costs, is a key design goal in such crowdsourcing system. However, this problem is extremely hard because even in the offline situation, this problem has been proved to be NP-hard. In the online situation, we need to consider not only future unknown task arrivals, but also the heterogeneity of both tasks and workers. In this paper, we address this challenging problem from following aspects. To solve this problem, we first build an optimization framework to formulate this problem by explicitly modelling task utility and worker costs. Then, under this framework, we design efficient online assignment algorithms to assign tasks to workers. To analyze the efficiency of our proposed algorithms, we develop a dual-fitting method to analyze both primal objective and dual objective. We prove that our designed algorithms can achieve a constant competitive ratio of 2. Finally, we conduct extensive trace-driven simulations to demonstrate that the online algorithms can outperform baseline algorithms by nearly 20% in terms of the total profit achieved.https://ieeexplore.ieee.org/document/9352787/Task utilityworker costsonline task assignmentsdual-fitting methodcompetitive performance |
| spellingShingle | Qi Li Lijun Cai Huanle Xu Tao Meng Profit Maximization in Mobile Crowdsourcing: A Competitive Analysis IEEE Access Task utility worker costs online task assignments dual-fitting method competitive performance |
| title | Profit Maximization in Mobile Crowdsourcing: A Competitive Analysis |
| title_full | Profit Maximization in Mobile Crowdsourcing: A Competitive Analysis |
| title_fullStr | Profit Maximization in Mobile Crowdsourcing: A Competitive Analysis |
| title_full_unstemmed | Profit Maximization in Mobile Crowdsourcing: A Competitive Analysis |
| title_short | Profit Maximization in Mobile Crowdsourcing: A Competitive Analysis |
| title_sort | profit maximization in mobile crowdsourcing a competitive analysis |
| topic | Task utility worker costs online task assignments dual-fitting method competitive performance |
| url | https://ieeexplore.ieee.org/document/9352787/ |
| work_keys_str_mv | AT qili profitmaximizationinmobilecrowdsourcingacompetitiveanalysis AT lijuncai profitmaximizationinmobilecrowdsourcingacompetitiveanalysis AT huanlexu profitmaximizationinmobilecrowdsourcingacompetitiveanalysis AT taomeng profitmaximizationinmobilecrowdsourcingacompetitiveanalysis |