A Mechanism Design Approach for Dynamic Task Online Scheduling
TL;DR
Simulation results show that compared with random-bidding protocols, RAMDT reduces the number of rounds for resource equilibrium from exponential to linear in the number of users, and achieves a higher task completion rate than the first-come, first-served (FCFS) scheme.
Abstract
In game-theoretic grid computing, selfish users may misreport task information to obtain individual advantages, leading to prolonged scheduling negotiations and degraded system performance. This study aims to develop the resource allocation mechanism for dynamic tasks (RAMDT), an online scheduling mechanism based on the direct revelation principle. RAMDT incentivizes users to truthfully disclose their private task attributes—value, length, arrival time, and deadline—at the initial bidding stage, thereby accelerating equilibrium convergence, reducing bidding rounds, and minimizing resource waste. Theoretical analysis demonstrates that RAMDT satisfies individual rationality and incentive compatibility, ensuring truthful reporting is a weakly dominant strategy for rational users. Simulation results show that compared with random-bidding protocols, RAMDT reduces the number of rounds for resource equilibrium from exponential to linear in the number of users, and achieves a higher task completion rate than the first-come, first-served (FCFS) scheme. Overall, RAMDT aligns self-interested user behavior with system-wide scheduling efficiency.