Algorithmic Mechanisms for Reliable Crowdsourcing Computation under Collusion |
| |
Authors: | Antonio Fernández Anta Chryssis Georgiou Miguel A Mosteiro Daniel Pareja |
| |
Institution: | 1. IMDEA Networks Institute, Madrid, Spain.; 2. Dept. of Computer Science, University of Cyprus, Nicosia, Cyprus.; 3. Dept. of Computer Science, Kean University, Union, New Jersey, United States of America.; Tianjin University of Technology, CHINA, |
| |
Abstract: | We consider a computing system where a master processor assigns a task for execution to worker processors that may collude. We model the workers’ decision of whether to comply (compute the task) or not (return a bogus result to save the computation cost) as a game among workers. That is, we assume that workers are rational in a game-theoretic sense. We identify analytically the parameter conditions for a unique Nash Equilibrium where the master obtains the correct result. We also evaluate experimentally mixed equilibria aiming to attain better reliability-profit trade-offs. For a wide range of parameter values that may be used in practice, our simulations show that, in fact, both master and workers are better off using a pure equilibrium where no worker cheats, even under collusion, and even for colluding behaviors that involve deviating from the game. |
| |
Keywords: | |
|
|