资源描述：
《Mechanism Design for Task Execution via Crowdsourcing》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、MechanismDesignforTimeCriticalandCostCriticalTaskExecutionviaCrowdsourcingSwapravaNath1,PankajDayama2,DineshGarg3,Y.Narahari1,andJamesZou41DepartmentofComputerScienceandAutomation,IndianInstituteofScience,Bangalore,India,{swaprava,hari}@csa.iisc.ernet.in2IBMIndiaResearchLab,Bangal
2、ore,India,pankajdayama@gmail.com3IBMIndiaResearchLab,NewDelhi,India,garg.dinesh@in.ibm.com4HarvardSchoolofEngineeringandAppliedSciences,Cambridge,MA,jzou@fas.harvard.eduAbstract.Anexcitingapplicationofcrowdsourcingistousesocialnet-worksincomplextaskexecution.Inthispaper,weaddresst
3、heproblemofaplannerwhoneedstoincentivizeagentswithinanetworkinordertoseektheirhelpinexecutinganatomictaskaswellasinrecruitingotheragentstoexecutethetask.Westudythismechanismdesignproblemundertwonaturalresourceoptimizationsettings:(1)costcriticaltasks,wheretheplanner’sgoalistominim
4、izethetotalcost,and(2)timecrit-icaltasks,wherethegoalistominimizethetotaltimeelapsedbeforethetaskisexecuted.Weidentifyasetofdesirablepropertiesthatshouldideallybesatisfiedbyacrowdsourcingmechanism.Inparticular,sybil-proofnessandcollapse-proofnessaretwocomplementarypropertiesinourde
5、siderata.Weprovethatnomechanismcansatisfyallthedesirablepropertiessimultaneously.Thisleadsusnaturallytoexploreapproximateversionsofthecriticalproperties.Wefocusourattentiononapproximatesybil-proofnessandourexplorationleadstoaparametrizedfamilyofpay-mentmechanismswhichsatisfycollap
6、se-proofness.Wecharacterizetheapproximateversionsofthedesirablepropertiesincostcriticalandtimecriticaldomain.1IntroductionarXiv:1208.1676v1[cs.GT]8Aug2012AdvancesintheInternetandcommunicationtechnologieshavemadeitpos-sibletoharnessthewisdomandeffortsfromasizableportionofthesocietyt
7、owardsaccomplishingtaskswhichareotherwiseherculean.Examplesincludelabelingmillionsofimages,predictionofstockmarkets,seekinganswerstospe-cificqueries,searchingforobjectsacrossawidegeographicalarea,etc.Thisphe-nomenonispopularlyknownascrowdsourcing(fordetails,seeSurowiecki[10]andHowe
8、[7]).AmazonMechanicalTurkisoneoft
