Truthful Mechanisms for Competitive Reward-Based Scheduling

摘要

We consider a competitive environment for reward-based scheduling of periodic tasks, where the execution of each task consists of a mandatory and an optional part. Each task obtains a value if the processor successfully schedules all its mandatory part, and also an additional reward value if the processor successfully schedules a part of its optional execution. Each task is owned by a self-interested agent who has multiple choices for its requests based on its optional part. We model the reward-based scheduling problem by considering such multi-minded agents. However, the agent may try to manipulate the system to obtain an unfair optional allocation. We address this challenge by designing novel truthful mechanisms in which it is always in the agent's best interest to report their true task characteristics. We propose two truthful mechanisms (an exact and approximate) for selecting a feasible subset of agents and an allocation of optional execution that maximizes the total reward obtained by the selected tasks. To address the pseudo-polynomial complexity of the exact mechanism, we show that our proposed approximate mechanism is a polynomial-time approximation scheme (PTAS). Our extensive experiments show that our proposed approximation mechanism is capable of finding near-optimal solutions efficiently while guaranteeing truthfulness.