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

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.