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

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

 

Accepted Papers

Track H


Budget-Feasible Sybil-Proof Mechanisms for Crowdsensing

Xiang Liu, Weiwei Wu, Wanyuan Wang, Yuhang Xu, Xiumin Wang, Helei Cui

Abstract:
The rapid use of smartphones and devices leads to the development of crowdsensing (CS) systems where a large crowd of participants can take part in performing data collecting tasks in large-scale distributed networks. Participants/users in such systems are usually selfish and have private information, such as costs and identities. Budget-feasible mechanism design, as a sub-field of auction theory, is a useful paradigm for crowdsensing, which naturally formulates the procurement scenario with buyers’ budgets being considered and allows the users to bid their private costs. Although the bidding behavior is well-regulated, budget-feasible mechanisms are still vulnerable to the Sybil attack where users may generate multiple fake identities to manipulate the system. Thus, it is vital to provide Sybil-proof budget-feasible mechanisms for crowdsensing. In this paper, we design a budget-feasible incentive mechanism which can guarantee truthfulness and deter Sybil attack. We prove that the proposed mechanism achieves individual rationality, truthfulness, budget feasibility, and Sybil-proofness. Extensive simulation results further validate the efficiency of the proposed mechanism.