Computer Science

Computer Science ›› 2023, Vol. 50 ›› Issue (10): 184-192.doi: 10.11896/jsjkx.220900130

• Artificial Intelligence • Previous Articles     Next Articles

Spatial Crowdsourcing Task Pricing Algorithm Based on Nash Bidding

LIN Weida, DONG Hongbin, ZHAO Bingxu   

  1. College of Computer Science and Technology,Harbin Engineering University,Harbin 150001,China
  • Received:2022-09-14 Revised:2023-02-26 Online:2023-10-10 Published:2023-10-10
  • About author:LIN Weida,born in 1998,postgraduate.His main research interests include spatial and crowdsourcing and intelligent computing.DONG Hongbin,born in 1963,Ph.D,professor.His main research interests include computational intelligence,machine learning and data mining.
  • Supported by:
    National Natural Science Foundation of China(61472095) and Natural Science Foundation of Heilongjiang Pro-vince,China(LH2020F023).

PDF (PC)

1558

Abstract: Task pricing is an important step for crowdsourcing platforms to solve profit-driven task allocation and maximize pro-fits.However,there are relatively few studies on task pricing about worker expectations,and most existing studies do not consi-der the dynamic demands of workers and tasks.Furthermore,obtaining complete worker information is difficult due to worker privacy and sensor limitations.In order to solve the above problems,a pricing algorithm for spatial crowdsourcing tasks based on nash bidding is proposed.The algorithm first obtains the price range of the task through the machine learning algorithm,and then conducts nash bidding on the price range.In order to solve the problem of large price fluctuations caused by dynamic supply and demand,an adjustment mechanism is designed to stabilize the average price of tasks.Finally,in order to simulate the Nash equilibrium point,two different gradient functions are used to search for the task price with the largest number of matches.The proposed algorithm is tested on the gMission data set and the synthetic data set respectively.The results show that the algorithm is 60% and 1.57 times of the MCMF algorithm in terms of the number of matches and the average task price,and the time cost is 9.6% of the MCMF algorithm.Experimental results show the effectiveness of the proposed algorithm.

Key words: Nash equilibrium, Task pricing, Worker expectations, Dynamic supply and demand, Incomplete information

CLC Number: 

  • TP391
