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 finis 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. 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 $n$ jobs and $m$ workers ("m" stands for "machine", since the problem comes from scheduling job streams to computers). Worker $i$ can do job $j$ in time $t_{i,j}$. If worker $i$ is assigned a set of jobs $J_{i}$, then he can execute them in time:

$t_{i}(J_{i})=\sum _{j\in J_{i}}t_{i,j}$

Given an allocation $J_{1},\dots ,J_{m}$ of jobs to workers, The makespan of a project is:

$Makespan(J_{1},\dots ,J_{n})=\max _{i}{t_{i}(J_{i})}$