Truthful job scheduling

Truthful job scheduling is a mechanism design variant of the job shop scheduling problem from operations research.
We have a project composed of several "jobs" (tasks). There are several workers. Each worker can do any job, but for each worker it takes a different amount of time to complete each job. Our goal is to allocate jobs to workers such that the total makespan of the project is minimized. In the standard job shop scheduling problem, the timings of all workers are known, so we have a standard optimization problem. In contrast, in the truthful job scheduling problem, the timings of the workers are not known. We ask each worker how much time he needs to do each job, but, the workers might lie to us. 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.
Definitions.
There are formula_1 jobs and formula_2 workers ("m" stands for "machine", since the problem comes from scheduling jobs to computers). Worker formula_3 can do job formula_4 in time formula_5. If worker formula_3 is assigned a set of jobs formula_7, then he can execute them in time:
Given an allocation formula_9 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. The minimum makespan is denoted by formula_11.
A "mechanism" is a function that takes as input the matrix formula_12 (the time each worker needs to do each job) and returns as output:
The utility of worker formula_3, 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).
The "approximation factor" of a mechanism is the largest ratio between formula_17 and formula_18 (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.
Positive bound – m – VCG mechanism.
The first solution that comes to mind is VCG mechanism, which is a generic truthful mechanism. A VCG mechanism can be used to minimize the sum of costs. 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. To keep the mechanism truthful, each worker that accepts a job is paid the second-shortest time for that job (like in a Vickrey auction).
Let OPT be an allocation which minimizes the makespan. Then:
(where the last inequality follows from the pigeonhole principle). Hence, the approximation factor of the VCG solution is at most formula_2 – the number of workers.
The following example shows that the approximation factor of the VCG solution can indeed be exactly formula_2. Suppose there are formula_23 jobs and the timings of the workers are as follows:
Then, the VCG mechanism allocates all tasks to worker 1. Both the "make-total" and the makespan are formula_23. But, when each job is assigned to a different worker, the makespan is formula_24.
An approximation factor of formula_2 is not very good, and many researchers have tried to improve it over the following years.
On the other hand, there are some impossibility results that prove that the approximation factor cannot be too small.
Negative bound – 2.
The approximation factor of every truthful deterministic mechanism is at least 2.
The proof is typical of lower bounds in mechanism design. We check specific scenarios (in our case, specific timings of the workers). By truthfulness, when a single worker changes his declaration, he must not be able to gain from it. 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, formula_29. We consider the following scenarios:
Hence, the approximation factor of the mechanism must be at least 2.