[1]LI Y,XU W,YIU M L.Client-Side Service for Recommending Rewarding Routes to Mobile Crowdsourcing Workers[J].IEEE Transactions on Services Computing,2021,14(6):1995-2010.
[2]TONG Y,WANG L,ZHOU Z,et al.Flexible online task assignment in real-time spatial data[J].Proceedings of the Vldb Endowment,2017,10(11):1334-1345.
[3]ZHAO Y,ZHENG K,CUI Y,et al.Predictive Task Assignment in Spatial Crowdsourcing:A Data-driven Approach[C]//2020 IEEE 36th International Conference on Data Engineering(ICDE).IEEE,2020.
[4]ZHOU Z,CHEN R,WANG C,et al.Dynamic pricing in profit-driven task assignment:a domain-of-influence based approach[J].International Journal of Machine Learning and Cybernetics,2021,12(2021):1015-1030.
[5]GUO B,YAN L,WU W,et al.ActiveCrowd:A Framework for Optimized Multi-Task Allocation in Mobile Crowdsensing Systems[J].IEEE Transactions on Human-Machine Systems,2017,(3):392-403.
[6]FARBER H S.Why you can't find a taxi in the rain and other labor supply lessons from cab drivers[J].The Quarterly Journal of Economics,2015,130(4):1975-2026.
[7]CHEN Z,FU R,ZHAO Z,et al.gMission:A general spatialcrowdsourcing platform[J].Proceedings of the Vldb Endowment,2014,7(13):1629-1632.
[8]TONG Y X,CHEN L,SHAHABI C.Spatial crowdsourcing:challenges,techniques,and applications[C]//Proceedings of the VLDB Endowment.2017:1988-1991.
[9]TONG Y,CHEN L,SHAHABI C.Spatial crowdsourcing:challenges,techniques,and applications[C]//Very Large Data Bases.VLDB Endowment,2017.
[10]LI X H,DONG H B.Matching modeling and optimization me-thod of ride-sharing trip based on E-CARGO model [J].Computer Applications,2022,42(3):778-782.
[11]PAN Q X,YIN Z X,DONG H B,et al.Task Allocation Algorithm for Space-Time Crowdsourcing Based on Tabu Search [J].Journal of Intelligent Systems,2020,15(6):1040-1048.
[12]GUAN S.Analysis of Optimal Pricing Model of Crowdsourcing Platform Based on Cluster and Proportional Sharing[C]//2018 6th International Symposium on Computational and Business Intelligence(ISCBI).2018.
[13]WANG H,NGUYEN D N,HOANG D T,et al.Real-TimeCrowdsourcing Incentive for Radio Environment Maps:A Dynamic Pricing Approach[C]//2018 IEEE Global Communications Conference(GLOBECOM).IEEE,2019.
[14]TONG Y,WANG L,ZHOU Z,et al.Dynamic pricing in spatial crowdsourcing:A matching-based approach[C]//Proceedings ACM SIGMOD International Conference on Management of Data.2018:773-788.
[15]孙雪峰,张成堂,朱林.考虑企业社会责任的双渠道闭环供应链定价决策研究[J].重庆工商大学学报(自然科学版),2022,39(4):51-59.
[16]XIA H,ZHANG R,CHENG X,et al.Two-Stage Game Design of Payoff Decision-Making Scheme for Crowdsourcing Dilemmas[J].IEEE/ACM Transactions on Networking,2020,28(6):2741-2754.
[17]PENG J,ZHU Y,SHU W,et al.When data contributors meet multiple crowdsourcers:Bilateral competition in mobile crowdsourcing[J].Computer Networks,2016,95(11):1-14.
[18]NIE J,LUO J,XIONG Z,et al.A Stackelberg Game Approach Toward Socially-Aware Incentive Mechanisms for Mobile Crowdsensing[J].IEEE Transactions on Wireless Communications,2019,18(1):724-738.
[19]YANG D,XUE G,XI F,et al.Incentive Mechanisms forCrowdsensing:Crowdsourcing With Smartphones[J].IEEE/ACM Transactions on Networking,2016,24(3):1732-1744.
[20]WANG B,LIU P,ZHANG C,et al.Research on Hybrid Model of Garlic Short-term Price Forecasting based on Big Data[J].Computers,Materials and Continua,2018,57(2):283-296.
[21]BONDE G,KHALED R.Stock price prediction using genetic algorithms and evolution strategies[C]//International Conference on Genetic and Evolutionary Methods.2012.
[22]KARGER D R,OH S,SHAH D.Budget-Optimal Task Allocation for Reliable Crowdsourcing Systems[J].Operations Research,2014,62(1):1-24.
[23]SCHUMAKER R P.Machine learning the harness track:Crowdsourcing and varying race history[J].Decision Support Systems,2013,54(3):1370-1379.
[24]MONDERER D,SHAPLEY L S.Potential games[J].Gamesand economic behavior,1996,14(1):124-143.
[25]NISAN N,ROUGHGARDEN T,TARDOS E,et al.Algorithmic Game Theory[J／OL].https://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=DE1D742A2A81DF238CF38C3F8125ED88?doi=10.1.1.720.4143&rep=rep1&type=pdf.
[26]CHEN L,KYNG R,LIU Y P,et al.Maximum Flow and Minimum-Cost Flow in Almost-Linear Time[J].arXiv:2203.00671,2022.
[1] JIANG Yang-yang, SONG Li-hua, XING Chang-you, ZHANG Guo-min, ZENG Qing-wei. Belief Driven Attack and Defense Policy Optimization Mechanism in Honeypot Game [J]. Computer Science, 2022, 49(9): 333-339.
[2] YUAN Wei-lin, LUO Jun-ren, LU Li-na, CHEN Jia-xing, ZHANG Wan-peng, CHEN Jing. Methods in Adversarial Intelligent Game:A Holistic Comparative Analysis from Perspective of Game Theory and Reinforcement Learning [J]. Computer Science, 2022, 49(8): 191-204.
[3] XU Hao, CAO Gui-jun, YAN Lu, LI Ke, WANG Zhen-hong. Wireless Resource Allocation Algorithm with High Reliability and Low Delay for Railway Container [J]. Computer Science, 2022, 49(6): 39-43.
[4] XUE Zhan-ao, HOU Hao-dong, SUN Bing-xin, YAO Shou-qian. Label-based Approach for Dynamic Updating Approximations in Incomplete Fuzzy Probabilistic Rough Sets over Two Universes [J]. Computer Science, 2022, 49(3): 255-262.
[5] LI Shao-hui, ZHANG Guo-min, SONG Li-hua, WANG Xiu-lei. Incomplete Information Game Theoretic Analysis to Defend Fingerprinting [J]. Computer Science, 2021, 48(8): 291-299.
[6] FU Kun, ZHAO Xiao-meng, FU Zi-tong, GAO Jin-hui, MA Hao-ran. Deep Network Representation Learning Method on Incomplete Information Networks [J]. Computer Science, 2021, 48(12): 212-218.
[7] XUE Zhan-ao, ZHANG Min, ZHAO Li-ping, LI Yong-xiang. Variable Three-way Decision Model of Multi-granulation Decision Rough Sets Under Set-pair Dominance Relation [J]. Computer Science, 2021, 48(1): 157-166.
[8] BAO Jun-bo, YAN Guang-hui, LI Jun-cheng. SIR Propagation Model Combing Incomplete Information Game [J]. Computer Science, 2020, 47(6): 230-235.
[9] HOU Cheng-jun,MI Ju-sheng,LIANG Mei-she. Attribute Reduction Based on Local Adjustable Multi-granulation Rough Set [J]. Computer Science, 2020, 47(3): 87-91.
[10] ZHAI Yong, LIU Jin, LIU Lei, CHEN Jie. Analysis of Private Cloud Resource Allocation Management Based on Game Theory in Spatial Data Center [J]. Computer Science, 2020, 47(11A): 373-379.
[11] LI Fang-wei, ZHOU Jia-wei, ZHANG Hai-bo. Anti-eavesdropping Physical Layer Transmission Scheme Based on Time-reversal in D2D Communication Link [J]. Computer Science, 2019, 46(5): 100-104.
[12] ZENG Jin-song, RAO Yun-bo. Intelligent Classification of Massive Information Based on Conflict Game Algorithm [J]. Computer Science, 2018, 45(8): 208-212.
[13] ZHANG Pan-pan, PENG Chang-gen, HAO Chen-yan. Privacy Protection Model and Privacy Metric Methods Based on Privacy Preference [J]. Computer Science, 2018, 45(6): 130-134.
[14] RAN Zheng, LUO Lei, YAN Hua, LI Yun. Nash Equilibrium Based Method for Mapping AUTOSAR Tasks to Multicore ECU [J]. Computer Science, 2018, 45(6): 166-171.
[15] DING Mian-wei, ZHANG Teng-fei and MA Fu-min. Incremental Attribute Reduction Algorithm Based on Binary Discernibility Matrix in Incomplete Information System [J]. Computer Science, 2017, 44(7): 244-250.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.