Truthful job scheduling is a mechanism design variant of the job shop scheduling problem from operations research.
Our goal is to allocate jobs to workers such that the total makespan of the project is minimized.
In contrast, in the truthful job scheduling problem, the timings of the workers are not known.
Therefore, we have to give the workers an incentive to tell us their true timings by paying them a certain amount of money.
The challenge is to design a payment mechanism which is incentive compatible.
The truthful job scheduling problem was introduced by Nisan and Ronen in their 1999 paper on algorithmic mechanism design.
workers ("m" stands for "machine", since the problem comes from scheduling jobs to computers).
of jobs to workers, The makespan of a project is: An optimal allocation is an allocation of jobs to workers in which the makespan is minimized.
A mechanism is a function that takes as input the matrix
, under such mechanism, is: I.e, the agent gains the payment, but loses the time that it spends in executing the tasks.
Note that payment and time are measured in the same units (e.g., we can assume that the payments are in dollars and that each time-unit costs the worker one dollar).
A mechanism is called truthful (or incentive compatible) if every worker can attain a maximum utility by reporting his true timing vector (i.e., no worker has an incentive to lie about his timings).
(smaller is better; an approximation factor of 1 means that the mechanism is optimal).
The research on truthful job scheduling aims to find upper (positive) and lower (negative) bounds on approximation factors of truthful mechanisms.
Here, we can use VCG to find an allocation which minimizes the "make-total", defined as: Here, minimizing the sum can be done by simply allocating each job to the worker who needs the shortest time for that job.
On the other hand, there are some impossibility results that prove that the approximation factor cannot be too small.
[1]: 177- The proof is typical of lower bounds in mechanism design.
This induces some constraints on the allocations returned by the mechanism in the different scenarios.
In the following proof sketch, for simplicity we assume that there are 2 workers and that the number of jobs is even,
Archer and Tardos[2] prove that a scheduling algorithm is truthful if and only if it is monotone.
This means that, if a machine reports a higher speed, and all other inputs remain the same, then the total processing time allocated to the machine weakly increases.