An Optimal Reverse Affine Maximizer Auction Mechanism for Task Allocation in Mobile Crowdsensing
Jixian Zhang, Peng Chen, Xuelin Yang, Hao Wu, Weidong Li
Abstract
Mobile crowdsensing service (MCS) providers recruit users to complete data collection tasks with an incentive mechanism. How to maximize the utility of service providers has long been a popular topic in MCS research. Applying the existing reverse auction mechanism to an MCS may result in excessively high payments, thereby reducing the utility of the MCS provider. The affine maximizer auction (AMA) mechanism increases the revenue of service providers and meets dominant-strategy incentive-compatible (DSIC) characteristics. However, the AMA mechanism is a forward auction mechanism and cannot be applied to MCSs. Inspired by the AMA mechanism, this paper innovatively proposes a reverse affine maximizer auction (RAMA) mechanism to solve the task allocation problem of MCSs, effectively improving the MCS provider utility. Specifically, we construct a RAMA theoretical model and prove that the mechanism satisfies DSIC characteristics. For the discrete MCS task allocation problem, we use the reverse virtual valuation combinatorial auction (RVVCA) mechanism, a subclass of RAMA, to design a random mechanism RVVCA<inline-formula><tex-math notation="LaTeX">$^{t}$</tex-math></inline-formula> and prove that the RVVCA<inline-formula><tex-math notation="LaTeX">$^{t}$</tex-math></inline-formula> has a logarithmic approximate ratio. For the differentiable MCS task allocation problem, we use the deep learning transformer framework to design RAMANet, which can fit an exponential number of allocation solutions and output the optimal allocation and payment. We experimentally compare the algorithms of the RAMA family we propose, which use affine maximization, with existing state-of-the-art algorithms, demonstrating that the proposed algorithms significantly improve MCS provider utility.