I detta dokument anser vi att det finns ett problem med mekanismens utformning i samband med storskaliga crowdsourcingmarknader som Amazons Mechanical Turk (MTRK), ClickWorker (CLKWRKR), CrowdFlower (CRDFLWR). På dessa marknader finns det en beställare som vill anställa arbetstagare för att utföra vissa uppgifter. Varje arbetare antas ge någon nytta till den som begär anställning. Dessutom har varje arbetstagare en minimikostnad som han vill få betalt för att få anställning. Denna minimikostnad antas vara den privata informationen till arbetstagarna. Frågan är då - om beställaren har en begränsad budget, hur man utformar en direkt uppenbarelse mekanism som väljer rätt uppsättning arbetstagare att anställa för att maximera den begärandes nytta? Vi noterar att även om det tidigare arbetet (Singer (2010); Chen et al. (2011) har studerat detta problem, en avgörande skillnad där vi avviker från tidigare arbete är begreppet storskaliga marknader som vi introducerar i vår modell. Utan det stora antagandet på marknaden är det känt att ingen mekanism kan uppnå ett konkurrensförhållande som är bättre än 0,414 respektive 0,5 för deterministiska respektive randomiserade mekanismer (medan de mest kända deterministiska och randomiserade mekanismerna uppnår ett approximationsförhållande på 0,292 respektive 0,33). I detta dokument utformar vi en budgetgenomförbar mekanism för stora marknader som uppnår ett konkurrensförhållande på 1 – 1 – 1 – e 0,63. Vår mekanism kan ses som en generalisering av ett alternativt sätt att se på den proportionella delningsmekanismen, som används i alla tidigare arbeten hittills på detta problem. Det är intressant att lägga märke till att vi också kan visa att vår mekanism är optimal genom att visa att ingen sanningsenlig mekanism kan uppnå en faktor som är bättre än 1 – 1 e; alltså helt och hållet lösa denna situation. Slutligen överväger vi det mer allmänna fallet med submodulära allmännyttiga funktioner och ger nya och förbättrade mekanismer för fallet när marknaden är stor.
En bättre approximation för en budget genomförbar mekanism är känd när man har en ytterligare "stora marknader" antagande Ref.
Mechanism Design for Crowdsourcing: An Optimal 1-1/e Competitive Budget-Feasible Mechanism for Large Markets
{'venue': '2014 IEEE 55th Annual Symposium on Foundations of Computer Science', 'journal': '2014 IEEE 55th Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}