An official website of the United States government
Crowdsourcing has become an efficient paradigm to utilize human intelligence to perform tasks that are challenging for machines. Many incentive mechanisms for crowdsourcing systems have been proposed. However, most of existing incentive mechanisms assume that there are sufficient participants to perform crowdsourcing tasks. In large-scale crowdsourcing scenarios, this assumption may be not applicable. To address this issue, we diffuse the crowdsourcing tasks in social network to increase the number of participants. To make the task diffusion more applicable to crowdsourcing system, we enhance the classic Independent Cascade model so the influence is strongly connected with both the types and topics of tasks. Based on the tailored task diffusion model, we formulate the Budget Feasible Task Diffusion ( BFTD ) problem for maximizing the value function of platform with constrained budget. We design a parameter estimation algorithm based on Expectation Maximization algorithm to estimate the parameters in proposed task diffusion model. Benefitting from the submodular property of the objective function, we apply the budget-feasible incentive mechanism, which satisfies desirable properties of computational efficiency, individual rationality, budget-feasible, truthfulness, and guaranteed approximation, to stimulate the task diffusers. The simulation results based on two real-world datasets show that our incentive mechanism can improve the number of active users and the task completion rate by 9.8% and 11%, on average.
more »
« less
Sybil-Proof Online Incentive Mechanisms for Crowdsensing
Crowdsensing leverages the rapid growth of sensor-embedded smartphones and human mobility for pervasive information collection. To incentivize smartphone users to participate in crowdsensing, many auction-based incentive mechanisms have been proposed for both offline and online scenarios. It has been demonstrated that the Sybil attack may undermine these mechanisms. In a Sybil attack, a user illegitimately pretends multiple identities to gain benefits. Sybil-proof incentive mechanisms have been proposed for the offline scenario. However, the problem of designing Sybil-proof online incentive mechanisms for crowdsensing is still open. Compared to the offline scenario, the online scenario provides users one more dimension of flexibility, i.e., active time, to conduct Sybil attacks, which makes this problem more challenging. In this paper, we design Sybil-proof online incentive mechanisms to deter the Sybil attack for crowdsensing. Depending on users’ flexibility on performing their tasks, we investigate both single-minded and multi-minded cases and propose SOS and SOM, respectively. SOS achieves computational efficiency, individual rationality, truthfulness, and Sybil-proofness. SOM achieves individual rationality, truthfulness, and Sybil-proofness. Through extensive simulations, we evaluate the performance of SOS and SOM.
more »
« less
- Award ID(s):
- 1717197
- PAR ID:
- 10076448
- Date Published:
- Journal Name:
- IEEE INFOCOM
- Page Range / eLocation ID:
- 2438
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Recently, Graph Neural Networks (GNNs) have been applied for scheduling jobs over clusters, achieving better performance than hand-crafted heuristics. Despite their impressive performance, concerns remain over whether these GNN-based job schedulers meet users’ expectations about other important properties, such as strategy-proofness, sharing incentive, and stability. In this work, we consider formal verification of GNN-based job schedulers. We address several domain-specific challenges such as networks that are deeper and specifications that are richer than those encountered when verifying image and NLP classifiers. We develop vegas, the first general framework for verifying both single-step and multi-step properties of these schedulers based on carefully designed algorithms that combine abstractions, refinements, solvers, and proof transfer. Our experimental results show that vegas achieves significant speed-up when verifying important properties of a state-of-the-art GNN-based scheduler compared to previous methods.more » « less
-
Böhme, Rainer; Kiffer, Lucianna (Ed.)The incentive-compatibility properties of blockchain transaction fee mechanisms have been investigated with passive block producers that are motivated purely by the net rewards earned at the consensus layer. This paper introduces a model of active block producers that have their own private valuations for blocks (representing, for example, additional value derived from the application layer). The block producer surplus in our model can be interpreted as one of the more common colloquial meanings of the phrase "maximal extractable value (MEV)." We first prove that transaction fee mechanism design is fundamentally more difficult with active block producers than with passive ones: With active block producers, no non-trivial or approximately welfare-maximizing transaction fee mechanism can be incentive-compatible for both users and block producers. These results can be interpreted as a mathematical justification for augmenting transaction fee mechanisms with additional components such as order flow auctions, block producer competition, trusted hardware, or cryptographic techniques. We then consider a more fine-grained model of block production that more accurately reflects current practice, in which we distinguish the roles of "searchers" (who actively identify opportunities for value extraction from the application layer and compete for the right to take advantage of them) and "proposers" (who participate directly in the blockchain protocol and make the final choice of the published block). Searchers can effectively act as an "MEV oracle" for a transaction fee mechanism, thereby enlarging the design space. Here, we first consider a TFM that is inspired by how searchers have traditionally been incorporated into the block production process, with each transaction effectively sold off to a searcher through a first-price auction. We then explore the TFM design space with searchers more generally, and design a mechanism that circumvents our impossibility results for TFMs without searchers. Our mechanism (the "SAKA" mechanism) is incentive-compatible (for users, searchers, and the block producer), sybil-proof, and guarantees roughly 50% of the maximum-possible welfare when transaction sizes are small relative to block sizes. We conclude with a matching negative result: even when transaction sizes are small, no DSIC and sybil-proof deterministic TFM can guarantee more than 50% of the maximum-possible welfare.more » « less
-
A major challenge in mobile crowdsensing applications is the generation of false (or spam) contributions resulting from selfish and malicious behaviors of users, or wrong perception of an event. Such false contributions induce loss of revenue owing to undue incentivization, and also affect the operational reliability of the applications. To counter these problems, we propose an event-trust and user-reputation model, called QnQ, to segregate different user classes such as honest, selfish, or malicious. The resultant user reputation scores, are based on both `quality' (accuracy of contribution) and `quantity' (degree of participation) of their contributions. Specifically, QnQ exploits a rating feedback mechanism for evaluating an event-specific expected truthfulness, which is then transformed into a robust quality of information (QoI) metric to weaken various effects of selfish and malicious user behaviors. Eventually, the QoIs of various events in which a user has participated are aggregated to compute his reputation score, which in turn is used to judiciously disburse user incentives with a goal to reduce the incentive losses of the CS application provider. Subsequently, inspired by cumulative prospect theory (CPT), we propose a risk tolerance and reputation aware trustworthy decision making scheme to determine whether an event should be published or not, thus improving the operational reliability of the application. To evaluate QnQ experimentally, we consider a vehicular crowdsensing application as a proof-of-concept. We compare QoI performance achieved by our model with Jøsang's belief model, reputation scoring with Dempster-Shafer based reputation model, and operational (decision) accuracy with expected utility theory. Experimental results demonstrate that QnQ is able to better capture subtle differences in user behaviors based on both quality and quantity, reduces incentive losses, and significantly improves operational accuracy in presence of rogue contributionsmore » « less
-
IEEE (Ed.)Vehicular crowdsensing (VCS) is a subset of crowd-sensing where data collection is outsourced to group vehicles. Here, an entity interested in collecting data from a set of Places of Sensing Interest (PsI), advertises a set of sensing tasks, and the associated rewards. Vehicles attracted by the offered rewards deviate from their ongoing trajectories to visit and collect from one or more PsI. In this win-to-win scenario, vehicles reach their final destination with the extra reward, and the entity obtains the desired samples. Unfortunately, the efficiency of VCS can be undermined by the Sybil attack, in which an attacker can benefit from the injection of false vehicle identities. In this paper, we present a case study and analyze the effects of such an attack. We also propose a defense mechanism based on generative adversarial neural networks (GANs). We discuss GANs' advantages, and drawbacks in the context of VCS, and new trends in GANs' training that make them suitable for VCS.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
