A Utility-Optimal Reverse Posted Pricing Mechanism for Online Mobile Crowdsensing Task Allocation

In contrast to traditional mechanism design, the posted pricing mechanism can quickly determine the winning user and ensure the revenue of the seller through a predetermined price. Additionally, the posted pricing mechanism inherently possesses economic properties such as truthfulness and individual rationality. These properties make it an ideal method for solving online task allocation problems for mobile crowdsensing services (MCSs). The challenge in posted pricing mechanism design is being able to find reasonable posted prices under complex MCS task constraints. This paper presents an innovative posted pricing mechanism to solve a general point of interest (POI)-based online MCS task allocation problem. We transform the problem into an integer programming model with the goal of maximizing the total utility of the system while satisfying various constraints. We prove that under any user arrival order, there must exist a posted price structure that can ensure that the total utility of the system is approximately optimal, with an approximation ratio of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$1/(d+1)$</tex-math></inline-formula> in the worst case. With the support of theoretical analysis, the posted price calculation can be completed using only a simple gradient descent algorithm. Compared with existing methods, our solution achieves very good results in terms of total utility and the task completion ratio, indicating that it can effectively improve the efficiency and service quality of MCSs.