Truthful job scheduling

Truthful job scheduling is a <a href="/facts/Mechanism_design/l3Uj6wfe">mechanism design</a> variant of the <a href="/facts/Job_shop_scheduling/1JjAvD3m">job shop scheduling</a> problem from <a href="/facts/Operations_research/H5yJkV5n">operations research</a>.
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 <a href="/facts/Makespan/w1HEjJaQ">makespan</a> 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 <a href="/facts/Incentive_compatible/pE8NEGNx">incentive compatible</a>.
The truthful job scheduling problem was introduced by Nisan and Ronen in their 1999 paper on <a href="/facts/Algorithmic_mechanism_design/Lc9Q7Fre">algorithmic mechanism design</a>.

Truthful job scheduling open-in-new

Truthful job scheduling