International Joint Conference On Theoretical Computer Science – Frontier of Algorithmic Wisdom

August 15-19, 2022, City University of Hong Kong, Hong Kong


Invited Speakers

Track A

Verifiable Crowd Computing: Coping with Bounded Rationality

Lu Dong

Pace University

In this paper we use the repeated-games framework to design and analyze a master-worker (MW) mechanism, where a master repeatedly outsources computational tasks to workers in exchange for payment. Previous work on MW models assume that all workers are perfectly rational and aim to maximize their expected utility. Perfect rationality is a strong behavioral assumption because it requires that all workers follow the prescribed equilibrium. Such a model may be unrealistic in a practical setting, where some agents are not perfectly rational and may deviate from the equilibrium for short-term gains. Since the correctness of these MW protocols relies on workers following the equilibrium strategies, they are not robust against such deviations.
We augment the game-theoretical MW model with the presence of such bounded-rational players or deviators. In particular, we show how to design a repeated-games based MW Verifiable Crowd Computing mechanism that incentivizes the rational workers (or followers) to effectively punish such deviators through the use of terminal payments. We show that the master can use terminal payments to obtain correct answers to computational problems even in this more general model. We supplement our theoretical results with simulations that show that our mechanism outperforms related approaches.

Lu Dong is a PhD candidate in the Computer Science Department at Pace University. He received his master degree in Computer Science from Pace University and bachelor degree in Mathematics from University College London. His current research interests includes distributed computing with constrained resources, machine learning assisted algorithms for Wireless Networks, etc.